ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Reduced Cover-Trees and their Application in the Sabre Access Path Model.

Kjell Karlsson: Reduced Cover-Trees and their Application in the Sabre Access Path Model. VLDB 1981: 345-353
@inproceedings{DBLP:conf/vldb/Karlsson81,
  author    = {Kjell Karlsson},
  title     = {Reduced Cover-Trees and their Application in the Sabre Access
               Path Model},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {345-353},
  ee        = {db/conf/vldb/Karlsson81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we define a tree-structure, the reduced cover-tree (RCT), for implementing both classical indexes and multi-attribute search structures and we outline its application in the data access model of the relational multi-processor data base machine SABRE. The kernel of this data access model is an RCT describing the placement of a relation that could be either a multi-attribute clustering scheme also used to - in some extent - substitute secondary indexes, or a non-dense unique key index. If the placement is achieved by multi-attribute clustering a unique key index can be nicely constructed with the same tree-structure. The RCT is represented by a bit-table in a most economic way and thus the number of accesses to memory when retrieval can be considerably cut down. On the average the memory occupation rate should turn about 75 per cent.

Key-words : Data base machine, access paths, multi- attribute clustering, primary index, secondary index, index selection, cover-tree, reduced cover-tree, tree-structure.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


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 ...

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
...
[3]
Jean Le Bihan, Christian Esculier, Gérard Le Lann, Witold Litwin, Georges Gardarin, S. Sedillort, L. Treille: SIRIUS: A French Nationwide Project on Distributed Data Bases. VLDB 1980: 75-85 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
...
[7]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
...
[10]
Henry D. Anderson, P. Bruce Berra: Minimum Cost Selection of Secondary Indexes for Formatted Files. ACM Trans. Database Syst. 2(1): 68-90(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:56 2010 by Michael Ley (ley@uni-trier.de)