A KLM Perspective on Defeasible Reasoning for Description Logics

Abstract

In this paper we present an approach to defeasible reasoning for the description logic $\mathcal {ALC}$. The results discussed here are based on work done by Kraus, Lehmann and Magidor (KLM) on defeasible conditionals in the propositional case. We consider versions of a preferential semantics for two forms of defeasible subsumption, and link these semantic constructions formally to KLM-style syntactic properties via representation results. In addition to showing that the semantics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. With the semantics of the defeasible version of $\mathcal {ALC}$ in place, we turn to the investigation of an appropriate form of defeasible entailment for this enriched version of $\mathcal {ALC}$. This investigation includes an algorithm for the computation of a form of defeasible entailment known as rational closure in the propositional case. Importantly, the algorithm relies completely on classical entailment checks and shows that the computational complexity of reasoning over defeasible ontologies is no worse than that of the underlying classical $\mathcal {ALC}$. Before concluding, we take a brief tour of some existing work on defeasible extensions of $\mathcal {ALC}$ that go beyond defeasible subsumption.

1 Introduction

Description logics (DLs) [1] are central to many modern AI and database applications since they provide the logical foundation of formal ontologies. Yet, as classical formalisms, DLs do not allow for the proper representation of and reasoning with defeasible information, as shown up in the following example, adapted from Giordano et al. [39]: Students do not get tax invoices; employed students do; employed students who are also parents do not. From a naïve (classical) formalisation of this scenario, one concludes that the notion of employed student is an oxymoron, and consequently the concept of employed student is unsatisfiable. A more nuanced view is to represent such statements as defeasible.

Endowing DLs with defeasible reasoning features is therefore a promising endeavour from the point of view of applications of knowledge representation and reasoning. Indeed, the past 25 years have witnessed many attempts to introduce defeasible reasoning capabilities in a DL setting, usually drawing on a well-established body of research on non-monotonic reasoning (NMR). These comprise the so-called preferential approaches [19,20,21, 30, 32, 40, 44, 45, 57, 58, 63] and the circumscription-based ones [8, 9, 60], amongst others [7, 36, 46,47,48, 53, 56, 62]. Not surprisingly, Franz was among those who first made a meaningful contribution in this regard [2, 3].

Preferential extensions of DLs turn out to be particularly promising, mainly because they are based on an elegant, comprehensive and well-studied framework for non-monotonic reasoning in the propositional case proposed by Kraus, Lehmann and Magidor [49, 52], often referred to as the KLM approach. Such a framework is valuable for a number of reasons. First, it provides for a thorough analysis of some formal properties that any consequence relation deemed as appropriate in a non-monotonic setting ought to satisfy. Such formal properties play a central role in assessing how intuitive the obtained results are and enable a more comprehensive characterisation of the introduced non-monotonic conditional from a logical point of view. Second, the KLM approach allows for many decision problems to be reduced to classical entailment checking, sometimes without blowing up the computational complexity compared to the underlying classical case. Finally, it has a well-known connection with the AGM approach to belief revision [38, 59] and with frameworks for reasoning under uncertainty [6, 37]. It is therefore reasonable to expect that most, if not all, of the aforementioned features of the KLM approach should transfer to KLM-based extensions of DLs too.

Following the motivation laid out above, several extensions to the KLM approach to description logics have been proposed recently [19, 21, 23, 24, 27, 30, 32, 39, 40, 44, 45], each of them investigating particular constructions and variants of the preferential approach. Here we provide an overview of the formal foundations of preferential defeasible reasoning in DLs. By that we mean (i) providing a general and intuitive semantics; (ii) showing that the corresponding representation results (in the KLM sense of the term) hold, linking the semantic constructions to the KLM-style set of properties, and (iii) presenting an appropriate analysis of entailment in the context of ontologies with defeasible information with an associated decision procedure that is implementable.

After a brief introduction to the required background on the DL we consider here (in Sect. 2), we introduce the notion of defeasible subsumption along with a set of KLM-inspired properties it ought to satisfy (Sect. 3). In particular, using an intuitive semantics for the idea that “usually, an element of the class C is also an element of the class D”, we provide a characterisation (via representation results) of two important classes of defeasible statements, namely preferential and rational subsumption. In Sect. 4, we discuss two obvious candidates for the notion of entailment in the context of defeasible DLs, namely preferential and modular entailment. These turn out not to have all properties seen as important in a non-monotonic DL setting, mimicking a similar feature in the propositional case [52]. This is followed in Sect. 5 by the presentation of a version of rational entailment satisfying all the required properties, and which can thus be seen as a suitable candidate for defeasible entailment. In Sect. 6 we discuss aspects of defeasible reasoning going beyond defeasible concept inclusion. We conclude in Sect. 7 with some pointers to research following on from the work presented here, and remarks on future related endeavours.

The overview presented in this paper relies heavily on research conducted by the present authors, et al. [15].

2 Background

Description Logics (DLs) [1] are decidable fragments of first-order logic with interesting properties and a variety of applications. There is a whole family of description logics, an example of which is $\mathcal {ALC}$ and on which we shall focus in the present paper. The (concept) language of $\mathcal {ALC}$ is built upon a finite set of atomic concept names $\mathsf {C}$, a finite set of role names $\mathsf {R}$ and a finite set of individual names $\mathsf {I}$ such that $\mathsf {C}$, $\mathsf {R}$ and $\mathsf {I}$ are pairwise disjoint. With $A,B,\ldots$ we denote atomic concepts, with $r, s,\ldots$ role names, and with $a,b,\ldots$ individual names. Complex concepts are denoted with $C,D,\ldots$ and are built according to the following rule:

$$ C \mathrel {\mathop :}\mathrel {\mathop :}=\top \mid \bot \mid \mathsf {C}\mid \lnot C \mid C\sqcap C \mid C\sqcup C \mid \forall r.C \mid \exists r.C $$

With $\mathcal {L}$ we denote the language of all $\mathcal {ALC}$ concepts.

The semantics of $\mathcal {L}$ is the standard set theoretic Tarskian semantics. An interpretation is a structure $\mathcal {I}=_{\mathrm {def}}\langle \varDelta ^{\mathcal {I}},\cdot ^{\mathcal {I}} \rangle$, where $\varDelta ^{\mathcal {I}}$ is a non-empty set called the domain, and $\cdot ^{\mathcal {I}}$ is an interpretation function mapping concept names A to subsets $A^{\mathcal {I}}$ of $\varDelta ^{\mathcal {I}}$, role names r to binary relations $r^{\mathcal {I}}$ over $\varDelta ^{\mathcal {I}}$, and individual names a to elements of the domain $\varDelta ^{\mathcal {I}}$, i.e., $A^{\mathcal {I}}\subseteq \varDelta ^{\mathcal {I}}$, $r^{\mathcal {I}}\subseteq \varDelta ^{\mathcal {I}}\times \varDelta ^{\mathcal {I}}$, $a^{\mathcal {I}}\in \varDelta ^{\mathcal {I}}$. Define $r^{\mathcal {I}}(x) =_{\mathrm {def}}\{y \mid (x,y) \in r^{\mathcal {I}}\}$. We extend the interpretation function $\cdot ^{\mathcal {I}}$ to interpret complex concepts of $\mathcal {L}$ in the following way:

$$ \begin{array}{c} \top ^{\mathcal {I}}=_{\mathrm {def}}\varDelta ^{\mathcal {I}}, \ \bot ^{\mathcal {I}}=_{\mathrm {def}}\emptyset ,\ \ (\lnot C)^{\mathcal {I}}=_{\mathrm {def}}\varDelta ^{\mathcal {I}}\setminus C^{\mathcal {I}}\\ (C\sqcap D)^{\mathcal {I}}=_{\mathrm {def}}C^{\mathcal {I}}\cap D^{\mathcal {I}}, \ (C\sqcup D)^{\mathcal {I}}=_{\mathrm {def}}C^{\mathcal {I}}\cup D^{\mathcal {I}}\\ (\exists r.C)^{\mathcal {I}}=_{\mathrm {def}}\{ x\in \varDelta ^{\mathcal {I}} \mid r^{\mathcal {I}}(x)\cap C^{\mathcal {I}}\ne \emptyset \}, \ (\forall r.C)^{\mathcal {I}}=_{\mathrm {def}}\{ x\in \varDelta ^{\mathcal {I}} \mid r^{\mathcal {I}}(x)\subseteq C^{\mathcal {I}}\} \end{array} $$

