Alternative semantics - Foundations of Data Exchange - page 100

Recall from Theorem 7.4 that computing certain answers to conjunctive queries with
inequalities is an intractable problem. But Example 8.3 above showed that for this class
of queries, the usual certain answers need not coincide with the universal certain answers.
This suggests that it may still be possible to compute universal certain answers for conjunc-
tive queries with inequalities in polynomial time. We will actually state a much stronger
result in Theorem 8.5 : under the universal certain answers semantics, we have tractabil-
ity of query answering for a big and practically relevant class of FO queries that extends
unions of conjunctive queries.
Roughly, an existential FO query is given by an FO formula of the form

∃ y ϕ ( x , y ),where

ϕ ( x , y ) is a quantifier-free formula in disjunctive normal form satisfying a safety condition.

More precisely, it is given by a formula of the form

y
i j α ij ,

ψ ( x )= ∃

where

• each α ij is either an atomic formula, or the negation of an atomic formula;

• the free variables of each α ij come from x , y ;and

• (safety condition) if α ij is a negated atom, i.e., of the form ¬ R ( z ), then each variable in

z must occur in some formula α ij which is a nonnegated atom.

For example, both unions of conjunctive queries, and unions of conjunctive queries with
inequalities and negated atoms satisfy these three conditions.
Existential formulae ψ are known to be monotone in the following sense. If I is an
induced sub-instance of I and t belongs to the evaluation of

over I ,then t belongs to the

ψ

over I . Recall that an induced sub-instance I of an instance I is given by a

evaluation of ψ

set A ⊆ D OM ( I ); it contains exactly all the tuples of I whose elements come from A .

Since every universal solution contains a copy of the core as an induced sub-instance,
we conclude that the problem of computing the universal certain answers for an existential
FO query over the core of the universal solutions, discarding

all tuples that contain nulls. Thus, in order to compute the universal certain answers of an
existential Q with respect to a source instance S , one can use the following procedure.

ψ boils down to evaluating ψ

Recall from Theorem 6.18 that the core of the universal solutions can be computed in
polynomial time for every mapping whose sets of target dependencies consists of a set of
egds and a weakly acyclic set of tgds. Furthermore, existential queries are FO queries and
thus have polynomial time data complexity. Putting these two things together we obtain
the following positive result.

Theorem 8.5 Σ t consists of

a set of egds and a weakly acyclic set of tgds, and let Q be an existential query over R t .
Then the algorithm C OMPUTE U NIVERSAL C ERTAIN A NSWERS (Q,

Let M =(R s , R t , Σ st , Σ t ) be a relational mapping such that

M ) correctly computes

universal certain answers of Q with respect to a source S under M in polynomial time.