Database Reference
In-Depth Information
universal solution is the “best” universal solution - since it is the most economical one in
terms of size - and hence that it should be the preferred one at the moment of materializing
a solution. On the other hand, we will see that there are additional costs involved in con-
structing such a solution. For now our goal is to characterize the smallest solutions in data
exchange.
It turns out that such smallest universal solutions happen to be the
cores
of universal
solutions. The notion of a
core
originated and played an important role in graph theory.
Here we present it for arbitrary instances. Recall that if we have two instances
T
and
T
,
then
T
is a
subinstance
of
T
if
V
T
⊆
V
T
for every relation symbol
V
used in
T
.Inthat
case we write
T
⊆
T
. If at least one of the inclusions
V
T
is proper, i.e.,
V
T
⊆
V
T
⊂
V
T
,
then
T
is a
proper subinstance
of
T
, and we write
T
⊂
T
.
Definition 6.13 (Core) Let
T
be a target instance with values in C
ONST
V
AR
,andlet
T
be a subinstance of
T
.Then
T
is a
core
of
T
if there is a homomorphism from
T
to
T
,
but there is no homomorphism from
T
to a proper subinstance of
T
.
∪
Recall that homomorphisms only act on nulls from V
AR
, i.e., they are always the identity
on constants from C
ONST
.
The proposition below lists some well-known facts about cores.
Proposition 6.14
1. Every instance has a core.
2. All cores of a given instance are isomorphic, i.e., the same up to a renaming of nulls.
3. Two instances are homomorphically equivalent if and only if their cores are isomorphic.
4. If T
is the core of the instance T , then there is a homomorphism h
:
T
T
such that
→
D
OM
(
T
)
.
h
(
v
)=
v for each element v
∈
The first two items in
Proposition 6.14
mean that we can talk about
the
core of an in-
stance. To give an intuition, for instance, behind the second fact, assume that
T
1
and
T
2
are
cores of
T
,andthat
h
i
:
T
T
i
are homomorphisms, for
i
= 1
,
2. Then
h
1
restricted to
T
2
cannot map it to a subinstance of
T
1
, for otherwise
h
1
→
h
2
would be a homomorphism from
T
to a subinstance of the core
T
1
. Likewise,
h
2
restricted to
T
1
cannot map it to a subin-
stance of
T
2
. Hence, these restrictions are one-to-one homomorphisms between
T
1
and
T
2
.
From here it is easy to derive that
T
1
and
T
2
are isomorphic.
The next result summarizes some of the good properties of cores in data exchange.
◦
Theorem 6.15
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
be a mapping, such that
Σ
st
consists of a set of
st-tgds and
Σ
t
consists of a set of tgds and egds.
1. If S is a source instance and T is a solution for S, then the core of T is also a solution
for S.
2. If S is a source instance and T is a universal solution for S, then the core of T is also a
universal solution for S.
3. If S is a source instance for which a universal solution exists, then all universal solutions
have the same core (up to renaming of nulls), and the core of an arbitrary universal
solution is precisely the smallest universal solution.
