+1 Recommend
1 collections
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

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

      , ,

      Proceedings of the Fifth International Workshop on Database Programming Languages (DBPL-5)

      Database Programming Languages

      6-8 September 1995

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          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.

          Related collections

          Author and article information

          September 1995
          September 1995
          : 1-13
          Dept. WNI, University of Limburg

          B-3590 Diepenbeek, Belgium
          AT&T Bell Laboratories

          Murray Hill, NJ 07974, USA
          Comp. Sci. Dept., Indiana University

          Bloomington, IN 47405-4101, USA
          © Marc Gyssens et al. Published by BCS Learning and Development Ltd. Proceedings of the Fifth International Workshop on Database Programming Languages, Gubbio, Umbria, Italy

          This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

          Proceedings of the Fifth International Workshop on Database Programming Languages
          Gubbio, Umbria, Italy
          6-8 September 1995
          Electronic Workshops in Computing (eWiC)
          Database Programming Languages
          Product Information: 1477-9358BCS Learning & Development
          Self URI (journal page): https://ewic.bcs.org/
          Electronic Workshops in Computing


          Comment on this article