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 SizeFormat 
Expressiveness.pdf494.56 kBAdobe PDFView/Open
Show full item record

Page view(s)

52
checked on May 21, 2022

Download(s)

98
checked on May 21, 2022

Google ScholarTM

Check

Altmetric


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