Query answering and rewriting - Foundations of Data Exchange - page 81

We leave it as a simple exercise to the reader to prove that ϕ is satisfiable iff

certain M ( Q , S ϕ )= false . This finishes the proof of the theorem.

Notice that the query Q constructed in the proof of the previous theorem contains exactly
three inequalities. But this can be strengthened, as there is a Boolean conjunctive query Q
with exactly two inequalities and a L AV mapping

such that CERTAIN M ( Q ) is CO NP-
hard. We leave the proof of this fact as an interesting exercise for the reader. For the class
of (unions of) conjunctive queries with at most one inequality per disjunct, the certain
answers can be computed in polynomial time. We explain how this can be done in the next
section.

M

Summary
Summing up, conjunctive queries with inequalities do not retain the good properties of
unions of conjunctive queries for data exchange. In particular, while the problem of com-
puting certain answers for conjunctive queries with inequalities remains decidable, it be-
comes intractable even in the absence of target dependencies. However, this still leaves
open the question of whether the class of unions of conjunctive queries can be extended
with a limited amount of negation in such a way that:

1. The extension preserves the good properties of conjunctive queries for data exchange;
and
2. it also allows expressing relevant data exchange properties.

We show how to construct such language in the next section.

7.4 Tractable query answering with negation

So far we have seen the following examples of the behavior of query answering in data
exchange:

• Good behavior, as observed for unions of conjunctive queries: certain answers to them

can be found efficiently by running naıve evaluation over the canonical solution (in fact,
over an arbitrary universal solution). This is based on the key fact that

certain ( Q , T )= Q naıve ( T ) (7.3)

for all instances T ,when Q is a union of conjunctive queries.

• Bad behavior, as for arbitrary relational algebra queries: for them, no algorithm in gen-

eral can compute certain M ( Q , S ).

• Moderately bad behavior, as for unions of conjunctive queries with inequalities: for

them, certain M ( Q , S ) can be computed, but the computation is intractable.

What we look for now is examples of moderately good behavior : that is, certain an-
swers can be efficiently computed, but not necessarily by naıve evaluation. We first do this
search within the realm of relational algebra, and then leave it and move to more expressive
languages such as D ATALOG .