Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/631
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNEVEN, Frank-
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2005-03-09T15:27:58Z-
dc.date.available2005-03-09T15:27:58Z-
dc.date.issued1998-
dc.identifier.citationPODS 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.isbn0-89791-996-3-
dc.identifier.urihttp://hdl.handle.net/1942/631-
dc.description.abstractStructured 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.extent506425 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherACM Press-
dc.titleExpressiveness of Structured Document Query Languages Based on Attribute Grammars-
dc.title.alternativehttp://doi.acm.org/10.1145/505241.505245-
dc.typeProceedings Paper-
local.type.specifiedProceedings Paper-
dc.bibliographicCitation.oldjcat-
item.accessRightsClosed Access-
item.contributorNEVEN, Frank-
item.contributorVAN DEN BUSSCHE, Jan-
item.fullcitationNEVEN, 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.fulltextWith Fulltext-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
Expressiveness.pdf494.56 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric


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