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

[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

[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

[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

[10]

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

[11]

...

[12]

...

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[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)

[21]

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

[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

[23]

...

[24]

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

[25]

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

[26]

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

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