logo ExceptionOWL

Nonmonotonic Extensions of Description Logics and OWL for defeasible inheritance with exceptions

by Gian Luca Pozzato

Introduction and main aim

The Semantic Web is as an extension of the World Wide Web (WWW) that allows computers or agents to manipulate, search, integrate Web contents referring to the meaning that such content has to human beings. To this aim, Semantic Web languages allow to express the semantics of data in a machine-understandable syntax by means of metadata. Ontologies, intended as descriptions of knowledge about a domain of interest for a specific application, have become a key concept for the Semantic Web technologies. One of the main limits of the existing languages for ontology engineering is that of not supporting the formalization of exceptions as well as related prototypical reasoning in taxonomies. The need of representing properties holding only for typical members of a given class, and not for all such members, emerges in several domain applications. This limit of the actually available formalisms for building ontologies is explained by the fact that the logical formalisms underlying these languages, known as the Description Logics, are monotonic.

Description Logics (for short, DLs) are reminiscent of the early semantic networks and of frame-based systems. They have found a great success in several applications, since they offer the following key advantages: (i) they have a well-defined semantics based on first-order logic; (ii) they offer a good trade-off between expressivity of the language and computational complexity (in fact, they correspond to decidable fragments of first-order logic); (iii) they have been successfully implemented by a range of efficient and provably correct reasoning tools, such as Pellet, FaCT++, and RACER. Thanks to the above properties, DLs have been used as the base of the languages of the Semantic Web such as the Web Ontology Language OWL. OWL is the ontology modeling language standardized by the World Wide Web Consortium. The OWL DL variant of OWL is the language usually adopted for practical applications in several research fields, just to mention a few: biology, medicine, geography, astronomy, agriculture, and defense.

According to the Description Logics, a knowledge base (KB) comprises two components: (i) a TBox, containing the definition of concepts (and possibly roles) and a specification of inclusion relations among them; (ii) an ABox, containing instances of concepts and roles, in other words, properties and relations of individuals. Since the primary objective of the TBox is to build a taxonomy of concepts, the need of representing prototypical properties and of reasoning about defeasible inheritance of such properties easily arises. Consider the following example about assuming folic acid during pregnancy in order to reduce neonatal mortality from neural tube disorders. Given a KB=(TBox,ABox), let TBox contain the following information (1) Woman ⊑ ¬FolicAcidSupplementation (2) Pregnant ⊑ Woman (3) Pregnant ⊑ FolicAcidSupplementation, representing that (1) women do not assume folic acid, whereas (2) pregnant ones are women that (3) assume it. Let the ABox contain the information that Kelly is a woman: from (1), it follows that Kelly does not assume folic acid. If one further discovers that Kelly is pregnant, and the ABox is extended accordingly, one should be able to retract the information previously inferred and conclude by (3) that Kelly assumes folic acid, according to specificity, i.e. the standard human practice of giving preference to the more specific information. The monotonicity of standard DLs avoids this kind of reasoning. Moreover, in standard DLs, the knowledge base of the example is consistent only if there are not pregnant women.

Recently, a renewed interest in the definition of nonmonotonic extensions of DLs has been spurred by the research in ontologies and Semantic Web. This extensive practical experience has confirmed the benefits of using DLs in knowledge representation, but it has also highlighted the mentioned limitations, and finding a suitable nonmonotonic extension for inheritance reasoning with exceptions seems far from being solved. The main aim of ExceptionOWL is to extend DLs and OWL in order to reason about defeasible inheritance with exceptions in ontologies, by proposing a new approach which is technically well-founded, motivated both from the knowledge representation and philosophy points of view, computationally effective and usable in the context of practical applications.

State of the art

