Forward node-selecting queries over trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Forward node-selecting queries over trees

Full text

Pdf (511 KB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 32 , Issue 1 (March 2007) table of contents

Article No. 3

Year of Publication: 2007

ISSN:0362-5915

Author

Dan Olteanu

Universität des Saarlandes, Saarbrücken, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 86, Citation Count: 5

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

ABSTRACT

Node-selecting queries over trees lie at the core of several important XML languages for the web, such as the node-selection language XPath, the query language XQuery, and the transformation language XSLT. The main syntactic constructs of such queries are the backward predicates, for example, ancestor and preceding, and the forward predicates, for example, descendant and following. Forward predicates are included in the depth-first, left-to-right preorder relation associated with the input tree, whereas backward predicates are included in the inverse of this preorder relation.

This work is devoted to an expressiveness study of node-selecting queries with proven theoretical and practical applicability, especially in the field of query evaluation against XML streams. The main question it answers positively is whether, for each input query with forward and backward predicates, there exists an equivalent forward-only output query. This question is then positively answered for input and output queries of varying structural complexity, using LOGLIN and PSPACE reductions.

Various existing applications based on the results of this work are reported, including query optimization and streamed evaluation.

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	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	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	S. Amer-Yahia , S. Cho , L. V. S. Lakshmanan , D. Srivastava, Tree pattern query minimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.315-331, December 2002 [doi>10.1007/s00778-002-0076-7]
	4	Apache Project. 2001a. Cocoon 2.0: XML publishing framework. http://xml.apache.org/cocoon/index.html.
	5	Apache Project. 2001b. Xalan-Java, version 2.2. http://xml.apache.org/xalan-j/index.html.
	6	Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
	7	Barton, C., Charles, P., Goyal, D., Raghavachari, M., Fontoura, M., and Josifovski, V. 2003. Streaming XPath processing with forward and backward axes. In Proceedings of the International Conference on Data Engineering (ICDE). 455--466.
	8	Michael Benedikt , Wenfei Fan , Gabriel Kuper, Structural properties of XPath fragments, Theoretical Computer Science, v.336 n.1, p.3-31, 25 May 2005 [doi>10.1016/j.tcs.2004.10.030]
	9	Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Siméon, J. 2006. XQuery 1.0: An XML query language. Candidate recommendation, World Wide Web Consortium.
	10	Francois Bry , Fatih Coskun , Serap Durmaz , Tim Furche , Dan Olteanu , Markus Spannagel, The XML Stream Query Processor SPEX, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.1120-1121, April 05-08, 2005 [doi>10.1109/ICDE.2005.141]
	11	François Bry , Peer Kröger, A Computational Biology Database Digest: Data, Data Analysis, and Data Management, Distributed and Parallel Databases, v.13 n.1, p.7-42, January 2003 [doi>10.1023/A:1021540705916]
	12	Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
	13	Clark, J. 1999. XSL Transformations (XSLT) version 1.0. W3C recommendation, World Wide Web Consortium.
	14	Clark, J. and DeRose, S. 1999. XML path language (XPath) version 1.0. W3C recommendation, World Wide Web Consortium.
	15	DeRose, S., Jr., R. D., Grosso, P., Maler, E., Marsh, J., and Walsh, N. 2002. XML pointer language (XPointer). W3C recommendation, World Wide Web Consortium. http://www.w3.org/TR/xptr/.
	16	Desai, A. 2001. Introduction to sequential XPath. In Proceedings of the IDEAlliance XML Conference.
	17	Fallside, D. C. and Walmsley, P. 2001. XML-Schema. W3C recommendation, World Wide Web Consortium. http://www.w3.org/XML/Schema.
	18	Flesca, S., Furfaro, F., and Masciari, E. 2003. On the minimization of XPath queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 153--164.
	19	Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 95--106.
	20	Georg Gottlob , Christoph Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM (JACM), v.51 n.1, p.74-113, January 2004 [doi>10.1145/962446.962450]
	21	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 [doi>10.1145/1131342.1131345]
	22	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]
	23	Sven Helmer , Carl-Christian Kanne , Guido Moerkotte, Optimized Translation of XPath into Algebraic Expressions Parameterized by Programs Containing Navigational Primitives, Proceedings of the 3rd International Conference on Web Information Systems Engineering, p.215-224, December 12-14, 2002
	24	Hidders, J. and Michiels, P. 2003. Avoiding unnecessary ordering operations in XPath. In Proceedings of the International Conference on Data Base Programming Languages (DBPL). 54--70.
	25	Ide, N., Bonhomme, P., and Romary, L. 2000. XCES: An XML-Based standard for linguistic corpora. In Proceedings of the Annual Conference on Language Resources and Evaluation (LREC) 825--830.
	26	Zachary G. Ives , A. Y. Halevy , D. S. Weld, An XML query engine for network-bound data, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.380-402, December 2002 [doi>10.1007/s00778-002-0078-5]
	27	Kay, M. 2004. XSL Transformations (XSLT), version 2.0. Working draft, World Wide Web Consortium.
	28	Patrick Lincoln , Jim Christian, Adventures in associative-communtative unification, Journal of Symbolic Computation, v.8 n.1-2, p.217-240, Jul./Aug. 1989 [doi>10.1016/S0747-7171(89)80026-4]
	29	Marian, A. and Siméon, J. 2003. Projecting XML documents. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 213--224.
	30	Maarten Marx, Conditional XPath, ACM Transactions on Database Systems (TODS), v.30 n.4, p.929-959, December 2005 [doi>10.1145/1114244.1114247]
	31	NASA. 2004. XML group resources page. http://xml.gsfc.nasa.gov/.
	32	Newman, M. H. A. 1942. On theories with a combinatorial definition of ‘equivalence’. Ann. Math. 43, 2, 223--243.
	33	Olteanu, D. 2004. Evaluation of XPath queries against XML streams. Ph.D. thesis, University of Munich.
	34	Olteanu, D., Furche, T., and Bry, F. 2004. Evaluating complex queries against XML streams with polynomial combined complexity. In Proceedings of the Annual British National Conference on Databases (BNCOD). 31--44.
	35	Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
	36	Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
	37	Raghavan, V., Deschler, K., and Rundensteiner, E. A. 2005. Vamana: A scalable cost-driven XPath engine. In International Workshop on XML Schema and Data Management (XSDM).
	38	Steffen Schott , Markus L. Noga, Lazy XSL transformations, Proceedings of the 2003 ACM symposium on Document engineering, November 20-22, 2003, Grenoble, France [doi>10.1145/958220.958224]
	39	Wood, P. T. 2001. Minimizing simple XPath expressions. In Proceedings of the International Workshop on Web and Databases (WebDB). 13--18.

CITED BY 5

	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
	Stefanos Souldatos , Xiaoying Wu , Dimitri Theodoratos , Theodore Dalamagas , Timos Sellis, Evaluation of partial path queries on xml data, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Dimitri Theodoratos , Xiaoying Wu, Assigning semantics to partial tree-pattern queries, Data & Knowledge Engineering, v.64 n.1, p.242-265, January, 2008
	Pawel Placek , Dimitri Theodoratos , Stefanos Souldatos , Theodore Dalamagas , Timos Sellis, A heuristic approach for checking containment of generalized tree-pattern queries, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Dan Olteanu, SPEX: Streamed and Progressive Evaluation of XPath, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.934-949, July 2007