Database Reference
In-Depth Information
21
Structural characterizations of schema mapping
Mappings are logical specifications of the relationship between schemas. In data exchange,
one typically restricts the kind of dependencies allowed in mappings, either to be able to
find more efficient procedures for constructing solutions and answering target queries, or
to make mappings have desirable properties, such as closure under composition. These two
tasks could be contradictory. For instance, the mapping language of SO tgds ensures clo-
sure under composition, but such mappings include a form of second-order quantification
that can be difficult to handle in practice. Thus, it is desirable to replace an SO tgd by an
equivalent set of st-tgds whenever possible.
In this chapter, we consider the problem of simplifying schema mappings by providing
characterizations of the most common classes of mappings in terms of the structural prop-
erties they satisfy. The main goal for studying these properties is to isolate the features
that different classes of mappings satisfy, and to understand what one can lose or gain by
switching from one class of mappings to another. We present basic structural properties
and then we use them to characterize the class of mappings specified by st-tgds, both gen-
erally, and in LAV and GAV scenarios. We also show that the structural characterizations
can be used to derive complexity-theoretical results for testing definability of a mapping
into some class of mappings.
21.1 Structural properties
In this chapter, we restrict our attention to mappings that do not make use of target de-
pendencies. We now view mappings in a purely semantic way: we think of them as binary
relations. Formally, in this section a mapping
M
from a source schema R
s
to a target
schema R
t
is a set of pairs (
S
,
T
) in I
NST
(R
s
)
I
NST
(R
t
). The only restriction we impose
on them is that they must be closed under isomorphisms. By isomorphisms we mean iso-
morphisms in the usual mathematical sense: in particular, they do not distinguish between
constants and null values, thus they can map a constant to a null value and vice versa.
For example, if a pair of instances with the source
×
{
(
⊥
,
1)
}
and the target
{
(1
,
⊥
)
}
is in
⊥
)
⊥
,
5)
the mapping, then a pair of instances with the source
is
in the mapping too, since they represent the same transformation: swapping the elements.
{
(5
,
}
and the target
{
(
}
