Ontologies have the nasty habit of growing in size and expressivity until all reasoners are at a loss to treat them in reasonable time. While it is widely known that the worst case complexity for OWL 2 DL reasoning is double exponential in time, but in fact most ontologies tend to be well behaved in practice, it is less well known that any ontology, left to itself, will grow until the worst OWL constructs gang up together and stop any reasoner from providing answers fast. We present a brand new idea to tackle this issue, by using a metareasoner which leverages best of breed reasoners and modularisation techniques to prevent the worst side e ects of growing ontologies and keep query answering performance to its best. In our approach, each query will be answered by using only part of the ontology, and the best reasoner for the query will be selected on the basis of the features of this ontology portion, which is built using modularisation and/or atomic decomposition. We show the performances of an implementation of this approach. Our Chainsaw metareasoner is not designed to deal with small and inexpressive ontologies, for which a regular reasoner is more than adequate. It, instead, deals with large, complex and unwieldy ontologies, for which better solutions are not (yet) available.
As it is well known to ontology engineers, ontologies become harder to manage, in terms of understanding them and reasoning with them, in a way which is, unfortunately, not proportional to the increase of their size. It is often the case that a small number of changes makes an ontology much harder for a reasoner to process. However, keeping ontologies small and simple is not always possible, because they might fail to satisfy the application requirements. On the other hand, it is possible for a small ontology to be hard to reason about.
How to best divide an ontology into smaller portions according to the needs of the task at hand is still an open problem; the rule of thumb that many approaches follow is that, when in doubt, one should try to keep the ontology as small as possible.
This is the main intuitive reason for modularization, i.e., a set of techniques for splitting ontologies into fragments without loss of entailments for a given set of terms. To date, however, not many tools provide either user support for these techniques, nor leverage them for reasoning tasks.
Chainsaw, our metareasoner implementation prototype, exploits the idea in the following way. For every inference query it creates a module of the ontology that is then used to answer the query. The module is created in a way that guarantees the result of the query should be the same as for the whole ontology, i.e., there is no loss of entailments.
Chainsaw is designed as a wrapper for other reasoners. It uses reasoner
factories to build reasoners on modules of its root ontology, and will integrate
the ability to choose the reasoner best suited to each reasoning task on the basis
of the module characteristics, such as size and/or expressivity. The most obvious
characteristic is an OWL 2 pro le of the module. E.g., if the pro le is OWL 2
EL then some e cient EL reasoner, like ELK [
The advantages of using modules instead of whole ontologies inside a reasoner reside in the simpli cation of reasoning. The complexity of reasoning in OWL 2 DL is N2EXPTIME-hard on the size of the input, therefore being able to divide the ontology is likely to produce performance improvements orders of magnitude larger than the relative reduction in size.
Moreover, using modules inside the reasoner can help the knowledge engineer to concentrate on modelling the knowledge instead of worrying about the language pitfalls, since the extra complexity can be tackled in a transparent way. This, however, does not mean that complexity is no longer an issue. Modularisation is not a silver bullet for reasoning, as in some cases the module needed to answer a query might still include most of the ontology.
Another advantage of Chainsaw architecture is that it is able to use di erent OWL reasoners for each query and module; this allows for choosing the reasoner best suited for the OWL 2 pro le of a speci c module. In those cases where it is not clear which reasoner is best, it is possible to start more than one reasoner and simply wait for the rst one to nish the task - this might require more resources, but statistical records can be kept to improve future choices. This functionality, however, is not yet implemented.
The reverse of the medal is that, for simple ontologies, Chainsaw is likely to be slower than most of the reasoners it uses; this derives from the overhead needed to manage multiple reasoners and modularization of the ontology itself. Our objective, in this paper, is to illustrate an approach that can squeeze some answers out of ontologies that are too troublesome for a single traditional reasoner to handle.
In Section 2, we describe brie y the theory behind Atomic Decomposition and Modularization, which are the building blocks of this approach; in Section 3 we describe the implementation details, trade-o s and strategies adopted, and in Section 4 we present some preliminary results on the e ectiveness of Chainsaw.
Atomic Decomposition and Modularization We assume that the reader is familiar with the notion of OWL 2 axiom, ontology and entailments. An entity is a named element of the signature of an ontology. For an axiom we denote e a signature of that axiom, i.e. a set of all entities in . The same notation is also used for the set of axioms.
De nition 1 (Query). Let O be an ontology. An axiom is called an entailment in O if O j= . A check whether an axiom is an entailment in O is an entailment query. A subclass (superclass, sameclass) query for a class C in an ontology O is to determine a set of classes D 2 Oe such that O j= C v D (resp. O j= D v C; O j= C = D). A hierarchical query is either subclass, superclass, or sameclass query. e De nition 2 (Module). Let O be an ontology and be a signature. A subset M of the ontology is called module of O w.r.t. if for every axiom such that , M j= () O j= .
One way to build modules is through the use of axiom locality. An axiom
is called (?-) local w.r.t. a signature if replacing all entities not in with
? makes the axiom a tautology. This syntactic approximation of locality was
proposed in [
This modularisation algorithm is used to create an atomic decomposition of
an ontology, which can then be viewed as a compact representation of all the
modules in it [
De nition 3 (Atomic Decomposition). A set of axioms A is an atom of the ontology O, if for every module M of O, either A M or A \ M = ;. An atom A is dependent on B (written B 4 A) if for every module M if A M then B M . An Atomic Decomposition of an ontology O is a graph G = hS; 4i, where S is the set of all atoms of O.
The dependency closure of an atom, computed by following its dependencies, constitutes a module; this module can then be used to answer queries about the terms contained in this closure.
However, for a hierarchical query the signature would contain a single entity, but the answer set would contain entities that might not be in the module built for that signature.
In order to address this problem, we use Labelled Atomic Decomposition
(LAD), as described in [
De nition 4 (Labelled Atomic Decomposition). A Labelled Atomic Decomposition is a tuple LAD = hS; 4; Li, where G = hS; 4i is an atomic decomposition and L is a labelling function that maps S into a set of labels. A top-level labelling maps an atom A to a (possibly empty) subset of its signature L(A) = Ae n (SB4A L(B)).
Proposition 1. Let LAD = hS; 4; Li be a top-level labelled atomic decomposition of an ontology O. Then for all named classes x; y from Oe the following holds: 1. If O j= x v y, then 9A; B 2 S : x 2 L(A); y 2 L(B) and B 4 A; : 2. If O j= x = y, then 9A 2 S : x 2 L(A) and y 2 L(A).
Proof. 1) From [
: 2) Assume O j= x = y, which is equivalent to O j= x v y and O j= x v y. From Case 1) this means that there are atoms A; A0; B; B0 such that x 2 L(A); x 2 L(A0); y 2 L(B); y 2 L(B0) and B0 4 A; A0 4 B. As shown in Case 1), there is only one atom that contains x (resp. y) in its label, so A = A0; B = B0 and B 4 A; A 4 B. The latter is possible only in case A = B. tu
This proposition provides a way to separate parts of the ontologies necessary to answer hierarchical queries about named classes. Indeed, it is enough to label the atomic decomposition with a top-level labelling and the modules for nding a subsumption relation could easily be found. This approach is orthogonal to a modularity-based one: while the latter deals easily with the entailment-like queries, the former provides a way to describe an ontology subset suitable to answer hierarchical queries. 3
The essence of Chainsaw is mirrored in the paper's title. Unlike other reasoners, which usually do the classi cation of the ontology before any query is asked, Chainsaw deals with requests in a lazy way, leaving classi cation to the delegate reasoners, which are usually at work on a small subset of the ontology.
For each query received, Chainsaw tries to keep the subset of the ontology needed to answer as small as possible without sacri cing completeness. This is achieved using di erent strategies according to the query; i.e., it is not possible to reduce the size of the ontology when checking for its consistency; however, other queries, as detailed in Section 2, can be answered by using modules built via LAD or locality based modules. More in detail, querying about superclasses of a term will only need the dependency closures of the top-level atoms for that term for the answers to be computed; the opposite is true for subclass requests.
During preprocessing of the ontology, a LAD of that ontology is built,
using the Atomic Decomposition algorithm available in FaCT++ [
A naive strategy for answering any query would consist of: { Build a module M for the query { Start a new reasoner R on M { Answer the original query using R
However, it is easy to nd possible optimizations to this strategy.
First, this approach creates a new reasoner for each query; if two queries with the same signature are asked, two (identical) modules would be built and two reasoners would be initialized, while just keeping the same reasoner would be enough.
Moreover, while the number of possible signatures for a query is exponential
in the size of the ontology signature (not counting possible fresh entities used
in the query), the number of distinct modules that can be computed against a
given ontology with these signatures is much smaller [
Therefore, a trade-o exists between reducing the size of the module to be reasoned upon, the complexity of determining such a module and the cost of starting a new reasoner for each query; to this, one must add the memory requirements of keeping a large module and reasoner cache.
Our approach in Chainsaw is to use a cache for modules and a cache for reasoners, both limited in the number of cached elements, and ordered as LRU caches; this has shown to perform rather well in some of our tests, reported in Section 4.1, where around one hundred thousand entailment checks against a large ontology have been satis ed using approximately 100 simultaneous reasoners, some of which were reused up to 20 times before being discarded. Similar results have been obtained when caching the modules to avoid rebuilding the same module for the same signature. 3.1
There is one more optimization that was not implemented: if a module is included in another module, the larger module can be used in place of the smaller one. However, this presents a slippery slope problem: at what level do we stop using the next containing module, since we do not have an easy way to predict where this series of modules will become really hard to reason with?
Determining the containment is also an expensive operation; for simple modules, this operation might cost more than the actual reasoning required. The sweet spot for this optimization is a situation in which many fairly complex modules share a large number of axioms and are used often, and their union does not produce a module which pushes the reasoner's envelope. Using the union would provide for a good boost in performance and save memory as well, but at the time of writing we do not have an e ective way of nding such spots.
It seems that atomic decomposition could provide relevant information for this task; an educated guess would be that such sweet spots reside near the parts of the dependency graph where a number of edges converge, but, to the best of our knowledge, there is no strong evidence in favor of this correlation. Future work might well explore this area.
Another improvement is to add a strategy to choose the best suited reasoner for a given module; such a strategy would have to take into account the known weak spots and strong points of each reasoner, as well as the characteristics of the module and of the query, such as size and OWL pro le, or whether the query requires classi cation of the module or not. Where this is not su cient, statistical records could be kept in order to create evidence based preferences and improve the strategy over time. 3.2
Chainsaw implements the OWLReasoner interface de ned in the OWL API1; it is therefore easy to add it to existing applications, such as ontology editors, which already use some of the existing implementations of OWLReasoner. 4
To check the performance of Chainsaw we ran several tests with it. For the tests we used a MacBooc Pro laptop with 2.66 GHz i7 processor and 8Gb of memory.
We use Chainsaw with FaCT++ v 1.5.3 as a delegate reasoner, and compare the results with the same version of FaCT++.
As a test suite we took 57 of the BioPortal ontologies2. For every ontology we perform a set of classes, properties and individuals tests, i.e., for every class we checked its satis ability, ask for its instances and for sub-, super- and equivalent classes. Moreover, for every class we took its subclass C and superclass D, and ask whether C is a subclass of D. For every individual we ask the sets of its types, and for same and di erent individuals. For every property, its sub-, super, and equivalent properties were queried, together with property range and domain.
The test results are presented in a few tables below. All the tables have the same format: the name of the method called, total number of calls for all tests, and the total time spend in that method for Chainsaw and FaCT++, given in milliseconds.
Table 1 contains operations that are done only once for every ontology. First every reasoner is initialised, then it is asked to precompute inferences (in our tests reasoners were asked to precompute a class hierarchy). In the next step the consistency of an ontology is checked. After that, we asked reasoners whether there were any unsatis able classes.
It is easy to see that the initialisation of Chainsaw reasoner took much more time than the one for FaCT++. That overhead comes from the necessity of creating LAD for each ontology. Interesting to see, however, how the time is distributed between the precomputeInferences and isConsistent steps. In the case of Chainsaw nothing is done during the precomputing step, and there is a need to do work for checking the ontology consistency. On the other hand, FaCT++ tests consistency during classi cation, so answering that query costs nothing.
The data on individuals is presented in the Table 2. There were only 3 ontologies with individuals in our test suite, and the time needed for individual-related operations is similar for both reasoners, with the exception of getInstances case, in which FaCT++ behaves much better than Chainsaw.
However, the discerning reader will have noticed that there is a number of ontologies not containing any individual; yet, the reasoners are taking some time, in the case of Chainsaw quite some time, to answer the query with an empty set. This points to possible optimisations for both Chainsaw and FaCT++ itself.
Class-related queries are presented in the Table 3. Note that the hierarchical questions are faster for Chainsaw; this is mainly because there is a simple way to check them, based on LAD. Satis ability and entailment queries, however, took more time in Chainsaw than in FaCT++; here the overhead to produce modules and to create a reasoner starts play a negative role.
Method getEquivalentClasses getSubClasses getSuperClasses isSatis able isEntailed Method getDisjointDataProperties getEquivalentDataProperties getDataPropertyDomains getSubDataProperties getSuperDataProperties getDisjointObjectProperties getEquivalentObjectProperties getInverseObjectProperties getObjectPropertyDomains getObjectPropertyRanges getSubObjectProperties getSuperObjectProperties getObjectPropertyValues getDataPropertyValues
Chainsaw 2,012 7,433 5,059 309,067 661,707 Number of calls 287 287 574 574 574 662 662 662 1324 1324 1324 1324 3907 3960
Queries about properties are presented in the Table 4. Besides a few queries (like getSubObjectProperties), the two reasoners appear to behave similarly on that data, i.e. the di erence, comparing with Tables 2 and 3, is much smaller. 4.1
Genesis of Chainsaw and OBI Prototype Results The idea for Chainsaw was born of a concrete need: experiments needed to be run to prove a theory, and one of the ontologies chosen for the task was the latest version of the OBI ontology3.
The task of Knowledge Exploration is to explore the structure of a model for a given class expression. In particular, the tableau algorithm proves the satis ability of a class by providing a tree-shaped model of that class. The knowledge exploration allows one to access that model, i.e. to know the form of the model as well as the labels of the nodes and edges of the model's tree.
These experiments are based on an extension to OWLReasoner that was designed to allow a developer to gain information about the completion graph that a tableaux reasoner builds for classes and properties; this interface, available in
the OWL API as OWLKnowledgeExplorerReasoner, is, at the time of writing, only implemented by FaCT++, so said experiments had to rely on it to be executed.
Unfortunately, the latest version of OBI is not easily managed by FaCT++; classifying the ontology takes, in fact, four hours and approximatively six gigabytes of memory to reach 97%. Our tests needed to query for the subsumption hierarchy of almost all classes declared and used in OBI, and to check whether a given class expression would subsume said classes; this amounted to little more than a hundred thousand subsumption tests.
Using the same idea we illustrated as the basis for Chainsaw, we were able to write code that would extract a module for the query, classify it and answer the query, using FaCT++; the maximum amount of time needed to classify one of these modules was ve seconds, and the memory used for each classi cation was proportionally small; we were able to use caching of modules and reasoners e ectively, and the whole experiment could be run in under four hours, using approximatively three gigabytes of RAM.
These (highly experimental) results are reported in Table 4.1. As is it easy to see, for this ontology Chainsaw is much better than FaCT++, as the latter could not provide any results in a given time frame. As we mentioned in Section 1, this is the kind of task for which Chainsaw was designed.
Reasoner FaCT++ Chainsaw
Classi cation
time > 4 hrs
Total memory 6 GB 3 GB
Subsumption tests
100,000
Time
4 hrs
Tests per second 7
Reasoner instances 1 300 In this paper, we presented an approach to the use of modularization and atomic decomposition to improve scalability for reasoners, and Chainsaw, a prototype reasoner implementation for this approach. We showed the potential advantages of this approach in the face of increasingly complex and large ontologies, at the expense of pure performance on simple ontologies.
We provided an overview of what trade-o s in terms of memory and speed are involved in our approach, and how our prototype copes with them, presenting a few test results on BioPortal and OBI ontologies, and hinted at future developments and optimizations that have emerged during the prototype creation.