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

with mappings without target dependencies (in particular, for avoiding the problem of the
existence of universal solutions).

Definition 7.11 (Rewritings) Let Σ st ) be a mapping and Q a query over the

target schema R t . We say that Q is FO -rewritable over the canonical universal solution
(respectively, the core) under

M =(R s , R t ,

, if there is an FO-query Q over R t such that
certain M ( Q , S )= Q ( T ) ,

M

for every source instance S with canonical universal solution (respectively, core) T .

The following facts are known about FO-rewritings in data exchange.

• Unions of conjunctive queries are FO-rewritable under any mapping , both over the

canonical universal solution and the core. Indeed, we have seen that the rewriting of
a union of conjunctive queries Q ( x 1 ,..., x m ) is the query Q naıve , which is obtained by
evaluating Q and only keeping tuples without nulls. It can therefore be expressed as

M

Q ( x 1 ,..., x m ) ∧ C( x 1 ) ∧···∧ C( x m ) .

Notice that this rewriting is a union of conjunctive queries as well, is independent of the
mapping, and can be constructed in linear time from Q ( x 1 ,..., x m ).

• There exists a union of conjunctive queries with negated atoms, Q ,andaL AV mapping

M

, such that Q is not FO-rewritable under M over the canonical universal solution. We

gave an example in the proof of Theorem 7.5 .

• There exists a Boolean conjunctive query Q with a single inequality and a L AV mapping

M

, both over the canonical universal solution
and over the core. The proof of this fact is left as an exercise to the reader. We prove a
closely related result in the next section ( Proposition 7.16 ).

, such that Q is not FO-rewritable under M

The previous two observations naturally raise the following question: Is the problem
of checking whether an FO-query admits an FO-rewriting over the canonical universal
solution (or the core) decidable? Unfortunately, the answer is negative.

Proposition 7.12 Σ st )

and an FO -query Q over R t ,whetherQis FO -rewritable over the canonical universal
solution or over the core under

The problem of checking, for a relational mapping M =(R s , R t ,

M , is undecidable.

Proof In order to prove the proposition we need the concept of a domain-independent
query. We avoid the formal definition but take advantage of one of the more important
properties of a domain-independent query Q over schema R:If K is an instance of a
schema R that extends R and K is the restriction of K to the relation symbols in R,
then Q ( K )= Q ( K ). Intuitively, this means that the evaluation of Q is independent of the
interpretation of the relation symbols that are not mentioned in Q . An example of a query
that is not domain-independent is R ( x )).

It follows from Trakhtenbrot's theorem that the following problem is undecidable: Given
a domain-independent Boolean FO formula

∀ x ( ¬ Q ( x ) →

ϕ over schema R, is there an instance K of