Beschreibung:
<jats:p>
We represent a
<jats:italic>set of possible worlds</jats:italic>
using an incomplete information database. The representation techniques that we study form a hierarchy, which generalizes relations of constants. This hierarchy ranges from the very simple Codd-table, (i e , a relation of constants and distinct variables called nulls, which stand for values present but unknown), to much more complex mechanisms involving views on conditioned-tables, (i e , queries on Codd-tables together with conditions). The views we consider are the queries that have polynomial data-complexity on complete information databases. Our conditions are conjunctions of equalities and inequalities.
</jats:p>
<jats:p>
(1) We provide matching upper and lower bounds on the data-complexity of testing
<jats:italic>containement</jats:italic>
,
<jats:italic>membership</jats:italic>
, and
<jats:italic>uniqueness</jats:italic>
for sets of possible worlds and we fully classify these problems with respect to our representation hierarchy. The most surprising result in this classification is that it is complete in
<jats:italic>Π</jats:italic>
<jats:sub>2</jats:sub>
<jats:sup>p</jats:sup>
, whether a set of possible worlds represented by a Codd-table is a subset of a set of possible worlds represented by a Codd-table with one conjuction of inequalities.
</jats:p>
<jats:p>
(2) We investigate the data-complexity of querying incomplete information databases. We examine both asking for
<jats:italic>certain facts</jats:italic>
and for
<jats:italic>possible facts</jats:italic>
. Our approach is algebraic but our bounds also apply to logical databases. We show that asking for a certain fact is coNP-complete, even for a fixed first order query on a Codd-table. We thus strengthen a lower bound of [16], who showed that this holds for a Codd-table with a conjunction of inequalities. For each fixed positive existential query we present a polynomial algorithm solving the bounded possible fact problem of this query on conditioned-tables. We show that our approach is, in a sense, the best possible, by deriving two NP-completeness lower bounds for the bounded possible fact problem when the fixed query contains either negation or recursion.
</jats:p>