Given $C, D\in \mathcal {L}$, $C\sqsubseteq D$ is called a subsumption statement, or general concept inclusion (GCI). $C\equiv D$ is an abbreviation for both $C\sqsubseteq D$ and $D\sqsubseteq C$. An $\mathcal {ALC}$ TBox $\mathcal {T}$ is a finite set of GCIs. We denote subsumption statements with $\alpha , \beta , \ldots$

An interpretation $\mathcal {I}$ satisfies a GCI $C\sqsubseteq D$ (denoted $\mathcal {I}\Vdash C\sqsubseteq D$) if $C^{\mathcal {I}}\subseteq D^{\mathcal {I}}$. An interpretation $\mathcal {I}$ is a model of a TBox TB (denoted $\mathcal {I}\Vdash \mathcal {T}$) if $\mathcal {I}\Vdash \alpha$ for every $\alpha \in \mathcal {T}$. A statement $\alpha$ is (classically) entailed by $\mathcal {T}$, denoted $\mathcal {T}\,\models \,\alpha$, if every model of $\mathcal {T}$ satisfies $\alpha$.

Given $C\in \mathcal {L}$, $r\in \mathsf {R}$ and $a,b\in \mathsf {I}$, an assertional statement (assertion, for short) is an expression of the form a : C or (a, b) : r. An $\mathcal {ALC}$ ABox $\mathcal {A}$ is a finite set of assertions. Given $\mathcal {T}$ and $\mathcal {A}$, with $\mathcal {KB}=_{\mathrm {def}}\mathcal {T}\cup \mathcal {A}$ we denote an $\mathcal {ALC}$ knowledge base, a.k.a. an ontology. This chapter focuses on defeasibility for description logic TBoxes only, and does not consider the extension to defeasible knowledge bases that include ABox statements. Various solutions for defeasible ABox reasoning have been proposed, that can be associated with the present approach for TBoxes [29, 30, 35, 45].

3 Defeasible Concept Inclusions

In a sense, class subsumption (alias concept inclusion) of the form $C\sqsubseteq D$ is the main notion in DL ontologies. Given its implication-like intuition, subsumption lends itself naturally to defeasibility: “provisionally, if an object falls under C, then it also falls under D”, as in “usually, students are tax exempted”. In this respect, a defeasible version of concept inclusion is the starting point for an investigation of defeasible reasoning in DL ontologies. We also address defeasibility of the entailment relation in later sections.

Definition 1

(Defeasible Concept Inclusion). Let $C,D\in \mathcal {L}$. A defeasible concept inclusion axiom (DCI, for short) is a statement of the form .

A DCI of the form is to be read as “usually, an instance of the class C is also an instance of the class D”. For instance, the DCI

formalises the example above. Paraphrasing Lehmann [50], the intuition of  is that “if C were all the information about an object available to an agent, then D would be a sensible conclusion to draw about such an object”. It is worth noting that , just as $\sqsubseteq$, is a ‘connective’ positioned between the concept language (object level) and the meta-language (that of entailment) and it is meant to be the defeasible counterpart of the classical subsumption $\sqsubseteq$.

Definition 2

(Defeasible TBox). A defeasible TBox (dTBox, for short) is a finite set of DCIs.

Given a TBox $\mathcal {T}$ and a dTBox $\mathcal {D}$, we let $\mathcal {KB}=_{\mathrm {def}}\mathcal {T}\cup \mathcal {D}$ and refer to it as a defeasible knowledge base (alias defeasible ontology).

Example 1

The following defeasible knowledge base gives a formal specification for our student scenario:

In the semantic construction later on, it will also be useful to be able to refer to infinite sets of concept inclusions. Let $\mathcal {KB}_{\text {inf}}$ therefore denote a defeasible theory, defined as a defeasible knowledge base but without the restriction on $\mathcal {T}$ and $\mathcal {D}$ to finite sets.

In order to assess the behaviour of the new connective and check it against both the intuition and the set of properties usually considered in a non-monotonic setting, it is convenient to look at a set of -statements as a binary relation of the ‘antecedent-consequent’ kind.

Definition 3

(Defeasible Subsumption Relation). A defeasible subsumption relation is a binary relation .

The idea is to mimic the analysis of defeasible entailment relations carried out by Kraus et al. [49] in the propositional case, where entailment is seen as a binary relation on the set in propositional sentences. Here we adopt the view of subsumption as a binary relation on concepts of our description language.

Sometimes (e.g. in the structural properties below) we write in the infix notation, i.e., as . The context will make clear when we will be talking about elements of a relation or statements (DCIs) in a defeasible knowledge base.

Definition 4

(Preferential Subsumption Relation). A defeasible subsumption relation  is a preferential subsumption relation if it satisfies the following set of properties, which we refer to as (the DL versions of the) preferential KLM properties:

The properties in Definition 4 result from a translation of those for preferential consequence relations proposed by Kraus et al. [49] in the propositional setting. They have been discussed at length in the literature for both the propositional and the DL cases [19, 21, 41, 42, 49, 52] and we shall not repeat so here.

If, in addition to the preferential properties above, the relation  also satisfies rational monotonicity (RM) below, then it is said to be a rational subsumption relation:

Rational monotonicity is often considered a desirable property to have, one of the reasons stemming from the fact that it is a necessary condition for the satisfaction of the principle of presumption of typicality (more on that in Sect. 4).

In what follows, we present a semantics for preferential and rational subsumption by enriching standard DL interpretations $\mathcal {I}$ with an ordering on the elements of the domain $\varDelta ^{\mathcal {I}}$. The intuition underlying this is simple and natural, and extends similar work in the propositional case by Shoham [61], Kraus et al. [49], Lehmann and Magidor [52] and Booth et al. [10,11,12] to the case for description logics. This is not the first extension of this kind, as evidenced by the work of Boutilier [14], Baltag and Smets [4, 5], Giordano et al. [39, 41,42,43,44,45], Britz et al. [17,18,19,20,21] and Britz and Varzinczak [22,23,24,25,26,27]. The present paper presents a cohesive semantic account of both preferential and rational subsumption, with accompanying representation results and computational characterisation based on the standard semantics for description logics.

Definition 5

(Preferential Interpretation). A preferential interpretation is a tuple $\mathcal {P}=_{\mathrm {def}}\langle \varDelta ^{\mathcal {P}},\cdot ^{\mathcal {P}},\prec ^{\mathcal {P}} \rangle$, where $\langle \varDelta ^{\mathcal {P}},\cdot ^{\mathcal {P}} \rangle$ is a (standard) DL interpretation (which we denote by $\mathcal {I}_{\mathcal {P}}$ and refer to as the classical interpretation associated with $\mathcal {P}$), and $\prec ^{\mathcal {P}}$ is a strict partial order on $\varDelta ^{\mathcal {P}}$ (i.e., $\prec ^{\mathcal {P}}$ is irreflexive and transitive) satisfying the smoothness condition (for every $C\in \mathcal {L}$, if $C^{\mathcal {P}}\ne \emptyset$, then $\min _{\prec ^{\mathcal {P}}}C^{\mathcal {P}}\ne \emptyset$).¹

Preferential interpretations provide us with a simple and intuitive way to give a semantics to DCIs.

Definition 6

(Satisfaction). Let $\mathcal {P}$ be a preferential interpretation and let $C,D\in \mathcal {L}$. The satisfaction relation $\Vdash$ is defined as follows:

• $\mathcal {P}\Vdash C\sqsubseteq D$ if $C^{\mathcal {P}}\subseteq D^{\mathcal {P}}$;

• if $\min _{\prec ^{\mathcal {P}}}C^{\mathcal {P}}\subseteq D^{\mathcal {P}}$.

