Database Reference
In-Depth Information
K
T
◦
a
a
a
◦
b
b
T
1
T
2
T
3
Figure 12.1 A
D
-kind
K
and a tree
T
∈
L
(
K
). The trees
T
1
,
T
2
have label
a
in the root and conform
to
D
a
;
T
3
has label
b
in the root and conforms to
D
b
.
work with a multicontext, called a
kind
, that contains this tree and has a port wherever new
nodes can be added according to the DTD. For the sake of uniformity, in the definition of
kind we assume that whenever the DTD contains a rule
+
...
, each
τ
→
...
σ
τ
-node in the
kind has one
σ
-child.
Definition 12.9 For a nested-relational DTD
D
over
Γ,a
D
-
kind K
is any XML tree
Γ
∪{◦
σ
σ
∈
Γ
}
conforming to the DTD
D
over
obtained by replacing for each
σ
, each
σ
∗
by
+
by
occurrence of
σ
? with
σ
, each occurrence of
◦
σ
, and each occurrence of
σ
σ
·◦
σ
, where the fresh labels
◦
σ
have no attributes and their productions are
◦
σ
→
ε
.
Note that for a nested-relational DTD
D
,all
D
-kinds are identical up to data values.
For a kind we define a set of trees that can be obtained from it by substitutions at ports,
according to the additional information provided by the label of the port.
Definition 12.10 Let
D
be a nested-relational DTD and let
D
σ
stand for the DTD obtained
from
D
by changing the root symbol to
.AnXMLtree
T agrees
with a
D
-kind
K
if
T
can
be obtained from
K
by substituting at each port labeled with
σ
◦
σ
a forest (possibly empty)
consisting of trees conforming to the DTD
D
σ
.By
L
(
K
) we denote the set of XML trees
that agree with
K
.
An illustration of these notions is given in
Figure 12.1
.Thetree
T
shown in the figure is
obtained from
K
by substituting
T
1
+
T
2
at the port labeled with
◦
a
and
T
3
at the port labeled
with
◦
b
.
Directly from the definition we get that for every nested-relational DTD
D
,
T
T
=
{
|
=
D
}
{
L
(
K
)
|
K
is a
D
-kind
}
.
(12.2)
L
(
K
) there exists a
witnessing substitution
: a sequence of forests
and contexts
T
u
, with
u
ranging over the ports of
K
, such that substituting each
u
in
K
with
T
u
we obtain
T
. It is easy to check that
T
u
is unique (
Exercise 16.3
). The combining
operation can be described as follows.
Note that for each
T
∈
