Converting nested algebra expressions into flat algebra expressions

J. Paredaens, D. Van Gucht

Research output: Contribution to journalArticleAcademicpeer-review

50 Citations (Scopus)


Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its operation on flat relational databases. We show that the flat relational algebra is rich enough to extract the same "flat information" from a flat database as the nested algebra does. Theoretically, this result implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nested algebra. Practically, this result is relevant to (flat) relational query optimization.
Original languageEnglish
Pages (from-to)65-93
Number of pages29
JournalACM Transactions on Database Systems
Issue number1
Publication statusPublished - 1992


Dive into the research topics of 'Converting nested algebra expressions into flat algebra expressions'. Together they form a unique fingerprint.

Cite this