Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/623

Title: Expressiveness of structured document query languages based on attribute grammars
Authors: NEVEN, Frank
Issue Date: 2002
Publisher: ACM Press New York, NY, USA
Citation: 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.
URI: http://hdl.handle.net/1942/623
Link to publication: http://doi.acm.org/10.1145/505241.505245
ISI #: 000175090500004
ISSN: 0004-5411
Category: A1
Type: Journal Contribution
Validation: ecoom, 2003
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A494.58 kBAdobe PDF

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