論文 / 著書情報
Article / Book Information
Title

Storage Consumption of Variable-length XML LabelsUninfluenced byInsertions

AuthorAkihiro Takahashi, Wenxin Liang, Haruo Yokota

Journal/Book name

Proceedings of the Second IEEE International Conference on Digital
Information Management, , , pp. 571-573

Issue date2007, 10DOI

http://dx.doi.org/10.1109/ICDIM.2007.4444284

URL

http://www.ieee.org/index.html

Copyright(c)2007 IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other users, including
reprinting/republishing this material for advertising or promotionalpurposes, creating new collective works for resale or redistribution toservers or lists, or reuse of any copyrighted components of this work inother works.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

Storage Consumption of Variable-length XML Labels
Uninfluenced by Insertions
Akihiro Takahashi

Wenxin Liang

Haruo Yokota

Tokyo Institute of Technology
akihiro@de.cs.titech.ac.jp

Japan Science and Technology Agency
Tokyo Institute of Technology
wxliang@de.cs.titech.ac.jp

Tokyo Institute of Technology
yokota@cs.titech.ac.jp

Abstract
In recent years, the method of assigning labels to thenodes of an XML tree is getting more attraction. Various
functions in an RDBMS can be easily utilized by storing thelabeled XML documents into the RDB. However, in traditional labeling methods, a number of nodes need to be relabeled, when the XML documents are updated. To address
this problem, we proposed DO-VLEI code combining VLEI
code with the Dewey Order method. DO-VLEI code is effective to reduce the update cost, but the label size increases
rapidly when handling large XML documents. To reduce thelabel size, we presented Compressed-bit-string DO-VLEI(C-DO-VLEI) code. However, it is difficult to handle thelength of C-DO-VLEI because it is a variable-length code.
In this paper, we propose two effective methods, VLEI-ABLand VLEI-EOL for handling the code length of C-DO-VLEI.
We perform experiments to compare the storage consumption of the proposed methods with the previously known ORDPATH. The experimental results show that our methods
considerably outperform the ORDPATH.

1 Introduction
Relational Database systems (RDBs) are now widelyused for storing XML data, so that their management functions can be used for retrieval, updating, transactions, storage, etc. An XML document can be considered as a tree
structure by treating each element between a start tag andend tag as a node [3], because the XML document forms anested construction of elements enclosed by these tags.
The method of assigning labels to the nodes of an XML
tree is called a labeling scheme. The labeling scheme makes
it possible to determine the containment relationships between nodes and the positions of the nodes in the XML tree.
A number of labeling schemes based on the Dewey Order (DO) numbering method [9] have been proposed. TheDO numbering method uses a delimiter to extend the label of a parent node and includes the code that represents
the child’s sibling order. However, the naive DO labelingscheme, which uses numerical values for the codes, has theproblem of expensive update cost. When a new node is inserted into an intermediate position of the XML tree, a number of nodes need to be re-labeled.

To address this problem, we proposed Variable-LengthEndless-Insertable code (VLEI code) and DO-VLEI labeling method [6] combining the VLEI code with the DO numbering method. It uses the VLEI code [6] for representing
the sibling orders, which enables unlimited insertion of newnodes without relabeling any nodes.
DO-VLEI code is effective to reduce the update cost.
However, the label size increases rapidly when handlinglarge XML documents. To reduce the label size, we
presented Compressed-bit-string DO-VLEI (C-DO-VLEI)
code which represents the label by using variable-length bitstrings instead of using character strings in DO-VLEI code.
However, it is difficult to handle the length of the code.
In this paper, we propose two effective methods, VLEIABL and VLEI-EOL for handling the code length of CDO-VLEI. We perform experiments to compare the storage
consumption of the proposed methods with the previously
known ORDPATH. The experimental results show that ourmethods considerably outperform the ORDPATH.
The rest of the paper is organized as follows. In Section 2, we introduce DO-VLEI and C-DO-VLEI labelingmethods. Section 3 describes the ORDPATH. In Section 4,
we describe the properties of C-DO-VLEI code. Section
5 discusses two methods for handling the variable-length
code. In Section 6, we show the experimental evaluation ofthe storage consumptions comparing the proposed methods
with the ORDPATH. Section 7 summarizes the paper anddiscusses future directions.

2 DO-VLEI
We first explain the VLEI code and the DO-VLEI code.

2.1

Definition of the DO-VLEI CodeDefinition 1 (VLEI code) Assume v is a bitstring comprising bits from {0,1} whose initial bit is 1. v is a VLEI code,
if it satisfies the following order:v · 0 · {0|1}∗ < v < v · 1 · {0|1}∗
A new VLEI code between two arbitrary adjacent VLEI
codes can be unrestrictedly generated [6][5].
In DO numbering method, the label for a child node isexpressed by adding a delimiter and a sibling code that represents the sibling order. In the DO-VLEI labeling method,
the sibling code is expressed by the VLEI code.