If $\mathcal {P}\Vdash \alpha$, then we say $\mathcal {P}$ satisfies $\alpha$. $\mathcal {P}$ satisfies a defeasible knowledge base $\mathcal {KB}$, written $\mathcal {P}\Vdash \mathcal {KB}$, if $\mathcal {P}\Vdash \alpha$ for every $\alpha \in \mathcal {KB}$, in which case we say $\mathcal {P}$ is a preferential model of $\mathcal {KB}$. We say $C\in \mathcal {L}$ is satisfiable w.r.t. $\mathcal {KB}$ if there is a model $\mathcal {P}$ of $\mathcal {KB}$ s.t. $C^{\mathcal {P}}\ne \emptyset$.

It is easy to see that the addition of the $\prec ^{\mathcal {P}}$-component preserves the truth of all classical subsumption statements holding in the remaining structure:

Lemma 1

Let $\mathcal {P}$ be a preferential interpretation. For every $C,D\in \mathcal {L}$, $\mathcal {P}\Vdash C\sqsubseteq D$ if and only if $\mathcal {I}_{\mathcal {P}}\Vdash C\sqsubseteq D$.

It is worth noting that, due to the smoothness of $\prec ^{\mathcal {P}}$, every (classical) subsumption statement is equivalent, with respect to preferential interpretations, to some DCI.

Lemma 2

For every preferential interpretation $\mathcal {P}$, and every $C,D\in \mathcal {L}$, $\mathcal {P}\Vdash C\sqsubseteq D$ if and only if .

An obvious question that can now be raised is: “How do we know our preferential semantics provides an appropriate meaning to the notion of DCI?” The following definition will help us in answering this question:

Definition 7

( $\mathcal {P}$-Induced Defeasible Subsumption). Let $\mathcal {P}$ be a preferential interpretation. Then is the defeasible subsumption relation induced by $\mathcal {P}$.

The first important result we present here, which also answers the above raised question, shows that there is a full correspondence between the class of preferential subsumption relations and the class of defeasible subsumption relations induced by preferential interpretations. It is the DL analogue of a representation result proved by Kraus et al. for the propositional case [49, Theorem 3].

Theorem 1

(Representation Result for Preferential Subsumption). A defeasible subsumption relation is preferential if and only if there is a preferential interpretation $\mathcal {P}$ such that .

What is perhaps surprising about this result is that no additional properties based on the syntactic structure of the underlying DL are necessary to characterise the defeasible subsumption relations induced by preferential interpretations.

In addition to preferential interpretations, we are also interested in the study of modular interpretations, which are preferential interpretations in which the $\prec$-component is a modular ordering:

Definition 8

(Modular Order). Given a set X, $\prec \ \subseteq X\times X$ is modular if it is a strict partial order, and its associated incomparability relation $\sim$, defined by $x\sim y$ if neither $x\prec y$ nor $y\prec x$, is transitive.

Definition 9

(Modular Interpretation). A modular interpretation is a preferential interpretation $\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle$ such that $\prec ^{\mathcal {R}}$ is modular.

Intuitively, modular interpretations allow us to compare any two objects w.r.t. their plausibility. Those that are incomparable are viewed as being equally plausible. As such, modular interpretations are special cases of the preferential ones, where plausibility can be represented by any smooth strict partial order.

The main reason to consider modular interpretations is that they provide the semantic foundation of rational subsumption relations. This is made precise by our second important result below, which shows that the defeasible subsumption relations induced by modular interpretations are precisely the rational subsumption relations. Again, this is the DL analogue of a representation result proved by Lehmann and Magidor for the propositional case [52, Theorem 5].

Theorem 2

(Representation Result for Rational Subsumption). A defeasible subsumption relation is rational if and only if there is a modular interpretation $\mathcal {R}$ such that .

It is worth pausing for a moment to emphasise the significance of these two results (Theorems 1 and 2). They provide exact semantic characterisations of two important classes of defeasible subsumption relations, namely preferential and rational subsumption, in terms of the classes of preferential and modular interpretations, respectively. As we shall see in Sect. 4, these results form the core of the investigation into an appropriate form of entailment for defeasible DL ontologies.

4 Defeasible Entailment

From the standpoint of knowledge representation and reasoning, a pivotal question is that of deciding which statements are entailed by a knowledge base. In the present section we lay out the formal foundations for that.

4.1 Preferential Entailment

In the exploration of a notion of entailment for defeasible ontologies, an obvious starting point is to consider a Tarskian definition of consequence:

Definition 10

(Preferential Entailment). A statement $\alpha$ is preferentially entailed by a defeasible knowledge base $\mathcal {KB}$, written $\mathcal {KB}\,\models \,_{\mathsf {pref}}\alpha$, if every preferential model of $\mathcal {KB}$ satisfies $\alpha$.

As usual, this form of entailment is accompanied by a corresponding notion of closure.

Definition 11

(Preferential Closure). Let $\mathcal {KB}$ be a defeasible knowledge base. With $\mathcal {KB}^{*}_{\mathsf {pref}}=_{\mathrm {def}}\{\alpha \mid \mathcal {KB}\,\models \,_{\mathsf {pref}}\alpha \}$ we denote the preferential closure of $\mathcal {KB}$.

Intuitively, the preferential closure of a defeasible knowledge base $\mathcal {KB}$ corresponds to the ‘core’ set of statements, classical and defeasible, that should hold given those in $\mathcal {KB}$. Hence, preferential entailment and preferential closure are two sides of the same coin, mimicking an analogous result for preferential reasoning in both the propositional [49] and the DL [16, 21] cases.

Recall (cf. the discussion following Definition 2) that a defeasible theory $\mathcal {KB}_{\text {inf}}$ is a defeasible knowledge base without the restriction to finite sets. When assessing how appropriate a notion of entailment for defeasible ontologies is, the following definitions turn out to be useful, as will become clear in the sequel:

Definition 12

( $\mathcal {KB}_{\text {inf}}$-Induced Defeasible Subsumption). Let $\mathcal {KB}_{\text {inf}}$ be a defeasible theory. Then is the dTBox induced by $\mathcal {KB}_{\text {inf}}$ and is the defeasible subsumption relation induced by $\mathcal {KB}_{\text {inf}}$.

So, the dTBox induced by $\mathcal {KB}_{\text {inf}}$ is the set of defeasible subsumption statements contained in $\mathcal {KB}_{\text {inf}}$, together with the defeasible versions of the classical subsumption statements in $\mathcal {KB}_{\text {inf}}$. The defeasible subsumption relation induced by $\mathcal {KB}_{\text {inf}}$ is simply the defeasible subsumption relation corresponding to $\mathcal {D}_{\mathcal {KB}_{\text {inf}}}$.

Definition 13

A defeasible theory $\mathcal {KB}_{\text {inf}}$ is called preferential if the subsumption relation induced by it satisfies the preferential properties in Definition 4.

It turns out that the defeasible subsumption relation induced by the preferential closure of a defeasible knowledge base $\mathcal {KB}$ is exactly the intersection of the defeasible subsumption relations induced by the preferential defeasible theories containing $\mathcal {KB}$.

Lemma 3

Let $\mathcal {KB}$ be a defeasible knowledge base. Then

It follows immediately that the preferential closure of a defeasible knowledge base $\mathcal {KB}$ is preferential, and induces the smallest defeasible subsumption relation induced by a preferential defeasible theory containing $\mathcal {KB}$.

Preferential entailment is not always desirable, one of the reasons being that it is monotonic, courtesy of the Tarskian notion of consequence it relies on (see Definition 10). In most cases, as witnessed by the great deal of work in the non-monotonic reasoning community, a move towards rationality is in order. Thanks to the definitions above and the result in Theorem 2, we already know where to start looking for it.

Definition 14

(Modular Entailment). A statement $\alpha$ is modularly entailed by a defeasible knowledge base $\mathcal {KB}$, written $\mathcal {KB}\,\models \,_{\mathsf {mod}}\alpha$, if every modular model of $\mathcal {KB}$ satisfies $\alpha$.

As is the case for preferential entailment, modular entailment is accompanied by a corresponding notion of closure.

Definition 15

(Modular Closure). Let $\mathcal {KB}$ be a defeasible knowledge base. With $\mathcal {KB}^{*}_{\mathsf {mod}}=_{\mathrm {def}}\{\alpha \ \mid \ \mathcal {KB}\,\models \,_{\mathsf {mod}}\alpha \}$ we denote the modular closure of $\mathcal {KB}$.

