Database Reference
In-Depth Information
Proof
We start by proving the first item. Assume that
T
is the core of
T
. We prove that
(
S
,
T
) satisfies every dependency in
Σ
st
∪
Σ
t
. Take an arbitrary st-tgd
ϕ
s
(
x
)
→∃
y
ψ
t
(
x
,
y
)
∈
Σ
st
and assume that
S
|
=
ϕ
s
(
a
), for some tuple
a
of elements in D
OM
(
S
) such that
|
a
|
=
|
x
|
.
ψ
t
(
a
,
b
), for some tuple
b
of elements
Since
T
is a solution for
S
it must be the case that
T
|
=
b
.But
T
is the core of
T
, and, therefore, there is a homomor-
in D
OM
(
T
) such that
|
|
=
|
y
|
T
. Notice that
h
(
a
)=
a
, since each element in
a
is a constant. As con-
junctive queries are preserved under homomorphisms, we conclude that
T
|
phism
h
:
T
→
t
(
a
,
h
(
b
)).
=
ψ
Thus,
T
|
=
∃
y
ψ
t
(
a
,
y
), and hence (
S
,
T
) satisfies the st-tgd.
Next, take an arbitrary tgd
∈
Σ
t
and assume that
T
|
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
)
=
ϕ
(
a
),forsome
tuple
a
of elements in D
OM
(
T
) such that
.Since
T
is a subinstance of
T
,itmust
|
a
|
=
|
x
|
(
a
,
b
)
be the case that
T
|
=
ϕ
(
a
), and, therefore, since
T
is a solution for
S
,that
T
|
=
ψ
for some tuple
b
of elements in D
OM
(
T
) such that
b
|
|
=
|
y
|
.From
Proposition 6.14
it
T
such that
h
(
v
)=
v
for each element
v
in
D
OM
(
T
). In particular,
h
(
a
)=
a
,since
a
is a tuple of elements in D
OM
(
T
). This implies
that
T
|
follows that there is a homomorphism
h
:
T
→
(
a
,
h
(
b
)), and, therefore, that
T
|
(
a
,
y
). We conclude that
T
satisfies the
=
ψ
=
∃
y
ψ
tgd.
Finally, take an arbitrary egd
x
i
=
x
j
∈
Σ
t
and assume that
T
|
ϕ
(
x
)
→
=
ϕ
(
a
),forsome
tuple
a
of elements in D
OM
(
T
) such that
|
a
|
=
|
x
|
. As in the previous case, we conclude
(
a
), and, therefore, since
T
is a solution for
S
,that
a
i
=
a
j
. Hence,
T
also
satisfies the egd, and, therefore,
T
is a solution for
S
.
The second part of the proposition follows easily from the facts that the core of
T
is a
solution for
S
and that there is a homomorphism
h
from
T
into any other solution (and,
thus,
h
is also a homomorphism from the core of
T
into such solution).
The third part follows easily from the properties of the core stated in
Proposition 6.14
.
Indeed, universal solutions are by definition homomorphically equivalent, and, thus, from
the third part of
Proposition 6.14
, they all have the same core up to renaming of nulls. Fur-
thermore, the core
T
∗
of the universal solutions is the smallest universal solution. Assume,
to the contrary, that there is a universal solution
T
for
S
of smaller size. But then
T
∗
must
be isomorphic to the core of
T
, which contradicts the fact that
T
is of smaller size than
T
∗
.
that
T
|
=
ϕ
Example 6.16 (
Example 6.12
continued) The solution
T
∗
is the core of the universal
solutions for
S
, since there is a homomorphism from
T
to
T
∗
but there is no homomorphism
from
T
∗
to a proper subinstance of itself.
In conclusion, the core of the universal solutions has good properties for data exchange.
This naturally raises the question about the computability of the core. As we have men-
tioned, the chase yields a universal solution that is not necessarily the core of the universal
solutions, so different techniques have to be applied in order to compute the core.
Computing the core
It is well known that computing the core of an arbitrary graph is a computationally in-
tractable problem. Indeed, we know that a graph
G
is 3-colorable if and only if there is a
