Database Reference
In-Depth Information
europe
country
( Scotland )
country
( England )
ruler
( James V )
ruler
( Mary I )
ruler
( James VI&I )
ruler
( Charles I )
ruler
( Elizabeth I )
ruler
( James VI&I )
ruler
( Charles I )
Figure 10.1 An XML tree: an example
ε
0
1
00 01 02 03
10 11 12
Figure 10.2 Unranked tree domain for the XML tree in Figure 10.1
XML documents: definition
To define XML documents, we need to specify both their structure and the data they carry.
The structure, as we already mentioned, comes in the shape of a tree. Unlike binary trees
(considered, for example, in Section 2.5 ), trees describing XML documents may have in-
ternal nodes with different numbers of children. For example, in the document shown in
Figure 10.1 , the root has two children, the Scotland node has four, and the England node
has three. We refer to such trees as unranked trees .
We describe the nodes of the tree by paths to them from the root . For example, the
Mary I node is the second child of the first child of the root, hence we describe it by the
sequence 01. Note that we start numbering children from 0, i.e., the first child is numbered
0, the second is numbered 1, and so on. The node corresponding to Charles I as the ruler
of England is the third child of the second child of the root, hence we describe it by the
sequence 12. In general each node is a sequence of natural numbers, i.e., a string over
.
If we have such a node s = i 1 i 2 ... i k , then all its prefixes i 1 ... i m for m < k are nodes of the
tree as well, as they lie on the path from the root to s .Furthermore,if s
N
·
i is a node in a
tree, then so is s
j for j < i : that is, if there is, say, a third child of a node, there must be
the first and the second as well. This leads to the following definition.
·
N
of strings of natural numbers that contains with each element all its prefixes (i.e., is prefix
closed) and such that s
Definition 10.1 (Unranked tree domain) An unranked tree domain is a finite set U
·
i
U implies s
·
j
U for all i , j
N
satisfying j < i .
The unranked tree domain of the tree from Figure 10.1 is shown in Figure 10.2 .
With this, we can formally define XML documents over a given labeling alphabet (i.e.,
the set of element types) and a set of attributes as follows.
Definition 10.2 (XML trees) Given a labeling alphabet
Γ
of element types and a set of
Search WWH ::




Custom Search