Merging inheritance hierarchies for database integration

Merging inheritance hierarchies with overlapping class extensions and types is an essential task in database design. In the context of view integration and schema integration for federated databases and multidatabases conflicting inheritance hierarchies have to be merged. Inheritance hierarchies often occur explicitly in object-oriented databases as well as implicitly in relational databases. Since a concept lattice can be regarded as an inheritance hierarchy we propose to apply the theory of concept analysis to the problem of merging inheritance hierarchies. After investigating the power and complexity of concept analysis algorithms we provide a new algorithm tailored to our problem. The new algorithm has polynomial complexity and helps to optimize the resulting hierarchy with respect to certain quality criteria, e.g. number of classes and null values. An example demonstrates the practicability of our approach to merge conflicting inheritance hierarchies.