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 | Open Access | - |
item.fulltext | With Fulltext | - |
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.contributor | NEVEN, Frank | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Expressiveness.pdf | 494.56 kB | Adobe PDF | View/Open |
Page view(s)
86
checked on Nov 7, 2023
Download(s)
152
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.