Database Reference
In-Depth Information
As before, we denote by S
OL
CWA
M
(
S
) the set of CWA solutions for
S
under
M
.
Σ
t
= 0.
Interestingly enough, it is possible to provide a simple characterization of the CWA
presolutions that are also CWA solutions. The proof is left as an exercise for the reader.
It is not hard to prove that this definition coincides with
Definition 8.8
when
Proposition 8.23
t
consists of a set of
tgds and egds, and S a source instance. Then for every target instance T , the following are
equivalent:
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
st
)
be a mapping, where
Σ
S
OL
CWA
M
1. T
(
S
)
.
2. T is a
CWA
presolution and a universal solution for S under
∈
M
.
The previous characterization is useful, as it can be applied to identify which solutions
are also CWA solutions.
Example 8.24 (
Example 8.21
continued)
Target
instances
T
1
and
T
2
belong to
S
OL
CWA
M
(
S
), since it is not hard to see that they are at the same time CWA presolutions
and universal solutions for
S
under
M
. Indeed,
T
1
is simply the result of the usual chase
(and, hence, it is universal) and
T
2
has a homomorphism
h
into
T
1
(
h
is the identity in every
element except
1
). This implies that
T
2
has a homomorphism
into every solution, and, therefore, that it is a universal solution.
On the other hand, the CWA presolution
T
3
does not belong to S
OL
CWA
M
⊥
2
, where it takes value
⊥
(
S
),simply
because it is not a universal solution for
S
(as there is no homomorphism from
T
3
to
T
1
).
We now prove an important proposition that shows that the core is always a CWA solu-
tion:
Proposition 8.25
Let
Σ
t
)
be a mapping and S be a source instance such
that at least one universal solution for S under
M
=(R
s
,
R
t
,
Σ
st
,
M
exists. Assume that T is the core of the
S
OL
CWA
M
universal solutions for S under
M
.ThenT
∈
(
S
)
.
Proof
We know from
Proposition 6.15
that
T
is a universal solution. Hence,
Proposition
8.23
tells us that we only need to show that
T
is the result of an α-chase sequence, for
some
V
AR
.
We start by inductively constructing partial mappings
α
:
K
M
→
C
ONST
∪
α
i
:
K
M
→
C
ONST
∪
V
AR
and
sequences
C
i
=(
L
1
,...,
L
i
) of instances of
R
s
,
R
t
such that:
α
i
-chase sequence for
S
under
α
i
:
• C
i
is an
M
, for each
K
M
→
C
ONST
∪
V
AR
that
α
i
coincides with
K
M
for which
extends
α
i
;thatis,
α
i
on every element of
α
i
is defined,
and
•
L
i
⊆
S
∪
T
.
We define
α
0
:
K
M
→
C
ONST
∪
V
AR
as the partial mapping that is undefined on each
α
0
-chase
element of
K
M
,and
C
0
=(
L
0
),where
L
0
:=
S
. Clearly,
L
0
⊆
S
∪
T
and
C
0
is an
α
0
:
sequence for
S
under
M
, for each
K
M
→
C
ONST
∪
V
AR
that extends
α
0
.
Assume, for the inductive case, that
α
i
:
K
M
→
C
ONST
∪
V
AR
and
C
i
=(
L
0
,...,
L
i
) are,
