Bug Fixed Version of the Paper in ICDE 2010

Optimal Tree Node Ordering forChild/Descendant Navigations
Atsuyuki Morishima #1 , Keishi Tajima ∗2 , Masateru Tadaishi #3#

Graduate School of Library, Information, and Media Studies, University of Tsukuba
1-2 Kasuga, Tsukuba, Ibaraki 305-8550 Japan1
3

mori@slis.tsukuba.ac.jp
tada@slis.tsukuba.ac.jp∗

Graduate School of Informatics, Kyoto University
Yoshida-Honmachi, Sakyo, Kyoto 606-8501 Japan2tajima@i.kyoto-u.ac.jp

Abstract— There are many applications in which users interactively access huge tree data by repeating set-based navigations. In this paper, we focus on label-specific/wildcard children/descendant navigations. For efficient processing of these
operations in huge data stored on a disk, we need a node ordering
scheme that clusters nodes that are accessed together by these
operations. In this paper, (1) we show there is no node order thatis optimal for all these operations, (2) we propose two schemes,
each of which is optimal only for some subset of them, and (3)we show that one of the proposed schemes can process all these
operations with access to a constant-bounded number of regions
on the disk without accessing irrelevant nodes.

I. I NTRODUCTION
There are many applications in which users interactively
access huge tree data (e.g., file directories or huge XML data)
by repeating set-based navigations. In set-based navigation, auser specifies one node and a type of navigation. Then thesystem retrieves all the nodes reachable from that node via
that type of navigation. The user browses the retrieved nodes,
and select one node in order to repeat a set-based navigationfrom it. For exploration of huge data, set-based navigations
are more efficient than simple node-at-a-time navigations.
In such an interactive browse-and-traverse style of access,users rarely specify complex traverse conditions. In this paper,
we focus on the following most basic tree navigations:∗ll∗a → X, a →X, a →
X, a →X.

a → X is an operation that retrieves all the children of a given∗
node a, and a →X retrieves all the descendants of a. The
other two operations traverse only edges with a given label l.
For interactive access, we need to process these operations
efficiently. This is easy when data is stored on the main
memory. We can construct a tree structure on the memory
by using pointers. When data is huge and stored on the disk,
however, we need a storage scheme that can process these
operations with low I/O cost. In order to reduce I/O cost, weneed to store the nodes in an appropriate order so that nodes
that are accessed together by these operations are clustered.
Such an order is not trivial. Suppose we store nodes of atree in the depth-first order on a disk, as shown in Fig. 1.
Here, we assume each disk block can store three nodes. This

1i
"" bb
b 10i
"
6i
2i
 T
 T

i12i
3i4i5i7i8i9i11
Fig. 1.

sequential read of disk blocks-

1 2i3 4 5 6i7 8 9 10i11 12Retrieval of children on the depth-first order storage∗
storage scheme can efficiently process a →X for any node a,because the descendants of a are always stored in consecutive
positions, and we can read them out by one sequential accessto a contiguous disk region without reading irrelevant nodes(except for those in the blocks at the both ends of the region).
∗In that sense, the depth-first order is optimal for a →X.
On the other hand, this storage scheme is not efficient
for a → X, because children of a are interleaved by theirsubsequent descendants. As a result, if the children have
many subsequent descendants, we have to read many irrelevant
nodes stored in the same disk blocks as the relevant ones.
In addition, we have to read many incontiguous regions,which significantly degrade performance compared to accessto a single contiguous region, because of the today’s diskarchitecture and the prefetch by the OS. We can adhere to one
sequential access, but then we have to read irrelevant blocks
on the way. For example, for retrieving children of the node
1 (i.e., nodes 2, 6, 10) in Fig. 1, we have to read irrelevant
nodes 1, 3, 4, 5, 11, 12. In addition, we have to access two
incontiguous regions, or have to read an irrelevant block ofnodes 7, 8, 9, if we use a single sequential access.
In this way, the depth-first order is I/O-inefficient for the
retrieval of children. Notice that the breadth-first order hasa counter problem: children are consecutive, but descendants
are not. For efficient interactive exploration of huge data, weneed a node ordering scheme that clusters answers to all the
supported operations. When we consider general path queries,
including multi-step path patterns, twig patterns, or value
predicates, it is difficult to design such a scheme. However,when we concentrate only on the most fundamental operations
explained above, there exists non-trivial ordering schemes thatcan cluster answers to these operations quite well.

