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
[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
- Yannis Papakonstantinou, Victor Vianu:
DTD Inference for Views of XML Data.
PODS 2000: 35-46
- Frank Neven, Thomas Schwentick:
Expressive and Efficient Pattern Languages for Tree-Structured Data.
PODS 2000: 145-156
- 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