Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/631
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | NEVEN, Frank | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2005-03-09T15:27:58Z | - |
dc.date.available | 2005-03-09T15:27:58Z | - |
dc.date.issued | 1998 | - |
dc.identifier.citation | 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 | - |
dc.identifier.isbn | 0-89791-996-3 | - |
dc.identifier.uri | http://hdl.handle.net/1942/631 | - |
dc.description.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. | - |
dc.format.extent | 506425 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | ACM Press | - |
dc.title | Expressiveness of Structured Document Query Languages Based on Attribute Grammars | - |
dc.title.alternative | http://doi.acm.org/10.1145/505241.505245 | - |
dc.type | Proceedings Paper | - |
local.type.specified | Proceedings Paper | - |
dc.bibliographicCitation.oldjcat | - | |
item.accessRights | Closed Access | - |
item.contributor | NEVEN, Frank | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.fullcitation | NEVEN, Frank & VAN DEN BUSSCHE, Jan (1998) Expressiveness of Structured Document Query Languages Based on Attribute Grammars. In: 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. | - |
item.fulltext | With Fulltext | - |
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.