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    Search WWH ::

Custom Search