Database Reference
In-Depth Information
technique that enables us to encode target schemas by means of constraints that guaran-
tee chase termination.
As for the complexity issue, we have seen ( Theorem 13.9 ) that the essential restric-
tion to ensure tractability of XML query answering in data exchange is the restriction
to nested-relational DTDs. Recall that these are DTDs with rules like db
book ,
author subject . The second essential restriction is to use patterns based only
on the child relation. That is, in our terminology, we are dealing with mappings from the
class SM nr (
, =), with nested-relational DTDs and patterns using child relation and equal-
These restriction are helpful in suggesting a shredding scheme. They do not go well with
schema-less representations, but match well the inlining scheme (which we shall define
formally later). It works very well with nested-relational DTDs and child-based patterns,
and generates relational schemas that only use acyclic constraints, which is perfect for
data-exchange scenarios.
Desiderata for the translation
We now formulate some basic requirements for the translation
, in order to be able to
achieve our goals described in the diagram above.
Requirement 1: translation of schemas The translation
( D ) appliedtoaDTDofaspe-
cial form (nested-relational) produces a relational schema that has only acyclic
Requirement 2: translation of documents The translation
) for a DTD D , applied
to document T conforming to D , produces relational database
σ D (
σ D ( T ) of schema
( D ).
Requirement 3: translation of queries For a DTD D , the translation
σ D ( Q ) of conjunc-
σ D ( Q ) σ D ( T ) = Q ( T ). In other words, the result of Q ( T )
can be computed by relational translations.
Requirement 4: translation of mappings For a mapping
tive queries Q satisfies
between a source DTD D s
and a target DTD D t , its translation
) is a mapping between
( D s ) and
( D t ) that preserves universal solutions. That is:
(a) each
σ D t -translation of a universal solution for T under
is a universal solu-
tion for
σ D s ( T ) under
(b) each universal solution for
σ D s ( T ) under
) contains a
σ D t -translation of a
. Note that we cannot possibly require equiv-
alence, as relational solutions are open to adding new tuples and thus cannot
always be translations of trees.
Requirement 5: query answering For conjunctive queries over trees, computing the an-
swer to Q under
universal solution of T under
over a source tree T is the same as computing a
solution of
( Q ) over that solution, as is nor-
mally done in a relational data-exchange system.
( T ), followed by evaluation of
Search WWH ::

Custom Search