Definition 16

A defeasible theory $\mathcal {KB}_{\text {inf}}$ is called rational if it is preferential and is also closed under the rational monotonicity rule (RM).

For modular closure we get a result similar to Lemma 3.

Lemma 4

Let $\mathcal {KB}$ be a defeasible knowledge base. Then

That is, the modular closure of a defeasible knowledge base $\mathcal {KB}$ induces the smallest defeasible subsumption relation induced by a rational defeasible theory containing $\mathcal {KB}$. However, the modular closure of $\mathcal {KB}$ is not necessarily rational. That is, if one looks at the set of statements (in particular the -ones) modularly entailed by a knowledge base as a defeasible subsumption relation, then it need not satisfy the RM property. This is so because modular entailment coincides with preferential entailment, as the following result, adapted from a well-known similar result in the propositional case [52, Theorem 4.2], shows.

Lemma 5

$\mathcal {KB}^{*}_{\mathsf {mod}}=\mathcal {KB}^{*}_{\mathsf {pref}}$.

Hence, modular entailment unfortunately falls short of providing us with an appropriate notion of defeasible entailment. In what follows, we overcome precisely this issue.

4.2 Rational Entailment

We now present a definition of semantic entailment which is appropriate in the light of the discussion above. The constructions we are going to present are inspired by the semantic characterisation of rational closure by Booth and Paris [13] in the propositional case.

We start by focusing our attention on a subclass of modular orders, referred to as ranked orders:

Definition 17

(Ranked Order). Given a set X, the binary relation $\prec \ \subseteq X\times X$ is a ranked order if there is a mapping $h_{\mathcal {R}}:X\longrightarrow \mathbb {N}$ satisfying the following convexity property:

• for every $i\in \mathbb {N}$, if for some $x\in X$ $h_{\mathcal {R}}(x)=i$, then, for every j such that $0\le j<i$, there is a $y\in X$ for which $h_{\mathcal {R}}(y)=j$,

and such that for every $x,y\in X$, $x\prec y$ iff $h_{\mathcal {R}}(x)<h_{\mathcal {R}}(y)$.

It is easy to see that a ranked order $\prec$ is also modular: $\prec$ is a strict partial order, and, since two objects x, y are incomparable (i.e., $x\sim y$) if and only if $h_{\mathcal {R}}(x)=h_{\mathcal {R}}(y)$, $\sim$ is a transitive relation. By constraining our preference relations to the ranked orders, we can identify a subset of the modular interpretations we refer to as the ranked interpretations.

Definition 18

(Ranked Interpretation). A ranked interpretation is a modular interpretation $\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle$ s.t. $\prec ^{\mathcal {R}}$ is a ranked order.

We now provide two basic results about ranked interpretations. First, all finite modular interpretations are ranked interpretations.

Lemma 6

A modular interpretation $\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle$ s.t. $\varDelta ^{\mathcal {R}}$ is finite is a ranked interpretation.

Next, for every ranked interpretation, the function $h_{\mathcal {R}}$ is unique.

Proposition 1

Given a ranked interpretation $\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle$, there is only one function $h_{\mathcal {R}}:\varDelta ^{\mathcal {R}}\longrightarrow \mathbb {N}$ satisfying the convexity property and s.t. for every $x,y\in \varDelta ^{\mathcal {R}}$, $x\prec y$ iff $h_{\mathcal {R}}(x)<h_{\mathcal {R}}(y)$.

Proposition 1 allows us to use the function $h_\mathcal {R}(\cdot )$ to define the notions of height and layers.

Definition 19

(Height and Layers). Let $\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle$ be a ranked interpretation with characteristic ranking function $h_{\mathcal {R}}(\cdot )$. Given an object $x\in \varDelta ^{\mathcal {R}}$, $h_{\mathcal {R}}(x)$ is called the height of x in $\mathcal {R}$. For every ranked interpretation $\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle$, we can partition the domain $\varDelta ^{\mathcal {R}}$ into a sequence of layers $(L_{0},\ldots ,L_{n},\ldots )$, where, for every object $x\in \varDelta ^{\mathcal {R}}$, we have $x\in L_{i}$ iff $h_{\mathcal {R}}(x)= i$.

Intuitively, the lower the height of an object in an interpretation $\mathcal {R}$, the more typical (or normal) the object is in $\mathcal {R}$. We can also think of a level of typicality for concepts: the height of a concept $C\in \mathcal {L}$ in $\mathcal {R}$ is the index of the layer to which the restriction of the concept’s extension to its $\prec ^{\mathcal {R}}$-minimal elements belong, i.e., $h_{\mathcal {R}}(C)=i$ if $\emptyset \subset \min _{\prec ^{\mathcal {R}}}C^{\mathcal {R}}\subseteq L_{i}$.

Given a set of ranked interpretations, we can introduce a new form of model merging, ranked union.

Definition 20

(Ranked Union). Given a countable set of ranked interpretations $\mathfrak {R}=\{\mathcal {R}_1,\mathcal {R}_2,\ldots \}$, a ranked interpretation $\mathcal {R}^{\mathfrak {R}}=_{\mathrm {def}}\langle \varDelta ^{\mathfrak {R}},\cdot ^{\mathfrak {R}},\prec ^{\mathfrak {R}} \rangle$ is the ranked union of $\mathfrak {R}$ if the following holds:

• $\varDelta ^{\mathfrak {R}}=_{\mathrm {def}}\coprod _{\mathcal {R}\in \mathfrak {R}}\varDelta ^{\mathcal {R}}$, i.e., the disjoint union of the domains from $\mathfrak {R}$, where each $\mathcal {R}\in \mathfrak {R}$ has the elements $x,y,\ldots$ of its domain renamed as $x_{\mathcal {R}}$, $y_{\mathcal {R}}$, ... so that they are all distinct in $\varDelta ^{\mathfrak {R}}$;

• $x_{\mathcal {R}}\in A^{\mathfrak {R}}$ iff $x\in A^{\mathcal {R}}$;

