Database Reference
In-Depth Information
d
. Also, the target instance
T
2
=
{
R
(
a
,
⊥
)
,
R
(
b
,
⊥
)
}
,where
⊥∈
V
AR
, is a CWA presolution
S
for
S
, as witnessed by the mapping
α
:
K
M
→
C
ONST
∪
V
AR
such that
α
(
j
,
z
)=
α
(
j
,
w
)=
⊥
.
Notice that although both
T
1
and
T
2
are solutions for
S
, none of them is a
universal
solu-
tion for
S
under
M
. This shows that the notions of CWA presolutions and CWA solutions
do not coincide.
By abstracting from the previous example, one can easily conclude that the canonical
universal solution
T
for a source instance
S
is also a CWA presolution for
S
under
M
.This
S
M
→
is witnessed by some assignment
α
can
:
K
C
ONST
∪
V
AR
that assigns a distinct null
S
M
value to each pair (
j
,
z
)
∈K
. Indeed, it is not hard to see that in this case the result of
is always a target instance that is isomorphic to
j
∈J
the chase for
S
under
M
B
α
can
(
j
).
We now relate the notions of CWA solutions and CWA presolutions, showing, as the
names suggest, that every solution is a presolution.
M
S
Proposition 8.12
Let
M
=(R
s
,
R
t
,
Σ
st
)
be a mapping, S a source instance and T a target
instance in
S
OL
CWA
M
(
S
)
.ThenT isa
CWA
presolution for S under
M
.
Proof
Since
T
is a CWA solution, it is, in particular, a homomorphic image of the canon-
ical universal solution
T
can
for
S
.Let
h
:
T
can
→
T
be the homomorphism that witnesses
this fact. Recall that we can assume that
T
can
is of the form
j
∈J
M
B
α
can
(
j
),where
S
S
α
can
:
K
M
→
C
ONST
∪
V
AR
is a mapping that assigns a distinct null value to each pair
.Butthen
T
is of the form
j
∈J
S
M
S
(
j
,
z
) in
K
M
B
α
(
j
),where
α
:
K
M
→
C
ONST
∪
V
AR
S
S
M
is defined as
α
(
j
,
z
)=
h
◦
α
can
(
j
,
z
), for each pair (
j
,
z
)
∈ K
.Thisimpliesthat
T
is a
S
CWA presolution, as is witnessed by the mapping
α
:
K
M
→
C
ONST
∪
V
AR
.
On the other hand, the converse of
Proposition 8.12
is not true, as it was already shown
in
Example 8.11
. That is, there are CWA presolutions that are not CWA solutions. The in-
tuition is that CWA presolutions can still make true some “statements” that are not neces-
sarily implied by the source instance and the st-tgds in Σ
st
. For instance, CWA presolution
T
1
in
Example 8.11
tells us that the fact
R
(
a
,
c
) is true. However, this is clearly not a logical
consequence of the source instance and the st-tgd. In the same way, CWA presolution
T
2
in
Example 8.11
tells us that the “statement”
∃
xR
(
a
,
x
)
∧
R
(
c
,
x
) is true. But again, this does
not follow from
S
and
Σ
st
. With this idea in mind, we can finally define requirement (A3),
which ensures that such “invented” statements do not appear in our solutions. But more
important, this last requirement will allow us to connect our definition of CWA solution
with a proper intuition behind the CWA.
Let
is a Boolean conjunctive
query over the target schema R
t
. Recall that the intuition behind requirement (A3) is that
every statement in a CWA solution
T
for a source instance
S
must logically follow from
S
and the st-tgds in
M
=(R
s
,
R
t
,
Σ
st
) be a mapping. A
statement
over
M
Σ
st
. We formally define this as follows:
(A3) Every statement that holds in
T
also holds in every solution
T
for
S
under
M
.
