Digital Symposium Collection 2000

Query Automata Frank Neven and Thomas Schwentick   View Paper (PDF)   Return to Semistructured Data Abstract It is common to model structured document databases by context-free and extended context-free grammars. A crucial difference is that the derivation trees of the former are ranked, while those of the latter are not. A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an important role in the context of structured document databases. We want to understand how the natural and well-studied computation model of tree automata can be used to express such queries. We define a query automaton (QA) as a deterministic two-way finite automaton over trees that has the ability to select nodes depending on the state and the label at those nodes. We study QAs over ranked as well as over unranked trees. More precisely, we characterize the expressiveness of the different formalisms by linking them to monadic second-order logic, and we establish the complexity of their non-emptiness and equivalence problem. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Sophie Cluet , Tova Milo : A Logical View of Structured Files. VLDB Journal 7(2) : 96-114(1998) [2] ... [3] Ricardo A. Baeza-Yates , Gonzalo Navarro : Integrating Contents and Structure in Text Retrieval. SIGMOD Record 25(1) : 67-79(1996) [4] Catriel Beeri , Tova Milo : Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999 : 296-313 [5] ... [6] ... [7] ... [8] ... [9] ... [10] ... [11] Noa Globerman , David Harel : Complexity Results for Two-Way and Multi-Pebble Automata and their Logics. TCS 169(2) : 161-184(1996) [12] Gaston H. Gonnet , Frank Wm. Tompa : Mind Your Grammar: a New Approach to Modelling Text. VLDB 1987 : 339-346 [13] Marc Gyssens , Jan Paredaens , Dirk Van Gucht : A Grammar-Based Approach Towards Unifying Hierarchical Data Models. SIAM J. Comput. 23(6) : 1093-1137(1994) [14] ... [15] ... [16] Pekka Kilpeläinen , Heikki Mannila : Retrieval from Hierarchical Texts by Partial Patterns. SIGIR 1993 : 214-222 [17] Pekka Kilpeläinen , Heikki Mannila : Query Primitives for Tree-Structured Data. CPM 1994 : 213-225 [18] Etsuro Moriya : On Two-Way Tree Automata. IPL 50(3) : 117-121(1994) [19] ... [20] ... [21] Andreas Neumann , Helmut Seidl : Locating Matches of Tree Patterns in Forests. FSTTCS 1998 : 134-145 [22] ... [23] Frank Neven , Jan Van den Bussche : Expressiveness of Structured Document Query Languages Based on Attribute Grammars. PODS 1998 : 11-17 [24] C. Pair , A. Quere : Définition et Etude des Bilangages Réguliers. Information and Control 13(6) : 565-593(1968) [25] ... [26] Masako Takahashi : Generalizations of Regular Sets and Their Applicatin to a Study of Context-Free Languages. Information and Control 27(1) : 1-36(1975) [27] ... [28] ... [29] Moshe Y. Vardi : Automata Theory for Database Theoreticans. PODS 1989 : 83-92 [30] ... BIBTEX @inproceedings{DBLP:conf/pods/NevenS99,   author    = {Frank Neven and                 Thomas Schwentick},    title     = {Query Automata},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {205-214},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM