ACM SIGMOD Anthology VLDB dblp.uni-trier.de

An Implementation of Impure Surrogates.

S. Misbah Deen: An Implementation of Impure Surrogates. VLDB 1982: 245-256
@inproceedings{DBLP:conf/vldb/Deen82,
  author    = {S. Misbah Deen},
  title     = {An Implementation of Impure Surrogates},
  booktitle = {Eigth International Conference on Very Large Data Bases, September
               8-10, 1982, Mexico City, Mexico, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1982},
  isbn      = {0-934613-14-1},
  pages     = {245-256},
  ee        = {db/conf/vldb/Deen82.html},
  crossref  = {DBLP:conf/vldb/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Surrogates or internal identifiers can be made to facilitate both fast access and storage in- dependence if they are implemented properly. Such an implementation is discussed here; it permits the tuplcs of a relation to be accessed very fast by primary key for both random and sequential search without retarding the per- formance of secondary keys. It employs a key compression and a hasiiing algorithm and attempts to place tuples on data pages in the primary key sequence. Subsequent updates are absorbed by a dynamic allocation of overflows. An indexing technique called a hash tree holds surrogates in primary key order, and facili- tates fast sequential access. The access speed remains high even at a 90% load factor, with- out being significantly affected by storage reorganisation resulting from the addition of new attributes, deletion of old attributes or change of data page sizes.

These techniques have been implemented in the PRECI database system at Aberdeen.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Eigth International Conference on Very Large Data Bases, September 8-10, 1982, Mexico City, Mexico, Proceedings. Morgan Kaufmann 1982, ISBN 0-934613-14-1
Contents BibTeX

References

[1]
...
[2]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[3]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[4]
Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX
[5-i]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[5-ii]
...
[6]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[7]
...
[8]
...
[9]
S. Misbah Deen, D. Nikodem, A. Vashishta: The Design of a Canonical Database System (PRECI). Comput. J. 24(3): 200-209(1981) BibTeX
[10]
...
[11]
David A. Bell, S. Misbah Deen: Key Space Compression and Hashing in PRECI. Comput. J. 25(4): 486-492(1982) BibTeX

Referenced by

  1. Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
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:45:16 2009