A verification algorithm for inheritance hierarchies in object-oriented databases

An object-oriented database (OODB) schema is represented by a collection of types (or class definitions), each of which consists of a set of typed attributes. A schema is generally organised according to an inheritance hierarchy, where subtypes are defined incrementally with respect to their supertypes. Along this hierarchy, subtypes inherit the characteristics of the supertypes. Despite the great variety of proposals in the literature, it is widely recognised that, in presence of inheritance, the object-oriented data model should guarantee, at extensional level, the following properties: (i) substitutiuity of instances; (ii) set inchsion of extensions. The former property guarantees that whenever an object of a given type is required (e.g., as a parameter in a function call) any subtype object can be used instead, without causing a type-check error. The latter property assures that the extension of a subtype is always (i.e., in any legal database) included in the extension of its supertypes. An object-oriented data model that complies with the two above points guarantees several desirable properties for the database schemas such as, for example, absence of run-time type errors [8]. Substitutivity and set inclusion semantics are difficult to be enforced without introducing strong limitations on the model, such as avoiding multiple inheritance or full recursion in the structure of the types.