A New Semantics for Overriding in 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 nonmonotonic inferences. Some recent examples stemming from the biomedical domain are discussed in [Rector, 2004; Stevens et al., 2007]. There, the goal of supporting default attributes and exceptions is deemed important enough to look for alternative representation methods, based on classical reasoning and ontology design patterns. However, these solutions do not scale to more complex examples with multiple exception dimensions, as discussed in [Rector, 2004]: The number of additional concepts introduced by the patterns may grow exponentially. Moreover, such auxiliary concepts are defined using computationally expensive constructs such as disjunction. So, even if the given knowledge base belongs to some low-complexity fragment (such as the OWL2 profiles), its nonmonotonic extension is generally not tractable.

Nonmonotonic DLs natively support default inferences and exceptions. However none of the standard nonmonotonic semantics produces exactly the set of expected consequences, and this can be verified on a range of rather simple examples. Some of the major known drawbacks are the following:

∗This is an extended abstract of the paper [Bonatti et al., 2015a], integrated with the developments in [Bonatti and Sauro, 2017], conditionally accepted for publication on the AIJ. This research is currently being funded by the European Unions Horizon 2020 research and innovation programme under grant agreement N. 731601.

Inheritance blocking: In several nonmonotonic logics a concept with exceptional properties inherits none of the default properties of its superclasses. For instance penguins, that are exceptional birds because they do not fly, do not inherit any of the other default properties of birds, such as having wings and feathers.

Undesired CWA effects: In some nonmonotonic DLs, an exceptional concept is shrinked to the individuals that explicitly belong to it; it may even become inconsistent. Using the penguin example again, by default no penguins exist unless explicitly stated otherwise. After asserting that the individual Opus is a penguin, the concept Penguin becomes the singleton {Opus}.

Limited control on role ranges: In most nonmonotonic DLs, the knowledge engineer cannot specify whether a role should range only over normal individuals or not. In the DLs based on default logic, rational closure, and variants thereof, default properties never apply to role fillers.

Silent removal of unresolved conflicts: Very frequently, unresolved conflicts between nonmonotonic assertions are a symptom of a gap in the axiomatization. The correct resolution of such conflicts is typically domain dependent and should require human intervention (see [Bonatti et al., 2015a; 2015b] for a detailed discussion of this issue). Most nonmonotonic logics hide such conflicts (i.e. they do not have any visible consequence) thereby hindering their identification - a necessary step for the validation and correction of knowledge bases.

Moreover, the computational complexity of nonmonotonic DLs is almost always higher than the complexity of the corresponding classical DL, and the tractability of the OWL 2 profiles is not preserved. The lack of optimization techniques for nonmonotonic DL reasoning is a further obstacle to the practical application of these logics.

Given the above motivations (more extensively articulated in the full paper), in this work we have investigated a new family of nonmonotonic DLs, called DLN, aimed at addressing the above drawbacks. The comparison of DLN with the major nonmonotonic DLs is summarized in Table 1. Preliminary performance tests have been reported in the full paper and have been later extended in [Bonatti et al., 2015b] using additional optimization techniques that show unparalleled scalability properties over large nonmonotonic knowledge bases, with more than 105 axioms. For instance, sub- CIRC, DEF, AEL, TYP, RAT, PR stand, respectively, for Circumscribed DLs [Bonatti et al., 2009; 2011], Default DLs [Baader and Hollunder, 1995a; 1995b], Autoepistemic DLs [Donini et al., 2002], DLs with Typicality [Giordano et al., 2009; 2013], DLs with Rational Closure [Casini and Straccia, 2010; Casini et al., 2013] and their combination with inheritance networks [Casini and Straccia, 2013], and Probabilistic DLs [Lukasiewicz, 2008].

1. Context dependent, see Example 29 in the full paper.
2. Only direct conflicts, as in Example 10 in the full paper.
3. Inconsistency may propagate to the entire KB.
4. Subsumption and assertion checking only, which suffice for application examples.
5. Currently proved for EL (Giovanni Casini, personal communication).

