On the Logical Properties of the Description Logic DL^N (Extended abstract)

1 Introduction

Recently, in [Bonatti et al., 2015a], a new nonmonotonic description logic called DLN has been introduced with the goal of supporting ontology authoring by means of nonmonotonic reasoning. DLN aims at removing some recurrent drawbacks of traditional nonmonotonic DLs 1 such as: (i) inheritance blocking, a drawback of preferential semantics and rational closure; (ii) undesired closed world assumption effects, that affect circumscription, typicality logic and some probabilistic logics; (iii) the inability to specify whether roles shall range over normal/prototypical individuals or not, that affects most nonmonotonic DLs. Moreover, DLN adopts a novel conflict resolution mechanism that helps in detecting unresolved conflicts between mutually inconsistent defaults. Since unresolved conflicts frequently correspond to missing knowledge, highlighting such conflicts constitutes an important support to knowledge base debugging and validation. A further useful property of DLN is that it can be translated into classical DLs, so that its implementations can rely on mature and well-optimized inference engines. The translation can be computed in polynomial time and does not involve complex constructs, so DLN preserves the tractability of the two major low-complexity families of DLs (EL and DL-lite, that correspond to the EL and QL profiles of OWL2, respectively). The experiments in [Bonatti et al., 2015a; 2015b] show unparalleled scalability properties over large knowledge bases, with more than 105 axioms. The relationships between the above features and the knowledge engineering requirements that have been independently introduced in the fields of biomedical ontologies and declarative policy languages have been extensively discussed in [Bonatti et al., 2015a].

∗This is an extended abstract of [Bonatti and Sauro, 2017].

1 Abbreviation for "description logics".

The main goal of this paper is studying the logical properties of DLN's consequence relation, defeasible axioms and normal instances. Our analysis includes a comparison of DLN's inferences with verbatim and internalized versions of the KLM postulates [Kraus et al., 1990]. For our purposes, these postulates are not necessarily desiderata, due to the loose correspondence between their motivations and DLN's goals and semantics (cf. [Bonatti et al., 2015a; Bonatti and Sauro, 2017]). However, we regard them as a useful technical tool for profiling and comparing the behavior of different logics, since the validity (or non-validity) of the postulates has been extensively investigated in most nonmonotonic logics.

In [Bonatti and Sauro, 2017] we fix also some technical problems affecting the original definition of DLN; here we skip these technical details due to space limitations.

2 The Basics of DLN

Let DL be any classical description logic language and let DLN be the extension of DL with a new concept name NC for each DL concept C. The new concepts are called normality concepts and denote the standard instances of C. Besides the usual axioms of DL, called classical or strong, DLN further supports new axioms called defeasible inclusions (DIs, for short) that are expressions C ⊑n D where C is a DL concept and D a DLN concept. The informal meaning of C ⊑n D, roughly speaking, is: "by default, the standard instances of any concept E should satisfy ¬C ⊔ D, unless stated otherwise", that is, unless some higher priority (possibly strong) axioms entail that the standard instances of E belong to C ⊓ ¬D; in that case, we say that C ⊑n D is overridden in E. The standard instances of a concept C (i.e., the members of NC) are required to satisfy all the DIs that are not overridden in C. We will call the set of DIs satisfied in NC the prototype associated to C.

DIs are prioritized by a strict partial order ≺. Such priority order is part of the knowledge base. It may be based on specificity, to make the defeasible properties of a class C override those of its superclasses, but it may also be based on time, to make more recent axioms override older axioms (as it is customary in law). If δ1 ≺ δ2, then δ1 has higher priority than δ2. DLN solves automatically only the conflicts that can be settled using ≺. Any other conflict shall be resolved by the knowledge engineer (typically by adding more DIs). Unresolved conflicts cause the affected concept C to have no standard instances, that is, NC ⊑ ⊥ is entailed by the knowledge base (in symbols: KB |≈ NC ⊑ ⊥). Thus unresolved conflicts can be detected by simple concept satisfiability tests, while all the other logics just hide the conflicts.

