Database Reference
In-Depth Information
However, the following example proves that this is not the case, as it shows two mappings
specified by st-tgds whose composition cannot be specified by a set of such dependencies.
Example 19.2 Consider a schema R
1
consisting of one binary relation
Takes
,thatas-
sociates a student name with a course she/he is taking, a schema R
2
consisting of a rela-
tion
Takes
1
, that is intended to be a copy of
Takes
, and of an additional relation symbol
Student
, that associates a student with a student id; and a schema R
3
consisting of a bi-
nary relation symbol
Enrolled
, that associates a student id with the courses this student is
taking. Consider now mappings
M
12
and
M
23
specified by the following sets of st-tgds:
Σ
12
=
{
Takes
(
n
,
c
)
→
Takes
1
(
n
,
c
)
,
Takes
(
n
,
c
)
→∃
s
Student
(
n
,
s
)
}
,
Σ
23
=
{
Student
(
n
,
s
)
∧
Takes
1
(
n
,
c
)
→
Enrolled
(
s
,
c
)
}
.
Mapping
M
12
requires that a copy of every tuple in
Takes
must exist in
Takes
1
and,
moreover, that each student name
n
must be associated with some student id
s
in the relation
Student
. Mapping
M
23
says that if a student with name
n
and id
s
takes a course
c
,then
(
s
,
c
) is a tuple in the relation
Enrolled
. Intuitively, in the compositionmapping one would
like to replace the name
n
of a student by a student id
i
n
, and then for each course
c
that is
taken by
n
, one would like to include the tuple (
i
n
,
c
) in the table
Enrolled
. Unfortunately,
it can be formally proved that it is not possible to express this relationship by using a set
of st-tgds.
In particular, an st-tgd of the form:
Takes
(
n
,
c
)
→∃
y
Enrolled
(
y
,
c
)
does not express the desired relationship, as it may associate a distinct student id
y
to each
tuple (
n
,
c
) in
Takes
and, thus, it may create several ids for the same student name.
Intuitively, the correct composition mapping in this case should postulate that the student
id depend solely on the name, and not the course. This could, intuitively, be expressed as
follows:
Takes
(
n
,
c
)
→
Enrolled
(
f
(
n
)
,
c
)
,
where
f
(
) is a function associating an id with a name. This intuition will be made precise
in this chapter.
·
The previous example shows that st-tgds are not enough to specify the composition of
st-tgd mappings. In other words, st-tgd mappings are not closed under composition. So to
achieve closure under composition, we could use two approaches:
•
we could restrict the class of mappings so that their compositions are expressible with
st-tgds; or
•
alternatively, we could extend the mapping language so that it captures compositions of
st-tgd mappings.
Of course, the second approach can be taken only if the complexity of the extended class
of mappings is feasible. This guides us in our search for classes of mappings closed under
composition.
