DDE: from dewey to a fully dynamic XML labeling scheme

ABSTRACT

Labeling schemes lie at the core of query processing for many XML database management systems. Designing labeling schemes for dynamic XML documents is an important problem that has received a lot of research attention. Existing dynamic labeling schemes, however, often sacrifice query performance and introduce additional labeling cost to facilitate arbitrary updates even when the documents actually seldom get updated. Since the line between static and dynamic XML documents is often blurred in practice, we believe it is important to design a labeling scheme that is compact and efficient regardless of whether the documents are frequently updated or not. In this paper, we propose a novel labeling scheme called DDE (for Dynamic DEwey) which is tailored for both static and dynamic XML documents. For static documents, the labels of DDE are the same as those of dewey which yield compact size and high query performance. When updates take place, DDE can completely avoid re-labeling and its label quality is most resilient to the number and order of insertions compared to the existing approaches. In addition, we introduce Compact DDE (CDDE) which is designed to optimize the performance of DDE for insertions. Both DDE and CDDE can be incorporated into existing systems and applications that are based on dewey labeling scheme with minimum efforts. Experiment results demonstrate the benefits of our proposed labeling schemes over the previous approaches.

REFERENCES

• 1: University of Washington XML Repository. http://www.cs.washington.edu/research/xmldatasets/.
• 2: XMark - An XML Benchmark Project. http://monetdb.cwi.nl/xml/downloads.html.
• 3: Serge Abiteboul , Stephen Alstrup , Haim Kaplan , Tova Milo , Theis Rauhe, Compact Labeling Scheme for Ancestor Queries, SIAM Journal on Computing, v.35 n.6, p.1295-1309, 2006 [doi>10.1137/S0097539703437211]
• 4: T. Amagasa, M. Yoshikawa, and S. Uemura. QRS: A Robust Numbering Scheme for XML Documents. ICDE, 2003.
• 5: T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau. Extensible Markup Language (XML) 1.0: fourth edition W3C recommendation, 2006.
• 6: 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]
• 7: Changqing Li , Tok Wang Ling, QED: a novel quaternary encoding to completely avoid re-labeling in XML updates, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099692]
• 8: Changqing Li , Tok Wang Ling , Min Hu, Efficient Processing of Updates in Dynamic XML Data, Proceedings of the 22nd International Conference on Data Engineering, p.13, April 03-07, 2006 [doi>10.1109/ICDE.2006.58]
• 9: Changqing Li , Tok Wang Ling , Min Hu, Efficient updates in dynamic XML data: from binary string to quaternary string, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.573-601, May 2008 [doi>10.1007/s00778-006-0021-2]
• 10: 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
• 11: 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]
• 12: Chong Sun , Chee-Yong Chan , Amit K. Goenka, Multiway SLCA-based keyword search in XML data, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242713]
• 13: 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]
• 14: 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
• 15: Liang Xu , Zhifeng Bao , Tok Wang Ling, A Dynamic Labeling Scheme Using Vectors, Proceedings of the 18th international conference on Database and Expert Systems Applications, September 03-07, 2007, Regensburg, Germany [doi>10.1007/978-3-540-74469-6_14]
• 16: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]
• 17: 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:
dewey, dynamic xml, labeling scheme, update