An Implementation for Nested Relational Databases.

@inproceedings{DBLP:conf/vldb/DeshpandeG88,
  author    = {Anand Deshpande and
               Dirk Van Gucht},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {An Implementation for Nested Relational Databases},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {76-87},
  ee        = {db/conf/vldb/DeshpandeG88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We propose an architecture for implementing nested relational databases. In particular, we discuss the storage structures, their organization and an access language for specifying access plans.

The features of our implementation are:

• A notation for hierarchical tuple identification.
• One value-driven indexing structure (VALTREE) for the entire database.
• A main-memory based component (CACHE) for manipulating hierarchical tuple-identifiers.
• A hashing scheme (RECLISTs) for fast access to data specified by tuple-identifiers.
• An access language based on the VALTREE, the RECLIST and the CACHE to define access plans for execution of queries.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

...

[2]

François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162 BibTeX

[3]

...

[4]

...

[5]

...

[6]

Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 BibTeX

[7]

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

[8]

...

[9]

Umeshwar Dayal, Frank Manola, Alejandro P. Buchmann, Upen S. Chakravarthy, David Goldhirsch, Sandra Heiler, Jack A. Orenstein, Arnon Rosenthal: Simplifying Complex Objects: The PROBE Approach to Modelling and Querying Them. BTW 1987: 17-37 BibTeX

[10]

Uwe Deppisch, H.-Bernhard Paul, Hans-Jörg Schek: A Storage System for Complex Objects. OODBS 1986: 183-195 BibTeX

[11]

...

[12]

...

[13]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX

[14]

Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents BibTeX

[15]

Per-Åke Larson: Dynamic Hash Tables. Commun. ACM 31(4): 446-457(1988) BibTeX

[16]

Michele Missikoff: A Domain Based Internal Schema for Relational Database Machines. SIGMOD Conference 1982: 215-224 BibTeX

[17]

Michele Missikoff, Michel Scholl: Relational Queries in a Domain Based DBMS. SIGMOD Conference 1983: 219-227 BibTeX

[18]

Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38 BibTeX

[19]

Peter Pistor, F. Andersen: Designing A Generalized NF2 Model with an SQL-Type Language Interface. VLDB 1986: 278-285 BibTeX

[20]

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

[21]

Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396 BibTeX

[22]

Karen E. Smith, Stanley B. Zdonik: Intermedia: A Case Study of the Differences Between Relational and Object-Oriented Database Systems. OOPSLA 1987: 452-465 BibTeX

[23]

...

[24]

Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX

[25]

Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110 BibTeX

[26]

Gio Wiederhold: File Organisation for Database Design. McGraw-Hill Book Company 1987, ISBN 0-07-100340-1
BibTeX

Referenced by

1. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
   Contents
2. Nevzat Hurkan Balkir, Eser Sükan, Gultekin Özsoyoglu, Z. Meral Özsoyoglu: VISUAL: A Graphical Icon-Based Query Language. ICDE 1996: 524-533
3. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
4. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
5. Vinay Deshpande, Per-Åke Larson: The Design and Implementation of a Parallel Join Algorithm for Nested Relations on Shared-Memory Multiprocessors. ICDE 1992: 68-77
6. Won Kim: Object-Oriented Databases: Definition and Research Directions. IEEE Trans. Knowl. Data Eng. 2(3): 327-341(1990)
7. Won Kim: Research Directions in Object-Oriented Database Systems. PODS 1990: 1-15
8. Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
9. Won Kim: A Model of Queries for Object-Oriented Databases. VLDB 1989: 423-432
10. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
11. Aladdin Hafez, Gultekin Özsoyoglu: The Partial Normalized Storage Model of Nested Relations. VLDB 1988: 100-111