IFDewey: A New Insert-Friendly Labeling Schemafor XML Data

Authors: S. Soltan, A. Zarnani, R. AliMohammadzadeh, M. Rahgozar

Abstract:

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.

Keywords: XML, tree labeling, query processing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056230

References:

[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.