Please use this identifier to cite or link to this item:
Title: Expressiveness of structured document query languages based on attribute grammars
Authors: NEVEN, Frank 
Issue Date: 2002
Publisher: ACM Press New York, NY, USA
Source: JOURNAL OF THE ACM, 49(1). p. 56-100
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. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.
Document URI:
Link to publication:
ISSN: 0004-5411
e-ISSN: 1557-735X
ISI #: 000175090500004
Category: A1
Type: Journal Contribution
Validations: ecoom 2003
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
21neven.pdf494.58 kBAdobe PDFView/Open
Show full item record


checked on May 14, 2022

Page view(s)

checked on May 19, 2022


checked on May 19, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.