ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Expressiveness of Structured Document Query Languages Based on Attribute Grammars.

Frank Neven, Jan Van den Bussche: Expressiveness of Structured Document Query Languages Based on Attribute Grammars. PODS 1998: 11-17
@inproceedings{DBLP:conf/pods/NevenB98,
  author    = {Frank Neven and
               Jan Van den Bussche},
  title     = {Expressiveness of Structured Document Query Languages Based on
               Attribute Grammars},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {11-17},
  ee        = {http://doi.acm.org/10.1145/275487.275489, db/conf/pods/NevenB98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. We finally show that RAGs are more powerful than monadic second-order logic for queries of any arity.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 943 KB]

References

[ACM93]
Serge Abiteboul, Sophie Cluet, Tova Milo: Querying and Updating the File. VLDB 1993: 73-84 BibTeX
[ACM95]
Serge Abiteboul, Sophie Cluet, Tova Milo: A Database Interface for File Updates. SIGMOD Conference 1995: 386-397 BibTeX
[BE97]
...
[CD88]
Bruno Courcelle, Pierre Deransart: Proofs of Partial Correctness for Attribute Grammars with Applications to Recursive Procedures and Logic Programming. Inf. Comput. 78(1): 1-55(1988) BibTeX
[DJL88]
Pierre Deransart, Martin Jourdan, Bernard Lorho: Attribute Grammars: Definitions, Systems, and Bibliography. Lecture Notes in Computer Science Vol. 323 Springer 1988, ISBN 3-540-50056-1
BibTeX
[DM93]
...
[Don70]
John Doner: Tree Acceptors and Some of Their Applications. J. Comput. Syst. Sci. 4(5): 406-451(1970) BibTeX
[EF95]
...
[End72]
...
[Gol95]
...
[GS84]
...
[GT87]
Gaston H. Gonnet, Frank Wm. Tompa: Mind Your Grammar: a New Approach to Modelling Text. VLDB 1987: 339-346 BibTeX
[Imm89]
Neil Immerman: Expressibility and Parallel Complexity. SIAM J. Comput. 18(3): 625-638(1989) BibTeX
[Knu68]
Donald E. Knuth: Semantics of Context-Free Languages. Mathematical Systems Theory 2(2): 127-145(1968) BibTeX
[Knu68a]
Donald E. Knuth: Correction: Semantics of Context-Free Languages. Mathematical Systems Theory 5(1): 95-96(1971) BibTeX
[Knu82]
...
[Mos74]
...
[NVsB97]
Frank Neven, Jan Van den Bussche: On Implementing Structured Document Query Facilities on Top of a DOOD. DOOD 1997: 351-367 BibTeX
[Tho97]
...
[TW68]
James W. Thatcher, Jesse B. Wright: Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic. Mathematical Systems Theory 2(1): 57-81(1968) BibTeX
[Var89]
Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92 BibTeX
[Woo95]
...

Referenced by

  1. Yannis Papakonstantinou, Victor Vianu: DTD Inference for Views of XML Data. PODS 2000: 35-46
  2. Frank Neven, Thomas Schwentick: Expressive and Efficient Pattern Languages for Tree-Structured Data. PODS 2000: 145-156
  3. Frank Neven, Thomas Schwentick: Query Automata. PODS 1999: 205-214
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:18 2009