Detecting, much less understanding, the di erence between two description logic based ontologies is challenging for ontology engineers due, in part, to the possibility of complex, non-local logic e ects of axiom changes. It is often quite di cult to even determine which terms have had their meaning altered by a change. To address this, various principled notions of \semantic di " (based on deductive inseparability) have been proposed in the literature and have been shown to be computationally practical for the expressively restricted case of ELHr-terminologies (which covers signi cant fragments of SNOMED-CT). However, problems arise even for such limited logics as ALC: First, computation gets more di cult, becoming undecidable for logics such as SROIQ which underly the Web Ontology Language (OWL). Second, the presence of negation and disjunction make the standard semantic di erence too sensitive to change: essentially, any logically e ectual change always a ects all terms in the ontology. To address these issues, we formulate the central notion of nding the minimal change set based on model inseparability, and present a method to di erentiate changes which are speci c to (and \of interest" for) particular concept names. Subsequently we present a series of computable approximations, and compare the variously approximated change sets over a series of versions of the NCI Thesaurus (NCIt).
Determining the signi cant di erences between two documents (so-called \di ")
is a standard and signi cant problem across a wide range of activities, notably
software development. Standard textual di ng algorithms perform poorly on
description logic (DL) based ontologies, both for structural reasons (e.g., ontology
serializations, such as those of OWL, tend not to impose stable ordering of
axioms), and due to the highly non-local and unintuitive logical e ects of changes
to axioms. Syntactic di s, such as those based on OWL's notion of \structural
equivalence" [
In this paper, we provide a non-trivializable notion of semantic di erence and a series of computable approximations of it for expressive description logics. We evaluate these algorithms on a select subset of the National Cancer Institute Thesaurus (NCIt) corpus, comparing the changes found via the proposed approximations and related approaches. Our experiments show that one approximation, \Grammar di ", nds signi cantly more changes than all other methods across the corpus and far more than are identi ed in the NCIt change logs. 2
We assume the reader to be reasonably familiar with ontologies and OWL, as
well as the underlying description logics (DLs) [
The restriction of an interpretation I to a set of terms is denoted Ij . Two interpretations I and J coincide on a signature (denoted Ij = J j ) if I = J and tI = tJ for each t 2 .
Throughout this paper we use the notion of model conservative extension
(mCE) [
. (1) (2) (3)
-inseparable from O1 (O1 mCE O2) w.r.t. L Di (O1; O2) if fIj j I j= O1g = fJ j j J j= O2g
= f j O1 6j= ; O2 j= and is a GCI over L, with e
g -entails O2 if Di (O1; O2) = ;
The tool ContentCVS [
C ! B j 9r:B j 8r:B j :B
The rationale behind the use of this grammar is not exactly clear, and seems
rather ad hoc. In a user study of ContentCVS, users criticised \the excessive
amount of information displayed when using larger approximations of the
deductive di erence" [
The di method underlying the system CEX [
The computational complexity of deciding -entailment is undecidable for
expressive DLs such as SROIQ. For E L it is already ExpTime-complete [
= fA; Bg, but if we take 0 = fOf1 \ Of2g then that is no longer the case. A witness axiom for the separability would be, e.g., := A v :C t D. This witness \witnesses" a change to every concept A0 2 0; for each witness axiom 0 : A0 v :C t D we have that O1 6j= 0, while O2 j= 0. Such a witness would su ce to pinpoint, according to -di erence, that all terms in 0 have changed: AT(O1; O2) 0 = 0 since > v :C t D. Consequently, this kind of witnesses are uninteresting for any particular concept aside from >. Likewise, a change A v ? implies that, for all B in the signature of the ontology in question, we have that A v B. Yet these consequences are of no interest to any concept B. 1 Additionally, ContentCVS also compares role hierarchies. 2 Albeit the implementation is restricted to acyclic ELHr terminologies (EL extended with role inclusions and range restrictions).
Similar to the case of the least common subsumer [
Given the shortcomings of existing methodologies, we present a semantic di method that a) determines which concepts have been a ected by changes. For exposition reasons, we concentrate on concepts, though roles are easily added. And b) identi es which concepts have been directly (or indirectly) changed.
Ideally, a solution to these problems would be 1) a computationally feasible function (for OWL 2 ontologies), 2) based on a principled grammar, that 3) returns those concept names a ected by changes between two ontologies, while 4) distinguishing whether each concept name is directly (or indirectly) specialised and/or generalised. 4.1
Given two ontologies O1 and O2, such that O1 6 O2 (i.e. there exists at least one e ectual change in Di (O1; O2)), we know that O1 and O2 are not -inseparable (for = Oe1 [ Oe2) w.r.t. model inseparability, i.e. O1 6 mCE O2 since an e ectual change implies some change in semantics. In order to pinpoint this change, we need to nd the set of terms 0 s.t. O1 is mCE-inseparable from O2 w.r.t. the remaining signature n 0: O1 mnCE0 O2. Then we know that, from O1 to O2, there are no changes in entailments over n 0. We refer to this set of terms 0 as the Minimal Change Set (denoted MinCS(O1; O2)), in the sense that we can formulate a non-trivial entailment over 0 s.t. O1 6j= but O2 j= . Thus we denote these terms as a ected.
a ected terms between O1 and O2 if: 0 is a set of minimal O1 6 m0CE O2 and for all 00 ( 0 : O1 m0C0E O2:
In order to form the minimal change set, we take the union over all sets of a ected terms in MinAT(O1; O2).
MinCS(O1; O2) := S MinAT(O1; O2) :
Given a set of witness axioms, we can tell apart specialised and generalised concepts depending on whether the witness concept is on the right hand side (RHS) or the left hand side (LHS) of the witness axiom, accordingly. Furthermore, we regard a concept name A as directly specialised (generalised) via some witness C if there is no concept name B that is a superconcept (subconcept) of A, and C is also a witness for a change in B. Otherwise A changed indirectly.
De nition 4 (A ected Terms) For a di function , the sets of a ected concept names for a signature are: - AT(O1; O2)L = fA 2 - AT(O1; O2)R = fA 2 j there exists A v C 2
- Di (O1; O2) g j there exists C v A 2 - Di (O1; O2) g - AT(O1; O2)> = - AT(O1; O2)? = f>g if there is a > v C 2
; otherwise f?g if there is a C v ? 2 ; otherwise - Di (O1; O2) - Di (O1; O2) - AT(O1; O2) = SY 2fL;R;>;?g - AT(O1; O2)Y
and a set of terms + := -AT(O1; O2)L (analogously A 2 [ f>; ?g:
and there is no B 2 + s.t. O2 j= A v B (O2 j= B v A); O2 6j= A B, and
B v C (C v B) 2 - Di (O1; O2) :
and there is at least one B 2 + s.t. O2 j= A v B (O2 j= B v A);
O2 6j= A B and B v C (C v B) 2 - Di (O1; O2) : Concept A is purely directly changed if it is only directly changed (analogously for purely indirectly changed).
As an example, given ontologies O1 := fA v B; 9r:C v Dg and O2 := O1 [ fB v 9r:Cg, we have that B is purely directly specialised via witness 9r:C, while A is indirectly specialised via the same witness, since O2 j= A v B and B v 9r:C 2 Di (O1; O2), in other words, concept A changes via B.
The distinction between directly- and indirectly-a ected concept names, and the separation of concepts a ected via > and ?, allows us to overcome the problems described in Section 3, w.r.t. propositionally closed description logics. 4.2
Deciding the minimal change set between two ontologies involves deciding whether, for a given signature , two ontologies are mCE-inseparable w.r.t.
. Since mCE-inseparability is undecidable for SROIQ [
In addition, and in order to provide a basis for comparison between di notions, we de ne the set of di erences which would be captured by a comparison of the concept hierarchies between two ontologies, i.e. di erences in atomic subsumptions, as AtDi (O1; O2) . Hereafter we refer to ContentCVS's di notion as CvsDi (O1; O2) .
The rst approximation, Subconcept di (denoted SubDi (O1; O2) ), is based on subconcepts of ontologies, wherein we check whether there is a difference in entailments of type C v D, where C or D is a possibly complex concept from the set of -subconcepts of O1 and O2 (see De nition 5). It is at least conceivable that many entailments will involve subconcepts, and, if that is the case, those would be witnesses that the user could understand, since they are explicitly asserted in either ontology. Moreover, this notion may exhibit entailment di erences which would not show up if we restrict ourselves to either atomic subsumptions, or speci c forms of entailments (in the manner of ContentCVS). The restriction to forms of concepts explicit in either ontology limits the amount of change captured. E.g., if we have O1 = fA v 9r:Bg, and in O2 add an axiom B v 9s:C, the change A v 9r:9s:C would not be found. However, the rationale behind this approach is that we could detect other kinds of change in a principled and relatively cheap way, e.g., O1 = fA v Bg, O2 = O1 [ fB v 9r:(C u 9r:D)g; we have that O1 6j= := A v 9r:(C u 9r:D), while O2 j= .
In order to avoid only considering witnesses in their explicitly asserted form, we extend the previous di notion and present Grammar di (denoted GrDi (O1; O2) ), which detects di erences in additional types of entailments; the grammars below de ne the types of concepts taken into account by Grammar di , where SC stands for a subconcept of O1 [ O2.
C ! SC j SC t SC j 9r:SC j 8r:SC j :SC
C ! SC j SC u SC j 9r:SC j 8r:SC j :SC
The semantic di erence between ontologies w.r.t. each mentioned di notion is de ned as follows: De nition 5 Given two ontologies and a signature for a di notion is: , the set of -di erences - Di (O1; O2) := f 2 -ax j O1 6j= ^ O2 j= ^ e g where the set -ax is de ned as follows: if if if if if = At; fC v D j C; D 2 g = Sub; fC v D j C; D subconcepts in O1 [ O2g = Gr; fC v D j D a concept over GL; or C a concept over GRg = Cvs; fC v D j C 2 and D a concept over Gcvsg = CEX; fC v D j C; D subconcepts in L( )g
It is not hard to see that there are subset relations between each di and the actual MinCS(O1; O2) that they approximate, as per Lemma 1: Lemma 1 Given two ontologies and a signature :
AtDi -AT(O1; O2)
SubDi -AT(O1; O2) CvsDi -AT(O1; O2)
GrDi -AT(O1; O2)
GrDi -AT(O1; O2)
MinCS(O1; O2)
The current implementation of CEX only takes as input acyclic ELHr terminologies, that is, ELHr TBoxes which are 1) acyclic and 2) every concept appears (alone) on the left-hand side of an axiom exactly once. In order to apply CEX to knowledge bases that are more expressive than ELHr terminologies, we rely on an approximation that uses CEX as a sub-routine.
De nition 6 (Approx-CEX) Given two non-ELHr ontologies, the ApproxCEX procedure is: 1. For i 2 f1; 2g, approximate Oi as an ELHr terminology, resulting in Oi0: (a) Remove all non-EL axioms. (b) Break cycles (non-deterministically).
(c) Remove all but one axiom with a given atomic left-hand side.
3. For each 2 T empCS, add to FinalCS if O1 6j= and O2 j= . 4. Return FinalCS; the set of axioms in the di .
Note that step 1 is parameterizable with any ELHr approximation algorithm.
Additionally, step 2 can be replaced with a di implementation for more
expressive logics, with either the input approximation (step 1) and soundness check
(step 3) removed, or with an altered step 1 depending on the expressivity of the
input. Step 4 in De nition 6 is necessary to ensure that changes detected within
the ELHr approximations (obtained in step 1) are sound changes w.r.t. the whole
ontologies. Obviously, this approximation-based procedure throws away a lot of
information and is not deterministic. However, even such an approximation can
o er useful insight, esp. if it nds changes that other methods do not. There are
more elaborate existing approximation approaches (e.g., [
The object of our evaluation is a subset of the NCIt corpus used in [
The experiment machine used is an Intel Xeon Quad-Core 3.20GHz, with
16Gb DDR3 RAM. The system runs Mac OS X 10.6.8, Java Virtual Machine
(JVM v1.5), and all tests were run using the OWL API (v3.2.4) [
In terms of computation times, on average computing AtDi (O1; O2) takes 20 seconds, Approx-CEX takes 9 minutes, while computing SubDi (O1; O2) takes 35 minutes. The computation of GrDi (O1; O2) takes 14 hours for a subset of the ontology signature of size 1800 concept names, and ContentCVS 10 hours on the same randomly selected signature as GrDi (O1; O2) .4 5.1
The comparison of each di w.r.t. number of a ected concept names found is shown in Table 1, which displays the number of specialised concepts (L-changes), generalised concepts (R-changes), and the total number of a ected concepts. Figure 1 shows a comparison of the number of a ected concept names found by ContentCVS and Grammar di within the randomly selected signatures. Note that, at this point, no distinction is made between direct and indirect changes.
Due to computational issues regarding Grammar di and ContentCVS, instead of comparing each pair of NCIt versions w.r.t. = Oe1 [ Oe2 we take a random sample of the terms in the ontology (generally n 1800) such that a straightforward extrapolation allows us to determine that the true proportion of changed terms lies in the con dence interval (+-3%) with a 99% con dence level. In general, Grammar di , even taking into account the con dence interval, consistently detects more changes (both L and R) than all other di s. Also, 3 http://owlapi.sourceforge.net/ 4 Note that, originally, ContentCVS only computes AT(O1; O2)L , but in order to provide a direct comparison with the di s here proposed we also compute AT(O1; O2)R according to ContentCVS's grammar. 1200 1000
ContentCVS Grammar diff despite the one case where the lower bound of detected changes is inferior to another di , in version 4, it cannot be worse than Subconcept di by Lemma 1. The change logs supplied with each version of the NCIt contain those concept names which were subject to changes. However, it is unclear whether each reported change also (or solely) relates to annotation changes. It could be the case that a reported concept change is purely ine ectual. In spite of this ambiguity, it should be expected that a change log contains concept names that were directly changed, and this is what we aim to nd out in our next experiment; we extract the concept names mentioned in the change log, and verify whether the obtained direct changes for each NCIt version are contained in said change logs. The results are shown in Table 2, where the a ected concept names shown in Section 5.1 are partitioned into purely direct, purely indirect, or both directly and indirectly changed concepts. Overall, we see that the change logs do miss a lot of direct changes, more speci cally, on average, AtDi (O1; O2) reveals 767 changed concept names not mentioned in the change logs, while SubDi (O1; O2) uncovers 908 such concept names per NCIt version. 6
First thing to notice is that SubDi nds many more changes than AtDi and Approx-CEX, while often not reaching close to the projected values of GrammarDi (the average coverage being 41%). The latter, as expected, captures far more changes within the selected signatures than ContentCVS.
Considering the high number of a ected concepts found by SubDi in versions 4 and 5 of the NCIt, one can argue that analysing such a change set would be rather unpleasant. By categorising concept names in the change set according to whether they are directly or indirectly a ected, we can greatly reduce the information overload; notice that, e.g., in version 4 there are 45,825 specialised concepts, out of which there are only 78 purely directly changed concepts, and the majority of the remainder are purely indirect changes (43,100). Similarly in version 5, from 15,254 specialised concepts there are only 1,527 purely direct changes. Immediately we see that this mechanism can provide an especially helpful means to assist change analysis, by, e.g., con ning the changes shown upfront to only those which are (purely) direct.
Despite the optimisations applied in GrammarDi 's implementation, e.g., for GrDi (O1; O2)L we start by verifying whether there exists some e ectual change between ?-mod(fAg; O1) and ?-mod(fAg; O2), for each A 2 (analogously we use >-modules for GrDi (O1; O2)R ), only considering witnesses whose signature is contained in the module signature, stopping once we nd a single witness for a concept name, the computation of GrDi (O1; O2) still takes long, and needs further optimisations. The major bottleneck is that the >-modules for a concept name provide too big an approximation, e.g., for a top-level concept its >-module contains almost the whole ontology. Thus >-modules do not restrict much of our search space, not at least in the same way as ?-modules do. Additionally, in order to take advantage of the categorisation mechanism proposed, we would need to compute all witnesses for each -concept (which is relatively cheap in SubDi ). 7
We have formulated the problem of nding the set of a ected terms between ontologies via model inseparability, and presented feasible approximations to nding this set. We have shown that each of the approximations can nd considerably more changes than those visible in a comparison of concept hierarchies. Both sound approximations devised capture more changes than Approx-CEX. The restrictions imposed by CEX on the input ontologies make change-preserving approximations a challenge, as we have seen in our attempt to reduce the NCIt to E L in a less naive way.
The proposed distinction between (purely) direct and indirect allows users to focus on those changes which are speci c to a given concept, in addition to masking possibly uninteresting changes to any and all concept names (such as those obtained via witnesses constructed with negation and disjunction), thereby making change analysis more straightforward. As demonstrated by the NCIt change log analysis, we have found a (often high) number of direct changes that are not contained in the NCIt change logs, which leads us to believe the recording of changes does not seem to follow from even a basic concept hierarchy comparison, but rather a seemingly ad hoc mechanism.
In future work we aim to optimise the devised approximations so as to compare all NCIt versions w.r.t. their signature union, and deploy an end-user tool.