Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.4, pp.523-540 (December 1993)
Redundant Inheritance Detection
for Object-Oriented Database

Ding-An Chiang, Chi-Ming Chung and Ming-Chi Lee*
Department of Computer Science
Tamkang University
Taipei, Taiwan, R.O.C.
*Department of Electrical Engineering
ST. John's & ST. Mary's
Institute of Technology
Taipei, Taiwan, R.O.C.

Inheritance is the main theme of schema design for an object-oriented database. It contributes to good properties of modularity, reusability and incremental design. However, once and object-oriented database schema is inserted or deleted during the lifetime of a database, it is prone to lead to redundant inheritance (IS-A) relationships, which suffer from massive data redundancy and inconsistency. To ensure the consistency and nonredundancy of the OODB schema after every insertion or deletion, we propose a rapid detection method by mapping a class hierarchy to a transitive closure matrix in this paper. A faster algorithm for computing a transitive closure matrix with respect to a class hierarchy is presented to help to detect redundant inheritance. Its time complexity is O(kn). Also, an algorithm to eliminate redundant inheritance is proposed.

Keywords: redundant inheritance, class hierarchy, transitive closure matrix

Received July 31, 1993; revised October 23, 1993.
Communicated by Wei-Pang Yang.