Introduction The design, maintenance, reuse, and integration of ontologies are highly complex tasks— especially for ontologies formulated in a logic-based language such as OWL. Like software engineers, “ontology engineers” need to be supported by tools and methodologies that help them to minimise the introduction of errors, i.e., to ensure that ontologies have appropriate consequences. In order to develop this support, important notions from software engineering, such as module, black-box behavior, and controlled interaction, need to be adapted so as to take into account the fact that an OWL ontology is, in essence, a logical theory; due to the expressive power of OWL, this turns out to be difficult.
In this paper, we focus on the use of modularity to support the partial reuse of ontologies. Given a foreign ontology from which we are reusing a set of symbols, our goal is to extract, from the foreign ontology, a small fragment that captures the meaning of the terms we use in our ontology. For example, when building an ontology describing research projects, we may use terms such as Cystic Fibrosis and Genetic Disorder in our descriptions of medical research projects. In order to improve the precision of our ontology, we may want to add more detail about the meaning of these terms; for reasons of cost and accuracy, we would prefer to do this by reusing information from a medical ontology. Such ontologies are, however, typically very large, and importing the whole ontology would make the consequences of the additional information costly to compute and difficult for our ontology engineers (who are not medical experts) to understand. Thus, in practice, we need to extract a (hopefully small) module that includes just the relevant information. More specifically, we will require that, when answering a query (expressed in a fixed query language) against our project ontology, importing the module would give us exactly the same answers as if we had imported the whole medical ontology. In this case, importing the module instead of the whole ontology will have no observable effect on our ontology.
In this paper, we propose a definition of a module Q1 within a given ontology Q
for a given vocabulary S. We show that, for OWL DL, which is a syntactical variant
of the Description Logic SHOIN , checking whether Q1 is a module in Q for S is an
undecidable problem. Given this negative result, we propose sufficient conditions for
Q1 to be a module in Q—that is, if Q1 satisfies our conditions then we can guarantee
that it is a module for S in Q, but not vice-versa. The conditions we present here are
based on the notion of syntactic locality, first introduced in [
Ontology of medical research projects P: P1 Genetic Disorder Project ≡ Project u ∃has Focus.Genetic Disorder P2 Cystic Fibrosis EUProject ≡ EUProject u ∃has Focus.Cystic Fibrosis P3 EUProject v Project
Ontology of medical terms Q: M1 Cystic Fibrosis ≡ Fibrosis u ∃located In.Pancreas u ∃has Origin.Genetic Origin M2 Genetic Fibrosis ≡ Fibrosis u ∃has Origin.Genetic Origin M3 Fibrosis u ∃located In.Pancreas v Genetic Fibrosis M4 Genetic Fibrosis v Genetic Disorder M5 DEFBI Gene v Immuno Protein Gene u ∃associated With.Cystic Fibrosis in polynomial time for OWL DL ontologies. We propose an algorithm for computing locality-based modules and present our experimental results on a set of real-world ontologies of varying size and complexity. We show that the modules we obtain are much smaller than the ones computed using existing techniques.
We refer the interested reader to the extended version of this paper [
Modules for Knowledge Reuse For exposition, suppose that an ontology engineer wants to build an ontology about research projects. The ontology defines different types of projects according to the research topics they focus on. Suppose that the ontology engineer defines two concepts Genetic Disorder Project and Cystic Fibrosis EUProject in his ontology P. The first one describes projects about genetic disorders; the second one describes European projects about cystic fibrosis, as given by the axioms P1 and P2 in Table 1.
The ontology engineer is an expert on research projects: he knows, for example, that an EUProject is a Project (axiom P3). He might be unfamiliar, however, with most of the topics the projects cover and, in particular, with the terms Cystic Fibrosis and Genetic Disorder mentioned in P1 and P2. In this case, he decides to reuse the knowledge about these subjects from a well-established and widely-used medical ontology.
The most straightforward way to reuse these concepts is to import the foreign medical ontology. This may be, however, a large ontology, which deals with other matters in which the ontology engineer is not interested, such as genes, anatomy, surgical techniques, etc. Ideally, one would like to extract a (hopefully small) fragment of the medical ontology—a module—that describes in detail the reused concepts. Intuitively, importing the module Q1 into P instead of the full ontology Q should have the same impact on the modeling of the ontology P as importing Q.
Continuing with the example, suppose that Cystic Fibrosis and Genetic Disorder are described in an ontology Q containing axioms M1-M5 in Table 1. If we include in the module Q1 just the axioms that mention Cystic Fibrosis or Genetic Disorder, namely M1, M4 and M5, we lose the following dependency: (1) (2)
The dependencies Cystic Fibrosis v Genetic Fibrosis v Genetic Disorder follow from axioms M1-M5, but not from M1, M4, M5, since the dependency Cystic Fibrosis v Genetic Fibrosis does not hold after removing M2 and M3 from Q. The dependency (1), however, is crucial for our ontology P as it (together with axiom P3) implies the following axiom:
This means that all the projects annotated with Cystic Fibrosis EUProject must be included in the answer for a query on Genetic Disorder Project. Importing a part of Q containing only axioms that mention the terms used in P instead of Q results in an underspecified ontology. We stress that the ontology engineer might be unaware of dependency (2), even though it concerns the concepts of his primary scope.
The example above suggests that the central requirement for a module Q1 ⊆ Q to be reused in our ontology P is that P ∪ Q1 should yield the same logical consequences in the vocabulary of P as P ∪ Q does. Furthermore, the fact that Q1 is a module in Q should be independent from the particular P under consideration—that is, if Q1 “behaves” in the same way as Q for a given ontology P but not for a different ontology P0, then Q1 should not be a module in Q. Based on this intuition, we can formalize the notion of a module as follows: Definition 1 (Module). Let Q1 ⊆ Q be two ontologies and S a signature. We say that Q1 is an S-module in Q w.r.t. an ontology language L, if for every ontology P and axiom α expressed in L with Sig(P) ∩ Sig(Q) ⊆ S and Sig(α) ⊆ Sig(P), we have that P ∪ Q |= α if and only if P ∪ Q1 |= α.
Definition 1 implies that, for any P, the axioms in Q excluded from the module Q1 do
not cause new consequences in P and therefore can be disregarded. In Definition 1 the
signature S acts as the interface signature between P and Q in the sense that it contains
the symbols that P and may share with Q. Unfortunately, it can be shown that, for
the description logic ALCO—the fragment of OWL DL that disallows transitive roles,
role hierarchies, inverse roles, and cardinality restrictions—checking whether Q1 is a
module in Q for S is an undecidable problem (see [
Theorem 1. Given a signature S, an ALC-ontology Q and an ALCO ontology Q1 ⊆ Q, it is undecidable whether Q1 is an S-module in Q w.r.t. L = ALCO. It is a consequence of this theorem that many relevant tasks, such as the extraction of minimal modules or the extraction of all the modules, cannot be algorithmically solved in OWL DL. Theorem 1, however, does not imply the impossibility of designing an algorithm for finding some (not necessarily minimal) modules. In particular, it is always possible to extract an S-module in Q since one can simply return Q which is always an S-module in Q. From a practical point of view, our goal is to find a procedure for computing “reasonably small” modules. Obviously, by Theorem 1, the set of all modules and the set of all minimal modules in Q for a given signature S cannot be computed using our procedure.
Modules Based on Locality Consider axiom M5 from Table 1. Suppose that we are given an interpretation IS for the vocabulary S = {Cystic Fibrosis}. Suppose that we define a new interpretation I by taking IS and interpreting the remaining symbols in M5, namely DEFB Gene, Inmuno Protein Gene and associated With as the empty set. It is not hard to see that I is a model of M5 regardless of the interpretation of Cystic Fibrosis. For module extraction, this means that M5 is irrelevant to the meaning of Cystic Fibrosis and hence this axiom need not be included in a module for this symbol.
This intuition can be used to define a particular kind of modules, which are based
on the notion of syntactic locality, first introduced in [
Definition 2 (Syntactic Locality for SHOIQ).
Let S be a signature. The following grammar recursively defines two sets of concepts CS⊥ and CS> for a signature S: CS⊥ ::= A⊥ | (¬C>) | (C u C⊥) | (∃R⊥.C) | (∃R.C⊥) | (> n R⊥.C) | (> n R.C⊥) . CS> ::= (¬C⊥) | (C1> u C2>) . where A⊥ ∈/ S is a atomic concept, R is a role, and C is a concept, C⊥ ∈ CS⊥, C(>i) ∈ CS>, i = 1, 2, and R⊥ ∈/ Rol(S) is a role.
An axiom α is syntactically local w.r.t. S if it is of one of the following forms: (1) R⊥ v R, or (2) Trans(R⊥), or (3) C⊥ v C or (4) C v C>. A SHOIQ ontology O is syntactically local w.r.t. S if all its axioms are syntactically local w.r.t. S. Intuitively, every concept in CS⊥ becomes equivalent to ⊥ if we replace every symbol A⊥ or R⊥ not in S with the bottom concept ⊥ and the empty role respectively, which are both interpreted as the empty set under every interpretation. Similarly, the concepts from CS> are equivalent to > under this replacement. Syntactically local axioms become tautologies after these replacements.
For example, the axiom M5 from Table 1 is local w.r.t. S = {Fibrosis, has Origin}: if we replace the remaining symbols in this axiom with ⊥, we obtain a tautology ⊥ ≡ ⊥: ⊥ ⊥ zDEFB}I| Gen{e ≡ Iznmuno P}ro|tein Gen{e u ∃ zassocia}te|d With{ .Cystic Fibrosis empty role Given a signature S and an ontology O, syntactic locality can be used as a sufficient condition for a fragment O1 ⊆ O to be an S-module in O, as given by the following proposition: Proposition 1. Let O1, O2 be SHOIQ ontologies and S a signature such that O2 is local w.r.t. S ∪ Sig(O1). Then O1 is an S-module in O1 ∪ O2.
Based on Proposition 1, we can define a particular modules that can be identified using locality: Definition 3 (Modules based on Locality Condition).
Given an ontology Q and a signature S, we say that Q1 ⊆ Q is a locality-based Smodule in Q if Q \ Q1 is local w.r.t S ∪ Sig(Q1).
Algorithm 1 extract module(Q, S) Input:
Q: ontology
S: signature Output:
Q1: a locality-based S-module in Q
For example, we have seen that axiom M5 is local w.r.t. Sig(Q1) with Q1 = {M1, . . . , M4}. Hence, according to Definition 3, Q1 is a locality-based S-module in Q for every S ⊆ Sig(Q1).
In order to construct a locality-based S-module in an ontology Q, it suffices to partition the ontology Q as Q = Q1 ∪ Q2 such that Q2 is local w.r.t. S ∪ Sig(Q1). Algorithm 1 outlines a simple procedure which performs this task. Assuming there is an effective locality test locality test(α, S), which returns true only for axioms α that are local w.r.t. S, the algorithm first initializes the partition to the trivial one: Q1 = ∅ and Q2 = Q, and then repeatedly moves to Q1 those axioms from Q2 that are not local w.r.t. S ∪ Sig(Q1) until no such axioms are left in Q2.
In Table 2 we provide a trace of Algorithm 1 for the input (Q, S), where Q consists of the axioms M1-M5 from Table 1 and S = {Cystic Fibrosis, Genetic Disorder}. Each row in the table corresponds to an iteration of the while loop in Algorithm 1. The
New elements in S ∪ Sig(Q1)
last column of the table provides the result of the locality test in line 4. It can be shown
[
Note that there is an implicit non-determinism in Algorithm 1, namely, in line 3 in
which an axiom from Q2 is selected. It might well be the case that several choices for
α are possible at this moment. For example, in Table 2 at step 2 we might have selected
axiom M3 instead of M2: It is possible to show (see [
In many Semantic Web applications, reuse often boils down to the following
highlevel task: given an atomic concept in the ontology that we want to borrow, provide the
axioms in the ontology that are relevant to its meaning. Consequently, it is interesting
loc for A in Q.
to determine the scope of a locality-based module Q{A}
Proposition 2. Let Q be ontology, A and B atomic concepts, and Ql{oAc} a
localitybased module in Q for S = {A}. Then, Q |= (A v B) iff Ql{oAc} |= (A v B).
Proposition 2 (see [
As an illustration, consider in Figure 1 the locality-based module for the atomic
concept DNA Structure in the NCI ontology, as obtained in SWOOP [
Related Work
The problem of extracting modular fragments of ontologies has recently been addressed
in [
In [
Our notion module is closely related to the notion of a conservative extension, which
has been recently investigated in the context of ontologies [
Evaluation Given an input ontology and an input signature, locality-based modules are not the only possible modules we can obtain. It remains to be shown that the locality-based modules obtained in realistic ontologies are small enough to be useful in practice.
Ontology
] Atomic A1: Prompt-Factor [
Concepts Max.(%)
Avg.(%)
Max.(%) Avg.(%) Max.(%) Avg.(%) NCI SNOMED GO SUMO GALEN-Small GALEN-Full SWEET DOLCE-Lite 27772 255318 22357 869 2749 24089 1816 499
For evaluation and comparison, we have implemented the following algorithms
using Manchester’s OWL API:1
A1: The PROMPT-FACTOR algorithm, as described in [
Complex. This group contains the well-known GALEN ontology (GALEN-Full),6 the DOLCE upper ontology (DOLCE-Lite),7 and NASA’s Semantic Web for Earth and Environmental Terminology (SWEET)8. These ontologies are complex since they use many constructors from OWL DL and/or include a significant number of general inclusion axioms and cyclic dependencies. In the case of GALEN, we have also considered a version GALEN-Small that has commonly been used as a benchmark for OWL reasoners. This ontology is almost 10 times smaller than the original GALEN-Full ontology, but it is similar in structure. 1 http://sourceforge.net/projects/owlapi 2 http://www.mindswap.org/2003/CancerOntology/nciOncology.owl 3 http://ontology.teknowledge.com/ 4 http://www.geneontology.org 5 http://www.snomed.org 6 http://www.openclinical.org/prj galen.html 7 http://www.loa-cnr.it/DOLCE.html 8 http://sweet.jpl.nasa.gov/ontology/ (a)(aM) oMduoldaurliazraitziaotnioonf oNfCNICI
(b)(bM) oMduoldaurliazraitziaotnioonf oGfAGLAELNE-NSm-Samllall (c)(cM) oMduoldaurliazraitziaotnioonf oSfNSONMOEMDED (d)(dM) oMdouldaurliazraitziaotnioonf oGfAGLAELNE-NFu-Fllull
For each of these ontologies, and for each atomic concept in their signature, we have extracted the corresponding modules using algorithms A1-A3 and measured their size. We use modules for single atomic concepts to get an idea of the typical size of locality-based modules compared to the size of the whole ontology.
The results we have obtained are summarized in Table 3. The table provides the size of the largest module and the average size of the modules obtained using each of these algorithms. In the table, we can clearly see that locality-based modules are significantly smaller than the ones obtained using the other methods; in particular, in the case of SUMO, DOLCE, GALEN and SNOMED, the algorithms A1 and A2 retrieve the whole ontology as the module for each atomic concept. In contrast, the modules we obtain using our algorithm are significantly smaller than the size of the input ontology. In fact, our modules are not only smaller, but are also strict subsets of the respective modules computed using A1 and A2.
For NCI, SNOMED, GO and SUMO, we have obtained very small locality-based modules. This can be explained by the fact that these ontologies, even if large, are simple in structure and logical expressivity. For example, in SNOMED, the largest localitybased module obtained is approximately 1/10000 of the size of the ontology, and the average size of the modules is 1/10 of the size of the largest module. In fact, most of the modules we have obtained for these ontologies contain less than 40 atomic concepts.
For GALEN, SWEET and DOLCE, the locality-based modules are larger. Indeed, the largest module in GALEN-Small is 1/10 of the size of the ontology, as opposed to 1/10000 in the case of SNOMED. For DOLCE, the modules are even bigger—1/3 of the size of the ontology—which indicates that, either the dependencies between the different concepts in the ontology are very strong and complicated and thus actual minimal modules are big themselves, or that no small locality-based modules exist. The SWEET ontology is an exception: even though the ontology uses most of the constructors available in OWL, the ontology is heavily underspecified, which yields small modules.
In Figure 2, we have presented a more detailed analysis of the modules for each concept name in NCI, SNOMED, GALEN-Small and GALEN-Full. Here, the X-axis represents the size ranges of the obtained modules and the Y-axis the number of modules whose size is within the given range. The plots thus give an idea of the distribution for the sizes of the modules.
For SNOMED, NCI and GALEN-Small, we can observe that the size of the modules follows a smooth distribution. In contrast, for GALEN-Full, we have obtained a many small modules and many big ones, but no medium-sized modules in-between. This abrupt distribution indicates the presence of a big cycle of dependencies in the ontology, which involves all the concepts with large modules.