The ontology language OWL, a W3C recommendation, is currently being revisited by a W3C working group. It is anticipated that the updated version of the W3C recommendation produced by the working group will include a number of popular fragments of OWL that have more favourable computational properties than the full language. One candidate for such a fragment is an extension of the lightweight description logic E L, which only provides conjunction and existential restriction. It is well-known that, in E L and many of its extensions, satis ability, subsumption, and other standard reasoning problems can be decided in polynomial time. In this paper, we give further evidence for the attractive computational properties of E L by analyzing the practical feasibility of two more involved reasoning problems, which can also be solved in polynomial time: logical di and the extraction of semantic modules.
The standard di operation for text les is an indispensible tool for comparing
di erent versions of text les and source code les. In contrast, a purely syntactic
di operation is hardly useful to compare ontologies, see e.g. [
The purpose of module extraction is to identify, given a signature and an ontology T , a (preferably small) fragment T0 of T such that T0 contains the same information about as T and thus behaves in exactly the same way as T in all applications using only symbols from . Possible applications include (a) importing, instead of T , the ontology T0 into another ontology, (b) computing the classi cation of the terms in , and (c) querying a database using T0 instead of T . We use a logic-based, semantic de nition of a module based on (modeltheoretic) conservative extensions which ensures that T and T0 \contain the same information about " in a very strong sense.
This paper is structured into two parts. The rst part presents experiments
with the system CEX. This prototype computes, given two ontologies formulated
as (cyclic or acyclic) TBoxes in the description logic E L and a signature , a
complete list of concept names that are involved in a subsumption between (possibly
complex) -concepts that is a consequence of one TBox, but not of the other.
By de ning as the set of shared symbols of the two TBoxes, we thus obtain
a list that can be regarded as the logical di erence. Most of the experiments
with CEX are based on (di erent versions of) Snomed ct, the Systematized
Nomenclature of Medicine, Clinical Terms. This acyclic TBox comprises 0.4
million terms and underlies the systematized medical terminology used in the
health systems of the US, the UK, and other countries [
The second part of this paper presents experiments with the system MEX
that extracts modules from ontologies formulated as acyclic E L-TBoxes. Similar
to the systems described in [
Let NC and NR be countably in nite and disjoint sets of concept names and role names, respectively. In the description logic E L, concepts C are built according to the syntax rule
C ::= > j A j C u D j 9r:C; where A ranges over NC, r ranges over NR, and C; D range over concepts. The semantics of concepts is de ned by means of interpretations I = ( I ; I ), where the interpretation domain I is a non-empty set and I is a function mapping each concept name A to a subset AI of I and each role name rI to a binary relation rI I I . The function I is inductively extended to arbitrary concepts by setting >I := I , (C u D)I := CI \ DI , and (9r:C)I := fd 2 I j 9e 2 CI : (d; e) 2 rI g.
A TBox T is a nite set of axioms, where an axiom can be a concept inclusion (CI) of the form A v C or a concept equation (CE) of the form A C with A a concept name. It is required that no concept name occurs more than once on the left hand side of an axiom in T . De ne the relation T NC NC by setting A T X i there exists an axiom of the form A v C or A C in T such that X occurs in C. Denote by T the transitive closure of T and set dependT (A) = fX j A T Xg. Intuitively, dependT (A) consists of all concept names which are used in the de nition of A in T . A TBox T is called acyclic if A 62 dependT (A) for any A 2 NC.
An interpretation I satis es a CI C v D (written I j= C v D) if CI DI ; it satis es a CE C D (written I j= C D) if CI = DI . I is a model of a TBox T if it satis es all axioms in T . We write T j= C v D (T j= C D) if every model of T satis es C v D (C D, respectively).
A signature is a nite subset of NC [ NR. The signature sig(C) (sig( ), sig(T )) of a concept C (axiom , TBox T ) is the set of concept and role names which occur in C ( , T , respectively). If sig(C) and similarly for axioms and TBoxes. 3
, we also call C a -concept In this section, we present the experimental results for CEX. We rst give a logical characterization of the algorithm underlying CEX.
Description of CEX : For any two EL-TBoxes T0 and T1 and signature , the algorithm implemented in CEX outputs, in polytime, the following two lists: { the list Di R (T0; T1) consisting of all A 2
C with T0 6j= C v A and T1 j= C v A. { the list Di L (T0; T1) consisting of all A 2
C with T0 6j= A v C and T1 j= A v C. such that there is a -concept such that there is a -concept One can show that, if there exist -concepts C and D such that T1 j= C v D but T0 6j= C v D, then an A 2 occuring in C or D is in Di R (T0; T1) or Di L (T0; T1), respectively. In particular, both lists are empty if, and only if, T0 and T1 do not di er w.r.t. . We illustrate the de nition using the following example. Let T0 be the TBox containing the following three axioms:
(1) (2) Removal foreign body from neck
Assume that T0 is re ned by replacing axiom (1) by the axiom Neck injection v Neck operation. Let T1 be the new TBox. To nd out how this update in uences the relationship between concepts distinct from Neck operation, one computes the di erence between T0 and T1 for the signature consisting of all symbols distinct from Neck operation. Then Removal foreign body from neck 2
Removal foreign body from neck. Notice that no di erence between T0 and T1 is visible by comparing the induced class hierarchies over .
CEX is an OCaml program [
Logical di erence between SM-05 and SM-06. Table 1 shows the average time and memory consumption of CEX computing the lists Di R (SM-05; SM-06) and Di L (SM-05; SM-06) and vice versa for 20 randomly generated signatures of size 100, 1 000, etc. The average size of the sets Di R (SM-05; SM-06) and Di L (SM-05; SM-06) are provided. Observe that no di erences have been
CEX: Di (SM-05,SM-06) CEX: Di (SM-06,SM-05) Size of Time Memory jDi L j jDi R j Time Memory jDi L j jDi R j (Sec.) (MByte) (Sec.) (MByte) 100 found for signatures of size 100. This means that the two versions of Snomed ct are not distinguishable by any implied subsumptions formulated with concept names from the 20 randomly generated signatures of size 100.
Comparison with the classi cation approach. We compare the size of Di L [ Di R as computed by CEX with the number of concept names A 2 for which there is a di erence in the class hierarchy restricted to . The experiments show how many of the di erences between two TBoxes detected by CEX can be extracted from a straightforward comparison of class hierarchies.
To facilitate the experiments, we use an empty TBox and an SM-05 fragment containing about 140 000 axioms. For every number between 10 and 270 with the step of 10, we generated 500 samples of a random signature containing this number of concepts and 20 roles. The results of the experiments are given in Figure 1. (a) shows that, for these signatures, the number of concept names CEX outputs is about ve times larger than the number of concept names occuring in di erences between the class hierarchies. In (b), we do not count the number of di erences but analyse how often the two approaches detect di erences at all. More precisely, we give the percentage of cases when CEX detects a di erence between the two TBoxes and when a di erence is visible in the class hierarchies. For signatures larger than 200, both approaches almost always detect di erences. But for smaller signatures there is again a signi cant gap between the two approaches.
We note that the gap between di erences detected by CEX and di erences visible in class hierarchies is less signi cant if less roles names are in the signature . But experiments show that even for signatures without role names CEX often detects di erences that do not occur in the class hierarchy.
Scalability. We demonstrated in the previous section that CEX is capable of nding the logical di erence in two unmodi ed versions of Snomed ct. In order to see how CEX's performance scales, we now test it on randomly generated acyclic TBoxes of various sizes. Each randomly generated TBox contains a certain number of de ned- and primitive concept names and role names. The ratio between concept equations and concept inclusions is xed, as is the ratio between existential restrictions and conjunctions. The random TBoxes were generated for a (a) Di erence size (b) Proportion varying number of de ned concept names using the parameters of SM-05: 62 role names; the average number of conjuncts is 2:59; the equality-inclusion ratio is 0:102; and the exists-conjunction ratio is 0:652. For every chosen size, we generate a number of samples consisting of two random TBoxes as described above. We apply CEX to nd the logical di erence of the two TBoxes over their joint signature. Figure 2 shows the time and memory consumption of CEX on randomly generated TBoxes of various sizes, where the maximum length of conjunctions was xed as two (M=2).
The performance of CEX crucially depends on the length of conjunctions as illustrated in Figures 3 and 4, where the number of conjuncts in each conjunction is randomly selected between two and M . The curves break o at the point where CEX runs out of memory. For example, in the case M = 22 this happens for TBoxes with more than 9 500 de ned concept names. 4
The purpose of our second tool, MEX, is to extract modules from a TBox. We use the following, logic-based de nition of a module. De nition 1 (Semantic modules). Let T0 T1 be TBoxes and sig(T0). { T0 is a weak semantic -module of T1 if for every model I of T0 there exists a model I0 of T1 which coincides with I on . { T0 is a strong semantic -module of T1 if for every model I there exists a model I0 of T1 n T0 which coincides with I on .
In any standard description logic, every strong semantic -module is a weak
semantic -module. The converse does not hold: if T0 = fA >g, T1 = T0 [
fB v Ag and = fA; Bg, then T0 is a weak semantic -module of T1, but
not a strong semantic -module. Intuitively, the di erence between weak and
strong modules is that strong modules additionally require the ontology without
the module to not imply any dependencies between symbols in . This stronger
type of module has been introduced in [
Call an axioms trivial if it is of the form A >, or A > u >, etc. Surprisingly, for acyclic E L-TBoxes not containing trivial axioms the notions of weak and strong semantic modules are equivalent: Theorem 1. Let T0 T1 be acyclic E L-TBoxes not containing trivial axioms and sig(T0). Then T0 is a weak semantic -module of T1 i it is a strong semantic -module of T1.
We now discuss our tool MEX for extracting semantic modules.
Description of MEX. For any acyclic EL-TBox T1 not containing trivial axioms and signature , the algorithm implemented in MEX extracts the (uniquely determined) smallest weak/strong semantic [ sig(T0)-module T0 of T1.
Given , the algorithm may thus return a 0-module for some 0 . Intuitively, the purpose is to make the module self-contained in the sense that, if a TBox T implies a dependency between symbols occuring in T0, then this dependency is implied by T0 already.
The size of modules. We compare the modules generated by MEX with the
minimal modules generated by a number of other extraction algorithms. It is
not di cult to see that, when applied to an acyclic EL-TBox T1 and signature
, the module extraction algorithms presented in [
An exception are the modules generated using the >-based locality approach
of [
De nition-closed modules are appropriate for several applications of
extraction algorithms. For applications that do not need de nitions of terms in the
input-signature, however, the smallest weak/strong semantic module appears to
provide exactly the information required. We show that this can signi cantly
reduce the size of modules. The following experiment compares the minimal
size of de nition-closed modules with the size of modules generated using MEX,
when applied to Snomed ct. We note that the system MEX takes into account
also the role inclusions of Snomed ct. In the experiments below, it outputs a
weak (equivalently, strong) semantic module of Snomed ct, but because of the
role box this output of MEX is not necessarily a minimal semantic module. To
compute the minimal de nition-closed modules, we use the module extraction
feature of the CEL reasoner [
In Figure 5, an input signature consisted of a number of concept names that were randomly selected from SM-05. The size of the input signatures varied from 100 to 1 000 concept names. For every signature size, we use 1000 random signatures.
Figure 5 shows the maximal, minimal, and average module sizes depending on the size of the input signature. Figure 6 shows the frequency distribution of the de nition-closed modules, and Figure 7 the distribution for the semantic modules. In each gure, there are ve di erent histograms, one for each of the signature sizes ranging over 100, 250, 500, 750, and 1 000. Each of these histograms displays the distribution of the module sizes of 1 000 extracted SM-05 modules for randomly selected signatures of a certain size. For instance, the histogram labelled with CEL100 in Figure 6 shows the distribution of the size of 1 000 de nition-closed modules for the signature size 100 extracted from SM-05. For the sake of comparison, the axes in both gures have the same scaling resulting in the histogram MEX100 being capped at 200 for empty semantic modules. The missing value of MEX100 for empty modules is 547.
To facilitate the comparison of the module sizes, consider Table 2. It presents the average module size together with the standard deviation of de nition-closed and semantic modules for random input signatures of various sizes. Recall that the standard deviation indicates how much the module sizes vary from the average. Notice that, for small signature sizes, the standard deviation of semantic module sizes is relatively high. The reason is that MEX extracts many small or even empty semantic modules for small signature sizes. For instance, 547 of 1 000 extracted modules where empty for signature size 100. Intuitively, the reason for an empty module is that Snomed ct does not imply any subsumptions between concepts formulated in the chosen signature. When only considering the semantic modules for signature size 100 that contain more than 10 axioms, the average module size becomes 889:15 and the standard deviation decreases to 125:63; see the last column of Table 2. In this section, we show that MEX can be used to speed-up the computation of the logical di erence between TBoxes. The left hand side of Table 3 is taken from Table 1 while its right hand side shows the average time and memory consumption of computing the same lists, but here we rst use MEX to extract semantic -modules T0 and T1 from SM-05 and SM-06, respectively, and then CEX computes Di R (T0; T1) and Di L (T0; T1). Though CEX is already very e cient, the results show that the latter procedure is even faster and gives results almost instantaniously for small . 6
In this paper, we have proposed the novel notion of a logical di and presented
a new logic-based notion of a module in a TBox. In both cases, we have
developed polytime algorithms and presented an experimental evaluation on di erent
versions of Snomed ct. The experiments suggest that, in both cases, a rigorous
logic-based approach is computationally no more expensive than most ad-hoc
approaches while providing signi cant advantages. In the case of logical di , the
advantage is that also subtle di erences between TBoxes can be detected. In
100
10 000 517.7 1 424.3
module extraction, our approach leads to smaller modules than many other
approaches. It has to be noted, however, that so far our approach is limited to E L.
Extending at least some of the techniques to more expressive languages remains
a challenging problem. For rst results in this direction, we refer the reader to [