Definition 2 (DO-VLEI)
1. The DO-VLEI label of a root node is assumed to be 1.
2. A sibling code Cchild is a VLEI code in which the order between sibling nodes is expressed by the VLEIcode. If the label of a parent node is Lparent , the DOVLEI label of the child node comprises a delimiter “.”,Lparent , and Cchild as follows.
DO-VLEI = Lparent . Cchild

2.2

Compressed-bit-string DO-VLEI

DO-VLEI code is composed by character strings. Thus,
when it handles large XML documents, the size of DOVLEI code may increase exponentially. Therefore, an effective method for reducing the label size becomes critical.
In [7], we have proposed the Compressed- bit-string DOVLEI (C-DO-VLEI) labeling method, in which it expresses
both the DO-VLEI codes and the delimiters by bitstrings.
The Compressed-bit-string DO-VLEI(C-DO-VLEI) isdefined as follows:
Definition 3 (Compressed-bit-string DO-VLEI)Corresponding to DO-VLEI, “.1” is expressed as thebit string (11), the element “1” is expressed by bitstring(10) and the element “0” is expressed by the bitstring(0). This bitstring expression of DO-VLEI is called
Compressed-bit-string DO-VLEI (C-DO-VLEI).

3 Related Work
Similar to the DO-VLEI code method, some labelingmethods that can update the XML document without relabeling have been proposed[8][4][12]. In the following
subsection, we briefly introduce ORDPATH which is thecomparison object in our experiments.

3.1

ORDPATHThe ORDPATH label of a child node is made from a sibling code, a delimiter, and the label of the parent node basedon the DO numbering method.
In ORDPATH, only positive odd numbers are used forthe initial labeling, because negative integers and even numbers are used for insertion operations. Besides, the end ofa sibling code, which decides the sibling order, must be anodd number. For example, when a node is newly inserted
between nodes“1.3.1” and “1.3.3”, the label of the new node
can be “1.3.2.1” , where the sibling code is “2.1”.

Table 1. Algorithm: CompareDO-VLEI

Algorithm CompareDO-VLEI(v, w)!! Input!!!!!! v, w :C-DO-VLEI code to which are to be compared!!!!!!!! (where length(v)≤length(w))!! Output!!!!!! v is greater than wl = length(w) − length(v)v  = v · 1 · {0}l −1
if v ≥ w
return true
else
return false
endifthe string. Li is a bitstring specifying the number of bitsof Oi . Li is specified by analysis of the tree using a prefix
schema. Oi is treated as a binary number within a range set
by Li .

4 Properties of C-DO-VLEI
The C-DO-VLEI code keeps the property of DO, because we convert each element of DO-VLEI code into bitstrings.
Let “0” = v0 !$“.1” = vd !$“1” = v1 . If
1 · v0 ≺v 1 ≺v 1 · vd ≺v 1 · v1
(1)
then, the ascending order by using the comparison algorithm shown in Table 1 equals to the XML document order1 .

5 Handling Code Length
It is difficult to extract the C-DO-VLEI label from bitstring because the length of labels is variable. In order toderive the length of each label, we propose two methods.
The one provides the length of each code at the head ofthe bitstring, which is called VLEI-ABL. The other adds aterminal symbol (EOL) to the end of each code, which iscalled VLEI-EOL.

5.1

VLEI-ABLAt first we generate the C-DO-VLEI code. After that
we figure out the length of it, and add a part specifying
the length at the head of it. We call that code VLEI-Add
Bit Length (VLEI-ABL). In the VLEI-ABL, we use thevariable-bitstring component L/O just as C-ORDPATH. The
prefix schema of Table 2 is used for our experiments.

3.1.1 Compressed-bit-string ORDPATH

5.2

VLEI-EOLORDPATH is implemented by bitstring expressions using“0” and “1”. In this paper, the binary representation of ORDPATH is called the Compressed-bit-string ORDPATH (CORDPATH). An integer in ORDPATH is translated into abitstring by using a prefix schema. A pair of bitstrings Liand Oi are used to express an integer. A label is a string ofdelimited integers, and i is the order of the integer within

The length of a variable-length code can be also handled
by adding a terminal symbol, EOL (End of Label) to theend of the label. In this case, the elements representing theDO-VLEI code becomes: “.1”,“1”, “0” and “EOL”. Next,
we discuss how to convert the four elements into bitstrings.
1 See [11] for the prove.Table 4. Average ratio of each method

Table 2. Prefix Schema for Length

L Bitstring
0100
101
1100
1101
11100
11101
11110
11111

O length
34
68
12
16
20
2431

vlei-ABL
0.7638O value range[1, 7][8, 23][24, 87][88, 343][344, 4439][4440, 69975][69976, 1118551][1118552, 17895767][17895768, 2165379414]

vlei-ABL01011

vlei100
111001

vlei2
010
110
111

vlei30110
10111

vlei4011101111

vlei500
1010101

vlei600
1010110