• $(x_{\mathcal {R}},y_{\mathcal {R}'})\in r^{\mathfrak {R}}$ iff $\mathcal {R}=\mathcal {R}'$ and $(x,y)\in r^{\mathcal {R}}$;

• for every $x_{\mathcal {R}}\in \varDelta ^{\mathfrak {R}}$, $h_{\mathfrak {R}}(x_{\mathcal {R}})=h_{\mathcal {R}}(x)$.

The latter condition corresponds to imposing that $x_{\mathcal {R}}\prec ^{\mathfrak {R}}y_{\mathcal {R}'}$ iff $h_{\mathcal {R}}(x)<h_{\mathcal {R}'}(y)$.

The following lemma will be useful in what follows.

Lemma 7

Ranked interpretations are closed under ranked union.

Let $\mathcal {KB}$ be a defeasible knowledge base and let $\varDelta$ be a fixed countably infinite set. Define

$$ \text { Mod}_{\varDelta }(\mathcal {KB}) =_{\mathrm {def}}\{\mathcal {R}=\langle \varDelta ^{\mathcal {R}},\cdot ^{\mathcal {R}},\prec ^{\mathcal {R}} \rangle \mid \mathcal {R}\Vdash \mathcal {KB}, \mathcal {R}\text { is ranked and } \varDelta ^{\mathcal {R}}=\varDelta \}. $$

The following result shows that the set $\text { Mod}_{\varDelta }(\mathcal {KB})$ suffices to characterise modular entailment:

Lemma 8

For every $\mathcal {KB}$ and every $C,D\in \mathcal {L}$, iff , for every $\mathcal {R}\in \text { Mod}_{\varDelta }(\mathcal {KB})$.

Therefore, we can use just the set of interpretations in $\text { Mod}_{\varDelta }(\mathcal {KB})$ to decide the consequences of $\mathcal {KB}$ w.r.t. modular entailment.

We can now use the set $\text { Mod}_{\varDelta }(\mathcal {KB})$ as a springboard to introduce what will turn out to be a canonical modular interpretation for $\mathcal {KB}$. Using $\text { Mod}_{\varDelta }(\mathcal {KB})$ and ranked union we can define the following relevant model.

Definition 21

(Big ranked model). Let $\mathcal {KB}$ be a defeasible knowledge base. The big ranked model of $\mathcal {KB}$ is the ranked model $\mathcal {O}=_{\mathrm {def}}\langle \varDelta ^{\mathcal {O}},\cdot ^{\mathcal {O}},\prec ^{\mathcal {O}} \rangle$ that is the ranked union of the models in $\text { Mod}_{\varDelta }(\mathcal {KB})$.

Since ranked interpretations are closed under ranked unions (Lemma 7), we can state the following:

Lemma 9

$\mathcal {O}$ is a ranked model of $\mathcal {KB}$.

Armed with the definitions and results above, we are now ready to provide an alternative definition of entailment in the context of defeasible ontologies:

Definition 22

(Rational Entailment). A statement $\alpha$ is rationally entailed by a knowledge base $\mathcal {KB}$, written $\mathcal {KB}\,\models \,_{\mathsf {rat}}\alpha$, if $\mathcal {O}\Vdash \alpha$.

That such a notion of entailment indeed deserves its name is witnessed by the following result, a consequence of Lemma 9 and Theorem 2:

Corollary 1

Let $\mathcal {KB}$ be a defeasible knowledge base and $\mathcal {O}$ its big ranked model. Then is rational.

We shall see below that this form of entailment corresponds to the DL version of a well-known form of propositional defeasible entailment [52].

In conclusion, rational entailment is a good candidate for the appropriate notion of consequence we have been looking for. Of course, a question that arises is whether a notion of closure, in the spirit of preferential and modular closures, that is equivalent to it can be defined. In the next section, we address precisely this matter.

5 Rational Closure for Defeasible Knowledge Bases

We now turn our attention to the exploration, in a DL setting, of the well-known notion of rational closure of a defeasible knowledge base as studied by Lehmann and Magidor [52]. For the most part, we shall base the presentation of the constructions on the work by Casini and Straccia [30, 32], amending it wherever necessary. An alternative semantic characterisation of rational closure in DLs has also been proposed by Giordano et al. [44, 45]; their characterisation and the one we present here are equivalent [35, Appendix A].

As we shall see, rational closure provides a proof-theoretic characterisation of rational entailment and the complexity of its computation is no higher than that of computing entailment in the underlying classical DL.

5.1 Rational Closure and a Correspondence Result

Rational closure is a form of inferential closure based on modular entailment $\,\models \,_{\mathsf {mod}}$, but it extends its inferential power. Such an extension of modular entailment is obtained by formalising the already mentioned principle of presumption of typicality [51, Section 3.1]. That is, under possibly incomplete information, we always assume that we are dealing with the most typical possible situation that is compatible with the information at our disposal. We first define what it means for a concept to be exceptional, a notion that, as we shall see, is central to the definition of rational closure:

Definition 23

(Exceptionality). Let $\mathcal {KB}$ be a defeasible knowledge base and $C\in \mathcal {L}$. We say C is exceptional in $\mathcal {KB}$ if . A DCI is exceptional in $\mathcal {KB}$ if C is exceptional in $\mathcal {KB}$.

A concept C is considered exceptional in a knowledge base $\mathcal {KB}$ if it is not possible to have a modular model of $\mathcal {KB}$ in which there is a typical object (i.e., an object at least as typical as all the others) that is in the interpretation of C. Intuitively, a DCI is exceptional if it does not concern the most typical objects, i.e., it is about less normal (or exceptional) ones. This is an intuitive translation of the notion of exceptionality used by Lehmann and Magidor [52] in the propositional framework, and has already been used by Casini and Straccia [30] and Giordano et al. [45] in their investigations into defeasible reasoning for DLs.

Applying the notion of exceptionality iteratively, we associate with every concept C a rank in $\mathcal {KB}$, which we denote by $\mathsf {rank}_{\mathcal {KB}}(C)$. We extend this to DCIs and associate with every statement a rank, denoted :

• 1. Let $\mathsf {rank}_{\mathcal {KB}}(C)=0$, if C is not exceptional in $\mathcal {KB}$, and let for every DCI having C as antecedent, with $\mathsf {rank}_{\mathcal {KB}}(C)=0$. The set of DCIs in $\mathcal {D}$ with rank 0 is denoted as $\mathcal {D}^\mathsf {rank}_{0}$.

• 2. Let $\mathsf {rank}_{\mathcal {KB}}(C)=1$, if C does not have a rank of 0 and it is not exceptional in the knowledge base $\mathcal {KB}^1$ composed of $\mathcal {T}$ and the exceptional part of $\mathcal {D}$, that is, $\mathcal {KB}^1=\langle \mathcal {T},\mathcal {D}\setminus \mathcal {D}^\mathsf {rank}_{0} \rangle$. If $\mathsf {rank}_{\mathcal {KB}}(C)=1$, then let for every DCI . The set of DCIs in $\mathcal {D}$ with rank 1 is denoted $\mathcal {D}^\mathsf {rank}_{1}$.

• 3. In general, for $i>0$, a concept C is assigned a rank of i if it does not have a rank of $i-1$ and it is not exceptional in $\mathcal {KB}^{i}=\langle \mathcal {T},\mathcal {D}\setminus \bigcup _{j=0}^{i-1}\mathcal {D}^{\mathsf {rank}}_{j} \rangle$. If $\mathsf {rank}_{\mathcal {KB}}(C)=i$, then , for every DCI . The set of DCIs in $\mathcal {D}$ with rank i is denoted $\mathcal {D}^{\mathsf {rank}}_{i}$.

• 4. By iterating the previous steps, we eventually reach a subset $\mathcal {E}\subseteq \mathcal {D}$ such that all the DCIs in $\mathcal {E}$ are exceptional (since $\mathcal {D}$ is finite, we must reach such a point). If $\mathcal {E}\ne \emptyset$, we define the rank of the DCIs in $\mathcal {E}$ as $\infty$, and the set $\mathcal {E}$ is denoted $\mathcal {D}^\mathsf {rank}_\infty$.

The notion of rank can also be extended to GCIs as follows: $\mathsf {rank}_{\mathcal {KB}}(C\sqsubseteq D) = \mathsf {rank}_{\mathcal {KB}}(C)$.

Following on the procedure above, $\mathcal {D}$ is partitioned into a finite sequence $\langle \mathcal {D}^{\mathsf {rank}}_{0},\ldots ,\mathcal {D}^{\mathsf {rank}}_{n},\mathcal {D}^{\mathsf {rank}}_{\infty } \rangle$ ($n\ge 0$), where $\mathcal {D}^{\mathsf {rank}}_{\infty }$ may possibly be empty. So, through this procedure we can assign a rank to every DCI.

It is easy to see that for a concept C to have a rank of $\infty$ corresponds to not being satisfiable in any model of $\mathcal {KB}$, that is, $\mathcal {KB}\,\models \,_{\mathsf {mod}} C\sqsubseteq \bot$.

Lemma 10

$\mathsf {rank}_{\mathcal {KB}}(C)=\infty$ iff $\mathcal {KB}\,\models \,_{\mathsf {mod}}C\sqsubseteq \bot$.

Example 2

Let $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$, where $\mathcal {T}$ and $\mathcal {D}$ are as in Example 1, i.e., $\mathcal {T}=\{\mathsf {EmpStud}\sqsubseteq \mathsf {Stud}\}$ and

Examining the concepts on the LHS of each DCI in $\mathcal {KB}$, one can verify that $\mathsf {Stud}$ is not exceptional w.r.t. $\mathcal {KB}$. Therefore, $\mathsf {rank}_{\mathcal {KB}}(\mathsf {Stud})=0$. We also find that $\mathsf {rank}_{\mathcal {KB}}(\mathsf {EmpStud})\ne {0}$ and $\mathsf {rank}_{\mathcal {KB}}(\mathsf {EmpStud}\sqcap \mathsf {Parent})\ne {0}$ because both concepts are exceptional w.r.t. $\mathcal {KB}$.

$\mathcal {KB}^{1}$ is composed of $\mathcal {T}$ and $\mathcal {D}\setminus \mathcal {D}^{\mathsf {rank}}_{0}$, which consists of the DCIs in $\mathcal {D}$ except for . We find that $\mathsf {EmpStud}$ is not exceptional w.r.t. $\mathcal {KB}^{1}$ and therefore $\mathsf {rank}_{\mathcal {KB}}(\mathsf {EmpStud})=1$. Since $\mathsf {EmpStud}\sqcap \mathsf {Parent}$ is exceptional w.r.t. $\mathcal {KB}^{1}$, $\mathsf {rank}_{\mathcal {KB}}(\mathsf {EmpStud}\sqcap \mathsf {Parent})\ne {1}$. Similarly, $\mathcal {KB}^{2}$ is composed of $\mathcal {T}$ and . We have that $\mathsf {EmpStud}\sqcap \mathsf {Parent}$ is not exceptional w.r.t. $\mathcal {KB}^{2}$ and therefore $\mathsf {rank}_{\mathcal {KB}}(\mathsf {EmpStud}\sqcap \mathsf {Parent})=2$.

Adapting Lehmann and Magidor’s construction for propositional logic [52], the rational closure of a defeasible knowledge base $\mathcal {KB}$ is defined as follows:

Definition 24

(Rational Closure). Let $\mathcal {KB}$ be a defeasible knowledge base and $C,D\in \mathcal {L}$.

• 1. is in the rational closure of $\mathcal {KB}$ if

  $$ \mathsf {rank}_{\mathcal {KB}}(C\sqcap D)<\mathsf {rank}_{\mathcal {KB}}(C\sqcap \lnot D) \text { or } \mathsf {rank}_{\mathcal {KB}}(C)=\infty . $$

• 2. $C\sqsubseteq D$ is in the rational closure of $\mathcal {KB}$ if $\mathsf {rank}_{\mathcal {KB}}(C\sqcap \lnot D)=\infty$.

Informally, the definition above says that the DCI is in the rational closure of $\mathcal {KB}$ if the modular models of $\mathcal {KB}$ tell us that some instances of $C\sqcap D$ are more plausible than all instances of $C\sqcap \lnot D$, while the GCI $C\sqsubseteq D$ is in the rational closure of $\mathcal {KB}$ if the instances of $C\sqcap \lnot D$ are impossible. The attentive reader will note that this definition has some similarity with the epistemic entrenchment orderings used in belief revision [38, 59].

Example 2 (continued). Applying the definition above to the knowledge base in Example 2, we can verify that is in the rational closure of $\mathcal {KB}$ because $\mathsf {rank}_{\mathcal {KB}}(\mathsf {Stud}\sqcap \lnot \exists \mathsf {receives}.\mathsf {TaxInv})=0$ and $\mathsf {rank}_{\mathcal {KB}}(\mathsf {Stud}\sqcap \exists \mathsf {receives}.\mathsf {TaxInv})>0$. The latter can be derived from the fact that $\mathsf {Stud}\sqcap \exists \mathsf {receives}.\mathsf {TaxInv}$ is exceptional w.r.t. $\mathcal {KB}$.

Similarly, one can derive that both DCIs and are in the rational closure of $\mathcal {KB}$ as well.

   $\square$

We now state the main result of the present section, which provides an answer to the question raised at the end of Sect. 4.2.

Theorem 3

Let $\mathcal {KB}$ be a defeasible knowledge base having a modular model. A statement $\alpha$ is in the rational closure of $\mathcal {KB}$ iff $\mathcal {KB}\,\models \,_{\mathsf {rat}}\alpha$.

An easy corollary of this result is that rational closure preserves the equivalence between GCIs (of the form $C\sqsubseteq D$) and their defeasible counterparts ().

Corollary 2

$C\sqsubseteq D$ is in the rational closure of a defeasible knowledge base $\mathcal {KB}$ iff is the restriction of the closure of $\mathcal {KB}$ under rational entailment to defeasible concept inclusions.

Rational entailment from a knowledge base can therefore be formulated as membership checking of the rational closure of the knowledge base. Of course, from an application-oriented point of view, this raises the question of how to compute membership of the rational closure of a knowledge base, and what is the complexity thereof. This is precisely the topic of the next section.

5.2 Rational Entailment Checking

We now present an algorithm to effectively check the rational entailment of a DCI from a defeasible knowledge base. Our algorithm is based on the one given by Casini and Straccia [30] for defeasible $\mathcal {ALC}$.

Let $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ be a defeasible knowledge base. The first step of the algorithm is to assign a rank to each DCI in $\mathcal {D}$. Central to this step is the exceptionality function $\mathsf {Exceptional}(\cdot )$, which computes the semantic notion of exceptionality of Definition 23. Given a set of DCIs $\mathcal {D}'\subseteq \mathcal {D}$, $\mathsf {Exceptional}(\mathcal {T},\mathcal {D}')$ returns a subset $\mathcal {E}$ of $\mathcal {D}'$ such that $\mathcal {E}$ is exceptional w.r.t. $\mathcal {T}\cup \mathcal {D}'$.

The function makes use of the notion of materialisation to reduce concept exceptionality checking to entailment checking:

Definition 25

(Materialisation). Let $\mathcal {D}$ be a set of DCIs. With we denote the materialisation of $\mathcal {D}$.

We can show that, given $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ and $\mathcal {D}'\subseteq \mathcal {D}$, if $\mathcal {T}\,\models \,\bigsqcap \overline{\mathcal {D}'}\sqsubseteq \lnot C$, a DCI is exceptional w.r.t. $\mathcal {T}\cup \mathcal {D}'$, thereby justifying the use of Line 3 of function Exceptional.

