Existence of solutions - Foundations of Data Exchange - page 53

Corollary 5.13 Σ t is the

union of a set of egds and a weakly acyclic set of tgds. Then S OL E XISTENCE M can be
solved in P TIME . Furthermore, if a solution for a source instance S exists, a particular
solution can be computed in polynomial time.

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

Summary
In summary, the following holds for the problem of existence of solutions in relational data
exchange.

• For arbitrary relational mappings defined by (st)-tgds and egds the problem is undecid-

able.

• For the class of relational mappings Σ t consists of a set of

egds and a weakly acyclic set of tgds, the problem becomes decidable (using the chase),
and, indeed, tractable.

M =(R s , R t , Σ st , Σ t ) such that

• For the latter class of mappings, if a source instance S has a solution, then a particular

solution T for S can be computed in polynomial time.

We prove later, in Section 6.3 , that the class of mappings with a weakly acyclic set of
tgds enjoys further desirable properties. We will see that for each source instance S with at
least one solution, a particular universal solution for S (that is, a solution for S that is more
general than any other) can be efficiently constructed.

5.5 Complexity of the problem

We have seen that one can efficiently (in polynomial time) test whether solutions exist for
a given source instance if target constraints use a weakly acyclic set of tgds. But can we do
better than this? For instance, is it possible to prove that the problem is not only tractable
but, also, that it can be solved in some parallelizable class like NL OGSPACE or NC 1 ?We
give a negative answer to this question, at least under widely held complexity-theoretical
assumptions. We state, in particular, that this problem can be P TIME -complete, and, thus,
it can be considered to be inherently sequential. Moreover, we obtain this lower bound
for fairly simple mappings that contain only egds and full (st-)tgds. The proof of the next
proposition is left as an exercise ( Exercise 9.3 ).

Proposition 5.14 There exists a mapping M =(R s , R t , Σ st , Σ t ) , such that:

• Σ st consists of a set of full st-tgds;
• Σ t consists of a set of full tgds and egds;

for which the problem S OL E XISTENCE M is P TIME -complete.