Choosing ontologies for reuse

Abstract

The task of designing an ontology through reuse is difficult, and a major challenge in this effort is choosing between different ontologies that are candidates for reuse. To address this challenge, we introduce a notion of preference between ontologies and provide a definition that allows the developer to make a well-founded comparison across a set of ontologies, with respect to their semantic requirements. The preference between ontologies is based on an assessment of relative accuracy and precision, which are also defined here. These concepts formalize the underlying intuitions related to the different possible outcomes in the assessment of an ontology against a developer’s semantic requirements. We also present a procedure to demonstrate the viability of the definition of preference, resulting in a novel approach to the choice between ontologies for reuse; it is sufficiently well-defined such that it could provide the basis for tool support to assist in this task. By providing ontology developers with a means of effectively comparing different ontologies for reuse, this work addresses several of the key limitations for ontology reuse, as identified by the 2014 Ontology Summit Communiqué (Obrst et al., 2014, pp. 155–170).

Keywords

Ontology reuse requirements design first-order logic competency questions

1. Introduction

The inherent reusability and shareability of ontologies makes them particularly appropriate tools for Semantic Web applications. Apart from the usual development-related motivations, reuse is the key to supporting shareability between ontologies. When an ontology from one application is reused in another, shareability and interoperability between the applications results naturally, thereby eliminating the need for cross-application mappings and integration. Part of the case for ontologies is that they provide a method for knowledge representation that is shareable and reusable. Unfortunately, as recognized in the 2014 Ontology Summit Communiqué (Obrst et al., 2014), reuse is currently not a common means of ontology design. This lack of reuse presents a serious problem to the ontology community as it translates directly to a lack of demonstration these supposed benefits of ontologies.

In this paper we introduce a novel definition to formalize a notion of preference that may be used to inform the choice between different ontologies that are candidates for reuse. We illustrate its viability by way of a set of procedures that dictate how the definition may be implemented, resulting in a new approach to the comparison of ontologies. Given the difficult nature of choosing which ontology to use, it is not surprising to find that many of the limitations identified in the 2014 Ontology Summit Communiqué are in fact tied to this task. Consequently, by resolving challenges associated with the choice between ontologies this work addresses many of the key limitations of reuse identified by the summit.

In the Communiqué, the challenges identified during the Summit were consolidated into seven limitations for reuse. Of particular interest for this work are the following:

Mismatches and Misunderstandings

Ontology reuse sometimes fails because the developer misunderstands and attempts to reuse an ontology that is not suitable. This can sometimes result due to a mismatch between the meaning the developer perceives from the name of a concept, and its actual meaning resulting from the ontology’s axioms.

Finding Mr. Right Ontology

Simply finding the right ontology poses a challenge. The Communiqué discusses the need for useful metadata to assist in the identification of an ontology that matches the user’s requirements, beyond simply looking at traditional keyword search (semantic-oriented criteria such as provenance and competency questions, for example).

This Ontology Doesn’t Fit…

It’s possible for an ontology to be appropriate, while not directly reusable. In some cases an ontology may satisfy the requirements, if some issue(s) are corrected. For example, the ontology might be missing some semantics, a particular concept, or perhaps it is not formalized in the desired language. To better take advantage of existing ontologies, developers must be able to determine what parts of an ontology, or what modifications may be required to satisfy their requirements.

Just Do It Yourself

Due to the work required to find and understand existing ontologies, reuse may sometimes not be seen as a viable option. The Communiqué discusses that the barriers and bottlenecks apply to both reuse and traditional development, and note that reuse is a potential cost-saver. However, this is only true so long as it does not bring its own additional instances of these barriers and bottlenecks to the process.

We address the challenge of mismatches and misunderstandings by employing the already accepted and understood technique of competency questions (CQs) for requirements specification. We leverage CQs as a means of both identifying and assessing ontologies for reuse, such that the elimination of inappropriate ontologies is straightforward. The use of CQs here is also aligned with the best practices advised by the Communiqué.

Finding Mr. Right Ontology is a broad challenge including community-wide issues of metadata and infrastructure. While these are out of the scope of this work, we address this issue in part by identifying a rationally-motivated approach for the identification of ontologies for reuse, which describes how the search for ontologies may be reduced to a single criterion. We also discuss the range of different possible implementations of such an approach. Further, when given a set of ontologies, finding the ‘right’ one will be facilitated by the assessment of preference as defined here.

This work also accounts for the goldilocks problem of This Ontology Doesn’t Fit… described in the Communiqué. The approach to choosing between ontologies assumes that some changes may need to be made in order to reuse a particular ontology. The notion of preference provides a means of accounting for this through a formal assessment of which ontologies will be ‘easier’ to reuse. This also helps to mitigate the Just Do It Yourself issue. This approach to choosing an ontology reduces the amount of effort required to understand and assess preference between candidates. With this assistance in choosing between ontologies we can mitigate cases where the decision to design from scratch (“do it yourself”) is made simply to avoid the effort required to make an informed choice between the alternative ontologies.

2. Related work

The challenge of choosing between candidate ontologies is in itself, not novel. Much existing work has recognized the challenge of making a well-informed choice with a reasonable amount of effort, and attempted to design a solution. However, no work to date has been presented that addresses the challenge of assessing the candidates’ semantics. Whether implemented as a tool or presented as a guideline, the majority of existing work employs some sort of calculation over a set of subjectively-weighted criteria (Fernandez et al., 2006; Fernández-López et al., 2012; Lozano-Tello and Gómez-Pérez, 2004). While this may be a useful indication for some requirements, these approaches are too superficial to account for the candidates’ semantics. An ontology should not necessarily be preferred over another simply because it satisfies more requirements – such an assessment requires a deeper consideration. In contrast, the approach specified by Pinto and Martins (2001) gives the ontologies’ content a more thorough consideration. Unfortunately, this is labour-intensive, requiring considerable input from subject-matter experts and ontologists, and so it does not address the other half of the issue: the effort required for the comparison. Further, with a lack of formal definitions the methodology is not defined in sufficient detail to be easily reproduced.

On the subject of related work, it is worthwhile to note that the topic of ontology matching is conceptually related to this subject, as it also involves a comparison between ontologies. Whereas Euzenat et al. (2007) describes matching as being aimed at finding “correspondences between semantically related entities of ontologies”, this work is considerably different as we are attempting to compare candidate ontologies, with respect to some required semantics.

3. Scope

With respect to the entire ontology development process, this work is restricted to reuse, which we view as a specialization of axiom design. More specifically, this work focuses on supporting the task of choosing which ontology to reuse, with respect to the developer’s required semantics. Naturally, this problem also requires consideration of how these candidate ontologies are found; we term these tasks Choice and Search, respectively. In the following subsections we describe the informal intuitions of both tasks in order to more precisely define the scope of this work.

It is well accepted that design occurs after (possibly in a feedback loop with) the tasks of analysis and requirements specification. Consequently, aspects of analysis wherein the designer identifies the required signature and set of intended models for his/her conceptualization are outside of the scope of this work. However, it is important to clarify that the validity of this contribution does not depend on a complete set of intended models being known. While the definition of ontology preference is necessarily based upon a known (and shared) signature and set of intended models, whether or not (or to what degree) these models are known in practice is a matter for implementation. To this end, we devote an entire section to viability where we address this and other pragmatic concerns, such as assessment of preference between ontologies with varied signatures.

This work also makes several assumptions about the available infrastructure – primarily that the available ontologies are consistent and modular. While this may not be representative of the current state of practice, it is feasible and aligned with already recognized best practices. It is our hope that this work should serve as motivation for such infrastructure improvements, however in general the infrastructure itself is out of the scope of this work.

3.1. Search intuitions

Given a set of requirements, there may be a number of aspects that we would like to incorporate in our search against some repository(s). Consider the task of search independent of existing and proposed approaches: we have access to some collection (physical or otherwise) of ontologies; we also have access to the specification of requirements; we review these requirements and “keep them in mind” while sorting through the collection of ontologies, pulling out any that seem as though they might be related. This selection might be done based on a ontology’s title, some grouping that it is stored under, or perhaps a closer examination of its documentation or concepts.

This basic intuition behind the task of Search is also quite similar to that of using search engines on the web: given some criteria (e.g. keywords) the aim is to return a set of relevant results. With each ontology returned by the search process, a conjecture of relevance is implicitly being made. We might select a particular ontology for further consideration because we conjecture that (some of) its axioms could be used to satisfy (some of) the requirements. Naturally, the goal is not to return just any set of relevant ontologies – the familiar aims of high precision and recall apply here as well.

We consider the task of Search insofar as how it is structured and what the input and output should be. We do not aim to propose a single solution for Search, but to consider generically how the ontologies that are to be compared are found.

3.2. Choice intuitions