sumption/assertion query answering over nonmonotonic variants of the Gene Ontology with classical role fillers ranges from 0.25 to 2.46 seconds.

2 The Family DLN

Let DL be any description logic. The language of DLN is obtained by adding a new concept name NC for each DL concept C. The new concepts are called normality concepts, although the term standard would be more appropriate since DLN- unlike typicality logics and rational closure - has not been designed to model normality (as formalized by the KLM postulates, for example).

DLN has a utilitarian purpose, related to McCarthy's conventions [McCarthy, 1986], aimed at making knowledge bases more manageable, e.g. by reducing their size, improving modularity, and so on. We may want to assert that by default a drug has contraindication X not because this is normally so, but rather for mitigating the effects of potential human errors [Rector, 2004; Stevens et al., 2007]: It is safer to signal more contraindications than missing some; accordingly, with the above default assertion, forgetting to define the contraindications of a new drug cannot result in a missing contraindication. The goal of DLN is supporting such a variety of knowledge engineering needs in a scalable way.

A DLN knowledge base is a disjoint union KB = S ∪ D where S is a finite set of DLN inclusions and assertions and D is a finite set of defeasible inclusions (DIs, for short) that are expressions C ⊑n D where C is a DL concept and D a DLN concept. If δ = (C ⊑n D), then pre(δ) and con(δ) denote C and D, respectively.

The informal meaning of C ⊑n D is: "all standard instances, by default, satisfy C ⊑ D, unless stated otherwise", that is, unless some higher priority axioms entail that some standard instances satisfy C ⊓ ¬D; in that case, C ⊑n D is overridden. The instances of any concept NE are required to satisfy all the DIs that are not overridden in NE.

The priority relation over DIs is denoted by ≺. DLN solves automatically only the conflicts that can be settled using ≺. Any other conflict should be regarded as a representation error (cf. the discussion of silent conflict removal in the introduction) and shall be resolved by the knowledge engineer, typically by adding specific DIs. Unresolved conflicts yield inconsistent normality concepts, that can be detected by queries of the form NC ⊑ ⊥.

The priority relation is a parameter of DLN. The full paper considers both the specificity-based priority of rational closure and a simpler kind of specificity adopted by circumscribed DLs [Bonatti et al., 2015a], namely: δ1 ≺ δ2 iff

The expression KB |≈ α means that α is a DLN consequence of KB. Due to space limitations, we do not report the model-theoretic definition of |≈ and present only its reduction to classical reasoning [Bonatti et al., 2015a]. For all subsumptions and assertions α, KB |≈ α holds iff KBΣ |= α, 1 where Σ is the set of normality concepts explicitly occurring in KB∪{α}, and KBΣ is a classical knowledge base obtained as follows (recall that KB = S ∪ D):

1 In this classical translation, normality concepts are treated like new concept names.

All results hold for specificity and other priority relations in PC , where C is the complexity of subsumption in DL

Table 2: Some complexity results

The informal meaning of δNC is: "NC's instances satisfy δ". Then, let ↓≺δ be the operator that removes from any axiom set S ′ ⊇ S all the δNC 0 that do not have higher priority than δ, preserving the axioms of KB:

Third, let δ1, . . . , δ|D| be any linearization of (D,≺). 2 Finally, let KBΣ = KBΣ|D| , where the sequence KBΣi (i = 1, 2, . . . , |D|) is inductively defined as follows:

In other words, the above sequence starts with KB's strong axioms S, extended with the inclusions NC ⊑ C, then processes the DIs δi in non-increasing priority order.

If δi can be consistently added to C's prototype, given all higher priority DIs selected so far (which is verified by checking that NC ̸⊑ ⊥ in line (3)), then its translation δNC i is included in KBΣ (i.e. δi "enters C's prototype"), otherwise δi is discarded, and we say that δi is overridden in NC.

