Database Reference
In-Depth Information
country
(
England
)
ruler
(
Elizabeth I
)
ruler
(
James VI&I
)
ruler
(
Charles I
)
Figure 10.3 A subtree of the XML tree form
Figure 10.1
attributes
Att
,
XML trees (documents)
over
Γ
and
Att
are structures
T
=(
U
,
↓
,
→
,
lab
,
(
ρ
a
)
a
∈
Att
)
,
where
•
U
is an unranked tree domain;
•↓
is the binary
child
relation on
U
, i.e.,
s
↓
s
·
i
whenever both
s
and
s
·
i
are in
U
;
•→
is the binary
next-sibling
relation, i.e.,
s
·
i
→
s
·
(
i
+1) whenever both
s
·
i
and
s
·
(
i
+1)
are in
U
;
•
lab
:
U
→
Γ
is the labeling function; and
•
each
ρ
a
is a partial function from
U
to
V
, the fixed domain of attribute values, or
data
values
, that gives the values of attribute
a
for all the nodes in
U
where it is defined.
Consider again the document shown in
Figure 10.1
. It has 10 nodes, as depicted in
Figure 10.2
. The root is always
, the empty string, the children of the root are 0 and 1,
both labeled
country
, the children of 0 are 00
,
01
,
02, and 03, and the children of 1 are
10
,
11, and 12, all of which are labeled
ruler
. If we assume that both
country
and
ruler
have an attribute
@name
defined for them, then the values of this attribute, assigned by the
function
ε
@
name
(03)=
Charles I
.
Very often we will need to talk about parts of XML trees. A most basic part is the
subtree
rooted at some given node. For example, the subtree of the document in
Figure 10.1
rooted
at node 1 is the tree shown in
Figure 10.3
. Formally, we define subtrees as follows.
ρ
@
name
, are as shown in the figure, e.g.,
ρ
Definition 10.3 Let
T
=(
U
,
↓
,
→
,
lab
,
(
ρ
a
)
a
∈
Att
) be an XML tree and let
v
∈
U
be its
node. The
subtree of T rooted at v
is the XML tree
T
.
v
=
v
−
1
U
,
a
)
a
∈
Att
T
.
v
,
T
.
v
,
lab
T
.
v
,
(
T
.
v
↓
→
ρ
where
{
w
vw
∈
U
}
•
v
−
1
U
=
is the set of all words in
U
having
v
as a prefix;
T
.
v
and
T
.
v
are the child and sibling relations restricted to
v
−
1
U
,and
•↓
→
lab
T
.
v
(
w
) and
ρ
a
in
T
,i.e.,
lab
T
.
v
(
w
)=
lab
(
vw
),and
T
.
v
a
•
ρ
are inherited from
lab
and
T
.
a
(
w
)=
ρ
ρ
a
(
vw
).
,the
root's children are 0
,
1
,...,
k
, etc. For example, the node storing the value
Charles I
is 12
in the original document, but in the subtree it is 2.
Observe that the definition assures that the subtree is an XML tree, i.e., its root is
ε