In this paper, first, we show that there is no single nodeordering scheme that is optimal for all the operations above.
Then we propose two schemes, each of which is optimal only
for some subset of them, and finally, but most important,
we show that one of the proposed schemes can process all
those operations with access to a constant-bounded number ofregions on the disk, without accessing irrelevant nodes.
Notice that our ordering schemes are advantageous even inapplications that support general path queries, if most queries
actually issued by users are the fundamental operations above.
II. R ELATED W ORK
There has been much research on indexing schemes andlabeling schemes for path queries, but indexing or labelingschemes do not necessarily answer the question of how toorder the nodes on the disk in order to minimize I/O cost.
There are also many processing schemes of path queries
that scan nodes in the depth-first order [1], [2], [3]. These
schemes avoid scanning some irrelevant nodes in order toreduce computation cost. The depth-first order is, however, not
I/O-optimal for retrieving children as explained above. [4] hasproposed a scheme which uses two B-tree indices so that we
can scan a tree in both depth-first and breadth-first order. Thisapproach, however, requires the cost to maintain two B-trees.
There has also been research on storage schemes for tree
data, such as [5], [6], [7]. However, they focus on either
multi-step path queries, or twig queries, and no research hasstudied storage schemes specializing in child and descendantqueries starting from a single node, although they are the mostfrequently used operations in interactive data exploration.
l∗
Also notice that our operation set includes a →X. Although
this is a very fundamental operation in set-based navigation,
no existing scheme can process it efficiently.
[8] proposed a node ordering scheme that is equivalent tothe scheme we use in the simplest case, i.e., when we only∗
consider a → X and a →X. Our contribution is to proposell∗schemes that also support a →X and a →X.
There are also research on succinct data structure for trees
supporting efficient navigation, and some studies, e.g., [9],[10], also support queries retrieving node sets. However, they
assume data fits in the memory, and do not discuss I/O-cost.
III. P ROPOSED N ODE O RDERING
We first show a node order that is optimal for both child anddescendant navigations. Then we show that there is no suchan optimal scheme when we introduce two more operations
that specify edge labels. We propose two schemes that are
optimal for only some subset of them, and then show that in
one proposed scheme, the number of disk regions we need toaccess for those operations is bounded by a small constant.
In this paper, we omit the proofs of the theorems and thecorrectness of the algorithms for space limitation.
∗
A. Child and Descendant Navigations: a → X and a →X

Now we show an optimal node order for a → X and∗a→
X. The requirement is to cluster both the children andi@i i@ i A
 A
i i i i A
i i
iFig. 2.

I

1i

II 2i

3i

@
@i
4

 A
 A
III 5i 6i 9i 10iV
 A
IV 7i 8i
iVI
11

(a)
(b)
Children/descendants of nodes and node order that cluster themthe descendants of every node. The boxes in Fig. 2(a) show
the node sets to cluster in a tree. Notice that these boxes either
include, are included by, or are disjoint with each other, i.e.,they never partially overlap. Therefore, there exists a nodeorder that clusters all these node sets. In fact, the node order<t defined on a tree t as below achieves the requirement.
∗
Optimal Ordering for a → X and a →X: <t
For any nodes n1 , n2 in a tree t,• if n1 (or n2 ) is the root node, n1 <t n2 (n2 <t n1 , resp.).
• if n1 and n2 are siblings, n1 <t n2 iff n1 precedes n2
in the sibling order in t,• otherwise, n1 <t n2 iff the parent of n1 precedes theparent of n2 in the depth-first order in t.
2
In other words, we group siblings that share the same parent,
we sort the groups in the depth-first order in t, and within eachgroup we sort nodes in their sibling order. For example, inFig. 2(b), the roman numbers I to VI designate the depth-firstorder of sibling groups, and the numbers 1 to 11 designate theorder given by <t . Then the following theorem holds for <t :Theorem 1: For any tree t and for any node a in it, its
children and descendants (excluding a itself) have consecutive
positions in the ordering defined by <t .
2
For example, children of the node 2 have consecutive numbers
5, 6, and its descendants have consecutive numbers 5, 6, 7, 8.
In the following, we call those numbers the addresses of thenodes, and write addr (n) to denote the address of the node n.
We store nodes on a disk in the order of <t , and for each noden, we store the address of its parent, denoted by parent(n),and the address of its first child, denoted by firstChild (n).
Fig. 3 shows how we store the tree in Fig. 2(b). Then we can∗process a → X and a →X by the procedures below:
Algorithm for a → X:
1) scan the node entries starting at firstChild (a), and2) stop the scan at a node n s.t. parent(n) 6= addr (a). 2∗
Algorithm for a →X:1) retrieve the children of a by the procedure above, and2) continue to read the following nodes, until we reach anode n s.t. parent(n) < firstChild (a).
2
For example, suppose we retrieve descendants of node 2 inFig. 2(b). We first scan its children 5 and 6. Then we proceed
to 7 and 8. During that scan, the addresses of already founddescendants are in the range from 5 to the current address ofthe scan. When we reach node 9, its parent is 4, which is notwithin that range. Therefore the node 4 is not a descendant of2, and therefore, node 9 is not a descendant, either.

