Database Reference
In-Depth Information
as follows: if
A
i
=
R
(
y
1
,...,
y
p
) and
B
i
=
R
(
t
1
,...,
t
p
) for some
R
,let
g
(
y
j
)=
t
j
. In conse-
quence,
Algorithm 19.1
eventually extends
Σ
13
with
π
)
.
ϕ
1
∧···∧
ϕ
k
∧
g
(
α
)
−→
g
(
,
g
(
x
)[
f
,
c
1
,...,
c
k
] is equal to
the value assigned to
x
,
x
[
a
]. In consequence, for each formula
Note that
g
is defined so that for each variable
x
used in
π
)[
f
,
c
1
,...,
c
k
] is the
ψ
,
g
(
ψ
[
f
,
a
], as long as
)[
f
,
c
1
,...,
c
k
]
same as
ψ
ψ
only uses variables used in
π
. In particular,
g
(
α
[
f
,
a
].Since
[
f
,
a
] holds by the initial assumption, we have
is the same as
α
α
)[
f
,
c
1
,...,
c
k
]
,
S
1
|
=
ϕ
1
∧···∧
ϕ
k
∧
g
(
α
which implies
π
)[
f
,
c
1
,...,
c
k
]
,
S
3
|
=
g
(
π
[
f
,
a
] (by the assumption that no new variables are introduced
on the target sides of dependencies.)
which is equivalent to
S
3
|
=
Algorithm 19.1
can also be used to compute the composition of two mappings specified
by finite sets of st-tgds, as every such mapping can be transformed into an equivalent one
specified by an SO tgd. It can be shown that exponentiality is unavoidable in such an
algorithm, as there exist mappings
M
23
, each specified by a finite set of st-tgds,
such that every SO tgd that defines the composition of
M
12
and
M
12
and
M
23
is of size exponential
in the size of
23
(see
Exercise 22.3
).
Theorem 19.8
also implies that the composition of a finite number of mappings specified
by st-tgds can be defined by an SO tgd, as we can compose the mappings one by one.
M
12
and
M
Theorem 19.11
The composition of a finite number of mappings, each defined by a finite
set of st-tgds, can be defined by an SO tgd.
Example 19.12 We have already shown in
Example 19.7
how SO tgds can be used to
express the composition of mappings specified by st-tgds. As a second example, assume
that
M
23
are the mappings defined in
Example 19.2
. The composition of these
two mappings is defined by
Takes
(
n
,
c
)
M
12
and
→
Enrolled
(
f
(
n
)
,
c
)).
Up to this point, we have shown that the language of SO tgds is closed under composi-
tion, and that the composition of any finite number of mappings specified by st-tgds can
be defined by an SO tgd. Thus, SO tgds are a good language when dealing with the com-
position operator. But, of course, it is natural to ask whether all the features of SO tgds are
necessary, and whether there exists a smaller language that also has these good properties
for composition. Interestingly, it can also be proved that all the features of SO tgds are nec-
essary to deal with the composition operator, as every SO tgd defines the composition of a
finite number of mappings specified by st-tgds. This fact, which is the converse of
Theorem
19.11
, shows that SO tgds are exactly the right language for representing the composition
of mappings given by st-tgds.
