Database Reference
In-Depth Information
19
Mapping composition
In
Chapter 17
we described two key operations on schema mappings: composition and
inverse. These operators are needed to describe schema evolution and transformations of
data according to the changing schema. In this chapter we study mapping composition. The
goal of the composition operator is to generate a mapping
M
13
that has the same effect as
applying successively two given mappings
M
12
and
M
23
, provided that the target schema
of
M
23
. We shall see that in the relational case
such a mapping can always be specified with st-tgds extended with second-order quantifi-
cation or, equivalently, Skolem functions. In the XML case, the composition mapping can
be generated only if the set of available axes is restricted.
M
12
is the same as the source schema of
19.1 The notion of composition and key problems
As mentioned in
Chapter 17
, the semantics of the composition operator can be defined in
terms of the semantics of this operator for binary relations.
Definition 19.1 (Composition operator) Let
S
1
,
S
2
,
S
3
be relational or XML schemas.
Let
M
12
be a mapping from
S
1
to
S
2
,and
M
23
a mapping from
S
2
to
S
3
. Then the
composition of
M
12
and
M
23
is defined as
=
(
S
1
,
S
3
)
.
there exists an instance
S
2
of schema
S
2
such that
M
12
◦
M
23
(
S
1
,
S
2
)
∈
M
12
and (
S
2
,
S
3
)
∈
M
23
For example, for the mappings
M
12
,
M
23
,and
M
13
shown in
Chapter 17
,
M
13
corre-
sponds to the composition of
. It is important
to notice that this example shows two mappings specified by st-tgds whose composition
can also be specified by such dependencies. In contrast, the definition of the composition
operator itself only defines the
semantics
of the composition and does not say anything
about the existence of a
syntactic
specification of this mapping.
This motivates the first fundamental question about the composition operator, namely
whether the composition of st-tgds can always be specified in the same logical language.
At first glance, one may be tempted to think that the answer to this question is positive,
and that the example in the introduction can be generalized to any composition of st-tgds.
M
12
and
M
23
since
M
13
=
M
12
◦
M
23
