XPath leashed

ABSTRACT

This survey gives an overview of formal results on the XML query language XPath. We identify several important fragments of XPath, focusing on subsets of XPath 1.0. We then give results on the expressiveness of XPath and its fragments compared to other formalisms for querying trees, algorithms, and complexity bounds for evaluation of XPath queries, as well as static analysis of XPath queries.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Afanasiev, L., Blackburn, P., Dimitriou, I., Gaiffe, B., Goris, E., Marx, M., and de Rijke, M. 2005. PDL for ordered trees. J. Appl. Non-Classical Logics 15, 115--135.
• 3: Loredana Afanasiev , Massimo Franceschet , Maarten Marx , Maarten de Rijke, CTL Model Checking for Processing Simple XPath Queries, Proceedings of the 11th International Symposium on Temporal Representation and Reasoning, p.117-124, July 01-03, 2004
• 4: Shurug Al-Khalifa , H. V. Jagadish, Multi-level operator combination in XML query processing, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584817]
• 5: 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
• 6: 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
• 7: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 8: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, Buffering in query evaluation over XML streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065195]
• 9: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, On the memory requirements of XPath evaluation over XML streams, Journal of Computer and System Sciences, v.73 n.3, p.391-441, May, 2007 [doi>10.1016/j.jcss.2006.10.002]
• 10: Pablo Barcelo, Temporal Logics over Unranked Trees, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, p.31-40, June 26-29, 2005 [doi>10.1109/LICS.2005.51]
• 11: Danièle Beauquier , Jean-Eric Pin, Factors of Words, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.63-79, July 11-15, 1989
• 12: Benedikt, M., Bonifati, A., Flesca, S., and Vyas, A. 2005. Verification of tree updates for optimization. In Proceedings of the 17th International Conference on Computer Aided Verification.
• 13: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065172]
• 14: Michael Benedikt , Wenfei Fan , Gabriel M. Kuper, Structural Properties of XPath Fragments, Proceedings of the 9th International Conference on Database Theory, p.79-95, January 08-10, 2003
• 15: Bird, S., Chen, Y., Davidson, S., Lee, H., and Zheng, Y. 2005. Extending XPath to support linguistic queries. In PLAN-X.
• 16: Börger, E., Grädel, E., and Gurevich, Y. 1997. The Classical Decision Problem. Springer.
• 17: Matthias Brantner , Sven Helmer , Carl-Christian Kanne , Guido Moerkotte, Full-Fledged Algebraic XPath Processing in Natix, Proceedings of the 21st International Conference on Data Engineering, p.705-716, April 05-08, 2005 [doi>10.1109/ICDE.2005.69]
• 18: Brüggemann-Klein, A., Murata, M., and Wood, D. 2001. Regular tree and regular hedge languages over non-ranked alphabets: Version 1, April 3, 2001. Tech. Rep. HKUST-TCSC-2001-05, Hong Kong University of Science and Technology, Hong Kong SAR, China.
• 19: 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]
• 20: Burch, J., Clarke, E., McMillan, K., Dill, D., and Hwang, L. 1990. Symbolic model checking: 10²⁰ states and beyond. In Proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS).
• 21: Carme, J., Niehren, J., and Tommasi, M. 2004. Querying unranked trees with stepwise tree automata. In Rewriting Techniques and Applications.
• 22: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 23: Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
• 24: Clarke, E. M., Grumberg, O., and Peled, D. 2000. Model Checking. MIT Press.
• 25: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 26: Deutsch, A. and Tannen, V. 2001. Containment and integrity constraints for XPath. In Proceedings of the International Workshop on Knowledge Representation Meets Databases (KRDB). CEUR Workshop Proceedings 45.
• 27: YFilter: Efficient and Scalable Filtering of XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.341, February 26-March 01, 2002
• 28: Doner, J. 1970. Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4, 406--451.
• 29: Kousha Etessami , Moshe Y. Vardi , Thomas Wilke, First-order logic with two variables and unary temporal logic, Information and Computation, v.179 n.2, p.279-295, December 15, 2002 [doi>10.1006/inco.2001.2953]
• 30: Kousha Etessami , Thomas Wilke, An Until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic, Information and Computation, v.160 n.1-2, p.88-108, July 10/Aug. 1, 2000 [doi>10.1006/inco.1999.2846]
• 31: Wenfei Fan , Chee-Yong Chan , Minos Garofalakis, Secure XML querying with security views, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007634]
• 32: Thorsten Fiebig , Guido Moerkotte, Evaluating Queries on Structure with eXtended Access Support Relations, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.125-136, May 18-19, 2000
• 33: Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002 [doi>10.1145/602220.602222]
• 34: Markus Frick , Martin Grohe , Christoph Koch, Query Evaluation on Compressed Trees (Extended Abstract), Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p.188, June 22-25, 2003
• 35: Geerts, F. and Fan, W. 2005. XPath satisfiability with sibling axes. In Proceedings of the 10th International Conference on Database Programming Languages (DBPL).
• 36: 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
• 37: 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]
• 38: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, Proceedings of the 28th international conference on Very Large Data Bases, p.95-106, August 20-23, 2002, Hong Kong, China
• 39: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
• 40: Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005 [doi>10.1145/1059513.1059520]
• 41: Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, 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.1055585]
• 42: Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303979]
• 43: Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001 [doi>10.1145/382780.382783]
• 44: Gottlob, G., Leone, N., and Scarcello, F. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 3, 579--627.
• 45: Götz, M., Koch, C., and Martens, W. 2007. Efficient algorithms for the tree homeomorphism problem. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL).
• 46: Gang Gou , Rada Chirkova, Efficient algorithms for evaluating xpath over streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247512]
• 47: Grädel, E., Kolaitis, P., and Vardi, M. 1997. On the decision problem for two-variable first-order logic. Bull. Symbol. Logic 3, 53--69.
• 48: 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
• 49: Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
• 50: Martin Grohe , Christoph Koch , Nicole Schweikardt, Tight lower bounds for query processing on streaming and external memory data, Theoretical Computer Science, v.380 n.1-2, p.199-217, June, 2007 [doi>10.1016/j.tcs.2007.02.062]
• 51: 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
• 52: 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]
• 53: 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]
• 54: Hidders, J. 2003. Satisfiability of XPath expressions. In Proceedings of the 9th International Conference on Database Programming Language (DBPL).
• 55: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 56: Immerman, N. 1999. Descriptive Complexity. Springer Graduate Texts in Computer Science.
• 57: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 58: Vanja Josifovski , Marcus Fontoura , Attila Barta, Querying XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.197-210, April 2005 [doi>10.1007/s00778-004-0123-7]
• 59: Kamp, H. 1968. Tense logic and the theory of linear order. Ph.D. thesis, University of California, Los Angeles.
• 60: Christoph Koch, Efficient processing of expressive node-selecting queries on XML data in secondary storage: a tree automata-based approach, Proceedings of the 29th international conference on Very large data bases, p.249-260, September 09-12, 2003, Berlin, Germany
• 61: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Journal of Computer and System Sciences, v.61 n.2, p.302-332, Oct. 2000 [doi>10.1006/jcss.2000.1713]
• 62: Laks V. S. Lakshmanan , Ganesh Ramesh , Hui Wang , Zheng Zhao, On testing satisfiability of tree pattern queries, Proceedings of the Thirtieth international conference on Very large data bases, p.120-131, August 31-September 03, 2004, Toronto, Canada
• 63: Lange, M. and Lutz, C. 2005. 2-ExpTime lower bounds for propositional dynamic logics with intersection. J. Symbol. Logic 70, 4, 1072--1086.
• 64: Leonid Libkin, Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series), SpringerVerlag, 2004
• 65: Maarten Marx, Conditional XPath, the first order complete XPath dialect, 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.1055562]
• 66: Marx, M. 2004b. XPath with conditional axis relations. In Proceedings of the International Conference on Extending Database Technologys (EDBT), 477--494.
• 67: Marx, M. 2005. First order paths in ordered trees. In Proceedings of the 10th International Conference on Database Theory (ICDT).
• 68: Marx, M. and de Rijke, M. 2004. Semantic characterizations of XPath. In the TDM Workshop on XML Databases and Information Retrieval.
• 69: May, N., Brantner, M., Böhm, A., Kanne, C.-C., and Moerkotte, G. 2006. Index vs. navigation in xpath evaluation. In Proceedings of the Workshop at the 4th International XML Database Symposium, 16--30.
• 70: Meyer, A. R. 1975. Weak monadic second order theory of successor is not elementary-recursive. In Proceedings of the Logic Colloquium. Lecture Notes in Mathematics, vol. 453. Springer, 132--154.
• 71: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, 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.543623]
• 72: Andreas Neumann , Helmut Seidl, Locating Matches of Tree Patterns in Forests, Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, p.134-145, December 17-19, 1998
• 73: Frank Neven, Automata theory for XML researchers, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601869]
• 74: Frank Neven , Thomas Schwentick, Query automata over finite trees, Theoretical Computer Science, v.275 n.1-2, p.633-674, March 28 2002 [doi>10.1016/S0304-3975(01)00301-2]
• 75: Frank Neven , Thomas Schwentick, XPath Containment in the Presence of Disjunction, DTDs, and Variables, Proceedings of the 9th International Conference on Database Theory, p.315-329, January 08-10, 2003
• 76: Frank Neven , Jan Van Den Bussche, Expressiveness of structured document query languages based on attribute grammars, Journal of the ACM (JACM), v.49 n.1, p.56-100, January 2002 [doi>10.1145/505241.505245]
• 77: 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 [doi>10.1109/TKDE.2007.1063]
• 78: Olteanu, D., Kiesling, T., and Bry, F. 2003. An evaluation of regular path expressions with qualifiers against XML streams. In Proceedings of the 19th International Conference on Data Engineering (ICDE). Full version in Tech. Rep. PMS-FB-2002-12, Ludwig-Maximilians-Universität München, Munich, Germany, 2002.
• 79: 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
• 80: 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 [doi>10.1145/1007568.1007686]
• 81: Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley.
• 82: 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]
• 83: Ramanan, P. 2005. Evaluating an XPath query on a streaming XML document. In Proceedings of the International Conference on Management of Data (COMAD), 41--52.
• 84: Klaus Reinhardt, The complexity of translating logic to finite automata, Automata logics, and infinite games: a guide to current research, Springer-Verlag New York, Inc., New York, NY, 2002
• 85: Thomas Schwentick, XPath query containment, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974140]
• 86: Thomas Schwentick, Automata for XML---A survey, Journal of Computer and System Sciences, v.73 n.3, p.289-315, May, 2007 [doi>10.1016/j.jcss.2006.10.003]
• 87: Thomas Schwentick , Denis Thérien , Heribert Vollmer, Partially-Ordered Two-Way Automata: A New Characterization of DA, Revised Papers from the 5th International Conference on Developments in Language Theory, p.239-250, July 16-21, 2001
• 88: Luc Segoufin , Victor Vianu, Validating streaming XML documents, 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.543622]
• 89: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 90: Sudborough, I. 1977. Time and tape bounded auxiliary pushdown automata. In Proceedings of the Conference on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 53. Springer, 493--503.
• 91: Sur, G., Hammer, J., and Simeon, J. 2004. An XQuery-based language for processing updates in XML. In Proceedings of the ACM SIGPLAN Workshop on Programming Language Technologies for XML (PLAN-X).
• 92: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 93: Thatcher, J. and Wright, J. 1968. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2, 1, 57--81.
• 94: Denis Thérien , Thomas Wilke, Over words, two variables are as powerful as one quantifier alternation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.234-240, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276749]
• 95: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 96: Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]
• 97: Moshe Y Vardi , Pierre Wolper, Automata-Theoretic techniques for modal logics of programs, Journal of Computer and System Sciences, v.32 n.2, p.183-221, April 1986 [doi>10.1016/0022-0000(86)90026-7]
• 98: H. Venkateswaran, Properties that characterize LOGCFL, Journal of Computer and System Sciences, v.43 n.2, p.380-404, Oct. 1991 [doi>10.1016/0022-0000(91)90020-6]
• 99: Wadler, P. 2000. Two semantics for XPath. http://www.research.avayalabs.com/user/wadler/.
• 100: Wadler, P. December 1999. A formal semantics of patterns in XSLT. In Markup Technologies. Philadelphia. Revised version in Markup Languages, MIT Press, June 2001.
• 101: Weigel, F., Schulz, K. U., and Meuss, H. 2005. The BIRD numbering scheme for XML and tree databases—Deciding and reconstructing tree relations using efficient arithmetic operations. In Proceedings of the International XML Database Symposium (XSym), 49--67.
• 102: Wood, P. T. 2001. Minimizing simple XPath expressions. In Proceedings of International Workshop on the Web and Databases (WebDB).
• 103: Peter T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory, p.300-314, January 08-10, 2003
• 104: World Wide Web Consortium. 1999a. XML path language (XPath) recommendation. http://www.w3c.org/TR/xpath/.
• 105: World Wide Web Consortium. 1999b. XSL transformations (XSLT). W3C recommendation version 1.0. http://www.w3.org/TR/xslt.
• 106: World Wide Web Consortium. 2001. XML schema part 0: Primer. W3C recommendation. http://www.w3c.org/XML/Schema.
• 107: 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/.
• 108: World Wide Web Consortium. 2007. XML path language (XPath) 2.0.
• 109: Mihalis Yannakakis, Algorithms for acyclic database schemes, Proceedings of the seventh international conference on Very Large Data Bases, p.82-94, September 09-11, 1981, Cannes, France

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

General Terms:
Languages

Keywords:
XML, XPath