Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/716

Title: Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions
Issue Date: 2001
Publisher: Elsevier
Citation: Theoretical Computer Science, 254(1-2). p. 363-377
Abstract: Paredaens and Van Gucht proved that the flat relational algebra has the same expressive power as the nested relational algebra, as far as queries over flat relations and with flat results are concerned. We provide a new, very direct proof of this fact using a simulation technique. Our technique is also applied to partially answer a question posed by Suciu and Paredaens regarding the complexity of evaluating powerset algebra expressions. Specifically, we show that when only unary flat relations are into play, any powerset algebra expression is either equivalent to a nested algebra expression, or its evaluation will produce intermediate results of exponential size.
URI: http://hdl.handle.net/1942/716
DOI: 10.1016/S0304-3975(99)00301-1
ISI #: 000167791900013
ISSN: 0304-3975
Category: A1
Type: Journal Contribution
Validation: ecoom, 2002
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A273.93 kBAdobe PDF

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