Inheritance is introduced in object-oriented systems to enhance code reuse and create more compact and readable software. Powerful object models adopt multiple inheritance, allowing a type (or class) definition to inherit from more than one supertype. Unfortunately, in applying this powerful modeling mechanism, inheritance conflicts may be generated, which arise when the same property or operation is defined in more than one supertype. Inheritance conflicts identification and resolution is the key issue of this article. In strongly typed object-oriented systems the resolution of inheritance conflicts depends on the compatibility of the types of the conflicting definitions. In case of incompatible types, a contradiction arises. This article focuses on object-oriented databases (ODBs), providing a method aimed at supporting the designer in the construction of correct ODB schemas. The first necessary condition for schema correctness is the absence of contradictions. A second cause of schema incorrectness is due to the presence of structurally recursive types that, when defined within certain hierarchical patterns, cause the nontermination of the inheritance process. In the article, after the formal definition of a correct schema, two graph-theoretic methods aimed at verifying ODB schema correctness are analyzed. Although the first method is intuitive but inefficient, the second allows schema correctness to be checked in polynomial time, in the size of the schema. The results of this study are included in the implementation of Mosaico, an environment for ODB application design.

In this paper we address the inheritance process in the context of strongly typed Object-oriented database (OODB) systems, allowing multiple inheritance and overriding. For such powerful systems, it is important to analyse the inheritance hierarchy to identify a number of significant properties. The first, schema consistency, is connected to the inheritance conflicts. In the presence of an unsolvable inheritance conflict there is a contradiction in the schema. The second property is related to the termination of the inheritance process. We expect that all the subtypes in the schema, if consistent, can be rewritten in expanded form, after inheritance, in a finite time. Schemas that guarantee these two formal properties will be referred to as correct schemas. In the paper a graph-theoretic method is provided, aimed at supporting the designer in checking the correctness and deriving the expanded form of a schema. Furthermore, from the analysis of the complexity of the inheritance process, a third formal property has been defined, concerning the degree of compactness achievable in a schema, by using inheritance hierarchies. In particular, a class of schemas has been defined, referred to as logarithmic schemas, whose expanded forms, after inheritance, become exponential in the size of the original schemas.