Index nesting - An efficient approach to indexing in object-oriented databases

Beng Chin Ooi, Jiawei Han, Hongjun Lu, Kian Lee Tan

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)215-228
Number of pages14
JournalVLDB Journal
Volume5
Issue number3
DOIs
StatePublished - Jan 1 1996
Externally publishedYes

Keywords

  • Indexing structures
  • OODB
  • Query retrieval

ASJC Scopus subject areas

  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Index nesting - An efficient approach to indexing in object-oriented databases'. Together they form a unique fingerprint.

  • Cite this