Database Reference
In-Depth Information
an XML tree
T
, the instance I
NL
D
OC
(
T
,
D
) that corresponds to the shredding of
T
with
respect to
D
always satisfies the constraints in I
NL
S
CHEMA
(
D
).
Proposition 15.4
Let D be a DTD, and T an XML tree such that T conforms to D. Then
I
NL
D
OC
(
T
,
D
)
is an instance of the schema computed by
I
NL
S
CHEMA
(
D
)
.
15.3 Translations of patterns, mappings and queries
To ensure that the remaining requirements are satisfied and we can implement XML data
exchange via relational translations, we need to show how to translate mappings and
queries. Since both are based on patterns, we deal with patterns first; then translations
of mappings and queries become easy extensions of pattern translations.
Restrictions on patterns
In addition to restrictions on DTDs, we had to impose restrictions on schema mappings to
ensure tractability. Those restrictions essentially boiled down to omitting horizontal navi-
gation, as well as the descendant axis, and not allowing wildcards. That is, patterns that we
deal with in tractable XML data exchange are defined inductively as follows:
•
(
x
) is a pattern, where
is a label, and
x
is a (possibly empty) tuple of variables (listing
attributes of a node);
•
(
x
)[
π
1
,...,
π
k
] is a pattern, where
π
1
,...,
π
k
are patterns, and
and
x
are as above.
We write
(
x
) to indicate that
x
is the tuple of all the variables used in a pattern.
As before, we shall write
π
π
1
/
π
2
instead of
π
1
[
π
2
]. The semantics, of course, is exactly
the same as in
Chapter 11
.
Example 15.5 Consider again the tree
T
from
Figure 15.2
, and the tree pattern
π
(
x
,
y
)=
r
/
book
(
x
)
/
author
/
name
(
y
)
.
This patterns finds topics together with the names of their authors. The evaluation of
(
x
,
y
)
over
T
returns the tuples (
'Algorithm Design'
,
Tardos
), (
'Algorithm Design'
,
Kleinberg
),
and (
'Algebra'
,
Hungerford
).
π
is
compatible
with
D
if there exists
atree
T
that conforms to
D
and a tuple of attribute values
a
such that
Given a DTD
D
and a tree pattern
π
, we say that
π
(
a
) holds in
T
.
Of course it only makes sense to consider compatible patterns in mappings and queries.
Note that while in general, checking compatibility of patterns with DTDs is NP-complete
(see
Theorem 11.7
), for nested-relational DTDs we consider here it can be easily done in
polynomial time.
π
Example 15.6 (
Example 15.5
continued) The pattern
(
x
,
y
) is compatible with the DTD
D
we are using in our examples. On the other hand, the pattern
π
π
(
x
)=
r
/
author
(
x
) is
not compatible, because no tree consistent with
D
can have a child of
r
labeled as
author
,
nor an
author
-labeled node with an attribute.
