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

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.

Contributors

Marc Gyssens

Dan Suciu

Dirk Van Gucht

Conference

Publication date: September 1995

Publication date (Print): September 1995

Pages: 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

DOI: 10.14236/ewic/DBPL1995.12

Copyright statement: © Marc Gyssens et al. Published by BCS Learning and Development Ltd. Proceedings of the Fifth International Workshop on Database Programming Languages, Gubbio, Umbria, Italy

License:

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/

Conference name: Proceedings of the Fifth International Workshop on Database Programming Languages

Conference acronym: DBPL-5

Conference number: 5

Conference location: Gubbio, Umbria, Italy

Conference date: 6-8 September 1995

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: 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

Series title: Electronic Workshops in Computing