addr (n):

2
1

5

1

1

2

-

9

1

3

4

Fig. 3.
1i

λµ

ω

λ

2i

λ

λ

λ

µ

µ

µ

6i

ω

7i

5i
8i

(a) conflict with a → X
Fig. 4.

2

6

5

-

5

7

8

4

9

4

11
10

10

11

Disk image of the tree data

1i

λ

µ

5

λ
λ @

@
@
2i 3i 4i
5i

7

2

3i 4i

@

6i 7i

i
9i 10

∗
(b) conflict with a →Xl∗Conflicts caused by a →X

The procedures above can retrieve children and descendants
by scanning a single consecutive region on the disk without
reading irrelevant nodes, except for the last node at which westop the scan. In real disk access, because the unit of disk
access is a disk block that includes many nodes, we do notread a irrelevant block unless the node at which we shouldstop happens to appear in the first entry of some block.
If necessary, we can prevent such unnecessary access bystoring in each block (1) a flag showing whether the last nodein the block is a last sibling, and (2) the number of ancestorsof the last node in the block which have that last node as thelast descendant. Here, we omit the details for space limitation.
ll∗B. Edge Labels: a →X and a →Xll∗
Now we introduce a → X and a →X. When we havel∗∗a → X, and also have either a → X or a →X, no order cancluster answers to both operations without interleaving nodes.
l∗Fig. 4(a) illustrates the conflict between a →X and a → X.
λ∗µ∗
ω∗
In this tree, 1 → X, 1 → X, 1 → X, 1 → X retrieve nodes{2, 3, 4}, {2, 5}, {3, 6}, and {4, 7}, respectively. The boxes
in Fig. 4 represent these node sets, and obviously we cannot
serialize the nodes without decomposing any of these boxes.
l∗∗
On the other hand, a →X and a →X never conflict when
they start from the same node, because the answer to theformer is the subset of the latter. When they start from different
nodes, however, they may conflict, as shown in Fig. 4(b). In
λ∗∗∗this example, 1 →X retrieves nodes 2 to 7, and 2 →X, 3 →
X,∗
4 → X retrieve {5, 8}, {6, 9}, {7, 10}, respectively. The boxes
in Fig. 4(b) represent these node sets, and obviously, there isno node ordering that agrees with all these boxes.
l∗∗Because a →X conflicts with a → X or a →X, we need tol∗∗either sacrifice a → X, or sacrifice a → X and a →X. If wel∗lsacrifice a → X, a node order <t defined on a tree t, as below,∗lis optimal for the other operations, a → X, a →X, a →X:∗ll
Optimal Ordering for a → X, a → X, a → X: <tGiven a tree t, let t0 be the tree created from t by stable sortingof siblings by the labels of their incoming edges. Then for any
nodes n1 , n2 in t, n1 <lt n2 iff n1 <t0 n2 .
2For example, given a tree in Fig. 5(a), Fig. 5(b) is the sorted
tree, and the numbers beside the nodes represent the nodeorder given by <lt . Then we have the following theorem.
Theorem 2: For any tree t and its node a, answer nodes of∗la → X, a →X or a →X have consecutive positions in <lt . 2

vi
0
λ µ λ

@
@ vi
vi
vi
3
1
2
µ
λ
λ

vi
vi
vi
6
5
4
µ λ µ λ
B i
 Bi
vi
8 v 9 v10
7 vi

1 vi
0
λ
µ
λ 3@ 4
2
@
vi
vi
vi
3
1
2
λ
µ
λ
5 
8 9
vi
vi
vi
6
5
4
µ
λ
λ µ
6 B i7
10  B 11
i vi
i
v10
v8 v7
9

(a) the original tree(b) the order by <lt

Fig. 5.

1 vi
0
λ
µ
2
λ 3@ 8
@
vi
vi
vi
3
2
1
λ
µ 7
λ

4  
vi
4
λ µ

vi
vi
6
5 9
λ µ 115  B iBvi
vi
10 v10
9
8 vi
7 6

 

 

