Database Reference
In-Depth Information
as the conjunction of all atomic formulae
V
(
ρ
(
v
1
)
,...,
ρ
(
v
k
)) such that
V
(
v
1
,...,
v
k
) holds
in
T
i
, and define
θ
i
as the st-tgd
ϕ
i
(
x
,
y
)
→∃
z
ψ
i
(
x
,
z
).
Let
Σ
st
=
{
θ
1
,...,
θ
m
}
.Wehavethat
Σ
st
is a finite set of LAV st-tgds, so to conclude the
proof it is enough to show that
Σ
st
, that is, it is enough to show that given
instances
S
,
T
of R
s
and R
t
, respectively, the pair (
S
,
T
) is in
M
is defined by
Σ
st
.
This proof follows exactly the same lines as the proof of
Theorem 21.4
, so we leave it as
an exercise for the reader (see
Exercise 22.3
).
M
if and only if (
S
,
T
)
|
=
We conclude this section by presenting a characterization of GAV mappings, in which
we use all the properties mentioned in
Theorem 21.4
together with the following new
structural condition:
•
Closure under target intersection: A mapping
M
is
closed under target intersection
if (
S
,
T
1
∩
T
2
)
∈M
whenever (
S
,
T
1
)
∈M
and (
S
,
T
2
)
∈M
.
It is easy to see that every GAV mapping is closed under target intersection. On the other
hand, as the following example shows, mappings defined by arbitrary sets of st-tgds do not
have this property. Consider a mapping
M
defined by the following st-tgd:
R
(
x
)
→∃
yE
(
x
,
y
)
.
Let
S
=
{
R
(1)
}
be a source instance, and let
T
1
=
{
E
(1
,
2)
}
and
T
2
=
{
E
(1
,
3)
}
be target
instances. Clearly, both (
S
,
T
1
) and (
S
,
T
2
) belong to
M
,but(
S
,
T
1
∩
T
2
) does not as
T
1
∩
T
2
= 0, which shows that
is not closed under target intersection. Notice that the previous
st-tgd is a LAV st-tgd, and, thus, LAV mappings are not closed under target intersection.
M
Theorem 21.6
A mapping can be defined by a finite set of GAV st-tgds if and only if
it is closed under target homomorphisms, admits universal solutions, reflects source ho-
momorphisms, is closed under target intersection, and is n-modular for some n
≥
1
.
This theorem can be proved by using exactly the same construction as in the proof of
Theorem 21.4
, but relying instead on the following fact:
Proposition 21.7
If a mapping is closed under target homomorphisms, admits univer-
sal solutions and is closed under target intersection, then every source instance admits a
universal solution containing only constants.
Proof
Assume that
is a mapping from a source schema R
s
to a target schema R
t
satisfying the three conditions in the proposition, and let
S
be an instance of R
s
. Given that
M
M
.Let
h
be a homomorphism that maps every constant in
T
to itself and every null value in
T
to
a fresh constant. Then given that
admits universal solutions, there exists a universal solution
T
for
S
under
M
is closed under target homomorphisms and
h
is the
identity on constants, the instance
T
obtained from
T
by replacing every element
a
by
h
(
a
) is a solution for
S
under
M
is closed under target intersection,
T
=
T
T
M
.Since
M
∩
. It is a universal solution since
T
is a solution for
S
under
M
⊆
T
and
T
is a universal
solution. Also it contains only constants since
T
T
. This proves the proposition.
⊆