The original semantics is refined in [Bonatti and Sauro, 2017] in order to infer NC ≡ ND when C ≡ D. The corresponding iterative construction of KBΣ is very similar: it suffices to replace equation (2) with

Using the construction of KBΣ and the equivalence between KB |≈ α and KBΣ |= α it is not hard to prove that:

1. If DL belongs to a deterministic time complexity class C, then DLN preserves its complexity;
2. if C is nondeterministic, then DLN belongs to P C .

In particular, DLN preserves tractability. Some examples - applying to EL/Dl-lite, ALC, and SROIQ, respectively - are reported in Table 2.

2 That is, {δ1, . . . , δ|D|} = D and for all i, j = 1, . . . , |D|, if δi ≺ δj then i < j. All linearizations yield the same KBΣ.

Mamm ⊑n ∃ lungs Mamm ⊑n ¬∃fins

SeaAnim ⊑n ∃fins Whales ⊑Mamm ⊓ SeaAnim

Dolphins ⊑ Mamm ⊓ SeaAnim ⊓ ∃ fins

Table 3: The KB formalizing the example

3 Behavior of DLN

A DI δ = (C ⊑n D) is roughly similar to a set of defaults stating, for each normality concept NE, that the instances of NE satisfy C ⊑ D unless stated otherwise (equivalently, δNE holds by default). The full paper and [Bonatti et al., 2015b; Bonatti and Sauro, 2017] contain several examples inspired by real applications, but here - due to space limitations - we resort to an old-fashioned example that illustrates several features of DLN at once.

Example 1 Let us formalize a domain where "by default, mammals have lungs and not fins, by default sea animals have fins, whales are both mammals and sea animals, dolphins are both mammals and sea animals and have fins". The axiomatization in DLN is reported in Table 3. The priority relation on DIs is specificity.

Both Dolphins and Whales are in the intersection of Mamm and SeaAnim, that have conflicting default properties concerning fins. Since Mamm and SeaAnim are incomparable, specificity does not settle the conflict.

However, dolphins are explicitly asserted to have fins; this assertion overrides the second default property of mammals thereby resolving the conflict. Still, Dolphins inherit the other default property of mammals (since DLN is not affected by inheritance blocking) so the attributes of standard dolphins are captured by the following inference, stating in formal terms that standard dolphins have both fins and lungs:

The definition of Whales, instead, is incomplete: the knowledge engineer forgot to settle the conflict. However, the need for additional knowledge can be easily identified by looking for inconsistent normality concepts: in DLN (where unresolved conflicts are not silently removed because a DI can be overridden only by axioms with strictly higher priority) whales inherit all the (mutually inconsistent) default properties of mammals and sea animals, therefore:

In other words, the standard concept consistency tests carried out during KB validation point out also unresolved conflicts.

In some logics, like circumscribed DLs and typicality DLs, the fact that dolphins are exceptional mammals would cause the set of such exceptional individuals to be minimized. So, in the direct equivalents of the above knowledge base, Dolphins would be inconsistent (Dolphins ⊑ ⊥). On the contrary, in DLN neither Dolphins nor NDolphins are inconsistent. If we further asserted that Moby is a whale, then circumscribed DLs and typicality DLs would infer Whales ≡ {Moby} while DLN would not.

Table 4: Variants of cautious monotony in DLN

Even if DLN has not been built with the KLM postulates in mind (because it has different goals), it often behaves in a quite similar way. In DLN there exist several analogues of the postulates; Table 4 illustrates the three variants investigated in [Bonatti and Sauro, 2017] 3 through the corresponding versions of cautious monotony.

With respect to version (A) of the postulates, DLN is cumulative. Moreover, if each consistent DL concept has at least one standard instance, then DLN satisfies all postulates. Interestingly, the same precondition is hardwired in the semantics of typicality logics through the smoothness condition, and a similar assumption was made in a first-order extension of the postulates [Lehmann and Magidor, 1990]. The cumulativity property shows that DIs significantly differ from default rules, since default logic is not cumulative.

