Databases Reference
In-Depth Information
determines
grade
. This functional dependency would then force the equality of
G
1
and G
3
, and also the equality of G
2
and G
4
in the above instance.
Composition Algorithm.
Next, we explain on our example how the composition
algorithm of
Fagin et al.
[
2005b
] arrives at the formula that specifies
M
ı
M
0
.
We give an intuitive explanation of the algorithm rather than a complete and formal
one. Recall that
M
is specified by the following GAV s-t tgds
M
W
Takes
.s;m;
co
/ !
Student
.s;m/
Takes
.s;m;
co
/ !
Enrolled
.s;
co
/
M
0
is specified by the following GLAV s-t tgd
and that
0
W
Student
.s;m/ ^
Enrolled
.s;
co
/ !9G
Takes
0
.s;m;
co
;G/:
M
Intuitively, the composition algorithm will replace each relation symbol from
T
M
0
by relation symbols from
S
using the GAV s-t tgds of
M
in
. In this case, the
M
0
can be replaced by
fact
Student
.s;m/ that occurs on the left-hand side of
a
Takes
fact, according to the first GAV s-t tgd of
M
. Hence, we arrive at an
intermediate tgd shown below:
Takes
.s;m;
co
0
/ ^
Enrolled
.s;
co
/ !9G
Takes
0
.s;m;
co
;G/:
Observe that a new variable
co
0
in
Takes
is used instead of
co
.Thisavoidsan
otherwise unintended join with
Enrolled
, which also contains the variable
co
.
(This is accomplished in the algorithm by a variable renaming step.)
Next, the composition algorithm will replace
Enrolled
.s;
co
/ with a
Takes
fact, based on the second GAV s-t tgd of
. We then obtain the following GLAV
s-t tgd from the source schema
S
to the new target schema
T
0
. This tgd
3
M
specifies
M
ı
M
0
.
the composition
Takes
.s;m;
co
0
/ ^
Takes
.s;m
0
;
co
/ !9G
Takes
0
.s;m;
co
;G/:
3.2
Source Evolution: The Case of a Lossless Mapping
Let us now assume that the source schema evolves to a new schema
S
00
consist-
ing of the two relations
Takes
00
and
Course
showninFig.
7.2
. Thus, in the new
schema, courses are stored in a separate relation and are assigned ids (
cid
). The
relation
Takes
00
is similar to
Takes
except that
course
is replaced by
cid
.Let
us assume that the source evolution is described by the following LAV mapping:
3
Note that it is logically equivalent to the earlier way we expressed
M
ı
M
0
, and where the roles
of
co
and
co
0
were switched.
