Rational Closure For All Description Logics (Extended Abstract)

1 Introduction

Many modern applications of description logics (DLs, for short), such as biomedical ontologies and semantic web policies, provide fresh motivations for extending DLs with an overriding mechanism analogous to the homonymous feature of object-oriented programming (see [Rector, 2004; Stevens et al., 2007; Bonatti et al., 2015] for extended motivations). This may be accomplished - for instance - by extending a given monotonic DL with so-called defeasible inclusions (DIs), that are expressions C ⊏∼D, where C and D are concepts (such as OWL2 classes). The intended meaning of C ⊏∼ D is: "the instances of C are normally instances of D". 1 In other words, D is a default property of C's instances, that can be possibly overridden by conflicting properties in the subclasses of C, as in the following example.

∗This is an extended abstract of the homonymous paper published in the Artificial Intelligence journal [Bonatti, 2019].

1 Compare DIs with the "strong" classical inclusions C ⊑ D of DLs that mean: "all the instances of C are also instances of D". Relation ⊑ corresponds to the SubClassOf operator of OWL2.

Example 1. By definition, eucaryotic cells (EC for short) are cells that have a nucleus. Biologists consider mammalians' red blood cells (MRBC) eukaryotic even if they have no nucleus in their mature stage. This piece of biological knowledge can be naturally encoded by stating that mammalian red blood cells are eukaryotic, eukaryotic cells normally have a nucleus while mammalian red blood cells normally do not have it. A formalization of the above three statements by means of DIs and classical inclusions is the following:

(the concept ∃hasPart.Nucleus represents the class of all objects that have an attribute hasPart that is an instance of Nucleus). If all the above inclusion symbols were ⊑, then concept MRBC would be inconsistent, because it would be contained both in ∃hasPart.Nucleus and its complement. With ⊏∼, instead, no contradiction is derived: the third axiom overrides the second, and MRBC may have instances.

The formal semantics of DIs is nonmonotonic, that is - unlike classical logic - adding more axioms to a knowledge base (KB) may cause some of its consequences to be retracted.

Example 2. With reference to the above example, without the third axiom one should conclude that mammalian red blood cells normally have a nucleus, in symbols: MRBC ⊏∼∃hasPart.Nucleus. When the third axiom is added to the KB this conclusion is retracted (overridden) and replaced with MRBC ⊏∼ ¬∃hasPart.Nucleus.

Rational closure (RC) [Casini and Straccia, 2013; Britz et al., 2013; Giordano et al., 2015] is a nonmonotonic semantics applicable to DLs that received particular attention, because of the following properties: (i) it frequently preserves the complexity of the classical DL that it extends; (ii) it always yields a unique deductive closure, while some of the other nonmonotonic semantics may yield none or many deductive closures, thereby raising inconsistency or ambiguity problems; (iii) RC satisfies a set of postulates introduced long ago by Kraus, Lehmann, and Magidor, called KLM [Kraus et al., 1990; Lehmann and Magidor, 1992], that aim at modeling the logical properties of reasoning about normality. Some of the drawbacks of rational closure's inferences are being addressed in the works cited in Section 6. Our contribution, instead, is focussed on the generality of RC.

