Database Reference
In-Depth Information
Theorem 19.13
Every SO tgd defines the composition of a finite number of mappings,
each defined by a finite set of st-tgds.
We do not provide the proof of
Theorem 19.13
, instead we show the main ideas behind
this proof in the following example.
Example 19.14 Let R
s
be a schema consisting of a unary relation
P
and R
t
a schema
consisting of a binary relation
R
. Furthermore, assume that the relationship between these
schemas is given by the following SO tgd
σ
:
R
f
(
g
(
x
))
,
g
(
f
(
x
))
.
∧
→
P
(
x
)
f
(
x
)=
g
(
x
)
(19.4)
We show here the essential steps of an algorithm that, given an SO tgd
, generates a finite
sequence of mappings that are given by st-tgds and whose composition is defined by
σ
.
For the sake of readability, let R
1
be the schema R
s
. The algorithm starts by generating a
schema R
2
, consisting of binary relations
F
1
,
G
1
and of a unary relation
P
1
, and a mapping
M
12
=(R
1
,
R
2
,
σ
Σ
12
) that is specified by a set
Σ
12
of st-tgds consisting of the following
dependencies:
P
(
x
)
→
P
1
(
x
)
,
P
(
x
)
→∃
yF
1
(
x
,
y
)
,
P
(
x
)
→∃
zG
1
(
x
,
z
)
.
Intuitively,
P
1
is a copy of
P
,
F
1
(
x
,
y
) indicates that
f
(
x
)=
y
,and
G
1
(
x
,
y
) indicates that
g
(
x
)=
y
. In particular, the second and third dependencies above have the effect of guar-
anteeing that
f
(
x
) and
g
(
x
) are defined for every element
x
in
P
, respectively. Then the
algorithm generates a schema R
3
, consisting of binary relations
F
2
,
G
2
and of a unary
relation
P
2
, and a mapping
M
23
=(R
2
,
R
3
,
Σ
23
) that is specified by a set
Σ
23
of st-tgds
consisting of the following dependencies:
P
1
(
x
)
→
P
2
(
x
)
,
F
1
(
x
,
y
)
→
F
2
(
x
,
y
)
,
G
1
(
x
,
y
)
→
G
2
(
x
,
y
)
,
F
1
(
x
,
y
)
→∃
uG
2
(
y
,
u
)
,
G
1
(
x
,
y
)
→∃
vF
2
(
y
,
v
)
.
As in the previous case,
P
2
is a copy of
P
1
,
F
2
(
x
,
y
) indicates that
f
(
x
)=
y
and
G
2
(
x
,
y
)
indicates that
g
(
x
)=
y
. In particular, all the values of
f
stored in
F
1
are also stored in
F
2
,
by the second dependency above, and all the values of
g
stored in
G
1
are also stored in
G
2
,
by the third dependency above. But not only that, the fourth dependency also guarantees
that
g
(
y
) is defined for all
y
in the range of
f
, and the fifth dependency guarantees that
f
(
y
)
is defined for all
y
in the range of
g
. Finally, let R
4
be the schema R
t
. Then the algorithm
generates a mapping
M
34
=(R
3
,
R
4
,
Σ
34
) that uses
P
2
,
F
2
and
G
2
to populate the target
