An Algorithm for Type Subsumption in Object-Oriented Databases

This paper addresses the problem of computing the subsumption relation between sentences of OOL, a language for type definition for Object-Oriented databases. The relation of subsumption holds between types if one is a refinement of the other. Subsumption is a form of deduction, referred to as Taxonomic Reasoning, which is receiving increasing attention by the AI community. In this paper, after a short overview of the OOL data model, an algorithm that computes subsumption is presented and its correctness and termination in O(n logn) time is proved.