Pattern based processing of XPath queries

ABSTRACT

As the popularity of areas including document storage and distributed systems continues to grow, the demand for high performance XML databases is increasingly evident. This has led to a number of research efforts aimed at exploiting the maturity of relational database systems in order to increase XML query performance. In our approach, we use an index structure based on a metamodel for XML databases combined with relational database technology to facilitate fast access to XML document elements. The query process involves transforming XPath expressions to SQL which can be executed over our optimised query engine. As there are many different types of XPath queries, varying processing logic may be applied to boost performance not only to individual XPath axes, but across multiple axes simultaneously. This paper describes a pattern based approach to XPath query processing, which permits the execution of a group of XPath location steps in parallel.

REFERENCES

• 1: Attila Barta , Mariano P. Consens , Alberto O. Mendelzon, Benefits of path summaries in an XML query optimizer supporting multiple access methods, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: Boulos J. and Karakashian S. A New Design for a Native XML Storage and Indexing Manager. In Proceedings of EDBT 2006, LNCS vol. 3896, Springer, pp. 755--772, 2006.
• 3: Andrey Balmin , Fatma Özcan , Kevin S. Beyer , Roberta J. Cochrane , Hamid Pirahesh, A framework for using materialized XPath views in XML query processing, Proceedings of the Thirtieth international conference on Very large data bases, p.60-71, August 31-September 03, 2004, Toronto, Canada
• 4: DBLP Computer Science Bibliography (online). www.sigmod.org/dblp/db/index.html, 2008.
• 5: XMark - An XML Benchmark Project (online). www.xml-benchmark.org/, 2008.
• 6: Rajasekar Krishnamurthy , Raghav Kaushik , Jeffrey F. Naughton, Efficient XML-to-SQL query translation: where to add the intelligence?, Proceedings of the Thirtieth international conference on Very large data bases, p.144-155, August 31-September 03, 2004, Toronto, Canada
• 7: 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
• 8: Exploiting Local Similarity for Indexing Paths in Graph-Structured Data, Proceedings of the 18th International Conference on Data Engineering, p.129, February 26-March 01, 2002
• 9: Wolfgang Meier, eXist: An Open Source Native XML Database, Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Systems, p.169-183, October 07-10, 2002
• 10: Sedna - Native XML Database. http://modis.ispras.ru/sedna/, 2008.
• 11: MonetDB - open source XML database. http://monetdb.cwi.nl/, 2008.
• 12: The World Wide Web Consortium. http://www.w3.org/, 2008.
• 13: Noonan C., Durrigan C. and Roantree M. Using an Oracle Repository to Accelerate XPath Queries. In 17th International Conference on Database and Expert Systems Applications (DEXA 2006), LNCS vol. 4080, pp. 73--82, Springer, 2006.
• 14: Wenfei Fan , Jeffrey Xu Yu , Hongjun Lu , Jianhua Lu , Rajeev Rastogi, Query translation from XPATH to SQL in the presence of recursive DTDs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Jun Gao1., Dongqing Yang1 and Yunfeng Liu1. X2S: Translating XPath into Efficient SQL Queries. Conceptual Modeling for Advanced Application Domains, PSpringer Berlin / CoMWIM 2004. Web Information Integration, Pages 210--222.
• 16: Noonan C. and Roantree M. Optimising XML-based Web Information Systems. In Proceedings on International Workshop on Web Information Systems Modeling (WISM), pp. 803--814, Tapir Academic Press, 2007.
• 17: O'Connor M., Bellahsene Z. and Roantree M. An Extended PreOrder Index for Optimising XPath Expressions. Proceedings of 3rd XML Database Symposium, LNCS Vol. 3671, Springer, pp 114--128, 2005.
• 18: Qun C., Lim A. and Ong K. D(k)-Index: An Adaptive Structural Summary for Graph-Structured Data. Proceedings of the 29th VLDB Conference, Morgan Kaufmann, 2003.
• 19: Noonan C. Masters Thesis. Pruning XML Trees for XPath Query Optimisation. School of Computing, Dublin City University, 2007.
• 20: Suciu D. and Miklau G. University of Washington's XML Repository. at: URL http://www.cs.washington.edu/research/xmldatasets, 2002.
• 21: Frank Buschmann , Regine Meunier , Hans Rohnert , Peter Sommerlad , Michael Stal, Pattern-oriented software architecture: a system of patterns, John Wiley & Sons, Inc., New York, NY, 1996
• 22: Felix Weigel , Holger Meuss , Klaus U. Schulz , François Bry, Content and structure in indexing and ranking XML, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017092]
• 23: Ning Zhang , M. Tamer Özsu , Ihab F. Ilyas , Ashraf Aboulnaga, FIX: feature-based indexing technique for XML documents, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 24: O'Connor M. F., Roantree M. FASTX Repository Processing Framework. Technical Report ISG-08-01, Dublin City University, March 2008.
• 25: Megginson D., SAX - The Simple API for XML Version 2.0. Online Resource, 2008. http://www.saxproject.org/
• 26: Document Object Model (DOM) Level 3.0. World Wide Web Consortium, 2004. http://www.w3.org/DOM/
• 27: PostgreSQL, An Open Source Relational Database System Release 8.3.0. Online Resource, 2008. http://www.postgresql.org
• 28: 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]
• 29: Lu Qin and Jeffrey Xu Yu and Bolin Ding DASFAA, pp. 850--862, Springer, 2007.
• 30: Nicolas Bruno and Nick Koudas and Divesh Srivastava Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pp. 310--321, ACM, 2002.
• 31: Songting Chen and Hua-Gang Li and Junichi Tatemura and Wang-Pin Hsiung and Divyakant Agrawal and K. Selçuk Candan Proceedings of the 32nd international conference on Very large data bases, pp. 283--294, VLDB Endowment, 2006.
• 32: Torsten Grust , Jan Rittinger , Jens Teubner, Why off-the-shelf RDBMSs are better at XPath than you might expect, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247591]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Languages, Performance

Keywords:
XML storage, XPath optimisation, mapping techniques, patterns