The complexity of XPath query evaluation and XML typing

ABSTRACT

We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTIME in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, while the combined complexity is PTIME-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therefore, in the highly parallelizable complexity class NC². The second problem is the complexity of validating XML documents against various typing schemes like Document Type Definitions (DTDs), XML Schema Definitions (XSDs), and tree automata, both with respect to data and to combined complexity. For data complexity, we prove that validation is in LOGSPACE and depends crucially on how XML data is represented. For the combined complexity, we show that the complexity ranges from LOGSPACE to LOGCFL, depending on the typing scheme.

REFERENCES

• 1: Serge Abiteboul, Semistructured Data: From Practice to Theory, Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, p.379, June 16-19, 2001
• 2: Aho, A. V., and Ullman, J. D. 1971. Translations on a context-free grammar. Inf. Control 19, 439--475.
• 3: Allender, E. 2001. The division breakthroughs. The Computational Complexity Column, EATCS Bull. 74, 61--77.
• 4: David A. Mix Barrington , James Corbett, On the relative complexity of some languages in NC, Information Processing Letters, v.32 n.5, p.251-256, Sept. 22, 1989 [doi>10.1016/0020-0190(89)90052-5 ]
• 5: 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]
• 6: Catriel Beeri , Tova Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, Proceeding of the 7th International Conference on Database Theory, p.296-313, January 10-12, 1999
• 7: Bojanczyk, M., and Colcombet, T. 2004. TWA cannot be determinized. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP).
• 8: A. Borodin , S. A. Cook , P. W. Dymond , W. L. Ruzzo , M. Tompa, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, v.18 n.3, p.559-578, June 1989 [doi>10.1137/0218038]
• 9: 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. (Available at ftp://ftp11.informatik.tu-muenchen.de/pub/misc/caterpillars/.)
• 10: S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States [doi>10.1145/28395.28409]
• 11: Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
• 12: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• 13: Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M. 1999. Tree automata techniques and applications. Available at http://www.grappa.univ-lille3.fr/tata.
• 14: Stephen A. Cook , Pierre McKenzie, Problems complete for deterministic logarithmic space, Journal of Algorithms, v.8 n.5, p.385-394, Sept. 1987
• 15: Joost Engelfriet , Hendrik Jan Hoogeboom, Tree-Walking Pebble Automata, Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, p.72-83, January 1999
• 16: Joost Engelfriet , Hendrik Jan Hoogeboom , Jan-Pascal Van Best, Trips on trees, Acta Cybernetica, v.14 n.1, p.51-64, Feb 1999
• 17: Kousha Etessami, Counting quantifiers, successor relations, and logarithmic space, Journal of Computer and System Sciences, v.54 n.3, p.400-411, June 1997 [doi>10.1006/jcss.1997.1485 ]
• 18: 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'02). 95--106.
• 19: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 20: Gottlob, G., Koch, C., and Pichler, R. 2003b. XPath query evaluation: Improving time and space efficiency. In Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE'03). IEEE Computer Society Press, Los Alamitos, Calif., 379--390.
• 21: 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]
• 22: Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
• 23: Tao Jiang , B. Ravikumar, A note on the space complexity of some decision problems for finite automata, Information Processing Letters, v.40 n.1, p.25-31, Oct. 11, 1991 [doi>10.1016/S0020-0190(05)80006-7]
• 24: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 25: Jones, N. D. 1975. Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11, 68--85.
• 26: Steven Lindell, A logspace algorithm for tree canonization (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.400-404, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129750]
• 27: Markus Lohrey, On the Parallel Complexity of Tree Automata, Proceedings of the 12th International Conference on Rewriting Techniques and Applications, p.201-215, May 22-24, 2001
• 28: Lyons, R. 2001. Turing machine markup language. http://www.unidex.com/turing/.
• 29: Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
• 30: Frank Neven, Automata, Logic, and XML, Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, p.2-26, September 22-25, 2002
• 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 Mass.
• 33: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 34: Yannis Papakonstantinou , Victor Vianu, Incremental Validation of XML Documents, Proceedings of the 9th International Conference on Database Theory, p.47-63, January 08-10, 2003
• 35: Grzegorz Rozenberg , Arto Salomaa, Handbook of Formal Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 36: Ruzzo, W. 1980. Tree-size bounded alternation. J. Comput. Syst. Sci. 21, 218--235.
• 37: SAX Project Collaboration. 2004. Simple API for XML. Available at http://www.saxproject.org/.
• 38: Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773170]
• 39: 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]
• 40: Dan Suciu, Typechecking for Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.1-20, September 08-10, 2001
• 41: Sudborough, I. 1977. Time and tape bounded auxiliary pushdown automata. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science (MFCS'77). Lecture Notes in Computer Science, vol. 53. Springer-Verlag, New York, 493--503.
• 42: I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM (JACM), v.25 n.3, p.405-414, July 1978 [doi>10.1145/322077.322083]
• 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: 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]
• 45: Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 46: Wadler, P. 2000. Two semantics for XPath. Draft paper available at http://www.research.avayalabs.com/user/wadler/.
• 47: World Wide Web Consortium. 1999. XML path language (XPath) recommendation. http://www. w3c.org/TR/xpath/.
• 48: World Wide Web Consortium. 2004. Document object model. Available at http://www.w3c.org/dom, level 1 specification available at http://www.w3.org/TR/REC-DOM-Level-1/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

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

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

General Terms:
Algorithms, Languages, Theory

Keywords:
Complexity, DTD, LOGCFL, XML, XPath