XPath satisfiability in the presence of DTDs

ABSTRACT

We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query p in an XPath fragment and a DTD D, whether or not there exists an XML document T such that T conforms to D and the answer of p on T is nonempty. We consider a variety of XPath fragments widely used in practice, and investigate the impact of different XPath operators on the satisfiability analysis. We first study the problem for negation-free XPath fragments with and without upward axes, recursion and data-value joins, identifying which factors lead to tractability and which to NP-completeness. We then turn to fragments with negation but without data values, establishing lower and upper bounds in the absence and in the presence of upward modalities and recursion. We show that with negation the complexity ranges from PSPACE to EXPTIME. Moreover, when both data values and negation are in place, we find that the complexity ranges from NEXPTIME to undecidable. Furthermore, we give a finer analysis of the problem for particular classes of DTDs, exploring the impact of various DTD constructs, identifying tractable cases, as well as providing the complexity in the query size alone. Finally, we investigate the problem for XPath fragments with sibling axes, exploring the impact of horizontal modalities on the satisfiability analysis.

REFERENCES

• 1: Afanasiev, L., Blackburn, P., Dimitriou, I., Gaiffe, B., Goris, E., Marx, M., and de Rijke, M. 2005. PDL for ordered trees. J. Non-Classical Logics 15, 115--135.
• 2: 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]
• 3: 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]
• 4: 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]
• 5: Börger, E., Grädel, E., and Gurevich, Y. 1997. The Classical Decision Problem. Springer-Verlag, New York.
• 6: Bray, T., Paoli, J., and Sperberg-McQueen, C. M. 1998. Extensible markup language (XML) 1.0. W3C Recommendation. http://www.w3.org/TR/REC-xml.
• 7: 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
• 8: Chamberlin, D., Boag, S., Fernández, M. F., Florescu, D., Robie, J., and Siméon, J. 2001. XQuery 1.0: An XML query language. W3C Working Draft.
• 9: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 10: Bogdan S Chlebus, Domino-tiling games, Journal of Computer and System Sciences, v.32 n.3, p.374-392, June 1986 [doi>10.1016/0022-0000(86)90036-X]
• 11: Clark, J., and DeRose, S. 1999. XML Path Language (XPath). W3C Recommendation.
• 12: Alin Deutsch , Val Tannen, XML Queries and constraints, containment and reformulation, Theoretical Computer Science, v.336 n.1, p.57-87, 25 May 2005 [doi>10.1016/j.tcs.2004.10.032]
• 13: 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]
• 14: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002 [doi>10.1145/567112.567117]
• 15: Geerts, F., and Fan, W. 2005. Satisfiability of XPath queries with sibling axes. In Proceedings of the 10th International Symposium on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 3774. Springer-Verlag, New York, 122--137.
• 16: 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]
• 17: Hidders, J. 2004. Satisfiability of XPath expressions. In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 2921. Springer-Verlag, New York, 21--36.
• 18: 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
• 19: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava , Keith Thompson, TAX: A Tree Algebra for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.149-164, September 08-10, 2001
• 20: Orna Kupferman , Nir Piterman , Moshe Y. Vardi, Extended Temporal Logic Revisited, Proceedings of the 12th International Conference on Concurrency Theory, p.519-535, August 20-25, 2001
• 21: 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
• 22: Wim Martens , Frank Neven, Frontiers of tractability for typechecking simple XML transformations, 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.1055563]
• 23: Wim Martens , Frank Neven, On the complexity of typechecking top-down XML transformations, Theoretical Computer Science, v.336 n.1, p.153-180, 25 May 2005 [doi>10.1016/j.tcs.2004.10.035]
• 24: Marx, M. 2004. XPath with conditional axis relations. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science, vol. 2992. Springer-Verlag, New York, 477--494.
• 25: Maarten Marx , Maarten de Rijke, Semantic characterizations of navigational XPath, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083792]
• 26: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 27: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, v.66 n.1, p.66-97, 01 February 2003 [doi>10.1016/S0022-0000(02)00030-2]
• 28: Makoto Murata, Extended path expressions of XML, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375569]
• 29: Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335217]
• 30: Neven, F., and Schwentick, T. 2006. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Meth. Comput. Sci. 2, 3, 1--30.
• 31: 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
• 32: Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, MA.
• 33: Stelios Paparizos , Yuqing Wu , Laks V. S. Lakshmanan , H. V. Jagadish, Tree logical classes for efficient evaluation of XQuery, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007579]
• 34: Stockmeyer, L. 1974. The complexity of decision problems in automata theory and logic. Tech. rep. MIT, Cambridge, MA.
• 35: Sur, G., Hammer, J., and Siméon, J. 2004. An XQuery-based language for processing updates in XML. In Proceedings of Workshop on Programming Language Technologies for XML (Plan-X). 40--53.
• 36: Thatcher, J., and Wright, J. 1968. Generalized finite automata with an application to a decision problem of second-order logic. Math. Syst. Theory 2, 57--82.
• 37: 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]
• 38: W3C. 2006. XML Path Language (XPath) 2.0. W3C Recommendation.
• 39: Wood, P. 2001. Minimising simple XPath expressions. In Proceedings of the 4th International Workshop on the Web and Databases (WebDB). 13--18.
• 40: 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

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

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

General Terms:
Algorithms, Languages, Theory

Keywords:
Containment, DTDs, Satisfiability, XML, XPath