Journal of Software, Vol 6, No 10 (2011), 2043-2049, Oct 2011
doi:10.4304/jsw.6.10.2043-2049

An Encoding and Labeling Scheme Based on Continued Fraction for Dynamic XML

Yi Jiang, Xiangjian He, Fan Lin, Wenjing Jia

Abstract


Much research about labeling schemes has been conducted to efficiently determine the ancestor-descendant relationships and the document-order between any two random XML nodes without re-labeling for updates. In this paper, we present an efficient XML encoding and labeling scheme for dynamic XML document, named as {\it Continued Fraction-based Encoding (CFE)}. The proposed CFE scheme labels nodes with continued fractions and has the following three important properties: (1) CFE codes can be inserted between any two consecutive CFE codes with the orders kept and without re-encoding the existing nodes; (2) CFE is orthogonal to specific labeling schemes, thus it can be applied broadly to different labeling schemes or other applications to efficiently process the updates; (3) CFE supports all structural relationships query in XPath. Two test data sets were built for evaluation. The experimental results show that CFE provides fairly reasonable XML query processing performance while completely avoiding re-labeling for updates.


Keywords


continued fraction; labeling scheme; dynamic XML data

References


[1] A. Berglund, S. Boag, and D. Chamberlin, “Xml path language (xpath) 2.0,” W3C working draft, 2002.

[2] S. Abiteboul, D. Quass, J. McHugh, J. Widom, J.L. Wiener. “The Lorel query language for semistructured data”[J]. International Journal on Digital Libraries, Volume 1,Number1,pp.68–88.

[3] A. Deutsch, M. Fernadez, D. Florescu, A. Levy, and D. Suciu. “A Query Language for XML”[C]. In Proceedings of the 8th International World Wide Web Conference. Toronto,Canada,1999,pp.77-91.

