BLAS: an efficient XPath processing system

ABSTRACT

We present BLAS, a Bi-LAbeling based System, for efficiently processing complex XPath queries over XML data. BLAS uses P-labeling to process queries involving consecutive child axes, and D-labeling to process queries involving descendant axes traversal. The XML data is stored in labeled form, and indexed to optimize descendent axis traversals. Three algorithms are presented for translating complex XPath queries to SQL expressions, and two alternate query engines are provided. Experimental results demonstrate that the BLAS system has a substantial performance improvement compared to traditional XPath processing using D-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: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 3: Stephen Alstrup , Theis Rauhe, Improved labeling scheme for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.947-953, January 06-08, 2002, San Francisco, California
• 4: From XML Schema to Relations: A Cost-Based Approach to XML Storage, Proceedings of the 18th International Conference on Data Engineering, p.64, February 26-March 01, 2002
• 5: J. Bosak. Shakespeare. http://www.ibiblio.org/xml/examples/shakespeare/.
• 6: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 7: Y. Chen, S. Davidson, C. Hara, and Y. Zheng. RRXS: Redundancy reducing XML storage in relations. In Proceedings of VLDB, 2003.
• 8: Y. Chen, S. B. Davidson, and Y. Zheng. Constraint Preserving XML Storage in Relations. In WebDB, 2002.
• 9: Shu-Yao Chien , Vassilis J. Tsotras , Carlo Zaniolo , Donghui Zhang, Efficient Complex Query Support for Multiversion XML Documents, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.161-178, March 25-27, 2002
• 10: S.-Y. Chien, Z. Vagena, D. Zhang, V. J. Tsotras, and C. Zaniolo. Efficient Structural Joins on Indexed XML Documents. In Proceedings of VLDB, 2002.
• 11: J. Clark and S. DeRose. XML Path language (XPath), November 1999. http://www.w3.org/TR/xpath.
• 12: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 13: David DeHaan , David Toman , Mariano P. Consens , M. Tamer Özsu, A comprehensive XQuery to SQL translation using dynamic interval encoding, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872832]
• 14: A. Deutsch. An Experimental Evaluation of the MARS System. In Excerpt from PhD Thesis Alin Deutsch, 2002.
• 15: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 16: Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
• 17: D. Florescu and D. Kossmann. Storing and querying XML data using an RDBMS. In Bulletin of the Technical Committee on Data Engineering, pages 27--34, September 1999.
• 18: Georgetown Protein Information Resource. Protein Sequence Database, 2001. http://www.cs.washington.edu/research/xmldatasets/.
• 19: Torsten Grust, Accelerating XPath location steps, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564705]
• 20: H. Jiang, H. Lu, W. Wang, and B. C. Ooi. XR-Tree: Indexing XML Data for Efficient Structural Joins. In Proceedings of ICDE, 2003.
• 21: Raghav Kaushik , Philip Bohannon , Jeffrey F Naughton , Henry F Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564707]
• 22: R. Kaushik, P. Shenoy, P. Bohannon, and E. Gudes. Exploiting local similarity for efficient indexing of paths in graph structured data. In Proceedings of ICDE, 2002.
• 23: 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
• 24: J. McHugh, J. Widom, S. Abiteboul, Q. Luo, and A. Rajaraman. Indexing semistructured data. Technical report, Stanford University, 1998.
• 25: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 26: Jun-Ki Min , Myung-Jae Park , Chin-Wan Chung, XPRESS: a queriable compression for XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872775]
• 27: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 28: J. Simon and M. Fernndez. Galax. http://db.bell-labs.com/galax.
• 29: W. Wang, H. Jiang, H. Lu, and J. X. Yu. PBiTree Coding and Efficient Processing of Containment Joins. In Proceedings of ICDE, 2003.
• 30: XMARK the XML-benchmark project, April 2001. http://monetdb.cwi.nl/xml/index.html.
• 31: 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