The hcC-tree: An Efficient Index Structure for Object Oriented Databases.

B. Sreenath, S. Seshadri: The hcC-tree: An Efficient Index Structure for Object Oriented Databases. VLDB 1994: 203-213

@inproceedings{DBLP:conf/vldb/SreenathS94,
  author    = {B. Sreenath and
               S. Seshadri},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {The hcC-tree: An Efficient Index Structure for Object Oriented
               Databases},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {203-213},
  ee        = {db/conf/vldb/vldb94-203.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Object oriented database systems, in contrast to traditional relational database systems, allow the scope of a query against a class to be either the class itself or all classes in the class hierarchy rooted at the class. If object oriented databases have to achieve acceptable performance levels against such queries, we need indexes that support efficient retrieval of instances from a single class as well as from all the classes in a class hierarchy. In this paper, we propose a new index structure called hcC-tree (hierarchy class Chain tree) that supports both kinds of retrieval efficiently. Moreover, the update cost of the index structure is bounded by the height of the hcC-tree (which is usually never more than four). We have implemented hcC-trees along with H-trees and CH-trees (two other index structures that have been proposed in the literature) and report a detailed performance analysis of the three structures. The performance study reveals that hcC-trees perform much better than the other two structures under most circumstances. The balanced behaviour of hcC-tree under all kinds of queries and in the presence of updates shows that it is a promising index structure for the future.

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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

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/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents

References

[BK89]: Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
[Com79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[IKO93]: Yoshiharu Ishikawa, Hiroyuki Kitagawa, Nobuo Ohbo: Evaluation of Signature Files as Set Access Facilities in OODBs. SIGMOD Conference 1993: 247-256
[KKD89]: ...
[KM90]: Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
[LLOH91]: Chee Chin Low, Hongjun Lu, Beng Chin Ooi, Jiawei Han: Efficient Access Methods in Deductive and Object-Oriented Databases. DOOD 1991: 68-84
[LOL92]: Chee Chin Low, Beng Chin Ooi, Hongjun Lu: H-trees: A Dynamic Associative Search Index for OODB. SIGMOD Conference 1992: 134-143