Expressive and Efficient Pattern Languages for Tree-Structured Data Frank Neven and Thomas Schwentick   View Paper (PDF)   Return to Semistructured Data 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, arguably, (1). References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Peter Buneman , Dan Suciu : Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann 1999, ISBN 1-55860-622-X [2] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [3] Serge Abiteboul , Dallan Quass , Jason McHugh , Jennifer Widom , Janet L. Wiener : The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1) : 68-88(1997) [4] Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133 [5] ... [6] ... [7] Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516 [8] Peter Buneman , Wenfei Fan , Scott Weinstein : Path Constraints in Semistructured and Structured Databases. PODS 1998 : 129-138 [9] Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Rewriting of Regular Expressions and Regular Path Queries. PODS 1999 : 194-204 [10] ... [11] Sophie Cluet , Claude Delobel , Jérôme Siméon , Katarzyna Smaga : Your Mediators Need Data Conversion! SIGMOD Conference 1998 : 177-188 [12] Alin Deutsch , Mary F. Fernandez , Daniela Florescu , Alon Y. Levy , Dan Suciu : A Query Language for XML. WWW8 / Computer Networks 31(11-16) : 1155-1169(1999) [13] ... [14] ... [15] Mary F. Fernandez , Daniela Florescu , Jaewoo Kang , Alon Y. Levy , Dan Suciu : Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998 : 414-425 [16] ... [17] Nils Klarlund : Mona & Fido: The Logic-Automaton Connection in Practice. CSL 1997 : 311-326 [18] ... [19] Alberto O. Mendelzon , Peter T. Wood : Finding Regular Simple Paths in Graph Databases. SIAM J. Comput. 24(6) : 1235-1258(1995) [20] ... [21] ... [22] Frank Neven , Thomas Schwentick : Query Automata. PODS 1999 : 205-214 [23] Frank Neven , Jan Van den Bussche : Expressiveness of Structured Document Query Languages Based on Attribute Grammars. PODS 1998 : 11-17 [24] Yannis Papakonstantinou , Victor Vianu : DTD Inference for Views of XML Data. PODS 2000 : 35-46 [25] ... [26] ... [27] Dan Suciu : Semistructured Data and XML. FODO 1998 : 0- [28] Wolfgang Thomas : Classifying Regular Events in Symbolic Logic. JCSS 25(3) : 360-376(1982) [29] Wolfgang Thomas : Logical Aspects in the Study of Tree Languages. CAAP 1984 : 31-50 [30] Wolfgang Thomas : On Chain Logic, Path Logic, and First-Order Logic over Infinite Trees. LICS 1987 : 245-256 [31] ... BIBTEX @inproceedings{DBLP:conf/pods/NevenS00,   author    = {Frank Neven and                 Thomas Schwentick},    title     = {Expressive and Efficient Pattern Languages for Tree-Structured                 Data},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {145-156},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.