The task of choice is complex; it requires the consideration and assessment of a variety of objective and subjective requirements – criteria that often have interdependencies as well as individual, implicit and explicit priorities. Independent of any particular methodology, the task of choice can be described as follows: given some set of potentially relevant ontologies, the developer must choose which is the ‘best’ with respect to some explicit and/or implicit requirements. Owing to the aforementioned variety of potential requirements, the precise interpretation of what it means to be the ‘best’ is unclear. Intuitively though, in the context of reuse the ‘best’ choice is the one that requires the least effort in order to satisfy the developer’s requirements. While other requirements oriented to ontology qualities such as representation languages and evaluation results will certainly have an impact on the final choice of ontology, these factors are not in the scope of this work. This approach is restricted to consider only the semantic requirements. Therefore, while we cannot claim to provide a complete solution to the task of choice, this work does serve to provide a critical input to the decision-making process.

4. Background

Here we review the technical concepts that play a role in the definition and techniques that follow.

4.1. Competency questions as semantic requirements

The requirements for a semantically correct ontology may be defined using the relationship between the intended models for the ontology, and the actual models of its axiomatization (see Fig. 1). A theory is a set of first-order sentences closed under logical entailment. and within this paper, use the words ‘ontology’ and ‘theory’ interchangeably.1

¹
Note that we do not claim an arbitrary theory to be the definition of an ontology. Indeed, an ontology is not just an arbitrary logical theory, but rather a particular logical theory aiming at characterising people’s assumptions about the nature and structure of a domain, and the intended meaning of terms used to talk about such domain. However, for the purposes of this paper, it is enough to assume that an ontology is a logical theory.

$Mod (T)$ denotes the class of all models of an ontology T. The signature $σ (T)$ of an ontology T is the set of all nonlogical symbols that appear in T.

Definition 1.

An axiomatization $T_{onto}$ for an elementary class of structures $M^{intended}$ is semantically correct if and only if for any structure $M$ , where $M \in Mod (T_{onto})$ iff $M \in M^{intended}$ .

In other words, an axiomatization is semantically correct if and only if it does not include any unintended models, and it does not omit any intended models.

Recall that a class of structures is elementary iff it is first-order axiomatizable, so with the above notion of correctness used in this paper, we are restricting our attention to applications in which the intended models of the ontologies are axiomatizable in first-order logic. We are not considering classes of intended structures such as connected graphs or the standard model of Peano Arithmetic, which are not first-order axiomatizable.

Fig. 1.

The relationship between intended models for an ontology and the models of the ontology’s axioms (from (Guarino, Oberle & Staab, 2009)).

Formally, the potential semantic errors that prevent an ontology from being semantically correct are defined as follows:

Definition 2.

An error of superfluous models is present in the ontology $T_{onto}$ if and only if there exists a structure $M$ such that $M \in Mod (T_{onto})$ and $M \notin M^{intended}$ .

Following from Definition 2, we can define the class of superfluous models $SUP (T)$ of a candidate theory T.

Definition 3.

$\begin{matrix} M \in SUP (T) ⟺ M \in Mod (T), M \notin M^{intended} . \end{matrix}$

In other words, a superfluous model of T is one which is not in the class of intended structures.

A second potential semantic error considers structures which are intended, yet which are not models of the ontology.

Definition 4.

An error of model omission is present in the ontology $T_{onto}$ if and only if there exists a structure $M$ such that $M \in M^{intended}$ and $M \notin Mod (T_{onto})$ .

Following from Definition 4, we can define the class of omitted models $OM (T)$ of a candidate theory T.

Definition 5.

$\begin{matrix} M \in OM (T) ⟺ M \notin Mod (T), M \in M^{intended} . \end{matrix}$

Competency questions (CQs) are a well-accepted means of requirements specification for ontologies (Grüninger and Fox, 1995, 1994; Uschold and Grüninger, 1996); they represent sentences that the ontology should be able to entail, thus they indirectly impose requirements on both the scope of an ontology’s concepts and its semantics. For example, when specifying the requirements for a time ontology, we might have a CQ such as: (CQ-1) ‘is there some time interval that contains a unique timepoint?’, or (CQ-2) ‘is there some timepoint that cannot be contained by any interval?’ If we were developing an ontology for a more general application, perhaps we might have something like: (CQ-3) ‘is there some process that can only occur at a single timepoint?’. Recent work interprets CQs more specifically as semantic requirements and provides a methodology for their evaluation with the use of an automated theorem prover in the process of ontology development (Katsumi and Grüninger, 2010). The evaluation of these entailment problems requires the CQs to be encoded in a chosen logical language and vocabulary, for example CQ-1 might become: $\begin{array}{l} (\exists x) (\forall t_{1}, t_{2}) interval (x) \land timepoint (t_{1}) \land timepoint (t_{2}) \\ \land t_{1} = beginof (x) \land t_{2} = endof (x) \supset (t_{1} = t_{2}) . \end{array}$ At the core of this use of CQs is the relationship between the consequent of the entailment problem, and the models of the axiomatization.

4.2. Hierarchies and root theories

We adopt the concept of a hierarchy from the COLORE repository, where it is presented as a means of storing similar ontologies (Grüninger et al., 2012). Formally:

Definition 6.
A hierarchy $H = ⟨ H, ⩽ ⟩$ is a partially ordered, finite set of theories $H = T_{1}, \dots, T_{n}$ such that:
$σ (T_{i}) = σ (T_{j})$ , for all i, j;

$T_{1} ⩽ T_{2}$ iff $T_{2}$ is an extension of $T_{1}$ ;

$T_{1} < T_{2}$ iff $T_{2}$ is a non-conservative extension of $T_{1}$ .
The Root Theory, $T_{root}$ of $H$ is a minimal theory in the hierarchy.

We make reference to these COLORE-specific concepts in the procedures only because they are convenient for the presentation of this work. It is important to note that the contributions presented here are independent of any particular repository or other approach to the search for candidate ontologies. The hierarchy is utilized as a construct to provide a common basis for organizing and assessing the candidates in cases where the scope of the concepts in the CQs and the candidates are not completely in-line with one another. For instance, the scope of CQ-3 includes not only time but also the concept of an event, even though it was a requirement for a time ontology. It is therefore quite possible that in this case the candidates might include both time and event ontologies. The notion of a hierarchy provides a common context to allow for the collective consideration of candidates with varying scopes that may not precisely correspond to that of the CQs.
4.3. Interpretations and signature translations

Essentially, in a signature translation we map the concepts (signature) from one theory into the language of another. This is closely aligned to the definition of an interpretation from a language into a theory as specified by Enderton (1972). The key difference in our notion of signature translations is that we do not require them to be complete (whereas the language interpretation by Enderton specifies a mapping on the whole language). For our purposes the mapping of even a single term in a language is of interest and thus a signature translation is defined as an extended notion of language interpretation.

