Database Reference
In-Depth Information
admits universal solutions, reflects source homomorphisms, but cannot be defined by a
finite set of st-tgds.
Proof
Let R
s
be a source schema consisting of a binary predicate
U
, R
t
be a target schema
consisting of a binary predicate
V
and
M
be a mapping from R
s
to R
t
specified by the
following dependency:
ϕ =
∀
x
∃
y
∀
z
(
U
(
x
,
z
)
→
V
(
y
,
z
))
.
We leave it as an exercise for the reader to prove that
is closed under target homo-
morphisms, admits universal solutions and reflects source homomorphisms (see
Exercise
22.3
). Next we show that
M
cannot be defined by a finite set of st-tgds.
For the sake of contradiction, assume that
M
Σ
st
of st-tgds, and
let
n
be the maximum number of variables occurring in the left-hand side of an st-tgd in
Σ
st
.
M
is defined by a finite set
Claim 21.3
If S, T are instances of
R
s
and
R
t
, respectively, such that
(
S
,
T
)
∈M
,then
it has a subinstance S
⊆
D
OM
(
S
)
n and
(
S
,
T
)
S such that
|
|≤
∈M
.
Proof
Given that
M
is defined by
Σ
st
, we need to prove that if
S
,
T
are instances of R
s
Σ
st
, then there exists a subinstance
S
⊆
and R
t
, respectively, such that (
S
,
T
)
|
=
S
such that
D
OM
(
S
)
n
and (
S
,
T
)
|
|≤
|
=
Σ
st
. Notice that if (
S
,
T
)
|
=
Σ
st
, then there exists an st-tgd
b
of elements from D
OM
(
S
) such that
S
(
a
,
b
)
ϕ
(
x
,
y
)
→∃
z
ψ
(
x
,
z
) in
Σ
st
and tuples
a
,
|
=
ϕ
(
a
,
z
).Let
S
be the subinstance of
S
induced by the elements in
a
,
b
. Clearly,
and
T
|
=
∃
z
ψ
(
a
,
b
).Thus,wehave
b
S
|
D
OM
(
S
)
n
,and(
S
,
T
)
=
ϕ
|
|≤
n
since
|
a
|
+
|
|≤
|
=
Σ
st
since
(
a
,
b
) and
T
S
|
|
∃
(
a
,
z
).
=
ϕ
=
z
ψ
Let
⊥
1
,
...
,
⊥
n
+1
be a sequence of pairwise distinct null values,
S
be the following
instance of R
s
:
U
S
=
{
(1
,
i
)
|
1
≤
i
≤
n
+1
}
,
and
T
be the following instance of R
t
:
V
T
=
{
(
⊥
i
,
j
)
|
1
≤
i
≤
n
+1
,
1
≤
j
≤
n
+1and
i
=
j
}
.
∈
U
S
but
Then we have (
S
,
T
)
|
=
ϕ
,asforevery
i
∈{
1
,...,
n
+ 1
}
, it holds that (1
,
i
)
∈
V
T
. Furthermore, for every subinstance
S
⊆
S
such that
D
OM
(
S
)
(
⊥
i
,
i
)
|
|≤
n
,wehave
(
S
,
T
)
. To see this, notice that if
S
⊆
S
and
D
OM
(
S
)
|
=
ϕ
|
|≤
n
, then there is
k
∈{
1
,...,
n
+
U
S
.Butthen(
S
,
T
)
U
S
, it holds that
1
}
such that (1
,
k
)
∈
|
=
ϕ
as for every tuple (1
,
i
)
∈
V
T
. Thus, we have obtained a contradiction, since
(
⊥
k
,
i
)
∈
ϕ
defines
M
and instances
S
,
T
do not satisfy the statement of
Claim 21.3
.
In the proof of
Proposition 21.2
, we identified the following structural property:
•
n
-modularity: Assume that
M
is a mapping from a source schema R
s
to a target schema
R
t
.Then
M
is
n
-modular,
n
≥
1, if for every instance
S
of R
s
and every instance
T
of
