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