Definition 7.
An interpretation π of the theory $T_{1}$ with signature $σ (T_{1})$ into a theory $T_{2}^{'}$ with signature $σ (T_{2}^{'})$ is a function on the set of non-logical symbols of $σ (T_{1})$ and formulae in the language $L (T_{1})$ such that
π assigns to ∀ a formula $π_{\forall}$ of $σ (T_{2}^{'})$ in which at most the variable $v_{1}$ occurs free, such that $T_{2}^{'} ⊧ (\exists v_{1}) π_{\forall}$ ;

π assigns to each n-place relation symbol P a formula $π_{P}$ of $Σ (T_{2}^{'})$ in which at most the variables $v_{1}, \dots, v_{n}$ occur free;

for any atomic sentence $Σ \in σ (T_{1})$ with relation symbol P, $π (Σ) = π (P)$ ;

for any sentence $Σ \in σ (T_{1})$ , $\begin{matrix} π (\neg Σ) = \neg π (Σ); \end{matrix}$

for any sentences $Σ, τ \in σ (T_{1})$ , $\begin{matrix} π (Σ \supset τ) = π (Σ) \supset π (τ); \end{matrix}$

for any sentence $Σ \in σ (T_{1})$ , $\begin{matrix} π (\forall x Σ) = \forall x π_{\forall} \supset π (Σ); \end{matrix}$

For any sentence $Σ \in σ (T_{1})$ , $T_{1} ⊧ Σ \Rightarrow T_{2}^{'} ⊧ π (Σ)$ .

Definition 8.
Given some theory, $T_{1}$ , in signature $σ (T_{1})$ and some theory $T_{2}$ in a (possibly partially or completely different) signature $σ (T_{2})$ , a signature translation of $T_{1}$ with signature $σ (T_{1})$ into $σ (T_{2})$ is an interpretation π of $T_{1}$ into a subtheory of $T_{2}$ , $T_{2}^{'} \subseteq T_{2}$ .

5. Finding ontologies

Recall that the basic intuition of Search can be described as follows: given some specification of requirements, the developer is tasked with collecting a set of relevant candidate ontologies. There are two variables of this task that affect how it is performed:

the criteria employed in the collection process, and

the source(s) being searched.

In other words, the two key aspects are where the developer looks and how they look. Once the requirements have been specified, the search criteria can be extracted and applied to retrieve a set of candidates in a completely objective manner.

5.1. Search criteria

Any theory that is selected as a candidate ontology by the search criteria essentially corresponds to one or more conjectures of relevance. For example, if I select a particular ontology, $T_{A}$ from my collection of ontologies, I am doing so because I believe it is relevant, that it ‘matches’ some part of my requirements in some way; I am implicitly conjecturing that $T_{A}$ is relevant to the aspect(s) of the requirements where I perceived a match. In the context of ontology development various types of requirements may be specified, however relevance is a requirement on content and therefore for the purposes of search we are concerned only with the content-specific (semantic) requirements. The developer uses these to (manually or otherwise) sort through the collection of ontologies and arrive at a set of conjectures of which ontologies are relevant candidates and how.

If a theory is relevant, we should be able to describe the way in which its content corresponds (i.e. maps) to our requirements. In other words, if a theory is relevant, it must be interpreted by some subtheory of the semantic requirements; if not, then we can conclude that it is irrelevant with respect to the requirements we have specified. We can formally describe a conjecture of relevance as a translation definition(s) from the candidate’s own signature to the signature of $T_{R}$ . These definitions are conjectures that a theory is interpreted by some part(s) of the requirements.

It follows that the criteria for Search may be formalized simply as the signature of $T_{R}$ ; a theory is retrieved as a candidate if a mapping(s) to the signature of $T_{R}$ (recall, this is denoted $σ (T_{R})$ ) may be conjectured. Each candidate comprises not only the ontology but the conjecture(s) of its relevance via a set of translation definitions that maps (a subset of) the signature of the candidate to (a subset of) the signature of the requirements. Note that it is in fact possible to derive multiple candidates from the same ontology by making multiple different conjectures of relevance, (i.e. different sets of translation definitions for $T_{R}$ ).

In order for an ontology to be a candidate it must have at least one conjectured mapping (translation definition) to the signature of the set of semantic requirements. The current approach to search does this implicitly; when searching through a repository for ontologies with some keyword (presumably an important concept in the ontology), the results are essentially a set of alternative ontologies with a single direct mapping to the keyword.

While keyword search in itself is straightforward, to use this technique for the retrieval of relevant ontologies with high precision and recall is extremely cumbersome to do well. In most cases it is not feasible to completely specify an accurate condition for relevance with a single term. Even in a specialized domain, there is the possibility for morphemes and synonyms to come into play. Often times there may be many relevant concepts as the requirements may cover several domains. To perform all necessary searches and aggregate the results requires considerable effort on the part of the developer. A procedure to perform this task would mean that it could be offloaded (potentially automated) in its entirety and thus completely removed from the workload of the developer.

Not only is such a procedure feasible, but there is a range of possible implementations – varying with respect to how the conjectures are identified. For each alternative, we could specify a different procedure, and for each such procedure we could prove its correctness and completeness (with respect to a given repository), relative to the specification of the conjecture type. However, as each candidate output by search is simply, by definition, a conjecture of a potentially relevant theory, it makes no sense to discuss the correctness or completeness of the output in the absolute sense. How then, do we know what these alternative means of conjecture specification are, and how can we decide which of these is best? Again, we emphasize that this is an implementation decision. It is a heuristic to be defined that has no bearing on any of the formal definitions or subsequent procedures we specify; it is a decision based on consideration of the trade-off between exhaustivity and efficiency in the search for candidates.

The following is an example of an implementation with a simple heuristic for generating candidates. For each ontology ( $T_{C}$ ) in each input source ( $R_{j}$ ), this procedure searches only for term matches based on the signature of the semantic requirements – in other words it only generates candidates with one-to-one translation definitions between terms in the signature of $T_{R}$ and terms in the candidate’s signature. A candidate is conjectured only when there is a direct match in both the term name and its arity. This is formalized as follows in Procedure 1.

Procedure 1

An example of candidate retrieval

Clearly this example procedure could result in the omission of potentially relevant candidates in some cases – however, there may also be scenarios in development via reuse when the desired signature is known and thus this would be sufficient. A more thorough approach to develop conjectures might look beyond basic matches to include synonyms and morphemes. We could even look at candidates outside of the context of our requirements and conjecture mappings simply based on term arity matches, (this might lead to reuse scenarios similar to the work presented by Grüninger and Katsumi (2012), where the same ontology is reused in a variety of domains).

Translation definitions need not be restricted to one-to-one term mapping. There are many different approaches that might be incorporated to identify possible sentences that might be used to define terms in the candidate’s signature. For example, while a candidate may not possess a relevant concept of mother explicitly in its theory, we may make the conjecture that the candidate’s concept of a woman who has a child is in fact relevant (equivalent) to the concept of mother. At the most thorough end of the spectrum, we find an approach with a procedure that may not terminate. In such an approach, for each term in $T_{R}$ and for each theory in the repository we consider all possible sentences in the language of the ontology as translation definitions for different possible candidate conjectures.

This second approach is clearly not a reasonable one; it illustrates that there is a balance that should be found between exhaustiveness and practicality. Yet we need not sacrifice rigour for efficiency; there are certainly opportunities to implement clever ways of generating good, thorough conjectures. For example, we could implement some type of learning from previous users’ translation definitions; we could leverage relationships between theories to make additional conjectures; we could apply a relatively basic conjecture generation approach with an option for user-override to allow for additional conjectures the user may want to test out.

5.2. The design of conjecture generation

There are countless approaches to conjecture generation that could be implemented in a procedure for search. While there is no single correct procedure, there will certainly be some methods that will be better than others, and perhaps some more appropriate in different contexts. What is important is that some effort is made to design a heuristic that will provide a useful, thorough set of candidates. While the recall of a procedure will be limited by certain feasibility considerations, it is high recall that will contribute to the objective of increased reuse benefits by minimizing the opportunity for the omission of candidates with the potential to facilitate these benefits. Finally, it is important to note that the possible conjecture criteria implementations are also dictated by the sources used. For example, to implement a procedure that retrieves additional conjectures based on mappings between ontologies would require the use of a source(s) that provides this information. Regardless of the approach taken to identify the candidate ontologies, modularity is a critical factor for the feasibility of the subsequent solutions. Given the size and breadth of scope of some ontologies it is crucial that the search return only the relevant modules, rather than the entire theory.

6. Choosing between ontologies

By allowing the developer to capture their desired scope of concepts and semantics, CQs play a vital role in ontology development. It follows that they should also be a key consideration when comparing candidate ontologies in the task of reuse. However, the application of CQ evaluation to assess preference between candidates is not straightforward. We cannot simply compare the number of CQs satisfied; for example, what if one candidate satisfies more requirements than some alternative, while in fact requiring more extensive modification to meet all of the requirements? Or, what if two candidates satisfy the same number, but different sets, of the CQs – should they be considered comparable? Clearly more knowledge is required in order to make an accurate assessment.

In the context of reuse, superfluous models correspond to a semantic error where some aspect of the candidate is weaker than required. Such models satisfy the candidate, but are not models of the requirements. Such models will prevent some aspect of the requirements from being satisfied (i.e. some competency questions will not be provable) and so the theory must be strengthened if the designer wishes to reuse it.

Omitted models on the other hand, indicate a semantic error where the theory is stronger than is required. These are intended models of the requirements that are not entailed by the candidate ontology. In such cases the candidate has consequences beyond what was specified in the requirements; the designer may therefore need to weaken the axioms so as to include the otherwise omitted models which they have deemed necessary.

Recall from Section 4.1 that at the core of the specification of semantic requirements is the relationship between the consequent of the entailment problem, and the models of the axiomatization. Building on our understanding of semantic requirements, we will formally define a notion of preference between candidate ontologies that will serve to inform our decision. Such a definition would allow for the production of unambiguous, verifiable results about the candidates. Most importantly, it would simplify the task of performing a thorough comparison, thereby reducing the investment required to obtain a deep understanding of how the candidates compare to each other, with respect to the desired ontology.

6.1. Preference defined

In general, any notion of preference between candidates should address the question of which ontology is the closest match to the requirements. The underlying motivation of this being that the closer a candidate is to the requirements, the less development work will be required to achieve the desired ontology via reuse. In the context of semantic requirements, the consideration of which semantic requirements are and are not satisfied provides an indication of the effort that will be required in each case to “bridge the gap” to obtain the desired ontology, should a particular candidate be chosen for reuse. We formalize the concept of preference as the comparative effort required between two candidates, relative to the set of semantic requirements.

The concept of preference is comprised of two complementary perspectives that capture the relative effort required to achieve the desired ontology: candidate accuracy and precision. Intuitively, an ontology that is more accurate or more precise with respect to the models of the desired ontology will be preferred over other candidates; its reuse will require less effort as there are fewer corrections to be made. Both of these perspectives are expressed (naturally) as orderings, and are based on the possible models of the candidates, and the identification of semantic errors, as described in the previous section. The orderings derived from these models represent a three-way relationship between theories – a comparison of two candidate theories, relative to the requirements.

The Accuracy Ordering captures the notion of required effort by extending the notion of semantic correctness discussed in the previous section; a candidate requires less effort if it is more correct than another, as fewer changes and corrections will need to be made in order to reuse it.

Definition 9.
Candidate ontology $T_{2}$ is more accurate than candidate ontology $T_{1}$ (denoted by $T_{1} ⪯ T_{2}$ ) iff $\begin{matrix} (1) & SUP (T_{2}) \subseteq SUP (T_{1}), OM (T_{2}) \subseteq OM (T_{1}) . \end{matrix}$

If one candidate has fewer omitted and fewer superfluous models than another, it is clearly the more accurate candidate. In cases where one candidate does not have both fewer superfluous and omitted models than another, they are incomparable in the Accuracy Ordering. This is a necessary limitation because there is no means of comparing a combination of omitted and superfluous models in general.
Lemma 1.
Candidate ontology $T_{1}$ is more accurate than candidate ontology $T_{2}$ and candidate ontology $T_{2}$ is more accurate than candidate ontology $T_{1}$ iff they are logically equivalent.
Proof.
Candidate ontology $T_{1}$ is more accurate than candidate ontology $T_{2}$ and candidate ontology $T_{2}$ is more accurate than candidate ontology $T_{1}$ iff $\begin{matrix} SUP (T_{2}) = SUP (T_{1}), OM (T_{2}) = OM (T_{1}) . \end{matrix}$ By the definition of superfluous models, $M \in Mod (T_{2})$ and $M \notin M^{intended}$ iff $M \in Mod (T_{1})$ and $M \notin M^{intended}$ , so that if $M \notin M^{intended}$ , we have $M \in Mod (T_{2})$ iff $M \in Mod (T_{1})$ .

By the definition of omitted models, $M \notin Mod (T_{2})$ and $M \in M^{intended}$ iff $M \notin Mod (T_{1})$ and $M \in M^{intended}$ , so that if $M \in M^{intended}$ , we have $M \in Mod (T_{2})$ iff $M \in Mod (T_{1})$ .

Combining these cases give us $M \in Mod (T_{1})$ iff $M \in Mod (T_{2})$ . □

In this special case of accuracy, we will say that $T_{1}$ and $T_{2}$ are equally accurate, denoted $T_{1} =_{≺} T_{2}$ .
Lemma 2.
Let $T$ be a set of candidate ontologies.

$⟨ T, ⪯ ⟩$ is a partial ordering.
Proof.
If $T_{1} ⪯ T_{2}$ and $T_{2} ⪯ T_{3}$ , then $\begin{array}{l} SUP (T_{2}) \subseteq SUP (T_{1}), OM (T_{2}) \subseteq OM (T_{1}), \\ SUP (T_{3}) \subseteq SUP (T_{2}), OM (T_{3}) \subseteq OM (T_{2}) \end{array}$ and hence $\begin{matrix} SUP (T_{3}) \subseteq SUP (T_{1}), OM (T_{3}) \subseteq OM (T_{1}) \end{matrix}$ so that $T_{1} ⪯ T_{3}$ . Therefore ⪯ is transitive.

$T_{1} ⪯ T_{1}$ since $SUP (T_{1}) = SUP (T_{1})$ , $OM (T_{1}) = OM (T_{1})$ . Therefore ⪯ is reflexive.

If $T_{1} ⪯ T_{2}$ and $T_{2} ⪯ T_{1}$ , then $\begin{array}{l} SUP (T_{2}) \subseteq SUP (T_{1}), OM (T_{2}) \subseteq OM (T_{1}), \\ SUP (T_{1}) \subseteq SUP (T_{2}), OM (T_{1}) \subseteq OM (T_{2}) \end{array}$ and hence $\begin{matrix} SUP (T_{2}) = SUP (T_{1}), OM (T_{2}) = OM (T_{1}) \end{matrix}$ and $T_{1}$ and $T_{2}$ are equally accurate, and hence logically equivalent. Therefore ⪯ is antisymmetric.

Since ⪯ is transitive, reflexive, and antisymmetric, it is a partial ordering. □

The Precision Ordering is motivated by the distinction between omitted and superfluous models – it addresses a special case in which candidates are not comparable in the Accuracy Ordering, but one should still be preferred over the other. Informally, this preference can be motivated by the observation that whether choosing an ontology for reuse or developing one from scratch, it is far easier to identify and address errors of omitted models than superfluous models. The omitted models are clearly present in the requirements theory, and the cause of their omission is unambiguously present in the theory itself. It is fairly straightforward then, to identify which axioms are causing the omission of certain models from the candidate theory (then, as part of design determine which axioms to change and how). The resolution for superfluous models on the other hand, is much less clear. Even once they are identified, the task of designing an axiom to eliminate them is more challenging as the possibilities and their implications may be complex and difficult to recognize. The Precision Ordering is defined as follows:
Definition 10.
Candidate ontology $T_{2}$ is more precise than candidate ontology $T_{1}$ (denoted by $T_{1} ⊲ T_{2}$ ) iff $\begin{matrix} (2) & SUP (T_{1}) \neq \emptyset, SUP (T_{2}) = \emptyset . \end{matrix}$
Lemma 3.
Let $T$ be a set of candidate ontologies.

$⟨ T, ⊲ ⟩$ is a strict ordering.
Proof.
If $T_{1} ⊲ T_{1}$ , then $SUP (T_{1}) \neq \emptyset$ and $SUP (T_{1}) = \emptyset$ , so ⊲ must be irreflexive.

Similarly, $T_{1} ⊲ T_{2}$ and $T_{2} ⊲ T_{1}$ leads to a contradiction, and ⊲ is asymmetric.

Transitivity is trivially satisfied, since we cannot have both $T_{1} ⊲ T_{2}$ and $T_{2} ⊲ T_{3}$ . □

This second ordering may be less intuitive than the first as it strictly prefers candidates with no superfluous models, regardless of the differences in omitted models. However, when this condition is satisfied, the relationship between the candidates’ omitted models is irrelevant to the preference between candidates. In contrast to superfluous models, omitted models affect only the completeness of a candidate with respect to the requirements. If we have no superfluous models, regardless of what models are omitted, we can say for certain that the models of the candidate are correct with respect to the requirements. On the other hand, any instance of superfluous models indicates that the candidate’s models are not correct with respect to the requirements and therefore less precise. Further, candidates without superfluous models can entail all of the CQs specified in the requirements. Assuming that the CQs do not completely characterise the desired ontology, such candidates may even be satisfactory as-is for the intended application. Thus any theory that is more precise than another will require less (possibly no) effort to reuse. So, in the context of the required effort for reuse, these more precise theories should be preferred over candidates that contain superfluous models.

Preference ( $≪ =$ ) is defined as the combination of the Accuracy Ordering (⪯) and the Precision Ordering (⊲).
Definition 11.
Candidate ontology $T_{2}$ is preferred over candidate ontology $T_{1}$ (denoted by $T_{1} ≪ T_{2}$ ) iff $T_{1} ⪯ T_{2}$ or $T_{1} ⊲ T_{2}$ .

Earlier work by Staab et al. (2004) introduces similar assessments of coverage and precision, however in this case they are used to provide an indication of quality. These concepts are combined in the notion of accuracy presented in this work, whereas the notion of precision in this work is a specialized case of the precision described by Staab et al. (2004). It is important not to confuse the assessment and interpretation of these concepts with the orderings presented here. This earlier work presents a means of assessing quality, whereas the orderings defined here are meant to define a preference with respect to which ontology will be the easiest to reuse; it is not necessarily the case that an ontology with a higher quality will be the easiest to adapt to satisfy the designer’s requirements.

Note that we will never run the risk of having to resolve conflicting orderings to determine the Preference Ordering – if we prefer $T_{1}$ over $T_{2}$ then we cannot find $T_{2}$ to be more correct than $T_{1}$ , and vice versa.
Theorem 1.
If $T_{1} ⪯ T_{2}$ , then $T_{2} ⋪ T_{1}$ .
Proof.
Assume that there exist two theories, $T_{1}$ , $T_{2}$ , such that: $\begin{matrix} T_{1} ⪯ T_{2} and T_{2} ⊲ T_{1} . \end{matrix}$ If $T_{2} ⊲ T_{1}$ then, by definition we must have: $\begin{matrix} SUP (T_{1}) = \emptyset and SUP (T_{2}) \neq \emptyset . \end{matrix}$ It follows that: $SUP (T_{1}) \subset SUP (T_{2})$ .

Therefore, by definition we cannot also have $T_{1} ⪯ T_{2}$ as this requires that $SUP (T_{2}) \subset SUP (T_{1})$ . Our assumption cannot hold, therefore ⪯ cannot conflict with ⊲. □

In other words, if we say that $T_{2}$ is more accurate than $T_{1}$ , then $T_{1}$ cannot be more precise than $T_{2}$ . Since this is equivalent to saying that $T_{1} ⊲ T_{2}$ implies $T_{2} ⋠ T_{1}$ , we can also say that if $T_{1}$ is more precise than $T_{2}$ then we cannot find $T_{2}$ to be more accurate than $T_{1}$ .
Lemma 4.
Let $T$ be a set of candidate ontologies.

$⟨ T, ≪ ⟩$ is a partial ordering.
Proof.
Since $T ⋪ T$ (by Lemma 3), $T ≪ T$ iff $T ≺ T$ , which follows from Lemma 2, and hence $T ≪ T$ , so that ≪ is reflexive.

Suppose $T_{1} ≪ T_{2}$ and $T_{2} ≪ T_{1}$ ; by definition, $\begin{matrix} T_{1} ≺ T_{2} or T_{1} ⊲ T_{2} \end{matrix}$ and $\begin{matrix} T_{2} ≺ T_{1} or T_{2} ⊲ T_{1} . \end{matrix}$ There are four cases:

If $T_{1} ≺ T_{2}$ and $T_{2} ≺ T_{1}$ , then by Lemma 2, $T_{1} ≺ T_{1}$ , and hence $T_{1} ≪ T_{1}$ .

The second case ( $T_{1} ≺ T_{2}$ and $T_{2} ⊲ T_{1}$ ) is not possible by Theorem 1.

The third case ( $T_{2} ≺ T_{1}$ and $T_{1} ⊲ T_{2}$ ) is also not possible by Theorem 1.

Finally, the fourth case ( $T_{1} ⊲ T_{2}$ and $T_{2} ⊲ T_{1}$ ) is not possible by Lemma 3.

Thus, the Preference relation ≪ is antisymmetric.

Now suppose $T_{1} ≪ T_{2}$ and $T_{2} ≪ T_{3}$ ; by definition, $\begin{matrix} T_{1} ≺ T_{2} or T_{1} ⊲ T_{2} \end{matrix}$ and $\begin{matrix} T_{2} ≺ T_{3} or T_{2} ⊲ T_{3} . \end{matrix}$ By Lemma 2 and Lemma 3, $T_{1} ≪ T_{3}$ . Thus, the Preference relation ≪ is transitive. □

The definition of Preference allows us to formalize the fact that we prefer a more accurate and/or precise candidate as it will be less work to reuse. If we were to consider the problem of choosing between time ontologies, using examples CQ-1 and CQ-2 from the previous section to approximate the intended models, the definitions would indicate that we should prefer to reuse the theory of linear points2
²
http://colore.oor.net/timepoints/linear_point.clif.

to that of moments.3
³
http://colore.oor.net/combined_time/moment.clif.

Although both candidates are able to entail the requirements and so contain no superfluous models, the comparison would find that the theory of linear points is more accurate than the theory of moments because it omits fewer models, and is therefore closer to the required theory approximated by $T_{R}$ via the CQs.4
⁴
Note that in practice the set of CQs would likely be much larger making for more interesting and complex results.

6.2. Viability

We now operationalize our notion of preference by introducing a set of procedures capable of producing the Preference Ordering for a given set of candidates and formalized CQs. These procedures implement a set of criteria that is provably complete and correct with respect to the definition of preference.

6.2.1. Assumptions

The procedures make the following assumptions:

$M^{intended} = Mod (T_{R})$ We use the set of CQs, $T_{R}$ , to approximate the intended models. While $T_{R}$ will likely not completely characterize the intended models, it is the best approximation that is available to the developer at this stage of design. This is a necessarily practical assumption to make, and one that is also true of the current state of traditional ontology development where the specification and evaluation of CQs is a generally accepted practice. The sufficiency of CQs is discussed further in Section 7.2.

The candidates share some common (the same or overlapping) signature with the CQs. We assume whatever mappings exist between the theories have already been applied. This is a reasonable assumption due to the fact that, should a candidate be relevant in any way, there must exist mappings between its terms and those of the CQs. In fact, the procedures described to aid in the task of Search in the previous section produce the necessary mappings via their conjectures of relevance. Even forgoing any implementation of such procedures, the mappings must be known (at least implicitly) in order for a theory to be identified as relevant. Once they are it is straightforward to apply them to achieve a common signature. While this could be incorporated into the procedures, it is replaced with this assumption for simplicity.

The candidates are in the same logical language as the CQs. This is reasonable given that most search tools or sources of ontologies are language-specific. Further, if a particular language is necessary or desired, it is reasonable to assume that the CQs would be formalized in this language, and the selection of candidates would include only those in the appropriate language.

All candidate ontologies are consistent and modularized. In the absence of such an assumption there are model builders that could be employed to test this and filter out inconsistent theories; a procedure was also presented by Grüninger et al. (2012) to decompose theories into modules which could be called in the case of non-modularized candidates. However, the inclusion of such procedures for every candidate would not be practical nor ideal, thus we view the modularization and consistency/verification of theories as supporting infrastructure requirements rather than necessary steps in the procedure.

6.3. The procedures

The following set of procedures are designed to obtain the Preference Ordering defined in the previous section.

The Preference Ordering is assigned between a pair of candidates if any of the following criteria holds:

If $T_{R} \cup T_{2} ⊧ T_{1}$ and $\neg T_{R} \cup T_{1} ⊧ T_{2}$ then assign $T_{2} ≪ T_{1}$ ;

If $T_{R} ⩽ T_{1}, T_{R} ≰ T_{2}$ then assign $T_{2} ≪ T_{1}$ ;

If $T_{1} \equiv T_{2}$ then assign $T_{1} =_{≪} T_{2}$ .

Where

T_{R}

corresponds to a theory comprised of the collection of CQs;

T_{i}

corresponds to any given candidate theory as transformed in the common, candidate hierarchy,

H_{R}

(a detailed description of this will follow); and

\neg T

corresponds to the negation of a theory T, which we define as the disjunction of the negation of its axioms. If none of the criteria is met, then a preference ordering cannot be determined, in other words one candidate is not more accurate or more precise than another and therefore they are incomparable. For any pair of theories

T_{1}

T_{2}

, we denote this

T_{1} ∥ T_{2}

We adopt the concept of a hierarchy from Grüninger et al. (2012), where it is presented as a means of storing similar ontologies. Formally:

Definition 12.
A hierarchy $H = ⟨ H, ⩽ ⟩$ is a partially ordered, finite set of theories $H = T_{1}, \dots, T_{n}$ such that:
$σ (T_{i}) = σ (T_{j})$ , for all $i, j$ ;

$T_{1} ⩽ T_{2}$ iff $T_{2}$ is an extension of $T_{1}$ ;

$T_{1} < T_{2}$ iff $T_{2}$ is a non-conservative extension of $T_{1}$ .
The Root Theory, $T_{root}$ of $H$ is a minimal theory in the hierarchy.

We make reference to these COLORE-specific concepts in the procedures, strictly because they are convenient for the presentation of this work. It is important to note that the contributions presented here are independent of any particular repository or other approach to the search for candidate ontologies. The hierarchy is created as part of a procedure meant to provide a common basis for the candidates’ signatures in cases where the scope of the concepts in the CQs and the candidates are not completely in-line with one another. For instance, consider CQ-3 described in the example of time ontologies: its scope includes not only time but also the concept of an event. It is therefore quite possible that in this case the candidates might include both time and event ontologies. The notion of a hierarchy provides a common context to allow for the collective consideration of candidates with varying scopes that may not precisely correspond to that of the CQs ( $T_{R}$ ).

Procedure 2
$CompareCandidates (T, T_{R})$

Procedure 3
$ConsiderCombination (T)$

The top-level procedure required to implement the criteria is specified below in Procedure 2. First, we consider the possible combinations between all candidates as additional candidates; this expanded set of candidates is then transferred into a common context (the Requirements’ Hierarchy, $H_{R}$ ); and finally the Preference Ordering is assigned in the form of a partial order, based on the specified criteria. The role of Procedure 3, considering all possible combinations of candidates, is to identify cases where a combination of candidates may be advantageous. As in the previous example, say the CQs describe both concepts of time and events. If there are some time ontology candidates and some event ontology candidates, it may be the case that a combination of a time ontology and an event ontology will be better than any single candidate. The procedure aims to account for such cases by including candidate combinations as alternatives. Transferring theories to a common context (Procedure 4) works by taking the union of each candidate with the root theory of the Requirements Hierarchy, $H_{R}$ , which is generated with the specification of a simple tautological axiom for each term in the collective signature of candidates and requirements; the purpose of this is simply to ensure that the candidates’ signatures are comparable. After this signature expansion is complete, each theory may be organized in the hierarchy simply by determining the partial ordering via the Poset-Sort algorithm. This is accomplished according to a previously defined procedure for poset sorting from Daskalakis et al. (2011). The Preference Ordering is then calculated in Procedure 5 by evaluating every combination of candidate theories against the three ordering criteria defined above.

Procedure 4
$Create H_{R} (M, T_{R})$

Note that this specification of procedures is primarily intended to demonstrate the feasibility of the implementation of the Preference Ordering, and is not meant to be the most efficient approach. For example, the consideration of all possible combinations of candidates in Procedure 3 simply generates all (consistent) combinations of the candidates’ modules and adds these to the set of candidates to be considered.

Procedure 5
$AssignOrder (H, T_{R})$

The pseudocode for the sorting procedure is provided in Fig. 2; it is taken directly from its original presentation and adapted to determine partial ordering is on a set of theories by searching for the “weakest/strongest theory that entails/is entailed by e”, as opposed to the smallest/largest elements. The authors employ the concept of a chain, referring to a subset of mutually comparable elements from the ordering, in order to define and navigate the partial ordering more precisely.

Fig. 2.
The Poset-BinInsertionSort algorithm from Daskalakis et al. (2011) is adapted here to determine a partial ordering of theories based on entailment.
Theorem 2.
Given a set of theories, $T = {T_{1}, \dots, T_{n}}$ , and a theory comprised of some semantic requirements, $T_{R}$ , if Procedure 2 $CompareCandidates (T, T_{R})$ terminates, it will return a poset on $T$ and all consistent combinations of its modules, in their expanded signature $σ (T_{1}) \cup \dots \cup σ (T_{n}) \cup σ (T_{R})$ , according to the Preference Ordering with respect to the requirements $T_{R}$ .
Proof.
$CompareCandidates (T, T_{R})$ calls procedures $ConsiderCombination (T)$ , $Create H_{R} (M, T_{R})$ , and $AssignOrder (H, T_{R})$ . Therefore, if we show that:
$AssignOrder (H, T_{R})$ returns a poset on all of the theories in $H$ according to the Preference ordering, with respect to $T_{R}$ ;

and $Create H_{R} (M, T_{R})$ creates a hierarchy containing all of the theories in $M$ and $T_{R}$ and all consistent combinations of their modules, in their expanded signature;

and $ConsiderCombination (T)$ generates $T$ and all consistent combinations of its modules,
we will have shown that Procedure 2 $CompareCandidates (T, T_{R})$ returns a poset on $T$ and all consistent combinations of its modules, in their expanded signature $σ (T_{1}) \cup \dots \cup σ (T_{n}) \cup σ (T_{R})$ , according to the Preference Ordering with respect to the requirements $T_{R}$ . Claim.
Given some set of theories $T = {T_{1}, \dots, T_{n}}$ , if Procedure 3 $ConsiderCombination (T)$ terminates, it will return all consistent combinations of the modules of $T$ .

This follows from the definition of a power set. By definition, the power set of $F$ is the set of all subsets of $F$ ; in other words, the set of all sets of the modules of the theories in $T$ . For each member of the set, the procedure evaluates whether the union of its members (modules) is consistent (line 5 of Procedure 3) and any consistent members are added to the set $M$ to be returned. Thus $M$ contains all consistent combinations of the modules of $T$ . Claim.
Given some set of theories $M$ and some theory $T_{R}$ , if Procedure 4 $Create H_{R} (M, T_{R})$ terminates it will return a hierarchy $H_{R} = ⟨ H_{R}, ⩽ ⟩$ such that each $T_{R}, T_{i}^{} \in H_{R}$ is the conservative extension of each $T_{R}, T_{i} \in M$ , (respectively) by the root theory of $H_{R}$ .

Lines 1–3 of Procedure 4 initialize the hierarchy $H_{R}$ .

Lines 4–13 of Procedure 4 create the root theory $T_{root}$ of $H_{R}$ .

Lines 14–17 of Procedure 4 add $T_{root}$ to each $T_{i} \in M$ , and to $T_{R}$ , and add the extension to $H_{R}$ .

Therefore, the partially ordered set of theories, sorted on entailment (as per the algorithm from Daskalakis et al. (2011)) returned on line 18 is in fact a hierarchy $H_{R} = ⟨ H_{R}, ⩽ ⟩$ such that each $T_{R}, T_{i}^{} \in H_{R}$ is the conservative extension of each $T_{R}, T_{i} \in M$ , (respectively) by the root theory of $H_{R}$ .

Since $T_{root}$ is composed solely of tautologies, each $T_{i}^{}, T_{R}^{}$ must be conservative extensions of each $T_{i}, T_{R}$ (respectively) in the expanded signature $σ (T_{1}) \cup \dots \cup σ (T_{n}) \cup σ (T_{R})$ . Claim.
Given a hierarchy $H = ⟨ H, ⩽ ⟩$ and a theory $T_{R}$ , if Procedure 5 $AssignOrder (H, T_{R})$ terminates, it will return a poset on the theories in $H$ , according to the Preference Ordering with respect to $T_{R}$ .

The procedure considers each pair of theories, $T_{i}, T_{j} \in H$ , with the exception of the requirements $T_{R}$ and the root theory $T_{root}$ . Each pair is evaluated against the Preference Ordering Criteria 1, 2, and 3 on lines 6, 2, and 4 (respectively) of Procedure 5. According to Theorem 1, the criteria do not conflict, so the ordering of their assessment is irrelevant. The completeness and correctness of Criteria 3 for equally preferred candidates is a result of Lemma 1. The completeness and correctness of Criteria 1 and 2 for the Preference Ordering between candidates is a result of Theorem 3, proven in Section 6.4. Thus the procedure will assign the correct Preference Ordering for each pair of candidates in $H$ (with the exception of $T_{R}$ and $T_{root}$ ). By Lemma 4, this ordering will be a poset.

$CompareCandidates (T, T_{R})$ first calls $ConsiderCombination (T)$ , which we have shown will return all consistent combinations of the modules of $T$ . It then calls $Create H_{R} (M, T_{R})$ , where $M$ is the set of theories returned by $CompareCandidates (T, T_{R})$ . We have shown this returns a hierarchy $H_{R} = ⟨ H_{R}, ⩽ ⟩$ containing all candidates and the consistent combinations of their modules in the expanded signature $σ (T_{1}) \cup \dots \cup σ (T_{n}) \cup σ (T_{R})$ . Finally, $AssignOrder (H, T_{R})$ is called, where $H$ is the hierarchy returned by $Create H_{R} (M, T_{R})$ . We have shown this will return a poset, according to the Preference Ordering over all of the theories in $H$ with respect to the requirements, $T_{R}$ . □
6.4. Correctness and completeness of criteria

From Lemma 1, two candidates are equally accurate if and only if they are logically equivalent. This addresses both the correctness and the completeness of the third criteria in the procedure. Thus the following theorem considers only the first two criteria, (1) $T_{R} \cup T_{2} ⊧ T_{1}$ and $\neg T_{R} \cup T_{1} ⊧ T_{2}$ , and (2) $T_{R} ⩽ T_{1}, T_{R} ≰ T_{2}$ that are used in the previous procedure to detect and assign a preference ordering between candidates.

Theorem 3.
Suppose $T_{R}$ corresponds to a theory comprised of the collection of competency questions.

For any two candidate ontologies $T_{1}$ , $T_{2}$ ,

$T_{2} ≪ T_{1}$ iff:
$T_{R} \cup T_{2} ⊧ T_{1}$ and $\neg T_{R} \cup T_{1} ⊧ T_{2}$ , or

$T_{R} ⩽ T_{1}, T_{R} ≰ T_{2}$ .

In the following, we first prove that if either condition (1) or (2) in Theorem 3 are met, then the preference ordering $T_{2} ≪ T_{1}$ holds. If none of the conditions are met, then the Preference Ordering cannot be determined, in other words one candidate is not more accurate or more precise than another and therefore they are incomparable. For any pair of theories $T_{1}$ , $T_{2}$ , we denote this $T_{1} ∥ T_{2}$ .

In the second part of the proof, we show that for all $T_{1}$ , $T_{2}$ in candidate hierarchy $H_{R}$ , if $T_{1}$ , $T_{2}$ are comparable (i.e. $T_{1} ≪ = T_{2}$ or $T_{2} ≪ = T_{1}$ ), then at least one of the procedure’s criteria will be met. Proof.
⇐
If $T_{R} \cup T_{2} ⊧ T_{1}$ and $\neg T_{R} \cup T_{1} ⊧ T_{2}$ then $T_{2} ≪ T_{1}$ . Proof.
If $T_{R} \cup T_{2} ⊧ T_{1}$ , then:

For all models $M$ : $\begin{array}{l} M \in Mod (T_{R}), M \in Mod (T_{2}) \to M \in Mod (T_{1}), \\ M \in Mod (T_{R}), M \notin Mod (T_{1}) \to M \notin Mod (T_{2}) . \end{array}$ By definition of $OM (T)$ : $\begin{matrix} OM (T_{1}) \subseteq OM (T_{2}) . \end{matrix}$

If $\neg T_{R} \cup T_{1} ⊧ T_{2}$ then:

For all models $M$ : $\begin{matrix} M \notin Mod (T_{R}), M \in Mod (T_{1}) \to M \in Mod (T_{2}) . \end{matrix}$ By definition of $SUP (T)$ : $\begin{matrix} SUP (T_{1}) \subseteq SUP (T_{2}) . \end{matrix}$

Therefore, if $T_{R} \cup T_{2} ⊧ T_{1}$ and $\neg T_{R} \cup T_{1} ⊧ T_{2}$ then by definition we must have $\begin{matrix} OM (T_{1}) \subseteq OM (T_{2}) and SUP (T_{1}) \subseteq SUP (T_{2}) . \end{matrix}$

Therefore by definition of the accuracy ordering we have $T_{2} ⪯ T_{1}$ , and so by definition of the preference ordering we have $T_{2} ≪ = T_{1}$ . □

If $T_{R} ⩽ T_{1}, T_{R} ≰ T_{2}$ then $T_{2} ≪ T_{1}$ . Proof.
Since $T_{R} ⩽ T_{1}$ then it must be the case that $Mod (T_{1}) \subseteq Mod (T_{R})$ .

Therefore $T_{1}$ cannot have any superfluous models, so $SUP (T_{1}) = \emptyset$ .

Since $T_{R} ≰ T_{2}$ then it must be the case that $Mod (T_{2}) ⊈ Mod (T_{R})$ .

Therefore $SUP (T_{2}) \neq \emptyset$ .

Therefore $T_{2} ⊲ T_{1}$ , and so by definition of the preference ordering, we have $T_{2} ≪ T_{1}$ . □
⇒

Assume that a Preference Ordering holds between two candidates, $T_{1}$ , $T_{2}$ and none of the criteria hold. By definition, if $T_{1} ≪ = T_{2}$ , then either $T_{1} ⪯ T_{2}$ or $T_{1} ⊲ T_{2}$ must be true.

Assume $T_{1} ≺ T_{2}$ . By definition, $\begin{matrix} T_{1} ⪯ T_{2} ⟺ SUP (T_{2}) \subseteq SUP (T_{1}), OM (T_{2}) \subseteq OM (T_{1}) . \end{matrix}$

For any two candidate theories, $T_{1}$ , $T_{2}$ in the Candidate Hierarchy, $H_{R}$ , from the definition of $OM (T)$ : $\begin{array}{l} OM (T_{1}) \subseteq OM (T_{2}) & ⟺ (M \in Mod (T_{R}), M \notin Mod (T_{1}) \to M \notin Mod (T_{2})) \\ ⟺ M \in Mod (T_{R}), M \in Mod (T_{2}) \to M \in Mod (T_{1}) \\ ⟺ T_{R} \cup T_{2} ⊧ T_{1} . \end{array}$

For any two candidate theories, $T_{1}$ , $T_{2}$ in the Candidate Hierarchy, $H_{R}$ , from the definition of $SUP (T)$ : $\begin{array}{l} SUP (T_{1}) \subseteq SUP (T_{2}) & ⟺ (M \in Mod (T_{1}), M \notin Mod (T_{R}) \to M \in Mod (T_{2})) \\ ⟺ T_{1} \cup \neg T_{R} ⊧ T_{2} . \end{array}$

This conflicts with our assumption that no criteria hold, as we have shown it is impossible to have $T_{1} ⪯ T_{2}$ and not satisfy Criteria 1.

Assume $T_{1} ⊲ T_{2}$ . By definition, $\begin{matrix} T_{1} ⊲ T_{2} ⟺ SUP (T_{1}) \neq \emptyset, SUP (T_{2}) = \emptyset . \end{matrix}$ By definition of $SUP (T)$ , if: $\begin{array}{l} SUP (T_{2}) = \emptyset, \\ M \in Mod (T_{R}) \to M \in Mod (T_{2}), \\ T_{R} ⩽ T_{2} . \end{array}$

If $\begin{matrix} SUP (T_{1}) \neq \emptyset . \end{matrix}$ There exists some $\begin{array}{l} M such that M \notin Mod (T_{R}), M \in Mod (T_{1}) \\ T_{R} ≰ T_{1} . \end{array}$

This conflicts with our assumption as we have shown that it is impossible to have $T_{1} ⊲ T_{2}$ and not satisfy Criteria 3. □

7. Discussion

In the following, we identify and justify choices that were made in the design of the procedures to implement the definition of preference.

7.1. The use of hierarchies

The reader will likely have noticed that the transfer to a hierarchy structure in Procedure 4 is not necessary to determine the ordering, however there was sufficient motivation for its inclusion. The hierarchy structure provides useful means of storing the candidates in a common context after the translation and expansion of their signatures. It also offers a structured venue for storing and reusing results of these evaluations. Beyond this, the ordering of theories in the hierarchy may be leveraged to improve the efficiency of the Preference Ordering implementation, as certain cases of the Preference Ordering may be identified via the non-conservative extension ordering, thus eliminating the need to evaluate certain pairs against the entailment criteria.

The use of a hierarchy also offers potential benefits for other areas of reuse. The use of hierarchies supports the potential to leverage the notion of the similarity5

⁵
Informally, the similarity between a set of theories is the strongest theory that is entailed by all of the theories.

between theories, as defined by Grüninger et al. (2012), to determine what will be shareable. Given that there already exists a procedure for adding theories to such a hierarchy, it seemed advantageous to collect candidates in this manner.

7.2. The sufficiency of CQs

While the use of CQs as requirements is well-established, their role as approximating the required theory, $T_{R}$ , in the implementation of the Preference Ordering may be subject to speculation. However, at this stage in development, no better approximation of the theory exists. Further, if some draft axioms do exist, these sentences could be added to $T_{R}$ without affecting the definition or the procedure.

In the review of related work, we saw approaches that assigned weightings or priorities to the requirements. It follows from this perspective that requirements are often times not equally important, and thus our definition of preference is lacking this dimension. However, it is our position that in the context of semantic requirements, such approaches are flawed; given the nature of a CQ there should be nothing malleable about them. Although the decision of which interpretations should be models of the ontology may be subject to revision, at any point in time a model is either desired or it is not.

7.3. $H_{R}$ root theory definition

A reader familiar with the notion of a hierarchy as defined in COLORE will have noticed that the root theory used here differs from that which is defined in the COLORE literature Grüninger et al. (2012). This deviation was supported by pragmatic and philosophical factors; we discuss the alternative approaches, and the rationale behind this decision here.

Typically, the root theory represents the most basic ontological commitment in a given hierarchy (domain). In the context of COLORE, where hierarchies provide a tool to organize different theories, it makes sense to require that a hierarchy have a unique root theory. This acts as a kind of sorting mechanism as it requires that theories with varied basic commitments be stored in separate hierarchies.

For our purposes, we wanted to gather the candidate theories into a single hierarchy for comparison, but what would it mean to be the root theory of such a hierarchy? After all, a hierarchy of candidate theories is not necessarily a true hierarchy. It is a collection of candidate conjectures gathered via some heuristics and there is no guarantee that there is a meaningful, underlying commitment shared between them, in fact we expect this will often not be the case. The root theory was a necessary tool to expand the signature of the candidate theories (and semantic requirement theory) in a consistent manner, such that they could be considered in the same hierarchy. The concept of the root theory for this task was appealing in that, as the ‘weakest theory’ in the hierarchy it would be a benign addition to each of the theories in order to achieve the required vocabulary. However the meaning and attainability of a true root theory in a scenario of varied candidates with overlapping and possibly even disjoint signatures is unclear.

One potential means of discovering the root theory was to take an informed approach, requiring the identification and consideration of the root of each candidate. The idea would be to iteratively create a root theory for $H_{R}$ , starting with the root theory of the requirements, and revising it by finding the similarity (the weakest common theory, as defined by Grüninger et al. (2012)) between itself and one of the candidate theories. Several potential questions arise when considering this case, such as: What would be the initial root theory? How would we generate a new theory when there is some signature overlap? The signature mismatch would need to be resolved before being able to find the similarity, however recall the original purpose of the root theory was to provide the candidates with a common signature. If we solve the issue of mismatched signatures in order to identify the similarities between the candidates - then we have already solved the original problem that the root theory was intended for! Further, while it still may be appealing to identify the ‘true’ root theory of the candidates’ hierarchy, finding the similarity between two theories is theoretically possible but it is also complicated and would need to be performed a number of times. Would this approach even be scalable?

Instead, we chose to derive the weakest possible root for $H_{R}$ based solely on the signature of $T_{R}$ and all of the candidates. To maintain simplicity, this approach generates a simple axiom for each term in the signature which introduces no additional semantics, i.e. a tautology, (this process is described in full in Procedures 4). This approach appeals to any pragmatic concerns as the necessary implementation is straightforward, presenting no feasibility or scalability concerns. It also offers a completely uniform solution in that the axioms will be generated, without exception, with the same intuition and the same method; this is crucial to avoid skewing the assessment results. Finally, when considering the meaning of the hierarchy in this case, a root theory of tautologies appeals to our intuitions. As opposed to traditional hierarchies that group theories based on some shared, ontological commitment, the purpose of this hierarchy is to provide a common context for comparison of the candidates. In this case we cannot assume there exists any meaningful, shared ontological commitments between all of the candidates and the requirements. It is logical then, that the shared commitment between any set of candidate consists of a theory comprising the collective signature, but with essentially meaningless axioms.

7.4. Implementation concerns

As mentioned, the procedure presented here is a bare-bones demonstration of feasibility. While in theory these procedures may be followed and even (semi-)automated to achieve the desired results, in their current state they would admittedly not make for a very pragmatic solution.

For instance, in Procedure 3, we provide for a consideration of potential candidate merges through the addition of all possible combinations of candidate modules. This is a brute force approach – although it will identify combinations of candidates that may be advantageous merges, it will also result in the consideration of many combinations which could easily be identified as useless. Consider the case where two candidates, $T_{1}$ , $T_{2}$ have complementary signatures: if we merge $T_{1}$ and $T_{2}$ then the resulting theory (a new candidate, let’s say $T_{3}$ ) would have a broader scope than both $T_{1}$ and $T_{2}$ and thus potentially be more capable in satisfying the semantic requirements. On the other hand, if $T_{2}$ ’s signature contained the signature of $T_{1}$ , then in terms of scope we are no better off with $T_{3}$ than we were with $T_{2}$ . It would be straightforward enough to implement a procedure that captures this observation in order avoid the unnecessary assessment of these sorts of non-beneficial merges. For example, rather than adding all combinations of modules, we could perform a simple check to determine whether the merge would be advantageous in terms of signature. If the merge of some theories has a broader scope than both original theories (i.e. if $σ (T_{3}) \supset σ (T_{1})$ and $σ (T_{3}) \supset σ (T_{2})$ ) then it would be added to the set of candidates to consider for reuse. If this condition is not met then, with respect to breadth of scope, there is no reason to consider it. This sort of approach, outlined in Procedure 7 could take the place of the brute force approach presented previously.

Procedure 7

$ScopeBeneficialMerge (T)$

Procedure 8

Identify semantics beneficial merges

A similar observation can be made with respect to the candidates’ semantics; if the combination of two theories does not result in a new candidate that is better with respect to the semantic requirements, then we have no cause to consider it as a potential merge. This could be accounted for with an approach similar to the previous suggestion, as outlined in Procedure 8. Alternatively, we might simply omit consideration of merges altogether unless prompted by the designer.

Beyond these suggestions, there is a great deal of room to improve upon the design of the procedures we have presented here. In general, while we recognize that the implementation’s efficiency is an important consideration, it is out of the scope of this work.

8. Summary

By leveraging the formal and objective nature of CQs we were able design a procedure capable of producing a useful comparison between candidate ontologies. We have provided an solution that successfully simplifies the evaluation and assessment of candidate ontologies with respect to the semantic requirements. The definition of preference described here addresses several of the limitations for reuse identified in the 2014 Ontology Summit Communiqué.

The ordering can be used to clearly identify and compare relative mismatches or misunderstandings (Mismatches and Misunderstandings) that might have occurred in candidate selection – a candidate that is considerably less preferred differs substantially from the required semantics. Where initial impressions may have indicated that some candidate should be chosen for reuse, the Preference Ordering allows the developer to either confirm or refute this without the difficulty of performing a detailed investigation of all of the alternatives.

We describe how CQs may be employed to select candidate ontologies, and further with the implementation of the Preference Ordering we illustrate how these CQs may again be used to sort through the candidates to find the most suitable ontology (Finding Mr. Right Ontology), with respect to the semantic requirements.

The problem of ontologies not ‘fitting’ the requirements (This Ontology Doesn’t Fit…) stems from the fact that the answer to the previous question of whether or not an existing ontology meets the requirements is not a simple yes or no. The Preference Ordering accounts for this and essentially compares the relative effort to fit each of the candidates to the semantic requirements.

Because this work simplifies these aspects of design by reuse, it also reduces the potential for the difficulties involved to prompt developers to simply to do-it-themselves (Just Do It Yourself).

The work presented here may be extended to address the recommendations in the Communiqué. The assumed infrastructure necessary to support these solutions may serve as input for the best practices for shareable and reusable content that the Communiqué recommends be adopted by the community. The procedures specified here are sufficiently well-defined such that they could provide the basis for tool support to address these limitations of reuse. This makes a substantial contribution to the Communiqué’s recommendation that tools should be developed to better support reuse, (among other aspects of development). Finally, this work has implications beyond design by reuse. An interesting direction of future work may be to consider how this notion of preference could be applied to assess the relative shareability between existing ontologies to determine, for example, which applications might work best together.

References

Daskalakis, C., Karp, R.M., Mossel, E., Riesenfeld, S.J. & Verbin, E. (2011). Sorting and selection in posets. SIAM Journal on Computing, 40(3), 597–622. doi:10.1137/070697720.

Enderton, H.B. (1972). A Mathematical Introduction to Logic.

Euzenat, J., Shvaiko, P., et al. (2007). Ontology Matching (Vol. 333). Springer.

Fernandez, M., Cantador, I. & Castells, P. (2006). CORE: A tool for collaborative ontology reuse and evaluation. In 4th International Workshop on Evaluation of Ontologies for the Web (EON 2006), Edinburgh, UK, 23–26 May 2006.

Fernández-López, M., Suárez-Figueroa, M.C. & Gómez-Pérez, A. (2012). Ontology development by reuse. In Ontology Engineering in a Networked World (pp. 147–170). Springer. doi:10.1007/978-3-642-24794-1_7.

Grüninger, M. & Fox, M.S. (1994). The role of competency questions in enterprise engineering. In Proceedings of the IFIP WG5.7 Workshop on Benchmarking – Theory and Practice.

Grüninger, M. & Fox, M.S. (1995). Methodology for the design and evaluation of ontologies. In International Joint Conference on Artificial Intelligence (IJCAI95), Workshop on Basic Ontological Issues in Knowledge Sharing.

Grüninger, M., Hahmann, T., Hashemi, A., Ong, D. & Özgövde, A. (2012). Modular first-order ontologies via repositories. Applied Ontology, 7(2), 169–209.

Grüninger, M. & Katsumi, M. (2012). Specifying ontology design patterns with an ontology repository. WOP, 929.

10.

Guarino, N., Oberle, D. & Staab, S. (2009). What Is an Ontology? (2nd ed., pp. 1–17). Berlin: Springer.

11.

Katsumi, M. & Grüninger, M. (2010). Automated Reasoning Support for Ontology Development (pp. 208–225). Berlin: Springer.

12.

Lozano-Tello, A. & Gómez-Pérez, A. (2004). Ontometric: A method to choose the appropriate ontology. Journal of Database Management, 2(15), 1–18. doi:10.4018/jdm.2004040101.

13.

Obrst, L., Gruninger, M., Baclawski, K., Bennett, M., Brickley, D., Berg-Cross, G., Hitzler, P., Janowicz, K., Kapp, C., Kutz, O., et al. (2014). Semantic web and big data meets applied ontology: The ontology summit 2014. Applied Ontology, 9(2), 155–170.

14.

Pinto, H.S. & Martins, J.P. (2001). A methodology for ontology integration. In Proceedings of the 1st International Conference on Knowledge Capture (pp. 131–138). ACM.

15.

Staab, S., Gómez-Pérez, A., Daelemana, W., Reinberger, M.-L. & Noy, N.F. (2004). Why evaluate ontology technologies? Because it works!IEEE Intelligent Systems, 19(4), 74–81. doi:10.1109/MIS.2004.37.

16.

Uschold, M. & Grüninger, M. (1996). Ontologies: Principles, methods and applications. Knowledge Engineering Review, 11, 93–136. doi:10.1017/S0269888900007797.