Database Reference
In-Depth Information
11
Patterns and mappings
XML schema mappings are expressed in terms of
tree patterns
, a simple query language
for XML trees that plays the role analogous to that of conjunctive queries for relational
databases. In this chapter we define the syntax and semantics of tree patterns, introduce a
classification based on the features they use, and determine the complexity of basic com-
putational problems. Then we do the same for XML schema mappings.
11.1 Tree patterns: classification and complexity
In XML trees information can be represented by means of data values, as well as the
structure of the tree. Let us return to the example shown in
Figure 10.1
. The edge between
the node storing
Scotland
and the node storing
Mary I
represents the fact that Mary I
ruled Scotland. The value
Charles I
appearing twice informs us that Charles I ruled both
Scotland and England. The node storing
Mary I
coming directly after the node storing
James V
corresponds to the fact that Mary I succeeded James V on the throne of Scotland.
This already suggests the querying features needed to extract information from XML trees:
child
,
next sibling
, and their transitive closures:
descendant
,
following sibling
. We call these
four features
axes
. It is also necessary to compare data values stored in different nodes.
In the light of
PART TWO
, a natural query language for XML trees is the family of
conjunctive queries over XML trees viewed as databases over two sorts of objects: tree
nodes, and data values. Relations in such representations include child, next sibling, and
relations associating attribute values with nodes.
To avoid the syntactically unpleasant formalism of two-sorted structures, conjunctive
queries on trees are best formalized by means of tree patterns with variables for attribute
values. Nodes are described by formulae
(
x
),where
is either a label or the wildcard ,
and
x
is a tuple of variables corresponding to the attributes of the node (possibly empty).
For each node, a list of its children and descendants is specified, together with (perhaps
partial) information on their order.
For instance, the pattern on the left of
Figure 11.1
expresses that
y
succeeded ruler
x
in
some country; the solid edges of the tree express the child relation, and the solid arrow
denotes the next-sibling relation. The middle patterns simply says that
x
is a ruler; the
dashed edge expresses the descendant relation. The pattern on the right expresses that
x
