On the Complexity of Dealing with Inconsistency in Description Logic Ontologies
Riccardo Rosati
We study the problem of dealing with inconsistency in Description Logic (DL) ontologies. We consider inconsistency-tolerant semantics recently proposed in the literature, called AR-semantics and CAR-semantics, for which reasoning has been studied in the context of the Description Logics of the DL-Lite family. These inconsistency-tolerant semantics for DL ontologies are based repairing (i.e., modifying) in a minimal way the extensional knowledge (i.e., the ABox) while keeping the intensional knowledge (i.e., the TBox) untouched. We study the main forms of extensional reasoning in DL ontologies (instance checking and conjunctive query entailment) under the above inconsistency-tolerant semantics for a wide spectrum of DLs, ranging from tractable ones (EL) to very expressive ones (SHIQ). Our results show that reasoning under the above semantics is inherently intractable, even for very simple DLs. To the aim of overcoming such a high computational complexity of reasoning, we study sound approximations of both the above semantics. Surprisingly, our computational analysis shows that, differently from the logics of the DL-Lite family, reasoning under the approximated semantics is intractable even for tractable DLs. Finally, we identify suitable language restrictions of such DLs that allow for tractable reasoning under inconsistency-tolerant semantics.