Automated generation of axioms from streaming data, such as tra c and text, can result in very large ontologies that single machine reasoners cannot handle. Reasoning with large ontologies requires distributed solutions. Scalable reasoning techniques for RDFS, OWL Horst and OWL 2 RL now exist. For OWL 2 EL, several distributed reasoning approaches have been tried, but are all perceived to be ine cient. We analyze this perception. We analyze completion rule based distributed approaches, using di erent characteristics, such as dependency among the rules, implementation optimizations, how axioms and rules are distributed. We also present a distributed queue approach for the classi cation of ontologies in description logic EL+ (fragment of OWL 2 EL).
The rate at which data is generated is increasing at an alarming rate in this age
of Big Data. Data processing techniques should also scale up correspondingly.
This also holds true in the case of OWL ontologies and reasoning. Manually
constructed ontologies would most likely remain small or medium-sized, in the
order of several thousands or up to a few million axioms. Generating axioms
automatically from streaming data such as tra c [
While some progress has been made regarding scalable reasoning over RDFS,
OWL Horst and OWL 2 RL [
Rest of the paper is as follows. Section 2 contains a brief description of EL+ and classi cation. In Section 3, three approaches to distributed reasoning are
Normal Form Completion Rule A1 u u An v B R1 If A1; : : : ; An 2 S(X), A1 u
then S(X) := S(X) [ fBg A v 9r:B R2 If A 2 S(X), A v 9r:B 2 O, and (X; B) 62 R(r)
then R(r) := R(r) [ f(X; B)g 9r:A v B R3 If (X; Y ) 2 R(r), A 2 S(Y ), 9r:A v B 2 O, and B 62 S(x) then S(X) := S(X) [ fBg r v s R4 If (X; Y ) 2 R(r), r v s 2 O, and (X; Y ) 62 R(s)
then R(s) := R(s) [ f(X; Y )g r s v t R5 If (X; Y ) 2 R(r), (Y; Z) 2 R(s), r s v t 2 O, (x; Z) 62 R(t) then R(t) := R(t) [ f(X; Z)g Table 1. Completion rules for classifying EL+ ontologies u An v B 2 O, and B 62 S(X) described. Section 4 o ers alternative evaluation strategies. In Section 5, some possible future directions are mentioned and Section 6 contains some related work. We conclude in Section 7. 2
We brie y introduce the description logic EL+. Let the concept names be denoted by NC , role names by NR and NC> denotes NC including >. Concepts in EL+ are formed according to the grammar
A ::= C j > j A u B j 9r:B where C 2 NC>, r 2 NR, and A; B over (possibly complex) concepts. An EL+ ontology is a nite set of general concept inclusions (GCIs) A v B and role inclusions (RIs) r1 rn v r, where A; B 2 NC>, n is a positive integer and r; r1; : : : ; rn 2 NR.
The reasoning task that we consider here is classi cation { the computation of the complete subsumption hierarchy of all concept names occurring in the ontology. Other reasoning tasks such as concept satis ability can be reduced to classi cation. Classi cation is computed using a set of completion rules shown in Table 1. It requires the input ontology O to be in normal form, where all concept inclusions have one of the forms
A v B j A1 u : : : u An v B j A v 9r:B j 9r:A v B and all role inclusions have the form r v s or r s v t. A; A1; : : : ; An; B 2 NC> and r; s; t 2 NR.
The transformation into normal form can be done in linear time [
The classi cation rules make use of two mappings S and R, S : NC> 7! 2NC> , R : NR 7! 2(NC> NC>). Intuitively, B 2 S(A) implies A v B, while (A; B) 2 R(r) implies A v 9r:B. Before applying the rules, for each element X 2NC>, S(X) is initialized to contain fX; >g, and R(r), for each role name r, is initialized to ?. The sets S(X) and R(r) are then extended by applying the completion rules shown in Table 1. Here we consider two ways in which these rules are applied to the axioms, which are described in later sections.
Classi cation of ontologies using the completion rules is guaranteed to
terminate in polynomial time relative to the size of the input ontology, and it is
also sound and complete. Proofs can be found in [
In this paper, we consider only completion rule based distributed approaches for classi cation.
We use the terms node and machine interchangeably throughout the paper. 3
We analyze three di erent distributed approaches to EL+ classi cation. Among them two have been published previously. 3.1
Prologue Before embarking on a parallelization e ort, it will be useful to check how amenable it is for parallelization. Note that we are using the term parallelization to mean the following { group of processes co-operating with each other to accomplish a common goal. These processes could either be running on the same machine or on di erent machines. Here, we are interested in the latter, in which case, there is no shared memory.
Dependency among the completion rules of Table 1 is shown in Figure 1. Every rule is dependent on one or more rules. So, in this case, applying rules to axioms cannot be an embarrassingly parallel computation. When these rules are applied in a distributed environment, some amount of communication is required among the nodes handling the rules which slows down the system.
Contrary to this, in RDFS and OWL Horst, little or no dependency exists
among the rules and thus embarrassingly parallel computations are possible [
MapReduce Approach
Taking the lead from the application of MapReduce to RDFS and OWL Horst
reasoning, an attempt was made in [
MapReduce is a programming model for distributed processing of data on
clusters of machines [
Map : (k1; v1) 7! list(k2; v2)
Reduce : (k2; list(v2)) 7! list(v3)
The completion rules in Table 1 are slightly modi ed to suit the key-value nature of MapReduce approach. The modi ed rules are given in Table 2. In the map phase, preconditions of the rules are checked and in the reduce phase, conclusion of the rules are computed. For each concept X 2 NC> and r 2 NR, S(X) is initialized to fX; >g and R(r); P (X); Q(X) are initialized to ?. Rules R1, R3 and R5 from Table 1 cannot be dealt with using MapReduce approach, since they have multiple join conditions, which is the reason to split them in the modi ed rules.
The general strategy used in this approach is given in Algorithm 1. At the end of each iteration, duplicates are removed from S; R; P; Q. Algorithm terminates when there are no changes made by the application of all the rules.
From [
1. Pros Aspects such as parallelization and fault tolerance are taken care of by the framework. 2. Cons There are several disadvantages of this approach. a) Duplicates are generated and an extra step is required to remove the duplicates. b) Since there are dependencies among the rules (Figure 1), MapReduce approach may not best suited. c) In each iteration, the algorithm needs to consider only the newly generated data (compared to last iteration). It is di cult to detect and lter axioms that generate redundant inferences. d) In every iteration, axioms are again reassigned to the machines in the cluster. In the case of RDFS reasoning, schema triples are loaded in-memory and this assignment of schema triples to machines takes place only once. This is not possible in the case of EL+ reasoning. 3. Axiom Distribution Axioms are distributed randomly. 4. Rule Distribution In each iteration, all the machines in the cluster, apply the same rule on the local axioms. 5. Optimizations Rule R4 is taken care of in the reduce phase of rules R2 and
R5. So rule R4 need not be applied again.
Compared to the xpoint iteration method of rule application, it is claimed that
the queue based approach is e cient on a single machine [
For each concept in NC>, a queue is assigned. Instead of applying the rules mechanically, in the queue approach, appropriate rules are triggered based on the type of entries in the queue. The possible entries in the queue are of the S(X) fX; >g, for each X 2 NC> R(r) fg, for each r 2 NR P (X) fg, for each X 2 NC> Q(X) fg, for each X 2 NC> repeat
Old.S(X) S(X); Old.R(r) R(r); Old.P (X) P (X); Old.Q(X) Q(X); P (X) := P (X) [ apply R1-1; S(X) := S(X) [ apply R1-2; R(r) := R(r) [ apply R2; Q(X) := Q(X) [ (apply R3-1); S(X) := S(X) [ apply R3-2; R(r) := R(r) [ apply R4;
R(r) := R(r) [ apply R5; until ((Old.S(X) = S(X)) and (Old.R(r) = R(r)) and (Old.P (X) = P (X)) and (Old.Q(X) = Q(X))); Algorithm 1: General strategy for applying rules in MapReduce approach form B1; : : : ; Bn ! B0 and 9r:B with B1; : : : ; B0; B 2 NC> and r 2 NR. If n = 0, B1; : : : ; Bn ! B0 is simply written as B0. Ob is a mapping from a concept to sets of queue entries as follows.
{ if A1 u : : : u An v B 2 O and Ai = A; then A1 u : : : u Ai 1 u Ai+1 u : : : u An !
B 2 Ob(A) { if A v 9r:B 2 O; then 9r:B 2 Ob(A) { if 9r:A v B 2 O; then B 2 Ob(9r:A)
For each concept A 2 NC>, queue(A) is initialized to Ob(A) [ Ob(>). For each queue, an entry is fetched and Algorithm 2 is applied. The procedure in Algorithm 3 is called by process(A; X) whenever a new pair of (A; B) is added to R(r). Note that, for any concept A, Ob(A) does not change during the application of the two procedures (process, process-new-edge); S(A), queue(A) and R(r) keep changing.
In the distributed setup, axioms are represented as key-value pairs as shown in Table 4. For axioms of the form A1 u : : : u An v B, for each Ai (key) in the conjunct, (A1; : : : ; Ai 1; Ai+1; : : : ; An; B) is associated as its value. if X = B1; : : : ; Bn ! B0 and B0 2= S(A) then if B1; : : : ; Bn 2 S(A) then
continue with X B0 ; else
return; if X is a concept name and X 2= S(A) then
S(A) S(A) [ fXg; queue(A) queue(A) [ Ob(X); forall the concept names B and role names r with (B; A) 2 R(r) do queue(B) queue(B) [ Ob(9r:X); if X is an existential restriction 9r:B and (A; B) 2= R(r) then process-new-edge(A; r; B);
forall the role names s with r vOb s do
R(s) R(s) [ f(A; B)g; queue(A) queue(A) [ SfB0jB02S(B)g Ob(9s:B0); forall the concept names A0 and role names t; u do t s v u 2 O and (A0; A) 2 R(t) and (A0; B) 2= R(u) do process-new-edge(A0; u; B); forall the concept names B0 and role names t; u do s t v u 2 O and (B; B0) 2 R(t) and (A; B0) 2= R(u) do process-new-edge(A; u; B0);
H : K 7! N For each concept A, care is taken to map Ob(A), queue(A) and S(A) to the same node. This localizes the interaction (read/write) between these three sets, which in turn improves the performance. In order not to mix up the keys among these three sets, unique namespace is used along with the key. For example, O : A; Q : A; S : A, for Ob(A), queue(A) and S(A) respectively, but, for the hash function, A is used in all the three cases.
After the axioms are loaded, each machine applies Algorithm 2 to only the queues local to it. In order to read/write to the non-local values, each machine uses the hash function, H. Each machine acts as a reasoner and cooperates with other machines to get the missing values and perform the classi cation task.
A single process called Termination Controller (TC), keeps track of the status of computation across all the nodes in the cluster. TC receives either DONE or NOT-DONE message from each machine. A double check termination strategy is
Axiom
A v B A1 u : : : u An v B
A v 9r:B 9r:A v B
r v s r s v t followed here. TC waits till it receives a DONE message from all the machines in the cluster. It then asks all the nodes to check if any local queues are non-empty. This is required because, after a node is done with OneIteration (Algorithm 5), there is a possibility of other nodes inserting values in the queues of this node. If this condition does indeed arise then a NOT-DONE message is sent to TC. TC resets its state to NO-CHECK and implements the double check termination strategy again. The pseudocode of TC is given in Algorithm 4. To simplify, TC is single threaded and works on only one message at a time. Process named Job Controller runs on each node of the cluster and implements the queue based algorithm. This is shown in Algorithm 6.
This approach is implemented in Java and the key-value store used is Redis1. Our system is called DQuEL and the source code is available at https: //github.com/raghavam/DQuEL. We used a 13-node cluster with each node hav1 http://redis.io queues GetNonEmptyLocalQueues(); forall the queue A 2 queues do forall the entry X 2 A do
process(A; X); TC ! DONE;
OneIteration(); on TC ? CHECK-AND-RESTART ! f queues GetNonEmptyLocalQueues(); if queues is ; then
TC ! DONE; else
TC ! NOT-DONE; g on TC ? CONTINUE-WORKING ! OneIteration(); on TC ? TERMINATE ! terminate-self;
Algorithm 6: Job Controller ing two quad-core AMD Opteron 2300MHz processors and 12GB of heap size is available to JVM. Timeout limit was set to 2 hours.
Not-Galen, GO, NCI, SNOMED CT and 2-SNOMED ontologies were used for testing. The rst three are obtained from http://lat.inf.tu-dresden. de/~meng/toyont.html and SNOMED CT can be obtained from http://www. ihtsdo.org/snomed-ct. 2-SNOMED is SNOMED replicated twice. The time taken by some popular reasoners such as Pellet, jCEL and ELK on these ontologies is given in Table 5. Table 6 shows the classi cation times of DQuEL with varying nodes. 3.3.1 Analysis Although the results are good for smaller ontologies, this approach turns out to be ine cient for larger ontologies such as SNOMED CT. The following two factors contributes to the ine ciency. a) Batch processing of axioms is not possible because each entry in the queue could be di erent from the one processed before. It is a known fact that batch processing especially involving communication over networks improves the performance drastically. Batch
Ontology 1 node 7 nodes 13 nodes Not-Galen 153.77 147.07 41.37
GO 165.94 147.28 43.12
NCI 205.62 55.52 30.21 SNOMED CT TimeOut TimeOut TimeOut 2-SNOMED TimeOut TimeOut TimeOut
Table 6. Classi cation time (in seconds) of DQuEL processing has been used to the extent possible, but the approach described in the next section is more amenable to that. b) Not all data required for the queue operations is available locally. For example, data of the form Ob(9r:B) might be present on a di erent node. 1. Pros Good load balancing is possible since the hash function makes an attempt to distribute axioms across the cluster equally. 2. Cons Large ontologies like SNOMED CT generate many (X; Y ) values which makes rule R3 (Table 1) computation slow compared to other rules. This problem is alleviated in the approach described next, by choosing r as the key in R(r). This spreads R(r) across the cluster and enables more nodes to work on it. 3. Axiom Distribution It is a random distribution of axioms. 4. Rule Distribution In each iteration, all the rules are applied by every node in the cluster. 5. Optimizations R(r) sets involving role chains are duplicated as show in Table 4. This makes it easy to retrieve (X; Y ) pairs associated with either r or s in r s v t. 3.4
Distributed Fixpoint Iteration Approach
In xpoint iteration approach, the completion rules are applied on the axioms
iteratively until there are no changes to S(X); R(r). This idea is extended to
the distributed setting [
All the axioms in a normalized ontology fall into one of the normal form categories mentioned in Table 1. This allows axioms to be split into disjoint collections. Each such collection is assigned to a group of nodes in the cluster. Only one rule can be applied on axioms of a particular normal form. So this leads to a clear assignment of axioms and rules to nodes.
Architecture of this approach is shown in Figure 2. The number of nodes per group need not be the same across all the groups. Higher number of nodes are generally assigned to groups handling rules involving roles since they are generally slower.
U (X) is used instead of S(X) in this approach. In the naive xpoint iteration approach, in order to apply a rule such as R1 from Table 1 on axioms of the form A1 u : : : u An v B, each S(X) needs to be checked for the presence of A1; : : : ; An. With U (X), it turns into set intersection of conjuncts, which are generally small in number.
Termination is achieved with the help of barrier synchronization. At the end of each iteration, every node broadcasts a status message indicating whether any changes were made in this iteration and then waits for the other nodes to nish its current iteration. After receiving the update messages from all the nodes, if at least one node made an update then all the nodes continue with their next iteration. Algorithm terminates when no updates are made.
This approach is implemented in Java and makes use of Redis as the keyvalue store. The same cluster set up and ontologies as mentioned in the previous section are used here. This system is named DistEL and is available at https:// github.com/raghavam/DistEL. The classi cation time of DistEL across several nodes is given in Table 7. 3.4.1 Analysis Although the runtimes of DistEL are high compared to existing reasoners, it is better than the other approaches described so far. With more optimizations such as dynamic load balancing, the results can be further improved.
MapReduce approach and the approach described here, use xpoint iteration for classi cation. But compared to MapReduce approach, an important advantage is that nodes can communicate with each other. Since the completion rules are interdependent, inter-node communication makes this approach e cient relatively. Since a node deals with all axioms of the same type, batch processing can be used here. Communications involving network and database can be improved a lot with the help of batch processing. 1. Pros Axioms and rules are neatly divided across the cluster based on their type. 2. Cons Improper load balancing. 3. Axiom Distribution Axioms are distributed based on their normal form type. 4. Rule Distribution Group of nodes in the cluster handle the same type of rule.
All the rules are applied in parallel across the cluster. 5. Optimizations a) Batch processing b) only the newly made changes in the previous iteration are considered for the next iteration and c) for R(r) = f(X; Y )g, instead of considering r as the key (as done in Queue approach), (Y; r) is chosen as the key and value is X. Since distribution of set R(r) is based on the key, this leads to a better spread of R(r) across the cluster. 4
Comparing the performance of single machine reasoners with distributed reasoners is unfair; not only due to the nature of the computation involved but also due to the following reason. All things being equal, if the time taken on a single machine is t then on n nodes, it takes p t=n where p is the overhead, p 1. In the case of super linear speedup, p < 1. But, as we have seen from the results presented here, this reduction in runtime does not happen at all in the case of distributed reasoners. But are all things equal? Considering the steps in the algorithm in both the cases is the same, one main di erence is the computations in case of single machine reasoners takes place in-memory whereas for distributed approaches mentioned here either a database or a le system was used. The performance varies vastly in these cases.
A simple comparison of speeds is shown in Table 8. Integers are read and written to a HashMap in the case of RAM. For Redis, pipeline (batch operation) read and write are used. The code used for this experiment is available at https: //gist.github.com/raghavam/2be48a98cae31c418678. Admittedly, this is a rather simple experiment, but it shows the di erence in read/write speeds for simple operations. For read operation, usage of RAM is 43 times faster than Redis and 26 times faster than le. For write operation also, there is a similar variation in performance. For random read and write operations, Redis performs better than a le. 1. Re-implement existing reasoners by making use of the storage system that is used in the distributed model. For example, use Redis or a le in jCEL or ELK. 2. Simulate distribution using existing reasoners by running a reasoner on each node of the cluster. A messaging system can be used to facilitate communicate and exchange of missing data on each node. But the performance in this case depends on the axiom distribution. So care should be taken to follow the same axiom distribution model in case of the distributed approach. 5
Although some progress has been made in distributed OWL 2 EL reasoning,
current results clearly indicate that more needs to be done. Apart from further
optimizations to the approaches presented here, following can be tried.
{ Module based axiom distribution. For a given set of entities, a module
includes all the axioms that are relevant to them [
Apart from the work presented here, other approaches to distributed reasoning
of OWL 2 EL ontologies have been tried. Distributed resolution technique was
applied to EL+ classi cation in [
Though not distributed, parallelization of OWL 2 EL classi cation has been
studied in [
It is possible to have very large ontologies if axioms are generated automatically from streaming data or text. Reasoners should be capable of scaling up to these large ontologies. But, existing reasoners are severely handicapped by their use of only one machine. Scalable and distributed approaches to ontology reasoning is required. We reviewed and analyzed three distributed approaches to OWL EL ontology classi cation. Apart from this, we discussed some possible future directions and also evaluation strategies that can be followed to make the comparison fair between distributed and single machine approaches.
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.