A recursive algebra and query optimization for nested relations
- 1 June 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 18 (2), 273-283
- https://doi.org/10.1145/66926.66952
Abstract
The nested relational model provides a better way to represent complex objects than the (flat) relational model, by allowing relations to have relation-valued attributes. A recursive algebra for nested relations that allows tuples at all levels of nesting in a nested relation to be accessed and modified without any special navigational operators and without having to flatten the nested relation has been developed. In this algebra, the operators of the 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. In this paper, we show that queries are more efficient and succinct when expressed in the recursive algebra than in languages that require restructuring in order to access subrelations of relations. We also show that most of the query optimization techniques that have been developed for the relational algebra can be easily extended for the recursive algebra and that queries are more easily optimizable when expressed in the recursive algebra than when they are expressed in languages like the non-recursive algebra.Keywords
This publication has 13 references indexed in Scilit:
- The powerset algebra as a result of adding programming constructs to the nested relational algebraPublished by Association for Computing Machinery (ACM) ,1988
- SQL/NF: A query language for ¬1NF relational databasesInformation Systems, 1987
- The verso algebra or how to answer queries with fewer joinsJournal of Computer and System Sciences, 1987
- Extending relational algebra and relational calculus with set-valued attributes and aggregate functionsACM Transactions on Database Systems, 1987
- Architecture and implementation of the Darmstadt database kernel systemPublished by Association for Computing Machinery (ACM) ,1987
- A database language for sets, lists and tablesInformation Systems, 1986
- A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchiesPublished by Association for Computing Machinery (ACM) ,1986
- Non first normal form relations to represent hierarchically organized dataPublished by Association for Computing Machinery (ACM) ,1984
- Remarks on the algebra of non first normal form relationsPublished by Association for Computing Machinery (ACM) ,1982
- A relational model of data for large shared data banksCommunications of the ACM, 1970