On the complexity of nonrecursive XQuery and functional query languages on complex values

ABSTRACT

This article studies the complexity of evaluating functional query languages for complex values such as monad algebra and the recursion-free fragment of XQuery. We show that monad algebra, with equality restricted to atomic values, is complete for the class TA[2^O(n), O(n)] of problems solvable in linear exponential time with a linear number of alternations if the query is assumed to be part of the input. The monotone fragment of monad algebra with atomic value equality but without negation is NEXPTIME-complete. For monad algebra with deep value equality, that is, equality of complex values, we establish TA[2^O(n), O(n)] lower and exponential-space upper bounds. We also study a fragment of XQuery, Core XQuery, that seems to incorporate all the features of a query language on complex values that are traditionally deemed essential. A close connection between monad algebra on lists and Core XQuery (with “child” as the only axis) is exhibited. The two languages are shown expressively equivalent up to representation issues. We show that Core XQuery is just as hard as monad algebra with respect to query and combined complexity. As Core XQuery is NEXPTIME-hard, the best-known techniques for processing such problems require exponential amounts of working memory and doubly exponential time in the worst case. We present a property of queries---the lack of a certain form of composition---that virtually all real-world XQueries have and that allows for query evaluation in PSPACE and thus singly exponential time. Still, we are able to show for an important special case---Core XQuery with equality testing restricted to atomic values---that the composition-free language is just as expressive as the language with composition. Thus, under widely-held complexity-theoretic assumptions, the language with composition is an exponentially more succinct version of the composition-free language.

REFERENCES

