Database Reference
In-Depth Information
22
Endnotes to Part Four
22.1 Summary
•
A reasonable mapping should be consistent, i.e., there should be at least one source
instance admitting a solution. A stronger notion of consistency, called
absolute consis-
tency
, demands a solution for every source instance.
•
For relational mappings specified by st-tgds, both consistency and absolute consistency
are trivial problems, as every source instance admits a solution in this case.
•
In the XML setting consistency problems are difficult. Even in the absence of data com-
parisons, checking consistency requires exponential time, and if data comparisons are
allowed, the problem is undecidable. Consistency is only tractable when the schema
language is restricted to nested-relational DTDs, and mappings use only vertical order.
•
The absolute consistency problem is decidable for the class of all XML schema map-
pings. The problem can be solved in exponential space, but a single-exponential time
algorithm is unlikely. For schemas admitting only trees of some bounded depth, the
complexity is within the polynomial hierarchy, so the problem can be solved by a single-
exponential time algorithm.
•
Two of the most important operations on mappings are composition and inversion.
•
Composition of mappings maps an instance
I
to an instance
J
,if
I
is mapped by the first
mapping to an intermediate instance
K
, which is then mapped by the second mapping to
J
.
•
To express syntactically a composition of schema mappings, one needs to state that a null
value in the target only depends on some particular values in the source. This can be
achieved by enriching the mapping language with function symbols that are quantified
existentially (Skolem functions).
•
Composition of relational mappings specified by st-tgds can be specified with SO tgds
(st-tgds extended with function symbols).
•
Composition of XML schema mappings is problematic as soon as disjunction is allowed
in schemas.
•
For mappings between nested-relational DTDs, a syntactic representation of the compo-
sition is guaranteed only if the mappings use no wildcard, descendant, sibling order and
