www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
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
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.
URI: http://hdl.handle.net/1942/631
ISBN: 0-89791-996-3
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A494.56 kBAdobe PDF

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