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 VAN DEN BUSSCHE, Jan |
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: | http://hdl.handle.net/1942/623 | Link to publication/dataset: | http://doi.acm.org/10.1145/505241.505245 | 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 | Size | Format | |
---|---|---|---|---|
21neven.pdf | 494.58 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
26
checked on Oct 14, 2024
Page view(s)
80
checked on Jun 28, 2023
Download(s)
322
checked on Jun 28, 2023
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.