QED: a novel quaternary encoding to completely avoid re-labeling in XML updates

ABSTRACT

The method of assigning labels to the nodes of the XML tree is called a labeling scheme. Based on the labels only, both ordered and un-ordered queries can be processed without accessing the original XML file. One more important point for the labeling scheme is the label update cost in inserting or deleting a node into or from the XML tree. All the current labeling schemes have high update cost, therefore in this paper we propose a novel quaternary encoding approach for the labeling schemes. Based on this encoding approach, we need not re-label any existing nodes when the update is performed. Extensive experimental results on the XML datasets illustrate that our QED works much better than the existing labeling schemes on the label updates when considering either the number of nodes or the time for re-labeling.

REFERENCES

• 1: Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
• 2: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 3: T. Amagasa, M. Yoshikawa, and S. Uemura. QRS: A Robust Numbering Scheme for XML Documents. In Proc. of ICDE, pages 705--707, 2003.
• 4: J.A. Anderson and J.M. Bell. Number Theory with Application. Prentice-Hall, New Jersey, 1997.
• 5: A. Berglund, S. Boag, D. Chamberlin, M. F. Fernandez, M. Kay, J. Robie, and J. Simon. XML path language (XPath) 2.0. W3C working draft 04, Apr 2005.
• 6: S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, and J. Simon. XQuery 1.0: An XML Query Language. W3C working draft 04, Apr 2005.
• 7: T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau. Extensible markup language (XML) 1.0 third edition W3C recommendation. Oct. 2000.
• 8: Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543648]
• 9: Maggie Duong , Yanchun Zhang, LSDX: a new labelling scheme for dynamically updating XML data, Proceedings of the sixteenth Australasian database conference, p.185-193, January 01, 2005, Newcastle, Australia
• 10: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 11: C. Li and T.W. Ling. An Improved Prefix Labeling Scheme: A Binary String Approach for Dynamic Ordered XML. In Proc. of DASFAA, pages 125--137, 2005.
• 12: Changqing Li , Tok Wang Ling , Jiaheng Lu , Tian Yu, On reducing redundancy and improving efficiency of XML labeling schemes, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099599]
• 13: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 14: Jason McHugh , Serge Abiteboul , Roy Goldman , Dallas Quass , Jennifer Widom, Lore: a database management system for semistructured data, ACM SIGMOD Record, v.26 n.3, p.54-66, Sept. 1997 [doi>10.1145/262762.262770]
• 15: Svetlozar Nestorov , Jeffrey D. Ullman , Janet L. Wiener , Sudarshan S. Chawathe, Representative Objects: Concise Representations of Semistructured, Hierarchial Data, Proceedings of the Thirteenth International Conference on Data Engineering, p.79-90, April 07-11, 1997
• 16: NIAGARA Experimental Data. Available at: http://www.cs.wisc.edu/niagara/data.html
• 17: Patrick O'Neil , Elizabeth O'Neil , Shankar Pal , Istvan Cseri , Gideon Schaller , Nigel Westbury, ORDPATHs: insert-friendly XML node labels, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007686]
• 18: Adam Silberstein , Hao He , Ke Yi , Jun Yang, BOXes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.285-296, April 05-08, 2005 [doi>10.1109/ICDE.2005.29]
• 19: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 20: University of Washington XML Repository. Available at: http://www.cs.washington.edu/research/xmldatasets/
• 21: Xiaodong Wu , Mong Li Lee , Wynne Hsu, A Prime Number Labeling Scheme for Dynamic Ordered XML Trees, Proceedings of the 20th International Conference on Data Engineering, p.66, March 30-April 02, 2004
• 22: XMark -- An XML Benchmark Project. Available at: http://monetdb.cwi.nl/xml/downloads.html
• 23: F. Yergeau. UTF8: A Transformation Format of ISO 10646. Request for Comments (RFC) 2279, January 1998.
• 24: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
dynamic XML, labeling scheme, quaternary, update