Blog
About

160
views
0
recommends
+1 Recommend
1 collections
    4
    shares
      • 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

      Bookmark
          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.

          Abstract

          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

          Contributors
          Conference
          September 1995
          September 1995
          : 1-13
          Affiliations
          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
          Article
          10.14236/ewic/DBPL1995.12
          © 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
          DBPL-5
          5
          Gubbio, Umbria, Italy
          6-8 September 1995
          Electronic Workshops in Computing (eWiC)
          Database Programming Languages
          Product
          Product Information: 1477-9358BCS Learning & Development
          Self URI (journal page): https://ewic.bcs.org/
          Categories
          Electronic Workshops in Computing

          Comments

          Comment on this article