Lemma 11

For $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$, if $\mathcal {T}\,\models \,\bigsqcap \overline{\mathcal {D}}\sqsubseteq \lnot C$ then is exceptional w.r.t. $\mathcal {T}\cup \mathcal {D}$.

While the converse of Lemma 11 does not hold, it follows from Lemma 13 below that this reduction to classical entailment checking, when applied iteratively (lines 4–14 in function ComputeRanking below), fully captures the semantic notion of exceptionality of Definition 23.

Example 2 (continued). If we feed the knowledge base in Example 2 to the function $\mathsf {Exceptional}(\cdot )$, we obtain the output

This is because both concepts on the LHS of the DCIs in $\mathcal {D}'$ are exceptional w.r.t. $\mathcal {KB}$ in Example 2.

We now describe the overall ranking algorithm, presented in the function $\mathsf {ComputeRanking}(\cdot )$ below. The algorithm makes a finite sequence of calls to the function $\mathsf {Exceptional}(\cdot )$, starting from the knowledge base $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$. The algorithm terminates with a partitioning of the axioms in the dTBox, from which a ranking of axioms can easily be obtained.

We initialise $\mathcal {T}^{*}$ to $\mathcal {T}$ and $\mathcal {D}^{*}$ to $\mathcal {D}$ (Lines 1 and 2 of $\mathsf {ComputeRanking}$). We then repeatedly invoke the function $\mathsf {Exceptional}$ to obtain a sequence of sets of DCIs $\mathcal {E}_{0},\mathcal {E}_{1},\ldots$, where $\mathcal {E}_{0}=\mathcal {D}^{*}$ and each $\mathcal {E}_{i+1}$ is the set of exceptional axioms in $\mathcal {E}_{i}$ (Lines 4–14 of $\mathsf {ComputeRanking}(\cdot )$).

Now, let , i.e., $\mathcal {C}_{\mathcal {D}^{*}}$ is the set of all antecedents of DCIs in $\mathcal {D}^{*}$. The exceptionality ranking of the DCIs in $\mathcal {D}^{*}$ computed by $\mathsf {Exceptional}(\cdot )$ makes use of $\mathcal {T}^{*}$, $\overline{\mathcal {D}^{*}}$, and $\mathcal {C}_{\mathcal {D}^{*}}$. That is, it checks, for each concept $C\in \mathcal {C}_{\mathcal {D}^{*}}$, whether $\mathcal {T}^{*}\,\models \,\bigsqcap \overline{\mathcal {D}^{*}}\sqsubseteq \lnot C$. In case C is exceptional, every DCI is exceptional w.r.t. $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$ and is added to the set $\mathcal {E}_{1}$.

