Accelerating XPath location steps

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Accelerating XPath location steps

Full text

Pdf (1.12 MB)

Source

International Conference on Management of Data archive
Proceedings of the 2002 ACM SIGMOD international conference on Management of data table of contents

Madison, Wisconsin

SESSION: Research sessions: path indexing table of contents

Pages: 109 - 120

Year of Publication: 2002

ISBN:1-58113-497-5

Author

Torsten Grust

University of Konstanz, D-78457 Konstanz, Germany

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 130, Citation Count: 70

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/564691.564705 What is a DOI?

ABSTRACT

This work is a proposal for a database index structure that has been specifically designed to support the evaluation of XPath queries. As such, the index is capable to support all XPath axes (including ancestor, following, preceding-sibling, descendant-or-self, etc.). This feature lets the index stand out among related work on XML indexing structures which had a focus on regular path expressions (which correspond to the XPath axes children and descendant-or-self plus name tests). Its ability to start traversals from arbitrary context nodes in an XML document additionally enables the index to support the evaluation of path traversals embedded in XQuery expressions. Despite its flexibility, the new index can be implemented and queried using purely relational techniques, but it performs especially well if the underlying database host provides support for R-trees. A performance assessment which shows quite promising results completes this proposal.

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	Anders Berglund, Scott Boag, Don Chamberlin, Mary F. Fernandez, Michael Kay, Jonathan Robie, and Jérôme Siméon. XML Path Language (XPath) 2.0. Technical Report W3C Working Draft, Version 2.0, World Wide Web Consortium, December 2001. http://www.w3.org/TR/xpath20/.
	2	Christian Böhm , Stefan Berchtold , Hans-Peter Kriegel , Urs Michel, Multidimensional Index Structures in Relational Databases, Journal of Intelligent Information Systems, v.15 n.1, p.51-70, July—Aug. 2000 [doi>10.1023/A:1008729828172]
	3	John Bosak. XML markup of Shakespeare's plays, January 1998. http://www.ibiblio.org/pub/sun-info/standards/xml/eg/.
	4	Don Chamberlin, James Clark, Daniela Florescu, Jonathan Robie, Jérôme Siméon, and Mugur Stefanescu. XQuery 1.0: An XML Query Language. Technical Report W3C Working Draft, World Wide Web Consortium, December 2001. http://www.w3.org/TR/xquery.
	5	Zhiyuan Chen , H. V. Jagadish , Flip Korn , Nick Koudas , S. Muthukrishnan , Raymond T. Ng , Divesh Srivastava, Counting Twig Matches in a Tree, Proceedings of the 17th International Conference on Data Engineering, p.595-604, April 02-06, 2001
	6	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
	7	P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
	8	Daniela Florescu and Donald Kossmann. A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database. Technical Report 3680, INRIA, Rocquencourt, France, May 1999.
	9	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
	10	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	11	Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
	12	Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
	13	Hans-Peter Kriegel , Marco Pötke , Thomas Seidl, Managing Intervals Efficiently in Object-Relational Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.407-418, September 10-14, 2000
	14	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
	15	SAX (Simple API for XML). http://sax.sourceforge.net/.
	16	A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
	17	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
	18	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

