The Partial Normalized Storage Model of Nested Relations.

@inproceedings{DBLP:conf/vldb/HafezO88,
  author    = {Aladdin Hafez and
               Gultekin {\"O}zsoyoglu},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {The Partial Normalized Storage Model of Nested Relations},
  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     = {100-111},
  ee        = {db/conf/vldb/HafezO88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper introduces the partial normalized storage model of nested relations which uses the workload information of the database system under consideration to obtain a "better" storage model (i.e., one with a lower query cost) for a given nested relation. Based on the normalized storage model, the nested relation scheme is graphically represented as a tree called the scheme tree. By using the workload information, and by performing a series of merges on the nodes of the scheme tree. a near-optimum scheme tree is produced to represent the partial normalized storage model.

We prove that our approach which uses the greedy method, locates the optimum scheme tree in most of the cases. In few cases, when the approach locates a "near" optimum scheme tree, the relative difference between the costs of the produced scheme tree and the optimum scheme tree is shown to be very small.

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

[AbiB84]

Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations to Represent Hierarchical Organized Data. PODS 1984: 191-200

[CDRS86]

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

[CopK85]

George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279

[Date87]

...

[DesV88]

Anand Deshpande, Dirk Van Gucht: An Implementation for Nested Relational Databases. VLDB 1988: 76-87

[DKAB86]

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

[HafO88]

...

[HamN78]

Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101

[HofS75]

Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86

[KCJB87]

Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez: A Query Processing Strategy for the Decomposed Storage Model. ICDE 1987: 636-643

[KiCB87]

Won Kim, Hong-Tai Chou, Jay Banerjee: Operations and Implementation of Complex Objects. ICDE 1987: 626-633

[McGe77]

...

[NCWJ84]

Shamkant B. Navathe, Stefano Ceri, Gio Wiederhold, Jinglie Dou: Vertical Partitioning Algorithms for Database Design. ACM Trans. Database Syst. 9(4): 680-710(1984)

[Olle71]

...

[RoTK82]

Doron Rotem, Frank Wm. Tompa, David G. Kirkpatrick: Foundations for Multifile Design by Application Partitioning. PODS 1982: 262-267

[StoR86]

Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355

[VaKC86]

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

[ValB86]

Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293

[vald87]

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

[Wied83]

...