• 1: Serge Abiteboul , Catriel Beeri, The power of languages for the manipulation of complex values, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, p.727-794, October 1995 [doi>10.1007/BF01354881]
• 2: Serge Abiteboul , Gerd G. Hillebrand, Space Usage in Functional Query Languages, Proceedings of the 5th International Conference on Database Theory, p.439-454, January 11-13, 1995
• 3: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 4: David A. Mix-Barrington , Neil Immerman , Howard Straubing, On uniformity within NC1, Journal of Computer and System Sciences, v.41 n.3, p.274-306, Dec. 1990 [doi>10.1016/0022-0000(90)90022-D]
• 5: Benedikt, M. and Koch, C. 2006. Interpreting tree-to-tree queries. In Proc. ICALP.
• 6: Berman, L. 1980. The complexity of logical theories. Theor. Comput. Sci. 11, 216--224.
• 7: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 8: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 9: 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]
• 10: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 11: Stephen A. Cook , Pierre McKenzie, Problems complete for deterministic logarithmic space, Journal of Algorithms, v.8 n.5, p.385-394, Sept. 1987 [doi>10.1016/0196-6774(87)90018-6]
• 12: Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001 [doi>10.1145/502807.502810]
• 13: Evgeny Dantsin , Andrei Voronkov, Complexity of Query Answering in Logic Databases with Complex Values, Proceedings of the 4th International Symposium on Logical Foundations of Computer Science, p.56-66, July 06-12, 1997
• 14: Evgeny Dantsin , Andrei Voronkov, Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.157-165, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335218]
• 15: Mary F. Fernandez , Jérôme Siméon , Philip Wadler, An Algebra for XML Query, Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, p.11-45, December 13-15, 2000
• 16: Fernandez, M. F. and Siméon, J. 2004. Building an extensible XQuery engine: Experiences with Galax. (Extended Abstract). In Proceedings of XML Database Symposium (XSYM'04). Toronto, Canada, 1--4.
• 17: Ferrante, J. and Rackoff, C. 1975. A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4, 1, 69--76.
• 18: Florescu, D., Hillery, C., Kossmann, D., Lucas, P., Riccardi, F., Westmann, T., Carey, M. J., Sundararajan, A., and Agrawal, G. 2003. The BEA/XQRL streaming XQuery processor. In Proceedings of Very Large Data Bases. 997--1008.
• 19: 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]
• 20: Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
• 21: Stéphane Grumbach , Leonid Libkin , Tova Milo , Limsoon Wong, Query languages for bags: expressive power and complexity, ACM SIGACT News, v.27 n.2, p.30-44, June 1996 [doi>10.1145/235767.235770]
• 22: Stéphane Grumbach , Tova Milo, Towards tractable algebras for bags, Journal of Computer and System Sciences, v.52 n.3, p.570-588, June 1996 [doi>10.1006/jcss.1996.0042]
• 23: Stéphane Grumbach , Victor Vianu, Tractable query languages for complex object databases, Journal of Computer and System Sciences, v.51 n.2, p.149-167, Oct. 1995 [doi>10.1006/jcss.1995.1058]
• 24: Hartmanis, J., Lewis II, P. M., and Stearns, R. E. 1965. Hierarchies of memory limited computations. In Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logical Design. 179--190.
• 25: Hidders, J., Paredaens, J., Verkammen, R., and Demeyer, S. 2004. A light but formal introduction to XQuery. In Proceedings of XML Database Symposium (XSYM). 5--20.
• 26: Richard Hull , Jianwen Su, On accessing object-oriented databases: expressive power, complexity, and restrictions, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.147-158, June 1989, Portland, Oregon, United States
• 27: Richard Hull , Jianwen Su, Algebraic and calculus query languages for recursively typed complex objects, Journal of Computer and System Sciences, v.47 n.1, p.121-156, Aug. 1993
• 28: G. Jaeschke , H. J. Schek, Remarks on the algebra of non first normal form relations, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588133]
• 29: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 30: Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, 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.1065179]
• 31: Koch, C. 2005b. On the role of composition in XQuery. In Proceedings of WebDB. Baltimore, MD.
• 32: Koch, C., Scherzinger, S., Schweikardt, N., and Stegmaier, B. 2004. Schema-based scheduling of event processors and buffer minimization for queries on structured data streams. In Proceedings of the International Conference on Very Large Data Bases. Toronto, Canada.
• 33: Gabriel M. Kuper , Moshe Y. Vardi, On the complexity of queries in the logical data model, Theoretical Computer Science, v.116 n.1, p.33-57, Aug. 2, 1993
• 34: Gabriel M. Kuper , Moshe Y. Vardi, The logical data model, ACM Transactions on Database Systems (TODS), v.18 n.3, p.379-413, Sept. 1993 [doi>10.1145/155271.155274]
• 35: Leonid Libkin , Limsoon Wong, Query languages for bags and aggregate functions, Journal of Computer and System Sciences, v.55 n.2, p.241-272, Oct. 1997 [doi>10.1006/jcss.1997.1523]
• 36: Ludäscher, B., Mukhopadhyay, P., and Papakonstantinou, Y. 2002. A transducer-based XML query processor. In Proceedings of the International Conference on Very Large Data Bases. Hong Kong, China, 227--238.
• 37: Marian, A. and Siméon, J. 2003. Projecting XML documents. In Proceedings of the International Conference on Very Large Data Bases. 213--224.
• 38: Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley.
• 39: Jan Paredaens , Dirk Van Gucht, Possibilities and limitations of using flat operators in nested algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.29-38, March 1988, Austin, Texas, United States [doi>10.1145/308386.308402]
• 40: Stockmeyer, L. J. 1974. The complexity of decision problems in automata theory. Ph.D. thesis, Department of Electrical Engineering, MIT, Cambridge, MA.
• 41: Dan Suciu , Val Tannen, A query language for NC, Journal of Computer and System Sciences, v.55 n.2, p.299-321, Oct. 1997 [doi>10.1006/jcss.1997.1525]
• 42: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• 43: 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]
• 44: Sergei Vorobyov , Andrie Voronkov, Complexity of nonrecursive logic programs with complex values, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-253, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275515]
• 45: Voronkov, A. 2004. Personal communication.
• 46: Limsoon Wong, Normal forms and conservative extension properties for query languages over collection types, Journal of Computer and System Sciences, v.52 n.3, p.495-505, June 1996 [doi>10.1006/jcss.1996.0037]
• 47: World Wide Web Consortium. 2005. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Candidate Recommendation (Nov.). http://www.w3.org/TR/xquery-semantics/.
• 48: XQueryUseCases 2005. XML query use cases. W3C Working Draft (Sept.). http://www.w3.org/TR/xquery-use-cases/.

INDEX TERMS

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

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

General Terms:
Algorithms, Languages

Keywords:
Complex values, XML, XQuery, complexity, conservativity, expressiveness, monad algebra, nested-relational algebra