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.fulltextWith Fulltext-
item.contributorVAN DEN BUSSCHE, Jan-
item.contributorNEVEN, Frank-
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.accessRightsOpen Access-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
Expressiveness.pdf494.56 kBAdobe PDFView/Open
Show simple item record

Page view(s)

52
checked on Jul 1, 2022

Download(s)

108
checked on Jul 1, 2022

Google ScholarTM

Check

Altmetric


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