Index Nesting - An Efficient Approach to Indexing in Object-Oriented Databases.

Beng Chin Ooi, Jiawei Han, Hongjun Lu, Kian-Lee Tan: Index Nesting - An Efficient Approach to Indexing in Object-Oriented Databases. VLDB J. 5(3): 215-228(1996)

@article{DBLP:journals/vldb/OoiHLT96,
  author    = {Beng Chin Ooi and
               Jiawei Han and
               Hongjun Lu and
               Kian-Lee Tan},
  title     = {Index Nesting - An Efficient Approach to Indexing in Object-Oriented
               Databases},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {3},
  year      = {1996},
  pages     = {215-228},
  ee        = {db/journals/vldb/OoiHLT96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In object-oriented database systems where the concept of the superclass-subclass is supported, an instance of a subclass is also an instance of its superclass. Consequently, the access scope of a query against a class in general includes the access scope of all its subclasses, unless specified otherwise. An index to support superclass-subclass relationship efficiently must provide efficient associative retrievals of objects from a single class or from several classes in a class hierarchy. This paper presents an efficient index called the hierarchical tree (the H-tree). For each class, an H-tree is maintained, allowing efficient search on a single class. These H-trees are appropriately linked to capture the superclass-subclass relationships, thus allowing efficient retrievals of instances from a class hierarchy. Both experimental and analytical results indicate that the H-tree is an efficient indexing structure.

Key Words

OODB, Indexing structures, Query Retrieval

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." 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/An4-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

References

[Bertino and Kim 1989]: Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
[Carey et al. 1986]: Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100
[Chan and Ooi 1995]: ...
[Comer 1979]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[Kemper and Moerkotte 1990]: Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
[Kilger and Morkotte 1994]: Christoph Kilger, Guido Moerkotte: Indexing Multiple Sets. VLDB 1994: 180-191
[Kim et al. 1989]: Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394
[Knuth 1973]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
[Kriegel 1984]: Hans-Peter Kriegel: Performance Comparison of Index Structures for Multi-Key Retrieval. SIGMOD Conference 1984: 186-196
[Low et al. 1992]: Chee Chin Low, Beng Chin Ooi, Hongjun Lu: H-trees: A Dynamic Associative Search Index for OODB. SIGMOD Conference 1992: 134-143
[Low et al. 1993]: Chee Chin Low, Hongjun Lu, Beng Chin Ooi, Jiawei Han: Efficient Access Methods in Deductive and Object-Oriented Databases. DOOD 1991: 68-84
[Maier and Stein 1986]: David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182
[Niu et al. 1994]: ...
[Scheuermann and Ouksel 1982]: Peter Scheuermann, Aris M. Ouksel: Multidimensional B-trees for associative searching in database systems. Inf. Syst. 7(2): 123-137(1982)
[Sreenath and Seshadri 1994]: B. Sreenath, S. Seshadri: The hcC-tree: An Efficient Index Structure for Object Oriented Databases. VLDB 1994: 203-213
[Valduriez et al. 1986]: Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110