Database Reference
In-Depth Information
16
Endnotes to Part Three
16.1 Summary
•
In XML schema mappings, analogs of st-tgds
state how patterns over the source
translate into patterns over the targets.
•
Conditions imposed by XML schemas on the structure of target instances can contra-
dict conditions imposed by st-tgds. This makes the existence of solutions an issue even
without target dependencies.
•
Testing existence and materializing solutions is tractable (for a fixed mapping).
•
Query answering, even for XML analogs of relational conjunctive queries, can be in-
tractable (
CO
NP-complete,
to be exact), and is tractable only under the following re-
strictions:
1. mappings that use nested-relational DTDs and patterns with child navigation and
equality comparisons only; and
2. queries that use vertical navigation (child, descendant), wildcard, and equality com-
parisons.
•
In this restricted case there is a polynomial-time algorithm that builds a universal solu-
tion for a given tree. Then certain answers can be computed by evaluating the query in
that solution.
•
For real-life XML-to-XML queries, certain answers' semantics has to be redefined. A
notion of certain answers consistent with the traditional one can be built upon max-
descriptions, maximally informative patterns holding in every possible answer.
•
Under this semantics certain answers can be computed for mappings that use nested-
relational DTDs and patterns with child and descendant navigation, wildcards, and
equality.
•
If schemas are assumed to be nested-relational DTDs, and mappings and queries are
both based on patterns using only child and equality, certain answers can be computed
via a translation to the relational case.
