=Paper=
{{Paper
|id=None
|storemode=property
|title=Ontology adaptation upon updates
|pdfUrl=https://ceur-ws.org/Vol-999/paper5.pdf
|volume=Vol-999
|dblpUrl=https://dblp.org/rec/conf/esws/SolimandoG13a
}}
==Ontology adaptation upon updates==
https://ceur-ws.org/Vol-999/paper5.pdf
Ontology Adaptation upon Updates
Alessandro Solimando, Giovanna Guerrini
Dipartimento di Informatica, Bioingegneria, Robotica e Ingegneria dei Sistemi
Università di Genova, Italy
name.surname@unige.it
Abstract. Ontologies, like any other model, change over time due to
modifications in the modeled domain, deeper understanding of the do-
main by the modeler, error corrections, simple refactoring or shift of
modeling granularity level. Local changes usually impact the remainder
of the ontology as well as any other data and metadata defined over
it. The massive size of ontologies and their possible fast update rate
requires automatic adaptation methods for relieving ontology engineers
from a manual intervention, in order to allow them to focus mainly on
high-level inspection. This paper, in spirit of the Principle of minimal
change, proposes a fully automatic ontology adaptation approach that
reacts to ontology updates and computes sound reformulations of onto-
logical axioms triggered by the presence of certain preconditions. The
rule-based adaptation algorithm covers up to SROIQ DL.
1 Introduction and Motivations
Ontologies, like any other model, change over time and a revalidation of all data
and metadata defined on top of the modified ontology is needed upon updates.
Massive ontology size and fast update rate1 call for automated support and
adaptation algorithms. Despite the great attention devoted in the last ten years
to ontology evolution [1, 7], to the best of our knowledge there are no proposals
in the literature coping with ontology adaptation upon updates. With similar
motivations, an adaptation algorithm for a subset of SPARQL queries (with ex-
pressivity equivalent to union of Conjunctive Queries) in response to ontology
updates is proposed in [6]. Protégé 2 , one of the most complete ontology frame-
works, does not support any kind of adaptation w.r.t. ontology updates: when a
concept or a role is deleted, all the axioms referring it are removed as well. Even
if there are cases in which this behavior is acceptable (e.g., error corrections),
there are others for which it is detrimental, for instance a modification of the
modeling granularity of the ontology. In this scenario, a sound reformulation of
axioms by means of super/sub concepts or roles is not only desirable but usu-
ally manually performed by the modeler. Additionally, in Artificial Intelligence
(Belief Revision), knowledge deletion usually follows the Principle of Minimal
1
An example is the Gene Ontology (http://www.geneontology.org/), with ∼ 416K
axioms and ∼ 40K entities, daily updated (statistics for data-version 2013-02-22).
2
Available here: http://protege.stanford.edu/
57
Change [5], which suggests that the amount of lost information should be as
minimal as possible. Given that ontologies do not necessarily (explicitly) include
all their logical consequences, also the implicit knowledge should be taken into
account, as well as explicit one (that is, ontology axioms).
While a set of basic ontology changes can be easily defined, it is impossible
to identify a set of complex changes without fixing the granularity level, i.e., up-
dates expressed as arbitrarily complex graph patterns (see [10], Section 3.2.1). In
this proposal we consider the basic updates proposed by [3]: addition, deletion
and update of entities (concepts and roles). Given that adding or updating enti-
ties do not reduce knowledge, and that ontology consistency can be tested using
ontology reasoners, our adaptation algorithm focuses only on entity deletions.
In this paper, we propose an algorithm that, given an ontology and an entity
(concept or role) to delete, scans for an equivalent, a super and a sub-entity
and tries to reformulate the axioms involving the entity in question, with a rule-
based approach. Our reformulated axioms are a fraction of the implicit knowledge
of the ontology under update that would be lost by deleting all of the axioms
involving the removed entity. An alternative would be to compute the closure
(that is, complete inference of implicit knowledge) for the ontology prior to entity
deletion. Due to its high computational cost and possible non-finiteness of the
result, a suboptimal but less expensive approach is preferable for our target
scenario, that is interactive modeling.
Even if the adaptation algorithm is completely automatic, it may not always
be aligned with the modeler’s intention. For this reason, the present proposal
has to be intended as an optional feature. When activated, it provides a preview
of the changes to show the automatic adaptation effects. On this basis, the mod-
eler can accept or ignore the proposed changes. In addition, a straightforward
extension could be the possibility, for the modeler, to select the equivalent (resp.
sub/super) entity for the reformulation, when different alternatives are available.
The contribution of the present paper can be summarized as follows: an
automatic adaptation algorithm supporting up to SROIQ expressivity, its cor-
rectness proof, and temporal complexity analysis (Section 3), an experimental
evaluation of the percentage of adaptable entities and axioms on a dataset of
real ontologies (Section 4). First, DL basics are introduced (Section 2), and the
paper concludes discussing future work (Section 5).
2 Preliminaries
Our proposal covers up to SROIQ Description Logic (DL), on top of which the
Ontology Web Language (OWL2) [11] is defined. The notations and definitions
used in this section are borrowed from [4]. An ontology is defined by a set
of axioms and a set of entity names (signature), composed by three disjoint
subsets: NR for role names, NI for individual names, NC for concept names.
These entities are defined by means of expressions. We have Role expressions
−
R ::= U | NR | NR , and Concept expressions C ::= NC | (C tC) | (C uC) | ¬C |
> | ⊥ | ∃R.C | ∀R.C | ≥n R.C | ≤n R.C | ∃R.Self | {NI }, with n ≥ 0. For the
58
Precondition Rule
a.1 C ≡ C0, axiom → axiom[C/C 0 ]
C ∈ signature(axiom)
a.2 CvD E ≡ ∃R.C → E v ∃R.D
a.3 CvD E ≡≥n R.C → E v≥n R.D
a.4 CvD E ≡C tF →E vDtF
a.5 CvD E ≡C uF →E vDuF
a.6 CvD E ≡ ¬C → ¬D v E
a.7 CvD C(a) → D(a)
a.8 CvD E ≡ ∀R.C → E v ∀R.D
a.9 BvC E ≡≤n R.C → E v≤n R.B
a.10 BvC E ≡C tF →BtF vE
a.11 BvC E ≡C uF →BuF vE
a.12 BvC E ≡ ¬C → E v ¬B
a.13 BvC CvE→BvE
Table 1. Adaptation rules for concept deletion DEL(C), where B, C, C 0 , D, E, F ∈ NC ,
R ∈ NR and a ∈ NI .
semantics associated with nominals, role and concept expressions the reader may
refer to [4]. The set of axioms of an ontology, denoted with Axioms, is defined as
Axiom ::= ABox ∪ RBox ∪ T Box. The reader may refer to [4] also for a detailed
description of the different available axioms for SROIQ DL, and to [9] for the
definitions of ontology interpretation and ontology satisfiability. W.l.o.g. in the
paper we will consider normalized ontologies in Negation Normal Form (NNF),
with an application of Structural Reduction (SR), as shown in [9] (Subsection
5.3). SR introduces fresh concept names for (complex) concept expressions, thus
letting us to easily refer to each concept expression by means of its associated
concept name. Neither the SR nor the NNF are required for the application of
our method. NNF, however, may increase the ratio of adapted axioms.
3 Algorithm
This section introduces the adaptation rules (Section 3.1), the rule-based adap-
tation algorithm (Section 3.2), the correctness proof for the given rules (Sec-
tion 3.3), and the temporal complexity of the algorithm (Section 3.4).
3.1 Adaptation Rules
The adaptation rules are presented in Table 1 (rules for concepts) and Table 2
(rules for roles). We denote by axiom[A/B] the alpha renaming of an axiom of
entity A by entity B. A rule r is composed by a left hand side, LHS(r), a right
hand side, RHS(r), and a precondition prec(r). A rule is defined applicable
iff prec(r) is satisfied by at least one concept (resp. role). Given an ontology o
and an entity e to delete, the LHS of a rule r is said to be matching iff an
axiom in o exists that is equal to LHS(r) modulo alpha renaming of C (resp. R)
59
Precondition Rule
b.1 R ≡ R0 , axiom → axiom[R/R0 ]
R ∈ signature(axiom)
b.2 QvR T0 ◦ . . . ◦ Tm ◦ R ◦ T00 ◦ . . . ◦ Tp0 v T
→ T0 ◦ . . . ◦ Tm ◦ Q ◦ T00 ◦ . . . ◦ Tp0 v T
b.3 QvR E ≡ ∀R.C → E v ∀Q.C
b.4 QvR E ≡≤n R.C → E v≤n Q.C
b.5 QvR T ≡ R − → Q− v T
b.6 QvR Disjoint(R, T ) → Disjoint(Q, T )
b.7 RvS R(a, b) → S(a, b)
b.8 RvS E ≡ ∃R.C → E v ∃S.C
b.9 RvS E ≡ ∃R.Self → E v ∃S.Self
b.10 RvS E ≡≥n R.C → E v≥n S.C
b.11 RvS T ≡ R− → T v S −
b.12 RvS T0 ◦ . . . ◦ Tq v R → T0 ◦ . . . ◦ Tq v S
Table 2. Adaptation rules for role deletion DEL(R), where E, C ∈ NC , Q, R, R0 , S,
T , Ti , Tj0 ∈ NR , with m, n, p, q ≥ 0, and a, b ∈ NI .
with e, denoted with LHS(r)[e]. The application of an applicable rule r w.r.t.
o and e rewrites any axiom of o matching LHS(r)[e] into RHS(r)[e0 ], where
e0 is the selected entity for reformulation. It is worth noting that if a DL less
expressive than SROIQ is adapted, only a subset of the rules will be applicable,
depending on the axioms and constructors available. For instance, for basic ALC
with General Concept Inclusion (i.e., C v D), rules a.3, a.9, b.2, b.4, b.5, b.9,
b.10, b.11, b.12 are not applicable.
3.2 Adaptation Algorithm
Algorithm 1 presents the adaptation algorithm for ontology updates. It takes as
input the entity e to be deleted and the ontology o it belongs to. By means of
function computeP rec, the set of axioms related to e is computed, as well as
a triple p consisting of a (nondeterministically choosen) equivalent, a sub and
a super entity, if any (line 3). For each axiom a having e in its signature (line
4), it tests if the axiom matches the left hand side of the rule (line 5). At this
point, function satisf ies (line 6) checks if the current axiom is compatible with
rule r and if the required element in p is not null. The reformulated axiom is
inserted in o (line 7). Finally, all the axioms involving entity e are removed from
o (line 8). Even if a preliminar classification phase is not required, it may increase
the algorithm effectiveness. In what follows we give a toy example of ontology
update, comparing the result of adaptation to classical deletion approach.
Example 1. Consider an ontology o consisting of these axioms and the ob-
vious associated signature: Human ≡ ∃eats.F ood, F ood(cheese), Eater ≡
∀eats.F ood, ⊥ ≡ P lastic u F ood, U neatable ≡ ¬Eatable, P izza v F ood,
F ood v Eatable. Deleting F ood concept from o with adaptation we obtain:
Human v ∃eats.Eatable, Eatable(cheese), Eater v ∀eats.Eatable, P lastic u
60
Algorithm 1 Ontology Update Adaptation
1: function OntoUpdateAdapt(Entity e, Ontology o)
2: axioms = ∅
3: p := heq, sub, supi ← computeP rec(e, axioms, o)
4: for a ∈ axioms do
5: for r ∈ Rules . a = LHS(r)[e] do
6: if satisf ies(ha, e, e0 i, prec(r)), e0 ∈ {eq, sub, sup} then
7: Axioms(o) ← Axioms(o) ∪ {RHS(r)[e0 ]}
8: end if
9: end for
10: end for
11: Axioms(o) ← Axioms(o) \ axioms
12: end function
13: function computePrec(Entity e, Set axioms, Ontology o)
14: eq, sub, sup ←
15: for a ∈ Axioms(o) . e ∈ signature(a) do
16: axioms ← axioms ∪ {a}
17: if eq, sub, sup 6= then
18: break
19: end if
20: if a = e ≡ e0 or a = e0 ≡ e then
21: eq ← e0
22: else if a = e v e0 then
23: sup ← e0
24: else if a = e w e0 then
25: sub ← e0
26: end if
27: end for
28: return heq, sub, supi
29: end function
P izza v ⊥, P izza v Eatable, U neatable ≡ ¬Eatable (using rule a.2, a.7, a.8,
a.11 and a.13, respectively). Without adaptation, instead, only the last axiom
would be present in o after concept deletion.
3.3 Rules Correctness Proof
Before stating the proposition about the correctness of the adaptation rules we
introduce some definitions and lemmata. For sake of brevity we will interchange-
ably refer to the axioms and their semantics, according to [4].
Definition 1. An axiom A1 entails an axiom A2 iff, for any interpretation I,
I |= A2 =⇒ I |= A1 , that is A2 I ⊆ A1 I .
Definition 2. An adaptation rule r is sound iff {LHS(r), prec(r)} entails
RHS(r).
Lemma 1. ∀C, D, F ∈ NC . C v D =⇒ C t F v D t F .
Proof. By considering the associated semantics the Lemma can be restated as
C I ⊆ DI =⇒ |C I {z∪ F I} ⊆ D I
| {z∪ F I}. Assume that the preceding formula does
α β
not hold, that is α 6⊆ β. This means ∃x ∈ β . x 6∈ α, and requires that at least
one of the following conditions holds:
61
– x ∈ F I , but this implies x ∈ α, resulting in a contradiction,
– x ∈ C I , and thus this implies C I ⊆ DI =⇒ x ∈ α, contradicting the
hypothesis.
Lemma 2. ∀C, D, F ∈ NC . C v D =⇒ C u F v D u F .
Proof. By considering the associated semantics the Lemma can be restated as
C I ⊆ DI =⇒ |C I {z
∩ F I} ⊆ D I
| {z∩ F I}. Assume that the preceding formula does not
α β
hold, that is α 6⊆ β. This means ∃x ∈ β . x 6∈ α. Note that x ∈ β is equivalent
to requiring that x ∈ F I ∧ x ∈ DI holds. However, x ∈ F I ∧ x 6∈ α =⇒ x 6∈ C I .
Given that x ∈ DI holds, this contradicts the premise C v D.
Lemma 3. ∀C, D ∈ NC . C v D =⇒ ∃R.C v ∃R.D.
Proof. Assume that {x | ∃y ∈ C I . hx, yi ∈ RI } 6⊆ {x | ∃y ∈ DI . hx, yi ∈ RI }
holds, that is, ∃R.C 6v ∃R.D. This requires that the following condition holds:
∃hx, yi ∈ RI . y ∈ C I ∧ y 6∈ DI . But, if such condition holds, then C 6v D,
contradicting the premise.
Lemma 4. ∀C, D ∈ NC . C v D =⇒ ∀R.C v ∀R.D.
Proof. Assume that {x | ∀hx, yi . hx, yi ∈ RI =⇒ y ∈ C I } 6⊆ {x |
I I
∀hx, yi . hx, yi ∈ R =⇒ y ∈ D } holds, that is, ∀R.C 6v ∀R.D. This requires
that the following condition holds: (∃x . ∀hx, yi . hx, yi ∈ RI =⇒ y ∈ C I ) ∧ (∃ȳ
. hx, ȳi ∈ RI ∧ ȳ 6∈ DI ). But, if this condition holds, then an ȳ exists and RI is
not empty. Therefore, since the left operand of the implication holds, then right
operand also does. From this, we obtain C I 6⊆ DI , contradicting the premise.
Proposition 1. Adaptation rules application preserves ontology satisfiability.
Proof. Ontology satisfiability is preserved because every adaptation rule is
sound. We prove this for each rule separately:
a.1 The proof directly follows from Concept Equivalence axiom definition.
a.2 E ≡ ∃R.C → E v ∃R.D. ∃R.C v ∃R.D must hold: thanks to the rule
precondition, C v D, we can apply Lemma 3.
a.3 E ≡≥n R.C → E v≥n R.D. ≥n R.C v≥n R.D must hold, but it is
sufficient that {x | ∃y ∈ C I . hx, yi ∈ RI } ⊆ {x | ∃y ∈ DI . hx, yi ∈ RI }
holds. Thanks to the rule precondition, C v D, we can apply Lemma 3.
a.4 E ≡ C t F → E v D t F . C t F v D t F holds for Lemma 1 because
C v D holds.
a.5 E ≡ C u F → E v D u F . C u F v D u F holds for Lemma 2 because
C v D holds.
a.6 E ≡ ¬C → ¬D v E. ¬D v ¬C must hold: the semantics is ∆I \ DI ⊆
∆I \ C I , but this contradicts C v D.
a.7 C(a) → D(a). C(a) =⇒ D(a) is guaranteed by the rule precondition.
a.8 E ≡ ∀R.C → E v ∀R.D. E ≡ ∀R.C =⇒ E v ∀R.D holds for Lemma 4
because C v D holds.
62
a.9 E ≡≤n R.C → E v≤n R.B. ≤n R.B v≤n R.C, but it is sufficient that
{x | ∃y ∈ B I . hx, yi ∈ RI } ⊆ {x | ∃y ∈ C I . hx, yi ∈ RI }. Thanks to the
rule precondition, B v C, we can apply Lemma 3.
a.10 E ≡ C t F → B t F v E. The proof for B t F v C t F is the dual of the
one given in item (a.4).
a.11 E ≡ C u F → B u F v E. The proof for B u F v C u F is the dual of the
one given in item (a.5).
a.12 E ≡ ¬C → E v ¬B. the proof for ¬C v ¬B is the dual of the one given
in item (a.6).
a.13 C v E → B v E. The rule precondition, B v C. By transitivity, this
implies B v E.
b.1 The proof directly follows from Role Equivalence axiom definition.
b.2 T0 ◦ . . . ◦ Tm ◦ R ◦ T00 ◦ . . . ◦ Tp0 v T → T0 ◦ . . . ◦ Tm ◦ Q ◦ T00 ◦ . . . ◦ Tp0 v
| {z } | {z }
α β
T . assume that β I 6⊆ αI holds. This requires that ∃x0 , . . ., xm+p+3 .
I
hx0 , x1 i ∈ T0 I ∧ . . . ∧ hxm+1 , xm+2 i ∈ QI ∧ hxm+p+2 , xm+p+3 i ∈ Tp0 ∧
I
hxm+1 , xm+2 i 6∈ R . This contradicts Q v R.
b.3 E ≡ ∀R.C
| {z } → E v ∀Q.C . Assume that αI 6⊆ β I holds. This requires that
| {z }
α β
∃x . x ∈ αI ∧ x 6∈ β I , that is, ∃x.((∀y . hx, yi ∈ RI =⇒ y ∈ C I ) ∧ (∃y 0
. hx, y 0 i ∈ QI ∧ y 0 6∈ C I )). Given that Q v R, if such y 0 exists, α cannot
hold, leading to a contradiction.
b.4 T ≡ ≤n R.C → T v ≤n Q.C . Assume that αI 6⊆ β I . This requires that
| {z } | {z }
α β
∃x . |{y | y ∈ C I ∧ hx, yi ∈ RI }| ≤ n ∧ |{y | y ∈ C I ∧ hx, yi ∈ QI }| > n.
This implies |QI | > |RI |, contradicting Q v R.
I I
b.5 T ≡ R− → Q− v T . Assume that Q− 6⊆ R− . This requires that ∃hx, yi
. hy, xi ∈ Q ∧ hy, xi 6∈ R . This contradicts QI ⊆ RI .
I I
b.6 Disjoint(R, T ) → Disjoint(Q, T ). Assume that RI ∩ T I = ∅ =⇒ QI ∩
T I = ∅ does not hold. This requires that ∃hx, yi ∈ QI ∧ hx, yi ∈ T I ∧
hx, yi 6∈ RI holds, but hx, yi ∈ QI ∧ hx, yi 6∈ RI contradicts Q v R.
b.7 R(a, b) → S(a, b). From R v S we have that ∀hx, yi . hx, yi ∈ R =⇒
hx, yi ∈ S.
I I
| {z } → E v ∃S.C
b.8 E ≡ ∃R.C | {z }. Assume that α 6⊆ β . This requires that ∃x .
α β
∃y ∈ C I . hx, yi ∈ S I ∧ hx, yi 6∈ RI holds. This contradicts R v S.
b.9 E ≡ ∃R.Self → E v ∃S.Self . Assume that αI 6⊆ β I . This requires that
| {z } | {z }
α β
∃x . hx, xi ∈ S I ∧ hx, xi 6∈ RI holds. This contradicts R v S.
b.10 E ≡ ≥n R.C → E v ≥n S.C . Assume that αI 6⊆ β I . This requires that
| {z } | {z }
α β
∃x . |{y | y ∈ C I ∧ hx, yi ∈ RI }| ≥ n ∧ |{y | y ∈ C I ∧ hx, yi ∈ S I }| < n.
This implies |RI | > |S I |, contradicting R v S.
63
I I
b.11 T ≡ R− → T v S − . Assume that R− 6⊆ S − . This requires that ∃hx, yi
. hy, xi ∈ RI ∧ hy, xi 6∈ S I , thus contradicting R v S.
b.12 T0 ◦ . . . ◦ Tq v R → T0 ◦ . . . ◦ Tq v S. This immediately follows, by
transitivity, from R v S.
3.4 Temporal Complexity
Proposition 2. The time complexity of the algorithm is in O(n), where n is
the number of axioms of the input ontology o.
Proof. computeP recond scans all the axioms of ontology o. For each of them it
performs some comparison having a total cost of c1 , so it has a cost of n · c1 . The
for statement of line 4 in Algorithm 1 is executed n times in the worst case (each
axiom of the ontology refers to the entity in question). The for statement of line
5 is executed c2 = |Rules| times, where Rules is the set of adaptation rules.
satisf ies test requires a constant (c3 ) time for checking the required conditions.
Axiom rewriting and its insertion requires constant (c4 ) time. The removal of
old axioms requires constant time (c5 ) too. The overall complexity is therefore
equal to n · c1 + c2 · c3 · c4 · n + c5 , that belongs to O(n).
4 Experiments
In order to evaluate the practical applicability of our proposal we implemented
a Java prototype based on the OWL API library3 . In OWL API the axioms are
immutable objects, and it supports only axiom addition and removal. Whenever
possible, the rule application has been simulated with a pair of add and delete
changes. In the other cases we employed Java Reflection for directly modifying
the involved axiom. In addition to correctness, we also experimentally evaluated
the coverage of OWL2 axioms and constructors of our set of rules. The dataset
is presented in Table 3 (manual selection on the Web based on ontology size and
DL expressivity).
Correctness The developed proof-of-concept prototype has been used for testing
correctness of our adaptation rules, the experimental counterpart of the proofs
given in Section 3.3. More precisely, the test consists in taking as input a satisfi-
able ontology composed by the precondition and an axiom corresponding to the
LHS of a rule r (modulo alpha renaming of the entity to delete). At this point,
using Hermit reasoner (v1.3.7)4 , we check the entailment of RHS(r)[e0 ].
Evaluation An entity e is adaptable iff it satisfies at least one rule precondition,
while an axiom a is adaptable iff it at least one rule r s.t. LHS(r)[e] = a
exists, in case prec(r) holds w.r.t. e, the axiom is said fully adaptable. As
an estimation of the practical effectiveness of our algorithm, we consider, for
3
Available here: http://owlapi.sourceforge.net/
4
Hermit and related information are available at http://hermit-reasoner.com/
64
ID DL URI Axioms Logical Axioms (C.1) (C.2) (C.3) (C.4) (C.2)* (C.4)*
1. ALUQ(D) http://omv.ontoware.org/2009/09/OWLChanges 186 100 100.00 49.49 0.00 N/A 49.49 N/A
2. SHIN(D) http://ccdb.ucsd.edu/SAO/1.2 7767 2712 100.00 17.92 97.22 76.17 17.95 76.17
3. ALEHI+(D) http://swat.cse.lehigh.edu/onto/univ-bench.owl 243 93 97.67 35.11 36.00 45.16 37.10 45.16
4. SHOIN(D) http://www.w3.org/TR/2003/CR-owl-guide-20030818/wine 747 657 94.81 67.88 84.62 66.96 88.29 66.96
5. ALCO http://purl.obolibrary.org/obo/ogms.owl 576 84 100.00 50.00 N/A N/A 50.00 N/A
6. ALQ(D) http://owlodm.ontoware.org/OWL2 353 215 90.80 45.50 0.00 N/A 46.91 N/A
7. SRIQ(D) http://semanticscience.org/ontology/sio-core.owl 5043 1747 100.00 48.07 100.00 93.55 48.43 93.55
8. SHOIN http://www.co-ode.org/ontologies/pizza/pizza.owl 939 712 100.00 22.14 75.00 100.00 22.15 100.00
9. SHOIN(D) http://sweet.jpl.nasa.gov/2.1/reprSciUnits.owl 503 475 100.00 8.20 33.33 0.00 42.86 0.00
10. SR http://purl.obolibrary.org/obo/hao/2011-11-03/hao.owl 20027 8493 96.22 38.53 0.00 N/A 50.47 N/A
11. SROIF http://purl.obolibrary.org/obo/ido.owl 3499 1025 100.00 34.67 86.67 67.02 36.92 67.73
12. SROIF http://ontology.neuinfo.org/NIF/Dysfunction/NIF-Dysfunction.owl 5649 350 100.00 50.00 N/A N/A 50.00 N/A
13. SHIN(D) http://aims.fao.org/aos/geopolitical.owl 23527 22834 100.00 100.00 100.00 100.00 100.00 100.00
14. S http://human.owl 30364 11545 99.82 49.84 0.00 N/A 49.84 N/A
15. ALE http://mouse.owl 11043 4838 67.02 36.99 0.00 N/A 38.93 N/A
16. ALCHOIN http://owl.man.ac.uk/2005/07/sssw/people.owl 396 108 100.00 69.94 71.43 81.25 71.18 81.25
65
17. SROIF http://ontology.neuinfo.org/NIF/BiomaterialEntities/NIF-GrossAnatomy.owl 19849 2930 99.75 39.62 18.18 100.00 39.62 100.00
18. SROIN(D) http://purl.obolibrary.org/obo/flu/dev/flu.owl 874 204 100.00 100.00 100.00 100.00 100.00 100.00
19. ALCOIF http://www.owl-ontologies.com/generations.owl 60 38 94.44 77.14 75.00 100.00 100.00 100.00
20. AL(D) http://protege.stanford.edu/plugins/owl/owl-library/ka.owl 404 216 100.00 57.03 0.00 N/A 57.18 N/A
21. SROIF http://ontology.neuinfo.org/NIF/BiomaterialEntities/NIF-Cell.owl 3508 398 100.00 46.73 0.00 N/A 46.73 N/A
22. SOIN(D) http://www.owl-ontologies.com/travel.owl 145 93 100.00 49.61 33.33 100.00 50.00 100.00
23. ALUHN http://www.hozo.jp/owl/YAMATO20120714.owl 4428 2444 100.00 51.69 95.63 11.67 51.69 11.67
24. ALHIF(D) http://purl.org/net/ontology/beer.owl 165 81 84.48 42.86 22.22 100.00 42.86 100.00
25. SH(D) http://msi-ontology.sourceforge.net/ontology/NMR.owl 1096 290 100.00 50.00 N/A N/A 50.00 N/A
26. SHIF(D) http://www.nada.kth.se/∼mehrana/Delegation.owl 103 63 63.16 40.91 80.00 81.25 40.91 81.25
27. ALCRIQ(D) http://www.biomodels.net/kisao/KISAO 2044 647 100.00 42.70 100.00 92.23 42.82 92.47
28. ALCO http://purl.obolibrary.org/obo/omrse.owl 99 25 100.00 50.00 0.00 N/A 50.00 N/A
Table 3. Dataset and coverage results presented in Section 4. Ontologies 14 and 15 are part of the dataset used by Ontology Alignment
Evaluation Initiative, and are available at http://oaei.ontologymatching.org/. Coverage results are unaggregated and based on the data
of Table 4. N/A means the ontology contains no roles/adaptable roles.
each ontology in our dataset, the following scenario: we simulate the deletion
of each single entity, in isolation, and we take into account the percentage of
adaptable ones (i.e., such that another entity suitable for reformulation exists).
For each of these adaptable entities, we also inspect how many axioms involving
them would be adapted instead of simply deleted. For this reference scenario we
defined Coverage measure as: (C.1) the percentage of adaptable concepts (resp.
roles (C.3)) out of the total number of concepts (resp. roles), and (C.2) the
percentage of adaptable axioms w.r.t. the deleted concept (resp. role, (C.4))
out of the number of axioms to be deleted (that is, presenting the deleted entity
in their signature). The (C. )* variants count the fully adaptable axioms, and
evaluate the completeness of our adaptation rules (the complement of the fully
adaptable axioms is not supported by our rules).
In Table 3 the coverage for each ontology in isolation is reported (computed
from the raw data of Table 4), while the result considering the dataset as a
whole ontology is the following: (C.1) 93.247%, (C.2) 41.757%, (C.2*) 44.185%,
(C.3) 73.647%, (C.4) 79.63%, (C.4*) 80.847%. Table 3 shows that 10 out of 12
of the worst performing ontologies w.r.t. role coverage ((C.3), (C.4) and (C.4)*)
are expressed in a DL missing role hierarchy constructs (identified by letter
H in the DL name). Without role hierarchy constructs only role equality can
be used for adaptation, thus reducing the number of adaptable roles. Concept
coverage (C.1) presents, instead, high values (above 60%) for all the considered
ontologies, independently from the DL they are expressed with. This is not
surprising because concept hierarchy constructs are available for DLs at least as
expressive as AL. On the contrary, coverage results for concept rules w.r.t. OWL2
axioms and constructors seem to be unrelated to either the underpinning DL or
the ontology size (in terms of number of axioms and/or entities). For instance,
the ontologies with worst values for (C.2)* are 2. (SHIN (D)), 8. (SHOIN (D))
11. (SROIF) 3. (ALEHI + (D)) and 15. (ALE), with very different number of
concepts and axioms (Table 4). Similarly, among the best results for (C.2)* the
expressivity ranges from AL(D) to SROIN (D), again with varying number of
axioms and concepts. Ideally the proposal should adapt all the axioms: (C.2)*,
in particular, is far from this result, but it is well known that OWL2, despite
being based on SROIQ, adds new constructors and axioms, that are derivable
from SROIQ ones (they do not add expressive power). For example, Concept
Disjointness axiom (i.e., Disjoint(C, D), with C, D ∈ NC ) is only a shortcut for
C u D v ⊥5 . Our prototype strictly applies the rules of Table 1 and Table 2, so
it cannot directly process the axioms and constructors not available in SROIQ
DL, thus diminishing the number of adaptable axioms.
5 Future Work
The paper represents, to the best of our knowledge, the first proposal for ontology
adaptation upon updates. In addition, the algorithm is totally automatic and
supports ontology expressivity up to SROIQ, on top of which OWL2 is defined.
5
Refer to [9], Chapter 9, for further examples and details.
66
The present paper could be extended in several directions. The set of adap-
tation rules is a preliminary proposal, we plan to further enrich it in order to
increase the coverage rate reported in Section 4 and to consider reasonable al-
ternatives for each single rule (e.g., sound alternatives for a.8 could Fbe C v
n
D, E ≡ ∀R.C → ∀R.D v E or B0 . . . Bn v C, E ≡ ∀R.C → E v ∀R. i=0 B).
We also plan to consider the integration of anonymous entities (e.g., using > as
superclass). Another possible extension is the integration of a complex update
(e.g., concept merge and split) proposals, such as [2]. The relationship between
DL updates and Belief Revision has been investigated [8], we plan to further
investigate it w.r.t. our proposal. We also intend to improve our prototype up to
a full support of OWL2. Our final goal will be a Protégé plugin, from which we
hope to receive feedbacks from the community of ontology engineers and practi-
tioners. The experimental evaluation will also be strengthened with an extended
ontology dataset and temporal profiling of the prototype.
References
1. Flouris, G., Manakanatas, D., Kondylakis, H., Plexousakis, D., Antoniou, G.: On-
tology change: Classification and survey. Knowl. Eng. Rev. 23(2), 117–152 (2008)
2. Hartung, M., Groß, A., Rahm, E.: COnto–Diff: Generation of Complex Evolution
Mappings for Life Science Ontologies. Journal of Biomedical Informatics (2012)
3. Hartung, M., Groß, A., Rahm, E.: Rule-based Generation of Diff Evolution Map-
pings between Ontology Versions. CoRR abs/1010.0122 (2010)
4. Horrocks, I., Kutz, O., Sattler, U.: The Even More Irresistible SROIQ. In: Princi-
ples of Knowledge Representation and Reasoning – KR 2006. pp. 57–67 (2006)
5. Katsuno, H., Mendelzon, A.O.: Propositional Knowledge Base Revision and Min-
imal Change. Artificial Intelligence 52(3), 263–294 (1991)
6. Kondylakis, H., Plexousakis, D.: Ontology Evolution: Assisting Query Migration.
Conceptual Modeling – ER 2012 pp. 331–344 (2012)
7. Noy, N., Klein, M.: Ontology Evolution: Not the same as Schema Evolution. Knowl-
edge and Information Systems 6(4), 428–440 (2004)
8. Ribeiro, M.M., Wassermann, R., Antoniou, G., Flouris, G., Pan, J.: Belief Con-
traction in Web-Ontology Languages. In: Workshop on Ontology Dynamics, IWOD
(2009)
9. Rudolph, S.: Foundations of Description Logics. Reasoning Web. Semantic Tech-
nologies for the Web of Data pp. 76–136 (2011)
10. Stojanovic, L.: Methods and Tools for Ontology Evolution. Ph.D. thesis, University
of Karlsruhe (2004)
11. W3C as Hitzler, P. and Krötzsch, M. and Parsia, B. Patel-Schneider, P.F. and
Rudolph, S.: OWL 2 Web Ontology Language Primer. http://www.w3.org/TR/
owl2-primer/ (2009)
67
ID Concepts Adaptable Concept Adaptable Roles Adaptable Role Adaptable Unsatisfiable Unsatisfiable
Concepts Axioms Concept Roles Axioms Role Concept Role
Axioms Axioms Axioms Axioms
1. 100 100 198 98 2 0 0 0 0 0
2. 736 736 5129 919 36 35 256 195 8 0
3. 43 42 131 46 25 9 31 14 7 0
4. 77 73 411 279 13 11 345 231 95 0
5. 92 92 168 84 0 0 0 0 0 0
6. 87 79 367 167 44 0 0 0 11 0
7. 1021 1021 2823 1357 184 184 946 885 21 0
8. 100 100 1477 327 8 6 180 180 1 0
9. 12 12 183 15 6 2 137 0 148 136
10. 1930 1857 9809 3779 4 0 0 0 2321 0
11. 509 509 2189 759 30 26 285 191 133 3
12. 352 352 700 350 0 0 0 0 0 0
13. 12 12 460 460 6 6 4888 4888 0 0
14. 3304 3298 10880 5423 2 0 0 0 0 0
15. 2744 1839 6256 2314 3 0 0 0 312 0
68
16. 60 60 173 121 14 10 48 39 3 0
17. 1628 1624 6116 2423 11 2 86 86 0 0
18. 213 213 447 447 19 19 83 83 0 0
19. 18 17 35 27 4 3 20 20 8 0
20. 96 96 377 215 60 0 0 0 1 0
21. 373 373 794 371 2 0 0 0 0 0
22. 35 35 129 64 6 2 11 11 1 0
23. 925 925 4589 2372 183 175 1542 180 0 0
24. 58 49 105 45 9 2 6 6 0 0
25. 301 301 580 290 0 0 0 0 0 0
26. 19 12 22 9 20 16 48 39 0 0
27. 202 202 1335 570 9 9 386 356 4 1
28. 27 27 50 25 2 0 0 0 0 0
Table 4. Raw data used for coverage analysis of Section 4. Unsatisfied axioms stands for axioms matching the LHS of a rule having a
precondition not satisfied by the entity under deletion.