Database Reference
In-Depth Information
Algorithm 19.1 Composing relational schema mappings
Require: on the source side variables are reused only in equalities
Σ
13
:= 0
m
:= max
(ϕ
→
ψ)
∈
Σ
23
ϕ
for all
ϕ
1
−→
π
1
,
ϕ
2
−→
π
2
, ...,
ϕ
k
−→
π
k
∈
Σ
12
,
k
≤
m
do
{
in case of repetitions, rename variables
}
ρ
π
1
∧···∧
π
k
for all
:=
π
∧
α
−→
π
∈
Σ
23
and all homomorphisms
h
:
π
→
ρ
do
ϕ
π
)
Σ
←
∧···∧
ϕ
k
∧
h
(
α
)
−→
h
(
13
1
end for
end for
return Σ
13
Proof
Each constraint in
Σ
13
is of the form
ϕ
1
∧···∧
ϕ
k
∧
h
(
α
)
−→
h
(
ψ
)
,
π
∧
α
−→
π
∈
Σ
23
,and
h
is a
where
ϕ
1
−→
π
1
,
ϕ
2
−→
π
2
, ...,
ϕ
k
−→
π
k
∈
Σ
12
and
)[
f
,
a
].
homomorphism from
π
into
π
1
∧···∧
π
k
.Pick
a
such that
S
1
|
=
ϕ
1
∧···∧
ϕ
k
∧
h
(
α
π
1
∧···∧
π
k
[
f
,
a
] and we get
S
2
|
)[
f
,
a
].As
h
(
)[
f
,
a
] holds, we have
Then
S
2
|
=
=
h
(
π
α
)[
f
,
a
] and hence
S
3
|
)[
f
,
a
].
S
2
|
=
h
(
π
)
∧
h
(
α
=
h
(
ψ
f , there exists an interme-
Lemma 19.10
If
(
S
1
,
S
3
)
∈
M
13
with a witnessing valuation
diate instance S
2
such that
(
S
1
,
S
2
)
∈
M
12
and
(
S
2
,
S
3
)
∈
M
23
with the same witnessing
f.
valuation
Proof
Consider
S
2
=
R
(
t
1
,...,
t
)[
f
,
a
]
,
[
f
,
a
],
R
(
t
1
,...,
t
) is an atom in
ϕ
−→
π
∈
Σ
12
,
S
1
|
=
ϕ
π
where
R
(
t
1
,...,
t
)[
f
,
a
] is the tuple obtained from
R
(
t
1
,...,
t
) by interpreting the function
symbols according to
f
and the variables according to
a
. Obviously, (
S
1
,
S
2
)
∈
M
12
with
the witnessing valuation
f
, so it remains to see that (
S
2
,
S
3
)
∈
M
23
with the witnessing
valuation
f
.
Suppose that
S
2
|
[
f
,
a
] for some
π
∧
α
−→
π
∈
Σ
23
and let
=
π
∧
α
π
=
A
1
∧···∧
A
k
with
m
. By definition of
S
2
,
A
1
[
f
,
a
]
,...,
A
k
[
f
,
a
] are equal to
B
1
[
f
,
c
1
]
,...,
B
k
[
f
,
c
k
]
,
k
≤
ϕ
i
[
f
,
c
i
] for
i
= 1
,
2
,...,
k
where
B
i
is an atom of some
π
i
such that
ϕ
i
−→
π
i
∈
Σ
12
and
S
1
|
=
(we can assume the rules use disjoint sets of variables).
Since
π
uses no function symbols, nor reuses variables, we can define a homomorphism
g
:
π
→
π
1
∧···∧
π
k
