Database Reference
In-Depth Information
(
⇒
) Assume that (
S
,
T
)
∈ M
and that
ϕ
S
i
(
x
,
y
)
→∃
z
ψ
T
i
(
x
,
z
) is a dependency in
ϕ
S
i
(
a
,
b
) for some tuples
a
,
b
of values from D
OM
(
S
). We need to prove
Σ
st
such that
S
|
=
that
T
ψ
T
i
(
a
,
z
).
Given that
S
|
=
∃
z
ϕ
S
i
(
a
,
b
), we have by definition of
ϕ
S
i
(
x
,
y
) that there exists a homomor-
phism
h
from
S
i
to
S
. In particular, if
c
,
d
are the tuples of elements from D
OM
(
S
i
) such that
ρ
|
=
(
d
)=
y
,thenwehave
h
(
c
)=
a
and
h
(
d
)=
b
. Given that
reflects source
homomorphisms, there exists a homomorphism
h
from
T
i
to
T
that extends
h
,where
T
is an arbitrary universal solution for
S
under
(
c
)=
x
and
ρ
M
M
(such a solution exists since
M
admits
universal solutions). Thus, given that
T
i
|
=
∃
z
ψ
T
i
(
c
,
z
) by the definition of
ψ
T
i
, we conclude
that
T
ψ
T
i
(
a
,
z
) since
h
is a homomorphism from
T
i
to
T
that extends
h
(hence,
h
(
c
)=
h
(
c
)=
a
). Since
T
is a universal solution for
S
under
|
=
∃
z
,there
exists a homomorphism
g
from
T
to
T
that is the identity on constants. Therefore, given
that
a
is a tuple of constants, we conclude that
T
M
and (
S
,
T
)
∈M
ψ
T
i
(
a
,
z
) since
T
|
=
∃
z
|
=
∃
z
ψ
T
i
(
a
,
z
),
which was to be shown.
(
⇐
) Assume that (
S
,
T
)
∈M
. Then we need to prove that (
S
,
T
)
|
=
Σ
st
.
is
n
-modular, there exists a subinstance
S
⊆
Given that (
S
,
T
)
∈M
and
M
S
such that
D
OM
(
S
)
n
and (
S
,
T
)
st
there exists an instance
S
|
|≤
∈M
. Thus, by the definition of
Σ
of R
s
such that
S
and
S
are isomorphic and
st
. Assume that
f
:D
OM
(
S
)
θ
S
,
T
∈
Σ
→
b
are the tuples of elements
D
OM
(
S
) is an isomorphism between
S
and
S
,andthat
a
,
(
y
)=
b
.Moreover,let
T
be an instance of R
t
obtained from
T
by replacing every element
a
in
a
by
f
(
a
),and
leaving the other elements unchanged. Notice that every element in (D
OM
(
T
)
from
S
used in the construction of
ϕ
S
(
x
,
y
),thatis,
ρ
(
x
)=
a
and
ρ
D
OM
(
S
))
is a null value, as every element in (D
OM
(
T
)
D
OM
(
S
)) is a null value given that
T
is a universal solution for
S
under
M
(by definition of
θ
S
,
T
)and
M
isassumedtobe
closed under isomorphisms. Also notice that (
S
,
T
)
,since(
S
,
T
) is isomorphic to
∈M
(
S
,
T
), the pair (
S
,
T
) is in
M
and
M
is closed under isomorphisms.
We claim that (
S
,
T
)
θ
S
,
T
. To the contrary, assume that (
S
,
T
)
|
=
|
=
θ
S
,
T
. Given that
ϕ
S
(
f
(
a
)
,
f
(
b
)), we conclude that
T
S
|
ψ
T
(
f
(
a
)
,
z
). Thus, by the definition of
T
=
|
=
∃
z
and given that every element in (D
OM
(
T
)
D
OM
(
S
)) is a null value, we conclude by
ψ
T
that there exists a homomorphism from
T
to
T
that is the identity
on constants. Therefore, given that (
S
,
T
)
∈ M
, we conclude that (
S
,
T
)
∈ M
as this
mapping is closed under target homomorphisms (that are the identity on constants). This
obviously leads to a contradiction.
We have shown that (
S
,
T
)
the definition of
θ
S
,
T
.Since
S
⊆
|
=
S
and
θ
S
,
T
is a st-tgd, we have that
(
S
,
T
)
|
=
θ
S
,
T
. Hence, given that
θ
S
,
T
∈
Σ
st
, we conclude that (
S
,
T
)
|
=
Σ
st
,whichwas
to be shown.
A natural question at this point is whether any of the conditions introduced in this chapter
can be withdrawn when characterizing LAV or GAV mappings. We show next that, indeed,