Database Reference
In-Depth Information
, then there exists a subinstance
S
⊆
D
OM
(
S
)
R
t
,if(
S
,
T
)
∈M
S
such that
|
|≤
n
and
(
S
,
T
)
∈M
.
In fact, what we showed in the proof of
Proposition 21.2
is that if a mapping
M
is specified
by a finite set of st-tgds, then
is
n
-modular, where
n
is the maximumnumber of variables
occurring in the left-hand side of a dependency in
M
Σ
st
. Interestingly, it can be shown that
n
-modularity, together with the basic properties presented in the previous section, precisely
characterize the mappings that can be defined by finite sets of st-tgds.
Theorem 21.4
A mapping can be defined by a finite set of st-tgds if and only if it is closed
under target homomorphisms, admits universal solutions, reflects source homomorphism,
and is n-modular for some n
≥
1
.
Proof
We have already shown that if a mapping
is defined by a finite set of 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. Then for every in-
stance
S
of R
s
, choose an arbitrary universal solution
T
for
S
under
M
M
(it exists
since
M
admits universal solutions), and define a st-tgd
θ
S
,
T
as follows. Assume that
ρ
is a one-to-one function that associates to each element in (D
OM
(
S
)
∪
D
OM
(
T
)) a
fresh variable, and assume that
x
=(
ρ
(
a
1
)
,...,
ρ
(
a
i
)),where
{
a
1
,...,
a
i
}
=(D
OM
(
S
)
∩
D
OM
(
T
)),
y
=(
ρ
(
b
1
)
,...,
ρ
(
b
j
)),where
{
b
1
,...,
b
j
}
=(D
OM
(
S
)
D
OM
(
T
)),and
z
=
(
ρ
(
c
1
)
,...,
D
OM
(
S
)).
It is important to notice that every element in the set (D
OM
(
T
)
ρ
(
c
k
)),where
{
c
1
,...,
c
k
}
=(D
OM
(
T
)
D
OM
(
S
)) is a null
value. Indeed, assume otherwise, and let
a
be a constant that occurs in (D
OM
(
T
)
is closed under isomorphisms, any instance
T
in which
a
is replaced
M
D
OM
(
S
)).Since
⊥
by a null
not occurring elsewhere in
T
is also a solution for
S
. But then we have a ho-
momorphism (in the usual data-exchange sense) from
T
to
T
(sending
to
a
) but not
the other way around. This contradicts our assumption that
T
is universal. Thus, indeed,
(D
OM
(
T
)
D
OM
(
S
)) contains only nulls.
We define
⊥
ϕ
S
(
x
,
y
) as the conjunction of all atomic formulae
U
(
ρ
(
u
1
)
,...,
ρ
(
u
)) such
that
U
(
u
1
,...,
u
) holds in
S
,and
ψ
T
(
x
,
z
) as the conjunction of all atomic formulae
V
(
ρ
(
v
1
)
,...,
ρ
(
v
m
)) such that
V
(
v
1
,...,
v
m
) holds in
T
.Then
θ
S
,
T
is defined as the st-tgd
ϕ
S
(
x
,
y
)
ψ
T
(
x
,
z
).
Let
S
1
,
...
,
S
k
be a sequence of pairwise nonisomorphic instances of R
s
such that for
every instance
S
of R
s
satisfying
→∃
z
|
D
OM
(
S
)
|≤
n
, it holds that
S
is isomorphic to
S
i
for some
i
∈{
1
,...,
k
}
. Then define
Σ
st
as the following set of st-tgds:
{
θ
S
i
,
T
i
|
1
≤
i
≤
k
}
.
Next we show that mapping
Σ
st
, that is, we prove that given instances
S
,
T
of R
s
and R
t
, respectively, it holds that (
S
,
T
)
M
is defined by
∈M
if and only if (
S
,
T
)
|
=
Σ
st
. Notice
that given that
Σ
st
is a finite set of st-tgds, we conclude that the theorem holds.
