A recursive algebra for nested relations
Information SystemsPublished 1 January 1990
Latha S. Colby
Citations81
SJR quartileQ1
SJR score0.89
SNIP1.96
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A recursive algebra for nested relations that allows relations to be accessed and modified at all levels without always having to flatten them is presented.
Abstract
The nested relational model provides a better representational model for complex objects than the (flat) relational model by allowing relations to have relation-valued attributes. A recursive algebra for nested relations that allows relations to be accessed and modified at all levels without always having to flatten them is presented in this paper. The operators of the classical nested relational algebra are extended with recursive definitions so that they can be applied not only to relations but also to subrelations of a relation. Queries are much more efficient and succinct when expressed in this algebra than in languages that require restructuring in order to access subrelations of relations. A sketch of a proof showing the equivalence of the expressive powers of the recursive algebra and the nested relational algebra is given.
Keywords
Computer Science
Communications of the ACMA relational model of data for large shared data banks
5,238 Citations1970E. F. Codd
A model based on n-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced and certain operations on relations are discussed and applied to the problems of redundancy and consistency in the user's model.
Communications of the ACMA relational model of data for large shared data banks
4,834 Citations1983E. F. Codd
Information SystemsThe relational model with relation-valued attributes
474 Citations1986Hans‐Jörg Schek, Marc H. Scholl
This paper allows the application of the basic relational operators to any relation-valued attribute within a relation, which leads to a (hierarchically) nested relational algebra.
Remarks on the algebra of non first normal form relations
355 Citations1982Gerhard Jaeschke, Hans‐Jörg Schek
An extension of the relational model is proposed consisting of Non First Normal Form (NF2) relations, enriched mainly by so called nest and unnest operations which transform between NF2 relations and the usual ones.
ACM Transactions on Database SystemsExtended algebra and calculus for nested relational databases
279 Citations1988Mark A. Roth, Herry F. Korth +1 more
This paper takes a first step towards unifying the various theories of ¬1NF databases by determining an appropriate model to couch their formalisms in and defining an extended relational calculus as the theoretical basis for their database query language.
ACM SIGMOD RecordA DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies
263 Citations1986Peter Dadam, K. Kuespert +3 more
ACM Transactions on Database SystemsExtending relational algebra and relational calculus with set-valued attributes and aggregate functions
226 Citations1987Gültekin Özsoyoğlu, Z. Meral Özsoyoğlu +1 more
This paper extends the relational algebra with three new operators, namely, pack, unpack, and aggregation-by-template, to manipulate set-valued attributes and to utilize aggregate functions.
A consideration on normal form of not-necessarily-normalized relation in the relational data model
200 Citations1977Akifumi Makinouchi
Non first normal form relations to represent hierarchically organized data
150 Citations1984Serge Abiteboul, Nicole Bidoít
A database model, namely, the Verso model, where data is organized in non 1NF relations, by using relation as underlying structure, to preserve some of the positive features of the relational model, for instance, a simple algebraic query language.
Information SystemsSQL/NF: A query language for ¬1NF relational databases
142 Citations1987Mark A. Roth, Henry F. Korth +1 more
This paper extends one of the most widely used relational query languages, SQL, to operate on non-first-normal-form relations, and includes all of the power of standard SQL as well as the ability to define nested relations in the data definition language and query these relations directly in the extended data manipulation language.
Architecture and implementation of the Darmstadt database kernel system
115 Citations1987H.-B. Paul, H.-J. Schek +1 more
The multi-layered architecture of the DArmStadt Data Base System (DASDBS) for advanced applications is introduced and a multi-level transaction methodology is applied.
ACM SIGMOD RecordA recursive algebra and query optimization for nested relations
100 Citations1989Latha S. Colby
Information SystemsA database language for sets, lists and tables
86 Citations1986Peter Pistor, R. Traunmueller
This paper describes a language interface for an extended NF2 model, i.e. a model which covers a much broader range of data structures than the original [17] NF’ model, and does not appropriately match further vital needs of new database applications.
On Line Processing of Compacted Relations
57 Citations1982François Bancilhon, Philippe Richard +1 more
In this paper the problem of satisfying the two seemingly contradictory requirements of finding an "optimal" compaction scheme and processing optimally compacted relations on the fly is addressed.
ACM SIGMOD RecordThe powerset algebra as a result of adding programming constructs to the nested relational algebra
48 Citations1988Marc Gyssens, Dirk Van Gucht
Very Large Data BasesSupporting Flat Relations by a Nested Relational Kernel
44 Citations1987Marc H. Scholl, H.-B. Paul +1 more
A more general two-level rolution: The authors' databsse kernel offer6 hierarchical clnsteriug expmwed as nested (NF2) relationa Flat relations, resulting from logical database d&n, are then mapped to thir internal kernel interface.
A storage system for complex objects
40 Citations1986Uwe Deppisch, H.-B. Paul +1 more
The main focus of this paper is the description of storage structures which allow to preserve this set orientation down to the page layer and the introduction of an address space for every internally stored object which - usually - can be obtained by two set oriented page requests.
Non first normal form relations and recursive queries: An SQL-based approach
39 Citations1987Volker Linnemann
It is shown by examples that this method can be used to formulate queries which are rather cumbersome if only flat relations are used, and provide a contribution to the problem of modelling complex data.
Journal of Computer and System SciencesMultilevel nested relational structures
34 Citations1988Dirk Van Gucht, Patrick C. Fischer
Algebraic characterizations are given for the classes of normalization-lossless relations, the nested flat relations (obtainable by applying NEST operations to a flat relation) and the permutable nested relations (the result is independent of the order of nesting).
On the expressive power of the extended relational algebra for the unnormalized relational model
32 Citations1987Dirk Van Gucht
The orlgmal relatIona database model proposed by Codd permltted complex structures to be entrles m a component of a tuple to be able to more falthfully model some database apphcatlons.