H-trees: a dynamic associative search index for OODB

ABSTRACT

The support of the superclass-subclass concept in object-oriented databases (OODB) makes an instance of a subclass also an instance of its superclass. As a result, the access scope of a query against a class in general includes the access scope of all its subclasses, unless specified otherwise. To support the superclass-subclass relationship efficiently, the index must achieve two objectives. First, the index must support efficient retrieval of instances from a single class. Second, it must also support efficient retrieval of instances from classes in a hierarchy of classes. In this paper, we propose a new index called the H-tree that supports efficient retrieval of instances of a single class as well as retrieval of instances of a class and its subclasses. The unique feature of H-trees is that they capture the superclass-subclass relationships. A performance analysis is conducted and both experimental and analytical results indicate that the H-tree is an efficient indexing structure for OODB.

REFERENCES

• BeK89: E. Bertino , W. Kim, Indexing Techniques for Queries on Nested Objects, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.196-214, June 1989 [doi>10.1109/69.87960 ]
• CDR86: Michael J. Carey , David J. DeWitt , Joel E. Richardson , Eugene J. Shekita, Object and File Management in the EXODUS Extensible Database System, Proceedings of the 12th International Conference on Very Large Data Bases, p.91-100, August 25-28, 1986
• Com79: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• KeM90: Alfons Kemper , Guido Moerkotte, Access support in object bases, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.364-374, May 23-26, 1990, Atlantic City, New Jersey, United States
• KKD89: Won Kim , Kyung-Chang Kim , Alfred Dale, Indexing techniques for object-oriented databases, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989 [doi>10.1145/63320.66510]
• LLO91: C. C. Low, H. Lu, B. C. Ooi, J. Han: Efficient Access Methods in Deductive and Object-Oriented Databases. Proc. Intl. Conf. on Deductive and Object. Oriented Databases, Lecture Notes in Computer Science 566, 68-84 (1991).
• MeS86: David Maier , Jacob Stein, Indexing in an object-oriented DBMS, Proceedings on the 1986 international workshop on Object-oriented database systems, p.171-182, September 23-26, 1986, Pacific Grove, California, United States
• SuO82: P. Scheuermann, M. Ouksel: Multidimensional B. trees .for associative searching in database systems, information Systems, 7(2), 123-137 (1982).
• VKC86: Patrick Valduriez , Setrag Khoshafian , George P. Copeland, Implementation Techniques of Complex Objects, Proceedings of the 12th International Conference on Very Large Data Bases, p.101-110, August 25-28, 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Measurement, Performance, Theory