OWL 2 EL is one of the tractable pro les of the Web Ontology Language (OWL) which has been standardized by the W3C. OWL 2 EL provides su cient expressivity to model large biomedical ontologies as well streaming tra c data. Automated generation of ontologies from streaming data and text can lead to very large ontologies. There is a need to develop scalable reasoning approaches which scale with the size of the ontologies. We brie y describe our distributed reasoner, DistEL along with our experience and lessons learned during its development.
nodes as well. The Java process on all the nodes work co-operatively to achieve the common goal of reasoning over the axioms which are distributed over the cluster. 2
DistEL can be used to classify any EL+ ontology, but is e ective on very large ontologies where the number of axioms are in the millions and more. Detailed instructions are given at https://github.com/raghavam/DistEL. Linux shell scripts are provided and can be used to run the steps described brie y here. 1. Enable passwordless ssh to all the machines in the cluster. 2. Specify the cluster information in the con guration le. 3. Normalize the ontology if not already normalized and load the axioms into the database present on each node of the cluster. 4. Classify the loaded ontology. Depending on the ontology, it takes several iterations to classify it. Final results are collected in the node speci ed in the con guration le. 3
Some of the highlights during the development of DistEL in terms of features, technologies, optimizations and the implementation e ort required are described here. 3.1
Classi cation algorithm consists of applying a set of rules to the axioms iteratively until no new inferences can be computed. Rules almost exclusively involve set operations. Based on this and the distributed nature of the implementation, following were the requirements from the database.
{ Very good read and write speed. It is not the case here that there are very less number of reads compared to writes or vice-versa. So, both read and write speeds are important. { Built-in set operations. If there is no built-in support, then client (Java reasoning process) should fetch the required data, perform the set operations and write it back. This is ine cient especially if the data has to be fetched from a non-local database. { Transaction support. In a distributed setup, there is a possibility that several requests can be sent to the same database by di erent processes. Atomicity of some operations is also required. { Random reads { Server-side scripting. Operations on large data is e cient if done at the server-side rather than fetching the data to the client side. { Batch processing. Network round-trip time on each message/request can be avoided if several operations can be batched together. { Scalability. As the data grows, the reads and writes should scale accordingly. { Good documentation and community support. { Support for Java. Since rest of the application is in Java, a good Java interface to the database is needed.
An in-memory key-value store provides excellent read/write speed. Among the options available, Redis has support for all the mentioned requirements. It is a single thread server that supports set operations, sharding and Lua2 scripts for server-side scripting. 3.2
Computing classi cation is an iterative process and at the end of each iteration,
a check is made to determine whether any new inferences have been derived
in this iteration. If there are no new additions, process is terminated. But in
a distributed setup, checking for termination condition is not straightforward
because reasoning process on each node of the cluster needs to know whether
any of the reasoning processes on other nodes have derived any new inference.
If a new inference has been derived, only in that case will a reasoning process
go to the next iteration. Note that, this requires each process to wait for all
the other processes to complete their current iteration. This is achieved through
barrier synchronization [
Barrier synchronization in DistEL is implemented using a combination of status message broadcast by each reasoning process to all others and the blocking wait feature of Redis. A status message is a simple UPDATE/NO-UPDATE indicating whether a new inference has been derived or not by a speci c process. Each process can be made to block until it receives status messages from the reasoning process on all the other nodes. 3.3
When a process reaches the barrier, instead of waiting, it can help other busy
processes. The idle process steals a xed set of axioms from the busy process
[
To the best of our knowledge, there is no freely usable distributed work stealing Java library. So we implemented work stealing in DistEL using Lua
scripting and Java. The idle process runs a script against the database of the busy process. The script rst checks if there are any chunks available for stealing, and if they are, it adjusts the chunk counter on the busy process and retrieves the chunk for local processing. Note that this script should be run atomically and Redis ensures the atomicity of Lua scripts. After the idle process gets the chunk, it should temporarily implement the same functionality as that of the busy process since the data obtained corresponds to the busy process. After processing this chunk, the idle process looks for another chunk and steals it. This continues until no chunks are available on any of the database processes. 4
We brie y describe our experience and lessons learned during the development of DistEL.
{ In a distributed system, debugging synchronization and timing issues (race
conditions) is hard since it makes the results non-deterministic. Each run
would give a di erent result. While debugging, it is best to consider the
smallest available dataset as input. This should be small enough to hand
trace the output and possible steps taken during execution. In this case,
timing issues can be traced since we already know the order.
{ We could not nd any unit testing frameworks that can simulate a
distributed setup involving a key-value store. Due to this, more time was spent
on debugging than on coding. Reasoning related errors can be debugged
using the explanation (justi cation) feature [
It not only deploys the job on each node but also collects the output from each node.
Acknowledgements: This work was supported by the National Science Foundation under award 1017225 \III: Small: TROn - Tractable Reasoning with Ontologies." Any opinions, ndings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily re ect the views of the National Science Foundation.