Ontologies, like any other model, change over time due to modi cations in the modeled domain, deeper understanding of the domain 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 de ned 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 ontological axioms triggered by the presence of certain preconditions. The rule-based adaptation algorithm covers up to SROIQ DL.
Ontologies, like any other model, change over time and a revalidation of all data
and metadata de ned on top of the modi ed 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 [
While a set of basic ontology changes can be easily de ned, it is impossible
to identify a set of complex changes without xing the granularity level, i.e.,
updates expressed as arbitrarily complex graph patterns (see [
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 rulebased 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- niteness 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 e ects. On this basis, the modeler 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 di erent alternatives are available.
The contribution of the present paper can be summarized as follows: an automatic adaptation algorithm supporting up to SROIQ expressivity, its correctness 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
Our proposal covers up to SROIQ Description Logic (DL), on top of which the
Ontology Web Language (OWL2) [
This section introduces the adaptation rules (Section 3.1), the rule-based adaptation algorithm (Section 3.2), the correctness proof for the given rules (Section 3.3), and the temporal complexity of the algorithm (Section 3.4). 3.1
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 de ned applicable i prec(r) is satis ed 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 i an axiom in o exists that is equal to LHS(r) modulo alpha renaming of C (resp. R)
Precondition
R R0, R 2 signature(axiom)
Q v R
Rule axiom ! axiom[R=R0] 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. 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 classi cation phase is not required, it may increase the algorithm e ectiveness. 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 obvious associated signature: Human 9eats:F ood, F ood(cheese), Eater 8eats: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 9eats:Eatable, Eatable(cheese), Eater v 8eats:Eatable, P lastic u Algorithm 1 Ontology Update Adaptation 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
Before stating the proposition about the correctness of the adaptation rules we
introduce some de nitions and lemmata. For sake of brevity we will
interchangeably refer to the axioms and their semantics, according to [
I j= A2 =) I j= A1, that is A2I
A1I .
De nition 1. An axiom A1 entails an axiom A2 i , for any interpretation I, De nition 2. An adaptation rule r is sound i RHS(r). fLHS(r); prec(r)g entails Lemma 1. 8C; D; F 2 NC . C v D =) C t F v D t F .
Proof. By considering the associated semantics the Lemma can be restated as CI
DI =)
CI [ F I | {z }
DI [ F I . Assume that the preceding formula does | {z } not hold, that is
6 one of the following conditions holds: . This means 9x 2
, and requires that at least { x 2 F I , but this implies x 2 , resulting in a contradiction, { x 2 CI , and thus this implies CI DI =) x 2 , contradicting the hypothesis.
Lemma 2. 8C; D; F 2 NC . C v D =) C u F v D u F .
Proof. By considering the associated semantics the Lemma can be restated as CI DI =) CI \ F I DI \ F I . Assume that the preceding formula does not | {z } | {z } hold, that is 6 . This means 9x 2 . x 62 . Note that x 2 is equivalent to requiring that x 2 F I ^ x 2 DI holds. However, x 2 F I ^ x 62 =) x 62 CI . Given that x 2 DI holds, this contradicts the premise C v D.
Lemma 3. 8C; D 2 NC . C v D =) 9R:C v 9R:D.
Proof. Assume that fx j 9y 2 CI . hx; yi 2 RI g 6 fx j 9y 2 DI . hx; yi 2 RI g holds, that is, 9R:C 6v 9R:D. This requires that the following condition holds: 9hx; yi 2 RI . y 2 CI ^ y 62 DI . But, if such condition holds, then C 6v D, contradicting the premise.
Lemma 4. 8C; D 2 NC . C v D =) 8R:C v 8R:D.
Proof. Assume that fx j 8hx; yi . hx; yi 2 RI =) y 2 CI g 6 fx j 8hx; yi . hx; yi 2 RI =) y 2 DI g holds, that is, 8R:C 6v 8R:D. This requires that the following condition holds: (9x . 8hx; yi . hx; yi 2 RI =) y 2 CI ) ^ (9y . hx; yi 2 RI ^ y 62 DI ). But, if this condition holds, then an y exists and RI is not empty. Therefore, since the left operand of the implication holds, then right operand also does. From this, we obtain CI 6 DI , contradicting the premise. Proposition 1. Adaptation rules application preserves ontology satis ability. Proof. Ontology satis ability 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 de nition. a.2 E 9R:C ! E v 9R:D. 9R:C v 9R: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 su cient that fx j 9y 2 CI . hx; yi 2 RI g fx j 9y 2 DI . hx; yi 2 RI g 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 n DI
I n CI , 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 8R:C ! E v 8R:D. E 8R:C =) E v 8R:D holds for Lemma 4 because C v D holds. a.9 E n R:C ! E v n R:B. n R:B v n R:C, but it is su cient that fx j 9y 2 BI . hx; yi 2 RI g fx j 9y 2 CI . hx; yi 2 RI g. 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.
6 hx0; x1i 2 T0I ^ : : : ^ hxm+1; xm+2i 2 QI ^ hxm+p+2; xm+p+3i 2 Tp0 I ^ hxm+1; xm+2i 62 RI . This contradicts Q v R. b.3 E 8|R{z:C} ! E v 8|Q{z:C}. Assume that I 6 I holds. This requires that
I holds. This requires that 9x0, : : :, xm+p+3 . 9x . x 2 I ^ x 62 I , that is, 9x:((8y . hx; yi 2 RI =) y 2 CI ) ^ (9y0 . hx; y0i 2 QI ^ y0 62 CI )). Given that Q v R, if such y0 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 } 9x . jfy j y 2 CI ^ hx; yi 2 RI gj n ^ jfy j y 2 CI ^ hx; yi 2 QI gj > n.
This implies jQI j > jRI j, contradicting Q v R. b.5 T R ! Q v T . Assume that Q I 6 R I . This requires that 9hx; yi . hy; xi 2 QI ^ hy; xi 62 RI . This contradicts QI RI . b.6 Disjoint(R; T ) ! Disjoint(Q; T ). Assume that RI \ T I = ; =) QI \ T I = ; does not hold. This requires that 9hx; yi 2 QI ^ hx; yi 2 T I ^ hx; yi 62 RI holds, but hx; yi 2 QI ^ hx; yi 62 RI contradicts Q v R. b.7 R(a; b) ! S(a; b). From R v S we have that 8hx; yi . hx; yi 2 R =) hx; yi 2 S. b.8 E 9|R{z:C} ! E v 9|S{z:C}. Assume that I 6 I . This requires that 9x .
9y 2 CI . hx; yi 2 SI ^ hx; yi 62 RI holds. This contradicts R v S. b.9 E 9R:Self ! E v 9S:Self . Assume that I 6 I . This requires that | {z } | {z } 9x . hx; xi 2 SI ^ hx; xi 62 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 } 9x . jfy j y 2 CI ^ hx; yi 2 RI gj n ^ jfy j y 2 CI ^ hx; yi 2 SI gj < n. This implies jRI j > jSI j, contradicting R v S. b.11 T R ! T v S . Assume that R I 6 S I . This requires that 9hx; yi . hy; xi 2 RI ^ hy; xi 62 SI , 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
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 = jRulesj 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
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 Re ection 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 satis 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 i it satis es at least one rule precondition, while an axiom a is adaptable i 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 e ectiveness 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/ e n in l io ow le l IRU ..:tttrrseeog/20a09/ooo//90ag/vhnphnLwCOmW..:.ttsccce////12ubddduphSAO i.l..:i.l-ttttsscceeeeg/oa///oovhduhnpnubnhhww ..il:---re2003//o/go3g20030881///udwwwCwTwwRR li..l:.lttrrrrsaoog/o///ogoooybbupphbwm .l:.tttrreoooao///go2ndhpLwwOmW.ii:li.l-ttttrrssscccceeeeog/ooa//g/ooooynnnphwm .li.:ii.l-tttrsczzzzeeg/oooogoo///a/aondppphwwww ...l.:ii.ljttttrrsssceeeago/2a1//o/vnppSpnhwwU .ill..:--trrrrg/ooo/aooao0112//1103/aoo/ybhbbuphpw li..l:i.lttrrrroaoog///o/oooybbupphbdw .iil.fff-IItttrsscce//googoo/oyyyunnunnnunFFNNDD ..i:liil.lftttrssceog/aooa/go/a/oaophpwm :.ltt//aohupnhwm :.lttse//oouphwm .l..:l.lttssscee/2005a/07ao///oo/kunppphwwwm iil.iii.f-IItttrrrssseeeoa/a/goo/oynunnFFEBNNAGm .li.l:.lttrrrreaog/oooo////o/yvbbbuppuduhw li..l:i.l-ttttrssceeeoogooo/g/aoo/npnnhwwwwwm li..llli.:f-ttrrrrsseee/goago/oo/a/a//ykudpundnbpww i.i.liliif-IIttttrrseee/o/gaoogoa/oynunnnFFEBCNNm lil..:l.l-ttttrsceeooogo///oaovnphwwwwwm l..:.ljttzo//oo/20120714o/phphwwwwTwYAAOM l.l:.lttttrrreee/g/oooo///goynnupphbw ..lil.:f-ttttrrssceeeogogooo/o/oog/o/yyunnnpwRNmM ...:li.lttttrseeee/aaa///agaookhhdnnnphwwwwDm l.i.:iItttsseeoo///ao/kdnbphSwwwAKOm li.l.:.lttrrrrrseaoog/oo///oooybbupphbwm ili.ttttrrrsssceeeeeeeo4ogandnpuSnnO :lil.iltttttrceee//oaaaaooogaaavyhpbnm illltttrrssceeeoaoogoo/aaaooynnnndpb p t o p /o t ov d h t h / t h t th :/ th :/p c an s w o l .l t t h l w o . p t t h d , n n e a a v e
i t t m e a s i
t A a i / t
n a I N
.
D n 4 . o 3 it e
l e a b l lu a L ()DQ ()ND I()D+ I()ND LCO ()DQ I()DQ INO I()ND R IFO IFO ()ND S LE IHNO IFO I()ND IFO ()D IFO ()ND UHN I()FD ()D ()FD I()DQ CO D U I H S 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 de ned 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 (identi ed 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. (ALE HI + (D)) and 15. (ALE ), with very di erent 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 2 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
The paper represents, to the best of our knowledge, the rst 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 de ned.
5 Refer to [
The present paper could be extended in several directions. The set of
adaptation 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
alternatives for each single rule (e.g., sound alternatives for a.8 could be C v
D; E 8R:C ! 8R:D v E or B0 : : : Bn v C; E 8R:C ! E v 8R: Fin=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 [
9 8 ep ta e v u n d l 50 33 22 850 105 5489 129 794 377 35 447 1616 173 2656 10808 460 700 1289 9809 183 4177 2823 367 168 411 131 1529 198 n a 1 y
5 re is
s n tc 2 x o a . i 25 750 9 920 54 37 64 371 215 27 447 4223 121 3214 5423 460 350 759 7379 15 237 3157 167 84 729 46 199 98 io c t n p o n 2 me a
a sa ta
1 1 0 9 61 0 2 7 2 0 0 3 19 2 10 0 0 6 0 62 0 2 6 8 0 0 11 9 35 0 o p
5 4 p b s t l e