Defeasible Description Logics (DDLs) extend Description Logics with defeasible concept inclusions. Reasoning in DDLs often employs rational or relevant closure according to the (propositional) KLM postulates. If in DDLs with quanti cation a defeasible subsumption relationship holds between concepts, this relationship might also hold if these concepts appear in existential restrictions. Such nested defeasible subsumption relationships were not detected by earlier reasoning algorithms|neither for rational nor relevant closure. Recently, we devised a new approach for EL? that alleviates this problem for rational closure by the use of typicality models that extend classical canonical models by domain elements that individually satisfy any amount of consistent defeasible knowledge. In this paper we lift our approach to relevant closure and show that reasoning based on typicality models yields the missing entailments.
Description Logics (DLs) are usually decidable fragments of First Order Logic. In DLs concepts describe groups of objects by means of other concepts (unary FOL predicates) and roles (binary relations). Such concepts can be related to other concepts as sub- and super-concepts in the TBox which is essentially a theory constraining the interpretation of the concepts. One of the main reasoning problems in DLs is to compute subsumption relationships between two given concepts, i.e., decide whether all instances of one concept must be necessarily instances of the other (w.r.t. the TBox).
While classical DLs allow only for monotonic reasoning, defeasible DLs
admit a form of non-monotonic reasoning and have been intensively studied in the
last years [
We consider here an extension of the lightweight DL EL. In this DL complex
concepts are built by conjunctions and existential restrictions, which are a form
of quanti cation and clearly not expressible by propositional logic. The DL EL
enjoys good computational properties: subsumption can be computed in
polynomial time [
In [
The goal of this paper is to devise a reduction algorithm for reasoning under
relevant closure for EL? that derives defeasible knowledge for concepts nested in
existential restrictions. We have recently devised an approach that achieves this
for reasoning under the weaker rational closure by the use of typicality models
[
This paper is structured as follows: the next section introduces the basic
notions of (D)DLs and EL?. Section 3 recalls the materialisation-based approach
for rational and relevant closure and investigates their shortcomings. Section 4
introduces minimal typicality models over a lattice domain and shows that the
same subsumption relationships under relevant closure can be inferred as by the
materialisation-based approach from [
We introduce here the basic notions of (defeasible) DLs and their inferences. Starting from the two disjoint sets NC of concept names and NR of role names, complex concepts can be de ned inductively. Let C and D be EL-concepts and r 2 NR, then (complex) EL-concepts are: named concepts (A 2 NC ), the topconcept >, conjunctions C u D and existential restrictions 9r:C. The DL EL? extends EL by the bottom-concept ?, which can be used in conjunctions and existential restrictions. We will occasionally also use the concepts negation :C and disjunction C t D. The semantics of concepts is given by means of interpretations. An interpretation I = ( I ; I ) consists of an interpretation domain
I and a mapping function that assigns subsets of the domain I to concept names and binary relations over I to role names. The top-concept is interpreted as the whole domain (>I = I ) and the bottom-concept as the empty set (?I = ;). The complex concepts are interpreted as follows: conjunction (C uD)I = CI \DI , negation (:C)I = I nCI , disjunction (C tD)I = CI [DI , and existential restriction (9r:C)I = fd 2 I j 9e:(d; e) 2 rI and e 2 CI g. If in an interpretation I (d; e) 2 rI holds, then e is called a role successor of d.
DL ontologies can state (monotonous) relationships between concepts. Let C and D be concepts. A general concept inclusion axiom (GCI) is of the form: C v D. A TBox T is a nite set of GCIs. A concept C is satis ed by an interpretation I i CI 6= ;. A GCI C v D is satis ed in an interpretation I, i CI DI (written I j= C v D). An interpretation I is a model of a TBox T , i I satis es all GCIs in T (written I j= T ). Based on the notion of a model, DL reasoning problems are de ned. A concept is consistent w.r.t. a TBox T i some model of T satis es the concept. A concept C is subsumed by a concept D w.r.t. a TBox T (written C vT D) i CI DI holds in all models I of T .
We x some notation to access parts of knowledge bases or concepts. Let X
denote a concept or a TBox, then sig(X) denotes the signature of X. We de ne
sigNC (X) = sig(X) \ NC and sigNR (X) = sig(X) \ NR. We also de ne the set
Qc(X) of quanti ed concepts in X as F 2 Qc(X) i 9r:F syntactically occurs
in X for some r 2 NR. In extensions of EL that are in the Horn fragment of DLs,
canonical models are widely used for reasoning [
In defeasible DLs it can be stated that instances of a concept are subsumed
by another concept as long as there is no contradicting information. A
defeasible concept inclusion (DCI) is of the form C @ D and states that C usually
entails D. A DBox D is a nite set of DCIs. A defeasible knowledge base (DKB)
K = (T ; D) consists of a TBox T and a DBox D. The de nitions for sig(X),
sigNC (X), sigNR (X) and Qc(X) extend to DBoxes or DKBs in the obvious way.
A materialisation of a DBox D is the concept D = dE@F 2D(:E t F ). The
semantics of DBoxes di er from the ones for TBoxes, since DCIs need not hold
at each element in the model whereas GCIs do. The satisfaction of DCIs for
d 2 I is captured by I; d j= D i 8G @ H 2 D:d 2 GI =) d 2 HI . Usually,
the semantics of DBoxes is given by means of ranked/ordered interpretations|
called preferential model semantics [
We want to develop a decision procedure for (defeasible) subsumption relationships between concepts, say C and D, w.r.t. a given DKB K under relevant closure. For the remainder of the paper we make two simplifying assumptions for the sake of ease of presentation. We assume w.l.o.g. that (1) concepts C and D appear syntactically in Qc(T ) which can be achieved by adding 9r:E v > with E 2 fC; Dg to T and (2) all quanti ed concepts in K are consistent i.e., 8F 2 Qc(K):F 6vT ? and thus ? 2= Qc(K).
To motivate our approach for reasoning under relevant closure in defeasible EL?, we discuss rst earlier approaches for this task and identify their main shortcoming. 3
We recall the reduction algorithms for reasoning by Casini et al. from [
While rational closure treats inconsistencies with the granularity of the
partitions Ei, relevant closure uses a more ne-grained treatment. To illustrate this,
let G @ H 2 E0 and assume that C is only consistent with D nE0 (or its subsets).
It need not hold, that (:G t H) u D n E0 u C vT ?, since the inconsistency
may be due to other DCIs in E0. Still G @ H is never used for reasoning about
C. This e ect is called inheritance blocking, as it might be possible to include
G @ H for reasoning about C, but other DCIs induce some inconsistency and so
block the inheritance of property G @ H for C. Relevant closure disregards only
DCIs that are relevant for the inconsistency of C, thereby averting inheritance
blocking. The notion of relevance is introduced in [
To present a simpli ed (but equivalent) version of the algorithm from [
1Such as a quantitative ranking of DCIs.
The following example illustrates the problem of inheritance blocking caused by rational closure, but not by minimal relevant closure.
Example 2. Let Kex1 = (Tex1; Dex1) with:
Tex1 = fBoss v W orker; Boss u 9superior:W orker v ?g; Dex1 = fW orker @ 9superior:Boss; W orker @ P roductive;
Boss @ Responsibleg, and partition(Dex1) = E0 = fW orker @ 9superior:Boss; W orker @ P roductiveg;
E1 = fBoss @ Responsibleg : Rational closure recognises the inconsistency Dex1 u Boss vTex1 ?, but it holds that Dex1 n E0 u Boss 6vTex1 ?. Thus Boss @ W orker u Responsible is entailed from Kex1, while Boss @ P roductive is not, even though the DCI W orker @ P roductive does not cause the inconsistency of Boss. For minimal relevant closure, J1 = fW orker @ 9superior:Bossg is the only Boss-justi cation w.r.t. Kex1. Therefore, the largest consistent DBox subset of Dex1 for reasoning about the concept Boss is D0 = fW orker @ P roductive; Boss @ Responsibleg, providing the consequence D0 u Boss vTex1 P roductive.
Example 2 also illustrates the issue caused by employing materialisation that is addressed in this paper. Materialising the DCI W orker @ P roductive to :W orker t P roductive in conjunction with 9superior:W orker yields a concept that is not subsumed by 9superior:P roductive. The defeasible information is unjustly disregarded when reasoning about quanti ed concepts yielding uniformly non-typical role successors. Hence, in Example 2, both rational and relevant closure (based on materialisation) are oblivious to the conclusion W orker @ 9superior:Responsible.
In order to achieve relevant entailment also for quanti ed concepts, DCIs need
to hold for concepts in (nested) existential restrictions. A naive idea to
extend the materialisation approach is to enrich all concepts in existential
restrictions with materialisations of the DBox. However, for Example 2, enriching the
concept 9superior:Boss with W orker @ 9superior:Boss to 9superior:(Boss u
(:W orker t 9superior:Boss)) leads to in nitely many such enriching steps (due
to Boss v W orker). Instead, our approach is to extend the canonical models
for the classical members of the EL-family to DDLs. Our new kind of models
captures varying amounts of DCIs from a DKB to be satis ed by role successors.
Their domain essentially consist of copies of the domain of a classical canonical
model for each set of DCIs. These typicality models were recently introduced by
us in [
In order to infer all the undefeated facts for a concept F , the representative domain element of F in a model needs to satisfy the largest subset of D that is still satis able together with the TBox. If minimal relevant closure is used, this subset is obviously DF . Now, in EL?-concepts a syntactical sub-concept F can occur in multiple existential restrictions (not top-level), causing several role successors in a model. These in turn might be able to satisfy any subset of DCIs \up to" DF each. To be able to capture elements satisfying any set of DCIs, typicality interpretations (potentially) need a representative domain element for each subset of the given DBox D. The subsets of D form a lattice. De nition 3. Let K = (T ; D) be a DKB. A complete lattice domain is de ned as K = SU D dUF j F 2 Qc(K) . A domain with fd;F j F 2 Qc(K)g
K is a lattice domain.
Typicality interpretations over a lattice domain are the basis for our semantics and we de ne under which conditions a DKB is satis ed in such interpretations. De nition 4 (model of K). Let K = (T ; D) be a DKB. A typicality interpretation I = ( I ; I ) over a lattice domain I is a model of K (written I j= K) i 1. I j= T and 2. I; dUF j= U for all U D, F 2 Qc(K).
We de ne when a defeasible subsumption relationship holds in a typicality interpretation over a lattice domain.
De nition 5. Let I be a typicality interpretation over a lattice domain. Then I satis es a defeasible subsumption C @ D (written I j= C @ D) i dDC 2 DI . C In order to construct a model for K by means of a TBox, we use auxiliary concept names from the set NCaux NC n sig(K) to introduce representatives for all F 2 Qc(K) for each subset of the given DBox. Given concept F and DBox D, we use FD 2 NCaux to de ne the extended TBox of F :
T D(F ) = T [ fFD v F g [ fFD u G v H j G @ H 2 Dg (1) Here fFD v F g ensures that all constraints on F hold for the auxiliary concept as well. The last set of GCIs in Eq. (1) ensures that every element in F I (for D I j= T D(F )) satis es the DCIs in D. The auxiliary concept F; introduced in the extended TBox T ;(F ) and the concept F from T have the same subsumers. Proposition 6. Let T be a TBox and F; G be concepts with sig(G) \ NCaux = ;. Then F vT G i F; vT;(F ) G.
The proof for this proposition as well as most results of this paper are given in
detail in the technical report [
K j FU 6vTU (F ) ?g and an interpretation mapping that satis es the following conditions for all dUF 2 LK : { dUF 2 ALK i FU vTU (F ) A, for A 2 sigNC (K) and { (dUF ; d;G) 2 rLK i FU vTU (F ) 9r:G, for r 2 sigNR (K).
Typicality models need not use the complete lattice domain of 2jDj jQc(K)j elements due to inconsistent combinations of the represented concept F , U and T . Note that LK is well-de ned, as the initial assumption that F 6vT ? holds (for all F 2 Qc(K)) implies that all d;F exist in LK by Prop. 6. Furthermore, it is not hard to show that Prop. 6 implies that LK, restricted to elements regarding the empty set of DCIs, is the classical canonical model for the EL? TBox T . Example 8 (Minimal typicality model). Consider again the DKB Kex1 from Example 2 with the consistent subsets of the DBox DW orker = Dex1, and DBoss = fW orker @ P roductive; Boss @ Responsibleg w.r.t. W orker and Boss, respectively. The subset-lattice of Dex1 and LKex1 are illustrated in Fig. 1 using obvious abbreviations. Note, that the domain elements are grouped in grey boxes according to the subset-lattice indicating which DBox subsets are satis ed by which domain elements. According to De nition 5, LKex1 j= W orker @ 9superior:Boss, as well as LKex1 j= Boss @ Responsible u P roductive, because dDWWorokrkeerr and dBDBososss satisfy DW orker and DBoss, respectively. Rational closure would select the DBox subset fBoss @ Responsibleg for reasoning about Boss and would therefore not conclude the latter subsumption.
For the minimal typicality model LK it can be shown that dCDC 2 DLK (Def. 5) is equivalent to reasoning with the extended TBox, i.e. deciding CDC vTDC (C) D. The following claim can be proved using this equivalence.
Lemma 9. Let K = (T ; D) be a DKB. Then the minimal typicality model LK over the lattice domain LK is a model of K. ;
DB
W
B
We want to characterise di erent entailment relations based on di erent kinds
of typicality models for a given DKB K which vary in the defeasible information
admitted for required role successors. We use minimal typicality models over a
lattice domain to characterise entailment of propositional nature j=p.
This form of entailment is called propositional since all role successors are
uniformly non-typical and thus DCIs are neglected for quanti ed concepts. Next,
we investigate the relationship between j=m (Sec. 3) and j=p. Our approach to
decide propositional entailments based on the extended TBox for a concept F ,
coincides with enriching F with the materialisation of the given DBox.
Lemma 11. Let T be a TBox T , D a DBox, and C, D be concepts, with sig(X)\
NCaux = ; (for X 2 fT ; D; C; Dg). Then D u C vT D i CD vTD(C) D.
Proof (sketch). The lemma is proven by induction on the size of D. The base case
is D = ; and thereby Prop. 6 holds. For the induction step, let D0 = D[fG @ Hg
and use the hypothesis that the claim holds for D. We do a case distinction for
(i) D u C v G and (ii) D u C 6v G. For case (i), it can be shown that reasoning
with C u H, yields the same consequences as reasoning with C. All elements in
C u H satisfying G, already satisfy H. Thus we can remove the introduced DCI
G @ H without losing any consequences. Hence, G @ H can be removed from
D0 and the induction hypothesis holds. In case (ii) we show that the added DCI
has no e ect on the reasoning. By the condition of this case, no element in C,
satisfying all DCIs in D, satis es G. Therefore, the presence of the DCI G @ H
does not a ect the reasoning allowing it to be removed in order to reduce the
induction step to the induction hypothesis. In both cases, both sides of the \i "
in the claim are reduced to their respective sides of the induction hypothesis
individually. Since the full proof is fairly long and technical, it is deferred to the
technical report [
Although the entailment relations j=m as introduced in [
Proof (sketch). K j=p C @ D is de ned as LK j= C @ D, i.e. dCDC 2 DLK
which is equivalent to CDC vTDC (C) D as shown in the technical report [
We illustrate by continuing on Example 8 how defeasible information is disregarded for nested existential restrictions and our proposed countermeasure. Example 13. Consider again the DKB Kex1 from Example 8, with LKex1 (as depicted in Fig. 1). No defeasible information is used for reasoning over the superior successors of dDWWorokrkeerr and thus LK 6j= W orker @ 9superior:Responsible. However, Boss @ Responsible remains undefeated for d;Boss. Instead of satisfying Boss @ Responsible at d;Boss, we can \upgrade" the existing superior relationship, e.g. (dDWWorokrkeerr ; d;Boss) to (dDWWorokrkeerr ; dfBoss@Responsibleg) |as illustrated in Boss Fig. 2 by the dashed arrows. Note that Figure 2 depicts only an excerpt of LKex1 for comprehensibility. Our method upgrades typicality of role successors as much as possible, as long as it does not result in inconsistencies. Here, this even yields the conclusion W orker @ 9superior:P roductive.
Upgrading the typicality of a role successor depends on the information present in the model. Di erent orders of such upgrade steps can yield di erent models of increased typicality. In order to handle sets of models over the same lattice domain , we need the notions of intersection and inclusion of models.
De nition 14. For two interpretations I; J over the same domain we de ne { I \ J = ( ; I\J ) with
AI\J = AI \ AJ (for A 2 NC ) and rI\J = rI \ rJ (for r 2 NR) { I J i 8A 2 NC :AI AJ and 8r 2 NR:rI rJ.
W B DB
W B
W DW
W ;
W B W B
W
W Fig. 2: Increasing typicality of role successors Using this de nition we can formalise the notion of \upgrading the typicality" of a typicality interpretation, i.e. introduce copies of role edges that point to elements representing the same concept, but satisfying more defeasible statements. De nition 15. Let I be a typicality interpretation over a lattice domain for K = (T ; D). The set of more typical role edges for a given role r is de ned as T RI (r) = f(dXG ; dUH0 ) 2
I
I n rI j 9 U
D:(dXG ; dUH ) 2 rI ^ U
U 0
DH g: Let I and J be typicality interpretations. J is a typicality extension of I i 1. J = I , 2. AJ = AI (for A 2 NC ), 3. rJ = rI [ R, where R T RI (r) (for r 2 sigNR (K)), and 4. 9r 2 sigNR (K): rI rJ . The set of all typicality extensions of a typicality interpretation I is typ(I).
With typicality extensions at hand we can transform typicality interpretations into a set of more typical interpretations. Unfortunately, this operation does not preserve the property of being a typicality model. Let us demonstrate this by Example 13, let Kex2 = (T ex2; Dex1), and T ex2 = T ex1 [ f9superior:Responsible v 9coworker:W orkerg. Since LKex2 coincides with LKex1 , Fig. 2 depicts a typicality extension of LKex2 according to Def. 15. However, the extension in Fig. 2 is no longer a model of T ex2, as the newly introduced GCI is no longer satis ed for dDW orker. It can be extended to a model by introducing a coworker successor for dDW orker that belongs to W orker. In order not to introduce unwanted inconsistencies, the successor in this new relationship needs to be picked such that it only contains the information strictly required by K, i.e. d;W orker. We formalise the particular model completions that we are interested in.
De nition 16. Let K = (T ; D) be a DKB and a lattice domain. An interpretation I = ( ; I ) is a model completion of an interpretation J = ( ; J ) i 1. J I, 2. I j= K, and 3. 8E 2 Qc(K):dUF 2 (9r:E)I =) (dUF ; d;E ) 2 rI (for any F 2 Qc(K) and U D). The set of all model completions of J is denoted as mc(J ).
An interpretation that is a model completion to itself is called a safe model and obviously satis es the properties of Def. 16, e.g. for some typicality interpretation J over a lattice domain, all interpretations in mc(J ) are safe models.
Since model completions introduce minimal typical role successors they may necessitate further typicality extensions. So, typicality extensions and model completions need to be applied alternatingly until a maximum is reached. Maximality for typicality extensions is characterised in the following way: a typicality interpretation I is typicality extensible i 9J 2 typ(I):mc(J ) 6= ;. Intuitively, a typicality interpretation is typicality extensible if it admits to some typicality extension that is, or can be completed to a safe model. Therefore, a typicality interpretation is maximal i it is not typicality extensible. To formalise the process of increasing typicality and completing to a model until reaching maximal typicality, we introduce some notation and an upgrade operator. Given a lattice domain , de ne the set of all safe models over as P ( ) = fJ j J = ( ; J ) ^ J 2 mc(J )g.
De nition 17. The typicality upgrade operator T : 2P ( ) ! 2P ( ) is de ned for S P ( ) as: 1. T (S) = S n fIg [ SJ 2typ(I) mc(J ), if I 2 S is typicality extensible, 2. T (S) = S, otherwise.
For a given set of model completions S P ( ), the xpoint of T is Tm(S) if Tm(S) = Tm+1(S) with T0(S) = S, Ti(S) = T (Ti 1(S)) (i > 0). The set of maximal typicality extensions of the typicality interpretations in S is typmax(S) = Tm(S).
It is clear that neither De nition 15 nor 16 supply unique typicality extensions or model completions, respectively. Thus the typicality upgrade operator is de ned over sets of typicality interpretations. Applying T to fIg easily leads to an exponential amount of typicality interpretations. The following example illustrates that this typicality extension can quickly lead to multiple di erent maximal typicality interpretations, starting from a single interpretation. Example 18. We extend the DKB from Example 8 to DKB Kex3 = (T ex3; Dex1) with the TBox T ex3 = T ex1 [ f9superior:9superior:Responsible v ?g. Let the role edge (dDW orker; d;W orker) 2 superiorLKex3 be upgraded to (dDW orker; dDW orker) and likewise (dDW orker; d;Boss) 2 superiorLKex3 to (dDW orker; dBDBososss ). If both of these upgrades exist in the same typicality extension J , it does not admit to a model completion, as dDW orker 2 (9superior:9superior:Responsible)J . The typicality upgrade (dDW orker; dfW orker@P roductiveg), however, is \allowed" to occur in
Boss a typicality extension, leading to the entailment of W orker @ 9superior:(Boss u P roductive). This shows that inheritance blocking can be remedied even for quanti ed concepts when upgrading typicality of successors in a lattice domain. It is clear that the above described process leads to a variety of maximal typicality models, and there are several ways to use these sets for our new entailment. Since in classical DL reasoning entailment considers all models, we pick semantics closely related to cautious reasoning here. To this end we build a single model that is canonical in the sense that it is contained in all maximal typicality models obtained from LK.
De nition 19. The relevant canonical model is RK = TI2typmax(fLKg) I.
Note that the intersection over all maximal typicality models is well-de ned as
typmax(fLKg) is nite and since LK is a safe model (i.e. LK 2 mc(LK)) it is not
empty, as shown in the technical report [
Lemma 20. The relevant canonical model RK is a model of the DKB K. The main argument in the proof of Lemma 20 is that the intersection of models in any set S P ( ) yields another model in P ( ). This result is ensured by Condition 3 of De nition 16 The relevant canonical model is used to decide nested relevant entailment of the form C @ D, which requires to propagate DCIs to concepts occurring in existential restKrictions. We capture this stronger and quanti er-aware relevant entailment.
De nition 21. Let K be a DKB. A defeasible subsumption relationship C @ D
holds under nested relevant entailment (written K j=q C @ D) i RK j= C @ D.
We are ready to state our main result: nested relevant entailment allows for
strictly more inferences than the materialisation-based relevant entailment from
[
Theorem 22. For two EL? concepts C, D and an EL? DKB K 1. K j=m C @ D =) K j=q C @ D, and 2. K j=m C @ D (6= K j=q C @ D
The rst Claim of Theorem 22 is not too hard to show, as J 2 typmax(fLKg)
implies that LK J and thus LK RK. Hence by De nition 5, LK j= C @ D
implies RK j= C @ D. The second claim can be supported by Example 13 and
is formally shown in the technical report [
Extending our work on rational closure [
In this paper we have extended a new approach for reasoning in DDLs to
characterise entailment under relevant closure (for deciding subsumption) in the
DDL EL?. The new approach is motivated by the observation that earlier
reasoning procedures for this problem do not treat existential restrictions in an
adequate way. The key idea is to extend canonical models such that for each
concept from the DKB, several copies representing di erent amounts of
defeasible information are introduced. The new semantics supports the propagation
of defeasible information to concepts nested in existential restrictions. It allows
for extensions to more expressive approaches, e.g. more expressive DLs. While
rational closure needs to consider only one sequence of increasing subsets of the
DBox [
There are several paths for future work. Besides the extensions to more
expressive DLs, an extension to ABox reasoning, i.e., reasoning about data, would
be an interesting topic to investigate. Furthermore, a completion-like algorithm
as for classical EL [