Database Reference
In-Depth Information
n
+ 1 it must be the case that
h
(
u
k
)=
h
(
u
). We conclude that
T
is not a universal
solution for
S
(
≤
A
) under
M
, which also finishes the proof of the theorem.
Do we have to interpret the previous undecidability result as a serious drawback? Not
really. Indeed, as we proved in
Theorem 5.3
, even the conceptually more basic problem of
the existence of arbitrary solutions in data exchange is undecidable. Recall that in order to
recover decidability in that case, we had to further restrict the class of mappings to those
with a weakly acyclic set of tgds.
Thus, what the results in this section really suggest is that it is necessary to impose
extra conditions on mappings if one wants to ensure that the following two conditions are
satisfied:
(C1) The existence of solutions implies the existence of universal solutions.
(C2) The problem of checking for the existence of universal solutions is not only decid-
able, but also tractable.
Furthermore, since we are interested in materializing a good solution for a source instance,
we should also add the following desirable requirement:
(C3) If solutions exist for a source instance
S
, one must be able to construct some universal
solution in polynomial time.
We study these requirements in the next section. In particular, we show that the mappings
with a weakly acyclic set of tgds also behave well with respect to universal solutions,
as they satisfy the three good properties described above. (Notice, in particular, that the
mappings used in
Example 6.4
and in the proof of
Theorem 6.5
are not weakly acyclic.)
But before doing so, we show the strong connection between the chase and the class of
universal solutions.
6.3 Canonical universal solution and chase
We first prove an important result that relates the notion of the chase to the class of universal
solutions. It states that the result of a successful chase sequence, if it exists, is not only a
solution but also a universal solution. Moreover, if the chase fails for a source instance
S
,
then no solutions for
S
exist.
Theorem 6.7
t
)
be a mapping and S a source instance. If there is
a successful chase sequence for S under
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
with result T , then T is a universal solution
for S. On the other hand, if there exists a failing chase sequence for S under
M
, then S has
no solution.
M
Proof
In order to prove the theorem we need the following technical, but rather intuitive
lemma. The proof is left as an exercise.
d
,
a
−−→
Lemma 6.8
Let S
1
S
2
be a chase step, where S
2
=
fail
. Assume that S
3
is an instance
