=Paper=
{{Paper
|id=Vol-2052/paper3
|storemode=property
|title=Context-based defeasible subsumption for dSROIQ
|pdfUrl=https://ceur-ws.org/Vol-2052/paper3.pdf
|volume=Vol-2052
|authors=Katarina Britz,Ivan Varzinczak
|dblpUrl=https://dblp.org/rec/conf/commonsense/BritzV17
}}
==Context-based defeasible subsumption for dSROIQ==
https://ceur-ws.org/Vol-2052/paper3.pdf
Context-based defeasible subsumption for dSROIQ
Katarina Britz Ivan Varzinczak
CSIR-SU CAIR, Stellenbosch University CRIL, Univ. Artois & CNRS
South Africa France
abritz@sun.ac.za varzinczak@cril.fr
Abstract soning over defeasible ontologies [Britz and Varzinczak,
2016a; 2017]. Our proposal built on previous work to resolve
The description logic dSROIQ is a decidable exten- two important ontological limitations of the preferential ap-
sion of SROIQ that supports defeasible reasoning in proach to defeasible reasoning in DLs — the assumption of
the KLM tradition. It features a parameterised pref- a single preference order on all objects in the domain of in-
erence order on binary relations in a domain of inter- terpretation, and the assumption that defeasibility is intrinsi-
pretation, which allows for the use of defeasible roles cally linked to argument form [Britz and Varzinczak, 2013;
in complex concepts, as well as in defeasible concept 2016b].
and role subsumption, and in defeasible role assertions.
In this paper, we address an important limitation both We achieved this by extending SROIQ with nonmono-
in dSROIQ and in other defeasible extensions of de- tonic reasoning features in the concept language, in subsump-
scription logics, namely the restriction in the semantics tion statements and in role assertions, via an intuitive notion
of defeasible concept subsumption to a single prefer- of normality for roles. This parameterised the idea of pref-
ence order on objects. We do this by inducing prefer- erence while at the same time introducing the notion of de-
ence orders on objects from preference orders on roles, feasible class membership. Defeasible subsumption allows
and use these to relativise defeasible subsumption. This for the expression of statements of the form “C is usually
yields a notion of contextualised defeasible subsump- subsumed by D”, for example, “Chenin blanc wines are usu-
tion, with contexts described by roles. ally unwooded”. In the extended language dSROIQ, one
can also refer directly to, for example, “Chenin blanc wines
that usually have a wood aroma”. We can also combine these
1 Introduction seamlessly, as in: “Chenin blanc wines that usually have a
SROIQ [Horrocks et al., 2006] is an expressive, yet decid- wood aroma are usually wooded”. This cannot be expressed
able Description Logic (DL) that serves as semantic founda- in terms of defeasible subsumption alone, nor can it be ex-
tion for the OWL 2 profile, on which several ontology lan- pressed w.l.o.g. using a typicality operator on concepts. This
guages of various expressivity are based. However, SROIQ is because the semantics of the expression is inextricably tied
still allows for meaningful, decidable extension, as new to the two distinct uses of the term ‘usually’.
knowledge representation requirements are identified. A However, even this generalisation leaves open the question
case in point is the need to allow for exceptions and de- of different, possibly incompatible, notions of defeasibility in
feasibility in reasoning over logic-based ontologies [Bon- subsumption, similar to those studied in contextual argumen-
atti et al., 2009; 2011; 2015; Britz et al., 2011; 2013a; tation [Amgoud et al., 2000; Bikakis and Antoniou, 2010].
2013b; Britz and Varzinczak, 2016a; Casini et al., 2015; In the statement “Chenin blanc wines are usually unwooded”,
Casini and Straccia, 2010; 2013; Giordano et al., 2013; 2015; the context relative to which the subsumption is normal is left
Sengupta et al., 2011]. Yet, SROIQ does not allow for the implicit – in this case, the style of the wine. In a different con-
direct expression of and reasoning with different aspects of text such as consumer preference or origin, the most preferred
defeasibility. (or normal, or typical) Chenin blanc wines may not correlate
Given the special status of subsumption in DLs in par- with the usual wine style. Wine x may be more exceptional
ticular, and the historical importance of entailment in logic than y in one context, but less exceptional in another context.
in general, past research efforts in this direction have fo- This represents a form of inconsistency in defeasible knowl-
cused primarily on accounts of defeasible subsumption and edge bases arising from the presence of named individuals in
the characterisation of defeasible entailment. Semantically, the ontology. The example illustrates why a single ordering
the latter usually takes as point of departure orderings on a on individuals does not suffice. It also points to a natural in-
class of first-order interpretations, whereas the former usually dex for relativised context, namely the use of preferential role
assume a preference order on objects of the domain. names previously proposed for dSROIQ.
Recently, we proposed a decidable extension of SROIQ In this paper, we therefore propose to induce preference
that supports defeasible knowledge representation and rea- orders on objects from preference orders on roles, and use
these to relativise defeasible subsumption. This yields a no- I := h∆I , ·I i, where ∆I is a non-empty set called the do-
tion of contextualised defeasible subsumption, with contexts main, and ·I is an interpretation function mapping concept
described by roles. names A ∈ C to subsets AI of ∆I (with oI a singleton if
The remainder of the paper is structured as follows: In o ∈ N), role names r ∈ R to binary relations rI over ∆I ,
Section 2 we present some DL background on SROIQ. In and individual names a ∈ I to elements of the domain ∆I ,
Section 3 we introduce the syntax of the extended language i.e., AI ⊆ ∆I , rI ⊆ ∆I × ∆I , aI ∈ ∆I . We extend
dSROIQ, and in Section 4 its semantics. The newly intro- ·I from role names to roles by letting uI := ∆I × ∆I and
duced defeasible language constructs are discussed in Sec- (r− )I := {(y, x) | (x, y) ∈ rI }, and to role chains by setting
tion 5, where we also give examples to illustrate their se- (r1 ◦ · · · ◦ rn )I := r1I ◦ · · · ◦ rnI .
mantics and use. Section 6 covers a number of rewriting As an example, let C := {A1 , A2 , A3 }, R := {r1 , r2 }
and elimination results required for effective reasoning with and I := {a1 , a2 , a3 }. Figure 1 depicts the interpreta-
dSROIQ knowledge bases. tion I1 = h∆I1 , ·I1 i, where ∆I1 = {xi | 1 ≤ i ≤
We shall assume the reader’s familiarity with the preferen- 9}, AI1 1 = {x1 , x4 , x6 }, AI2 1 = {x3 , x5 , x9 }, AI3 1 =
tial approach to non-monotonic reasoning [Kraus et al., 1990; {x6 , x7 , x8 }, r1I1 = {(x1 , x6 ), (x4 , x8 ), (x2 , x5 )}, r2I1 =
Lehmann and Magidor, 1992; Shoham, 1988]. Whenever {(x4 , x4 ), (x6 , x4 ), (x5 , x8 ), (x9 , x3 )}, aI1 1 = x5 , aI2 1 = x1 ,
necessary, we refer the reader to the definitions and results and aI3 1 = x2 .
in the relevant literature.
2 The description logic SROIQ I1 : ∆
I1
AI1 1 AI2 1
xa1 2 xa2 3 x3
In this section, we provide the basics of SROIQ [Horrocks
et al., 2006]. For space considerations, but also to avoid rep-
etition, we defer many of its technicalities to the upcoming r2 r1
sections. r1 x4 xa5 1 r2
The language of SROIQ is built upon a finite set of
atomic concept names C, of which N, the set of nominals, r2 r1 r2
is a subset, a finite set of role names R and a finite set of indi-
vidual names I such that C, R and I are pairwise disjoint. The x6 x7 x8 x9
AI3 1
universal role is denoted by u and the set of all roles is given
by R := R ∪ {r− | r ∈ R} ∪ {u}, where r− denotes the
inverse of r. With A, B, . . . we denote atomic concepts, with Figure 1: A SROIQ interpretation.
r, s, . . . roles, and with a, b, . . . individual names. A nominal
will also be denoted by o, possibly with subscripts. The notion of interpretation can be extended to interpret
The set of SROIQ complex concepts is the smallest set (complex) SROIQ concepts and to provide a notion of sat-
such that: >, ⊥ and every A ∈ C are concepts; if C and D
N
are concepts, r, s ∈ R, and n ∈ , then ¬C (concept com-
isfaction of GCIs, RIAs, individual and role assertions in a
way that will be made clear in Section 3.
plement), C u D (concept conjunction), C t D (concept dis-
junction), ∀r.C (value restriction), ∃r.C (existential restric-
tion), ∃r.Self (self restriction), ≥ ns.C (at-least restriction), 3 Context-based defeasible SROIQ
≤ ns.C (at-most restriction) are also concepts. With C, D . . . In this section, we present the syntax and semantics of an ex-
we denote complex SROIQ concepts. A more detailed de- tension to SROIQ to represent defeasible complex concepts
scription of the roles allowed in complex concept descriptions and subsumption. The logic presented here is an incremental
will be provided in Definitions 1 and 3. extension of dSROIQ, which was introduced recently [Britz
If C and D are concepts, then C v D is a general concept and Varzinczak, 2017] to add defeasible reasoning features to
inclusion axiom (GCI, for short), read “C is subsumed by D”. SROIQ. Previous work included various defeasible con-
C ≡ D is an abbreviation for both C v D and D v C. structs on concepts based on preferential roles, but only a sin-
Given C a concept, r ∈ R and a, b ∈ I, an individual gle preference order on objects. This was somewhat of an
assertion is an expression of the form a : C, (a, b) : r, (a, b) : anomaly, as pointed out by some reviewers and colleagues.
¬r, a = b or a 6= b. We address this anomaly by adding context-based orderings
A role inclusion axiom (RIA) is a statement of the form on objects that are derived from preferential roles. This turns
r1 ◦· · ·◦rn v r, where r1 , . . . , rn , r ∈ R\{u} and r1 ◦· · ·◦rn out to be a remarkably seamless yet very useful refinement.
denotes the composition of r1 , . . . , rn . A role assertion is Briefly, each preferential role r, interpreted as a strict partial
a statement of the form Fun(r) (functionality), Ref(r) (re- order on the binary product space of the domain, gives rise
flexivity), Irr(r) (irreflexivity), Sym(r) (symmetry), Asy(r) to a context-based order on objects as detailed in Definition 6
(asymmetry), Tra(r) (transitivity), and Dis(r, s) (role dis- below.
jointness), where r, s 6= u. A more detailed description of
the roles allowed in RIAs will be given in Definition 2. 3.1 Defeasibility in RBoxes
The semantics of SROIQ is in terms of the standard set Let inv : R −→ R be such that inv : r 7→ r− , if r ∈ R,
theoretic Tarskian semantics. An interpretation is a structure inv : r 7→ s, if r = s− , and inv : u 7→ u.
Let r1 , . . . , rn , r ∈ R \ {u}. A classical role inclusion ax- N
s ∈ Rs , and n ∈ , then ¬C (concept complement), C u D
iom is a statement of the form r1 ◦ · · · ◦ rn v r. A defeasible (concept conjunction), C t D (concept disjunction), ∀r.C
role inclusion axiom has the form r1 ◦ · · · ◦ rn @ (value restriction), ∃r.C (existential restriction), ∼r.C (de-
W
∼r, read “usu-
ally, r1 ◦ · · · ◦ rn is included in r”. A finite set of (classical feasible value restriction), −−∼|r.C (defeasible existential re-
or defeasible) role inclusion axioms (RIAs) is called a role striction), ∃r.Self (self restriction), −
∼|r.Self (defeasible self
−
hierarchy and is denoted by Rh . restriction), ≥ ns.C (at-least restriction), ≤ ns.C (at-most
Definition 1 ((Non-)Simple Role) Let r ∈ R and let Rh be restriction), & ns.C (defeasible at-least restriction), . ns.C
a role hierarchy. Then r is non-simple in Rh iff: (defeasible at-most restriction) are also concepts. With C we
denote the set of all complex concepts.
1. There is r1 ◦ · · · ◦ rn v r or r1 ◦ · · · ◦ rn @
∼r in Rh such
that n > 1, or Note that every SROIQ concept is a dSROIQ concept,
too. We shall use C, D . . ., possibly with subscripts, to denote
2. There is s v r or s @ ∼r in Rh such that s is non-simple, or complex dSROIQ concepts.
3. inv(r) is non-simple.
With Rn we denote the set of non-simple roles in Rh . Rs := 3.3 Context-based defeasible subsumption
R \ Rn is the set of simple roles in Rh . Given C, D ∈ C, C v D is a classical general concept inclu-
Intuitively, simple roles are those that are not implied by sion, read “C is subsumed by D”. C ≡ D is an abbreviation
the composition of roles. They are needed to restrict the type for both C v D and D v C.
of roles in certain concept constructors (see below), thereby The extension of dSROIQ we propose here includes
preserving decidability [Horrocks et al., 2006]. context-based defeasible subsumption statements in the
TBox. Given C, D ∈ C and r ∈ R, C @ ∼r D is a defeasi-
Definition 2 (Regular Hierarchy) A role hierarchy Rh is ble general concept inclusion, read “C is usually subsumed
regular if there is a strict partial order < on Rn such that: by D in the context r”. A dSROIQ TBox T is a finite set
1. s < r iff inv(s) < r, for every r, s in Rn , and of general concept inclusions (GCIs), whether classical or de-
2. every role inclusion in Rh is of one of the forms: feasible.
(1a) r ◦ r v r, (1b) r ◦ r @ ∼r, Before we present the semantics, we introduce the remain-
(2a) inv(r) v r, (2b) inv(r) @ ∼r, ing components of dSROIQ ontologies. Recall I is a set of
(3a) s1 ◦ · · · ◦ sn v r, (3b) s1 ◦ · · · ◦ sn @∼r, individual names disjoint from both C and R. Given C ∈ C,
(4a) r ◦ s1 ◦ · · · ◦ sn v r, (4b) r ◦ s1 ◦ · · · ◦ sn @
∼r, r ∈ R and a, b ∈ I, an individual assertion is an expression
(5a) s1 ◦ · · · ◦ sn ◦ r v r, (5b) s1 ◦ · · · ◦ sn ◦ r @
∼r, where of the form a : C, (a, b) : r, (a, b) : ¬r, a = b or a 6= b. A
r ∈ R (i.e., a role name), and si < r, for i = 1, . . . , n. dSROIQ ABox A is a finite set of individual assertions.
(Regularity prevents a role hierarchy from inducing cyclic de- Let A be an ABox, T be a TBox and R an RBox. A knowl-
pendencies, which are known to lead to undecidability.) edge base (alias ontology) is a tuple KB := hA, R, T i.
A classical role assertion is a statement of the form
Fun(r) (functionality), Ref(r) (reflexivity), Irr(r) (irreflexiv- 4 Preferential semantics
ity), Sym(r) (symmetry), Asy(r) (asymmetry), Tra(r) (tran- We shall anchor our semantic constructions in the well-
sitivity), and Dis(r, s) (role disjointness), where r, s 6= u. A known preferential approach to non-monotonic reason-
defeasible role assertion is a statement of the form dFun(r) (r ing [Kraus et al., 1990; Lehmann and Magidor, 1992;
is usually functional), dRef(r) (r is usually reflexive), dIrr(r) Shoham, 1988] and its extensions [Boutilier, 1994; Britz
(r is usually irreflexive), dSym(r) (r is usually symmetric), and Varzinczak, 2013; a; 2016b; b], especially those to the
dAsy(r) (r is usually asymmetric), dTra(r) (r is usually tran- DL case [Britz et al., 2011; Britz and Varzinczak, 2016a;
sitive), and dDis(r, s) (r and s are usually disjoint), also with Giordano et al., 2009; Quantz and Royer, 1992].
r, s 6= u. With Ra we denote a finite set of role assertions. Let X be a set and let < be a strict partial order on X.
Given a role hierarchy Rh , we say that Ra is simple With min< X := {x ∈ X | there is no y ∈ X s.t. y < x}
w.r.t. Rh if all roles r, s appearing in statements of the we denote the minimal elements of X w.r.t. <. With #X we
form Irr(r), dIrr(r), Asy(r), dAsy(r), Dis(r, s) or dDis(r, s) shall denote the cardinality of X.
are simple in Rh (see Definition 1).
A dSROIQ RBox is a set R := Rh ∪ Ra , where Rh is Definition 4 (Ordered Interpretation) An ordered inter-
a regular hierarchy and Ra is a set of role assertions which is pretation is a tuple O := h∆O , ·O , O i in which h∆O , ·O i
simple w.r.t. Rh . is a SROIQ interpretation with AO ⊆ ∆O , for every
A ∈ C, AO a singleton for every A ∈ N, rO ⊆ ∆O × ∆O ,
3.2 Defeasibility in concepts for all r ∈ R, and aO ∈ ∆O , for every a ∈ I, and
We now extend the set of SROIQ complex concepts via the O := h O O O O O
1 , . . . , #R i, where i ⊆ ri × ri , for i =
definition of concept constructors allowing for the expression 1, . . . , #R, and such that each O i satisfies the smoothness
of defeasibility at the object level. condition [Kraus et al., 1990].
Definition 3 (dSROIQ Concepts) The set of dSROIQ As an example, let C := {A1 , A2 , A3 }, R :=
complex concepts is the smallest set such that >, ⊥ and every {r1 , r2 }, I := {a1 , a2 , a3 }, and let the r-ordered in-
A ∈ C are concepts, and if C and D are concepts, r ∈ R, terpretation O1 = h∆O1 , ·O1 , O1 i, where ∆O1 =
∆I1 , ·O1 = ·I1 , and O1 = h O O1
1 , 2 i, where
1
O is used, we shall drop the subscript in O
i ):
O 1 =
1
{(x4 x8 , x2 x5 ), (x2 x5 , x1 x6 ), (x4 x8 , x1 x6 )} and >O := ∆O ; ⊥O := ∅; (¬C)O := ∆O \ C O ;
O1
2 = {(x6 x4 , x4 x4 ), (x5 x8 , x9 x3 )}. (For the sake of read-
ability, we shall henceforth sometimes write tuples of the (C u D)O := C O ∩ DO ; (C t D)O := C O ∪ DO ;
form (x, y) as xy.) Figure 2 below depicts the r-ordered inter- (∀r.C)O := {x | rO (x) ⊆ C O };
pretation O1 . In the picture, O O1
1 and 2 are represented,
1
(∼r.C)O := {x | min O (rO|x )(x) ⊆ C O };
W
respectively, by the dashed and the dotted arrows. (Note the
(∃r.C)O := {x | rO (x) ∩ C O 6= ∅};
direction of the O -arrows, which point from more preferred
to less preferred pairs of objects.) Also for the sake of read- (−
∼|r.C)O := {x | min O (r O|x )(x) ∩ C O 6= ∅};
−
ability, we shall omit the transitive O -arrows. (∃r.Self)O := {x | (x, x) ∈ rO };
(−
∼|r.Self)O := {x | (x, x) ∈ min O (r O|x )};
−
∆O
O:
AO
1 AO
2
(≥ nr.C)O := {x | #rO (x) ∩ C O ≥ n};
xa1 2 xa2 3 x3
(≤ nr.C)O := {x | #rO (x) ∩ C O ≤ n};
r2 r1 (& nr.C)O := {x | # min O (rO|x )(x) ∩ C O } ≥ n;
(. nr.C)O := {x | # min O (rO|x )(x) ∩ C O ≤ n}.
r1 x4 xa5 1 r2
It is not hard to see that, analogously to the classical case,
r2 r1 r2 ∼ and −
W
∼|, as well as & and ., are dual to each other.
−
Definition 6 (Satisfaction) Let O = h∆O , ·O , O i and let
x6 x7 x8 x9
AO
3
r1 , . . . , rn , r, s ∈ R, C, D ∈ C, and a, b ∈ I. Let ≺O r :=
{(x, y) | there is some (x, z) ∈ rO such that for all (y, v) ∈
rO [((x, z), (y, v)) ∈ O r ]}. The satisfaction relation is
Figure 2: A dSROIQ ordered interpretation. defined as follows:
O r v s if rO ⊆ sO ;
Given O = h∆O , ·O , O i, the intuition of ∆O and ·O
O r@ O
∼ s if min O r ⊆ s ;
O
is the same as in a standard DL interpretation. The intu-
ition underlying each of the orderings in O is that they play O r1 ◦ · · · ◦ rn v r if (r1 ◦ · · · ◦ rn )O ⊆ rO ;
the role of preference relations (or normality orderings), in a O r1 ◦ · · · ◦ rn @ O
∼r if min O (r1 ◦ · · · ◦ rn ) ⊆ r ;
O
sense similar to that introduced by Shoham [Shoham, 1988] O O
Fun(r) if r is a function;
with a preference on worlds in a propositional setting and as
O dFun(r) if for all x, # min O (rO|x )(x) ≤ 1;
extensively investigated by Kraus et al. [Kraus et al., 1990;
Lehmann and Magidor, 1992] and others [Boutilier, 1994; O Ref(r) if {(x, x) | x ∈ ∆O } ⊆ rO ;
Britz et al., 2008; Giordano et al., 2007]: the pairs (x, y) O dRef(r) if for every x ∈ min≺O u
∆O , (x, x) ∈ rO ;
that are lower down in the ordering O i are deemed as the O Irr(r) if rO ∩ {(x, x) | x ∈ ∆O } = ∅;
most normal (or typical, or expected) in the context of (the O dIrr(r) if for every x ∈ min≺O ∆O , (x, x) ∈
/ rO ;
interpretation of) ri . Technically, the difference between our u
O
definitions and those in the aforementioned work lies on the O Sym(r) if inv(r) ⊆ rO ;
fact that our Oi are orderings on binary relations on the do- O dSym(r) if min O (r− )O ⊆ rO ;
main ∆O , instead of orderings on propositional valuations or O
O
Asy(r) if rO ∩ inv(r) = ∅;
on plain objects of ∆O .
O dAsy(r) if min O rO ∩ min O (r− )O = ∅;
In the following definition we show how ordered interpre- O Tra(r) if (r ◦ r)O ⊆ rO ;
tations can be extended to interpret the complex concepts of O dTra(r) if min O (r ◦ r)O ⊆ rO ;
the language.
O Dis(r, s) if rO ∩ sO = ∅;
Definition 5 (O extended) Let O = h∆O , ·O , O i. O dDis(r, s) if min O rO ∩ min O sO = ∅;
For any r, r1 , r2 ∈ R \ {u}, O interprets orderings O C v D if C O ⊆ DO ;
on role inverses and on role compositions as follows: O C@∼r D if min≺O r
C O ⊆ DO ;
O r−
:= {((y1 , x1 ), (y2 , x2 )) | ((x1 , y1 ), (x2 , y2 )) ∈ O r }, O a : C if aO ∈ C O ; O (a, b) : r if (aO , bO ) ∈ rO ;
and O r1 ◦r2 := {((x 1 , y1 ), (x 2 , y2 )) | for some z 1 , z2 O (a, b) : ¬r if O 6 (a, b) : r;
[((x1 , z1 ), (x2 , z2 )) ∈ O r1 and ((z ,
1 1 y ), (z ,
2 2 y )) ∈ O
r2 ], O a = b if aO = bO ; O a 6= b if O 6 a = b.
O
and for no z1 , z2 [((x2 , z2 ), (x1 , z1 )) ∈ r1 and ((z2 , y2 ),
O|x If O α, then we say O satisfies α. O satisfies a set of
(z1 , y1 )) ∈ O r2 ]}. Moreover, let ri := riO ∩ ({x} × ∆O ) statements or assertions X (denoted O X) if O α for
(i.e., the restriction of the domain of riO to {x}). The every α ∈ X, in which case we say O is a model of X. We
interpretation function ·O interprets dSROIQ concepts in say C ∈ C is satisfiable w.r.t. KB = hA, R, T i if there is a
the following way (whenever it is clear which component of model O of KB s.t. C O 6= ∅, and unsatisfiable otherwise.
A statement α is (classically) entailed by a knowledge since it shows the more traditional preference ordering on all
base KB, denoted KB |= α, if every model of KB satisfies α. objects in the domain to be a special case of our proposal.
Lemma 2 shows that the converse of Lemma 1 holds in the
5 Modelling with dSROIQ ontologies more general case of any context-based preference order O r .
The motivation for dSROIQ is to represent defeasible Lemma 1 Given domain ∆O and strict partial order ≺ on
knowledge, and to reason over defeasible ontologies. We now ∆O , let O O
u := {((x, z), (y, z)) | x ≺ y}, and let ≺u be as
O
consider the different aspects of defeasibility that can be ex- in Definition 6. Then ≺ = ≺u .
pressed in dSROIQ. We first consider defeasible existential Lemma 2 Let O = h∆O , ·O , O i, and let ≺O r be as in Def-
restriction: inition 6. Then ≺O O
r is a strict partial order on ∆ .
Cheninblanc u −
∼| hasAroma.Wood v ∃hasStyle.Wooded
− Corollary 1 Let ≺ be a strict partial order on ∆O , and let
O C@ O O
∼D iff min≺ C ⊆ D . Then universal defeasible
This statement is read: “Chenin blanc wines that normally subsumption ∼u has the same semantics as @
@ ∼.
have a wood aroma are wooded”. That is, any Chenin blanc
wine that has a characteristic wood aroma, has a wooded wine Corollary 1 makes the intuition of universal defeasible sub-
style. For an example of defeasible subsumption, consider the sumption clear. For the more general parameterised case, the
statement intuition is essentially the same. Consider the role hasOrigin,
which links individual wines to origins. Wine x is considered
Cheninblanc @
∼u ∃hasAroma.Floral more typical (or less exceptional) than y w.r.t. its origin if it
has some origin link which is preferred to any such link from
which states that Chenin blanc wines usually have some floral y.
aroma. That is, the most typical Chenin blanc wines all have Context-based defeasible subsumption @
some floral aroma. Similarly, ∼r can therefore
also be viewed as defeasible subsumption based on a prefer-
Cheninblanc @ ence order on objects in the domain of rO , bearing in mind
∼u ∀hasOrigin.Loire
that in any given interpretation, it is dependent on O r . This
states that Chenin blanc wines usually come only from the raises the question whether a preference order on objects in
Loire Valley. Now suppose we have a Chenin blanc wine x, the range of rO could be considered as an alternative, but
which comes from the Loire Valley but does not have a floral since role inverses are allowed in context-based defeasible
aroma, and another Chenin blanc wine y which has a floral subsumption, @ ∼inv(r) achieves this.
aroma but comes from Languedoc. No model of this ontology
The following result shows that context-based defeasible
can simultaneously have x ≺u y w.r.t. origin and y ≺u x
subsumption is indeed an appropriate notion of defeasible
w.r.t. aroma. There can therefore be no model that accurately
subsumption:
models reality.
This is precisely the limitation imposed by having only a Lemma 3 For every r ∈ R, @ ∼r is a preferential subsump-
single ordering on objects, as usually assumed by preferen- tion relation on concepts in that, for every O, the following
tial approaches to defeasible DLs [Britz et al., 2008; 2011; properties hold:
Giordano et al., 2007; 2009; 2013], and the motivation for O C ≡ D, O C @ ∼r E
(Ref) O C@
∼r C (LLE)
introducing context-based defeasible subsumption. Although O D@ ∼r E
the two defeasible statements are not inconsistent, the pres- O C@ @
∼r D, O C ∼r E O C@ @
∼r E, O D ∼r E
ence of both rules out certain intended models. In contrast, (And) (Or)
O C@ ∼r D u E O C tD@ ∼ E
r
with context-based defeasible subsumption, both subsump-
O C@
∼r D, O D v E O C@ @
∼r D, O C ∼r E
tion statements can be expressed and x and y can have in- (RW) (CM)
O C@ ∼ E
@
O C u D ∼r E
compatible preferential relationships in the same model: r
It is not hard to show that, moreover, if the ordering associ-
Cheninblanc @
∼hasAroma ∃hasAroma.Floral ated to a role r is modular, the defeasible subsumption @ ∼r it
Cheninblanc @
∼hasOrigin ∀hasOrigin.Loire induces is also rational, i.e., it satisfies the following rational
monotonicity property:
Note that this knowledge base cannot be changed to:
O C@ ∼r D, O C 6∼r ¬C
@ 0
Cheninblanc v −
∼|hasAroma.Floral
− (RM)
Cheninblanc v ∼hasOrigin.Loire
W O C uC @ 0
∼ D
r
A further feature of context-based subsumption is therefore
as the latter states that every Chenin blanc wine has a char- the ability to allow for both rational and preferential-only sub-
acteristic floral aroma and is usually exclusive to the Loire sumption relations.
Valley (ruling out the possibility of a Chenin blanc without a
floral aroma, or one that comes only from Languedoc).
Lemma 1 below shows that every strict partial order on
6 Eliminating ABoxes, classical GCIs and the
objects in the domain ∆O can be obtained from some strict universal role
partial order on ∆O × ∆O as in Definition 6. This justifies As for classical SROIQ [Horrocks et al., 2006, Lemma 7],
the use of @ ∼u in defeasible subsumption statements where it is possible to eliminate an ABox A by compiling all indi-
the context is universal. It also supports the definition of ≺O
u , vidual assertions in A as follows:
1. Let N0 := N ∪ {oa | a appears in A} (i.e., extend the The definitions and preliminary results reported in this pa-
signature with new nominals); per raise a number of immediate questions:
2. Let A0 := {a : C ∈ A}∪{a : ∃r.ob | (a, b) : r ∈ A}∪{a : • How to obtain the other direction of the KLM-style repre-
∀r.¬ob | (a, b) : ¬r ∈ A} ∪ {a : ¬ob | a 6= b ∈ A}; sentation result (cf. Lemma 3)?
3. For every C ∈ C, let C 0 := C u a:D∈A0 ∃u.(oa u D).
d
• How to reduce satisfiability w.r.t. defeasible TBoxes and
It is then easy to see that C is satisfiable w.r.t. hA, R, T i if RBoxes to satisfiability w.r.t. only defeasible RBoxes?
and only if C 0 is satisfiable w.r.t. h∅, R, T i, which allows us
• How to extend the tableau system for dSROIQ to ac-
to assume from now on and w.l.o.g. that ABoxes have been
count for multi-defeasible subsumptions of the kind we in-
eliminated.
troduced here?
Next, in the same way that most of the classical role asser-
tions can equivalently be replaced by GCIs or RIAs, under our • How to define and compute rational closure of a family of
preferential semantics, all of our defeasible role assertions, defeasible concept inclusions?
with the exception of dAsy(·) and dDis(·), can be reduced to • Can a notion of context, together with our more expres-
defeasible RIAs in the following way. dFun(r) can be re- sive language, give rise to new KLM-style postulates char-
placed by > v. 1r.> — to be ‘usually functional’ means acterising defeasible subsumption relations that are more
only non-normal arrows can break functionality. (Note that, powerful than the rational ones?
since the number restriction is unqualified, r need not be sim-
ple.) dRef(r) and dIrr(r) can, respectively, be replaced with These are some of the questions that will drive future investi-
>@ @
∼∃r.Self and > ∼¬∃r.Self. dSym(r) can be reduced to gation of the topic.
r− @∼ r and dTra(r) to r◦r @
∼r. Furthermore, note that dAsy(r)
can be reduced to dDis(r, r− ) (cf. Definition 6). Hence, from Acknowledgements
now on we can assume, w.l.o.g., that the set of role asser-
tions Ra contains only statements of the form Dis(r, s) and This work is based on research supported in part by the Na-
dDis(r, s). tional Research Foundation of South Africa (Grant Numbers
Finally, we can apply the same procedure for eliminat- 103345 and 85482).
ing both all classical TBox statements and the universal
role u defined for classical SROIQ [Horrocks et al., 2006, References
Lemma 8][Schild, 1991], extended to the case of dSROIQ
concepts. Hence, from now on we can assume that all [Amgoud et al., 2000] L. Amgoud, S. Parsons, and L. Per-
classical concept subsumptions (as well as occurrences of u russel. An argumentation framework based on contex-
therein) have been eliminated. tual preferences. In Proceedings of the International Con-
The next theorem summarises the reduction outlined in this ference on Formal and Applied and Practical Reasoning
section: (FAPR), pages 59–67, 2000.
Theorem 1 Let KB = hA, R, T i and let D := {C @ [Bikakis and Antoniou, 2010] A. Bikakis and G. Antoniou.
∼r D |
C@ ∼r D ∈ T }. Satisfiability of dSROIQ-concepts w.r.t. KB
Defeasible contextual reasoning with arguments in ambi-
can be polynomially reduced to satisfiability of dSROIQ- ent intelligence. IEEE Transactions on Knowledge and
concepts w.r.t. h∅, R, Di where all role assertions in R are of Data Engineering, 22(11):1492–1506, 2010.
the form Dis(r, s) and dDis(r, s). [Bonatti et al., 2009] P. Bonatti, C. Lutz, and F. Wolter. The
We leave an investigation of a reduction of the axioms in D complexity of circumscription in description logic. Jour-
for future work. nal of Artificial Intelligence Research, 35:717–773, 2009.
[Bonatti et al., 2011] P. Bonatti, M. Faella, and L. Sauro. De-
7 Concluding remarks feasible inclusions in low-complexity DLs. Journal of Ar-
In this paper, we have made a case for a context-based notion tificial Intelligence Research, 42:719–764, 2011.
of defeasible concept inclusion in description logics. We have
[Bonatti et al., 2015] P. Bonatti, M. Faella, I.M. Petrova, and
seen that roles can be used to provide a simple yet powerful
context for such a notion. We have shown how the semantics L. Sauro. A new semantics for overriding in description
of the resulting family of defeasible subsumption relations logics. Artificial Intelligence, 222:1–48, 2015.
can be anchored to that of preferential roles, which we studied [Boutilier, 1994] C. Boutilier. Conditional logics of normal-
in previous work. ity: A modal approach. Artificial Intelligence, 68(1):87–
From the knowledge-representation standpoint, context- 154, 1994.
based subsumption provides the user with more flexibility [Britz and Varzinczak, a] K. Britz and I. Varzinczak. From
in making defeasible statements in ontologies. From a mod-
KLM-style conditionals to defeasible modalities, and
elling point of view, the semantic characterisation we propose
back. To appear.
here resolves an important limitation of many defeasible ex-
tensions of description logics, namely the restriction in the [Britz and Varzinczak, b] K. Britz and I. Varzinczak. Prefer-
semantics of defeasible concept subsumption to a single pref- ential accessibility and preferred worlds. Journal of Logic,
erence order on objects. Language and Information. To appear.
[Britz and Varzinczak, 2013] K. Britz and I. Varzinczak. De- [Giordano et al., 2007] L. Giordano, V. Gliozzi, N. Olivetti,
feasible modalities. In Proceedings of the 14th Confer- and G.L. Pozzato. Preferential description logics. In
ence on Theoretical Aspects of Rationality and Knowledge N. Dershowitz and A. Voronkov, editors, Logic for Pro-
(TARK), pages 49–60, 2013. gramming, Artificial Intelligence, and Reasoning (LPAR),
[Britz and Varzinczak, 2016a] K. Britz and I. Varzinczak. number 4790 in LNAI, pages 257–272. Springer, 2007.
Introducing role defeasibility in description logics. In [Giordano et al., 2009] L. Giordano, V. Gliozzi, N. Olivetti,
L. Michael and A.C. Kakas, editors, Proceedings of the and G.L. Pozzato. ALC + T : a preferential extension of
15th European Conference on Logics in Artificial Intelli- description logics. Fundamenta Informaticae, 96(3):341–
gence (JELIA), number 10021 in LNCS, pages 174–189. 372, 2009.
Springer, 2016. [Giordano et al., 2013] L. Giordano, V. Gliozzi, N. Olivetti,
[Britz and Varzinczak, 2016b] K. Britz and I. Varzinczak. and G.L. Pozzato. A non-monotonic description logic
Preferential modalities revisited. In Proceedings of the for reasoning about typicality. Artificial Intelligence,
16th International Workshop on Nonmonotonic Reasoning 195:165–202, 2013.
(NMR), 2016. [Giordano et al., 2015] L. Giordano, V. Gliozzi, N. Olivetti,
[Britz and Varzinczak, 2017] K. Britz and I. Varzinczak. To- and G.L. Pozzato. Semantic characterization of rational
wards defeasible dSROIQ. In Proceedings of the 30th closure: From propositional logic to description logics.
International Workshop on Description Logics, volume Artificial Intelligence, 226:1–33, 2015.
1879. CEUR Workshop Proceedings, 2017. [Horrocks et al., 2006] I. Horrocks, O. Kutz, and U. Sattler.
[Britz et al., 2008] K. Britz, J. Heidema, and T. Meyer. The even more irresistible SROIQ. In P. Doherty, J. My-
Semantic preferential subsumption. In J. Lang and lopoulos, and C. Welty, editors, Proceedings of the 10th In-
G. Brewka, editors, Proceedings of the 11th International ternational Conference on Principles of Knowledge Rep-
Conference on Principles of Knowledge Representation resentation and Reasoning (KR), pages 57–67. Morgan
and Reasoning (KR), pages 476–484. AAAI Press/MIT Kaufmann, 2006.
Press, 2008. [Kraus et al., 1990] S. Kraus, D. Lehmann, and M. Magidor.
[Britz et al., 2011] K. Britz, T. Meyer, and I. Varzinczak. Se- Nonmonotonic reasoning, preferential models and cumu-
mantic foundation for preferential description logics. In lative logics. Artificial Intelligence, 44:167–207, 1990.
D. Wang and M. Reynolds, editors, Proceedings of the [Lehmann and Magidor, 1992] D. Lehmann and M. Magi-
24th Australasian Joint Conference on Artificial Intelli- dor. What does a conditional knowledge base entail? Ar-
gence, number 7106 in LNAI, pages 491–500. Springer, tificial Intelligence, 55:1–60, 1992.
2011. [Quantz and Royer, 1992] J. Quantz and V. Royer. A pref-
[Britz et al., 2013a] K. Britz, G. Casini, T. Meyer, K. Mood- erence semantics for defaults in terminological logics. In
ley, and I. Varzinczak. Ordered interpretations and entail- Proceedings of the 3rd International Conference on Prin-
ment for defeasible description logics. Technical report, ciples of Knowledge Representation and Reasoning (KR),
CAIR, CSIR Meraka and UKZN, South Africa, 2013. pages 294–305, 1992.
[Britz et al., 2013b] K. Britz, G. Casini, T. Meyer, and [Schild, 1991] K. Schild. A correspondence theory for ter-
I. Varzinczak. Preferential role restrictions. In Proceedings minological logics: Preliminary report. In Proceedings of
of the 26th International Workshop on Description Logics, the 12th International Joint Conference on Artificial Intel-
pages 93–106, 2013. ligence (IJCAI), pages 466–471, 1991.
[Casini and Straccia, 2010] G. Casini and U. Straccia. Ra- [Sengupta et al., 2011] K. Sengupta, A. Alfa Krisnadhi, and
tional closure for defeasible description logics. In T. Jan- P. Hitzler. Local closed world semantics: Grounded
hunen and I. Niemelä, editors, Proceedings of the 12th circumscription for OWL. In L. Aroyo, C. Welty,
European Conference on Logics in Artificial Intelligence H. Alani, J. Taylor, A. Bernstein, L. Kagal, N. Noy, and
(JELIA), number 6341 in LNCS, pages 77–90. Springer- E. Blomqvist, editors, Proceedings of the 10th Interna-
Verlag, 2010. tional Semantic Web Conference (ISWC), number 7031 in
[Casini and Straccia, 2013] G. Casini and U. Straccia. De- LNCS, pages 617–632. Springer, 2011.
feasible inheritance-based description logics. Journal of [Shoham, 1988] Y. Shoham. Reasoning about Change: Time
Artificial Intelligence Research (JAIR), 48:415–473, 2013. and Causation from the Standpoint of Artificial Intelli-
gence. MIT Press, 1988.
[Casini et al., 2015] G. Casini, T. Meyer, K. Moodley,
U. Sattler, and I. Varzinczak. Introducing defeasibility
into OWL ontologies. In M. Arenas, O. Corcho, E. Sim-
perl, M. Strohmaier, M. d’Aquin, K. Srinivas, P.T. Groth,
M. Dumontier, J. Heflin, K. Thirunarayan, and S. Staab,
editors, Proceedings of the 14th International Semantic
Web Conference (ISWC), number 9367 in LNCS, pages
409–426. Springer, 2015.