Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra

摘要

The nested model is an extension of the traditional, " flat' relational model in which relations can also have relation-valued entries. Its " default' query language, the nested algebra, is rather weak, unfor- tunately, since it is only a conservative extension of the traditional, flat relational algebra, and thus can express only a small fraction of the poly- nomial-time queries. Therefore, it was proposed to extend the nested algebra with a fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed.