Containment and equivalence for a fragment of XPath

ABSTRACT

XPath is a language for navigating an XML document and selecting a set of element nodes. XPath expressions are used to query XML data, describe key constraints, express transformations, and reference elements in remote documents. This article studies the containment and equivalence problems for a fragment of the XPath query language, with applications in all these contexts.In particular, we study a class of XPath queries that contain branching, label wildcards and can express descendant relationships between nodes. Prior work has shown that languages that combine any two of these three features have efficient containment algorithms. However, we show that for the combination of features, containment is coNP-complete. We provide a sound and complete algorithm for containment that runs in exponential time, and study parameterized PTIME special cases. While we identify one parameterized class of queries for which containment can be decided efficiently, we also show that even with some bounded parameters, containment remains coNP-complete. In response to these negative results, we describe a sound algorithm that is efficient for all queries, but may return false negatives in some cases.

REFERENCES

• 1: 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
• 2: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 3: J. Cai , R. Paige , R. Tarjan, More efficient bottom-up multi-pattern matching in trees, Theoretical Computer Science, v.106 n.1, p.21-60, Nov. 1992
• 4: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Answering and Query Containment over Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.40-61, September 08-10, 2001
• 5: Chamberlin, D., Clark, J., Florescu, D., Robie, J., Simeon, J., and Stefanascu, M. 2001. XQuery 1.0: An XML query language. http://www.w3.org/TR/xquery/.W3C working draft.
• 6: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 7: Richard Cole , Ramesh Hariharan , Piotr Indyk, Tree pattern matching and subset matching in deterministic O(n log3 n)-time, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.245-254, January 17-19, 1999, Baltimore, Maryland, United States
• 8: DeRose, S., Jr., R. D., and Maler, E. 1999. XML pointer language (XPointer) working draft. http://www.w3.org/TR/1999/WD-xptr-19991206.
• 9: DeRose, S., Maler, E., and Orchard, D. 2001. XML linking language (Xlink). http://www.w3.org/TR/2000/REC-xlink-20010627.
• 10: Deutsch, A. and Tannen, V. 2001. Containment and Integrity Constraints for XPath Fragments. In Proceedings of the 8th International Workshop on Knowledge Representation Meeting Database (KRDB) 2001 (Rome, Italy). CEUR Workshop Proceedings 45.
• 11: Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275503]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing xpath queries. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB 2002).
• 14: Gottlob, G., Koch, C., and Pichler, R. 2003. Xpath query evaluation: Improving time and space efficiency. In Proceedings of the 19th International Conference on Data Engineering (ICDE 2003).
• 15: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 16: Pekka Kilpelainen , Heikki Mannila, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing, v.24 n.2, p.340-356, April 1995 [doi>10.1137/S0097539791218202]
• 17: Kosaraju, S. R. 1989. Efficient tree pattern matching. In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 178--183.
• 18: 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
• 19: Neven, F., and Schwentick, T. 2003. Xpath containment in the presence of disjunction, dtds, and variables. In Proceedings of the 19th International Conference on Data Engineering (ICDE 2003).
• 20: Oded Shmueli, Equivalence of datalog queries is undecidable, Journal of Logic Programming, v.15 n.3, p.231-241, Feb. 1993 [doi>10.1016/0743-1066(93)90040-N]
• 21: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 22: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 23: Mikkel Thorup, Efficient preprocessing of simple binary pattern forests, Journal of Algorithms, v.20 n.3, p.602-612, May 1996 [doi>10.1006/jagm.1996.0029]
• 24: Vardi, M. 1997. Why is modal logic so robustly decidable. http://www.cs.rice.edu/∼vardi/papers/index.html.
• 25: 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]
• 26: Peter T. Wood, On the Equivalence of XML Patterns, Proceedings of the First International Conference on Computational Logic, p.1152-1166, July 01, 2000
• 27: Wood, P. T. 2001. Minimizing simple Xpath expressions. 4th International Workshop on the Web and Databases (WebDB'2001).
• 28: XSch 1999. XML Schema Part 1: Structures. http://www.w3.org/TR/1999/WD-xmlschema-1-19991217/. W3C Working Draft.
• 29: Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th Conference on Very Large Databases. Morgan-Kaufman, Los Altos, Calif.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

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

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

General Terms:
Algorithms, Languages, Theory

Keywords:
Tree pattern matching, XPath expressions, query containment, query equivalence