Sammendrag
Data exchange heavily relies on the notion of incomplete database instances. Several semantics
for such instances have been proposed and include open (OWA), closed (CWA), and open-closed
(OCWA) world. For all these semantics important questions are: whether one incomplete instance
semantically implies another; when two are semantically equivalent; and whether a smaller or
smallest semantically equivalent instance exists. For OWA and CWA these questions are fully
answered. For several variants of OCWA, however, they remain open. In this work we adress these
questions for Closed Powerset semantics and the OCWA semantics of [24]. We define a new OCWA
semantics, called OCWA*, in terms of homomorphic covers that subsumes both semantics, and
characterize semantic implication and equivalence in terms of such covers. This characterization
yields a guess-and-check algorithm to decide equivalence, and shows that the problem is NP-complete.
For the minimization problem we show that for several common notions of minimality there is in
general no unique minimal equivalent instance for Closed Powerset semantics, and consequently not
for the more expressive OCWA* either. However, for Closed Powerset semantics we show that one
can find, for any incomplete database, a unique finite set of its subinstances which are subinstances
(up to renaming of nulls) of all instances semantically equivalent to the original incomplete one. We
study properties of this set, and extend the analysis to OCWA*
Vis fullstendig beskrivelse