(c) the order by <l∗tOrdering for edge-labeled treesl∗However, <lt is very inefficient for a →X, as shown below:
Theorem 3: Given a tree t and its node a, answer nodes ofl∗a→
X appear, in the worst case, in N detached positions in
the ordering <lt , where N is the number of answer nodes. 2
This is obvious because each relevant node may appear
alone in the middle of a distinct sibling group.
We also modify the storage scheme. We store nodes in
the order of <lt , and for each node, we store a pointerfirstChild (a, l) for each label l, which points to the first childreachable via l. Child pointers of each node are stored in the
dictionary order of l. Fig. 6 shows the disk image in thisscheme. In Fig 6, a pointer to a node n is represented byaddr (n) for simplicity, but in the real implementation, we use
the byte offset in this image, because each entry in this scheme
has a variable length and we cannot use addr (n) as pointers.
∗
On this data representation, a → X and a →X are processedby the same procedure as before, except that each node may
have many child pointers, and we follow the first one amonglthese. a →X can be processed by the procedure below:l
Algorithm for a →X:1) scan the node entries starting at firstChild (a, l), and2) stop the scan when we reach a node n s.t. either (1)addr (n) = firstChild (a, l0 ) where l0 is the label of thenext child pointer in a, or (2) parent(n) 6= addr (a). 2l∗
Next, we consider the second choice, i.e., choosing a →X∗
and sacrificing a → X and a → X. First, we define a coupleof concepts. We define the maximal unilabeled connected subgraphs of a tree t as the maximal connected subgraphs of t that
include only one kind of edge label. Notice that they always
form trees. Then we define unilabeled clusters as subgraphs
created from the maximal unilabeled connected subgraphs, byremoving their root nodes. (deleted) Each unilabeled cluster
forms a forest. We also regard the root node of t always
forms a unilabeled cluster including only itself. The unilabeledclusters of t then disjointly classify all the nodes in t.
Now we define a node order <l∗t on a tree t, which isll∗
optimal for a →X and a →X, as follows:ll∗Optimal Ordering for a →X, a →
X: <l∗t
Let t0 be the tree created from t by sorting siblings as in thedefinition of <lt . For any nodes n1 , n2 in t, let f1 , f2 be theunilabeled clusters including n1 , n2 , let m1 , m2 be the first
nodes in f1 , f2 in the depth-first order in t0 , and let l1 , l2 beaddr (n):λ → 2, µ → 4
1 (v0 )

1

λ→5
2 (v1 )

1µ→8
3 (v3 )

Fig. 6.

1

λ→94 (v2 )2

λ → 6, µ → 7
5 (v4 )

5
6 (v8 )

5
7 (v7 )

3
8 (v6 )

4

λ → 10, µ → 11
9 (v5 )···

Disk image in the storage scheme based on <lt

the labels of the incoming edges of n1 , n2 , respectively. Thenl∗
• if f1 = f2 , n1 <t n2 iff n1 <t0 n2 ,l∗• if f1 6= f2 , n1 <t n2 iff m1 precedes m2 in the depth0
first order in t .
2
Fig. 5(c) illustrates <l∗defined
on
the
tree
in
Fig.
5(a).
The
t
boxes in the figure represent unilabeled clusters. For example,
v1 , v3 , v4 , v8 form a unilabeled cluster with a label λ, and its
first node is v1 . We sort seven unilabeled clusters in this tree inthe depth-first order of their first nodes. Within each unilabeledcluster, nodes are sorted by <t . Thus the numbers beside thenodes represent the node order given by <l∗t . The theoremll∗is
optimal
for
a
→
X
and
a→
X.
below shows that <l∗tTheorem 4: For any tree t and its node a, the answer nodesll∗of a →X or a →X have consecutive positions in <l∗2t .
We again modify our storage scheme. We store nodes in theorder of <l∗t , and for each node n, we store its label, denotedby label (n). Although we can process all the operationsl∗without label (n), here we show simpler algorithms for a →X∗
and a → X that use it because of space limitation. First, well∗
can process a →X and a →X as follows:l
Algorithm for a → X: The same procedure as before.
2l∗Algorithm for a →X:1) scan the node entries starting at firstChild (a, l), and2) stop the scan at n s.t. either (1) parent(n) 6= a ∧parent(n) < firstChild (a, l), or (2) label (n) 6= l.
2µ∗
For example, suppose we process v4 → X in Fig. 5(c). We
start the scan at firstChild (v4 , µ), i.e., v7 , and proceed to v6 .
When we reach v6 , parent(v6 ) = 3 < firstChild (v4 , µ) = 6.
λ∗On the other hand, when we process v2 →X, we start the scan
at v5 , and when we reach v9 , label (v9 ) = µ 6= λ.
Although <l∗t is not “optimal” for the other two operations,∗a → X and a →X, <l∗
t has the following good property:
Theorem 5: For any tree t and its node a, the answers to
a → X are clustered in, at most, L regions in <l∗t , where L is
the number of distinct labels on outgoing edges of a, and the∗answers to a →X are clustered in, at most, 2 regions.
2∗
We can actually evaluate a → X and a →X by accessing
only L and 2 regions by the following procedures:
Algorithm for a → X:l
Repeat a →X for all l s.t. a has firstChild (a, l).
2∗
Algorithm for a →X:1) Let l be label (a), and let minAdd be MAXINT.
2) If a has child pointers for some l0 (6= l), let l0 be thefirst one among them in the dictionary order, and let
minAdd be firstChild (a, l0 ).
3) Scan the node entries starting at firstChild (a, l).
4) When scanning n, if firstChild (n, l0 ) < minAdd forsome l0 (6= l), let minAdd be firstChild (n, l0 ).
5) Stop the scan at a node n s.t. either (1) parent(n) 6= a ∧parent(n) < firstChild (a, l), or (2) label (n) 6= l. Let
maxL be addr (n) − 1.

