ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Recursive Algebra and Query Optimization for Nested Relations.

Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283
@inproceedings{DBLP:conf/sigmod/Colby89,
  author    = {Latha S. Colby},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {A Recursive Algebra and Query Optimization for Nested Relations},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {273-283},
  ee        = {http://doi.acm.org/10.1145/67544.66952, db/conf/sigmod/Colby89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library

References

[1]
Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations to Represent Hierarchical Organized Data. PODS 1984: 191-200 BibTeX
[2]
François Bancilhon, Philippe Richard, Michel Scholl: On Line Processing of Compacted Relations. VLDB 1982: 263-269 BibTeX
[3]
Nicole Bidoit: The Verso Algebra or How to Answer Queries with Fewer Joins. J. Comput. Syst. Sci. 35(3): 321-364(1987) BibTeX
[4]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[5]
...
[6]
Peter Dadam, Klaus Küspert, F. Andersen, Henk M. Blanken, R. Erbe, Jürgen Günauer, Vincent Y. Lum, Peter Pistor, Georg Walch: A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies. SIGMOD Conference 1986: 356-367 BibTeX
[7]
Uwe Deppisch, H.-Bernhard Paul, Hans-Jörg Schek: A Storage System for Complex Objects. OODBS 1986: 183-195 BibTeX
[8]
...
[9]
Anand Deshpande, Dirk Van Gucht: A Storage Structure for Unnormalized Relational Databases. BTW 1987: 481-486 BibTeX
[10]
Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra. SIGMOD Conference 1988: 225-232 BibTeX
[11]
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
[12]
Volker Linnemann: Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach. ICDE 1987: 591-598 BibTeX
[13]
Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX
[14]
Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX
[15]
H.-Bernhard Paul, Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum, Uwe Deppisch: Architecture and Implementation of the Darmstadt Database Kernel System. SIGMOD Conference 1987: 196-207 BibTeX
[16]
Peter Pistor, F. Andersen: Designing A Generalized NF2 Model with an SQL-Type Language Interface. VLDB 1986: 278-285 BibTeX
[17]
Peter Pistor, Roland Traunmüller: A database language for sets, lists and tables. Inf. Syst. 11(4): 323-336(1986) BibTeX
[18]
Mark A. Roth, Henry F. Korth, Don S. Batory: SQL/NF: a query language for ¬1 NF relational databases. Inf. Syst. 12(1): 99-114(1987) BibTeX
[19]
...
[20]
...
[21]
...
[22]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[23]
Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396 BibTeX
[24]
Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 BibTeX
[25]
Stan J. Thomas, Patrick C. Fischer: Nested Relational Structures. Advances in Computing Research 3: 269-307(1986) BibTeX
[26]
...
[27]
Dirk Van Gucht: On the Expressive Power of the Extended Relational Algebra for the Unnormalized Relational Model. PODS 1987: 302-312 BibTeX
[28]
Dirk Van Gucht, Patrick C. Fischer: Multilevel Nested Relational Structures. J. Comput. Syst. Sci. 36(1): 77-105(1988) BibTeX

Referenced by

  1. Reda Alhajj: A Model that Simplifies the Coding of a Group of Object-Oriented Complex Queries. ADBIS (Short Papers) 1999: 178-184
  2. Zahir Tari, John Stokes, Stefano Spaccapietra: Object Normal Forms and Dependency Constraints for Object-Oriented Schemata. ACM Trans. Database Syst. 22(4): 513-569(1997)
  3. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  4. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  5. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  6. Stanley Y. W. Su, Mingsen Guo, Herman Lam: Association Algebra: A Mathematical Foundation for Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 5(5): 775-798(1993)
  7. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
  8. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
  9. Z. Meral Özsoyoglu, Jian Wang: A Keying Method for a Nested Relational Database Management System. ICDE 1992: 438-446
  10. Jan Van den Bussche: Complex Object Multi-Level Fixpoint Queries. MFDBS 1991: 1-13
  11. Leonid Libkin: A Relational Algebra for Complex Objects Based on Partial Information. MFDBS 1991: 29-43
  12. Li Yu, Sylvia L. Osborn: An Evaluation Framework for Algebraic Object-Oriented Query Models. ICDE 1991: 670-677
  13. Mizuho Iwaihara, Tetsuya Furukawa, Yahiko Kambayashi: Navigation and Schema Transformations for Producing Nested Relations form Networks. ICDE 1991: 181-190
  14. Mingsen Guo, Stanley Y. W. Su, Herman Lam: An Association Algebra For Processing Object-Oriented Databases. ICDE 1991: 23-32
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:58 2009