Database Reference
In-Depth Information
18
Consistency of schema mappings
The goal of this chapter is to analyze the consistency problem for schema mappings: that
is, whether a mapping can be applied to some source instance, or to all source instances,
to generate a target instance. The first problem is referred to as consistency, and the second
as absolute consistency. Since these problems are easily solvable for relational mappings
without target dependencies, we concentrate on those problems in the XML context.
We start by proving that without comparisons of data values in st-tgds, the consis-
tency problem is solvable in single-exponential time, and the bound cannot be improved.
When comparisons are added, it quickly becomes undecidable. However, the complexity
drops dramatically for nested-relational DTDs. As for absolute consistency, the problem
is actually much harder to solve: a priori even decidability is not clear. We do present
an algorithm, very different from the algorithm for consistency, that solves the problem
with exponential space (rather than time) bounds, and look for special cases that lead to
lower-complexity algorithms.
18.1 Problems statements
Consider a relational mapping
st
of st-tgds.
Note that the mapping does not have any target dependencies. In that case, we know that
S
OL
M
(
S
)
= 0 for every instance
S
of R
s
. In fact, assuming that
M
is fixed, we have
given polynomial-time algorithms that compute, for each source instance, solutions with
good properties (see
Sections 6.3
and
6.4
). Thus, consistency is not an issue for the class
of mappings specified by st-tgds: both consistency, as we described it in
Chapter 17
,and
absolute consistency, are trivially solvable, since the answer is simply “yes”.
On the other hand, the tree model used in the case of XML data exchange gives more
opportunities for expressing structural properties of data even with simple queries based on
patterns. In fact, we have already seen that schemas can impose strong conditions on the
structure of source and target instances, entering into complex interactions with source-
to-target dependencies, which makes consistency one of the central issues in XML data
exchange.
Unlike relational mappings, XML schema mappings may be inconsistent: there are map-
pings
M
=(R
s
,
R
t
,
Σ
st
) specifiedbyafiniteset
Σ
M
so that
M
= 0, i.e., no tree has a solution. In addition to consistent mappings,
