329
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-article
      , ,
      Proceedings of the Fifth International Workshop on Database Programming Languages (DBPL-5)
      Database Programming Languages
      6-8 September 1995
      Bookmark

            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.

            Content

            Author and article information

            Contributors
            Conference
            September 1995
            September 1995
            : 1-13
            Affiliations
            [0001]Dept. WNI, University of Limburg

            B-3590 Diepenbeek, Belgium
            [0002]AT&T Bell Laboratories

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

            Bloomington, IN 47405-4101, USA
            Article
            10.14236/ewic/DBPL1995.12
            e5963926-a2fb-48b0-b9f8-1a0bd3a9487f
            © 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 (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/DBPL1995.12
            Self URI (journal page): https://ewic.bcs.org/
            Categories
            Electronic Workshops in Computing

            Applied computer science,Computer science,Security & Cryptology,Graphics & Multimedia design,General computer science,Human-computer-interaction

            Comments

            Comment on this article