Database Reference
In-Depth Information
that satisfies the dependency d and such that there is a homomorphism from S
1
into S
3
.
Then there exists a homomorphism from S
2
into S
3
.
We now prove the theorem. Assume first that (
S
,
T
) is the result of a successful chase
sequence for
S
under
.Then
T
is a solution for
S
. We show next that it is also a universal
solution. Let
T
be an arbitrary solution for
S
. Thus, (
S
,
T
) satisfies every dependency in
Σ
st
∪
Σ
t
. Furthermore, the identity mapping is a homomorphism from (
S
,
0) into (
S
,
T
).
Applying
Lemma 6.8
at each step of the chase sequence with result (
S
,
T
), we conclude
that there exists a homomorphism
h
: (
S
,
T
)
M
(
S
,
T
). In fact,
h
is also a homomorphism
→
from
T
into
T
.
Next, assume that there is a failing chase sequence for
S
under
M
, and that the last chase
d
,
a
−−→
fail
. Thus,
d
is an egd of the form
step in that sequence is (
S
,
T
)
ϕ
(
x
1
,...,
x
m
)
→
x
i
=
x
j
, the formula
(
a
) holds in (
S
,
T
) for some tuple
a
=(
a
1
,...,
a
m
),and
a
i
and
a
j
are
distinct constants. Suppose that
S
has a solution
T
. As above, using
Lemma 6.8
,wesee
that there is a homomorphism
h
from
T
to
T
. Thus,
ϕ
(
h
(
a
)) holds in
T
(since conjunctive
queries are preserved under homomorphisms), but
h
(
a
i
)=
a
i
and
h
(
a
j
)=
a
j
are distinct
constants. This contradicts the fact that
T
satisfies
d
.
ϕ
The result of a successful chase sequence for a source instance
S
is usually called a
canonical
universal solution for
S
. As the following example shows, canonical universal
solutions are not unique up to isomorphism, since the order in which tgds and egds are
applied in a chase sequence may yield different results.
Example 6.9 Let
Σ
t
) be a mapping, such that R
s
consists of the single
unary relation
P
, R
t
consists of two binary relations,
E
and
F
,theset
M
=(R
s
,
R
t
,
Σ
st
,
Σ
st
consists of the
st-tgd:
P
(
x
)
→∃
z
∃
w
(
E
(
x
,
z
)
∧
E
(
x
,
w
))
,
and the set
Σ
t
consists of the following tgd and egd:
E
(
x
,
y
)
→∃
zF
(
y
,
z
)
,
E
(
x
,
y
)
y
=
y
.
E
(
x
,
y
)
∧
→
Consider the source instance
S
=
{
P
(
a
)
}
. We have to start by applying the st-tgd. This
populates the target with the instance
T
=
{
E
(
a
,
⊥
1
)
,
E
(
a
,
⊥
2
)
}
. At this point, we have two
possible choices. Either we apply the tgd or the egd in
Σ
t
, since both of them are violated.
We show that these choices lead to different chase results.
•
Suppose that we apply the tgd first to each one of the tuples in
T
.Then
T
is extended
with facts
F
(
⊥
1
,⊥
3
) and
F
(
⊥
2
,⊥
4
). The resulting instance violates the egd, and hence
this has to be applied. The application of the egd equates nulls
⊥
1
and
⊥
2
, which yields
a target instance:
T
1
=
{
E
(
a
,
⊥
1
)
,
F
(
⊥
1
,
⊥
3
)
,
F
(
⊥
1
,
⊥
4
)
}
.
