ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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 ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chan and Ooi 1995]
...
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper and Moerkotte 1990]
Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kilger and Morkotte 1994]
Christoph Kilger, Guido Moerkotte: Indexing Multiple Sets. VLDB 1994: 180-191 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knuth 1973]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kriegel 1984]
Hans-Peter Kriegel: Performance Comparison of Index Structures for Multi-Key Retrieval. SIGMOD Conference 1984: 186-196 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Maier and Stein 1986]
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sreenath and Seshadri 1994]
B. Sreenath, S. Seshadri: The hcC-tree: An Efficient Index Structure for Object Oriented Databases. VLDB 1994: 203-213 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez et al. 1986]
Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:34:25 2010 by Michael Ley (ley@uni-trier.de)