If $\mathcal {E}_{1}\ne \mathcal {E}_{0}$, then we call $\mathsf {Exceptional}(\cdot )$ for $\mathcal {T}^{*}\cup \mathcal {E}_{1}$, defining the set $\mathcal {E}_{2}$, and so on. Hence, given $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$, we construct a sequence $\mathcal {E}_{0},\mathcal {E}_{1},\ldots$ in the following way, for $i\ge 0$:

• $\mathcal {E}_{0}=_{\mathrm {def}}\mathcal {D}^{*}$

• $\mathcal {E}_{i+1}=_{\mathrm {def}}\mathsf {Exceptional}(\mathcal {T}^{*},\mathcal {E}_{i})$

Example 2 (continued). Using the knowledge base of Example 2, we initialise $\mathcal {T}^{*}$ as $\{\mathsf {EmpStud}\sqsubseteq \mathsf {Stud}\}$ and let

We then obtain the following exceptionality sequence:

Since $\mathcal {D}^{*}$ is finite, the construction will eventually terminate with a fixed point $\mathcal {E}_{\mathsf {fix}} = \mathsf {Exceptional}(\mathcal {T}^{*},\mathcal {E}_{\mathsf {fix}})$. If this fixed point is non-empty, then the axioms in there are said to have infinite rank. We therefore set $\mathcal {D}^{*}_\infty$ as $\mathcal {E}_{\mathsf {fix}}$ (Line 11 of $\mathsf {ComputeRanking}(\cdot )$), and the classical translations of these axioms are moved to the TBox. Hence we redefine the knowledge base in the following way (Lines 12 and 13 of $\mathsf {ComputeRanking}(\cdot )$):

• ;

• $\mathcal {D}^{*}\leftarrow \mathcal {D}^{*}\setminus \mathcal {D}^{*}_\infty$.

Function $\mathsf {ComputeRanking}(\cdot )$ must terminate since $\mathcal {D}$ is finite, and at every iteration, $\mathcal {D}^{*}$ becomes smaller (hence, we have at most $|\mathcal {D}|$ iterations). In the end, we obtain a knowledge base $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$ which is modularly equivalent to the original knowledge base $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ (see Lemma 12 below), in which $\mathcal {D}^{*}$ has no DCIs of infinite rank (all the strict knowledge ‘hidden’ in the dTBox has been moved to the TBox). In the following, we say that such a knowledge base is in rank normal form.

Once we have obtained the knowledge base $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$ and the final sequence $\mathcal {E}_{0},\mathcal {E}_{1},\ldots ,\mathcal {E}_{\mathsf {fix}}$, we partition the set $\mathcal {D}^{*}$ into the sets $\mathcal {D}_{0},\ldots ,\mathcal {D}_{n}$, for some $n\ge 0$ (Lines 15–17 of $\mathsf {ComputeRanking}(\cdot )$).

Example 2 (continued). For $\mathcal {KB}$ as in Example 2, we obtain the sequence:

At this stage, we have moved all the classical information possibly ‘hidden’ inside the dTBox to the TBox, and ranked all the remaining DCIs, where the rank of a DCI is the index of the unique partition to which it belongs, defined as follows:

Definition 26

(Ranking). For every $C,D\in \mathcal {L}$:

• $\mathsf {rk}(C)=_{\mathrm {def}}i$, $0\le i\le n$, if $\bigsqcap \overline{\mathcal {E}_i}$ is the first element in $(\bigsqcap \overline{\mathcal {E}_{0}},\ldots ,\bigsqcap \overline{\mathcal {E}_{n}})$ s.t. ;

• $\mathsf {rk}(C)=_{\mathrm {def}}\infty$ if there is no such $\bigsqcap \overline{\mathcal {E}_{i}}$;

• .

Remark 1

For every $i \le j\le n$, $\models \bigsqcap \overline{\mathcal {E}_{j}}\sqsubseteq \bigsqcap \overline{\mathcal {E}_{i}}$.

Remark 2

For every $i < j\le n$, $\mathcal {D}_{i}\cap \mathcal {D}_{j}=\emptyset$.

To summarise, we transform our initial knowledge base $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$, obtaining a modularly equivalent knowledge base $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$ (see Lemma 12 below) and a ranking of DCIs in the form of a partitioning of $\mathcal {D}^{*}$. The main difference between $\mathsf {ComputeRanking}(\cdot )$ and the analogous procedure by Casini and Straccia [30] is the reiteration of the ranking procedure until $\mathcal {D}^*_{\infty }=\emptyset$ (lines 4–14 in $\mathsf {ComputeRanking}(\cdot )$). While the two procedures behave identically in the case where there are no DCIs s.t. in $\mathcal {D}$, the original procedure [30] did not handle all the cases correctly in which there is strict information ‘hidden’ inside the dTBox.

Given the knowledge base $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$, we can now define the main algorithm for deciding whether a DCI is in the rational closure of $\mathcal {KB}$. To do that, we use the same approach as in the function $\mathsf {Exceptional}(\cdot )$, that is, given $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$ and our sequence of sets $\mathcal {E}_{0},\ldots ,\mathcal {E}_{n}$, we use the TBox $\mathcal {T}^{*}$ and the sets of conjunctions of materialisations $\bigsqcap \overline{\mathcal {E}_{0}},\ldots ,\bigsqcap \overline{\mathcal {E}_{n}}$.

Definition 27

(Rational Deduction). Let $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ and let $C,D\in \mathcal {L}$. We say that is rationally deducible from $\mathcal {KB}$, denoted , if $\mathcal {T}^{*}\,\models \, \bigsqcap \overline{\mathcal {E}_{i}}\sqcap C\sqsubseteq D$, where $\bigsqcap \overline{\mathcal {E}_{i}}$ is the first element of the sequence $\bigsqcap \overline{\mathcal {E}_{0}},\ldots ,\bigsqcap \overline{\mathcal {E}_{n}}$ s.t. . If there is no such element, if $\mathcal {T}^{*}\,\models \,C\sqsubseteq D$.

Observe that $\mathcal {KB}\vdash _{\mathsf {rat}}C\sqsubseteq D$ if and only if , i.e., if and only if $\mathcal {KB}\vdash _{\mathsf {rat}}C\sqcap \lnot D\sqsubseteq \bot$ (that is to say, $\mathcal {T}^{*}\,\models \,C\sqsubseteq D$).

The algorithm corresponding to the steps above is presented in the function $\mathsf {RationalClosure}(\cdot )$ below.

Example 2 (continued). Let $\mathcal {KB}$ be as in Example 2 and assume we want to check whether is in the rational closure of $\mathcal {KB}$. Then, the while-loop on Line 2 of function $\mathsf {RationalClosure}(\cdot )$ terminates when $i=1$. At this stage, $\bigsqcap \overline{\mathcal {E}_{i}}=(\lnot \mathsf {EmpStud}\sqcup \exists \mathsf {receives}.\mathsf {TaxInv})\sqcap (\lnot \mathsf {EmpStud}\sqcup \lnot \mathsf {Parent}\sqcup \lnot \exists \mathsf {receives}.\mathsf {TaxInv})$. Given this, one can check that .

Finally, we can confirm that , i.e., .

Before we state the main theorem of this section, we need to establish the correspondence between the ranking function $\mathsf {rank}_\mathcal {KB}(\cdot )$ presented in Sect. 5.1 in the construction of the rational closure of $\mathcal {KB}$ and linked by Theorem 3 to the definition of rational entailment, and the ranking function $\mathsf {rk}(\cdot )$ of Definition 26 used in the above algorithm. We also need to establish that the normalisation of a knowledge base by our algorithm maintains modular equivalence.

Lemma 12

Let $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ and let $\mathcal {KB}^{*}=\mathcal {T}^{*}\cup \mathcal {D}^{*}$ be obtained from $\mathcal {KB}$ through function $\mathsf {ComputeRanking}(\cdot )$. Then $\mathcal {KB}$ and $\mathcal {KB}^{*}$ are modularly equivalent.

Lemma 13

For every defeasible knowledge base $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ and every $C\in \mathcal {L}$, $\mathsf {rank}_{\mathcal {KB}}(C)=\mathsf {rk}(C)$.

Now we can state the main theorem, which links rational entailment to rational deduction via Theorem 3.

