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

@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

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

...

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

[4]

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

[5]

...

[6]

...

[7]

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

[8]

Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) BibTeX

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

Referenced by

1. Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)
2. Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444
3. Michele Missikoff: A Domain Based Internal Schema for Relational Database Machines. SIGMOD Conference 1982: 215-224