Traditional approaches to handle defeasible inheritance in DLs are based on the integration of DLs with some kind of nonmonotonic reasoning mechanism. This has led to study nonmonotonic extensions of DLs. We briefly mention some of them, without being exhaustive. In [1] it is proposed the extension of DLs with Reiter’s default logic. Intuitively, a KB comprises, in addition to standard TBox and ABox, a finite set of default rules whose prerequisites, justifications, and consequents are concepts. Default rules are used in order to formalize prototypical properties. The same authors have pointed out that this integration may lead to both semantical and computational difficulties, both caused by an unsatisfactory treatment of open defaults treated via Skolemization, which is needed in order to capture some intuitive inferences. The treatment of open defaults via Skolemization may also lead to an undecidable default consequence relation, even if the underlying logic is decidable. For this reason, the same authors propose a restricted semantics for open default theories, in which default rules are only applied to individuals explicitly mentioned in the ABox. A more general approach is undertaken in [3], where DLs of minimal knowledge and negation as failure are proposed by augmenting DLs with two epistemic operators, K and A, interpreted according to Lifschitz’s nonmonotonic logic MKNF. This approach studies an extension of classic DLs allowing to capture Reiter’s default logic, integrity constraints, procedural rules as well as role and concept closure. However, the decision procedure presented for such extension uses triple exponential time in the size of the KB to solve reasoning problems. In [2] the authors propose an extension of DL with circumscription. The basic idea is to express inclusions like “normally, birds fly” with an inclusion Bird ⊑ Fly ⊔ Abnormal_Bird in the TBox, where the concept Abnormal_Bird is the predicate to be minimized. In other words, it is formalized that birds are either flying items or abnormal birds. The basic idea is to consider only those models where the extension of abnormality predicates is minimal with respect to set inclusion.

A simple but powerful nonmonotonic extension of DLs is proposed in [4], where it is introduced a nonmonotonic extension of DLs based both on the well-established Kraus, Lehmann and Magidor (for short: KLM)’s preferential semantics for nonmonotonic reasoning [6] and on a minimal model mechanism similar, in spirit, to circumscription. On the one hand, the semantics stemming from KLM provides a clear analysis of the concept of typicality. In this approach, “typical” or “normal” properties can be directly specified by means of a “typicality” operator T enriching the underlying DL; the typicality operator T, whose meaning is that, for any concept C, T(C) singles out the instances of C that are “typical”, is essentially characterized by the core properties of nonmonotonic reasoning, axiomatized by preferential logic P in [6]. On the other hand, the minimal model mechanism allows to perform useful nonmonotonic inferences. Similarly to other nonmonotonic DLs mentioned above, adding the typicality operator with its minimal model semantics leads to a very high complexity, more precisely query entailment in the resulting extension of basic Description L!ogic ALC by the operator T is in co-NexpNP.

Beyond the state of the art

In order to tackle the problem of high complexities of the approach based on the typicality operator, ExceptionOWL intends to explore an alternative, innovative strategy, based on the combination of the typicality operator T and the well established notion of rational closure provided by Lehmann and Magidor in [7]. Rational closure is a true nonmonotonic mechanism on the top of the KLM rational logic R, which, on the one hand preserves the properties of R, on the other hand it allows to perform some truthful nonmonotonic inferences. The rational closure construction amounts to assigning a rank (a level of exceptionality) to every concept. This rank is used to evaluate typical inclusions of the form T(C) ⊑ D: the inclusion is supported by the rational closure whenever the rank of C is strictly smaller than the rank of C ⊓ ¬D (C and not D). Preliminary results in this direction have been provided for the basic Description Logic ALC in [5], also tackling the problem of defining a notion of rational closure of the ABox. Good computational complexity properties of rational closure for propositional logic allow us to show that the proposed mechanism retains the same complexity of the underlying DL, namely that the problem of deciding whether a typical inclusion belongs to the rational closure of the TBox is in EXPTIME as well as those of deciding whether an assertion C(a) belongs to the rational closure of the ABox. In this respect, the proposed approach is less complex than the other above mentioned approaches to nonmonotonic reasoning in DLs and thus a good candidate to define computationally effective nonmonotonic extensions of DLs.


  1. Baader, F., Hollunder, B., 1995. Embedding defaults into terminological knowledge representation formalisms. Journal of Automated Reasoning (JAR) 14 (1), 149–180.
  2. Bonatti, P. A., Lutz, C., Wolter, F., 2009. The Complexity of Circumscription in DLs. Journal of Artificial Intelligence Research (JAIR) 35, 717–773.
  3. Donini, F. M., Nardi, D., Rosati, R., 2002. Description logics of minimal knowledge and negation as failure. ACM Transactions on Computational Logic (ToCL) 3 (2), 177–225.
  4. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G. L., 2013. A NonMonotonic Description Logic for Reasoning About Typicality. Artificial Intelligence 195, 165 – 202.
  5. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G. L., 2015. Semantic characterization of rational closure: From propositional logic to description logics. Artif. Intell. 226, 1-33.
  6. Kraus, S., Lehmann, D., Magidor, M., 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence 44 (1-2), 167–207.
  7. Lehmann, D., Magidor, M., 1992. What does a conditional knowledge base entail? Art. Intell. 55(1),1–60.