Efficient algorithms for processing XPath queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient algorithms for processing XPath queries

Full text

Pdf (722 KB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 30 , Issue 2 (June 2005) table of contents

Pages: 444 - 491

Year of Publication: 2005

ISSN:0362-5915

Authors

Georg Gottlob	Technische Universität Wien, Vienna, Austria
Christoph Koch	Technische Universität Wien, Vienna, Austria
Reinhard Pichler	Technische Universität Wien, Vienna, Austria

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 213, Citation Count: 32

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1071610.1071614 What is a DOI?

ABSTRACT

Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We show that XPath can be processed much more efficiently, and propose main-memory algorithms for this problem with polynomial-time combined query evaluation complexity. Moreover, we show how the main ideas of our algorithm can be profitably integrated into existing XPath processors. Finally, we present two fragments of XPath for which linear-time query processing algorithms exist and another fragment with linear-space/quadratic-time query processing.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
	3	Apache Foundation. 2004. Xalan-Java version 2.2.D11. http://xml.apache.org/xalan-j/.
	4	Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, On the memory requirements of XPath evaluation over XML streams, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055584]
	5	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]
	6	Chan, C. Y., Fan, W., Felber, P., Garofalakis, M. N., and Rastogi, R. 2002a. Tree pattern aggregation for scalable XML data dissemination. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02) (Hong Kong, China). 826--837.
	7	Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
	8	Clark, J. 1999. XT---A Java implementation of XSLT. http://www.jclark.com/xml/xt.html/.
	9	Georg Gottlob , Christoph Koch, Monadic Queries over Tree-Structured Data, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.189-202, July 22-25, 2002
	10	Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
	11	Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
	12	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]
	13	Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
	14	Kay, M. 2003. Saxon version 6.5.2. http://saxon.sourceforge.net/.
	15	Kilpeläinen, P. 1992. Tree matching problems with applications to structured text databases. Ph.D. dissertation. Department of Computer Science, University of Helsinki. Report A-1992-6.
	16	Microsoft Corporation. 2001. Internet Explorer IE6. http://www.microsoft.com/windows/ie/default.asp.
	17	Feng Peng , Sudarshan S. Chawathe, XPath queries on streaming data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872810]
	18	Prakash Ramanan, Efficient algorithms for minimizing tree pattern queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564726]
	19	Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773170]
	20	Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
	21	Philip Wadler, A formal semantics of patterns in XSLT and XPath, Markup Languages, v.2 n.2, p.183-202, Spring 2000 [doi>10.1162/10996620052104302]
	22	Wadler, P. 2000. Two semantics for XPath. Draft paper available at http://www.research.avayalabs. com/user/wadler/.
	23	World Wide Web Consortium. 1998. XSL working draft http://www.w3.org/TR/1998/WD-xsl-19981216.
	24	World Wide Web Consortium. 1999. XML Path Language (XPath) Recommendation. http://www.w3c.org/TR/xpath/.
	25	World Wide Web Consortium. 2000. Extensible Markup Language (XML) 1.0 (second edition). http://www.w3.org/TR/REC-xml.
	26	World Wide Web Consortium. 2002. XQuery 1.0 and XPath 2.0 formal semantics. W3C working draft (Aug. 16th 2002). http://www.w3.org/TR/query-algebra/.
	27	World Wide Web Consortium. 2004a. DOM Specification http://www.w3c.org/DOM/.
	28	World Wide Web Consortium. 2004b. XML Path Language (XPath) 2.0, working draft. http://www.w3.org/TR/2004/WD-xpath20-20040723/.
	29	Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81). 82--94.