[4] J. Robie, J. Lapp, D. Schach. “XML Query Language(XQL)”[C]. In Proceedings of the W3C Query Languages Workshop (QL'98), Boston, Massachusets, USA, 1998, pp.3-4.

[5] P. Fankhauser, M. Fernandez, and A. Malhotra, “Xquery 1.0 formal semantics,” W3C Working Draft, 2002.

[6] D. Chamberlin, J. Robie, D. Florescu. Quilt: “An XML Query Language for Heterogeneous Data Sources”[C]. In Proceeings of Web DB 2000, Dallas,texas,2000,pp.53-62.

[7] D. Chamberlin. Xquery: “ A Query Language for XML”[C]. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego, California,2003,pp.682-682.
http://dx.doi.org/10.1145/872757.872877

[8] F. Paul and Dietz, “Maintaining order in a linked list,” in Proceedings of the 14th Annual ACM Symposium on Theory of Computing. San Francisco: ACM Press, 1982, pp. 122–127.

[9] Q. Li and B. Moon, “Indexing and querying xml data for regular path expressions,” in The 27th International Conference on VLDB. Roma: Morgan Kaufmann Publishers, 2001, pp. 361–370.

[10] C. Zhang, J. Naughton, and D. DeWitt, “On supporting containment queries in relational database management systems,” in Proc. of the 2001 ACM SIGMOD international COMAD. Santa Barbara:ACM Press, 2001, pp. 425–436.

[11] C. X. Wan and Y. S. Liu, “Restore: Middleware for xml’s relational storage and retrieve,” Wuhan University Journal of Natural Science, vol. 8, no. 1A, pp. 28–34, 2003.

[12] C.W. Chung, J.K. Min, K. Shim, K. Seoul. “APEX: An adaptive path index for XML data”[C]. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data, Madison, Wisconsin, 2002, pp.121-132.

[13] R. Kaushik, P. Shenoy, P. Bohannon, E. Gudes. “Exploiting local similarity for indexing paths in graph-structured data”[C]. In Proceedings of the 18th International Conference on Data Engineering, San Jose, USA, 2002, pp.129-140.
http://dx.doi.org/10.1109/ICDE.2002.994703

[14] H. Wang, S. Park, W. Fan, P.S. Yu. “ViST: a dynamic index method for querying XML data by tree structures”[C]. ACM SIGMOD 2003, Madison, USA, 2003, pp.110-121.

[15] P. Rao, B. Moon.” PRIX: Indexing and querying XML using prufer sequences”[C]. ICDE 2004, Boston, USA, 2004, pp.288-299.

[16] S. Tatarinov, K. S. Viglas, and Beyer, “Storing and querying ordered xml using a relational database system.” In Proc. of the 2002 ACM SIGMOD int’l COMAD. Madison: ACM Press, 2002, pp. 204–215.

[17] E. Cohen, H. Kaplan, and T. Milo, “Labeling dynamic xml trees. in spds,” in SPDS. Madison: ACM Press, 2002, pp.271–281.

[18] H. Wang, X. Meng. “On the sequencing of tree structures for XML indexing”[C]. ICDE 2005,Tokyo, Japan,2005, pp.372-383.

[19] S. A.l.-Khalifa, H.V Jagadish, N Koudas, “Structural joins: A primitive for efficient XML query pattern matching”[C]. ICDE 2002,San Jose, USA, 2002, pp.141-152.

[20] H. Jiang, W. Wang, H. Lu, J.X. Yu. “Holistic twig joins on indexed XML documents”[C]. VLDB 2003, Berlin, Germany,2003, pp.273-284.

[21] Q. Li, B. Moon. “Indexing and querying XML data for regular path expressions”[C]. VLDB 2001, Rome, Italy,2001, pp.361-370.

[22] X. Wu, M. L. Lee, and W. Hsu, “A prime number labeling scheme for dynamic ordered xml trees,” in Proceedings of 19th Int’l Conference on Data Engineering. Boston: IEEE Computer Society, 2004, pp. 66–78.

[23] T. Amagasa, M. Yoshikawa, and S. Uemura, “Qrs: A robust numbering scheme for xml documents,” in Proc. of 19th Int’l Conference on Data Engineering. Bangalore: IEEE Computer Society, 2003, pp. 705–707.

[24] P. O’Neil, E. O’Neil, and S. Pal, I. Cseri, G. Schaller,N. Westbury, “Ordpaths: Insert-friendly xml node labels,” in Proc. of the 2004 ACM SIGMOD Int’l COMAD. Paris: ACM Press, 2004, pp. 903–908.

[25] C. Li and T. W. Ling, “Qed: a novel quaternary encoding to completely avoid re-labeling in xml updates,” in Proc. of the 14th ACM Int’l CIKM. Bremen: ACM Press, 2005, pp. 501–508.

[26] H. Xiao, C. Tang, and T. Zhang, “Btcs: The binary traveling coding scheme for xml document,” Journal of Sichuan University of Natural Science, vol. 43, no. 3, pp.532–536, 2006.

[27] L. Xu, Z. Bao, and T. Wang, “A dynamic labeling scheme using vectors,” in Proc. of 18th Int’l Conference on DEXA. Regensburg: Springer-Verlag, 2007, pp. 130–140.

[28] R. Thonangi, “A concise labeling scheme for xml data,” in Proc. of Int’l COMAD. Delhi, India: Computer Society of India, 2006.

[29] J.-K. Min, J. Lee, and C.-W. Chung, “An efficient encoding and labeling for dynamic xml data,” in Proc. of 12th Int’l Conference on DASFAA. Bangkok, Thailand: Springer- Verlag, 2007, pp. 715–726.

[30] M. H. Changqing Li, Tok Wang Ling, “Efficient processing of updates in dynamic xml data,” in Proceedings of 22nd International Conference on Data Engineering. Atlanta, Georgia: IEEE Computer Society, 2006, pp. 13–23.

[31] Y. Lu, L. Zhang, and W. Wang, “A new xml document coding scheme,” Journal of Computer Research and Development, vol. 41, no. 3,2004, pp. 500–503.

[32] H. Jiang, H. Lu, W. Wang,”XR-Tree:Indexing XML data for efficient structural joins” [C]. ICDE 2003,San Jose,USA,2003.pp.78-82.

[33] N. Bruno, N. Koudas, D. Srivastava. “Holistic twig joins: optimal XML pattern matching” [C]. ACM SIGMOD 2002, Madison, USA,2002,pp.310-321.

[34] T. Chen, J. Lu, T.W. Ling. “On boosting holism in XML twig pattern matching using structural indexing techniques”[C]. ACM SIGMOD 2005, Baltimore, Maryland, 2005, pp.455-466.

[35] J. Lu, T.W. Ling, C.Y. Chan, T. Chen. “From region encoding to extended dewey: On efficient processing of XML twig pattern matching”[C]. VLDB 2005, Trondheim, Norway, pp.193-204.

[36] T. Chen, T. W. Ling, C-Y. Chan.” Prefix Path Streaming: A New Clustering Method for Optimal Holistic XML Twig Pattern Matching” [C]. DEXA 2004,Zaragoza, Spain,2004,pp.801-810.

[37] J. Lu, T. Chen, T.W. Ling. “Efficient processing of XML twig patterns with parent child edges: a look-ahead approach”[C]. CIKM 2004, Washington,USA,2004,pp.533-542.

[38] “The niagara project experimental data,” http://www.cs.wisc.edu/niagara/data.html.


Full Text: PDF


Journal of Software (JSW, ISSN 1796-217X)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.