Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions (Q5940927)
From MaRDI portal
scientific article; zbMATH DE number 1635078
Language | Label | Description | Also known as |
---|---|---|---|
English | Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions |
scientific article; zbMATH DE number 1635078 |
Statements
Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions (English)
0 references
20 August 2001
0 references
\textit{J. Paredaens} and \textit{D. Van Gucht} [Converting nested algebra expressions into flat algebra expressions, ACM Trans. Database Systems 17, No. 1, 65-93 (1992)] 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.
0 references
nested relational databases
0 references
query languages
0 references
expressive power
0 references