Version (B) is affected by overriding. For instance, if the second premise of this variant of cautious monotony were overridden, then the conclusion would not be supported. On the other hand, if the premises are not overridden, then all the postulates of type (B) are valid in DLN. A first interesting remark is that a similar behavior can be observed in Lehmann's account of default reasoning [Lehmann, 1995]: there the postulates hold only if overridden defaults are ignored. The second interesting remark is that two of these postulates unconditionally hold in most practically interesting cases: (i) the OR rule holds if the priority relation is specificity; (ii) LLE (left logical equivalence) holds whenever the priority relation treats logically equivalent DIs in the same way (like specificity does).

Version (C) of the postulates is analogous to the postulates satisfied by typicality logics. It can be shown that typicality DLs satisfy these postulates because the normality criterion is assumed to be concept-independent (i.e. if John is more typical than Mary as a parent, then he must also be more typical than Mary as a driver, as a worker, as a tax payer, and so on). DLN does not embrace this strong assumption and - consequently - does not universally satisfy version (C) of Cut and Cautious Monotony. The latter interferes also with inconsistent prototypes (and the characteristic way DLN deals with unresolved conflicts):

Example 2 Consider the simple N-free KB consisting of:

Here the defeasible inclusions (5) and (6) together contradict the strong inclusion (4), but they have the same priority, therefore the conflict cannot be resolved in C, and its prototype is inconsistent (i.e. NC ⊑ ⊥). On the contrary, the instances of C ⊓ D, by definition, satisfy D (be they normal or not); then they belong to ¬E, by (4), so (6) is overridden and N(C ⊓D) is consistent. This shows that version (C) of cautious monotony does not hold. If it were applied, then N(C ⊓D) would be made inconsistent, too, which is difficult to justify: it is not clear why the strong facts N(C ⊓D) ⊑ D and (4) should not override (6) in the prototype of C ⊓D.

3 Version (B) is already studied in the full paper.

If N does not explicitly occur in KB (which in practice means, as explained in the full paper, that role fillers are not required to be normal, similarly to what inevitably happens in rational closure and default DLs) then all postulates in version (C) hold but cautious monotony (cf. Example 2); if there are no unresolved conflicts, then cautious monotony holds, too. So DLN is almost rational also with respect to version (C).

Given these results, it is not surprising that DLN returns the standard expected conclusions in many artificial examples occurring in the literature. Over a set of examples due to Sandewall, DLN and the DL introduced in [Casini and Straccia, 2013] (that combines rational closure and inheritance networks) make the same inferences if the same priority relation is used, with the exception of the examples involving unresolved conflicts. In these cases, of course, DLN highlights the conflicts while the other logic silently removes them (cf. Section 6.5 of the full paper).

4 Further Properties and Results

The following contents of the full paper could not be described in this abstract due to space limitations.

Usage and representation methodologies. We show how to deal with a variety of representation needs, introducing some nonmonotonic design patterns for fine-grained control on overriding and role ranges. The latter address a characteristic property of DLN not discussed here (but reported in Table 1), namely, the ability to specify whether role filler may include both standard and nonstandard individuals, or whether roles should range on standard individuals only.

Test case generation and validation. Benchmarking techniques and tools for nonmonotonic DL reasoners are still in a pretty early stage. We propose some general criteria for guiding the generation of benchmark tests, and some ex-post validation metrics to assess the quality of the synthetic test cases. These principles apply to all nonmonotonic DLs.

Inferring DIs. The model theoretic semantics of DLN provides a natural way of inferring further DIs from those explicitly contained in a KB. This feature might turn out to be helpful in optimizing inferences, e.g. by identifying redundant DIs or restructuring DIs in a way that speeds up automated reasoning. We prove that DI inference is in general more expensive than assertion/subsumption inference; its complexity in the general case is still unknown.

The work on implementations and optimizations is currently being completed with refined modularization, incrementality, and parallelization techniques. Additional experiments with knowledge bases of increasing size are being carried out to complete the assessment of the scalability of DLN.