6) Scan the node entries starting at minAdd.
7) Stop the scan at n s.t. parent(n) 6= a ∧ parent(n) <firstChild (a, l) or maxL < parent(n) < minAdd. 2∗
For example, in Fig. 5(c), we process v1 →X by (i) retrieving its λ-descendants (v4 , v8 ) that are stored in consecutive
positions in one cluster, and (ii) retrieving their further descendants in other clusters by scanning nodes starting at minAdd,
which is set to firstChild (v4 , µ) = v7 when we scan v4 .
In this way, in this storage scheme, the number of disk
regions we need to access for processing a → X is the numberof distinct labels of the children of a, which is usually a small∗
constant, and that for processing a →X is at most 2.
IV. C ONCLUSION
This paper studies how we should order nodes of labeledtrees on the disk for efficient processing of children/descendant
and wildcard/label-specific navigations. We showed that there
does not exist an ordering scheme which is optimal for allthese operations, and we proposed two node orders <lt andl<l∗
t . Although <t is optimal for the three operations, it isl∗quite inefficient for a →X. On the other hand, <l∗t is optimalll∗
only for a → X and a →X, but it guarantees that the nodes to∗retrieve in a → X and a →X are clustered in a small numberof disk regions. Therefore, <l∗t is preferable in most cases.
ACKNOWLEDGMENT
This research was partially supported by the Grant-in-Aid
for Scientific Research (#20700076, #21013004) from MEXT,
Japan, and Research Projects of Graduate School of Library,
Information, and Media Studies, University of Tsukuba, Japan.
R EFERENCES[1] C. Zhang, J. Naughton, D. DeWitt, Q. Luo, and G. Lohman, “Onsupporting containment queries in relational database management systems,” in SIGMOD, 2001, pp. 425–436.
[2] S. Al-Khalifa, H. V. Jagadish, J. M. Patel, Y. Wu, N. Koudas, andD. Srivastava, “Structural joins: A primitive for efficient XML query
pattern matching,” in ICDE, 2002, p. 141.
[3] T. Grust, M. van Keulen, and J. Teubner, “Staircase join: Teach a
relational DBMS to watch its (axis) steps,” in VLDB, 2003, pp. 524–525.
[4] T. Grust, J. Rittinger, and J. Teubner, “Why off-the-shelf RDBMSs are
better at XPath than you might expect,” in SIGMOD, 2007, pp. 949–958.
[5] C.-C. Kanne and G. Moerkotte, “Efficient storage of XML data,” in
ICDE, 2000, p. 198.
[6] W. Wang, H. Jiang, H. Wang, X. Lin, H. Lu, and J. Li, “Efficient
processing of XML path queries using the disk-based F&B index,” in
VLDB, 2005, pp. 145–156.
[7] N. Zhang, V. Kacholia, and M. T. Özsu, “A succinct physical storage
scheme for efficient evaluation of path queries in XML,” in ICDE, 2004,
pp. 54–65.
[8] J. Banerjee, W. Kim, S.-J. Kim, and J. F. Garza, “Clustering a DAG
for CAD databases,” IEEE Trans. Software Eng., vol. 14, no. 11, pp.
1684–1699, 1988.
[9] P. Ferragina, F. Luccio, G. Manzini, and S. Muthukrishnan, “Compressing and searching XML data via two zips,” in WWW, 2006, pp. 751–760.
[10] R. K. Wong, F. Lam, and W. M. Shui, “Querying and maintaining acompact XML storage,” in WWW, 2007, pp. 1073–1082.