We consider, in this work, ontologies as documents describing the conceptualization of a domain, in a computer-processable language. Specifically, we address the problem of repairing and evolving ontologies consistently. These non-trivial tasks become even harder for ontologies with hundreds of thousands of axioms. Since the standard language set by the W3C for writing ontologies in the Semantic Web, OWL, is founded in the family of the description logics, we adopt the view of ontologies as finite sets of formulae in a logic of this family. This view allows us to combine the theory of Belief Revision, which formalises rational change in logical objects, and strategies of modularisation to devise and improve procedures for ontology change.
Nowadays, ontologies written in languages such as OWL have become the standard method to share information in the Semantic Web (according to the W3C). These documents provide the formal description of a domain in such way that properties can be verified and extracted with the aid of computer programs called reasoners.
To aid the maintenance and evolution of the ontologies, there have been studies in the area of ontology revision (which we discuss in Section 3) that formalized how these tasks should be done. However, even this theory is not able to completely define these operations. In particular, some of them can have more than one outcome considered “correct” and the comparison among them may not be clear.
Additionally, the size of some ontologies (some with hundreds of thousands of axioms) can also complicate the change management. However, modularisation strategies were devised to allow engineers, users and programs to handle only a part of the ontology at a time. Thus, in this work we intend to improve the methods devised in the theory of ontology revision, using techniques from the field of ontology modularisation.
In the rest of this paper, we consider that an ontology O is a set of formulas (or axioms) in a description logic. Also, if X is a formula or set of formulas, we denominate the signature of X the set of all non-logical symbols (concepts, roles and individuals) that X employs.
The subject matter of Belief Revision (or Belief Change) is how rational agents change their beliefs in consequence of the acquisition. The field was born with the seminal work from Alchourr o´n, Ga¨rdenfors and Makinson [Alchourr o´n et al. 1985], in the currently called “AGM theory”. In their framework, the beliefs are represented by a set of logical formulas closed under logical consequence.
With subsequent works, such as [
Most papers in the literature focus in one change operation, contraction, which consists in removing a formula from the consequences of the agent’s beliefs. There are two major constructive methods to obtain ontology contraction operations: the partial meet approach and the kernel approach.
The partial meet approach consists of obtaining maximal subsets of the ontology O that do not imply a formula ' (which we call remainders), selecting the best among them and taking the intersection. Dually, the kernel approach relies on minimal subsets of an ontology O that do imply a formula ' (called kernels) and removes the least relevant elements from each of such set.
In both constructions, there can be multiple plausible outcomes, depending on how one chooses among the remainders or between the formulas inside each kernel. And one of our objectives in this work is to use the structure of the ontology, according to a particular modularity approach, to devise criteria to rank these elements.
To deal with the size of some ontologies, there have been many approaches to modularise ontologies, which consist in extracting parts of the ontology (modules) that are relevant for a given set of terms (signature). Some of these techniques even tried to use the modules to induce a structure in the ontology to aid both algorithms and engineers.
Our intent is to employ one of such approaches to solve two particular issues that arise when trying to revise ontologies, especially when they are too big: the multiple plausible outcomes of the ontology revision operations and the lack of computational resources to compute execute the procedures. Thus, we need a modularisation scheme that can impose an ordering of the axioms in the ontology.
Del Vescovo [2013] evaluates different modularity techniques in the literature with respect to their aptitude to identify structure in ontologies. Since all the approaches considered were inept to the task, the author devises a technique that fulfils the requirements proposed. This technique is called atomic decomposition and is founded on the notion of syntactic locality-based modules, which we present first.
One of the most successful modularisation strategies is the syntactic variant of localitybased modules (syntactic LBMs) proposed in [Grau et al. 2008]. They are used nowadays in practice and are implemented thoroughly in the OWL API1, mostly due to its logical properties and efficiency.
The general idea is that a module of an ontology O for a signature , will consist
of all axioms of O that are relevant (non-local) with respect to the signature . The
locality check is based on syntactic matching rules that reduce each axiom to a form
where deciding whether relevant or not is simple
While the syntactic LBMs may solve the problem of module extraction, they do not induce a structure in the ontology by themselves. Besides, there can be exponentially many subsets of the ontology that are modules for some signature.
These issues on representing ontology structure were addressed with a technique
called atomic decomposition (AD) that is formalized by the following definitions:
Definition 4.1
Definition 4.2
It is also important to remark that this relation establishes a partial order of the atoms in A(O). Given this fact, the strict part of this relation, denoted by is a strict partial ordered set (i.e., a poset). Finally, we define the atomic decomposition of an ontology O as the pair: (A(O); ). Also, there are results which sustain the atomic decomposition as a succinct representation of all modules in an ontology [Del Vescovo 2013].
In this work, we aim to devise a solution to the problem of repairing and evolving big ontologies by combining the theory of ontology revision and modularisation techniques. In particular, we address both the computational problems associated with the size of the ontologies and that of the choice among the possible outcomes of a revision operation.
The principal contributions are: the software framework unifying an state-of-art modularisation strategies (the atomic decomposition) and the algorithms for ontology revision, the new criteria to automatically decide which of the revision outcomes is the best (without resorting to extralogical features) and the formal characterization of operations that follow the criteria devised.
Following the previous implementations that will be extended in this work, the framework will also be written in Java and rely upon the OWL API. This framework will be used to run experiments that will sustain our studies and will be equipped with tools to record the processing time and memory spent during the most critical tasks.
The framework will consist of three loosely coupled components. One of them
is the management of the input ontologies which will be responsible for generating use
cases from real world ontologies (such as those obtained in the NCBO Bioportal2) and
artificial ontologies which will be produced by the algorithm used in [
The second part of the framework will handle the structure of the ontology. In
short, it will execute the following tasks: compute, store, retrieve and maintain the
resulting atomic decompositions and provide syntactic LBMs. The principle is to use
the same techniques discussed in [
The last part handles the ontology change operations, extending the framework devised by Co´ be [C o´be 2014]. Besides using the algorithms already implemented, we also provide the implementation of the new operations devised.
We use the atomic decomposition to devise valuation functions over the axioms of the ontology to decide among the remainder and kernel sets discussed in Section 3. These criteria will try to encode the entrenchment (the importance) of each axiom in the ontology. Afterwards, operators that employ these criteria will be implemented in the aforementioned framework.
With the framework established, we generate a corpus of revision test cases and execute the experiments described below a sufficient number of times to obtain proper statistics for comparative purposes.
1. Measure the execution time and memory of the existing ontology revision
algorithms
Such changes include: agglomeration of atoms and removal of dependencies.
From the analysis, we aim to characterize the operators that employ our relevance criteria
with rationality postulates, that is, describe them using logical properties about their
results, as is common in the area of Belief Revision [Alchourr o´n et al. 1985,
This document presents the PhD proposal to be developed during the next three semesters. We hope this will bring light for those interested in repairing and debugging ontologies in a way that is both computationally efficient and theoretically well-founded.