The papers [Bonatti et al., 2015a; 2015b; Bonatti and Sauro, 2017] contain examples inspired by real applications, but here - due to space limitations - we resort to an artificial 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 1. 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 Nonstandard DL axioms α ∨ β, ¬β can be simulated with the universal role;

|≈ denotes the nonmonotonic consequence relation of DLN; |= denotes classical inference.

All these rules hold when there are no unresolved conflicts.

Table 2: The KLM postulates in DLN

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.

3 Relationships with the KLMPostulates

In their seminal papers, Makinson [Makinson, 1988] and Kraus, Lehmann, and Magidor [Kraus et al., 1990; Lehmann and Magidor, 1992; Lehmann, 1995] argued that in order to reason about what normally holds in the world, it is desirable to make nonmonotonic consequence relations closed under certain properties, called KLM postulates, from the initials of their authors. 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; the verbatim instantiation of the original, meta-level postulates - in DLN's terminology - is illustrated in Table 2. With respect to this version of the postulates, DLN is cumulative, i.e. it satisfies the first five rules. The cumulativity property shows that DIs significantly differ from default rules, since default logic is not cumulative.

If each consistent DL concept has at least one standard instance (i.e. all unresolved conflicts have been removed), then DLN satisfies all postulates - that is, its consequence relation is rational. 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]. This is All these rules hold when their premises are not overridden.

Table 3: Internalized KLM postulates for DIs

incompatible with DLN's new conflict highlighting behavior. DLN does not only facilitate the identification of unresolved conflicts; it becomes also rational after such conflicts have been removed, thus one can satisfy the KLM axioms without giving up the knowledge base debugging aids of DLN.

Since OR and RM may be violated when a concept has an inconsistent prototype, an interesting open question is whether some KLM postulates are incompatible with the novel conflict highlighting mechanism of DLN.

In the full paper, we prove also that the rational closure of DLs itself does not satisfy the equivalent of OR in Table 2, but only an internalized version thereof, illustrated below. This raises an interesting research question: to what extent do the logics based on internalized KLM postulates satisfy their original, meta-level version?

Several logics internalize the nonmonotonic consequence relation and push the KLM postulates to the object level (e.g. [Casini and Straccia, 2010; 2011; 2013; Giordano et al., 2013; 2015]). A similar internalized version is reported in Table 3. This version of the KLM axioms is clearly affected by overriding. For instance, if the second premise of CMn were overridden, then there would be no logical ground for supporting the conclusion. However, if the premises are not overridden, then all the postulates of Table 3 are valid in DLN. It is very interesting to note that a similar phenomenon 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).

Table 4 reports another internalized version of the postulates, analogous to those satisfied by typicality logics [Gior- All the above rules hold if N occurs only in the queries and there are no unresolved conflicts.

Table 4: Candidate inference rules for N inspired by KLM postulates

dano et al., 2013; 2015]. In the full paper, we show that typicality DLs satisfy these postulates only 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 - for this reason - it does not universally satisfy CTN and CMN .

So an interesting open question is whether the postulates of Table 4 can possibly be satisfied by a logic that does not rely on a unique, concept independent normality relation.

CMN 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 (2) and (3) together contradict the strong inclusion (1), 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 (1), so (3) is overridden and N(C ⊓D) is consistent. This shows that CMN 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 (1) should not override (3) in the prototype of C ⊓ D.

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 Table 4 hold but CMN , that holds only if unresolved conflicts are removed first (cf. Example 2). So a fair comparison of DLN with the rational closure of DLs shows that the two logics are very similar, under the expressiveness restrictions of the latter.

Given these results, it is not surprising that DLN returns the standard expected conclusions in most of the artificial examples occurring in the literature. The only differences are due to the unique unresolved-conflict handling strategy of DLN. See the full paper for extensive, detailed examples on a set of benchmarks provided by Sandewall.

