iO2 An Algorithmic Method for Building Inheritance Graphs in Object Database Design

摘要

This paper proposes a method, called iO2, for building the inheritance graph of an O2 database schema. TheiO2 method is based on the Galois lattice data structure. It encompasses three steps: a (first) construction step, a (second) optimization step, and a (final) generation step. This paper focuses on the two first steps. The construction step builds the Galois graph of the finite binary relation associating properties to entity and relationship types. A new algorithm is proposed for this first step. The optimization step builds the Galois inheritance graph from the Galois graph. A new algorithm is proposed for this second step in order to eliminate the redundancies. The generation step yields the 02 inheritance graph from the Galois inheritance graph. The transformation principles underlying this third step are given. The detailed generation algorithm is presented in [Yah96a].