The problem of relational data exchange - Foundations of Data Exchange - page 42

query languages, which we study next. In Section 7.2 we show that the query answer-
ing problem becomes tractable for conjunctive queries over the class of mappings with a
weakly acyclic set of tgds, i.e., those for which the existence of (universal) solutions can
be checked in polynomial time.
Unfortunately, this positive result cannot be extended much further, since we show in
Section 7.3 that adding a very restricted kind of negation to conjunctive queries leads to
intractability, even in the absence of target dependencies. In Section 7.4 we partially tackle
this problem, and develop a language that at the same time adds a limited form of negation
to conjunctive queries, can express interesting data exchange properties, and retains the
good properties of conjunctive queries for data exchange. Later, in Sections 7.5 and 7.6 we
study the notion of query rewriting - that is, when the certain answers of a query Q can
be obtained by posing a (perhaps different) query Q over a materialized target instance.
We develop techniques that help us decide when a query admits a rewriting in some query
language.
Finally, in Chapter 8 , we study alternative semantics for data exchange. These semantics
are not based on the class of all solutions, as the certain answers semantics defined above,
but rather on subclasses of suitably chosen preferred solutions. For instance, Section 8.1
develops a semantics based only on the set of universal solutions. Sections 8.2 and 8.3 are
devoted to the study of a closed-world semantics that, unlike the other semantics, does not
allow solutions to be open for adding new facts. Since neither the closed-world nor the
open-world semantics are completely satisfactory in some scenarios, we study in Section
8.4 a clopen semantics that tries to combine the best of both worlds.