In the full paper we analyze also the interplay of N with the standard boolean operators. Table 5 illustrates some natural candidates. Not all of themmake sense. Normality concepts satisfy the following natural axiom schema:

which is strong, that is, it cannot be overridden. Axiom neg 1 follows from (4) and its contrapositive. It is easy to see that neg 2 is undesirable, instead. Together with (4) and neg 1 it implies NC ≡ C, that is, there could be no exceptional individuals, and there would be no difference between defeasible inclusions and strong axioms.

The axioms for ⊓ and ⊔ violate the goal of representing exceptions, too. Many motivational examples in the literature contradict and 2 and or 1 (see the full paper for examples). Accordingly, neither and 2 nor or 1 are valid in DLN.

Axioms and 1 and or 2 are more controversial. They are valid in some logics, but we believe that a flexible nonmonotonic logic should not always satisfy them, for the reasons explained below.

Example 3 (Drawbacks of and 1) Suppose the following facts hold. Most students (denoted by concept S) are not older than 25. Most employees (denoted by E) have a family income that exceeds e1000 per month. Most working students (S ⊓ E) are older than 25, being slowed down by their job, and their family income is less than e 1000 per month. It is natural to assert that, by default, the instances of NS are not older than 25, that the family income of the instances of NE is at least e 1000, and that the instances of N(S⊓E) are older than 25 and their family income is less than e 1000. Note that the default properties of N(S ⊓ E), in this case, are incompatible with those of NS and NE, so this natural approach at encoding the example is not compatible with and 1, that would force the instances of N(S ⊓ E) to contain the members of NS ⊓NE, that are younger than 25 and have a family income greater than e 1000.

The example showing the drawbacks of and 2 is not reported here due to space limitations. In typicality DLs, and 1 and or 2 are strong axioms, enforced by the underlying monotonic logic ALC +T. In the full paper (cf. Appendix B) we show that they are valid because the models of typicality logics adopt a single, concept-independent normality relation (as discussed above).

On the contrary, in DLN, and 1 and or 2 are not valid. Should they be appropriate in some application, they could be enforced by asserting them explicitly in the knowledge base. This is an interesting method for specializing DLN and tuning the set of its valid axioms when needed, so as to obtain maximum flexibility.

4 Conclusions

DLN is a flexible logic, where axioms like and 1 and or 2 - that seem not to be universally desirable - are not forced by the semantics and can be asserted if and when needed. The possibility of choosing different priority relations on DIs provides further flexibility and expressiveness. Even if the semantics of DLN has nothing to do with the typical foundations of the KLM postulates (like ranked interpretation and the exceptionality rankings of rational closure), still DLN satisfies the postulates to a significant extent. After all unresolved conflicts have been removed, all the meta-level postulates are satisfied. The internalized version for DIs is satisfied whenever the premises are not overridden, as in Lehmann's default logic (that introduced the lexicographic closure). The internalized postulates for N (Table 4) are satisfied only under stronger conditions, but the logics that currently satisfy those postulates adopt the debatable assumption that there is a unique, concept-independent notion of normality, that forces also the questionable axioms in Table 5. For all the above reasons, DLN constitutes a particularly nice tradeoff between the purely logical KLM desiderata, and the knowledge engineering needs analyzed in [Bonatti et al., 2015a].

The analysis of DLN in terms of the KLM postulates provides also a fine-grained comparison with other nonmonotonic DLs (see also Sec. 7 of the full paper).

The analysis of why some KLM postulates are not unconditionally satisfied in DLN led to the formulation of several research questions, some of which are currently being investigated by other authors. For example, the unique, concept-independent normality relation of ranked interpretations is now being replaced with multiple normality relations in ongoing works such as [Giordano and Gliozzi, 2018; Britz and Varzinczak, 2017]. Hopefully, these investigations will tell whether the KLM postulates can be enforced in a semantics that supports multiple, contextualized normality criteria, thereby addressing Example 3.