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
(
book
→
↓
,
=), with nested-relational DTDs and patterns using child relation and equal-
ity.
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
constraints.
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
M
between a source DTD
D
s
and a target DTD
D
t
, its translation
σ
(
M
) 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
M
is a universal solu-
tion for
σ
D
s
(
T
) under
σ
(
M
);and
(b) each universal solution for
σ
D
s
(
T
) under
σ
(
M
) 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
M
M
over a source tree
T
is the same as computing a
σ
(
M
)-
solution of
(
Q
) over that solution, as is nor-
mally done in a relational data-exchange system.
σ
(
T
), followed by evaluation of
σ
