An Approach to Subsumption in a DL with Implication

Papers Submitted to the Workshop

Designing a DL system poses the problem of the trade-off between power of expression and complexity. In spite of their rich expressive capacity, the or and not constructors are usually avoided because of the intractability of the resulting subsomption algorithm. So is implication. However, implication may constitute an interesting compromise between expressive power and tractability. We present an approach to the treatment of implication in the Osiris system, for mono-valued attributes with enumerated domains. It is based on the partitioning of each attribute’s domain by the predicates on this attribute, and it has been implemented in a prototype version of the Osiris system.