Expressiveness of Structured Document Query Languages Based on Attribute Grammars
Frank Neven, Jan Van den Bussche
Full Paper (PDF)

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.

References

References, where available, link to the DBLP on the World Wide Web.

[ACM93]
Serge Abiteboul, Sophie Cluet, Tova Milo: Querying and Updating the File. VLDB 1993: 73-84
[ACM95]
Serge Abiteboul, Sophie Cluet, Tova Milo: A Database Interface for File Updates. SIGMOD Conference 1995: 386-397
[BE97]
...
[CD88]
Bruno Courcelle, Pierre Deransart: Proofs of Partial Correctness for Attribute Grammars with Applications to Recursive Procedures and Logic Programming. Information and Computation 78(1): 1-55(1988)
[DJL88]
Pierre Deransart, Martin Jourdan, Bernard Lorho: Attribute Grammars: Definitions, Systems, and Bibliography. Springer 1988
[DM93]
...
[Don70]
John Doner: Tree Acceptors and Some of Their Applications. JCSS 4(5): 406-451(1970)
[EF95]
...
[End72]
...
[Gol95]
...
[GS84]
...
[GT87]
Gaston H. Gonnet, Frank Wm. Tompa: Mind Your Grammar: a New Approach to Modelling Text. VLDB 1987: 339-346
[Imm89]
Neil Immerman: Expressibility and Parallel Complexity. SIAM J. Comput. 18(3): 625-638(1989)
[Knu68]
Donald E. Knuth: Semantics of Context-Free Languages. Mathematical Systems Theory 2(2): 127-145(1968)
[Knu68a]
Donald E. Knuth: Correction: Semantics of Context-Free Languages. Mathematical Systems Theory 5(1): 95-96(1971)
[Knu82]
...
[Mos74]
...
[NVsB97]
Frank Neven, Jan Van den Bussche: On Implementing Structured Document Query Facilities on Top of a DOOD. DOOD 1997: 351-367
[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)
[Var89]
Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
[Woo95]
...
BIBTEX

@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-966-3},
pages = {11-17},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).