=Paper=
{{Paper
|id=Vol-1195/long15
|storemode=property
|title=Revising Description Logic Terminologies to Handle Exceptions: a First Step
|pdfUrl=https://ceur-ws.org/Vol-1195/long15.pdf
|volume=Vol-1195
|dblpUrl=https://dblp.org/rec/conf/cilc/MicalizioP14
}}
==Revising Description Logic Terminologies to Handle Exceptions: a First Step==
https://ceur-ws.org/Vol-1195/long15.pdf
Revising Description Logic Terminologies to
Handle Exceptions: a First Step
Roberto Micalizio, Gian Luca Pozzato
Dipartimento di Informatica - Università degli Studi di Torino
roberto.micalizio@unito.it,gianluca.pozzato@unito.it
Abstract. We propose a methodology to revise a Description Logic
knowledge base when detecting exceptions. Our approach relies on the
methodology for debugging a Description Logic terminology, addressing
the problem of diagnosing incoherent ontologies by identifying a mini-
mal subset of axioms responsible for an inconsistency. In the approach
we propose, once the source of the inconsistency has been localized, the
identified axioms are revised in order to obtain a consistent knowledge
base including the detected exception. To this aim, we make use of a non-
monotonic extension of the Description Logic ALC based on the com-
bination of a typicality operator and the well established nonmonotonic
mechanism of rational closure, which allows to deal with prototypical
properties and defeasible inheritance.
1 Introduction
Exceptions do exist. Intuitively, we can define an exception as an individual (or
a group of individuals) that has, or has not, a property in contrast with other
individuals of the same class. For instance, a penguin can be considered as an
exceptional bird since, although equipped with wings, is unable to fly. We can
find numerous examples of exceptions in nature, but also in natural languages
(e.g., irregular verbs), medicine (e.g. situs inversus is an anomaly in which the
major visceral organs are reversed or mirrored from their normal positions, so
that the heart is positioned in the right-hand side of the chest), and many other
real-world scenarios.
Dealing with exceptions can be tricky for an ontology engineer. All the
exceptions should be known in advance by the ontology engineer; i.e., when
the ontology is being designed. Unfortunately, in many real-world scenarios,
exceptions are discovered just while the system is running, and the ontology
is actually used. Whenever exceptions are discovered at runtime, the resulting
ontology becomes incoherent (i.e., at least one concept is mapped to an empty set
of individuals). Some recent works [16, 17, 15, 8, 9, 13] have addressed the problem
of diagnosing incoherent ontologies by identifying a minimal subset of axioms
responsible for the inconsistency. The idea of these works is that once the source
of the inconsistency has been localized, the ontology engineer can intervene and
revise the identified axioms in order to restore the consistency. These approaches
presuppose that the ontology has become incoherent due to the introduction of
errors; as for instance when two ontologies are merged together. It is worth
noting that, albeit an exception has the same e↵ect of an error (i.e., it causes an
ontology to become incoherent), an exception is not an error. An exception is
225
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
rather a piece of knowledge that partially contradicts what is so far known about
a portion of the ontology at hand. Thus, on the one hand, ignoring exceptions
would be deleterious as the resulting ontology would not reflect the applicative
domain correctly. On the other hand, accommodating exceptions requires the
exploitation of some form of defeasible reasoning that allows us to revise some
of concepts in the ontology.
In this paper we propose a methodology to revise a Description Logic (for
short: DL) knowledge base when detecting exceptions. Our approach relies on the
above mentioned methodology of [16, 17, 15] for detecting exceptions by identify-
ing a minimal subset of axioms responsible for an inconsistency. Once the source
of the inconsistency has been localized, the identified axioms are revised in order
to obtain a consistent knowledge base including the detected exception. To this
aim, we use a nonmonotonic extension of the DL ALC recently presented by
Giordano and colleagues in [7]. This extension is based on the introduction of a
typicality operator T in order to express typical inclusions. The intuitive idea is
to allow concepts of the form T(C), whose intuitive meaning is that T(C) selects
the typical instances of a concept C. It is therefore possible to distinguish between
properties holding for all instances of a concept C (C v D), and those only hold-
ing for the typical instances of C (T(C) v D). For instance, a knowledge base
can consistently express that birds normally fly (T(Bird ) v Fly), but penguins
are exceptional birds that do not fly (Penguin v Bird and Penguin v ¬Fly).
The T operator is intended to enjoy the well-established properties of rational
logic, introduced by Lehmann and Magidor in [12] for propositional logic. In order
to reason about prototypical properties and defeasible inheritance, the semantics
of this nonmonotonic DL, called ALC R min T, is based on rational models and
exploits a minimal models mechanism based on the minimization of the rank of
domain elements. This semantics corresponds to a natural extension to DLs of
Lehmann and Magidor’s notion of rational closure [12].
The paper is organized as follows: in Section 2 we recall extensions of DLs for
prototypical reasoning, focusing on the approach based on a typicality operator
T and rational closure [7]; in Section 3 we recall and extend the notions intro-
duced in [17, 13] for diagnosing incoherent ontologies; in Section 4 we present
our methodology for revising a DL terminology to handle exceptions by means
of T; we conclude with some pointers to future issues in Section 5.
2 Description Logics and Exceptions
The family of Description Logics [1] is one of the most important formalisms of
knowledge representation. DLs are reminiscent of the early semantic networks
and of frame-based systems. They o↵er two key advantages: (i) a well-defined
semantics based on first-order logic and (ii) a good trade-o↵ between expressiv-
ity and computational complexity. DLs have been successfully implemented by a
range of systems, and are at the base of languages for the Semantic Web such as
OWL. In a DL framework, a knowledge base (KB) comprises two components:
(i) a TBox, containing the definition of concepts (and possibly roles) and a spec-
ification of inclusion relations among them; (ii) an ABox, containing instances
226
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
of concepts and roles, in other words, properties and relations of individuals.
Since the primary objective of the TBox is to build a taxonomy of concepts, the
need of representing prototypical properties and of reasoning about defeasible
inheritance of such properties easily arises.
In the recent years, a large amount of work has been done in order to extend
the basic formalism of DLs with nonmonotonic reasoning features. The tradi-
tional approach is to handle defeasible inheritance by integrating some kind of
nonmonotonic reasoning mechanisms [5, 2, 10, 3, 4]. A simple but powerful non-
monotonic extension of DLs is proposed in [6]. In this approach, “typical” or
“normal” properties can be directly specified by means of a “typicality” op-
erator T enriching the underlying DL; the typicality operator T is essentially
characterized by the core properties of nonmonotonic reasoning, axiomatized by
preferential logic P in [11].
In this work we refer to the most recent approach proposed in [7], where
the authors extend ALC with T by considering rational closure as defined by
Lehman and Magidor [12] for propositional logic. Here the T operator is in-
tended to enjoy the well-established properties of rational logic R . Even if T
is a nonmonotonic operator (so that for instance T(Bird ) v Fly does not entail
that T(Bird uPenguin) v Fly), the logic itself is monotonic. Indeed, in this logic
it is not possible to monotonically infer from T(Bird ) v Fly, in the absence of
information to the contrary, that also T(Bird u Black ) v Fly. Nor it can be
nonmonotonically inferred from Bird (tweety), in the absence of information to
the contrary, that T(Bird )(tweety). Nonmonotonicity is achieved by adapting to
ALC with T the propositional construction of rational closure. This nonmono-
tonic extension allows to infer typical subsumptions from the TBox. Intuitively,
and similarly to the propositional case, the rational closure construction amounts
to assigning a rank (a level of exceptionality) to every concept; this rank is used
to evaluate typical inclusions of the form T(C) v D: the inclusion is supported
by the rational closure whenever the rank of C is strictly smaller than the rank of
C u¬D. From a semantic point of view, nonmonotonicity is achieved by defining,
on the top of ALC with typicality, a minimal model semantics where the notion
of minimality is based on the minimization of the ranks of the domain elements.
The problem of extending rational closure to ABox reasoning is also taken into
account: in order to ascribe typical properties to individuals, the typicality of an
individual is maximized. This is done by minimizing its rank (that is, its level
of exceptionality). Let us recall the resulting extension ALC R min T in detail.
Definition 1. We consider an alphabet of concept names C, of role names R,
and of individual constants O. Given A 2 C and R 2 R, we define:
CR := A | > | ? | ¬CR | CR u CR | CR t CR | 8R.CR | 9R.CR
CL := CR | T(CR )
A knowledge base is a pair (TBox, ABox). TBox contains a finite set of concept
inclusions CL v CR . ABox contains assertions of the form CL (a) and R(a, b),
where a, b 2 O.
We define the semantics of the monotonic ALC + TR , formulated in terms of
rational models: ordinary models of ALC are equipped with a preference relation
227
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
< on the domain, whose intuitive meaning is to compare the “typicality” of
domain elements, that is to say x < y means that x is more typical than y.
Typical members of a concept C, that is members of T(C), are the members x
of C that are minimal with respect to this preference relation (s.t. there is no
other member of C more typical than x).
Definition 2 ([7]). A model M of ALC + TR is any structure h , <, Ii where:
is the domain; < is an irreflexive, transitive and modular (if x < y then either
x < z or z < y) relation over ; I is the extension function that maps each
concept C to C I ✓ , and each role R to RI ✓ ⇥ as follows: >I = , ?I =
;, (¬C)I = \C I , (C u D)I = C I \ DI , (C t D)I = C I [ DI , (8R.C)I = {x 2
| 8y.(x, y) 2 RI ! y 2 C I }, (9R.C)I = {x 2 | 9y.(x, y) 2 RI and y 2 C I },
(T(C))I = M in< (C I ), where M in< (S) = {u : u 2 S and @z 2 S such that z <
u}. Furthermore, < satisfies the Well Foundedness Condition, i.e., for all S ✓
, for all x 2 S, either x 2 M in< (S) or 9y 2 M in< (S) such that y < x.
Given an ALC+TR model M= h , <, Ii, we say that (i) M satisfies an inclusion
C v D if it holds C I ✓ DI , (ii) M satisfies an assertion C(a) if aI 2 C I and
(iii) M satisfies an assertion R(a, b) if (aI , bI ) 2 RI . Given K=(TBox,ABox),
we say that M satisfies TBox if M satisfies all inclusions in TBox, M satisfies
ABox if M satisfies all assertions in ABox and M satisfies K if it satisfies both
its TBox and its ABox.
Given a knowledge base K, an inclusion CL v CR and an assertion CL (a),
with a 2 O, we say that the inclusion CL v CR is derivable from K, written
K |=ALC R T CL v CR , if CL I ✓ CR I holds in all models M =h , <, Ii satisfying
K. Moreover, we say the assertion CL (a) is derivable from K, written K |=ALC R T
CL (a), if aI 2 CL I holds in all models M =h , <, Ii satisfying K.
As already mentioned, although the typicality operator T itself is nonmonotonic
(i.e. T(C) v D does not imply T(C uE) v D), the logic ALC +TR is monotonic:
what is inferred from K can still be inferred from any K 0 with K ✓ K 0 . This is a
clear limitation in DLs. As a consequence of the monotonicity of ALC + TR , one
cannot deal with irrelevance, for instance. So, from the knowledge base of birds
and penguins, one cannot derive that K |=ALC R T T(Penguin u Black ) v ¬Fly,
even if the property of being black is irrelevant with respect to flying. In the same
way, if we added to K the information that Tweety is a bird (Bird(tweety)), in
ALC + TR one cannot tentatively derive, in the absence of information to the
contrary, that T(Bird)(tweety) and F ly(tweety).
In order to tackle this problem, in [7] the definition of rational closure intro-
duced by Lehmann and Magidor [12] for the propositional case has been extended
to the DL ALC + TR . Due to space limitations, we omit all definitions of the
rational closure of a DL knowledge base, reminding to [7].
From a semantic point of view, in [7] it is shown that minimal rational models
that minimize the rank of domain elements can be used to give a semantical
reconstruction of this extension of rational closure. The rank kM of a domain
element x is the length of the longest chain x0 < · · · < x from x to a minimal x0
(i.e. such that there is no x0 such that x0 < x0 ). The idea is as follows: given two
228
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
models of K, one in which a given domain element x has rank x1 and another in
which it has rank x2 , with x1 > x2 , then the latter is preferred, as in this model
the element x is “more normal” than in the former.
Given a knowledge base K=(TBox,ABox), in [7] it is shown that an inclu-
sion C v D (respectively, an assertion C(a)) belongs to the rational closure of
K if and only if C v D (resp., C(a)) holds in all minimal models of K of a “spe-
cial” kind, named canonical models. The rational closure construction for ALC
is inexpensive, since it retains the same complexity of the underlying logic, and
thus a good candidate to define e↵ective nonmonotonic extensions of DLs. More
precisely, the problem of deciding whether a typical inclusion belongs to the ra-
tional closure of the TBox is in ExpTime as well as the problem of deciding
whether an assertion C(a) belongs to the rational closure over the ABox.
3 Explaining Incoherent Terminologies
In this paper, we propose a methodology to deal with exceptions that builds up
on the methodology for debugging a DL terminology proposed by Schlobach et
al. since their seminal work [17].
Let us first introduce the notion of incoherent terminology. Given a TBox
T , we say that it is coherent if there is no unsatisfiable concept, in other words
there is at least a model of T in which the extensions of all concepts are not
empty.
To explain incoherences in terminologies, Schlobach et al. propose a method-
ology based on two steps: first, axiom pinpointing excludes axioms which are
irrelevant to the incoherence; second, concept pinpointing provides a simplified
definition highlighting the exact position of a contradiction within the axioms
previously selected. In this paper we are interested in the axiom pinpointing step,
which identifies debugging-relevant axioms. Intuitively, an axiom is relevant for
debugging if, when removed, a TBox becomes coherent, or at least one pre-
viously unsatisfiable concept turns satisfiable. The notion of subset of relevant
axioms is captured by the following definition.
Definition 3 (MUPS, Definition 3.1 [17]). Let C be a concept which is
unsatisfiable in a TBox T . A set T 0 ✓ T is a minimal unsatisfiability-preserving
sub-TBox (MUPS) of T if C is unsatisfiable in T 0 , and C is satisfiable in every
sub-TBox T 00 ⇢ T 0 .
In the following, mups(T , C) is used to denote the set of MUPS for a given
terminology T and a concept C. Intuitively, each set of axioms in mups(T , C)
represents a conflict set; i.e., a set of axioms that cannot all be satisfied. From
this point of view, it is therefore possible to infer a diagnosis for the concept
C by applying the Hitting-Set tree algorithm proposed by Reiter [14]. However,
the set mups(T , C) is sufficient for our purpose of dealing with exceptions.
A drawback of the debugging approach in [16, 17] is that it is restricted to
unfoldable TBoxes, only containing unique, acyclic definitions. An axiom is called
a definition of A if it is of the form A v C, where A 2 C is an atomic concept. An
229
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
axiom A v C is unique if the KB contains no other definition of A. An axiom
is acyclic if C does not refer either directly or indirectly (via other axioms)
to A [1]. This restriction is too strong for our objective of representing and
reasoning about defeasible inheritance in a natural way. As an example, the TBox
expressing that students are not tax payers, but working students do pay taxes,
can be naturally expressed by the following, not unfoldable, TBox={Student v
¬TaxPayer , Student u Worker v TaxPayer }. In order to overwhelm this gap, in
[13, 8] axiom pinpointing is extended to general TBoxes, more suitable to our
purposes. As a further di↵erence, Schlobach and colleagues limit their attention
to the basic ALC, whereas Parsia and colleagues in [8] are able to deal also with
the more expressive SHOIN , corresponding to OWL-DL. A set of algorithms
for computing axiom pinpointing, in particular to compute the set of MUPS for
a given terminology T and a concept A, is also provided.
In [16], Schlobach also proposes a methodology for explaining concept sub-
sumptions. The idea is to reduce the structural complexity of the original con-
cepts in order to highlight the logical interplay between them. To this aim,
Schlobach proposes to exploit the structural similarity of concepts, that can be
used to simplify terminological concepts, and hence the subsumption relations.
The structural similarity is based on the notion of qualified subconcepts; namely,
variants of those concepts a knowledge engineer explicitly uses in the model-
ing process, and where the context (i.e., sequence of quantifiers and number of
negations) of this use is kept intact. Schlobach specifies the notion of qualified
subconcepts in two ways: Generalized Qualified Subconcepts (gqs), and Special-
ized Qualified Subconcepts (sqs) which are defined by induction as follows:
Definition 4 (Generalized and Specialized Qualified Subconcepts, [16]).
Given concepts A, C and D, we define:
gqs(A) = sqs(A) = {A} if A is atomic
gqs(C u D) = {C 0 , D0 , C 0 u D0 |C 0 2 gqs(C), D0 2 gqs(D)}
gqs(C t D) = {C 0 t D0 |C 0 2 gqs(C), D0 2 gqs(D)}
gqs(9r.C) = {9r.C 0 |C 0 2 gqs(C)}
gqs(8r.C) = {8r.C 0 |C 0 2 gqs(C)}
gqs(¬C) = {¬C 0 |C 0 2 sqs(C)}
sqs(C u D) = {C 0 u D0 |C 0 2 sqs(C), D0 2 sqs(D)}
sqs(C t D) = {C 0 , D0 , C 0 t D0 |C 0 2 sqs(C), D0 2 sqs(D)}
sqs(9r.C) = {9r.C 0 |C 0 2 sqs(C)}
sqs(8r.C) = {8r.C 0 |C 0 2 sqs(C)}
sqs(¬C) = {¬C 0 |C 0 2 gqs(C)}
As Schlobach himself notes, a simple consequence of this definition is that |=
C v C 0 for every C 0 2 gqs(C), and |= D0 v D for each D0 v sqs(D).
We slightly extend the base case of Definition 4 as follows:
Definition 5 (Generalized and Specialized Qualified Subconcepts ex-
tended). We define sqs(C) and gqs(C) by adding to clauses in Definition 4 the
following ones:
230
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
gqs(A) = {A} [ {gqs(D) | A v D 2 TBox} if A is atomic
sqs(A) = {A} [ {sqs(C) | C v A 2 TBox} if A is atomic
gqs(¬A) = {¬A} [ {gqs(D) | ¬A v D 2 TBox} if A is atomic
sqs(¬A) = {¬A} [ {sqs(C) | C v ¬A 2 TBox} if A is atomic
Thus, we also take into account the axioms (i.e., concept inclusions) defined in
a given TBox. This generalization allows us to move upward (by means of gqs),
and downward (by means of sqs) in the hierarchy of concepts defined by a given
TBox T . Relying on the notions of sqs and gqs, we can define a partial ordering
relation between concepts as follows:
Definition 6. Let C and D be two concepts in a given TBox T , we say that
C is more specific than D, denoted as C D, i↵ at least one of the following
relations holds: (i) C 2 sqs(D), or (ii) D 2 gqs(C).
It is easy to see that is irreflexive, antisymmetric, and transitive; however, it
is just partial because is not defined for any pair of concepts; i.e., there may
exist two concepts C and D such that neither C D nor D C holds. As we
will discuss later, the methodology we propose for determining which concepts
represent properties to be made “typical” relies on the fact that concepts are
considered in order from the most specific to the most general. In those situations
where two concepts are not directly comparable with one another by means of ,
we need some further tools. For this reason, we introduce the notions of Concept
Network and depth of concepts. First of all, let S be the set of concepts (and
subconcepts) occurring in a given TBox.
Definition 7 (Concept Network). Given a TBox T , a concept network for T
is a graph CN (T ) : hV, Ei where V is a set of vertexes, each of which corresponds
to a concept C 2 S, and E is a set of oriented edges of the form hC, Di, where
C and D belong to V ; an edge hC, Di is in E i↵ C D.
Definition 8 (Depth of a concept). Given a TBox T , its corresponding con-
cept network CN (T ), and a concept C 2 S, the depth of a concept C 2 T ,
denoted as depth(C), corresponds to the length of the longest path from > to C.
In principle, any two concepts C and D at the same depth can be considered by
our methodology in either orderings C D or D C. However, when both C
and ¬C are at the same depth, we use a further criteria of preference based on
the distance between concepts.
Definition 9 (Distance between concepts). Given a TBox T , its corre-
sponding concept network CN (T ), and two concepts C, D 2 S, the distance
between C and D in T , denoted as dist(C, D) is given by the shortest path in
CN (T ) from C to D, if C D; 1, otherwise.
Example 1. Let us consider a simple example in which a TBox Tstudent contains
the following concept definitions:
Student v ¬ TaxPayer
Student uWorker v TaxPayer
231
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
Of course, Tstudent is consistent only if there are no working students, and in
the following we will show how it can be repaired by means of the typicality
operator. For the time being, we are just interested in determining the depth of
the concepts in Tstudent . By applying Definition 6 we obtain:
Student u Worker Student ¬TaxPayer; Student u Worker TaxPayer.
It is easy to see that Student uWorker is the deepest concept in our terminology.
In fact, we have that both TaxPayer and ¬TaxPayer are at the same depth
1, as well as Worker; Student is at depth 2; whereas Student u Worker is at
depth 3. However, since dist(Student u W orker, T axP ayer) < dist(Student u
W orker, ¬T axP ayer), we will prefer to consider T axP ayer before ¬T axP ayer.
Definition 5 above does not take into account that the terminology may be incon-
sistent, and hence some of the concepts generated via the generalization (special-
ization) rules might be trivially contradictory (e.g., having the form D u ¬D).
Moreover, the set of concepts within the gqs (sqs) of a given concept C are
not necessarily consistent with one another. For instance, let us consider again
Tstudent ; it is easy to see that gqs(Student uWorker) is the set:
{Student u Worker, Student, TaxPayer, ¬TaxPayer, ¬ (Student u Worker),
Worker, ¬ TaxPayer u Worker, ¬ (Student u Worker) u Worker, TaxPayer}.
Both TaxPayer and ¬TaxPayer are members of gqs(Student uWorker), but
only one of them will be correct, the other will have to be pruned. As we have
already mentioned above, TaxPayer will be preferred as it is closer to Student u
Worker. In the next section we propose a pruning technique that discards those
concepts that, albeit generalize a concept C (i.e., belong to gqs(C)), contradict
the terminology T . Our pruning technique relies on a compact representation of
gqs. That is, rather than explicitly computing all concepts in gqs(C) by recur-
sively unfolding every gqs(C 0 ) for each C 0 2 gqs(C), we consider gqs(C) as a list
of concepts (not necessarily atomic), and gqss.
For example, gqs(Student uWorker) can be compactly represented as the list
of elements {Student u Worker, gqs(Student) u gqs(W orker), gqs(Student),
gqs(W orker)}. Intuitively, gqs(Student uWorker) is given by the union of the
concepts that are directly mentioned in the list (e.g., Student uWorker), or that
belong to one of the gqss mentioned in the list itself (e.g., gqs(Student)).
Note that we keep the list associated with gqs(C) ordered according to the
depth (and distance when necessary) of the mentioned concepts. Also in this case,
deepest concepts come first. However we have to pay some attention in dealing
with gqss. In fact, if D E, then also gqs(D) E, and hence gqs(D) gqs(E).
However, if both D and gqs(D) are in gqs(C), then D gqs(D). On the other
hand, if D and F have the same depth, we put first the concept which is closer
to C. In case, D and F are at the same distance from C than their relative
ordering is arbitrary. The idea is that gqs(D) abstracts a set of concepts which
are at least as specific as D, but possibly more general than D. Therefore, any
concept more specific than D is also more specific than gqs(D). Vice versa, if
D E, then also gqs(D) E as gqs(D) contains at least D.
232
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
4 Revising Terminologies Including Exceptions
In this section we present the methodology for automatically modify a TBox
T whenever a detected inconsistency can be treated as an exception. The basic
idea of our proposal is first to isolate a subset of T which is relevant for the
inconsistency, and for this purpose we will adopt the notion of MUPS introduced
in Definition 3. Then we reconsider all the concepts within a MUPS and try to
identify which concepts describe characterizing properties to be made “typical”.
The intuition is that all the properties labeled as typical hold for all “normal”
members of a given class C, but not necessarily for all members in C. That is,
we admit that a subset of individuals in C do not present the typical properties
of the class, and hence are considered as exceptional.
Let us start by considering a coherent terminology T , and assume we dis-
cover a new subsumption relation newC v D that once added to T introduces
an incoherence. As mentioned above, the first step consists in restricting our
attention to only those concepts that are relevant for the incoherence. These
concepts are identified by mups(T , newC) [18]. For the sake of discussion, we
will assume that mups(T , newC) will only contain a set of incoherent axioms,
the approach can be easily extended to consider the more general situation in
which mups(T , newC) is a set of sets.
In principle, we have to identify which concept subsumptions in mups(T , newC)
are to be modified by introducing the T operator on the left-hand side of an ax-
iom. The main issue in this process is that the terminology T might hide implicit
knowledge (i.e., implicit subsumptions), and these implicit subsumptions are still
hidden in mups(T , newC). Inferring implicit subsumptions is therefore essential
in order to correctly identify the most specific properties to be made typical.
To reach this result, we propose a search process that is based on the fol-
lowing intuition: Given a concept C in mups(T , newC), all the implicit sub-
sumptions we are looking for are already contained in gqs(C). In other words,
for any concept D 2 gqs(C) (either atomic or not), the subsumption C v D
must hold by definition of gqs. However, we have to be cautious when dealing
with gqs(C) as it potentially contains subsumptions which are irrelevant, or even
incorrect, for the specific case under consideration. First of all, gqs(C) consid-
ers all the possible concept definitions in T , but we are just interested in those
concepts mentioned within mups(T , newC). Thus, in considering the concepts
mentioned within gqs(C) we have to restrict ourselves only to those concepts
which are also mentioned mups(T , newC); any other concept in gqs(C) will be
ignored as irrelevant. In addition, not all the generalizations suggested by gqs(C)
are consistent with the concepts in mups(T , newC). As we have already noted,
mups(T , newC) might contain the subsumption relation C v D; at the same
time, the concept ¬D appears in gqs(C); implying that C v ¬D. Of course, this
second subsumption is in direct contrast with a subsumption in mups(T , newC);
we say that C v ¬D syntactically contradicts C v D. (Note that such a contra-
diction is just syntactic, and hence it can be checked by inspecting concepts in
mups(T , newC).)
Another critical issue is that we are interested in finding the most specific
properties that have to be considered as typical. This is also the reason why we
233
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
look for implicit subsumptions: we want to discover what properties are inherited
by the concepts in mups(T , newC). Thus, when we look for inclusions, we have to
proceed from the most specific concepts in mups(T , newC) to the most general
ones. In this way, we can progressively build a new set of subsumption relations
S, in which the typicality operator is added to only those specific properties that
are relevant for dealing with the exception introduced by newC.
4.1 Algorithms
In this section we give a detailed description of the methodology we propose for
automatically managing, by means of the typicality operator, a concept newC
with exceptional properties D. We give for granted that mups(T , newC) has
already been computed by means of one of the calculi proposed in [8]. Thus,
mups(T , newC) identifies a minimal subset of concept inclusions that are rele-
vant for the inconsistency arising when T is extended with newC v D.
Algorithm 1 FindSubsumptionsMain(mups(T , newC))
1: S ;
2: for all depth l of concepts in mups(T , newC), from the highest to the lowest do
3: for all Ci in mups(T , newC) such that depth(Ci ) = l do
4: Si FindSubsmption(Ci , gqs(Ci ), S)
5: end for S
6: if S [ Si isScoherent then
7: S S [ Si
8: else
9: for all Si do
10: for all C v D 2 Si , such that C does not occur in D do
11: S S [ {T(C) v D}
12: end for
13: end for
14: end if
15: end for
16: return S
FindSubsumptionsMain To restore the consistency in T , we propose to
rewrite the inclusion relations in mups(T , newC) by characterizing some of them
with the typicality operator. As said above, we reach this goal by considering
all concepts mentioned in mups(T , newC) in depth ordering, starting from the
deepest ones up to the most generic concepts. Algorithm 1 simply shows this
loop over the concepts in mups(T , newC). At each iteration, a set S of inclu-
sions is incrementally extended with the new relations discovered by function
FindSubsumptions. In case several concepts Ci have the same depth, a further
consistency check among their corresponding sets Si s is performed to deal with
inconsistent properties, coming from di↵erent Si s, and inherited by a given con-
cept F . For instance, let us assume that F v C u D 2 S, C and D have the same
depth and distance from F , thus we cannot prefer one to the other. In addition,
by invoking FindSubsumptions over C and D we get, respectively, C v E 2 SC
234
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
and D v ¬E 2 SD . Since F inherits both E and ¬E, we do not conclude
anything about F having, or not, property E; however, to build a coherent S,
T(C) v E and T(D) v ¬E are added to S.
FindSubsumptions Algorithm 2 sketches the main steps of function Find-
Subsumption: it takes as inputs a concept Ci mentioned in mups(T , newC), the
corresponding gqs(Ci ) given as a list in compact form, and the set S of inclusions
found so far. The intuition is that all implicit inclusions we are looking for have
the form Ci v D, where D 2 gqs(Ci ).
First of all, the algorithm initializes some local structures: Si will contain
the subsumptions discovered in this invocation, BlackList will only contain the
gqs of concepts that have been pruned: future occurrences of concepts belonging
to these gqs have to be discarded; Queue will either contain concept nodes or
complex nodes: a concept node represents a concept (not necessarily atomic),
whereas a complex node represents a structure where at least a gqs is mentioned
(i.e., a complex node is an abstraction of a number of concepts). All nodes in
Queue are kept ordered from the most specific to the most general according to
the depth of the concepts they contain. At the beginning of the algorithm (see
lines 3- 12), Queue is initialized with the elements in gqs(C).
After these preliminary steps, the algorithm loops over the elements in Queue.
At each iteration, the first node n is removed from the head of Queue. The
algorithm then checks whether n is a concept node or a complex node.
Handling concept nodes (lines 15 - 28). If n is a concept node, for instance
representing concept D, the algorithm has discovered a possible inclusion Ci v D
to be added to Si . However, if Ci v ¬D is already in S [ Si , relation Ci v D
has to be discarded. Moreover, since we know that D is not acceptable, then
any other concept which generalizes D is not acceptable, too; thereby we remove
from Queue any node e belonging to gqs(D) (line 18), and then add gqs(D) in
BlackList (line 19). Otherwise (Ci v ¬D is not in S [ Si ), Ci v D represents a
new piece of knowledge that we can add to Si . If S [ Si [ {Ci v D} is coherent,
the new relation is added to Si as it is (line 22). Conversely, we have discovered
one of the most specific properties of Ci that have to be made typical. That is,
in order to restore the consistency in T when we also consider the exceptional
properties of newC, the inclusion Ci v D has to be rewritten as T(Ci ) v D
(line 24).
Note that, since we add either Ci v D or T(Ci ) v D, we can conclude that
any other concept in gqs(¬D) will not be acceptable as it would introduce an
inconsistency. Thus, we can remove from Queue any node e which is a general-
ization of ¬D (line 26), and then add gqs(¬D) in BlackList (line 27).
Handling complex nodes (lines 29 - 32). In case the head node n is a complex
node, then it must mention at least a gqs, which abstracts a number of con-
cepts. Dealing with a complex node means generating a number of child-nodes
by expanding one of the gqs mentioned in n. The ExpandComplexNode func-
tion is shown in Algorithm 3. The set of new nodes N ewN odes returned by
ExpandComplexNode are enqueue in Queue in the specificity ordering.
235
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
Algorithm 2 FindSubsumptions(Ci , gqs(Ci ), S)
1: Si ;
2: BlackList ;
3: Queue ;
4: for all element e 2 gqs(Ci ), in the specificity ordering do
5: if e is a concept E then
6: create a concept node n[E]
7: enqueue n[E] in Queue in the ordering
8: else . e is a generalization of a concept E; i.e., gqs(E)
9: create a complex node n[gqs(E)]
10: enqueue n[gqs(E)] in Queue in the ordering
11: end if
12: end for
13: while Queue is not empty do
14: n Head (Queue)
15: if n is a concept node then
16: Let D be the concept in n; then Si is possibly extended to include Ci v D
17: if Ci v ¬D 2 S [ Si then
18: remove from Queue any node e such that e 2 gqs(D)
19: enqueue gqs(D) in BlackList
20: else . Ci v ¬D 2 /S
21: if S [ Si [ {Ci v D} is coherent then
22: Si Si [ {Ci v D}
23: else
24: Si Si [ {T(Ci ) v D}
25: end if
26: remove from Queue any node e such that e 2 gqs(¬D)
27: enqueue gqs(¬D) in BlackList
28: end if
29: else . n is a complex node
30: N ewN odes ExpandComplexNode(n, BlackList)
31: enqueue each node n0 2 N ewN odes in Queue in the ordering
32: end if
33: end while
34: return Si
Algorithm 3 ExpandComplexNode(n, BlackList)
1: List ;
2: Let gqs(D) be one of the most specific gqs mentioned in n
3: for all element e 2 gqs(D) such that e 62 gqs(F ), 8gqs(F ) 2 BlackList do
4: create a node n0 by substituting gqs(D) with e in n
5: if n0 is an inconsistent concept then
6: discard n0
7: else
8: put n0 in List
9: end if
10: end for
11: return List
236
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
ExpandComplexNode The expansion of a complex node is outlined in Algo-
rithm 3. It takes as inputs the complex node n that has to be expanded, and
the BlackList containing the gqss of those concepts that have been pruned o↵
so far. The algorithm returns a list of new nodes, either concept or complex.
After having initialized List, (line 1), the algorithm selects one of the most
specific gqs in n. In fact, since n is a complex node, then it must mention at
least one gqs (line 2). Let us assume that gqs(D) has been selected, remember
that gqs(D) is compactly encoded as a list of concepts or gqss. The algorithm
therefore loops over the elements e in the list gqs(D), if e belongs to any gqs(F ) 2
B lackList, then e can be pruned o↵ as it has already been determined that F ,
and then any other concept in gqs(F ), is not consistent with some axioms in
S (line 3). Otherwise, e can be used to create a new node n0 . More precisely,
n0 is obtained by substituting gqs(D) with e in n. Of course, n0 can either be
a concept node or a complex node (line 4). As noted above, the generalizations
of a given concept D might contain contradictory concepts since the initial set
of axioms in mups(T , newC) is inconsistent. Thus, before adding n0 to List,
we first check whether n0 is contradictory, in which case we discard it (line 5).
Otherwise, n0 is added to List (line 8). The algorithm terminates by returning
the, possibly empty, list of new nodes (line 11).
Let newC v D be the subsumption relation that, once added to a TBox T ,
generates an inconsistency, and let mups(T , newC) the minimal subset of axioms
in T preserving the inconsistency, then we can prove the following properties.
Proposition 1. The set S of concept inclusions generated by Algorithm 1 with
the invocation FindSubsumptionsMain(mups(T , newC)) is coherent.
Intuitively, S is only modified either in line 7 or in line 11 of algorithm FindSub-
sumptionsMain. In the first case, we already know that all the sets Si s inferred
for all concepts at a given depth l are altogether coherent. In the second case,
instead, we know that an inconsistency has been detected; thereby we “correct”
the axioms in Si s by means of T, yielding the consistency of S. In fact, for the
properties ALC R min T in [7], since T is nonmonotonic, we have that S is coherent.
Proposition 2. Let S be the set of concept inclusions generated by Algorithm
1, then either newC v D or T(newC) v D belongs to S.
This follows directly by the fact that newC v D has generated an inconsistency
in T , and then mups(T , newC) necessarily includes such a relation. Algorithm
1 simply reconsiders all the axioms in mups(T , newC), and builds a new set S
of axioms which contains, at least, the same axioms as in mups(T , newC), but
at least one has been modified by the typicality operator.
Theorem 1. Let T 0 be a new terminology obtained as T 0 = T \ mups(T , newC) [
S. The new terminology T 0 is coherent.
This allows us to conclude that once we have computed S, we have a means for
correcting the initially incoherent terminology T . The simplest way to do that is
237
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
to substitute the axioms in mups(T , newC) with S. Further details and proofs
are omitted due to space limitations.
Example 2. Let us consider again the terminology Tstudent presented in Exam-
ple 1. Algorithm 1 considers the concepts in the ordering: Student u W orker,
Student, T axP ayer, ¬T axP ayer, W orker. The first invocation of FindSub-
sumptons (Algorithm 2) is therefore over the inputs: StudentuW orker, gqs(Stu-
dentuW orker), and ; (i.e., at the beginning S is empty). The result of such a first
invocation is the set S = {Student u W orker v Student; Student u W orker v
T axP ayer; Student u W orker v W orker}. The second invocation of Find-
Subsumptions is over the inputs: Student, gqs(Student), S. In this case, the
algorithm will find the subsumption Student v ¬T axP ayer, which is inco-
herent with the subsumptions already in S, thus, ¬T axP ayer is considered
as the typical property of Student; in other words, S is modified by adding
T(Student) v ¬T axP ayer. It is easy to see that no further subsumptions
are added in S when FindSubsumptions is invoked over the remaining concepts
T axP ayer, W orker, and ¬T axP ayer. In conclusion, the original terminology
0
Tstudent , can be rewritten as Tstudent :
Student u Worker v Student Student u Worker v TaxPayer
Student u Worker v Worker T(Student) v ¬TaxPayer
By the properties of the DL ALC Rmin T, from the resulting knowledge base above
we are able to reason about defeasible inheritance. For instance, if we have
Student(franco) (Franco is a student), we are able to infer ¬TaxPayer (franco)
(Franco does not pay taxes), however this conclusion is retracted if we fur-
ther discover that Worker (franco) (Franco is also a worker), from which we ob-
tain TaxPayer (franco). We are also able to deal with irrelevance: for instance,
T(Student u Fat) v ¬TaxPayer can be inferred, and the above conclusions still
hold even if we further know Fat(franco) (Franco is fat).
Example 3. Let us consider a simplified variant of the Pizza ontology distributed
together with Protégé. In particular, let us assume that a TBox Ttops contains
the following subsumption relations:
ax1 : FatToppings v PizzaToppings,
ax2 : CheesyToppings v FatToppings,
ax3 : VegetarianToppings v ¬FatToppings.
Now, let us assume that we discover that there also exists the tofu cheese, which
is made of curdled soybeanmilk. Thus, we change Ttops by adding the following:
ax4 : CheesyVegetarianToppings v CheesyToppings u VegetarianToppings.
Let the ABox Atops contain CheesyVegetarianToppings(tofu). The resulting
knowledge base is inconsistent, respectively, the knowledge base obtained by
adding CheesyVegetarianToppings(tofu) to the initial ABox is inconsistent, since
FatToppings and DieteticToppings are disjunct concepts, whereas CheesyVege-
tarianToppings falls in their intersection.
238
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
The tofu cheese is an exception, and the first step to tackle is to compute
mups(Ttops , CheesyVegetarianToppings) = {ax2 , ax3 , ax4 }. Concept inclusions
(even implicit) are taken into account: possibly, some of them will be “corrected”
by means of the typicality operator in order to accommodate the exceptional
CheesyVegetarianToppings concept. In particular, the inclusions discovered are:
Stops = {
CheesyVegetarianToppings v CheesyToppings,
CheesyVegetarianToppings v VegetarianToppings,
T(CheesyToppings) v FatToppings,
T(VegetarianToppings) v ¬FatToppings
}
The concept inclusions in mups(Ttops , CheesyVegetarianToppings) can be now
substituted in Ttops with the set Stops . Theorem 1 ensures that the new Ttop
so obtained is now coherent and correctly addresses the exceptional concept
CheesyVegetarianToppings. By the properties of ALC R min T, from the resulting
knowledge base, we will be able to reason about defeasible inheritance: for in-
stance, if we know CheesyToppings(brie) (Brie is a cheesy topping), we conclude
that FatToppings(brie) (Brie is a fat topping), whereas for tofu we say nothing
about being a fat topping or not. We are also able to deal with irrelevance:
for instance, it can be inferred that, normally, cheesy potatoes toppings are fat
toppings, i.e. T(Cheesy u Potatoes) v FatToppings.
5 Conclusions and Future Issues
We have presented some preliminary results in defining a methodology for au-
tomated revision of a DL terminology in presence of exceptions. We exploit
techniques and algorithms proposed in [8], which are also extended to more ex-
pressive DLs such as SHOIN , corresponding to ontology language OWL-DL.
On the one hand, we aim at extending our approach to such expressive DLs. On
the other hand, we intend to develop an implementation of he proposed algo-
rithms, by considering the integration with existing tools for manually modifying
ontologies when inconsistencies are detected.
Acknowledgements
The authors are supported by the twin projects ODIATI#1 and ODIATI#2:
“Ontologie, DIAgnosi e TIpicalità nelle logiche descrittive” of the local research
funds 2013 by the Università degli Studi di Torino - part B, supporting young
researchers.
239
R. Micalizio and G.L. Pozzato. Revising Description Logic Terminologies to Handle Exceptions
References
1. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.: The
Description Logic Handbook - Theory, Implementation, and Applications, 2nd edi-
tion. Cambridge (2007)
2. Baader, F., Hollunder, B.: Embedding defaults into terminological knowledge rep-
resentation formalisms. J. Autom. Reasoning 14(1), 149–180 (1995)
3. Casini, G., Straccia, U.: Rational Closure for Defeasible Description Logics. In:
Janhunen, T., Niemelä, I. (eds.) Proceedings of the 12th European Conference on
Logics in Artificial Intelligence (JELIA 2010). Lecture Notes in Artificial Intelli-
gence, vol. 6341, pp. 77–90. Springer, Helsinki, Finland (September 2010)
4. Casini, G., Straccia, U.: Defeasible Inheritance-Based Description Logics. In:
Walsh, T. (ed.) Proceedings of the 22nd International Joint Conference on Artifi-
cial Intelligence (IJCAI 2011). pp. 813–818. Morgan Kaufmann, Barcelona, Spain
(July 2011)
5. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: ALC+T: a preferential ex-
tension of Description Logics. Fundamenta Informaticae 96, 1–32 (2009)
6. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A NonMonotonic Description
Logic for Reasoning About Typicality. Artificial Intelligence 195, 165–202 (2013)
7. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Minimal Model Semantics
and Rational Closure in Description Logics . In: Eiter, T., Glim, B., Kazakov, Y.,
Krtzsch, M. (eds.) Informal Proceedings of the 26th International Workshop on
Description Logics (DL 2013). CEUR Workshop Proceedings, vol. 1014, pp. 168 –
180. Ulm, Germany (7 2013)
8. Kalyanpur, A., Parsia, B., Cuenca-Grau, B., Sirin, E.: Axiom pinpointing: Finding
(precise) justifications for arbitrary entailments in SHOIN (owl-dl). Technical
report, UMIACS, 2005-66 (2006)
9. Kalyanpur, A., Parsia, B., Sirin, E., Grau, B.C.: Repairing unsatisfiable concepts
in owl ontologies. In: ESWC. pp. 170–184 (2006)
10. Ke, P., Sattler, U.: Next Steps for Description Logics of Minimal Knowledge and
Negation as Failure. In: Baader, F., Lutz, C., Motik, B. (eds.) Proceedings of De-
scription Logics. CEUR Workshop Proceedings, vol. 353. CEUR-WS.org, Dresden,
Germany (May 2008)
11. Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential mod-
els and cumulative logics. Artificial Intelligence 44(1-2), 167–207 (1990)
12. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Arti-
ficial Intelligence 55(1), 1–60 (1992)
13. Parsia, B., Sirin, E., Kalyanpur, A.: Debugging owl ontologies. In: WWW. pp.
633–640 (2005)
14. Reiter, R.: A theory of diagnosis from first principles. Artificial Intelligence 32 (1),
57–96 (1987)
15. Schlobach, S.: Diagnosing terminologies. In: AAAI. pp. 670–675 (2005)
16. Schlobach, S., Cornet, R.: Explanation of terminological reasoning: A preliminary
report. In: Description Logics (2003)
17. Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of
description logic terminologies. In: IJCAI. pp. 355–362 (2003)
18. Schlobach, S., Huang, Z., Cornet, R., van Harmelen, F.: Debugging incoherent
terminologies. Journal of Automated Reasoning 39(3), 317–349 (2007)
240