Efficient XPath query processing

ABSTRACT

We propose improved XPath query processing algorithms on XML documents by extending the MTree navigational XML database index. Our algorithms efficiently resolve element name specific XPath navigational queries, in many cases without a need for sorting or for qualified name filtering on intermediate sequences. The optimization methods are applicable for all axes but are presented for the four major XPath axes: descendant, ancestor, following and preceding. Experimental results are included that show substantial performance improvements over other well known methods.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: D. S. Batory , C. C. Gotlieb, A unifying model of physical databases, ACM Transactions on Database Systems (TODS), v.7 n.4, p.509-539, Dec. 1982 [doi>10.1145/319758.319760]
• 3: R. J. Bayardo , D. Gruhl , V. Josifovski , J. Myllymaki, An evaluation of binary xml encoding optimizations for fast stream based xml processing, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988719]
• 4: Kevin Beyer , Roberta J. Cochrane , Vanja Josifovski , Jim Kleewein , George Lapis , Guy Lohman , Bob Lyle , Fatma Özcan , Hamid Pirahesh , Normen Seemann , Tuong Truong , Bert Van der Linden , Brian Vickery , Chun Zhang, System RX: one part relational, one part XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066197]
• 5: B. C. Desai , P. Goyal , F. Sadri, Use of composite index in DDBMS, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.251-260, February 1986, Cincinnati, Ohio, United States [doi>10.1145/324634.325432]
• 6: T. Fiebig , S. Helmer , C.-C. Kanne , G. Moerkotte , J. Neumann , R. Schiele , T. Westmann, Anatomy of a native XML base management system, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.292-314, December 2002 [doi>10.1007/s00778-002-0080-y]
• 7: Haris Georgiadis , Vasilis Vassalos, Xpath on steroids: exploiting relational engines for xpath performance, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247517]
• 8: 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
• 9: 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]
• 10: Torsten Grust , Maurice van Keulen , Jens Teubner, Staircase join: teach a relational DBMS to watch its (axis) steps, Proceedings of the 29th international conference on Very large data bases, p.524-535, September 09-12, 2003, Berlin, Germany
• 11: Torsten Grust , Maurice Van Keulen , Jens Teubner, Accelerating XPath evaluation in any RDBMS, ACM Transactions on Database Systems (TODS), v.29 n.1, p.91-131, March 2004 [doi>10.1145/974750.974754]
• 12: 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]
• 13: Theo Haerder, Implementing a generalized access path structure for a relational database system, ACM Transactions on Database Systems (TODS), v.3 n.3, p.285-298, Sept. 1978 [doi>10.1145/320263.320284]
• 14: Hidders, J. and Michiels, P., Efficient XPath Axis Evaluation for DOM Data Structures, Workshop on Programming Language Technologies for XML (PLAN-X 2004)
• 15: 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]
• 16: Judy Mullins , Vijay Kumar, An integrated data structure with multiple access paths for database systems, Proceedings of the 1992 ACM annual conference on Communications, p.57-64, March 03-05, 1992, Kansas City, Missouri, United States [doi>10.1145/131214.131222]
• 17: McHugh, Jason and Jennifer Widom, Optimizing Branching Path Expressions. 1999. http://www-db.stanford.edu/lore/pubs/mp.pdf
• 18: Oracle, Oracle9i Index-Organized Tables Technical Whitepaper, http://www.oracle.com/technology/products/oracle9i/pdf/iot_twp.pdf, September 2001
• 19: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 20: P. Mark Pettovello , Farshad Fotouhi, MTree: an XML XPath graph index, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141389]
• 21: Pettovello, P. M., Brockmeyer, M. and Fotouhi, F. 2008. P2PXD: P2P Service Discovery and Routing. In Proceedings of IADIS Telecommunications, Networks and Systems, TNS 2008 (July 22--27, Amsterdam, Netherlands). MCCSIS'08.
• 22: W3C, xgrammar.zip http://www.w3.org/2004/08/applets/xqueryA pplet.html
• 23: Felix Weigel , Klaus U. Schulz , Holger Meuss, Exploiting native XML indexing techniques for XML retrieval in relational database systems, Proceedings of the 7th annual ACM international workshop on Web information and data management, November 04-04, 2005, Bremen, Germany [doi>10.1145/1097047.1097054]
• 24: XMLmind, Qizx/db XML Database. http://www.xmlmind.com/qizx
• 25: XSL family of specifications. http://www.w3.org/Style/XSL/
• 26: Beverly Yang , Marcus Fontoura , Eugene Shekita , Sridhar Rajagopalan , Kevin Beyer, Virtual cursors for XML joins, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031271]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Experimentation, Performance