CITED BY 32

	Marc Gyssens , Jan Paredaens , Dirk Van Gucht , George H. L. Fletcher, Structural characterizations of the semantics of XPath as navigation tool on a document, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Pierre Genevès , Nabil Layaïda, Comparing XML path expressions, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands
	Markus Lohrey , Sebastian Maneth, The complexity of tree automata and XPath on grammar-compressed trees, Theoretical Computer Science, v.363 n.2, p.196-210, 28 October 2006
	Christoph Koch, Processing queries on tree-structured data efficiently, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Journal of the ACM (JACM), v.53 n.2, p.238-272, March 2006
	Pierre Genevès , Nabil Layaïda, A system for the static analysis of XPath, ACM Transactions on Information Systems (TOIS), v.24 n.4, p.475-502, October 2006
	Jaap Kamps , Maarten Marx , Maarten de Rijke , Börkur Sigurbjörnsson, Articulating information needs in XML query languages, ACM Transactions on Information Systems (TOIS), v.24 n.4, p.407-436, October 2006
	James J. Lu , Chia-Hsin Huang , Tyng-Ruey Chuang, Querying and browsing XML and relational data sources, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Ding Chen , Chee-Yong Chan, Minimization of tree pattern queries with constraints, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Emmanuel Filiot , Joachim Niehren , Jean-Marc Talbot , Sophie Tison, Polynomial time fragments of XPath with variables, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Michael Haustein , Theo Härder, An efficient infrastructure for native transactional XML processing, Data & Knowledge Engineering, v.61 n.3, p.500-523, June, 2007
	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
	Xiaoying Wu , Stefanos Souldatos , Dimitri Theodoratos , Theodore Dalamagas , Timos Sellis, Efficient evaluation of generalized path pattern queries on XML data, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Mikolaj Bojańczyk , Pawel Parys, XPath evaluation in linear time, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Wolfgang May , Erik Behrends , Oliver Fritzen, Integrating and querying distributed XML data via XLink, Information Systems, v.33 n.6, p.508-566, September, 2008
	Gang Gou , Rada Chirkova, Efficiently Querying Large XML Data Repositories: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1381-1403, October 2007
	Nils Grimsmo, Faster path indexes for search in XML data, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Michael Benedikt , Christoph Koch, XPath leashed, ACM Computing Surveys (CSUR), v.41 n.1, p.1-54, December 2008
	Sven Groppe , Jinghua Groppe , Stefan Böttcher, Simplifying XPath queries for optimization with regard to the elimination of intersect and except operators, Data & Knowledge Engineering, v.65 n.2, p.198-222, May, 2008
	Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM (JACM), v.55 n.2, p.1-79, May 2008
	Daniel Deutch , Tova Milo, Type inference and type checking for queries on execution traces, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Krzysztof Jankiewicz , Aleksandra Siekierska , Maciej Siekierski, Quantity comparison of concurrency control methods for XML database systems based on DOM API, International Journal of Web Engineering and Technology, v.4 n.4, p.534-554, August 2008
	Sofía Brenes, Structural summaries for efficient XML query processing, Proceedings of the 2008 EDBT Ph.D. workshop, March 25-25, 2008, Nantes, France
	Tova Milo , Daniel Deutch, Querying and monitoring distributed business processes, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Rajesh Bordawekar , Lipyeow Lim , Oded Shmueli, Parallelization of XPath queries using multi-core processors: challenges and experiences, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Henrik Björklund , Wouter Gelade , Marcel Marquardt , Wim Martens, Incremental XPath evaluation, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	George H. L. Fletcher , Dirk Van Gucht , Yuqing Wu , Marc Gyssens , Sofía Brenes , Jan Paredaens, A methodology for coupling fragments of XPath with structural indexes for XML documents, Information Systems, v.34 n.7, p.657-670, November, 2009
	Pawel Parys, XPath evaluation in linear time with polynomial combined complexity, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Serge Abiteboul , Pierre Bourhis , Bogdan Marinoiu, Satisfiability and relevance for queries over active documents, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Michaela Götz , Christoph Koch , Wim Martens, Efficient algorithms for descendant-only tree pattern queries, Information Systems, v.34 n.7, p.602-623, November, 2009
	Sven Hartmann , Sebastian Link, Efficient reasoning about a robust XML key fragment, ACM Transactions on Database Systems (TODS), v.34 n.2, p.1-33, June 2009
	Diego Figueira, Satisfiability of downward XPath with data equality tests, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA