The detection of changes between OWL ontologies is an important service for ontology engineering. There are several approaches to this problem, both syntactic and semantic. A purely syntactic analysis of changes is insufficient to detect changes with logical effect, while the current state of the art in semantic diffing ignores logically ineffectual changes, which might be of great interest to the user. We develop an exhaustive categorisation of ineffectual changes, based on their justifications. In order to verify the applicability of our approach, we collected 88 OWL versions of the National Cancer Institute (NCI) Thesaurus (NCIt), and extracted all pairwise, consecutive diffs. We discovered a substantial number of ineffectual changes and, as a result, argue that the devised categorisation of changes is beneficial for ontology engineers. We devised and applied a method for performance impact analysis (culprit finding) based on the diff between ontologies, and identified a number of culprits between two NCIt versions.
The comparison of ontologies is a valuable service whether for purely analytic
purposes, versioning systems [
In this paper we propose a diff notion that builds on structural diff with a logical impact analysis, which we refer to as intentional difference, incorporating a categorisation of ineffectual axioms based on their justifications. The goal of this categorisation is to suggest on the intent behind such changes. For the purpose of verifying the suitability of our approach, we collected all 88 versions of the National Cancer Institute (NCI) Thesaurus (NCIt) available in OWL format, freely downloadable1 from the web, and conducted a diachronic study of the corpus. This study consisted of the extraction of all pairwise, consecutive diffs between NCIt versions. Our diff revealed a fairly high number of ineffectual changes across the corpus, averaging at 13% and even reaching values above 90%. In addition to this we carried out a reasoner performance test to inspect the performance impact of both effectual and ineffectual changes throughout the NCIt. While ineffectual changes carry no logical impact, it is still the case that they have a performance impact.2 The test revealed an unusual performance increase between 2 versions, the latter of which was 89% faster and also slightly bigger in number of axioms. This motivated a more in-depth performance impact analysis, wherein we attempt to find subsets of the slow ontology without which the ontology performs considerably faster (referred to as culprits). We devise a culprit finding method based on the diff between ontologies, and demonstrate its applicability with a number of culprits for the NCIt case. 2
We assume the reader to be reasonably familiar with OWL [
The problem of computing the difference between pairs of ontologies has been approached both syntactically and semantically. We distinguish two major aspects of ontology diffing: (i) the detection of changes, and (ii) the presentation of changes to the end-user. As we analyse existing diff approaches, we point out that most effort has been largely dedicated to (i). It is often the case that the output of diff operations is the set of axioms or terms in the diff. While this may reflect the desired identification of change, it does not convey sufficient information to the user w.r.t. the intent of changes, or whether these are effectual or not. 3.1
2 A trivial example is adding all inferred subsumptions, therefore speeding up reasoning tasks.
Among the stated properties, an ideal logical diff should combine effective computability for OWL 2 ontologies while providing some analysis of the impact of changes, whether these be effectual or ineffectual. Although this is a complex task in itself, from Table 1 we see that some diffs analyse effectual changes, but none of them inspects ineffectual changes. This desideratum leads to the categorisation method proposed in this paper for the latter type of changes.
Given the limitations of diff approaches described in Table 1 w.r.t. (ii) (as described at the beginning of Section 3), we build on the notion of structural difference with a categorisation mechanism for ineffectual axioms. This requires checking if axioms in the first ontology are entailed by the second (and vice-versa), if that is not the case then those axioms are regarded as effectual changes.
Consider the following ontologies O1 and O2, which are referred to in examples throughout this section:
O1 = f 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 :
A v C; B v C; E D; D v F; F v G; G v H u 9s:H; F v I; F v G u I u J g
O2 = f 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 :
A v B t C; A v B; B v C; E v D; D v E; E v B t 9r:C; D v E t G; G v 9s:H u H; F v G u Ig
The notion of structural difference is based on OWL’s notion of structural
equivalence (denoted s) [
Additions(O1; O2) = f 2 O2 j there is no Removals(O1; O2) = f 2 O1 j there is no 2 O1 s.t. 2 O2 s.t.
s g s g
So if there is an axiom s.t. 2 Additions, this implies that similarly for Removals. Examine the following example: 2 O2 n O1, and Example 1 From the defined ontologies O1 and O2 we have that:
Additions(O1; O2) = f 1; 2; 4; 5; 6; 7; 9g
Removals(O1; O2) = f 1; 3; 4; 5; 7; 8g Note that the axiom 2 is syntactically equal to 3; 2 = 6 s 8. Therefore these axioms are not reported as changes. 3. We also have that
Based on these two sets, the logical difference pinpoints which axioms in Additions (or Removals) affect the set of entailments of O1 (or O2). In other words, it distinguishes between those axioms in the structural difference which are entailed by O1 (or O2), as follows: Definition 2 (Logical Difference) The logical difference between O1 and O2 are the following sets:
E ectualAdditions(O1; O2) = f 2 Additions(O1; O2) j O1 2 E ectualRemovals(O1; O2) = f 2 Removals(O1; O2) j O2 2 Ine ectualAdditions(O1; O2) = Additions n E ectualAdditions Ine ectualRemovals(O1; O2) = Removals n E ectualRemovals g g
The resulting sets Ine ectualAdditions and Ine ectualRemovals are composed of those axioms which do not change the set of entailments of O1 and O2, respectively. An axiom is in Ine ectualAdditions iff O1 j= , and similarly for Ine ectualRemovals (Example 2).
Example 2 Given the sets Additions and Removals (from Example 1) we have that: E ectualAdditions(O1; O2) = f 2; 6g E ectualRemovals(O1; O2) = f 4; 8g Ine ectualAdditions(O1; O2) = f 1; 4; 5; 7; 9g Ine ectualRemovals(O1; O2) = f 1; 3; 5; 7g
In order to characterise ineffectual changes, we devise a categorisation of axioms based on their justifications as follows:
2 Ine ectualRemovals is: Strengthened, if there is a J for with J \ E ectualAdditions 6= ;. Rewritten, if there is a justification J for with J \ Additions 6= ;, and If J Additions then is a complete rewrite, otherwise a partial rewrite. Redundant, if there is a J for with J (O1 \ O2). If J Ine ectualAdditions then is an avoided redundancy. (O1 \ O2) [ To obtain the corresponding categories for added axioms 2 Ine ectualAdditions, replace , Additions, E ectualAdditions and Ine ectualAdditions with , Removals, E ectualRemovals and Ine ectualRemovals respectively. In Ine ectualAdditions the label for the criteria of Strengthened axioms changes to Weakened axioms.
The intentional difference gives possibly overlapping sets of axioms, as demonstrated in Example 3. Also we note that these categories are exhaustive, in the sense that there is no axiom such that the justifications of which do not imply one of the defined categories. Consider an axiom and ontologies O1 and O2, with 2 O1 but 2= O2, and O2 j= . Then there must be a justification J O2 for . If J (O1 \ O2) [ Ine ectualAdditions then is redundant, otherwise if J \ E ectualAdditions 6= ;, then is strengthened.
Example 3 Given the sets Ine ectualAdditions and Ine ectualRemovals (from Example 2) we have that:
O1 ! O2 Rewritten = f 3g Strengthened = f 1g Redundant = f 1; 3; 5; 7g
O2 ! O1 Rewritten = f 9g Weakened = f 7; 9g
Redundant = f 1; 4; 5; 7; 9g
Note that the existence of a rewritten axiom from O1 to O2 does not imply that the same holds in the opposite direction. This is applicable to all categories. Also we can have that an axiom is in more than one categorical set, exemplified as follows: Rewritten and redundant The axiom 3 has been rewritten from O1 to O2. The justification for 3 is J1 = f 4; 5g, which is categorised as a rewrite since 3 j= J1. However, since f 4; 5g 2 Ine ectualAdditions, J1 also indicates a redundancy.
So the axiom 3 is part rewritten part redundant.
Strengthened and redundant Consider axiom 1; we can see that O2 j= 1. A justification J1 for 1 is J1 = f 2; 3g, which indicates a strengthening (since 2 2 E ectualAdditions), as well as a redundancy ( 3 2 O1 \O2). Another justification J2 = f 1; 3g indicates a strict redundancy; 1 2 Ine ectualAdditions. Rewritten, weakened and redundant Axiom 9 is categorised as rewritten, weakened and redundant. A justification for 9 is J1 = f 5; 7g, where 9 j= J1, pointing to a rewrite. We also have that f 5; 7g 2 Ine ectualRemovals, therefore being categorised as redundant as well. A second justification is J2 = f 8g, and since 8 2 E ectualRemovals, 9 is categorised as weakened.
While the logical diff identifies those logically ineffectual axioms in the difference, it does not suggest on the intent of change or present appropriate reasons for it, i.e. justifications. With the categorisation method described, users have, at the very least, an indicator as to why such axioms have no impact. Note that these categories are merely suggestive of the developers’ intent. In order to ensure the real intent one would require either a detailed edit-based diff or contact with the ontology developers. 4
In order to substantiate our approach to ontology diffing, we carried out a diachronic study of the NCIt using the methods described. The NCIt archive3 contains 88 versions of the ontology in OWL format, two of which were unparsable (releases 05.03F and 05.04d) with the OWL API,4 and consequently Prote´ge´.5 The experiment machine is an Intel Xeon Quad-Core 3.20GHz, with 12Gb DDR3 RAM dedicated to the Java Virtual Machine (JVM v1.5). The system runs Mac OS X 10.6.7, and all tests were run using the OWL API (v3.1). All gathered test data is available from http://owl.cs.manchester.ac.uk/ncit, a part of it is published on Google Public Data Explorer,6 and can be visualised at http://bit.ly/jFKU3R. 4.1
The logical difference throughout the NCIt time-line consists mostly of subclass axioms (see Figure 1, and for complete results the mentioned website), with an average of 75% (excluding O14 and O16). The average proportion of logical changes is 15%, and the remaining are annotation changes. It should be noted that, despite the large number of annotations, NCIt developers devoted considerable effort towards the logical part of the ontology. Version O6 is a curious case, where a large number of classes (5170) were renamed,7 and around 220,000 annotations and 14,418 subclass axioms were deleted. This indicates a possible re-modelling, or mass-renaming of classes in the NCIt at this point. More evidence to support this includes the addition of 30,859 subclass axioms, 9,070 classes and 23 object properties (and roughly 240,000 entity annotations). Similarly in O25 a series of changes were carried out to the subsumption hierarchy, with the removal of 8,231 subclass axioms and 2,899 equivalent class axioms compared to the previous version, and also the addition of 10,591 subclass axioms and 3,011 equivalent class axioms.
There is a fair amount of ineffectual removals in the corpus, reaching values of 93% in O29 or 97% in O16, and with an average of 35% of all logical removals (see Figure 1). Out of these ineffectual removals 92% turned out to be strengthened axioms (e.g. O27 has 3,104 strengthened axioms out of 3,843 removals), while 42% were removed redundancies. On average 5% of logical additions are ineffectual, yet there are some high values such as 61% in O24. Among these 73% are added redundancies, and 82% are weakened axioms. We also identified a number of rewrites in the corpus. Particularly
4 http://owlapi.sourceforge.net/ 5 http://protege.stanford.edu/ 6 http://www.google.com/publicdata/home 7 Since throughout the NCIt evolution no classes are removed. from O32 to O33 there are 227 rewritten axioms, typically taking a form as shown in Example 4.
Example 4 A B u (9r:D) u (9s:F ) u (8t:G) rewritten into: A B u ((9r:D) u (9s:F )) u (8t:G)
This kind of change is not only syntactic but also trivial and easily detected. While ideally the underlying structural diff would not include these, at least with our categorisation and alignment with source axioms, it is easy to spot and recognize the triviality. One can also argue that certain ineffectual changes are in fact refactorings of one version into another, albeit in the case of strengthened and weakened axioms one could say that the intention was exactly that but turned out not to have the desired effect. The distinction here should be made that the strengthening of an axiom does not necessarily mean strengthening of the ontology. Consider an ontology O1 = f 1 : A v B; 2 : A v Cg, and a change of 1 into A v B u C. The axiom 1 was strengthened, but the resulting ontology O2 = f 1 : A v B u C; 2 : A v Cg was not. However, if we change 2 2 O2 into A v C u D, then we can say both the axiom 2 and the ontology O2 are strengthened.
We noted a recurring trend throughout the NCIt corpus, which is the addition of redundancies. This trend has more incidence up until O8, but there are high values in the rest of the corpus as well, such as O35 with 174 added redundant axioms (see Figure 1). The highest value found is in O17, where 482 redundant axioms were added. Upon investigating this phenomenon, we found that such added redundancies are, in most or all cases, entailments from previous versions. These entailments are those derived from the transitivity of the subclass relationship, e.g. O1 = f 1 : A v 9r:B; 2 : C v Ag, O2 = f 1; 2; 3 : C v 9r:Bg. From the example we see that 3 is redundant; C v A suffices for C v 9r:B to hold.
Overall the average of ineffectual changes is 13%, while the remaining are effectual. However there are cases where the number of ineffectual changes is quite high, such as O24 where 52% of logical changes are ineffectual, as well as O27, O29 and O30 with 48% each. In retrospect this is a high amount of changes that would go unexplained by existing diffs, and while structural diff captures this it does not analyse the logical impact of such changes. 4.2
It is often the case that, for reasoner testing, only a few or even one ontology version is tested against. There is no reported reasoner benchmark using a corpus of the same kind as the one here described. So, in the process of analysing the NCIt, we evaluated how modern reasoners handle all published OWL versions of the NCIt. Three major DL reasoners were put to the test; FaCT++ (v1.5.1), Pellet (v2.2.2) and HermiT (v1.3.3). Since we also possess the axioms in the difference between NCIt versions, this allows us to test incremental reasoning as well.8 In Figure 2 we plot the reasoning times in a 8 As implemented within Pellet. logarithmic scale of each reasoner, comprising consistency checking, classification and concept satisfiability (denoted RT(O)). Out of the three reasoners put to test, FaCT++ behaves consistently faster than Pellet and HermiT (O14 and O16 aside).
This performance test also shows that, to some degree, incremental reasoning
provides a big advantage when handling the NCIt (or other large ontologies) in terms of
reasoning time. However it did not terminate upon classifying O14 and, like HermiT,9
O16. This is due to the abundance of individuals: incremental reasoning is based on
locality-based modules [
Upon completing the reasoner performance test we noted that, from O79 to O80 (in Figure 2), there is a significant performance improvement in HermiT. While our initial premise was to categorise logical diff-based impact between ontologies, now we encounter another problem: identifying and dissecting performance impact. We ascertained that the source of the bad performance is in the diff removals between those versions (R = Removals(O79; O80)), as with the additions of O80 the reasoning time was substantially lower. In order to investigate this phenomenon, we started with a brute-force culprit finding approach: for each axiom 2 R check if RT(O80 [ f g) RT(O80). The size of R is 4,583 axioms, making this an expensive approach. It is also naive in the sense that culprits are not necessarily singleton sets. Nevertheless we examined RT(O80 [ f 2 Rg) and found 13 (effectual) axioms which yield reasoning times ranging from 76 to 8,490 seconds. Surprisingly adding all 9 HermiT returns a “StackOverflowError” when classifying O16, both in Prote´ge´ and OWL API. 13 axioms to O80 results in a reasoning time of little over 9 hours. Thus some of the non-culprit additions exhibit a protective effect.
However, this approach is not only computationally expensive, but also relies on
the existence of a diff which is not always available. We might want, given an
“unmanageable” ontology, to find a subset thereof with which one can work with. As such
we carried out a test partly based on the method described in [
We have demonstrated with the diachronic study of the NCIt that merely syntactic diffs do not provide nearly enough insight into the impact of changes carried out, since logical differences are not identified. We found that ineffectual changes exist and account for a significant amount of logical changes throughout the NCIt. Such changes are discarded by semantic diffs, yet we show that they may provide helpful modelling insights. The axiom categorisation we devised allows ontology engineers to understand the lack Algorithm 1 Identify subsets of an ontology O for which reasoning times are considerably better than the original ontology.
Input: Ontology O Output: Set of modules S, wherein for each Mi 2 S: RT(O n Mi) RT(O) average(SAT times 2 T imes)
BadConcepts [ C 50 then S ;; BadConcepts ; for all concepts C 2 Oe do
T imes T imes [ hC; SAT time(C)i end for for all C 2 Oe do if SAT time(C)
BadConcepts end if end for for all C 2 BadConcepts do
= fterms t 2 Usage(C)g M = >?*-mod( ) if RT(O n M) RT(O) then
S S [ M end if end for return S Concept Cerebral Glioblastoma TP53 Gene TP53 wt Allele Erlotinib Paclitaxel Trastuzumab Tumor Protein-p53 Platelet-Derived Growth Factor Receptor-Like Protein HRAS wt Allele p21 H-Ras Protein AC-T-T Regimen of impact of their changes, and possibly refine these before publishing newer versions, particularly if redundancies are present.
From our structural analysis, we were able to gain considerable insight into the NCIt
and its evolution. By looking at the entire history, it became relatively straightforward
to identify tool artefacts and significant events and thus to disentangle accidental and
essential features of the ontology. We are currently confirming our interpretation of
various events with the EVS and thus far it conforms to their understanding of the history.
Such an analysis is proving useful to the EVS as they find instances of the OWL version
that do not correspond with their intent, and thus allowing them to publish corrections.
In the future we plan to apply a similar categorization to logically effectual changes. We
also intend to examine the stability of entailments, i.e., whether an entailment persists
throughout some or all NCIt versions. Finally, more elaborate forms of structural
analysis, such as examining the justificatory structure [
The reasoner performance results identify areas of performance weakness that would not have been evident using standard “grab a version” methods. Furthermore, we demonstrate the advantage (in terms of time) of using incremental reasoning for ontology engineering tasks, especially when large and complex ontologies are involved. We found in the NCIt corpus a realistic case for performance impact analysis, based on which we identified a number of meaningful culprits. The preliminary culprit finding methods and results described indicate that this approach works reasonably well. However the question of how to present these culprits to, and validate our approach with users still remains.