Computing equivalent EL-ontologies of minimal size is useful for various reasoning tasks such as uniform interpolation, ontology learning, rewriting ontologies into simpler DLs, abduction and knowledge revision. The corresponding tool support for minimising concepts and ontologies can also provide great help to ontology developers and end-users. We present a method for computing equivalent acyclic ELontologies of minimal size, where size is measured by number of occurrences of predicates. We applied our minimisation method to both known and generated ontologies with promising results.
Logical languages allow to represent the same facts in di erent equivalent ways, whose complexity can vary signi cantly. Description logics are used to model ontologies describing 100,000s of terms. Understanding ontologies of this size is further hindered by unnecessary verbosity. For example, the following are two simpli ed versions of axioms found in the Galen ontology:
TrueCavity
BodyCavity TruelyHollowBodyStructure
(1) (2) Axiom 1 seems unnecessarily verbose, especially since Galen already contains a de nition for the concept TruelyHollowBodyStructure. Using this concept, we can reformulate Axiom 1, obtaining a much more concise and accessible de nition for TrueCavity, while preserving all logical consequences of the ontology: TrueCavity
(3) Arguably, Axiom 3 is more accessible than Axiom 1, as the user has to parse less information when reading it. Furthermore, Axiom 3 makes more use of the structure provided by the ontology, and contains less redundant information.
In this paper, we investigate the task of computing equivalent ontologies of
minimal size, where size is de ned as the number of occurrences of concept and
role symbols in the ontology, or as the sum of its axiom sizes. The
corresponding decision problem is NP-complete. Automatic simpli cation of ontologies can
bene t a range of areas, of which we give some examples. Optimise existing
ontologies. Simplifying large ontologies by hand can be cumbersome, as the
developer needs full knowledge of all concepts available in the ontology and has to
consider numerous alternatives. A tool that automatically detects and removes
redundancy and simpli es concept expressions could provide great help to
ontology developers and end-users. (Semi-)Automated Ontology Generation.
There is a variety of techniques to generate ontologies automatically or
semiautomatically from di erent data sources such as tables or text documents [
While there exist solutions for certain sub-problems such as removing
redundant axioms [
The Description Logic EL
We recall the description logic E L used in this paper [
C ::= > j A j 9r:C j C u C; where A 2 Nc and r 2 Nr. For a set C = fC1; : : : ; Cng, we may abbreviate the corresponding conjunction C1 u : : : u Cn with d C. If a concept is of the form A, A 2 Nc, it is atomic. Otherwise it is complex. An E L ontology or TBox consists of concept inclusion axioms C v D and equivalence axioms C1 Cn used
as a shorthand for Ci v Cj, i; j n. Equivalence axioms like this correspond
to axioms of type OWLEquivalentClasses de ned in the standard ontology
language OWL [
We denote by sub(C) and sub(T ) the concepts occurring syntactically in C
and T . The semantics used is standard (see for example [
A regular tree grammar is a tuple G = hns; N ; F ; Ri, composed of a start symbol ns, a set N of non-terminal symbols such that ns 2 N , a ranked alphabet F of terminal symbols such that N \ F = ;, and a set R of derivation rules of the form n !R , where n 2 N and is a term over N [ F . A context C[X] is a term in which one subterm is replaced by a variable X. Given a regular tree grammar G = hns; N ; F ; Ri, the derivation relation !G is a relation on terms over N [ F such that t1 !G t2 i there is a derivation rule n !R 2 R and a context C[X] such that t1 = C[X 7! n] and t2 = C[X 7! ]. We denote by !+G the transitive closure of !G. The language generated by G, denoted by L(G), is the set of ground terms t over F such that ns !+G t. 3
Minimising E L Concepts Before we study the problem of minimising EL-ontologies, we focus on minimising EL-concepts, which plays a central role in our approach. We de ne the s -size of an EL concept inductively by s (>) = s (A) = 1 for all A 2 Nc, s (9r:C) = s (C) + 1 and s (C1 u C2) = s (C1) + s (C2). Informally, the size of a concept corresponds to the number occurrences of concept and role symbols, as well as of the > concept.
The notion of minimal concepts is captured in the following de nition: De nition 1. Given an EL ontology T and an EL concept C, C is minimal in T if there is no concept C0 with T j= C C0 and s (C0) < s (C). For an ontology T and a concept C, we denote by minc(C; T ) the set of minimal concepts C0 with T j= C C0. For an ontology T and two EL concepts C, Cc, we denote by minc(C; T ; Cc) the set of conditioned minimal concepts C0 for which T j= Cc u C Cc u C0 and for which there is no concept C00 with s (C00) < s (C0) and T j= Cc u C Cc u C00.
Intuitively, minimising an ontology involves minimising the concepts occurring in it. Whereas minc(C; T ) contains all minimal concepts equivalent to C, the set minc(C; T ; Cc) of conditioned minimal concepts contains concepts that are minimal in conjunction with a xed concept Cc. Conditioned minimal concepts can be used to determine minimal concept inclusion axioms. Take as example the axiom 9r:A v B u 9r:>. The concept B u 9r:> is minimal with respect to the empty ontology. However, since 9r:A v 9r:> already follows from the empty ontology, the axiom 9r:A v B is equivalent and uses only B on the right hand side. By xing 9r:A, as a conjunct, we obtain the desired concept for the axiom, since j= 9r:A u (9r:> u B) 9r:A u B, and minc(B u 9r:>; ;; 9r:A) = fBg.
The decision problem corresponding to minimising E L-concepts|is there a
concept C2 for a given T , C1 and k such that T j= C1 C2 and s (C1) k|
is NP-complete [
We de ne F EL as the symbols constituting the logic E L, that is, F EL = Nc [ Nr [ fu; 9g. For a given ontology T and concept Cs, we de ne the set N T ;Cs = fnC j C 2 sub(T ) [ sub(Cs) [ f>gg which contains a non-terminal symbol nC for every concept C occurring in T or Cs. Given an ontology T and a concept Cs, the grammar Gv(T ; Cs) is then given by hnCs ; N T ;Cs ; F EL; Ri, where R contains the following derivation rules: (R1): nC !R C for all nC 2 N T ;Cs (R2): nC !R 9r:nD for all nC ; nD 2 N T ;Cs such that C = 9r:D (R3): nC !R nC1 u : : : u nCn for all nC 2 N T ;Cs and sets fnC1 ; : : : ; nCn g N T ;Cs such that T j= C v Ci, 1 i n.
In practice, instances of rule (R3) can be determined by attening and classifying the ontology using any standard description logic reasoner. The generation of the other rules is trivial. We extend the notion of s -size to terms generated by Gv(T ; Cs) by setting s (nC ) = 1 for all nC 2 N T ;Cs . Furthermore, we denote by Con(t; G) the result of saturating the term t with derivation rules of type (R1), that is, by replacing every non-terminal with the corresponding concept. Note that there is exactly one rule of type (R1) for every non-terminal, so that Con(t; G) is always uniquely de ned.
Example 1. Consider the following ontology T1: The set N T1 contains non-terminals for the concepts B u 9r:9s:A1, B, 9r:9s:A1, 9s:A1, A1, 9r:9t:A2, 9t:A2, A2, A3 and >. We show an example derivation in the grammar Gv(T1; B u 9r:9s:A1).
nBu9r:9s:A1 (R3)
!G nB u n9r:9t:A2 (R2) !G B u 9r:n9t:A2 (R1)
!G B u n9r:9t:A2 (R3) (R1) !G B u 9r:nA3 !G B u 9r:A3 The applied rules of type (R3) are due to the entailments T j= B u 9r:9s:A1 v B, T j= B u 9r:9s:A1 v 9r:9t:A2 and T j= 9t:A2 v A3. One can show that T j= B u9r:9s:A1 B u9r:A3. In fact, one cannot derive a smaller equivalent concept.
It is shown in [
Lemma 1. Let T be an acyclic E L ontology, C an E L concept and G = Gv(C; T ). Further, let t1; t2 be terms over N T [ F T .
{ If t1 !G t2, then T j= Con(t1) v Con(t2). (v-monotonicity) { If t1 !G t2, then s (t1) s (t2). (s -monotonicity)
Due to the s -monotonicity, we do not have to follow derivations from concepts C0 for which s (C0) > s (Cm), where Cm is the currently known smallest equivalent concept of C. Note that this way, we have to check at most exponentially many derivations. Due to the v-monotonicity, we do not have to follow derivations of concepts C0 such that T 6j= C0 v C, where C is the concept to minimise. 4
We describe our method for minimising acyclic E L ontologies. The notion of s size is extended as follows to E L axioms and TBoxes: s (C v D) = s (C) + s (D), s (C1 : : : Cn) = 1 i nCi, s (T ) = 2T s ( ). An E L ontology T m is minimal if there is no ontology T such that T T m and s (T ) < s (T m).
We focus on computing minimal equivalent ontologies for a class of E L ontologies that is characterized by the following de nition.
De nition 2. Let T be an E L ontology. T is acyclic i there are no E L concepts C, D such that C 2 sub(D) and T j= C v 9r:D.
Note that since the de nition of acyclicity is de ned purely semantically, acyclicity is robust under logical equivalence: given two equivalent ontologies T1 and T2, T1 is acyclic if and only if T2 is acyclic.
Acyclic ontologies have the following property, which facilitates the minimisation of ontologies compared to cyclic ontologies.
Lemma 2. Let T m be an s -minimal acyclic ontology. Further, let 2 T m be of the form C1 v C2 or C1 : : : Cn. Then, every equivalent E L ontology T contains an axiom of the form C10 v C20 or C10 : : : Cm0 such that T j= C1 C10.
Due to this lemma, it is su cient to consider axioms for the minimised ontology whose left-hand side is equivalent to the left-hand side of axioms in the input ontology. This allows to partition the axioms in the ontology based on their left-hand side concepts, and minimise the partitions one after the other.
To formalise this idea, we rst group equivalent concepts in the ontology. For a concept C, we denote by [C]T the equivalence class of C, the concepts that syntactically occur in T and are equivalent to C: [C]T = fC0 j C 2 sub(T ); T j= C C0g. For each equivalence class [C]T , we de ne the before-mentioned partitions as T[C] = f j = C1 v C2 or = C1 : : : Cn;, C1 2 [C]T g. By Lemma 2, each non-empty partition T[Cm] in a minimal ontology T m has a corresponding non-empty partition T[C] in any equivalent ontology T .
Note that in Example 1, if we replace the concept B u 9r:9s:A1 with its minimal equivalent B u 9r:A3, we obtain an ontology that is not equivalent. In order to minimise a partition, we can only take into account entailments from axioms outside of that partition. For example, all elements in [C]T are equivalent to the same concept Cm minimal with respect to T , but if we replace equivalence axioms in T[C] by the tautological axiom Cm Cm, we do not obtain an equivalent ontology. To determine which axioms of the ontology have to be considered when minimising a partition T[C], we structure the ontology based on an implicability relation ;T between axioms and equivalence classes. Intuitively, if we have ;T , for some 2 T[C], a ects the meaning of , and we should not take into account when minimising T[C].
We de ne the relation ;T formally. For two E L axioms , , ;T i there is a TBox T 0 with T j= T 0, such that 2 T 0, T 0 j= and T 0 n f g 6j= .
;T1 A3 v 9s:A1 ;T1 .
Example 2. Take the ontology T1 used in the last example, and the two axioms = B u9r:A1 v 9r:9t:A2 and = B u9r:9s:A1 B u9r:A3. We observed in the example that T1 j= . Set T 0 = T1. We have T1 j= T 0, T 0 j= and T 0 n f g 6j= . Therefore, . In the same way, we can establish 9t:A2 v A3 ;T1 and In acyclic E L ontologies, the only cycles in the implicability relation are between axioms of the same partition.
Lemma 3. Let T be an 9-acyclic E L ontology and let ; with = C v D and = C v D . Further, let ;T T j= C C . be entailments of T and ;T . Then,
We extend ;T to equivalence classes. [C]T ;T [D]T i there are axioms C = C1 v C2 and D = D1 v D2, T j= C1 C; D1 D, such that C ;T D. As a consequence of Lemma 3, the only cycles in the implicability relation between equivalence classes are due to re exivity of the relation. The ontology T[Cin] = SfT[D] j [D]T ;T [C]T ; [D]T 6= [C]T g contains all axioms in T that may have an impact on the minimised version of T[C]. Lemma 4. Let T be an E L ontology and C; D 2 sub(T ) be two E L concepts such that [C]T ;T [D]T . Then, one of the following is true. 1. T j= D v C. 2. T j= D 9r:C. Algorithm 1: Algorithm for computing minimal equivalent ontologies. 3. There is a concept C2 such that [C2]T 62 f[C]T ; [D]T g, [C]T ;T [C2]T and [C2]T ;T [D]T .
Lemma 4 allows to compute a super-relation of the implicability relation that is su cient for our purposes. Condition 1 can be checked by attening and classifying the ontology, Condition 2 is syntactical, and Condition 3 corresponds to the transitive closure.
Example 3. There are three non-empty partitions in T1, corresponding to the equivalence classes [B u 9r:9s:A1]T1 , [9t:A2]T1 and [A3]T1 . Based on the observations in Example 2, we have [9t:A1]T1 ;T1 [B u 9r:9s:A1]T1 and [A3]T1 ;T1 [B u 9r:9s:A1]T1 . Using Lemma 4 and T1 j= 9t:A1 v A3, we can further establish [A3]T1 ;T1 [9t:A1]T1 . The ontology T1i[nBu9r:9s:A1] contains the union of T1[9t:A1] and T1[A3], that is, the last two axioms of the ontology. Therefore, in order to minimise partition T1[Bu9r:A3], we are only allowed to take into account entailments from the last two axioms, which means the equivalence T1 j= B u 9r:9s:A1 B u 9r:A3, which depends on all axioms, cannot be used. Theorem 1. Let T 1 and T 2 be two acyclic E L ontologies s.t. T 1 be any E L concept. Then, the following statements are true: T 2, and C 1. (T 1)[iCn] (T 2)[iCn] 2. (T 1)[iCn] [ T[C] 1 (T 1)[iCn] [ T[C]
2
Note that Theorem 1 also holds for any minimal equivalent ontology T 2. We can therefore construct a minimal equivalent ontology by rst computing a minimal ontology equivalent to (T 1)[iCn], and then a minimal extension equivalent to (T 1)[iCn] [T[C1]. By starting with the concepts C for which (T 1)[iCn] is empty, we can compute minimal equivalent ontologies in an incremental way. In each step, we extend the current minimal ontology with the next partition, until all partitions are processed. An overview of the corresponding top-level procedure is shown in Algorithm 1. The algorithm makes use of a procedure minimise(T[C]; T m) that minimises partitions T[C] against the already constructed ontology T m. This is described in the next subsection. 4.2
The concepts occurring in a minimised partition can be computed solely based on the concepts that occur in the original partition T[C], making use of logical relations that follow from T[Cin]. Note that [C]T contains all concepts that occur on the left-hand side of an axiom in T[Cin]. We further de ne the set S(C)T = fCs j C1 v Cs 2 T[C] or C1 : : : Cs : : : Cn 2 T[C]g, which contains the corresponding concepts on the right-hand sides. [C]T and S(C)T encode all information in T[C]: we obtain an equivalent ontology if we replace T[C] by f ([C]T ); C v d S(C)T )g. In the remainder of the section, we specify how to remove all redundancy from these sets, and how to determine the shape of the minimised partition.
We rst specify a minimal subset of the concepts in [C]T whose equivalence has to be expressed in the partition of any equivalent ontology.
De nition 3. A set C of concepts is equivalence-reduced against T if there are no distinct concepts C1; C2 2 C such that T j= C1 C2.
A set [C]T is a minimal set of required equivalent concepts in T[C] if [C]T in such that there are is a maximal, equivalence-reduced subset of [C]T against T[C] no concepts C1 2 [C]T , C2 2 [C]T with T[Cin] 6j= C1 C2 and T[Cin] j= C1 v C2.
First, we only have to consider sets of concepts that are equivalence-reduced against T[Cin], since all remaining equivalences already follow from T[Cin]. Second, we exclude all concepts from [C] whose equivalence can be expressed by a single concept inclusion axiom.
Example 4. Let T2 extend T1 with the following axioms:
B2 u B v 9r:9s:A1
B3
B4 u A3 We have S(B2 u B)T2 = f9r:9s:A1g and S(B3)T2 = [B3]T2 = fB3; B4 u A3; B4 u 9t:A2; B4 u 9s:A1g. We determine a minimal set of required equivalent concepts in T2[B3]. We have [B u9r:9s:A1] ;T [B2 uB] and [9t:A2] ;T [B3], and therefore in T2[B3] = T1[fB2 v 9r:9s:A1g. The minimal set of required equivalent concepts in T2[B3] is [B3]T2in= fB3; B4u9s:A1g. B4uA3 and B4u9t:A2 are not included in this in set, because T2[B2] j= B4 uA3 v B4 u9s:A1 and T2[B2] j= B4 u9t:A2 v B4 u9s:A1.
In order to determine a minimised partition for T[C], we have to distinguish cases based on S(C)T and any minimal set of required equivalent concepts in T[C]. We rst give the de nition of minimised partitions, and then explain it in detail.
De nition 4. Let T be an acyclic E L ontology and C an E L concept. Then, T[Cm] = f C g is a minimised partition for C in T i C is as follows, where [C] = fC1; : : : ; Cng is a set of minimally required concepts of C in T and Cs = d S(C)T : 1. If j[C] j 1 and T[Cin] j= C v Cs: The minimised partition only contains an equivalence axiom if there is more than one required equivalent concept (Condition 3 and 4). Otherwise, whether we need a concept inclusion axiom depends on whether all concept inclusions already follow from T[Cin] or not (Condition 1 and 2). Note that Cs = d S(C)T contains all concept inclusion information for C. A minimal concept inclusion axiom is determined as discussed in Section 3. Assume we have more than one required equivalent concept and C v Cs does not follow solely from T[Cin] and the required equivalences (Condition 4). In this case, we might just add a concept inclusion axiom as for Condition 2. However, this way we might miss the minimal solution. Observe that the axioms C1 C2, C1 v Cs are equivalent to C1 C2 C1 uCs. C1 u Cs has the same size as C1 v Cs, but it can be equivalent to a concept that is smaller to any concept inclusion axiom for C. For simplicity, we therefore always encode concept inclusions into the equivalence axiom if Condition 4 of the de nition is ful lled.
Theorem 2. Let T be an acyclic E L ontology, T m a minimal equivalent ontology, C an E L concept and T[Cm] be a minimised partition for C in T . Denote by T m2 the result of replacing T[C] in T m by T[Cm]. Then, T T m2 and ( m) = s (T m2). s T
The result of the method minimise(T[C]; T m) used in Algorithm 1 is calculated by checking the cases in De nition 4. Together with Theorem 2, we can establish the correctness of our method.
Theorem 3. For any acyclic E L ontology T , Algorithm 1 terminates and returns a minimal ontology T m such that T T m.
Example 5. We continue on the running example. As it turns out, (T2)[iBn2uB] = T1 is already minimal. To minimise T[B2uB], we note that Case 2 applies, since [B2 u B]T contains only one element. Based on the minimisation result in Example 1, we obtain the minimised partition fB2 u B v 9r:A3g. For [B3]T , the minimal set of required equivalent concepts is fB3; B4 u 9s:A1g. Case 4 applies, which means we have to encode remaining concept inclusions from S(B3)T2 into the equivalence axiom. The resulting minimised partition is fB3 B4 u 9s:A1 B4 u 9t:A2g. As a result, we obtain the following minimal ontology:
We implemented the method in Java, using the OWL API [
The computation of minimal equivalent concepts was the most expensive part of the minimisation. Note that for each concept, there are exponentially many rules of type (R3) in the subsumer grammar, which makes an exhaustive search impossible. We therefore used several optimisations. (1) We determine the order in which rules of type (R3) are tried using a best- rst strategy, where we evaluate rules based on (a) the conjunction length, (b) the size of the concepts corresponding to the non-terminals in the conjunction, and (c) the size of concepts subsuming these non-terminals. This way, we could reduce the number of entailment tests to 1 or 2 in most cases.Without a strategy like this, we were not able to compute minimal equivalent concepts in almost every case. (2) For large conjunctions, we tested whether certain conjuncts have to be included in every equivalent concept. For small concepts, this test is more expensive than just using a best- rst search as described above, but it enabled us to minimise large conjunctions, which is why we only used this optimisation for large concepts.
We evaluated our method on ontologies from the NCBO BioPortal
repository [
Table 5 shows the sizes, the percentage of E L-axioms, and the percentage of equivalence classes in the acyclic part of the input ontologies. The percentage of the size reduced by our method is shown in the column labelled MSize1. To compare against simple syntactic transformations, we modi ed the input ontologies by exhaustively applying the transformation C1 v C2; C1 v C3 ) C1 v C2 u C3. The di erence in size against these ontologies is shown in the column labelled MSize2. We were especially interested in how the amount of complex concepts changed. We therefore computed the sum of the sizes of complex concepts, as well as the sum of the sizes of existential role restrictions in each ontology. The reductions with respect to these measures are shown in the columns respectively labelled CSize and 9Size. The running times per ontology are shown in the last column. We see a signi cant reduction for all measures, especially for complex concepts and existential restrictions, whose accumulative size was reduced by respectively 14.17% and 25.82% on average in the BioPortal repository. Ontologies
Size
EL acyclic MSize1 MSize2 CSize
9Size Duration
BioPortal 58,943.8 92.1% 78.5% 12.96% 7.64% 14.17% 25.82%
Interpolants 2,192.4 79.8% 98.5% 31.50% 25.37% 48.78% 48.62%
Galen 13,625 95.72% 90.53% 19.05% 13.41% 21.11% 31.15%
Gene Ext. 162,950 100.0% 100.0% 31.65% 16.81% 19.68% 50.71%
NCI 267,916 94.7% 100.0% 13.45% 3.36% 7.24% 8.71%
SNOMED 444,473 100.0% 73.7% 23.11% 20.59% 26.04% 27.51%
The problem of minimising E L concepts was rst studied in [
We presented a method for minimising acyclic E L ontologies, which might provide great help in improving existing ontologies as well as for tools that generate ontology content. Key to our method is to structure the axioms in the ontology into partitions that can be minimised one after another following a implicability relation. Minimal axioms for each partition are computed by analysing inclusion relations between concepts that syntactically occur in the ontology, and making use of a method for minimising E L concepts with respect to an ontology. E L concepts are minimised using a technique based on regular tree grammars. An evaluation on realistic and generated ontologies showed that our method reduced the overall size as well as the complexity of ontologies signi cantly. An open question is how to deal with cyclic ontologies. Whereas our approach could be used to minimise existing partitions in cyclic ontologies, the main challenge for cyclic ontologies is that we have to determine partitions not present in the original ontology. Apart from cyclic E L ontologies, we are currently investigating methods for minimising concepts in more expressive description logics.