On the power of walking for querying tree-structured data

ABSTRACT

XSLT is the prime example of an XML query language based on tree-walking. Indeed, stripped down, XSLT is just a tree-walking tree-transducer equipped with registers and look-ahead. Motivated by this connection, we want to pinpoint the computational power of devices based on tree-walking. We show that in the absence of unique identifiers even very powerful extensions of the tree-walking paradigm are not relationally complete. That is, these extensions do not capture all of first-order logic. In contrast, when unique identifiers are available, we show that various restrictions allow to capture LOGSPACE, PTIME, PSPACE, and EXPTIME. These complexity classes are defined w.r.t. a Turing machine model working directly on (attributed) trees. When no attributes are present, relational storage does not add power; whether look-ahead adds power is related to the open question whether tree-walking captures the regular tree languages.

REFERENCES

• 1: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 2: Serge Abiteboul , Laurent Herr, Temportal connectives versus explicit timestamps to query temporal databases, Journal of Computer and System Sciences, v.58 n.1, p.54-68, Feb. 1999 [doi>10.1006/jcss.1998.1598]
• 3: A. V. Aho and J. D. Ullman. Translations on a context-free grammar. Information and Control, 19(5):439-475, 1971.
• 4: Geert Jan Bex , Sebastian Maneth , Frank Neven, A formal model for an expressive fragment of XSLT, Information Systems, v.27 n.1, p.21-39, March 2002 [doi>10.1016/S0306-4379(01)00033-3]
• 5: Roderick Bloem , Joost Engelfriet, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Journal of Computer and System Sciences, v.61 n.1, p.1-50, August.1.2000 [doi>10.1006/jcss.1999.1684]
• 6: Nicole Bidoit , Sandra De Amo, Implicit Temporal Query Languages: Towards Completeness, Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, p.245-257, December 13-15, 1999
• 7: A. Brüggemann-Klein and Derick Wood. Caterpillars: a context specification technique. Markup Languages, 2(1):81-106, 2000.
• 8: D. Chamberlin et al. XQuery 1.0: An XML Query Language. W3C Working Draft, June 2001. http://www.w3.org/TR/xquery/
• 9: J. Clark. XSL Transformations (XSLT) Version 1.0. W3C Recommendation, November 1999. http://www.w3.org/TR/xslt
• 10: J. Clark and S. DeRose. XML Path Language (XPath) Version 1.0 W3C Recommendation 16 November 1999 http://www.w3.org/TR/xpath
• 11: Pierre Deransart , Martin Jourdan , Bernard Lorho, Attribute grammars: definitions, systems and bibliography, Springer-Verlag New York, Inc., New York, NY, 1988
• 12: 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
• 13: Joost Engelfriet , Hendrik Jan Hoogeboom , Jan-Pascal Van Best, Trips on trees, Acta Cybernetica, v.14 n.1, p.51-64, Feb 1999
• 14: Erich Grädel , Yuri Gurevich, Metafinite model theory, Information and Computation, v.140 n.1, p.26-81, Jan. 10, 1998 [doi>10.1006/inco.1997.2675]
• 15: 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
• 16: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• 17: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 18: Frank Neven , Thomas Schwentick, Query automata, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303997]
• 19: Frank Neven , Thomas Schwentick, On the Power of Tree-Walking Automata, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.547-560, July 09-15, 2000
• 20: Frank Neven , Thomas Schwentick , Victor Vianu, Towards Regular Languages over Infinite Alphabets, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.560-572, August 27-31, 2001
• 21: 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]
• 22: I. H. Sudborough. On tape-bounded complexity classes and multihead finite automata. Journal of Computer and System Sciences, 10(1):62-76, 1975.
• 23: 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages, Performance, Theory