Database Reference
In-Depth Information
n
-modularity can be removed in the LAV case, but at the cost of adding the following new
structural property:
•
Closure under union: A mapping
M
is
closed under union
if ( 0
,
0)
∈M
,and(
S
∪
S
,
T
T
)
and (
S
,
T
)
∪
∈M
whenever (
S
,
T
)
∈M
∈M
.
Notice that in the previous definition, instances
S
,
S
are not assumed to be disjoint, and
likewise for
T
,
T
. It is easy to see that every LAV mapping is closed under union. 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:
L
(
x
,
y
)
∧
L
(
y
,
x
)
→
E
(
x
,
y
)
.
,
S
=
Then for the source instances
S
=
{
L
(1
,
2)
}
{
L
(2
,
3)
}
,wehavethat(
S
,
0)
∈M
and
(
S
,
0)
S
,
0) does not belong to
∈ M
.However,(
S
∪
M
, as fact
E
(1
,
3) holds in every
S
under
solution for
S
is not closed under union. Notice that
the previous st-tgd is full, and, therefore, we also conclude that GAV mappings are not
closed under union.
Removing
n
-modularity and adding closure under union in the statement of
Theorem
21.4
yields a characterization of the class of LAV mappings:
∪
M
, which shows that
M
Theorem 21.5
A mapping can be defined by a finite set of LAV st-tgds if and only if it is
closed under target homomorphisms, admits universal solutions, reflects source homomor-
phisms, and is closed under union.
Proof
We have already shown that if a mapping
is defined by a finite set of LAV st-
tgds, then it satisfies the four properties mentioned in the statement of the theorem. Thus,
we only need to prove one direction of the theorem.
Assume that
M
is a mapping from a source schema R
s
to a target schema R
t
that
satisfies the four properties in the statement of the theorem. Moreover, assume that R
s
=
M
R
1
,...,
R
m
, with each
R
i
having arity
n
i
, and suppose that
n
= max
{
n
1
,...,
n
m
}
.Thenlet
d
1
,
...
,
d
n
be a sequence of pairwise distinct constants, and for every
i
∈{
1
,...,
m
}
,let
S
i
be an instance of R
s
such that:
R
S
i
j
=
{
(
d
1
,...,
d
n
i
)
}
i
=
j
0
i
=
j
.
For every instance
S
i
(1
≤
i
≤
m
) choose an arbitrary universal solution
T
i
for
S
i
un-
der
M
(such an instance exists since
M
admits universal solutions), and define st-
tgd
θ
i
as follows. Assume that
ρ
is a one-to-one function that associates to each ele-
ment in (D
OM
(
S
i
)
∪
D
OM
(
T
i
)) a fresh variable, and assume that
x
=(
ρ
(
a
1
)
,...,
ρ
(
a
j
)),
where
{
a
1
,...,
a
j
}
=(D
OM
(
S
i
)
∩
D
OM
(
T
i
)),
y
=(
ρ
(
b
1
)
,...,
ρ
(
b
k
)),where
{
b
1
,...,
b
k
}
=
(D
OM
(
S
i
)
D
OM
(
T
i
)),and
z
=(
ρ
(
c
1
)
,...,
ρ
(
c
)),where
{
c
1
,...,
c
}
=(D
OM
(
T
i
)
D
OM
(
S
i
)). Then, as in the proof of
Theorem 21.4
,define
ϕ
i
(
x
,
y
) as the conjunction of
all atomic formulae
U
(
ρ
(
u
1
)
,...,
ρ
(
u
j
)) such that
U
(
u
1
,...,
u
j
) holds in
S
i
,define
ψ
i
(
x
,
z
)