At first we present the Huffman-coding based method.
“EOL” has the lowest occurrence frequency because it appears only once in each label. “.1” occurs (depth)− 1 times
in each label, because it is the only element that represents
the delimiter. “0” and “1” occur at least once in each sibling
number.
“0” > “1” <> “.1” > “EOL”(2)
Inequality (2) shows the occurrence frequency of eachelement when the frequency of “0” is greater than “1”. According to Inequality (2), the vlei 1–3 show in Table 3 canbe generated based on the Huffman-coding.
On the other hand, since the occurrence frequency of“EOL” is apparently smaller than that of other symbols, wecan define specific sign patterns as “EOL”. The patterns of“EOL” used in vlei 4-6 are shown in Table 3. Since the“EOL” has the lowest occurrence frequency, the code lengthof vlei 4-6 can be decreased.
When XML documents are labeled by vlei1,3,4 , we canuse the comparison algorithm of Table 1.

6 Experiment
We assign the labels to the nodes of XML documents byVLEI-ABL, VLEI-EOL and C-ORDPATH to compare theirstorage consumptions. Because the C-ORDPATH is alsovariable-length codes, we add the bit length information tothe C-ORDPATH. We use 23 XML documents in the experiments that are taken from XML Data Repository [1] andgenerated from XMLGEN [2], which is a XML document
generator for XMark[10].

6.1

Experimental Results

The total label size of each method in the initial state ismeasured. Table 4 shows the average ratio of the label sizeof the VLEI-ABL and VLEI-EOL comparing with that ofthe C-ORDPATH2 .
As we can see from Table 4, the label size using vlei4–6
and vlei-ABL is about 30% and 24% smaller than that using
the C-ORDPATH. Therefore, we consider that the proposed
C-DO-VLEI methods consume much lower storage spacethan the C-ORDPATH.
2 Here the label size of C-ORDPATH is set to 1

viel2
0.7289vlei30.7505vlei40.7015vlei50.6979

vlei6
0.6911

7 Conclusions and Future Work

Table 3. Summary of VLEI-ABL and VLEI-EOL01.1
EOL

vlei10.8221

In this paper we have proposed two effective methods,
VLEI-ABL, VLEI-EOL for handling the length of C-DOVLEI code.
We have compared the storage consumption of the proposed methods with that of the C-ORDPATH. The experimental results show that our methods consume less storage
space than the C-ORDPATH.
In future, it is necessary to do further experiments toevaluate the performance of the C-DO-VLEI code.

Acknowledgments
This work is partially supported by MEXT of theJapanese Government via Grant-in-Aid for Scientific Research #19024028, the JST of CREST and the TokyoTech
21st Century COE Program.

References[1] XML Data Repository.
http://www.cs.
washington.edu/research/xmldatasets/.
[2] xmlgen. http://monetdb.cwi.nl/xml/downloads.html.
[3] T. Eda, Y. Amagasa, M. Yoshikawa, and S. Uemura. A
robust node-labeling scheme fro xml trees. In DBSJ Letters,No.1 in Vol.1,2002, 2002.
[4] M. P. Haustein, T. Härder, C. Mathis, and M. Wagner.
Deweyids - The Key to Fine-Grained Management of XML
Documents. In SBBD, pages 85–99, 2005.
[5] K. Kobayashi, W. Liang, D. Kobayashi, A. Watanabe, andH. Yokota. Update conscious xml labeling methods using
dedicated codes. Technical Report TR04-0006, Dept. ofComp. Sci., Tokyo Institute of Technology, 2004.
[6] K. Kobayashi, W. Liang, D. Kobayashi, A. Watanabe, andH. Yokota. VLEI code: An Efficient Labeling Method for
Handling XML Documents in an RDB. In ICDE, 2005.
[7] S. Murakami, D. Kobayashi, and H. Yokota. The label sizeand query performance of xml storage using the do-vlei. InProc. of DEWS2006., 2006.
[8] P. O’Neil, E. O’Neil, S. Pal, I. Cseri, G. Schaller, andN. Westbury. ORDPATHs: Insert-friendly XML Node Labels. In Proc. of the ACM SIGMOD International Conference on Management of Data 2004, pages 903–908. ACM
Press New York, NY, USA, 2004.
[9] Online Computer Library Center. Introduction to theDewey Decimal Classification. http://www.oclc.
org/oclc/fp/about/about the ddc.htm.
[10] A. Schmidt, F. Waas, M. Kersten, and D. Florescu. The
XML Benchmark Project. Technical report, TechnicalReport INS-R0103, http://monetdb.cwi.nl/xml/index.html, April 2001.
[11] A. Takahashi, W. Liang, and H. Yokota. Storage Consumption of Variable Length XML Labels Uninfluenced by Insertions. Technical report, IEICE Technical Report vol.107,No.131, DE2007-38, pp.97-102, 2007.
[12] W. H. Xiaodong Wu and, Mong Li Lee and. A Prime Number Labeling Schema for Dynamic Ordered XML Trees. InICDE, pages 66–78, 2004.