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

a contradiction. This implies that is FO-rewritable over the canonical universal solution

and over the core simply by the Boolean constant true .
The proof of the converse is postponed until the next section as we need to develop some
additional techniques, based on locality, for showing it. The proof will be given at the very
end of Section 7.5 .

θ

Despite this undecidability result, we can state some sufficient conditions for non-
rewritability of queries that allow us to exclude some classes of relational algebra queries
as not easily answerable in the data exchange scenario, This will be done in the next sec-
tion.

Rewritability: canonical universal solution vs the core
What is the relationship between rewritability over the canonical universal solution, and
over the core? It turns out that the class of queries rewritable over the core is strictly smaller
than the class of queries rewritable over the canonical universal solution, as long as map-
pings do not contain target constraints.

Theorem 7.13 For mappings without target dependencies Σ

t , the following hold:

1. Every FO -query Q that is FO -rewritable over the core is also rewritable over the canon-
ical universal solution.
2. There is a mapping

M

and an FO -query Q that is FO -rewritable over the canonical
universal solution but not over the core.

Thus, as we mentioned before, there is the following trade-off in choosing the canonical
universal solution or the core as the preferred solution in data exchange:

• the core allows the most compact materialization among all possible universal solutions;

however,

• this comes at the cost of losing the capability for FO-rewriting of some queries.

The proof of Theorem 7.13 depends on nontrivial model theoretical properties of cores
and canonical universal solutions that go beyond the scope of the topic.

7.6 Non-rewritability tool: locality

Locality is a standard tool in the study of logical expressibility, for instance, in relational
calculus (FO) and some of its extensions. Here we use it to answer questions about the
expressive power of FO-rewritings in data exchange. In particular, we develop a simple
locality tool that helps determine when a target query does not admit an FO-rewriting
over the solutions we have studied so far. But first we need to introduce the necessary
terminology for studying local properties of data.
The Gaifman graph ( S ) of an instance S of R is the graph whose nodes are the elements

of D OM ( S ), and such that there exists an edge between a and b in

G

G ( S ) iff a and b belong to

the same tuple of a relation R S ,forsome R

∈ R. For example, if H is an undirected graph,