IFDewey: A New Insert-Friendly Labeling Schemafor XML Data

XML has become a popular standard for information exchange via web. Each XML document can be presented as a rooted, ordered, labeled tree. The Node label shows the exact position of a node in the original document. Region and Dewey encoding are two famous methods of labeling trees. In this paper, we propose a new insert friendly labeling method named IFDewey based on recently proposed scheme, called Extended Dewey. In Extended Dewey many labels must be modified when a new node is inserted into the XML tree. Our method eliminates this problem by reserving even numbers for future insertion. Numbers generated by Extended Dewey may be even or odd. IFDewey modifies Extended Dewey so that only odd numbers are generated and even numbers can then be used for a much easier insertion of nodes.

• S. Soltan
• A. Zarnani
• R. AliMohammadzadeh
• M. Rahgozar

• XML
• tree labeling
• query processing.

[1] J. Lu, T. Wang Ling, C. Chan, T. Chen : From Region Encoding To
Extended Dewey: On Efficient Processing of XML Twig Pattern
Matching. VLDB (2005) 193-204.
[2] P. O'Neil, E. O'Neil, S. Pal, I. Cseri, G. Schaller, , N. Westbury:
ORDPATHs: Insert-Friendly XML Node Labels. SIGMOD (2004) 903-
908.
[3] S. Tatarinov, K.S. Viglas., J. Beyer, E. Shanmugasun-daram, J. Shekita,
C. Zhang, : Storing and querying ordered XML using a relational
database system. SIGMOD (2002) 204-215.
[4] N. Bruno, D. Srivastava, N. Koudas : Holistic twig joins: optimal XML
pattern matching. SIGMOD (2002) 310-321.
[5] S. Al-Khalifa, H.V. Jagadish, N. Koudas, J.M. Patel: Structural Joins: A
Primitive for Efficient XML Query Pattern Matching. ICDE (2002) 141-
152
[6] H. Jiang, W. Wang, H. Lu, J.X. Yu: Holistic Twig Joins on Indexed
XML Documents. VLDB (2003) 273-284.
[7] Q. Li, B. Moon: Indexing and querying XML data for regular path
expressions. VLDB (2001) 361-370.
[8] X. Wu, M. Lee, W. Hsu: A prime number labeling scheme for dynamic
ordered XML trees. ICDE (2004) 66-78.
[9] M. Emadi, M. Rahgozar, A. Ardalan, A. Kazerani, M.M .Arian: A
Comparative Study of DTD-Independent XML Data Storage
Approaches. 11th International CSI Computer Conference, Tehran, Iran,
CSICC (2006) 624-628.