Database Reference
In-Depth Information
not allowed to include extra values in the range of
f
,then(
S
,
T
)
|
=
σ
, as in this case the
only possible valuation of
f
maps
a
into itself since D
OM
(
S
)
∪
D
OM
(
T
)=
{
a
}
.
As shown in the previous example, the inclusion of extra values when interpreting the
function symbols of an SO tgd makes a difference. But it should be noticed that the
possibility of using an infinite set of extra values is not significant in the case of SO tgds,
as the domain and range of the witnessing valuations can be restricted to a finite superset
of D
OM
(
S
)
D
OM
(
T
), polynomial in the size of
S
and
T
(see
Exercise 22.3
).
Several features of SO tgds make them the right language for composition. First, it is
easy to see that every set of st-tgds can be transformed into an SO tgd. In fact, the well-
known Skolemization method can be used to compute an SO tgd equivalent to a set of
st-tgds. For example, the following set of st-tgds from
Example 19.2
:
∪
Takes
(
n
,
c
)
→
Takes
1
(
n
,
c
)
,
Takes
(
n
,
c
)
→∃
s
Student
(
n
,
s
)
is equivalent to the SO tgd:
f
∃
∀
n
∀
c
(
Takes
(
n
,
c
)
→
Takes
1
(
n
,
c
))
∧
→
Student
(
n
,
f
(
n
,
c
)))
.
∧∀
n
∀
c
(
Takes
(
n
,
c
)
Essentially, the existentially quantified variables are replaced with terms using fresh func-
tion symbols. It is very natural to just list the conjuncts of SO tgds omitting the existential
second-order quantifiers and the universal first-order quantifiers. Under this convention,
the SO tgd above is presented as the following set of rules:
Takes
(
n
,
c
)
→
Takes
1
(
n
,
c
)
,
Takes
(
n
,
c
)
→
Student
(
n
,
f
(
n
,
c
))
.
Second, it is possible to prove that SO tgds are closed under composition. That is, given an
SO tgd
σ
12
from a schema R
1
to a schema R
2
,andanSOtgd
σ
23
from R
2
to a schema R
3
,
there exists an SO tgd
σ
13
from R
1
to R
3
such that
M
13
=
M
12
◦M
23
,where
M
13
,
M
12
and
M
23
are the mappings defined by
σ
13
,
σ
12
and
σ
23
, respectively.
Example 19.7 We show here how to compute the composition of two SO tgds by consid-
ering a variation of the mappings used in the proof of
Theorem 19.3
.LetR
1
be a schema
consisting of a unary relation
node
and a binary relation
edge
, R
2
a schema consisting
of binary relations
coloring
and
edge
,andR
3
a schema consisting of unary relations
error
and
color
. Moreover, let
M
12
=(R
1
,
R
2
,
Σ
12
) and
M
23
=(R
2
,
R
3
,
Σ
23
),where
Σ
12
consists of the following st-tgds:
node
(
x
)
→∃
y
coloring
(
x
,
y
)
,
→
edge
(
x
,
y
)
,
edge
(
x
,
y
)
