A String Approach for Dynamic XML Document

Abstract:

Labeling the nodes of an XML document allows queries without accessing the original file. For dynamic XML documents, the labeling scheme should support both efficient queries and insertion updates. This paper proposed a new labeling scheme, DCPL (Dynamic Common Prefix Labeling), to process dynamic XML documents efficiently. Compared with the existing schemes, DCPL presents a prominent feature of maintaining its simplicity and efficiency in dynamic and static documents. Meanwhile, it can efficiently support labeling updates, especially frequent updates, without sacrifices of query performance. The conducted experiments have shown that our proposal works better than the previous ones.

• Periodical: Applied Mechanics and Materials (Volumes 220-223)
• Pages: 2512-2519
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.220-223.2512
• Online since: November 2012
• Authors: Zun Yue Qin, Yong Tang, Hong Zhi Xu
• Keywords: Common String Labeling Scheme, Dynamic XML Data, Update

References

[1] R. Agrawal, A. Borgida, and H.V. Jadadish, "Efficient Management of Transitive Relationships in Large Data and Knowledge Bases," Proc. ACM SIGMOD, pp.253-262, 1989.

DOI: 10.1145/66926.66950

[2] Q. Li and B. Moon, "Indexing and Querying XML Data for Regular Path Expressions," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp.361-370,2001.

[3] C. Zhang, J.F. Naughton, D.J. DeWitt, Q. Luo, and G.M. Lohman, "On Supporting Containment Queries in Relational Database ManagementSystems," Proc. ACM SIGMOD, pp.425-436, 2001.

DOI: 10.1145/376284.375722

[4] S. Abiteboul, H. Kaplan, and T. Milo, "Compact Labeling Schemes for Ancestor Queries," Proc. Symp. Discrete Algorithms (SODA), pp.547-556, 2001.

[5] E. Cohen, H. Kaplan, and T. Milo, "Labeling Dynamic XML Trees," Proc. Symp. Principles of Database Systems (PODS), pp.271-281, 2002.

DOI: 10.1145/543613.543648

[6] J. McHugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom, "Lore: A Database Management System for Semistructured Data," SIGMOD Record, vol. 2, no. 3, pp.54-66, 1997.

DOI: 10.1145/262762.262770

[7] Silberstein et al., "Boxes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data," Proc. Int'l Conf. Data Eng. (ICDE), pp.285-296, 2005.

DOI: 10.1109/icde.2005.29

[8] Li, T.W. Ling, and M. Hu, "Efficient Processing of Updates in Dynamic XML Data," Proc. Int'l Conf. Data Eng. (ICDE), pp.13-22, 2006.

DOI: 10.1109/icde.2006.58

[9] Li and T.W. Ling, "QED: A Novel Quaternary Encoding to CompletelyAvoid Re-Labeling in XML Updates," Proc. Int'l Conf. Information and Knowledge Management (CIKM), pp.501-508, 2005.

DOI: 10.1145/1099554.1099692

[10] Ko H, Lee S.IEEE Transactions on Knowledge and Data Engineering, 22(4): 602-608,(2010)

[11] L Xu, T-W Ling, H Wu, Z Bao. DDE: From Dewey to a Fully Dynamic XML Labeling Scheme. Proc. of the 35th SIGMOD international conference on Management of data, pp:719–730, (2009)

DOI: 10.1145/1559845.1559921

[12] P. O'Neil, E. O'Neil, S. Pal, I. Cseri, and G. Schaller, "ORDPATHs: Insert-Friendly XML Node Labels," Proc. ACM SIGMOD, pp.903-908, 2004.

DOI: 10.1145/1007568.1007686

[13] Tatarinov S, Viglas D, Beyer K J et al. Storing and Querying Ordered XML Using a Relational Database System. Proc of the ACM SIGMOD 2002 .Los Alamitos,CA:IEEE Computer Society,pp: 204-215, (2002)

DOI: 10.1145/564691.564715

[14] Li C, Ling T W, Hu M. Efficient Processing of Updates in Dynamic XML Data. Proc of the 22nd Int Conf Data Engineering (ICDE'06). Los Alamitos,CA:IEEE Computer Society,pp:13-22, (2006)

DOI: 10.1109/icde.2006.58