Database Reference
In-Depth Information
in a sense, the “maximal” element of the class of CWA solutions, since every other CWA
solution was a homomorphic image of it.
Example 8.21
shows that this property is no
longer true in the presence of target dependencies. In particular,
T
2
is a CWA solution that
is not a homomorphic image of the canonical universal solution
T
1
for
S
.
The observation that CWA solutions are not necessarily homomorphic images of the
canonical universal solution (if the latter exists) is particularly important, as it will affect
query answering in a significant way. In fact, we will see later that it implies that in the
presence of target dependencies it is no longer true that for every FO query
Q
,thesetof
CWA certain answers coincides with
Q
(
T
), for each source instance
S
with canonical
universal solution
T
.
But perhaps there is a different target instance that satisfies the role of being the “maxi-
mal” element of the class of CWA solutions in the presence of target dependencies (that is,
a CWA solution such that any other CWA solution is a homomorphic image of it)? And, if
a unique maximal element does not exist, perhaps there are polynomially many of them?
However, this is not the case, as source instances may generate an exponential number
of “maximal” elements in the class of CWA solutions. This holds even for the case of
mappings such that
Σ
t
consists of a set of egds and a weakly acyclic set of tgds. We leave
the proof of this fact as an interesting exercise for the reader.
Proposition 8.26
There exists a mapping
Σ
t
consists of a
set of egds and a weakly acyclic set of tgds, with the following property. For every positive
integer n, there exists a source instance S and distinct
CWA
solutions T
1
,
T
2
,...,
T
2
n
for S
under
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
, such that
M
such that:
•
the instance S contains
2
n tuples, and
•
each solution T
∈
S
OL
CWA
M
(
S
)
is the homomorphic image of exactly one T
i
,for
1
≤
i
≤
2
n
.
Existence of CWA solutions and target dependencies
In the presence of target dependencies the existence of CWA solutions is not a trivial prob-
lem. Indeed, it can be proved that it is equivalent to the existence of universal solutions.
Theorem 8.27
For every mapping
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
and source instance S, the fol-
lowing are equivalent:
S
OL
CWA
M
•
(
S
)
= 0
.
•
There exists a universal solution for S under
M
.
Proof
Clearly, if S
OL
CWA
M
M
(since each CWA solution is, by
Proposition 8.23
, a universal solution). Assume, on the
other hand, that
T
is a universal solution for
S
under
(
S
)
= 0 then there exists a universal solution for
S
under
. Take the core
T
of
T
.Thenit
M
follows from
Proposition 8.25
that
T
∈
S
OL
CWA
M
(
S
).
Since we already have a good understanding of when the problem of existence of uni-
versal solutions is decidable (and even tractable) from
Chapter 6
, we can now state the
