Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    The Restricted and the Bounded Fixpoint Closures of the Nested Relational Algebra are Equivalent

    Database Programming Languages

    Italy. 6th - 8th September 1995


    M. Gyssens, D. Suciu & D. Van Gucht


    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, unfortunately, since it is only a conservative extension of the traditional, "flat" relational algebra, and thus can only express a small fraction of the polynomial-time queries.

    Therefore, it was proposed to extend the nested algebra with a least-fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed.

    Two polynomial-time restrictions of the least-fixpoint closure of the nested algebra were proposed: the restricted least-fixpoint closure (by Gyssens and Van Gucht) and the bounded fixpoint closure (by Suciu).

    Here, we prove that both restrictions are equivalent in expressive power.

    We also exhibit a proof technique, called type substitution, by which we reduce our result to its obvious counterpart in the "flat" relational model; thus emphasizing the inherent weakness of the nested algebra.


    PDF filePDF Version of this Paper (308kb)