=Paper=
{{Paper
|id=Vol-519/paper-3
|storemode=property
|title=Highlighting Assertional Effects of Ontology Editing Activities in OWL
|pdfUrl=https://ceur-ws.org/Vol-519/pammer.pdf
|volume=Vol-519
|dblpUrl=https://dblp.org/rec/conf/semweb/PammerSL09
}}
==Highlighting Assertional Effects of Ontology Editing Activities in OWL==
https://ceur-ws.org/Vol-519/pammer.pdf
Highlighting assertional effects of ontology
editing activities in OWL
Viktoria Pammer1,2 , Luciano Serafini3 , and Stefanie Lindstaedt2
1
Knowledge Management Institute, TU Graz. Inffeldgasse 21a, 8010 Graz, Austria.
viktoria.pammer@tugraz.at
2
Know-Center. Inffeldgasse 21a, 8010 Graz, Austria.
slind@know-center.at
3
Fondazione Bruno Kessler. Via Sommarive, 18, 38100 Trento, Italy.
serafini@fbk.eu
Abstract. Within sufficiently large knowledge bases it is difficult for
each contributor to maintain an overview of existing axioms and how
they interact with the underlying data. To maintain conceptual consis-
tency however, it is essential that each contributor is able to judge the
effects of her actions when manipulating the knowledge base. Assertional
effects, exemplary facts which are lost or gained when removing or adding
terminological axioms, give contributors an easy-to-understand means to
do so. In this paper we formally define the problem of assertional effects
and show that it is decidable for the description logics SHOIQ and
SROIQ which underlie OWL 1 and OWL 2 respectively. A prototypi-
cal implementation which finds approximate solutions accompanies this
paper.
1 Introduction
Manual creation and maintenance of formal ontologies requires a significant
amount of human effort. This severely impedes the realisation of the Seman-
tic Web. Following success stories of massively user generated content in the
vein of Web 2.0, collaboratively maintained description logic knowledge bases
may be the way to distribute this effort between many actors. We envision that
in the future, contributors will not only add content, as e.g. in Wikipedia4 , or
facts, as e.g. in the Semantic Wikipedia envisioned by Krötzsch et al.[1], to a
knowledge base but also add terminological axioms to the underlying ontology.
Such a scenario is distinguished from traditional ontology engineering scenarios
in three main aspects: First, the knowledge engineering process is highly iter-
ative in that a large number of comparatively small revision steps instead of
one “ontology creation” phase is to be expected. Second, contributors vary ex-
tremely with respect to their (knowledge engineering) expertise. Finally, each
single contributor has only limited overview and control of the knowledge base’s
design and content.
4
http://www.wikipedia.org/
We propose to capitalize on the existence of meaningful data in such a knowledge
base in order to support contributors during ontology editing. In particular, our
approach makes the effects of removing or adding terminological axioms to the
knowledge base visible in terms of knowledge lost or gained about data. This will
help contributors to fully understand the results of their actions on the knowl-
edge base. Additionally, the formulation of effects in terms of assertions about
instance data is expected to be easily intelligible also for contributors with little
knowledge engineering expertise.
The contribution of this paper lies first in motivating such an approach, second
in the presentation of a formal characterization of the problem, and third in
putting down conditions on the underlying description logic under which the
problem is decidable. From this theoretical discussion, a decision algorithm im-
mediately follows. A prototypical implementation called TeA5 accompanies this
paper. TeA however does not carry out the full decision procedure but only a
pragmatic approximation.
2 Motivation
Consider a knowledge base which contains the facts that “Crete and Kos are
islands” (1,2), that “Crete is located in Greece” (3) and that “Crete is located
in the Mediterranean Sea” (4). Suppose also that the knowledge base is defined
on top of an ontology which defines a set of key concepts such as islands, areas
of land vs. areas of water, nations etc. Then suppose that a contributor wants
to formalise the concept Island and adds an axiom stating that all islands are
located (only) in areas of water (5).
Island(crete) (1)
Island(kos) (2)
locatedIn(crete, greece) (3)
locatedIn(crete, mediterranean) (4)
Island ! ∀locatedIn.W aterArea (5)
The most obvious consequence of the additional axiom is that greece will
then be inferred to be a W aterArea, which is surely not intended.
From the logical point of view, the new knowledge base is consistent. How-
ever there is still a form of conceptual inconsistency which is due to the fact that
the ontology entails a statement inconsistent with the world that the modeller
has in mind. Hence, the resulting theory will be represent the point of view of
the modeller inadequately or incorrectly. In order to indicate this situation we
say that the resulting ontology is inadequate or incorrect. We point out that
this problem is of conceptual nature, in contrast to more formal problems like
an unsatisfiable concept or a logically inconsistent knowledge base. Apart from
5
TeA: http://services.know-center.tugraz.at:8080/TeA/Tea.html
inconsistent vocabulary use, sources of conceptual inconsistency also include dif-
fering design preferences by contributors, divergent to incompatible underlying
views on the domain or simple modelling errors originating in (too) little expe-
rience with formal knowledge representation.
Considerations of this kind have led us to study the effects of terminological ax-
ioms on the instance data in a knowledge base. In this work, we consider inferred
facts caused by additional terminological axioms as effects. Where terminologi-
cal axioms are removed from a knowledge base, inferences that are lost and thus
“not known anymore” by the knowledge base are considered as effects.
Giving immediate feedback on the effect of ontology edits in terms of concrete
individuals gives the contributing users an easy means to review their actions
in the light of effects on the whole. This is in line with the realisation that an
inherent difficulty in ontology engineering is that such effects are not obvious.
This contrasts with the situation in e.g. software engineering where the conse-
quences of one’s changes are immediately executable and thus visible (see also
[2]). It is precisely this point that a reasoning service computing the effects of
axioms on instance data changes. From this perspective, effects in terms of in-
stance data serve as examples of how the terminological axioms will “work” on
the knowledge base’s data.
Such a reasoning service is therefore especially relevant in the knowledge bases
maintained in the spirit of Web 2.0, since (i) frequent ontology edits are ex-
pected, (ii) the group of contributors is expected to be heterogeneous in terms
of knowledge engineering expertise, but also in terms of views on the knowledge
itself and (iii) it follows that such a knowledge base is in danger of becoming
chaotic if not each contributor is able to judge the effects of her actions correctly
and efficiently.
3 Preliminaries
A vocabulary Σ consists of a set of concept names NC , a set of role names NR
and a set of individual names NI . In description logics (DLs), concepts and roles
are inductively defined by a set of constructors operating on the concept, role
and possibly individual names of Σ. Concepts (resp. roles) who are described just
by a concept (resp. role) name are also called primitive or named concepts (resp.
roles). The set of complex concepts C is determined by Σ and a description logic
DL. In case these parameters are relevant to the discussion, we write C(Σ, DL).
We use A, B to denote primitive concepts, C, D to denote possibly complex
concepts, R, S to denote a primitive role and a, b, x, y to denote individuals.
Terminological axioms describe the relation between concepts. An inclusion
axiom is a specific terminological axiom which of the form C ! D, and is often
verbalised as “D subsumes C” A set of terminological axioms constitutes a ter-
minological box, the so called TBox. In analogy, role axioms describe the relation
between roles or properties of single roles as for instance symmetry. A set of role
axioms constitutes a role box, the so called RBox. Terminological and role axioms
describe general truths in the domain of discourse. Assertional axioms describe
knowledge about individuals. A concept (resp. role) assertion for instance is a
statement of the form C(x) (resp. R(x, y)). These are often verbalised as “x is
of type C” and “x is related to y via R” respectively. A set of assertional axioms
constitute an assertional box, the so called ABox. By a DL ontology, a TBox T
and an RBox R is understood, while by knowledge base a TBox, an RBox and
an ABox KB = (T , R, A) is meant. Assertional axioms are also called facts.
An interpretation I = (∆I , ·I ) consists of a non-empty set ∆I , the domain of
interpretation, and the interpretation function ·I that assigns to every primitive
concept A ∈ NC a set AI ⊆ ∆I , to every primitive role R ∈ NR a binary rela-
tion RI ⊆ ∆I × ∆I and to every individual x ∈ NI an element xI ∈ ∆I . An
interpretation satisfies a concept inclusion axiom C ! D iff C I ⊆ DI , a concept
assertion C(x) iff xI ∈ C I and a role assertion R(x, y) iff (xI , y I ) ∈ RI ). An
ontology (resp. knowledge base) entails an axiom α if and only if all its inter-
pretations satisfy α. This is written as T |= α resp. KB |= α. An interpretation
which satisfies an ontology (resp. knowledge base) is also called a model of the
ontology (resp. knowledge base).
In particular, all discussions in this work target DLs which contain at least
ALC, in which complex concepts are constructed as shown in Table 1. Addition-
ally, ⊥ is used to abbreviate ¬', C ( D abbreviates ¬(¬C ) ¬D) and ∃R.C ab-
breviates ¬∀R.¬C. In all DLs which include ALC, every TBox T can be assumed
to be in the
! form ' ! CT without loss of generalisation: If T = {Ci ! Di }, then
T = ' ! i ¬Ci ( Di . Important description logics are SHOIQ and SROIQ,
both of which include ALC. The proposed standard languages for the Semantic
Web OWL 1 [3] and OWL 2 [4] are based on SHOIQ and SROIQ respectively.
For a comprehensive list of features for SHOIQ we refer to [5], and for SROIQ
we refer to [6] .
Name Syntax Semantics
Universal concept ! ∆I
Negation ¬C ∆ \ CI
I
Conjunction C "D C I ∩ DI
Universal restriction ∀R.C {w ∈ ∆ |∀v. (w, v) ∈ RI → v ∈ C I }
I
Table 1. Syntax and semantics of ALC.
4 Assertional effects of ontology editing activities
By ontology editing activities we understand quite narrowly the addition or
removal of terminological axioms to/from an ontology. We call one such activity
also an ontology edit. In this work we are not concerned with the manipulation
of role axioms or facts. The following definition also restricts the meaning of
effects to concept assertions. Possible extensions with regard to these limitations
are part of our ongoing research and discussed in Section 6.
Definition 1. (Assertional effects) Let KB = (T0 , R, A) and KB T = (T0 ∪
T , R, A). Let Σ = (NC , NR , NI ) be the vocabulary in which KB T is formulated
and let DL be the DL in which the assertional effects shall be formulated.
– C(x) such that C ∈ C(Σ, DL) is an assertional effect of T on KB iff KB ,|=
C(x) and KB T |= C(x).
– T affects an individual x ∈ NI in KB iff an effect C(x) of T on KB exists.
– T affects a knowledge base KB iff there exists an individual x ∈ NI such
that T affects x in KB .
Since this work is only concerned with assertional effects of ontology edits,
we sometimes omit the “assertional” and just speak of effects.
As preconditions we assume that KB T is consistent and that NI is not empty,
i.e. the knowledge base knows at least about one individual. Individuals can
occur in A or, if the DL allows for nominals as SHOIQ and SROIQ do, also
in T .
The above definition can be applied to both ontology editing activities. If
T is added to KB , then the effects of T on KB represent knowledge about
individuals which is gained. If T is removed from KB T , then the effects of T on
KB represent the knowledge about individuals which is lost.
4.1 Deciding the Existence of Assertional Effects
Since the set C(Σ, DL) is in general infinite for DLs equally or more expressive
than ALC, we consider at first the decidability of the general question whether
a particular TBox T affects a particular knowledge base KB . In order to do so,
we first define the notion of reachability of a concept C from an individual x in
a knowledge base KB .
Let R− denotes an inverse role such that (R− )I = {(y, x)|(x, y) ∈ RI }, and
let NR− = {R|R ∈ NR or R− ∈ NR } in description logics which include inverse
roles.
Definition 2. w0 R1 w1 . . . Rn wn is called a path in an interpretation I = (∆I , ·I )
if and only if for i = 1 . . . n it holds that wi ∈ ∆I , and (wi−1 , wi ) ∈ RiI and
Ri ∈ NR− .
Definition 3. A concept C is reachable from x ∈ NI w.r.t. KB iff there is a
model I = (∆I , ·I ) of KB in which xI = w0 , and a path w0 R1 w1 . . . Rn wn exists
in I such that wn ∈ C I .
In other words, C is reachable from x in KB iff either C(x) or ∃R1 . . . Rn .C(x)
for n > 0 is satisfiable w.r.t. KB .
The definition of reachability is motivated by the fact that it can be shown that
reachability equals the existence of assertional effects. First, this is shown under
the condition that the DL in question is decidable under a tableaux decision
procedure. Later, we will show a small generalisation.
Theorem 1 In description logics decidable under a tableaux decision procedure,
T = {' ! CT } affects KB iff an individual x exists in KB such that ¬CT is
reachable from x in KB .
For both SHOIQ and SROIQ tableaux decision procedures exist. For exact
descriptions of tableaux algorithms we refer the reader to [5] for SHOIQ and
to [6] for SROIQ. Nonetheless, we review some basic notions related to tableaux
decision procedures before delving into the proof for Theorem 1.
A completion graph for a knowledge base KB formulated in the vocabulary
.
Σ and the description logic DL is a labelled directed graph G = (V, E, L, =) ,
where each node x ∈ V is labelled with a set L(x) ⊆ C(Σ, DL) and each edge
(x, y) ∈ E is labelled with a set of role names L(x, y) ⊆ NR− . A set of completion
rules are used to manipulate the underlying completion graph(s).
A completion graph contains a clash iff a label L(x) contains either ⊥ or both
A and ¬A. A completion graph which does not contain a clash is called open,
while a a completion graph which contains a clash is called closed. A completion
graph to which no more completion rules apply is called complete.
More specifically we make use of the following connections between consistency,
completion graphs and models, which hold whenever a tableaux algorithm has
been shown to be a decision procedure for a DL language.
– If a knowledge base is consistent, then an open and complete com-
pletion graph can be constructed. This is the basis of the completeness
property of tableaux decision algorithms.
– Every open and complete completion graph can be translated into
a model. This is the basis of the correctness property of tableaux deci-
sion algorithms. The relevant part of this translation is the following: If a
.
completion graph G = (V, E, L, =) , is translated into a model I = (∆I , ·I ),
then every node x ∈ V corresponds to at least one node w ∈ ∆I such that
for all C ∈ C(Σ, DL), C ∈ L(x) if and only if w ∈ C I , and every edge
(x, y) ∈ E corresponds to at least one relation (v, w) ∈ ∆I × ∆I such that
for all R ∈ NR− , R ∈ L(x, y) if and only if (v, w) ∈ RI .
– All nodes in a completion graph for a knowledge base KB are either
an individual or connected to an individual iff KB contains at least
one individual. This property follows from the procedure of tableaux-based
algorithms, which start with a set of initial nodes consisting of individual
nodes (individuals or nominals) and create only new nodes which are con-
nected to an existing node. If KB does not contain any individual however,
tableaux-based algorithms typically start with an “invented” initial single
node labelled with CT given that T = ' ! CT . Remember that the exis-
tence of individuals was assumed as a precondition.
In the following we say that a concept C can be consistently added to the
.
label of a node w ∈ V of a completion graph G = (V, E, L, =) , iff G can be
completed into an open and complete graph using the completion rules after C
is added to the label of w.
Proof. Let KB = (T0 , A) and KB T = (T0 ∪ T , A).
⇐ If ¬CT is reachable from an individual x in KB , T affects x in KB
If ¬CT is reachable from an individual x, there is an n ∈ N0 such that if
n = 0 then ¬CT (x) or if n > 0 then (∃R1 . . . Rn .¬CT )(x) is satisfiable w.r.t.
KB . If n = 0 this means that KB ,|= CT (x) or if n > 0 this means that
KB ,|= (∀R1 . . . Rn .CT )(x). On the other hand, ' ! CT |= ' ! ∀R1 . . . Rn .CT
is trivially true, and therefore KB T |= CT (x) and KB T |= (∀R1 . . . Rn .CT )(x).
⇒ If T affects KB , then an individual x exists such that ¬CT is reach-
able from x in KB
Proof by contradiction, i.e. it is assumed that an effect exists but that ¬CT is
not reachable from x in KB .
Let D(x) be one of the possibly many effects of T on KB .
Since ¬D(x) is consistent w.r.t. KB , an open and complete completion graph
.
G = (V, E, L, =), for KB can be constructed such that ¬D ∈ L(x).
¬D(x) is inconsistent with the extended knowledge base KB T . Therefore the fol-
lowing procedure, extending the open and complete graph G leads to only closed
completion graphs: Add CT to the label of a node in V . Follow the completion
rules, and ensure that nodes newly created in the process are also labelled with
CT . Repeat for all nodes in G until for one node wC adding CT to L(wC ) leads
to only closed completion graphs.
Then however, ¬CT can be consistently added to L(wC ).
Since all nodes in a completion graph either are an individual node or connected
to one, there is then an individual y ∈ V from which a path to wC can be
constructed. Call this path yR1 w1 . . . Rn wC . If n = 0, then y = wC .
G can be translated into a model I such that wC ∈ (¬CT )I , and (y, w1 ) ∈ R1I ,
(w1 , w2 ) ∈ R2I , . . ., (wn−1 , wC ) ∈ RnI . Then, ¬CT is reachable in KB from y.
As by-product from the equivalence between axiom effects and reachability
the following corollary can be derived.
Corollary 1 If T = {' ! CT } affects KB , then an effect C(x) exists such
.
that C = ∀R1 . . . Rn .CT and Ri ∈ Σ, i = 1 . . . n. If n = 0, this corresponds to
C = CT . n is bounded by the maximal number of nodes in completion graphs for
the corresponding description logic.
Then, the following theorem about decidability follows immediately:
Theorem 2 The existence of assertional effects of T on KB can be decided in
all logics decidable under tableaux algorithms.
Some interesting observations follow from the these results: First, in order to
express such effects, DLs which contain at least ALC, i.e. which include nega-
tion over complex concepts and qualified universal/existential quantification,
are required. Second, if an effect exists, then not all effects are necessarily of the
.
form C(x) with C = ∀R1 . . . Rn .CT . As a simple example consider extending the
knowledge base KB = {R(a, b)} is with the TBox T = {' ! ∀R.A}. In this case,
the effect (∀R.A)(a) will be found if looking for effects of the above-mentioned
pattern, but clearly also A(b) is an effect. Third, although bounded, n can be
quite high: In SHOIQ, n is bounded double-exponentially with the size of the
closure of T0 (the smallest set containing all subconcepts of T0 and closed under
negation) and the number of roles and inverses occurring in the input [5, 7].
4.2 Generalisation to DLs with the connected model property
In description logics which additionally provide role union and the reflexive-
transitive closure
! (Kleene operator
∗
), “C is reachable from x in KB ” can also be
expressed as ∃( Ri ,R− ∈NR Ri ) .C(x). This led to the question of whether Theo-
∗
i
rem 1, which states equivalence between assertional effects and reachability, can
be generalised to require a more general property of the underlying description
logic than being decidable under a tableaux decision procedure. Indeed, it can
be shown that only the connected model property is required:
Definition 4. Connected model A model I = (∆I , ·I ) is connected if and only
if for every w ∈ ∆I there is an element x ∈ NI , xI = wo such that there is a
path w0 R1 w1 . . . Rn w in I.
A logic is said to have the connected model property if every satisfiable concept
or consistent knowledge base has a connected model. Since tree and forest models
are connected models, all logics which enjoy the tree (forest) model property, also
have the connected model property.
Theorem 3 In description logics with the connected model property T = {' !
CT } affects KB iff an individual x exists in KB such that ¬CT is reachable from
x in KB .
Proof. Theorem 3 Let KB = (T0 , A) and KB T = (T0 ∪ T , A).
⇐ If ¬CT is reachable from an individual x in KB , T affects x in KB
This direction is the same as in the proof for the tableaux-based Theorem 1.
⇒ If T affects KB , then an individual x exists such that ¬CT is reach-
able from x in KB
Proof by contradiction, i.e. it is assumed that an effect exists but that ¬CT is
not reachable from x in KB .
Let D(x) be one of the possibly many effects of T on KB .
Then there is a connected model I = (∆I , ·I ) of ¬D(x) w.r.t.
I is not a model however of the extended knowledge base KB T , since ¬D(x) is
inconsistent w.r.t. KB T .
Therefore, there is an element w ∈ ∆I such that w ,∈ (CT )I . Otherwise, ∆I =
(CT )I and I would also be a model of KB T .
Since w ,∈ (CT )I , it holds that w ∈ (¬CT )I .
Because of the connected model property, there is then an individual y ∈ NI
and y I = w0 such that there is a path w0 R1 w1 . . . Rn wC . If n = 0 this means
that w0 = wC . Then, ¬CT is reachable from the individual y, which contradicts
the assumption that ¬CT is not reachable from any individual in the knowledge
base.
Therefore, the problem of deciding
! whether T affects KB can be posed as
consistency checks of the form ∃( Ri ,R− ∈NR Ri )∗ .¬CT (x) for all x ∈ NI in DLs
i
which have the connected model property and the required concept and role con-
structors. Such a reformulation has the advantage of posing the original problem
as a standard reasoning problem. Naturally, this reformulation only makes sense
if the resulting logic is also decidable. A logic for which all these requirements
hold is for instance ALCQIb+ reg , which has been shown to be decidable [8]. Un-
fortunately no reasoners exist to date for this DL to the best of our knowledge.
4.3 TeA: Prototypical Implementation
The TeA prototype6 is, from a user’s point of view, a website where users can
upload a knowledge base, add terminological axioms and see the resulting as-
sertional effects. The TeA prototype accepts OWL knowledge bases and OWL
axioms as input. The current prototype can not be directly used to manipu-
late knowledge bases in any way but simply demonstrates the computation of
assertional effects. The TeA backend functionality will be integrated at some
point into the MoKi (a wiki environment for modelling) however, and there will
also support all editing activities, i.e. both deletion and addition of axioms. As
follows from Corollary 1, the depth n of an effect (∀R1 . . . Rn .CT )(x) could be
very large. In TeA a pragmatic approximation was implemented which limits
n. Hence, all assertional effects delivered by TeA are correct but TeA is not
guaranteed to find effects.
5 Related work
5.1 Conservative extensions in DL
Both conceptually and technically, conservative extensions in description logics
are a closely related topic. In short, deciding conservativity for two TBoxes T0
and T means finding out whether T0 ∪ T entails any inclusion axioms expressible
in a given vocabulary and a given DL that are not entailed by T0 alone [9, 10].
It can easily be shown that non-conservativity of T0 ∪ T with respect to T0 is
a precondition for the existence of TBox effects of T on KB = (T0 , R, A): By
inventing an ABox A = {'(x)}, any inclusion axiom entailed by T0 ∪ T but not
by T0 alone produces an effect on x.
However, non-conservativity is not a guarantee for the existence of effects. To
illustrate the latter, consider the following knowledge base KB = (T0 , R, A):
A ! ∀R.A
A ! ∃R.A (6)
A(x)
which is extended with T :
'!A (7)
6
TeA: http://services.know-center.tugraz.at:8080/TeA/Tea.html
Obviously, T0 ∪ T is not a conservative extension of T0 w.r.t. Σ = {A, R, x}
and the description logic ALC. There are however, no effects on the individual x,
since KB already entails all types that can be constructed from the vocabulary
{A, R} for x in ALC.
Complexity results for deciding conservativity therefore give a lower bound on
the complexity of deciding effects according to the deductive definition.
Depending on the choice of vocabulary, conservativity can be reduced to
subsumption if the full vocabulary of KB is considered [9]. Interestingly, the
problem becomes harder if the vocabulary under consideration is a subset of the
vocabulary used by KB . Then, conservativity is decidable up to ALCQI [10].
Using these results from conservativity now opens up the possibility to extend
the notion of assertional TBox effects as considered so far. Remember that as-
sertional TBox effects on a knowledge base have been defined only for the case
where Σ is the vocabulary in which KB T is formulated (Definition 4). If a con-
tributor is interested in effects in terms of a smaller vocabulary Σ $ ⊂ Σ, the
following procedure can be taken to circumvent this small restriction: Given is
the knowledge base KB = (T0 , R, A) which shall be extended with the TBox
T . Let KB T = (T0 ∪ T , R, A) and let Σ be the vocabulary in which KB T is
formulated. Furthermore we assume that Σ $ ⊂ Σ is the vocabulary and DL
the description logic in which the assertional effects on KB shall be formulated.
Then, in a first step it must be decided whether T0 ∪ T is a conservative ex-
tension of T0 w.r.t. Σ $ and DL can be decided. If T0 ∪ T is not a conservative
extension of T0 w.r.t. Σ $ and DL, then a witness concept CT$ such that ¬CT$ is
satisfiable w.r.t. T0 but unsatisfiable w.r.t. T0 ∪ T exists. A decision procedure
for conservativity such as e.g. in [10] outputs such a witness concept7 . Given
this CT$ , the question of whether and which assertional effects of T on KB exist
can be reformulated to the question whether ' ! CT$ affects KB , under the
condition that DL contains at least ALC.
Conceptually, we stress the difference in underlying motivation between con-
servative extensions and assertional TBox effects on a knowledge base. Compar-
ing TBoxes for differences is a general approach to support the frequent task
of extending or refining an ontology. The rationale behind focusing on effects in
terms of instance data is directed towards ontology edits in a specific ontology
application scenario, namely where the ontology describes data in a knowledge
base. In this scenario it is important that ontology and data are well aligned
with each other in order to maintain conceptual consistency. Second, expressing
effects of terminological axioms (general truths in a domain) in terms of con-
crete facts illustrates them in an easily understandable way8 . This gives users an
opportunity to double-check on whether the effectuated changes were actually
“meant this way”.
7
Note that this particular decision procedure would actually output the negation of
CT! .
8
Compare also [2], in which the creation of concept definitions from exemplary indi-
viduals is being discussed for exactly the same reason. It often seems to be helpful
to think in concrete terms when formulating abstractions.
5.2 Reasoning services for ontology engineering
In continuance of the idea underlying conservativity, Kontchakov et al [11] study
the differences between DL-Lite TBoxes. Especially, the authors study query-
differences over arbitrary ABoxes. Then the set of query-differences is either
empty (the two TBoxes do not differ in terms of queries given a specific vo-
cabulary at all) or infinite (infinitely many ABoxes exist after all). Naturally it
would be interesting to consider effects in terms of queries over a specific ABox,
which we have not done so far. We speculate that the results for such a problem
formulation will be similar than the comparison of deductively defined effects
with conservative extension, namely that it is at least as hard as deciding the
existence of query-differences, and not immediately clear how the existence of
query-differences then can be decided for a given ABox.
On a more general note, ontology editors like Swoop [12] and Protégé [13] dis-
play inferred types for all individuals and concepts in the loaded knowledge base.
Typically, such inferred types involve only primitive concepts. Additionally, the
dynamic aspect of the ontology edits is not considered in that inferred types are
shown for a complete knowledge base, and no relation is automatically made to
the most recent activities.
Under the names of ontology debugging and repair, reasoning services which
pinpoint axioms responsible for unsatisfiable concepts and suggest ways to re-
pair the ontology have been researched, see e.g. [14, 15]. Inference explanation,
e.g. [16, 17], is based on the same theoretical foundation, but with a different
focus in application, as is already suggested through the naming. Both ontology
repair and inference explanation start with an identified problem, whereas the
study of assertional effects seeks to make potential problems (effects) visible. In
this sense, repair and explanation are complementary reasoning services useful
after having identified a problematic effect.
6 Discussion and Outlook
Informative Effects Consider as slightly extended example a knowledge base
which contains diverse facts such as “Crete is an Island”, “The Mediterranean
is a Sea” and “Sophocles is a Greek” (8) . It is overlaid with an ontology that
defines relevant key concepts such as areas of land vs. areas of water, nations
etc, and that an island is a land-area, while a sea is a water-area, defined as
subsumption. One contributor decides to increase the accuracy of the ontology,
and adds a disjointness axiom for land- and water-areas (9), and an existential
restriction which states that each island must be located in some water-area (10).
Greek(sophocles)
Island(crete) (8)
Sea(mediterranean)
LandArea ) W aterArea ! ⊥ (9)
Island ! ∃locatedIn.W aterArea (10)
Then, depending on which kinds of facts “count”, effects of the disjointness
axioms are ¬W aterArea(crete), ¬LandArea(mediterranean) but also
(¬W aterArea(¬LandArea)(sophocles). Additionally, the existential restriction
(∃locatedIn.W aterArea)(crete) but also
(¬Island ( ∃locatedIn.W aterArea)(sophocles) are newly entailed facts.
As a personal rating, we would consider ¬W aterArea(crete),
¬LandArea(mediterranean) and (∃locatedIn.W aterArea)(crete) to be more
informative than for instance (¬W aterArea ( ¬LandArea)(sophocles) or
(¬Island ( ∃locatedIn.W aterArea)(sophocles). This short list demonstrates
that some assertional effects are more informative than others, and that this
quality does not directly depend on whether complex concepts are involved or
not. It is to date not completely clear which characteristics determine how in-
formative an assertional effect is. This shall be captured by a user study as part
of ongoing research.
Exemplary effects A critical issue concerning assertional effects in the envisioned
scenario concerns the quantity of data to be dealt with. Intuitively, if a knowl-
edge base contains data about a million song-titles and a new axiom stating that
“every song has an author” is added which, it is clearly not desirable to see a
million effects of the form “The song XY has an author”. Instead, assertional
effects should be expressed using exemplary individuals only. A lead into that
direction could be given by techniques such as ABox summarization [18]. The
authors exploit the observation that similar individuals are related in similar
ways to other individuals. For instance, songs have titles, belong to albums and
have maybe been in some charts for a given period of time. Songs do not however
have parents or children as do human persons. Thus, individuals about which
similar assertions exist in a knowledge base can be grouped together. The main
issues which need to be studied when applying this ABox summarization to the
computation of exemplary assertional effects are that (i) ABox summarization
has been defined for SHIN only in [18] and (ii) the summary ABox does not pre-
serve consistency, i.e. it is possible that the summary ABox is inconsistent while
the original ABox is consistent w.r.t. a knowledge base. Apart from these theo-
retical issues however, the benefit clearly lies not only in enabling an improved
presentation to the user but also in increasing the computational performance
(though not the computational complexity class).
Extending the definition of assertional effects The definition of assertional TBox
effects on a knowledge base (Definition 1) can be extended into a variety of di-
rections. One such extension, namely the possibility to restrict the vocabulary
under consideration to a subset of the vocabulary Σ in which KB T is formulated,
has already been discussed in Section 5 in relation with conservative extensions.
Another obvious but much more simple extension is to consider also role asser-
tions R(x, y) as assertional effects. This is trivial in DL languages in which the set
of roles which can occur in role assertions is finite, as is the case in both SHOIQ
and SROIQ and thus also in OWL 1 and OWL 2. Then, for every R ∈ NRext and
every pair (x, y), x, y ∈ NI , it simply needs to be checked whether KB ,|= R(x, y)
and KB T |= R(x, y). In SHOIQ, NRext = NR− = {R|R ∈ NR or R− ∈ NR }. For
SROIQ, NRext must be extended to be closed under negation. We note that
unless nominals occur in T , terminological axioms can not cause the gain or
loss of role assertion axioms. Furthermore, also equality or inequality assertions
between individuals could be considered as effects. Such effects may occur when
T contains nominals or number restrictions.
Finally, the notion of assertional effects could also be extended to consider as-
sertional effects of the addition or removal of role axioms.
7 Conclusion
We anticipate the spreading of collaborative description logic knowledge bases
in which users contribute not only by adding textual or multimedia content but
also facts about individuals or other axioms. Our approach to ensure conceptual
consistency of such knowledge bases is to highlight the consequences of termi-
nological axioms in terms of instance data, namely as facts which are lost or
gained. Contributors to a DL knowledge base benefit from this approach in two
different ways. First, such assertional effects give concrete examples of the gen-
eral knowledge (terminological axioms) which was removed or added. Second,
assertional effects take into account the complex interactions between all the
terminological, role and assertional axioms in the knowledge base.
Based on a formal definition of assertional TBox effects on a knowledge base, we
have derived conditions for decidability. In particular, the problem of deciding
the existence of assertional effects has been shown to be equivalent to deciding
the reachability of a given concept in a knowledge base if the underlying DL has
the connected model property. Additionally, we considered only DL languages
at least as expressive as ALC in our discussion. Consequently, our results hold
both for SHOIQ and SROIQ, the DL languages underlying OWL 1 and 2
respectively.
In a detailed discussion we pointed to wider-reaching conceptual issues such as
which assertional effects are informative to knowledge base contributors and how
assertional effects can be presented to contributors in a meaningful way in the
presence of a large quantity of data in the knowledge base. These issues are
investigated in ongoing and future research.
Acknowledgements
Some of the authors are supported by APOSDLE (www.aposdle.org), which is
partially funded under the FP6 of the European Commission within the IST work
program 2004 (FP6-IST-2004-027023). The Know-Center is funded within the
Austrian COMET Program - Competence Centers for Excellent Technologies
- under the auspices of the Austrian Ministry of Transport, Innovation and
Technology, the Austrian Ministry of Economics and Labor and by the State
of Styria. COMET is managed by the Austrian Research Promotion Agency
FFG.
References
1. Krötzsch, M., Vrandecic, D., Vlkel, M., Haller, H., Studer, R.: Semantic wikipedia.
Journal of Web Semantics 5 (Sept. 2007) 251–261
2. Lutz, C., Baader, F., Franconi, E., Lembo, D., Möller, R., Rosati, R., Sattler,
U., Suntisrivaraporn, B., Tessaris, S.: Reasoning support for ontology design. In:
OWL: Experiences and Directions 2006. (2006)
3. OWL Web Ontology Language Reference: http://www.w3.org/tr/owl-ref/, last
visited 2008-11-28
4. OWL 2 Web Ontology Language Quick Reference Guide:
http://www.w3.org/tr/owl2-quick-reference/, last visited 2009-07-15
5. Horrocks, I., Sattler, U.: A tableau decision procedure for SHOIQ. J. Autom.
Reason. 39(3) (2007) 249–276
6. Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: Proc.
of the 10th Int. Conf. on Principles of Knowledge Representation and Reasoning
(KR 2006), AAAI Press (2006) 57–67
7. Horrocks, I., Sattler, U., Tobies, S.: Reasoning with individuals for the description
logic SHIQ. In: CADE-17: Proceedings of the 17th International Conference on
Automated Deduction, London, UK, Springer-Verlag (2000) 482–496
8. Ortiz, M.: An automata-based algorithm for description logics around SRIQ.
In: Proceedings of the Fourth Latin American Workshop on Logic/Languages,
Algorithms and Non-Monotonic Reasoning 2008 (LANMR’08). Volume 408.,
Puebla,Mexico, CEUR Workshop Proceedings (October 2008)
9. Ghilardi, S., Lutz, C., Wolter, F.: Did I damage my ontology? A case for con-
servative extensions in description logics. In: Proceedings of KR2006: the 20th
International Conference on Principles of Knowledge Representation and Reason-
ing, 2006, AAAI Press (2006) 187–197
10. Lutz, C., Walther, D., Wolter, F.: Conservative extensions in expressive description
logics. In: Proceedings of the Twentieth International Joint Conference on Artificial
Intelligence IJCAI-07, AAAI Press (2007)
11. Kontchakov, R., Wolter, F., Zakharyaschev, M.: Can you tell the difference between
dl-lite ontologies? In: KR 2008: Eleventh International Conference on Principles
of Knowledge Representation and Reasoning. (2008)
12. Swoop: http://code.google.com/p/swoop/. Last visited 2008-11-28
13. Protégé: http://protege.stanford.edu/. Last visited 2008-11-28
14. Kalyanpur, A., Parsia, B., Sirin, E., Hendler, J.: Debugging unsatisfiable classes
in OWL ontologies. Journal of Web Semantics 3(4) (2005) 268–293
15. Schlobach, S., Huang, Z., Cornet, R., Harmelen, F.: Debugging incoherent termi-
nologies. J. Autom. Reason. 39(3) (2007) 317–349
16. Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of OWL
DL entailments. In: Proceedings of the 6th International Semantic Web Conference
and 2nd Asian Semantic Web Conference (ISWC/ASWC2007). Volume 4825 of
LNCS., Springer Verlag (November 2007) 267–280
17. Horridge, M., Parsia, B., Sattler, U.: Laconic and precise justifications in OWL. In:
International Semantic Web Conference. Volume 5318 of Lecture Notes in Com-
puter Science., Springer (2008) 323–338
18. Fokoue, A., Kershenbaum, A., Ma, L., Schonberg, E., Srinivas, K.: The summary
abox: Cutting ontologies down to size. In: International Semantic Web Conference.
Volume 4273 of Lecture Notes in Computer Science., Springer (2006) 343–356