Expressive and efficient pattern languages for tree-structured data (extended abstract)

ABSTRACT

It would be desirable to have a query language for tree-structured data that is (1) as easily usable as SQL, (2) as expressive as monadic second-order logic (MSO), and (3) efficiently evaluable. The paper develops some ideas in this direction. Towards (1) the specification of sets of vertices of a tree by combining conditions on their induced subtree with conditions on their path to the root is proposed. Existing query languages allow regular expressions (hence MSO logic) in path conditions but are limited in expressing subtree conditions. It is shown that such query languages fall short of capturing all MSO queries. On the other hand, allowing a certain guarded fragment of MSO-logic in the specification of subtree conditions results in a language fulfilling (2), (3) and, anguably, (1).

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 , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68-88, 1997.
• 4: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263676]
• 5: N. Alechina and N. Immerman. Efficient fragment of transitive closure logic. Unpublished, 1999.
• 6: H. Andr~ka, J. van Benthem, and I. N~meti. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27:217-274, 1998.
• 7: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 8: Peter Buneman , Wenfei Fan , Scott Weinstein, Path constraints on semistructured and structured data, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.129-138, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275502]
• 9: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 10: J. Clark. XSL transformations version 1.0. http://www.w3.org/TR/WD-xslt, august 1999.
• 11: 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
• 12: Alin Deutsch , Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for XML, Proceeding of the eighth international conference on World Wide Web, p.1155-1169, May 1999, Toronto, Canada
• 13: H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1995.
• 14: M. Fernandez, J. Simeon, and P. Wadler, editors. XML Query languages: Experiences and Exemplars, 1999. http://www-db.research.belll abs.com/user/simeon/xquery.html.
• 15: Mary Fernández , Daniela Florescu , Jaewoo Kang , Alon Levy , Dan Suciu, Catching the boat with Strudel: experiences with a Web-site management system, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.414-425, June 01-04, 1998, Seattle, Washington, United States
• 16: G. Gottlob, E. Gr~del, and H. Veith. Linear time datalog. Unpublished, 1999.
• 17: Nils Klarlund, Mona & Fido: The Logic-Automaton Connection in Practice, Selected Papers from the11th International Workshop on Computer Science Logic, p.311-326, August 23-29, 1997
• 18: S. Maneth and F. Neven. A formalization of tree transformations in XSL. In Proc. DBPL Conf., 1999.
• 19: Alberto O. Mendelzon , Peter T. Wood, Finding Regular Simple Paths in Graph Databases, SIAM Journal on Computing, v.24 n.6, p.1235-1258, Dec. 1995 [doi>10.1137/S009753979122370X]
• 20: F. Neven. Design and Analysis of Query Languages for Structured Documents A Formal and Logical Approach. Doctor's thesis, Limburgs Universitair Centrum (LUC), 1999.
• 21: Frank Neven, Extensions of Attribute Grammars for Structured Document Queries, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.99-116, September 01-03, 1999
• 22: 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]
• 23: Frank Neven , Jan Van den Bussche, Expressiveness of structured document query languages based on attribute grammars, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-17, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275489]
• 24: 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]
• 25: A. Potthoff. Logische Klassifizierung regul~rer Baumsprachen. Doctor's thesis, Institut fiir Informatik u. Prakt. Math., Universit~t Kiel, 1994.
• 26: J. Robie. The design of XQL. http://www, t excel, no / whit ep ap ers / xql- design, ht ml, 1999.
• 27: D. Suciu. Semistructured data and XML. In Proc. FODO Conf., 1998.
• 28: W. Thomas. Classifying regular events in symbolic logic. Journal of Computer and System Sciences, 25(3):360-376, 1982.
• 29: Wolfgang Thomas, Logical aspects in the study of tree languages, Proc. of the conference on Ninth colloquium on trees in algebra and programming, p.31-49, September 1984, Bordeaux, France
• 30: W. Thomas. On chain logic, path logic, and first-order logic over infinite trees. In Proc. LICS Conf., 1987.
• 31: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Languages