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

σ