CITED BY 70

	Ralf Duckstein , Klemens Böhm, Database support for species extraction from the biosystematics literature: a feasibility demonstration, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Kurt Deschler , Elke Rundensteiner, MASS: a multi-axis storage structure for large XML documents, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Patrick O'Neil , Elizabeth O'Neil , Shankar Pal , Istvan Cseri , Gideon Schaller , Nigel Westbury, ORDPATHs: insert-friendly XML node labels, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Tae-Sun Chung , Hyoung-Joo Kim, Techniques for the evaluation of XML queries: a survey, Data & Knowledge Engineering, v.46 n.2, p.225-246, August 2003
	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
	Yi Chen , Susan B. Davidson , Yifeng Zheng, BLAS: an efficient XPath processing system, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	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
	Chia-Hsin Huang , Tyng-Ruey Chuang , Hahn-Ming Lee, Fast structural query with application to chinese treebank sentence retrieval, Proceedings of the 2004 ACM symposium on Document engineering, October 28-30, 2004, Milwaukee, Wisconsin, USA
	Yi Chen , George A. Mihaila , Susan B. Davidson , Sriram Padmanabhan, EXPedite: a system for encoded XML processing, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Jaap Kamps , Maarten Marx , Maarten de Rijke , Börkur Sigurbjörnsson, Best-match querying from document-centric XML, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France
	Börkur Sigurbjörnsson , Jaap Kamps , Maarten de Rijke, Processing content-oriented XPath queries, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Hongjun Lu , Jeffrey Xu Yu , Guoren Wang , Shihui Zheng , Haifeng Jiang , Ge Yu , Aoying Zhou, What makes the differences: benchmarking XML database implementations, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.154-194, February 2005
	Martin Theobald , Ralf Schenkel , Gerhard Weikum, An efficient and versatile query engine for TopX search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Peter Boncz , Torsten Grust , Maurice van Keulen , Stefan Manegold , Jan Rittinger , Jens Teubner, Pathfinder: XQuery---the relational way, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Wei Wang , Haifeng Jiang , Hongzhi Wang , Xuemin Lin , Hongjun Lu , Jianzhong Li, Efficient processing of XML path queries using the disk-based F&B Index, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	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
	Maggie Duong , Yanchun Zhang, LSDX: a new labelling scheme for dynamically updating XML data, Proceedings of the sixteenth Australasian database conference, p.185-193, January 01, 2005, Newcastle, Australia
	Carl-Christian Kanne , Matthias Brantner , Guido Moerkotte, Cost-sensitive reordering of navigational primitives, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	SungRan Cho , Nick Koudas , Divesh Srivastava, MIX: a meta-data indexing system for XML, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Integrating XML data sources using approximate joins, ACM Transactions on Database Systems (TODS), v.31 n.1, p.161-207, March 2006
	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
	Jun-Ki Min , Myung-Jae Park , Chin-Wan Chung, A compressor for effective archiving, retrieval, and updating of XML documents, ACM Transactions on Internet Technology (TOIT), v.6 n.3, p.223-258, August 2006
	Damien K. Fisher , Franky Lam , William M. Shui , Raymond K. Wong, Dynamic labeling schemes for ordered XML based on type information, Proceedings of the 17th Australasian Database Conference, p.59-68, January 16-19, 2006, Hobart, Australia
	Praveen Rao , Bongki Moon, Sequencing XML data and query twigs for fast pattern matching, ACM Transactions on Database Systems (TODS), v.31 n.1, p.299-345, March 2006
	Mustafa Atay , Artem Chebotko , Dapeng Liu , Shiyong Lu , Farshad Fotouhi, Efficient schema-based XML-to-Relational data mapping, Information Systems, v.32 n.3, p.458-476, May, 2007
	Zhiyuan Chen , Johannes Gehrke , Flip Korn , Nick Koudas , Jayavel Shanmugasundaram , Divesh Srivastava, Index structures for matching XML twigs using relational query processors, Data & Knowledge Engineering, v.60 n.2, p.283-302, February, 2007
	S. Alireza Aghili , Hua-Gang Li , Divyakant Agrawal , Amr El Abbadi, TWIX: twig structure and content matching of selective queries using binary labeling, Proceedings of the 1st international conference on Scalable information systems, p.42-es, May 30-June 01, 2006, Hong Kong
	SungRan Cho , Nick Koudas , Divesh Srivastava, Meta-data indexing for XPath location steps, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Karen Sauvagnat , Mohand Boughanem , Claude Chrisment, Answering content and structure-based queries on XML documents using relevance propagation, Information Systems, v.31 n.7, p.621-635, November 2006
	Qun Chen , Andrew Lim , Kian Win Ong , Jiqing Tang, Indexing XML documents for XPath query processing in external memory, Data & Knowledge Engineering, v.59 n.3, p.681-699, December 2006
	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
	Torsten Grust , Sherif Sakr , Jens Teubner, XQuery on SQL hosts, Proceedings of the Thirtieth international conference on Very large data bases, p.252-263, August 31-September 03, 2004, Toronto, Canada
	Chang-Xuan Wan , Xi-Ping Liu, Structural join and staircase join algorithms of sibling relationship, Journal of Computer Science and Technology, v.22 n.2, p.171-181, March 2007
	Haifeng Jiang , Wei Wang , Hongjun Lu , Jeffrey Xu Yu, Holistic twig joins on indexed XML documents, Proceedings of the 29th international conference on Very large data bases, p.273-284, September 09-12, 2003, Berlin, Germany
	Keishi Tajima , Yoshiki Fukui, Answering xpath queries over networks by sending minimal views, Proceedings of the Thirtieth international conference on Very large data bases, p.48-59, August 31-September 03, 2004, Toronto, Canada
	Sabine Mayer , Torsten Grust , Maurice van Keulen , Jens Teubner, An injection with tree awareness: adding staircase join to postgreSQL, Proceedings of the Thirtieth international conference on Very large data bases, p.1305-1308, August 31-September 03, 2004, Toronto, Canada
	Liang Huai Yang , Mong Li Lee , Wynne Hsu, Efficient mining of XML query patterns for caching, Proceedings of the 29th international conference on Very large data bases, p.69-80, September 09-12, 2003, Berlin, Germany
	Shankar Pal , Istvan Cseri , Oliver Seeliger , Gideon Schaller , Leo Giakoumakis , Vasili Zolotov, Indexing XML data stored in a relational database, Proceedings of the Thirtieth international conference on Very large data bases, p.1146-1157, August 31-September 03, 2004, Toronto, Canada
	Akihiro Inokuchi , Koichi Takeda , Noriko Inaoka , Fumihiko Wakao, MedTAKMI-CDI: interactive knowledge discovery for clinical decision intelligence, IBM Systems Journal, v.46 n.1, p.115-133, January 2007
	Shu-Yao Chien , Zografoula Vagena , Donghui Zhang , Vassilis J. Tsotras , Carlo Zaniolo, Efficient structural joins on indexed XML documents, Proceedings of the 28th international conference on Very Large Data Bases, p.263-274, August 20-23, 2002, Hong Kong, China
	Andrei Arion , Angela Bonifati , Ioana Manolescu , Andrea Pugliese, XQueC: A query-conscious compressed XML database, ACM Transactions on Internet Technology (TOIT), v.7 n.2, p.10-es, May 2007
	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
	Artem Chebotko , Mustafa Atay , Shiyong Lu , Farshad Fotouhi, XML subtree reconstruction from relational storage of XML documents, Data & Knowledge Engineering, v.62 n.2, p.199-218, August, 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
	Radim Bača , Michal Krátký , Václav Snášel, On the efficient search of an XML twig query in large DataGuide trees, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	Dunren Che , Karl Aberer , Tamer Özsu, Query optimization in XML structured-document databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.263-289, September 2006
	Ralf Schenkel , Anja Theobald , Gerhard Weikum, Semantic Similarity Search on Semistructured Data with the XXL Search Engine, Information Retrieval, v.8 n.4, p.521-545, December 2005
	Johan List , Vojkan Mihajlovic , Vojkan Mihajlovi , Georgina Ramírez , Arjen P. Vries , Djoerd Hiemstra , Henk Ernst Blok, TIJAH: Embracing IR Methods in XML Databases, Information Retrieval, v.8 n.4, p.547-570, December 2005
	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
	Hongzhi Wang , Jianzhong Li , Wei Wang , Xuemin Lin, Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document, World Wide Web, v.11 n.4, p.485-510, December 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
	I. Sanz , M. Mesiti , G. Guerrini , R. Berlanga, Fragment-based approximate retrieval in highly heterogeneous XML collections, Data & Knowledge Engineering, v.64 n.1, p.266-293, January, 2008
	Jens Teubner, Scalable XQuery type matching, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Torsten Grust , Jan Rittinger , Jens Teubner, Data-intensive XQuery debugging with instant replay, Proceedings of the 4th international workshop on XQuery implementation, experience and perspectives, p.1-6, June 15-15, 2007, Beijing, China
	Akihiro Inokuchi , Koichi Takeda, A method for online analytical processing of text data, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Rebecca J. Cathey , Steven M. Beitzel , Eric C. Jensen , David Grossman , Ophir Frieder, Using a relational database for scalable XML search, The Journal of Supercomputing, v.44 n.2, p.146-178, May 2008
	Olli Luoma, Relevance measures for XML information retrieval, International Journal of Web and Grid Services, v.3 n.2, p.170-193, June 2007
	Shirish Tatikonda , Srinivasan Parthasarathy , Matthew Goyder, LCS-TRIM: dynamic programming meets XML indexing and querying, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Alexander Holupirek , Marc H. Scholl, Implementing filesystems by tree-aware DBMSs, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Virginie Sans , Dominique Laurent, Prefix based numbering schemes for XML: techniques, applications and performances, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Gerard Marks , Mark Roantree, Pattern based processing of XPath queries, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	P. Mark Pettovello , Farshad Fotouhi, Efficient XPath query processing, Proceedings of the 2008 conference of the center for advanced studies on collaborative research: meeting of minds, October 27-30, 2008, Ontario, Canada
	Hongzhi Wang , Jianzhong Li , Jizhou Luo , Hong Gao, Hash-base subgraph query processing method for graph-structured XML documents, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Fernando Farfán , Vagelis Hristidis , Raju Rangaswami, 2LP: A double-lazy XML parser, Information Systems, v.34 n.1, p.145-163, March, 2009
	Jun-Ki Min , Jihyun Lee , Chin-Wan Chung, An efficient XML encoding and labeling method for query processing and updating on dynamic XML data, Journal of Systems and Software, v.82 n.3, p.503-515, March, 2009
	K. Selçuk Candan , Mehmet E. Dönderler , Yan Qi , Jaikannan Ramamoorthy , Jong W. Kim, FMware: middleware for efficient filtering and matching of XML messages with local data, Proceedings of the ACM/IFIP/USENIX 2006 International Conference on Middleware, November 01-01, 2006, Melbourne, Australia
	Alexander Holupirek , Christian Grün , Marc H. Scholl, BaseX & DeepFS joint storage for filesystem and database, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Oleksandr Panchenko, Hybrid storage for enabling fully-featured text search and fine-grained structural search over source code, Proceedings of the 2009 ICSE Workshop on Search-Driven Development-Users, Infrastructure, Tools and Evaluation, p.37-40, May 16-16, 2009
	Haris Georgiadis , Minas Charalambides , Vasilis Vassalos, Cost based plan selection for xpath, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA