Database Reference
In-Depth Information
UnivSol
2
(
T
). Assume
T
is an arbitrary solution. Let
UnivSol
1
(
T
)
⇒
⊥
1
,...,
⊥
m
enu-
merate the nulls in D
OM
(
T
),andlet
T
c
be as defined above. Since
T
c
∈
S
OL
M
(
S
)
and does not contain nulls, it must be the case by UnivSol
1
(
T
) that
T
c
∈
Rep
(
T
).
Take a homomorphism
h
witnessing
T
c
∈
Rep
(
T
) and change it into a mapping
h
from D
OM
(
T
) into D
OM
(
T
) by setting
h
(
)=
c
i
,and
otherwise letting
h
coincide with
h
. Then clearly
h
is a homomorphism from
T
to
T
.
Take an arbitrary
T
∈
⊥
)=
⊥
i
whenever
h
(
⊥
Rep
(
T
),andlet
h
be a homomorphism from
T
in
T
.
Then
h
◦
h
is a homomorphism from
T
into
T
, and, thus,
T
∈
Rep
(
T
).
UnivSol
2
(
T
)
UnivSol
3
(
T
). Assume
T
∈
m
enumerate the
nulls in D
OM
(
T
),andlet
T
c
be as defined above. Then
T
c
∈
Rep
(
T
) and hence,
by UnivSol
2
(
T
),
T
c
∈
⇒
S
OL
M
(
S
).Let
⊥
1
,...,
⊥
Rep
(
T
). Take a homomorphism
h
witnessing
T
c
∈
Rep
(
T
)
and change it into a mapping
h
from D
OM
(
T
) into D
OM
(
T
) by setting
h
(
⊥
)=
)=
c
i
, and otherwise letting
h
coincide with
h
. Then clearly
h
is a homomorphism from
T
to
T
.
UnivSol
3
(
T
)
⊥
i
whenever
h
(
⊥
UnivSol
1
(
T
). Let
T
be an arbitrary instance in S
OL
M
(
S
) that does not
contain nulls. Then, by UnivSol
3
(
T
), there is a homomorphism
h
from
T
into
T
.
But this immediately implies that
T
∈
⇒
Rep
(
T
). This completes the proof of the
proposition.
Proposition 6.1
justifies the following definition.
Definition 6.2 (Universal solutions) Given a mapping
M
is a
universal
solution if one of UnivSol
i
(
T
),for
i
= 1
,
2
,
3, is satisfied (and hence all are
satisfied).
M
, a solution
T
for
S
under
Most commonly in the proofs one uses the condition that for every solution
T
for
S
,
there exists a homomorphism
h
:
T
→
T
.
Example 6.3 (
Example 4.3
continued) Neither solution
T
nor
T
in
Example 4.3
is
universal. In fact, there is no homomorphism
h
:
T
→
T
;otherwise
h
((
⊥
1
,
2320
,
⊥
1
,
AirFrance
)) = (
⊥
1
,
2320
,
⊥
2
,
AirFrance
)
,
⊥
1
)=
⊥
1
and
h
(
⊥
1
)=
⊥
2
, which is impossible. Moreover, there is no homo-
and, thus,
h
(
morphism
h
:
T
→
T
;otherwise
h
((
AF
406
,
2320
,
920
,
AirFrance
)) = (
⊥
1
,
2320
,
⊥
2
,
AirFrance
)
,
⊥
2
, which is impossible too, because a homo-
morphism must be the identity on constants. On the other hand, it can be seen that
T
is a
universal solution.
⊥
1
and
h
(920)=
and, thus,
h
(
AF
406)=
As we will see in the following sections, universal solutions have several good properties
that make them the preferred data exchange solutions. Unfortunately, universal solutions
are not a general phenomenon. Indeed, we show in the next section that there is a mapping
