The analysis of changes between OWL ontologies (in the form of a di ) is an important service for ontology engineering. A purely syntactic analysis of changes is insu cient to distinguish between changes that have logical impact and those that do not. The current state of the art in semantic di ng ignores logically ine ectual changes and lacks any further characterisation of even signi cant changes. We present and demonstrate a di method based on an exhaustive categorisation of e ectual and ine ectual changes between ontologies. In order to verify the applicability of our approach we apply it to 88 versions of the National Cancer Institute (NCI) Thesaurus (NCIt), and 5 versions of SNOMED CT, demonstrating that all categories are realized throughout the corpus. Based on the outcome of these studies we argue that the devised categorisation of changes is helpful for ontology engineers and their understanding of changes carried out between ontologies.
The comparison of ontologies is a valuable service whether used as a subroutine in a version control system or to support users in understanding changes. Di erent di methods vary in their sensitivity to changes: e.g., a di method based on character di erences will nd that two notationally distinct serializations of the same ontology are radically di erent. If a di method is too sensitive to irrelevant changes then the user will be faced with determining which reported changes are actually signi cant. On the other hand, a hard requirement is that the di method does not miss any change of signi cance.
The OWL 2 speci cation1 de nes a high level notion of syntactic equivalence,
so-called \structural equivalence" (and thus the associated notion of structural
di erence), which abstracts from certain neglectable changes such as the
order of axioms or concrete syntax. A di erent syntactic approach is that of an
edit-based di , wherein change records are produced within the ontology editor
being used, thereby capturing the history and intent of change, as implemented
in Swoop [
A major problem with the output of change sets is that the user is given a
(possibly large) set of axioms (or terms) to analyse, with no indication as to what
kind of change each of them represents. A reasonable presentation of changes
will cluster changes according to relevant properties. In this paper we discuss
and elaborate on the di method presented in [
For the purpose of verifying the suitability of the approach, we collected
88 versions of the National Cancer Institute (NCI) Thesaurus (NCIt) available
in OWL, as well as 5 of the latest Systematized Nomenclature of Medicine {
Clinical Terms (SNOMED CT)3 versions, and conducted a diachronic study of
each corpus. These studies aimed at showing the computational feasibility of our
approach and con rming that the devised categories are realized throughout each
corpus. Additionally we investigate whether this di method helps us understand
the evolution of both the NCIt and SNOMED CT. Moreover we demonstrate
via walkthroughs how the categorisation can support change analysis by users:
for the rst walkthrough we use toy ontologies, while for the second we use two
versions of the NCIt.
2 In addition to material in [
We assume the reader to be reasonably familiar with ontologies and OWL, as
well as the underlying description logics (DLs) [
The problem of computing the di erence between pairs of ontologies has been approached both syntactically and semantically. We distinguish two major aspects of ontology di ng: (i) the detection of changes, and (ii) the presentation of changes to the user. We note that most e ort has been largely dedicated to (i). It is often the case that the output (ii) of di operations is the set of axioms or terms in the di . While this may re ect the desired detection of change, it does not necessarily convey su cient information to the user w.r.t. the impact of changes. 3.1
Within the detection of changes (i), one would expect a preliminary distinction of axioms in the di according to their logical e ectuality. As such, a purely syntactic change analysis does not su ce to achieve this. Standard semantic di tools treat all ine ectual changes as neglectable. This goes too far, for example: consider the case where two ontologies di er in a substantial number of axioms, but the axioms in the di are only equivalences rewritten into subsumptions. Semantic di s would point out that there are no di erences, which may seem counter-intuitive to the user since a shallow inspection of the ontologies would reveal a discrepancy in number of axioms. In this case the ine ectual changes point to possibly unnecessary work. Though if these were intentional, then other developers should be aware of it rather than rewriting the axioms once again. So for this kind of change we would expect a more granular analysis to be helpful.
The second fundamental aspect of any di is the presentation of changes to the user (ii). Currently ontology di s return as the output an unstructured, uncharacterised set of changes. As a consequence the task of change analysis is not particularly appealing. Consider the fact that the average di size across the NCIt corpus is over 6,000 changes; relying on current di methods for change analysis would be frightening, to say the least. At this point it would be useful to determine further properties of individual changes which might help the user understand changes. A change could relate to, e.g, a newly introduced term, or an adjustment to the class hierarchy. Whatever it may be, the current state-ofthe-art in ontology di ng does not carry out such a characterisation of changes.
In terms of computability, one would expect an ontology di to be e ciently
computable for OWL 2 ontologies.4 CEX [
Overall there is little tool support available to end-users for analysing and
understanding di erences between ontologies. Particularly when it comes to large
ontologies, such as SNOMED CT, browsing through substantial change sets
while inspecting two of its versions is not only tedious, but also requires
aboveaverage hardware to browse through SNOMED CT seamlessly. Based on the di
method described in [
In order to demonstrate the usefulness of the di categories, let us compare ontologies O1 and O2, de ned in Table 1. From O1 and O2 we have the following structural di erences: Additions(O1; O2) = f 1; 2; 4; 5; 6; 7; 9; 10; 11; 12; 13g Removals(O1; O2) = f 1; 3; 4; 5; 7; 8g
Note that 6 is not syntactically equal to 8 ( 6 6= 8), however they are
structurally equivalent ( 6 s 8). Therefore these axioms are not reported as
changes. Given the sets of structural additions and removals from O1 to O2,
we check which axioms in the Removals(O1; O2) are entailed by O2 (ine ectual
removals), and vice-versa for the Additions(O1; O2). Thus we obtain a distinction
between e ectual and ine ectual changes, as follows:
4 Based on DLs up to SROIQ [
E ectualAdditions(O1; O2) = f 2; 6; 10; 11; 12; 13g E ectualRemovals(O1; O2) = f 8g Ine ectualAdditions(O1; O2) = f 1; 4; 5; 7; 9g Ine ectualRemovals(O1; O2) = f 1; 3; 4; 5; 7g
There are several ine ectual changes in the change set, while e ectual changes are mostly additions (and a single removal). The changes are categorised as shown in Table 2.
Let us consider two ine ectual additions; 9 is a rewrite of f 7; 5g, as well as an avoided redundancy (i.e., had it been added to O1 it would be redundant). The axiom is also weakened, due to 8. This may seem like an unintentional change, since now we face a loss of information regarding J , which is no longer mentioned in O2. Such a change may be worth revising. The axiom 1 is redundant, since we have from O1 that A v C, which is also entailed from O2. Therefore the user can dispose of this axiom.
Bear in mind 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 category. Consider axiom 1; a justi cation J1 for 1 is J1 = f 2; 3g, which indicates a strengthening (since we have that 2 2 E ectualAdditions(O1; O2)), as well as a redundancy ( 3 2 O1 \ O2). Another justi cation J2 = f 1; 3g indicates a redundancy; 1 2 Ine ectualAdditions(O1; O2).
In terms of e ectual changes there is only one removal, and six additions. The e ectual removal ( 8) represents a weakening of 9 with retired terms (J is not mentioned in O2). In the analysis of the ine ectual changes it was already noted that axiom 8 should be revised. The pure additions appear to be adjustments to the class hierarchy, some associated with new terms in O2. Both axioms 11 and 12 are strengthenings of 4, which suggests that they could be merged, especially since there is intra-axiom redundancy. Finally there is a new term K in O2 being described via axiom 10.
Generally speaking, with such a categorisation it becomes conceivably more intuitive to navigate and understand sets of changes. In addition to this, we gathered from the analysis of ine ectual changes useful information about the changes between O1 and O2, e.g., that axiom 4 is strengthened in two distinct, yet partially super uous axioms ( 11 and 12). Similarly we discover that axiom 9 is weakened, from 8, which should be reconsidered as we now have that O2 2 F v J (J becoming a retired term).
The algorithm to compute the di and its categories is straightforwardly
derivable from the de nitions in [
The NCIt archive11 contains 88 versions of the ontology in OWL format, two of which were unparsable (releases 05.03F and 05.04d) with the OWL API,12 11 http://evs.nci.nih.gov/ftp1/NCI_Thesaurus 12 http://owlapi.sourceforge.net/ and consequently Protege.13 The test data is published on Google Public Data Explorer,14 and can be visualised at http://bit.ly/leZ6fM.
SNOMED CT is not readily available in OWL, however IHTSDO15 supplies a Perl16 script to transform the published concept and stated relationships tables into OWL or KRSS formats. We collected all 5 International Releases of SNOMED CT that can be converted into OWL via this script, since January 2009 through to January 2011 (the versions before 2009 are not published with this transformation script into OWL). Upon executing the conversion of SNOMED CT releases into OWL we discovered a discrepancy between the OWL and KRSS transformation outputs. Speci cally in the January and July 2009 releases (bundled with version 1.1 of the Perl script), the OWL and KRSS serializations di er in over 100,000 subclass axioms. The OWL transformation of the January 2009 release contains 115,941 more subclass axioms than the KRSS output, while in the July 2009 release the OWL version has 113,665 more subclass axioms. This situation no longer presents itself with subsequent versions of the transformation script; the 2010 releases are bundled with version 2.0 of the script, while the 2011 release comes with version 2.1. Both these versions yield the same OWL and KRSS outputs. By applying version 2.1 of the Perl transformation script to the 2009 releases we get a match on the output (of OWL and KRSS). As such, we used version 2.1 of the transformation script on the 2009 releases in order to carry out this study. 4.1
As reported in [
Effectual Ineffectual 13 http://protege.stanford.edu/ 14 http://www.google.com/publicdata/home 15 http://www.ihtsdo.org/ 16 http://www.perl.org/ 10000 1000 100 10 1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20 v21 v22 v23 v24 v25 v26 v27 v28 v29 v30 v31 v32 v33 v34 v35 v36 v37 v38 v39 v40 v41 v42 v43 v44 v45 v46 v47 v48 v49 v50 v51 v52 v53 v54 v55 v56 v57 v58 v59 v60 v61 v62 v63 v64 v65 v66 v67 v68 v69 v70 v71 v72 v73 v74 v75 v76 v77 v78 v79 v80 v81 v82 v83 v84 v85 v86
Effectual Ineffectual
Throughout the corpus there is a high number of ine ectual removals, with an average of 35% of all removals. Out of these ine ectual removals 92% turned out to be strengthened axioms, which indicates a continuous re ning of information throughout the corpus. There is a high number of removed redundancies as well, constituting 49% of ine ectual removals. This tells us that there is some pruning of redundant information going on in the corpus. On average 5% of additions are ine ectual; among these, 73% are added redundancies, and 82% are weakened axioms. The latter occur typically due to adjustments in the class hierarchy. Despite being a high percentage, the number of ine ectual additions is generally low (Table 3). In cases where the number of ine ectual changes is quite high (e.g., O24 where 52% of changes are ine ectual, O27, O29 and O30 with 48% each) note that semantic di s would signi cantly understate the amount of activity performed. While structural di captures this, it does not analyse the logical impact of such changes.
We also identi ed a number of rewrites in the corpus. Particularly in O33, there are 227 rewritten axioms. Upon inspecting the rewritten axioms, we noticed that these changes are not only syntactic but also trivial and easily detected. While ideally the underlying structural di would not include these, at least with our categorisation and alignment with source axioms, it is easy to spot and recognise the triviality.
Among the categories of e ectual changes we discovered that the majority of these are new and retired descriptions. In terms of e ectual additions the average of new descriptions is 60%, while retired descriptions average 51% of e ectual removals. This high number of new descriptions is unsurprising, as the terminology keeps increasing. Despite the high values of retired descriptions, it does not mean that such concepts are deleted, it could instead suggest concept renamings. Strengthenings average around 4% of all additions (with and without new terms), indicating re nements of concepts with additional constraints. It is natural that upon introducing new terms, others need to be re-described, thus explaining the strengthenings with new terms. There are not as many weakenings in the corpus as there are strengthenings. This tells us that typically there is not much reduction of information from version to version. The average of weakenings (with or without retired terms) throughout is below 2% of all removals. Pure additions account for 37% of all additions, divided between 24% of additions with new terms and 13% without. Typically pure changes with shared terms suggest adjustments to the class hierarchy, while pure additions involving new terms point to the insertion of said terms and subsequent re-adjustment of the hierarchy accordingly. The average of pure removals throughout the corpus is 47%, split between 23% with retired terms and 24% without. 4.2
Throughout the 5 versions of SNOMED CT there are typically more e ectual changes (74%) than ine ectual (26%), as shown in Figure 4. However, within the removals there is a high number of ine ectual changes (10,214), averaging 37% of all removals (see Table 4). In the additions there are on average more e ectual changes (84%) than ine ectual (16%).
The majority of e ectual additions (43% of all changes) are pure additions, suggesting numerous alterations to the class hierarchy, possibly as a result of
Change
Type
the addition of new terms, as there is also a high number of pure additions involving new terms. Naturally when introducing a new, non-leaf term in the class hierarchy it causes shifts throughout one or more branches. Thus, given the high number of new descriptions (6,266) throughout SNOMED CT, the detection of many pure additions is not surprising.
Within the e ectual removals (31% of all changes) we see a similar pattern as in the additions: the majority (63%) of e ectual removals are pure removals, some with retired terms. There is also a high number of retired descriptions, suggesting that as terms are retired (either deleted or declared as `retired concepts') this causes modi cations to the class hierarchy. This also explains the high number of pure additions, with shared and retired terms. Weakenings are not as common, amounting to 10% of e ectual removals.
In terms of ine ectual additions (8% of all changes), there are mostly weakened axioms (3,897), as well as a high number of avoided redundancies (2,561). The latter are derived from modi cations to the class hierarchy, which in this case can be ignored. Had there been redundancies it would be advisable to inspect them, and possibly dispose of these from the ontology. The weakened axioms, on the other hand, should be veri ed for correctness, as they reveal a loss of constraints w.r.t. the terms described in such axioms.
The number of ine ectual removals (18% of all changes) is much higher than the additions, and consists of mostly strengthened axioms (9,386). This suggests that a constant tightening of the ontology is taking place; despite the fact that these axioms are removed, it is only due to the introduction of stronger constraints on the meaning of such axioms. The remaining ine ectual removals are avoided redundancies (4,395).
Overall we see a good balance of e ectual additions vs removals, and a lot more ine ectual removals than additions. By inspecting the di erent types of changes throughout the evolution of SNOMED CT, we can single out particular occurrences in more detail; e.g., when a new term is introduced in the class hierarchy (new description), it will typically lead to adjustments to the hierarchy (pure additions) involving both shared terms which have to be switched around, and the new term itself (or other new ones). Using a standard syntactic or semantic di such an analysis would be impractical, and much of the work would be left up to the user (such as checking which changes have logical impact). With this categorisation even a user who is not a domain expert or an ontology engineer can spot trends in the di between ontology versions, as we did here with SNOMED CT. Note that in SNOMED CT there is a bigger proportion of ine ectual changes than in the NCIt, and the number of certain types of change is similar in both cases, e.g., within ine ectual removals there are mostly strengthened axioms, followed by redundancies. However, in the case of SNOMED CT, there are only avoided redundancies, while in the NCIt there are redundancies which could be disposed of. Clearly certain ine ectual changes are in fact \refactorings", albeit in the case of strengthened and weakened axioms the refactoring would have to be of a set of axioms rather than a single axiom. Thus a strengthened axiom does not necessarily mean strengthening of the ontology, since the change might either introduce a redundancy or redistribute information from other axioms. 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, we can say both the axiom 2 and the ontology O2 are strengthened.
In terms of e ectual changes there are mostly new and retired descriptions in the NCIt, while in SNOMED CT the majority of e ectual changes are pure additions or removals. So we see that a major focus in SNOMED CT seems to be class hierarchy oriented, with many adjustments going on. In the NCIt, on the other hand, we see that there are a lot of new terms being introduced, and since we know that terms are never deleted, the high number of retired descriptions suggests there are many renamings of term names. In order to elaborate on the potential usefulness of the devised categories, let us look at a particular comparison, di (O32; O33), and walk through the output of the di from the perspective of a user. The output of di (O32; O33) is outlined in Table 5. A user whose role is to assure the overall progress and quality of changes is particularly interested in ensuring that e ectual changes are appropriate, and may also be interested in understanding why committed changes have no logical e ect. Looking at the di , the user immediately sees that the changes are balanced between e ectual and ine ectual, with most of the action in the e ectual additions and ine ectual removals. Being more concerned with added information, the user begins by inspecting the e ectual additions. Particularly by looking through new descriptions, the user is immediately aware of the new terms that have been introduced, as the following axioms demonstrate: 1: Oxidized Glutathione v P rotective Agent 2: CHP -HER-2 P eptide V accine v 9Chemical Or Drug Has P hysiologic Ef f ect.Immunopotentiation Ef f ect
Change
Type
The axiom 1 introduces the term Oxidized Glutathione, while 2 introduces CHP -HER-2 P eptide V accine. The user can restrict his/her attention to those additions that concern his domain expertise, thus being also interested in strengthenings within this domain. Let us look at the latter: axiom 3 is a strengthening of 3, and 4 a strengthening with new terms (Anterior F oramen M agnum) of 4, as follows: 3: Skin Appendage Adenoma Adenoma u Benign Epithelial Skin
N eoplasm u Benign Skin Appendage N eoplasm 3: Skin Appendage Adenoma v Adenoma 4: Anterior F oramen M agnum M eningioma F oramen M agnum M eningioma u 8Disease Has P rimary Anatomic Site.Anterior F oramen M agnum 4: Anterior F oramen M agnum M eningioma v F oramen M agnum
M eningioma
The user sees in both axioms an addition of information w.r.t. the previous version, and can narrow down the search to axioms concerning his/her domain area to verify correctness. In the same manner the user goes through those alterations with and without new terms. The following axiom 5 is an alteration, and 6 is an alteration with a new term c Concept Status: 5: Epidermal Involvement v Cutaneous Involvement 6: U M LS Cross-Ref erence Concept v c Concept Status
This type of axiom generally indicates adjustments to the class hierarchy, which the user may want to verify in his respective domain area. Switching over to ine ectual changes, the user begins by inspecting the rewrites. Since rewritten axioms are supposed to convey the same logical meaning in both O32 and O33, the user wants to understand why these are presented by the di . The users nds axiom 7 rewritten into 7, as follows:
The change from 7 to 7 is purely syntactic, and thus both axioms carry the same logical meaning. As discussed in Section 4.1, we nd here a particularity of OWL's notion of structural equivalence that could be re ned. Seeing as the inspected rewrites exhibit this form, the user skips further analysis of this type of change. Next the user looks at redundant axioms; since redundancies do not add any logical meaning the user may want to prune them. Such redundancies are guaranteed not to alter the semantics of the ontology alone, and so can be immediately disposed of. The user nds redundancies of similar form to 8, with a justi cation J 8 O33, as follows: 8: CS-1008 v 9Chemical Or Drug Has M echanism Of Action.
Antigen Binding Interaction J 8 = fCS-1008 v M onoclonal Antibody,
M onoclonal Antibody v 9Chemical Or Drug Has M echanism Of Action.Antigen Binding Interactiong
Upon nding these, the user proceeds to remove them from the ontology. Meantime it would be helpful to investigate with the corresponding developers why these redundancies were being added in the rst place. The user then carries on inspecting avoided redundancies; among these the user comes across several of the same kind as 9, with corresponding justi cation J 9 O32: 9: Lactic Acid L v Industrial P roduct J 9 = fLactic Acid L v P harmaceutical Excipient,
P harmaceutical Excipient v Industrial Aid,
Industrial Aid v Industrial P roductg
This change reveals to the user that some adjustments to the class hierarchy took place involving terms in f9. The user can inspect the class hierarchy to con rm this, and recognise that such changes would be redundant in the previous ontology. However, while 9 is redundant w.r.t. to O32 it is still the case that removing it from O33 would cause loss of information. As such, the user leaves these avoided redundancies behind and begins to verify weakened axioms. A weakened axiom implies a reduction of constraints on models of the ontology, and so should be carefully reviewed. The user comes across 10 with a justi cation
The user realises that 10 is indeed weaker than the axiom in J 10 O32, and not being the domain expert dispatches this change to the respective expert for review and con rmation of the original intent. Subsequently the user inspects the strengthened axioms, since these are more constricting in O33 than they were in O32. Consider axiom 11 and its justi cation J 11 O33:
11: Sporadic Cylindroma v Cylindroma J 11 = fSporadic Cylindroma Cylindroma u 8Disease Has F inding:
N on-Hereditary Lesiong
Given changes of this type it may be desirable to con rm them, and so the user takes the same action as for weakened axioms and delegates them to appropriate domain experts while inspecting other changes of interest.
We have shown here an example of how such categorisation makes change analysis far more manageable, as opposed to having users inspect a whole set of axioms or terms. The devised categories allow users to focus on speci c types of change, and particularly see what these are a change of (in the previous or subsequent version). Moreover a categorisation of this type produces a reasonable division of labour, thus making collaboration e orts more practical. 5
The diachronic studies of the NCIt and SNOMED CT revealed that all the categories of changes occur throughout each corpus, providing indications as to the impact of changes. We showed that such a categorisation of change sets is useful for change analysis, with particular bene ts for division of labour by ontology engineers. By means of this categorisation we can group changes according to their impact, allowing users to shift their attention to speci c types of changes, rather than going through a change set while inspecting both ontologies. With our correspondence of changes between ontologies we can show the changed axioms and what they are a change of. Consequently, by analysing changes in this way there is no need for constantly having to inspect ontologies manually. As such, we can support users in understanding the impact of their changes (or lack thereof), and re ne these before publishing newer versions.
We found that ine ectual changes account for a signi cant amount of changes throughout the NCIt, as well as in SNOMED CT with an even higher proportion. Despite the fact that semantic di s ignore these changes in their output, we show that they provide helpful modelling insights, and thus are worth examining. For instance, we discovered a high number of redundant axioms in the NCIt, some of which could be disposed of. Also we found a number of structurally distinct ine ectual changes that are clearly neglectable: the rewrites in the NCIt. These indicate the need for improvement of the underlying di . In general the inspection of ine ectual changes is helpful to prevent, e.g., re-doing work or introducing redundancy. Relying on semantic di s one would be missing out on these meaningful ine ectual changes, which in turn could help users recognise the impact of certain types of change.
The next step in our study is to evaluate the di tool with users. In particular we expect to con rm that the categorisation helps users in understanding changes between ontologies. In terms of further analysis of the NCIt and SNOMED CT we intend to inspect the history of axioms, as in checking the progress of each axiom throughout the corpus since it was introduced (e.g., changes in constructors or strengthenings that the axiom went through). Another future survey involves checking for patterns of change throughout the corpus, e.g., if all strengthenings exhibit a common form.