Databases Reference
In-Depth Information
we are in an “easy” case where we can express the result of this composition as a
GLAV mapping. This is essentially due to the fact that the first mapping is GAV.
(The second mapping
M
0
is a GLAV mapping.) We shall see that in cases where
M
is LAV or GLAV the composition need not be first-order and we need a more
powerful language to express the composition. For the scenario in this section, the
fact that the composition is a GLAV mapping follows from the next theorem.
Theorem 1
(
Fagin et al. 2005b
).
Let
M
1
and
M
2
be two consecutive schema
mappings. The following hold:
1.
If
M
1
and
M
2
are GAV mappings, then
M
1
ı
M
2
can be expressed as a GAV
mapping.
2.
If
M
1
is a GAV mapping and
M
2
is a GLAV mapping then
M
1
ı
M
2
can be
expressed as a GLAV mapping.
As a more general result, we obtain the following corollary that applies to a chain
of GAV mappings followed by a GLAV mapping.
Corollary 1.
Let
M
1
;:::;
M
kC1
;
M
k
be consecutive schema mappings. If
M
1
,
:::;
M
k
are GAV mappings and
M
kC1
is a GLAV mapping, then the composition
M
1
ı :::ı M
k
ı
M
kC1
can be expressed as a GLAV mapping.
Concretely, for our scenario, it can be verified that the following GLAV mapping
is the composition of
M
and
M
0
:
M
ı
M
0
W
Takes
.s;m;co/^
Takes
.s;m
0
;
co
0
/ !9G
Takes
0
.s;m;
co
0
;G/
Observe that the self-join on
Takes
in the above composition is needed. This can
be traced to the fact that students can have multiple majors, in general. At the same
time, the
Takes
relation need not list all combinations of
major
and
course
for
agiven
sid
. However, the evolution mapping
M
0
requires all such combinations.
M
ı
M
0
correctly accounts for all these subtle semantic aspects.
To see a concrete example, consider the following instance of
Takes
:
Takes
.007;
Math
;
MA
201/
Takes
.007;
CS
;
CS
101/
In the above instance, 007 identifies a student (say, Ann) who has a double major (in
Math and CS) and takes two courses. Given the above instance, the composition
M
ı
M
0
requires the existence of the following four
Takes
0
facts, to account for
all the combinations between Ann's majors and the courses that Ann took.
Takes
0
.007;
Math
;
MA
201;G
1
/
Takes
0
.007;
Math
;
CS
101;G
2
/
Takes
0
.007;
CS
;
MA
201;G
3
/
Takes
0
.007;
CS
;
CS
101;G
4
/
In practice, we would also have an additional target constraint (a functional
dependency) on
Takes
0
specifying that
sid
together with
course
functionally
The composition