RC has never been applied to the entire DL SHROIQ(D), that constitutes the foundation of the standard ontology language OWL2. The reason is that the model theoretic semantics of RC is based on suitable canonical models [Giordano et al., 2015] whose existence is proved by means of the disjoint model union property (DMUP), a property that is generally not enjoyed by the DLs that support nominals (equivalently, the ObjectOneOf operator of OWL2) or the universal role (i.e. OWL2's topObjectProperty).

This paper proves that the standard semantic framework of RC, with its models and related soundness and completeness results, cannot be extended to the DLs that do not enjoy the DMUP. Then we introduce a refinement of RC called stable RC, that does not rely on the DMUP, so in principle is applicable to all of SROIQ(D). Finally, we extensively analyze the properties of stable RC and compare it with RC. These three contributions are briefly described in sections 3, 4, and 5, respectively. Section 6 summarizes our conclusions. We are going to simplify several definitions in order to meet space limitations. 2

2 Preliminaries on DLs

Here we recall only the basics needed to read this abstract; see [Horrocks et al., 2006] for the missing details on the DL SROIQ(D). The vocabularies of DLs consist of countably infinite sets of concept names, role names, and individual names. The compound concepts used in this abstract are defined by the following grammar, where A and P range over concept names and role names, respectively:

DL interpretations are structures I = 〈∆I , ·I 〉 where ∆I is a nonempty set, and ·I is an interpretation function such that AI ⊆ ∆I , P I ⊆ ∆I × ∆I , for all individual names a, aI ∈ ∆I , ⊥I = ∅, and ⊤I = ∆I .

Function ·I is extended to compound concepts as follows: (C ⊓ D)I = C I ∩ DI , (C ⊔ D)I = C I ∪ DI , (¬C)I = ∆I \ C I , and (∃P.C)I = {x | ∃y : (x, y) ∈ P I ∧ y ∈ C I }. I satisfies C iff C I ̸= ∅. A concept inclusion is an expression C ⊑ D; it is satisfied by an interpretation I iff C I ⊆ DI .

3 Analysis of Standard RC

We may assume without loss of generality that knowledge bases are sets of DIs only. 3 The semantics of RC is based on ranked interpretations that are structures I = 〈∆I , ·I , hI 〉, where 〈∆I , ·I 〉 is a classical DL interpretation, and hI : ∆I → ω (where ω is the first infinite ordinal) assigns each individual x to an ordinal; the higher the ordinal, the higher the abnormality of x. The set of minimally abnormal members of C I will be denoted by min I (C). A ranked interpretation I satisfies C ⊏∼D iff min I (C) ⊆ DI , i.e., if the maximally normal instances of C satisfy D. As usual, we say that I is a model of a KB K iff I satisfies all the DIs in K. We also write K |= C ⊏∼ D when C ⊏∼ D is satisfied by all the models of K. C is consistent w.r.t. K if some model of K satisfies C.

2 In particular we do not discuss the restriction of reasoning to relevant concepts and DIs, that is adopted in the proofs of the complexity results.

3 Each classical inclusion E ⊑ F is equivalent to E ⊓ ¬F ⊏∼⊥.

The inferences of RC are computed by means of an exceptionality ranking rnk that maps each concept onto an ordinal in ω+1 (where ω is the first infinite ordinal). The ranking, in turn, is based on the following notion: A concept C is exceptional w.r.t. a KB K iff K |= ⊤ ⊏∼ ¬C (informally: none of the most normal individuals of any model of K are ever in C). A DI C ⊏∼ D is exceptional w.r.t. K if C is. Exceptionality induces a chain of KBs

where E0 = K and each Ei+1 is the set of DIs of Ei that are exceptional w.r.t. Ei, that is, Ei+1 contains a DI C ⊏∼D of Ei iff

Define rnk(C) = i iff i is the least finite ordinal such that C is not exceptional w.r.t. Ei; if no such i exists, then rnk(C) = ω.

Now the rational closure of K, denoted by RC(K), can be defined as the set of all DIs C ⊏∼ D such that either rnk(C) = ω or rnk(C) < rnk(C ⊓ ¬D). The rationale behind this definition is the following: (i) rnk(C) = ω should occur only when C is inconsistent w.r.t. K; in that case C ⊏∼ D vacuously holds; (ii) rnk(C) < rnk(C ⊓ ¬D) in fact means that the instances of C that satisfy ¬D are not the most normal instances of C.

The KLM postulates characterize |= and the set of DIs that are valid in the class of all ranked interpretations. However, these notions obviously constitute a monotonic logic. Therefore the model-theoretic semantics of RC(K) is based only on the minimal canonical models of K [Giordano et al., 2015]. The canonical models of K, roughly speaking, are models of K where all the concepts that are consistent w.r.t. K are simultaneously nonempty. Here is where the DMUP comes into play: if the underlying monotonic DL enjoys it, then each consistent K has a canonical model, that can be constructed by taking the union of any set that contains a model for each consistent concept. The correctness and completeness of RC inferences can now be stated as follows: a DI is in RC(K) iff it is satisfied by all minimal canonical models of K.

Unfortunately, we have shown that this result does not hold if the underlying classical DL does not enjoy the DMUP. In particular [Bonatti, 2019, Example 4.1] proves the following statement:

Theorem 1. There exist a KB K and a concept C such that C ⊏∼ ⊥ is satisfied by all the ranked models of K (including its canonical models) but C ⊏∼⊥ is not in RC(K).

In other words, when the DMUP does not hold, the procedure for computing RC is not complete w.r.t. the standard semantics of RC. We are not only talking about the current definition of canonical model; no semantics based on ranked models matches the computation of RC based on rnk .

4 Stable Rational Closure

There are two possible ways of fixing the above problem. First, one may change the semantics. This would be a major departure from the original foundations of RC, aimed at instantiating the KLM postulates; given the strict connection between the postulates and ranked models, changing the notion of interpretation may easily affect the validity of the postulates. Therefore, we followed the second possible choice, and modified the definition of ranking.

By analyzing the problematic example behind Theorem 1, it can be seen that the problem arises from the fact that each Ei+1 with i > 0 is determined based on Ei that, in general, is a strict subset of K; in this way, some of the constraints posed by K's axioms may be lost along the way. Thus we introduce a construction that takes into account the entire K at all steps.

Finding the new notion of ranking has not been easy; Section 4 of [Bonatti, 2019] illustrates a few dead ends. Eventually, a natural refinement of RC that does not depend on the DMUP has been obtained by setting up and solving a metalevel equation that captures the requirements on rankings.

For this purpose, let us consider arbitrary ranking functions r from concepts to ω+1; these are the candidate refinements of rnk. Each ranking function determines a class of ranked interpretations, called upward closed models, whose function h is constrained by r. More precisely, a model I of K is upward closed w.r.t. r iff for each concept C, and for all instances x ∈ min I (C), it holds that hI (x) = r(C). We write K |=r C ⊏∼D when C ⊏∼D is satisfied by all the models of K that are upward closed w.r.t. the given r.

Each ranking function r determines also the following analogue of sequence (1):

where for all i ≤ ω, E r i = {(C ⊏∼D) ∈ K | r(C) ≥ i}.

Finally, each r induces a relativized notion of rational closure denoted by RCr , analogous to RC(K):

Of course, only some ranking functions make sense. "Good" rankings should satisfy a "correct" version of the exceptionality criterion (2). In order to specify the new criterion, let ̂ E r i represent the class of all the individuals that satisfy all the DIs in E r i ; formally, ̂ E r i is a concept defined by:

Now the new exceptionality criterion can be formulated as follows. For all concepts C and all ordinals i < ω, a "good" ranking function should satisfy the following conditions:

A ranking function r is stable w.r.t. K iff it satisfies the above two conditions. By stable rational closure of K we mean any set RCr such that r is stable w.r.t. K.

Let us compare the new exceptionality conditions with (2). First, they depend on the entire K, as opposed to one of its subsets E r i . This addresses the issue that leads to Theorem 1.

The instances of concept ̂ E r i can be regarded as the most normal individuals at level i, since they satisfy all the DIs at that level, by definition. So the inclusion ̂ E r i ⊑ ¬C says that none of the most normal individuals at level i are in C; accordingly, the two conditions above say that C shall be regarded as exceptional w.r.t. E r i iff ̂ E r i ⊑ ¬C is entailed.

Note that we use ⊑ instead of ⊏∼ because ̂ E r i ⊏∼ ¬C is always equivalent to ⊤ ⊏∼ ¬C in all models of K, so (3) would always reach a fixpoint in one step, and would not model correctly the exceptionality of concepts.

Finally, |=r is adopted in order to obtain a model-theoretic characterization of stable rational closure; this matter is discussed in the next section.

5 Main Properties of Stable RC

We start by showing a model-theoretic characterization of stable RC

Theorem 2. For all stable rankings of K,

Note that in the above theorem upward-closed models play the role that minimal canonical models had in RC. The advantage of upward-closed models is that their existence does not depend on the DMUP. This is achieved by allowing consistent concepts to be empty in some upward-closed interpretations, thereby removing the main need for constructing a model from the union of other models (cf. the discussion of canonical models in Section 3). Thus, upward-closed models contribute to removing the limitation to generality that affects RC.

The use of |=r in the new exceptionality criteria (points 1 and 2 in Section 4) is essential for achieving the above modeltheoretic characterization. It turns out that if |=r were replaced with |=, then the resulting notion of stable closure would match neither the consequences of all ranked models (i.e. it might contain DIs δ such that K ̸|= δ), nor the consequences of upward-closed models only.

The next set of results constitutes the evidence that stable RC can be regarded as a natural extension of RC. The first result concerns the logical properties of stable RC:

Theorem3. If r is stable, then RCr is closed under the KLM postulates.

Next we turn to computational properties: like RC, stable RC does not increase the complexity of reasoning in a number of interesting DLs. In the following, let metavariable DL range over the names of classical description logics, such as EL, ALC or SROIQ, for example. We say that a set of DIs K is in DL if the set of classical inclusions obtained by replacing ⊏∼with ⊑ in K is in DL.

Definition 1. The entailment problem of stable RC in a description logic DL consists in deciding, for a given set of DIs D in DL, and for a given K in DL, whether D ⊆ RCr holds for some stable ranking r of K.

Theorem 4. Let DL be a description logic whose subsumption decision problem is in EXP. The entailment problem of stable RC in DL is in EXP, too. Moreover, the entailment problem of stable RC is in P in the logic EL extended with ⊥.

More generally, if DL's subsumption problem is in NEXP or N2EXP (that is the complexity of SROIQ), then the entailment problem of stable RC is in P NEXP or P N2EXP, respectively.

The next theorem provides further evidence that stable RC is a natural generalization of RC. It states that when the DMUP holds, then stable RC is equivalent to RC.

Theorem 5. If K is in a logic that enjoys the DMUP, then K has exactly one stable ranking r, such that r = rnk and RCr = RC(K).

Unfortunately, when the DMUP does not hold, there is no guarantee that stable rankings exist and are unique. The term "stable" is justified by the fact that the definition of a stable r depends on |=r and viceversa. Thus stable rankings are essentially defined by a stability condition, that may possibly have no solutions or multiple solutions. Indeed we can prove that:

Theorem 6. There exist K that have no stable rankings, and there exist K that have two or more stable rankings.

Consequently, one of the appealing properties of RC does not scale to the expressive DLs that do not enjoy the DMUP. In general, when stable rankings exist, the following relationship holds between the sequences (1) and (3):

In other words, rnk(C) ≤ r(C), for all concepts C. The disequality may be strict. Moreover, it can be proved that if r1 and r2 are two distinct stable rankings of K, then the two sequences 〈E r1 i 〉i≤ω and 〈E r2 i 〉i≤ω are not comparable with each other.

Reasoning with upward-closed models can be reduced to (monotonic) entailment over ranked models, for which a few calculi have been provided (cf. [Britz and Varzinczak, 2017], and Prop. 2.9 and Corollary 2.10 in [Giordano et al., 2018]). In particular:

Theorem 8. For all ranking functions r,

where C is a suitable, finite set of relevant concepts, that depends on K and δ.

The above reduction constitutes the basis for automated reasoning in stable RC and is exploited in the proofs of the aforementioned complexity results.

6 Discussion and Conclusions

Rational closure is tightly bound to the disjoint model union property. In general, when this property does not hold, the inferences computed through RC's notion of ranking do not match any model-theoretic semantics based on ranked interpretations - that have always constituted the semantic foundation of the logics designed around the KLM postulates, like RC itself.

It can be seen that this is a consequence of the internalization of the original framework by Kraus, Lehmann, and Magidor, that is, the trasformation of a nonmonotonic consequence relation into the object-level operator ⊏∼ [Bonatti, 2019, Sec. 10].

Stable rational closure removes the dependency on the DMUP and re-establishes a model-theoretic characterization based on ranked models. Stable RC is a natural generalization of RC: it coincides with RC when the KB enjoys the DMUP; it enjoys the same computational properties as RC; it satisfies the KLM postulates. Unfortunately, when the DMUP does not hold, a KB may have no stable RC or multiple stable RCs. In other words, similarly to other nonmonotonic logics, like default and autoepistemic logics, stable RC may yield multiple deductive closures or no deductive closures at all.

Further drawbacks of stable RC are inherited from RC, due to the equivalence of the two logics over the DLs that enjoy the DMUP. One of these drawbacks is that default properties do not apply to role fillers. For instance, suppose that Example 1 is extended with the axiom: HumanBody ⊑ ∃hasPart.MRBC. From the resulting KB it is not possible to conclude that HumanBody ⊏∼∃hasPart.¬∃hasPart.Nucleus, that is, the default property of MRBC is not reflected on the attribute hasPart of HumanBody.

Another drawback is the so-called inheritance blocking phenomenon: one overriding suffices to block the inheritance of all the default properties of the superclass. Consider again our biological example, and extend the KB of Example 1 with the axiom EC ⊏∼∃hasPart.Mithocondria. Since the property of having a nucleus is overridden in MRBC, the property of having mithocondria is not inherited, either, even if none of the properties of MRBC is inconsistent with having mithocondria.

A first solution to these problems has been given in [Pensel, 2019; Pensel and Turhan, 2018]. Generality is still an issue, though, since these works are specifically formulated for a logic of the EL family, that is a tiny fragment of SROIQ(D). Other approaches, like [Britz and Varzinczak, 2017], are still missing the definition of nonmonotonic inferences. In order to make stable RC applicable in practice, the above research efforts should be completed, integrated with each other, and further integrated with a satisfactory solution to the generality problem.

In the light of the above technical difficulties, the author believes that the competing logic DLN [Bonatti et al., 2015; Bonatti and Sauro, 2017] is currently an appealing alternative. DLN suffers from none of the drawbacks of RC; it has the same nice computational properties (actually, the results on tractability preservation are currently broader); moreover it "almost" satisfies several versions of the KLM postulates [Bonatti and Sauro, 2017], even if satisfying the postulates was not one of the goals of DLN. The major discrepancies between the postulates and DLN stem from DLN's novel treatment of unresolved conflicts, i.e. the conflicts between DIs that cannot be resolved by the chosen priority relation and require additional knowledge. Such discrepancies disappear when those conflicts are resolved by adding the missing knowledge. The new way of handling unresolved conflicts is motivated by knowledge engineering requirements, and - in general - the minor violations of the postulates (that in the author's opinion are not a must, rather a tool for analyzing nonmonotonic logics) are compensated by DLN's extended coverage of such requirements.