Theorem 4

Let $\mathcal {KB}=\mathcal {T}\cup \mathcal {D}$ and let $C,D\in \mathcal {L}$. Then iff .

As an immediate consequence, we have that the function $\mathsf {RationalClosure}(\cdot )$ is correct w.r.t. the definition of rational closure in Definition 24.

Corollary 3

Checking rational entailment is exptime-complete.

Hence entailment checking for defeasible ontologies is just as hard as classical subsumption checking.

We conclude this section by noting that although rational closure is viewed as an appropriate form of defeasible reasoning, it does have its limitations, the first of which is that it does not satisfy the presumption of independence [51, Section 3.1]. To consider a well-worn example, suppose we know that birds usually fly and usually have wings, that both penguins and robins are birds, and that penguins usually do not fly. That is, we have the following knowledge base: . Rational closure allows us to conclude that robins usually have wings, since they are viewed as typical birds, thereby satisfying the presumption of typicality. But with penguins being atypical birds, rational closure does not allow us to conclude that penguins usually have wings, thus violating the presumption of independence which, in this context, would require the atypicality of penguins w.r.t. flying to be independent of the typicality of penguins w.r.t. having wings.

This deficiency is well-known, and there are other forms of defeasible reasoning that can overcome this, most notably lexicographic closure [31], relevance closure [33], and inheritance-based closure [32, 34]. But note that the presumption of independence is propositional in nature. In fact, the DL version of lexicographic closure is essentially a lifting to the DL case of a propositional solution to the problem [51].

What is perhaps of more interest is the inability of rational closure to deal with defeasibility relating to the non-propositional aspects of descriptions logics. For example, Pensel and Turhan [54, 55] have shown that rational closure across role expressions does not always support defeasible inheritance appropriately.

Suppose we know that bosses are workers, do not have workers as their superiors, and are usually responsible. Furthermore, suppose we know that workers usually have bosses as their superiors. We thus have the knowledge base:

Since workers usually have bosses as their superiors, and bosses are usually responsible, one would expect to be able to conclude that workers usually have responsible superiors. But rational closure is unable to do so. From the perspective of the algorithm for rational closure, this can be traced back to the use of materialisation (Definition 25) when computing exceptionality, as Pensel and Turhan [54] show. A more detailed semantic explanation for this inability is still forthcoming, though.

6 Beyond Defeasible Concept Inclusion

Defeasible reasoning in description logics extends beyond defeasible concept inclusion. In this section, we outline two such extensions following on from the work presented here, firstly to account for named individuals in defeasible knowledge bases, and secondly to introduce defeasible class descriptions.

The introduction of defeasible reasoning also for ABox reasoning is a necessary extension of the results we have presented in this chapter. We want to be able to derive assertions of the kind “Presumably, the individual a falls under the concept C”, and, in the present framework, the natural way of doing it would be to model the presumption of typicality also w.r.t. the individuals named in the ABox, that is, to maximise the amount of defeasible information we associate with each individual: If all we know about Ann is that she is a student, we want to be able to conclude that presumably Ann does not get a tax invoice. The main technical problem in the present framework is the possibility of having multiple distinct configurations that maximise the presumption of typicality w.r.t. the individuals [30, Example 7]. Different solutions have been proposed [29, 30, 35, 45, 55], but, as mentioned in Sect. 2, we are not going to introduce here the different proposals regarding the introduction of defeasible reasoning for the ABox.

The systems proposed by Giordano and others [39, 40, 44, 45] introduce an operator $\mathbf{T}$ (typical) associated to the concepts. This allows extra expressivity in modelling defeasible information: an inclusion like $\mathsf {Stud}\sqcap \lnot \exists \mathsf {receives}.\mathsf {TaxInv}\sqsubseteq \mathbf{T}(\mathsf {Stud})$, indicating that the students that do not receive the a tax invoice must be considered typical students, is not expressible in a language using only defeasible subsumptions. However, in most of the systems they introduce, $\mathbf{T}$ can be used only in expressions of the form $\mathbf{T}(C)\sqsubseteq D$, which is interpreted exactly as an expression . Booth and others [10] have shown that, even at the propositional level, using freely an operator like $\mathbf{T}$ creates the possibility of multiple configurations satisfying the presumption of typicality, in a way that, from the formal point of view, is analogous to the problem registered working with the ABoxes.

Given the special status of subsumption in DLs in particular and the historical importance of argument forms and entailment in logic in general, the bulk of the effort in non-monotonic reasoning has quite naturally been spent on the definition of a proper account of defeasible subsumption and the characterisation of appropriate notions of defeasible entailment.

However, given the importance of concept descriptions in DLs, an extension of this work to also represent defeasible classes is called for. This includes the ability to represent notions such as plausible value or existential restrictions in complex concept descriptions [17, 23, 24, 27]. There are several ways to accomplish this, and we focus here on one such proposal.

We could, for example, ask whether the constraint that workers usually have bosses as their superior is necessarily correctly captured by the defeasible subsumption: . An alternative reading of the phrase is that all workers have some superior, who is usually a boss. It is therefore the class description $\exists \mathsf {hasSuperior}. \mathsf {Boss}$ which is defeasible. rather than the subsumption statement. This can be captured by extending the concept language of $\mathcal {ALC}$ as follows:

With $\widetilde{\mathcal {L}}$ we denote the extended language of all (possibly defeasible) $\mathcal {ALC}$ concepts.

Definition 28

Let $\mathcal {P}=\langle \varDelta ^{\mathcal {P}},\cdot ^{\mathcal {P}},\prec _{\mathcal {P}} \rangle$ be a preferential interpretation. Let $r\in \mathsf {R}$ and $C\in \mathsf {C}$. The truth conditions for defeasible universal restriction and strict existential restriction are given by:

That captures the notion of strict existential restriction follows since, not only does the semantics require that some r-filler be in $C^{\mathcal {P}}$, but it also demands that some most preferred r-filler be in $C^{\mathcal {P}}$. In contrast, defeasible universal (value) restriction relaxes the condition that all r-fillers be in $C^{\mathcal {P}}$, requiring only that all most preferred r-fillers be in $C^{\mathcal {P}}$.

Definition 28 now allows us to state that every worker has some typical superior who is a boss, i.e., , or that any superior of a worker is usually a boss, i.e., .

The defeasible quantifiers of Definition 28 are based on a single order on objects, but this generalises naturally to a parameterised ordering on either objects or role interpretations [23, 27], the details of which we omit here. The ramifications of extending the language with defeasible quantification have also been investigated for modal logics, where it assumes the form of defeasible modalities [25, 26].

7 Concluding Remarks

In this paper we have provided an overview of a specific approach to defeasible reasoning—one that is based on work initiated by Kraus, Lehmann and Magidor for the propositional case [49, 52]. This approach has a number of attractive characteristics: It has a simple and intuitive semantics for defeasible subsumption in description logics that is general enough to constitute the core framework within which to investigate defeasible extensions to DLs. It also allows for the characterisation of two forms of defeasible subsumption relations—preferential and rational subsumption—providing weight to the claim that the semantic constructions are intuitively appropriate. In addition, it provides the basis for defining an appropriate form of defeasible entailment—a description logic version of what is known as rational closure in the propositional case. Moreover, it comes equipped with an algorithm for computing the DL version of rational closure with computational complexity that is no worse than the complexity of entailment checking in $\mathcal {ALC}$. Importantly from a practical perspective, the algorithm can be reduced to a number of classical entailment checks, which means that it can be implemented on top of existing (highly optimised) description logic reasoners. In terms of performance, a relatively naïve version of such an algorithm has already been shown to scale well in practice [28].

Section 6 touched on some ways in which defeasible reasoning for description logics has already been extended beyond defeasible concept inclusion, but all these proposals are only preliminary investigations with much work that still needs to be done. Further topics for future research include the study of role-based defeasible constructors [23, 24, 27] and the investigation of defeasible versions of query answering [64]. Finally, a somewhat different area for future exploration is one that is aimed at exploiting the well-known connection between belief revision and rational consequence in the propositional case [38]. Given this connection on the propositional level, it seems reasonable to expect that the results presented in this paper can form the basis of a different perspective on belief revision for description logics.