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
ε
Search WWH ::




Custom Search