Ontologies are used in a variety of applications in domains such as healthcare, geoscience, IoT, and e-commerce. Many commonly used ontologies are manually constructed, and may not be large in size but could be very expressive. With the advances in automated knowledge base construction and ontology learning [2], it is becoming increasingly common to build very large ontologies. OWL 2 knowledge representation language, a W3C standard, provides several profiles such as OWL 2 Full, OWL 2 DL, OWL 2 EL, OWL 2 QL, and OWL 2 RL that vary in terms of their expressivity, and hence, the complexity of reasoning. While there are several existing reasoners [1] for different OWL profiles, including OWL 2 DL, they generally do not scale well for large ontologies and even medium-sized ontologies in the OWL 2 DL profile. Approximate reasoning [5] offers an attractive alternative in such cases by sacrificing either soundness or completeness in favor of reasoning runtime. Approximate reasoning is useful in applications where i) response time is crucial, or ii) the reasoning is performed in a resource-constrained environment, and iii) good enough answers from the reasoner are sufficient. TrOWL [4], is a well known approximate description logic reasoner that uses syntactic language weakening for approximating SROIQ TBox axioms to E L++ axioms. It also makes use of data structures to maintain complement and cardinality information. While offering significant improvements in reasoning runtime, TrOWL does not scale well for large ontologies (see Section 2). An alternate way of reducing the reasoning runtime is to better utilize the computing resources (multi-core, multi-processor architectures). ELK [3] is one such concurrent rule-based reasoner for +. Axioms are assigned to lock-free data structures called conttehxetsd,esacnrdipitniofenrelongciecsEaLre?computed independently and in parallel offering significant speedup when compared to the state-of-the-art. In this paper, we describe our ongoing efforts for developing a concurrent, approximate description logic reasoner. We propose to make use of the approximation rules of TrOWL and the concurrent strategy of ELK to create an efficient and concurrent approximate reasoner.
Introduction In this section, We compare the runtime performance of TrOWL (an approximate reasoner), ELK (a concurrent reasoner), and three other commonly used reasoners (Pellet, Hermit, and JFact). We use five different ontologies of varying sizes – GALEN (37,696 axioms), GO (107,909 axioms), FMA (126,548 axioms), Anatomy (268,513 axioms), and Snomed (569,701 axioms). In order to further test the reasoners’ scalability, we created interlinked copies of ontologies where independent copies of the ontologies are connected with each other. For example, this could lead to axioms such as A1 v B2, where A1 and B2 are copies of classes A and B in the original ontology. We report classification times achieved by different reasoners with 1, 5, and 10 interlinked copies (Table 1). The experiments were performed on an Intel(R) Xeon(R) 2.30GHz x86 64 server with 96GB RAM, 40 CPUs, 20 cores per CPU, and 2 threads per core. The maximum Java Heap Space allocated was 24GB and the timeout was set to 3600 seconds. The source code for replicating our experiments and creating interlinked ontologies is at https://github.com/kracr/dl-approx-reasoner. We observe from Table 1 that except for 1 copy of FMA ontology, JFact is not able to complete the reasoning tasks with in the specified time (1 hour) using available computing resources. Pellet and Hermit perform slightly better with 400 successful completion of the tasks for FMA on- 350 tology, but they also do not scale to other on- )sd300 tologies and their larger interlinked variants. Both (cseon220500 the variants of TrOWL successfully complete the em150 tasks, except for larger variants of Galen (5 and 10 iT100 copies) and Snomed (10 copies). ELK on the other 50 hand is able to successfully complete the tasks for 0 0 2 4 Num6ber8of P1a0rall1e2l W1o4rker1s6 18 20 all the ontologies, and their larger interlinked vari- Fig. 1. ELK Performance for 8 interants. Also note that except for Anatomy ontology, linked copies of Snomed using differELK outperforms TrOWL due to its concurrent ent no. of parallel workers architecture. For Anatomy, however, TrOWL outperforms ELK (even with 10 parallel processes). We speculate that this could be attributed to the nature of axioms present in the ontology and a large number of missing results due to TrOWL being a sound, but incomplete reasoner. We also note that the runtimes reduce with increasing the number of parallel workers employed by ELK (shown in parentheses). It was observed during experiments that large gains in performance could be achieved by increasing the number of parallel processes, and the gains saturate at about 10 parallel workers (Fig. 2). These experimental observations provide the motivating evidence for our efforts towards a concurrent approximate description logic reasoner that can scale to large, expressive ontologies and perform reasoning tasks efficiently in resource constrained environments. 3
Concurrent Approximate DL Reasoner
We extend the completion rules of ELK reasoner [
Algorithm Subsumption
2 if C.subs.add(D) then 3 if bottom.negOccurs>0 then 4 for each D2,G with C.subs(D2)and
Cardinality Links
2 if C.backCardLink.add(i; R; E) then 3 if C.subs.contains(bottom) then
E.enqueue(newSub(bottom)) conCompl(D2; G) and 4 conEq(D; G) do
C.enqueue(add(newSub(bottom))) 5 == R: for each G,H with conCompl(D; G) and conCompl(C; H) do
G.enqueue(newSub(H)) == R+ if D = bottom and C instanceOf : IdxConjunction and conCompl(C:secondConj; G) then
C.firstConj.enqueue(newSub(G)) == R
: if D instanceOf IdxCardinality then
D.filler.enqueue( newBackCardLink( D:card; D:role; C) C.enqueue( newF orwCardLink(
D:card; D:role; D:f iller) == Rc for each R,S,E,F with hier(R; S) and C.backCardLink(i; R; E) and D.backCardLink(j; S; F ) do
E.enqueue(newSub(F )) == Rc v 6 7 8 9 10 11 12 17 18 19 20 21 Algorithm 2: C.process(expression): Existential Links
2 if C.backLink.add(R; E) then 3 for each D; R2; S1; S2; S with C.forwCardLink(i; R2; D) and roleComp(S1; S2; S) and hier(R; S1) and hier(R2; S2) do
D.enqueue(newBackLink(S; E)) E.enqueue(newF orwLink(S; D))
7 if C.forwLink.add(R; E) then 8 for each E; R1; S1; S2; S with == Roc2 == Roc2 C.backCardLink(j; R1; E) and roleComp(S1; S2; S) and hier(R1; S1) and hier(R; S2) do
D.enqueue(newBackLink(S; E))
E.enqueue(newF orwLink(S; D)) 5 6
From among these 8 rules, one of the rules (R13 from [
R :
CvD
CvE :
Cv?
EviR:C
i,R
E !C 13 C.enqueue(Init); 14 C.process(ForwCardLink(i; R; D)): 15 if C.forwCardLink.add(i; R; D) then 16 for each E; R1; S1; S2; S with == Rc? == Rc+ == Roc1 == Roc3 for each D,F,S with C.subs(D) and negCard(i; S; D) and hier(R; S) do
E.enqueue(newSub(F )) for each D; R2; S1; S2; S with
D.enqueue(newBackLink(S; E)) E.enqueue(newF orwLink(S; D)) for eachD; R2; S1; S2; S with
D.enqueue(newBackLink(S; E)) E.enqueue(newF orwLink(S; D))
D.enqueue(newBackLink(S; E)) E.enqueue(newF orwLink(S; D)) == Roc1 for each E; R1; S1; S2; S with
and roleComp(S1; S2; S) and hier(R1; S1) andhier(R; S2) do == Roc3 D.enqueue(newBackLink(S; E)) E.enqueue(newF orwLink(S; D))
Rc+ E i;!RC Rv?OS
EviS:DCvD : iS:D occurs negatively in O
Roc1 E i!,RC Roc2 E !RC C i;R!2D : RR2vv?O?OSS12 Roc3 E i!,RC
E !SD S1 S2vS2O For efficient look-up of side conditions of inference rules, different look-up tables are constructed. For example, negConjs holds conjuncts of the form C u D. For the complement and cardinality rules, we added two additional look-up tables, conCompl and negCard. conCompl consists of pairs hA; :Ai for each concept A in the ontology. negCard holds information about qualified cardinality expressions in the form of tuple hi; S; D; iS:Di. For concurrent execution, contexts are assigned to each class expression on the basis of the inference rules. Every context c has a separate queue c.Todo and a set c.Closure which helps in achieving concurrency without using locks. c.Todo holds expressions that are yet to be processed and are initialized with the axioms from the input ontology. c.Closure holds all the processed expressions to which inference rules have already been applied. The expressions in c.Todo are represented with the corresponding number of parameters (Sub(D), BackLink(R; E), ForwLink(R; C), BackCardLink(R; E), ForwCardLink(R; C)), whereas the expressions in Closure are represented using tables for the respective types of expression (D 2 C.subs, hR; Ei 2 C.backLinks, hR; Ci 2 E, forwLinks hi; R; Ei 2 C.backCardLinks, hi; R; Ci 2 E.forwCardLinks). Note that two links (Back and Forw) are being used for both Existential R and Cardinality because let’s say we have expression E ! C; this expression would be added to both contexts E and C and similarly for cardinality E i,!R C (unlike expression of the form C v D which will be added to context C only). Adding an expression to contexts activates it and each item is taken by some worker (thread) for execution.
The pseudocode for the 10 rules of complement and cardinality are given in Algorithms 1, 2, and 3. When a worker takes an expression from c.Todo, c.process(expression) is called and depending on the type of that expression, one method from Algorithm 1, 2, or 3 is executed. On calling c.process(expression), expression is added to its corresponding c.closure and inferences are performed between elements of c.closure by applying inference rules given in the method body. Also, other than the expressions from c.closure, data structures such as concIncs, roleComps, conCompl, negCard, hier etc are used for efficient look-up of side conditions. Note that here we have given only additional rules in each method body but inferences would be drawn using these new rules and the original rules provided in ELK. We are currently implementing the proposed algorithms and modifications and plan to make the implementation available for the community to use and build upon.