Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/631
Title: | Expressiveness of Structured Document Query Languages Based on Attribute Grammars | Other Titles: | http://doi.acm.org/10.1145/505241.505245 | Authors: | NEVEN, Frank VAN DEN BUSSCHE, Jan |
Issue Date: | 1998 | Publisher: | ACM Press | Source: | PODS 1998. USA : Seattle, Washington, In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, p. 11-17. , ACM Press | 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. | Document URI: | http://hdl.handle.net/1942/631 | ISBN: | 0-89791-996-3 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Expressiveness.pdf | 494.56 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.