In this paper we present the results of running the ORE test suite and its reasoning tasks with three reasoners: Chainsaw, JFact and FaCT++. We describe the newest of these reasoners, Chainsaw, in detail, and we compare and contrast its advantages and disadvantages with the other two reasoners. We show the results obtained and how they compare to each other, and we list the cases in which the reasoners fail to complete a task in the assigned time.
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 modularisation, 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 [
Chainsaw is designed as a wrapper for other reasoners. It can use 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 modularisation 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 Modularisation, which are the building blocks of this approach; in Section 3 we describe the implementation details, tradeo s and strategies adopted, and in Section 5 we present the results on the e ectiveness of Chainsaw comparing to JFact and FaCT++ on the ORE test suite. 2
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 the signature of that axiom, i.e. the 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 the 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 can 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.
This also explains the choice of ?-locality in our approach. It is possible to de ne >-locality in a similar manner (replace all entities not in signature with >), and use it for the module extraction. Module extraction could be also done in a more complex manner, called ST AR, interleaving > and ? extraction passes until a xpoint is reached. However, >-local modules are usually larger than ?-local ones, so there is no reason to use them. The ST AR modularisation, although provides slightly smaller modules, does not ensure properties from Proposition 1, that are necessary for our approach. 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 optimisations 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 tradeo 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 least recently used (LRU) caches; this has shown to perform rather well in some of our tests, 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
Future Improvements There is one more optimisation 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 optimisation 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. 4
In this paper we present the comparison between three reasoners that have something in common.
Chainsaw is an OWL 2 DL reasoner that uses modularity to improve query
answering for large and complex ontologies. FaCT++ [
Characteristic OWL 2 pro le supported Interfaces Algorithms Optimisations Advantages Disadvantages Application focus
Chainsaw
AD/sub-reasoner meta-reasoning sub-reasoner scalability; good modularity approximation AD overhead large ontologies
JFact EL, RL, QL, DL
OWLAPI tableaux same as FaCT++ pure Java; extended DT
FaCT++ OWLAPI, LISP tableaux
N/A good general performance work in progress OWLAPI interface
is complicated general purposes
Some notes about the table. The algorithm used in Chainsaw for answering hierarchical queries is based on Labelled Atomic Decomposition. For entailment queries an algorithm used in the chosen sub-reasoner is applied. The architecture
provides the possibility of using di erent kinds of reasoners for di erent queries, so that more e cient reasoners can be used when possible; however, our current implementation does not provide this functionality yet.
We are not going to say much about FaCT++ and JFact here; the optimisations used in FaCT++ are described in a number of publications [6{9], and JFact is a port of FaCT++, so it uses the same techniques and contains the same optimisations. The advantage of Chainsaw is the focus: for every query it uses only the necessary part of the ontology. This allows it to work in situations where the ontology is too large and complex to be dealt with by any other reasoner. So we see the main application area of Chainsaw as large and complex ontologies. Both FaCT++ and JFact are general purpose reasoners, which can be easily integrated in any application that uses OWLReasoner interface. In addition to that, FaCT++ could be used directly from C and C++ programs.
Summarising the paper results, the main disadvantage of Chainsaw is the overhead that is brought in by the need to build a LAD and maintain a number of sub-reasoners that answers particular entailment queries. JFact is still a work in progress, so there is a high variance in performance depending on the task. Also, it has a small user base, by which we mean that there are probably bugs which have not been found yet. FaCT++ main problem, when used from Java applications, is its JNI interface, which makes it cumbersome to set up in some environments; for example, in web applications, native libraries are not straightforward to load and work with, and an error might cause issues to the whole application server. The datatype support is not very re ned at the time of writing as well. 5
To check the performance of Chainsaw we ran several tests with it. For the tests we used a MacBook 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++ and JFact v 0.9.
In Table 2 we present the results coming from the ORE test suite, speci cally the number of tests that our reasoners failed; these failures are either timeout failures or problems with some unsupported feature of the input ontologies.
As reported in the Total row, Chainsaw has the least amount of failures, while JFact has the highest; this can be explained in terms of time needed for the tasks: we know already that JFact performances are worse than FaCT++, and Chainsaw does not need to perform all tasks on the whole ontology. This gives it an edge over both JFact and FaCT++ in the case of large/complex ontologies; although FaCT++ is much faster on smaller ontologies, larger ontologies push it over our ve minutes timeout, thus causing a failure.
We do not report detailed timings for every task in the test suite. Instead, for every task we select the minimal time for successfully completing the task Task Classi cation Class Sat Ontology Sat Pos. Entailment Neg. Entailment Retrieval Total and use it to calculate a normalised performance index for each reasoner. This provides a relative measure on how good a reasoner is compared to the others.
The index is calculated for the initialisation of a reasoner and for performing the task itself. We then average this index for every reasoner over all the ontologies in every test suite task, and the resulting values are in Table 3.
Task Classi cation Class Sat Ontology Sat Pos. Entailment Neg. Entailment Retrieval
As can be seen from the data in Table 3, initialisation is a simple process for Chainsaw; in fact, it does very little work at this stage, while both JFact and FaCT++ do a substantial amount of loading and preprocessing; Chainsaw is instead delegating this work until it becomes necessary, i.e., at query answering time.
At query time, FaCT++ turns out to be the fastest reasoner by a large margin; Chainsaw comes second and JFact last. Chainsaw is faster in the retrieval task, but its results were checked manually and they are incorrect; the speed is therefore probably due to a bug in the modularisation code that is used for building the module to be used, and its good performance should not be taken into account.
It is worth mentioning that Chainsaw average includes the ontologies on which the other reasoners failed; therefore, we can conclude that, while slower than FaCT++, it can provide answers in cases in which the other reasoners would not be able to answer in a timely manner at all.
In this paper, we presented the relative performances of the three reasoners, and listed their advantages and disadvantages. From these results, we deduce that Chainsaw has the potential of providing acceptable performances where other reasoners fail; it also emerges that its current performances in other cases are not on a par with more mature reasoners such as FaCT++. We consider this an encouraging result, and we presented a few improvements that are already under development.