On the Feasibility of Implementing a Large Relational Data Base with Optimal Performance on a Mini-Computer.

@inproceedings{DBLP:conf/vldb/Manacher75,
  author    = {Glenn K. Manacher},
  editor    = {Douglas S. Kerr},
  title     = {On the Feasibility of Implementing a Large Relational Data Base
               with Optimal Performance on a Mini-Computer},
  booktitle = {Proceedings of the International Conference on Very Large Data
               Bases, September 22-24, 1975, Framingham, Massachusetts, USA},
  publisher = {ACM},
  year      = {1975},
  pages     = {175-201},
  ee        = {db/conf/vldb/Manacher75.html},
  crossref  = {DBLP:conf/vldb/75},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A less general model of Codd's relational model is proposed, for which queries and updates are maximally efficient. The differences in access methodfrom Codd's are minor enough so that almost all the compactness of expressionand quality of data independence remains.

The first new mechanism is an "algebra" of dependencies superimposed on the set of relations. These dependencies, called "subsumptions", permit the data base designer to impose a structure on the set of relations, thereby joining them together into a shape reflecting the overall organization of the data.

The second new mechanism is a new format in which fields are ordered, and lexical ordering of key values is enforced. It is shown that this format, used in conjunction with certain specific kinds of subsumptions, gives rise to a query sequence that is natural, linear, and intuitively related to access efficiency.

Finally, an alternative notion of "Normal form" is proposed for which the overhead for maintaining the form is truly minimal, and a set of efficient basic operations is proposed.

Copyright © 1975 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

• 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]

C. J. Date, P. Hopewell: Storage Structure and Physical Data Independence. SIGFIDET Workshop 1971: 139-168

[2]

Jürg Nievergelt: Binary Search Trees and File Organisation. ACM Comput. Surv. 6(3): 195-207(1974)

[3]

...

[4]

E. F. Codd: A Database Sublanguage Founded on the Relational Calculus. SIGFIDET Workshop 1971: 35-68

[5a]

...

[5b]

...

[6]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X

[7]

...

[8]

E. F. Codd: Normalized Data Structure: A Brief Tutorial. SIGFIDET Workshop 1971: 1-17

[9]

...

[10]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)

[11]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971)

[12]

...

[13]

E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972)

[14]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)

[15]

...

[16]

...

[17]

C. J. Date, E. F. Codd: The Relational and Network Approaches: Comparison of the Application Programming Interfaces. SIGMOD Workshop, Vol. 2 1974: 83-113

[18]

...

[19]

Donald E. Knuth: The Art of Computer Programming, Volume II: Seminumerical Algorithms. Addison-Wesley 1969

[20]

Daniel G. Bobrow: A Note on Hash Linking. Commun. ACM 18(7): 413-415(1975)

[21]

...

[22]

Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975)

[23]

...

[24]

...