Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions

Citation
J. Van Den Bussche, Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions, THEOR COMP, 254(1-2), 2001, pp. 363-377
Citations number
17
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
254
Issue
1-2
Year of publication
2001
Pages
363 - 377
Database
ISI
SICI code
0304-3975(20010306)254:1-2<363:SOTNRA>2.0.ZU;2-P
Abstract
Paredaens and Van Gucht proved that the flat relational algebra has the sam e 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 a lso applied to partially answer a question posed by Suciu and Paredaens reg arding the complexity of evaluating powerset algebra expressions. Specifica lly, we show that when only unary fiat relations are into play, any powerse t algebra expression is either equivalent to a nested algebra expression, o r its evaluation will produce intermediate results of exponential size. (C) 2001 Elsevier Science B.V. All rights reserved.