We investigate possible improvements to the existing algorithm for classifying EL+ TBoxes. We present a modi ed algorithm based on the well-known linear closure algorithm from relational databases. Despite its better worst-case complexity, surprisingly it turns out that this algorithm does not perform well in practice. We discuss optimizations to the existing algorithm and evaluate them using our prototypical reasoner cheetah on several large bio-medical knowledge bases.
In [9, 8] Brandt has shown that the tractability result in [
Successful applications of the E L family increased investment of further work in this direction. The E L family now provides the basis for the pro le OWL2 EL1. Moreover, there are now a few other reasoners speci cally tailored for the E L family, like Snorocket [16] and TrOWL [21], and CB [15], which extends the E L++ algorithm to Horn SHIQ. A comprehensive study comparing the performace of several reasoners on large bio-medical knowledge bases has been presented in [13].
In the present work we investigate possible improvements to the existing classi cation algorithm for the E L family. We present a modi ed algorithm based on the well-known linear closure algorithm [7] from relational databases [17]. We evaluate both the modi ed algorithm and the implementation of the simple 1 http://www.w3.org/TR/owl2-pro les/#OWL 2 EL algorithm in our prototypical E L+ reasoner cheetah on several large knowledge bases from life sciences. Surprisingly, it turns out that despite its better worst-case complexity, the modi ed algorithm performs worse than the simple algorithm in practice. In Section 2 we introduce the linear closure algorithm from relational databases. In Section 3 we present our modi ed algorithm based on linear closure, and in Section 4 we present our experimental results. 2
In relational databases [17], speci cation of constraints on data is of crucial importance for correct modelling of the world and correct design of the database schemas. One way of specifying constraints is using functional dependencies introduced in [10]. A functional dependency occurs when the values of a tuple on one set of attributes uniquely determine the values on another set of attributes. Formally, given a relation r and a set of attribute names R, a functional dependency (FD) is a pair of sets X; Y R written as X ! Y . The relation r satis es the FD X ! Y if the tuples with equal X-values also have equal Y-values. In this case, one says that the set of attributes X functionally determine the set of attributes Y .
Given a set of FDs F and an FD X ! Y , one interesting question is whether
F implies X ! Y , i.e., whether every relation that satis es all FDs in F also
satisfy X ! Y , which we denote as F j= X ! Y . In order to answer this, one
can compute the smallest set of all FDs that F implies by using a set of inference
axioms called Armstrong's axioms [
In [7] Beeri and Bernstein have given an algorithm for e ciently computing closure under a set of FDs. Brie y, for each attribute the algorithm keeps an index pointing to the set of FDs whose left handsides contain that attribute. Additionally, for each FD it keeps a counter whose value is initally the size of the left handside of that FD. Initialization of these data structures is shown in the procedure Initialization in Algorithm 1.
For computing the closure of a set of attributes x under a set of FDs F it keeps a queue update which is initally equal to x. In the procedure Closure it repeatedly fetches and removes an attribute from update and decrements the 2 Note that, from the viewpoint of logic, computing closure is computing consequences in propositional Horn logic. In fact, the notions we have de ned can easily be reformulated in propositional logic when we view the attributes as propositional variables. Algorithm 1 The Linear Closure Algorithm Procedure: Initialization 1: for all FD W ! Z 2 F do 2: count[W ! Z] := jW j 3: for all attribute A 2 W do 4: list[A] := list[A] [ fW ! Zg 5: end for 6: end for 7: newdep := update := x Procedure: Closure 1: while update 6= ; do 2: choose an A from update 3: update := update n fAg 4: for all FD W ! Z 2 list[A] do 5: count[W ! Z] := count[W ! Z] 1 6: if count[W ! Z] = 0 then 7: add := Z n newdep 8: newdep := newdep [ add 9: update := update [ add 10: end if 11: end for 12: end while
return newdep counters of FDs that contain this attribute in the left handside. Once a counter becomes zero, it extends the queue update and the closure newdep with the new attributes on the right handside of that FD. This continues until the queue update becomes empty.
Note that the initialization takes at most jF j:jW j time, which is linear in the size of the input. Now consider the closure computation: Each attribute can enter update at most once. For each attribute A fetched from update the counters of the FDs in list[A] are decremented, which is performed at most W !Z2F jW j times. If the counter of any FD W ! Z becomes 0, then the new attributes in Z are added to update and newdep. If the involved sets are represented as bit vectors, this operation takes time proportional to W !Z2F jZj.
Since all steps of the algorithm can be performed in time linear in the sizes of FDs F and the set of attributes, the algorithm has complexity O(n). 3
A Modi ed Algorithm for classifying E L+ TBoxes In the present section we present an EL+ classi cation algorithm based on the linear closure algorithm introduced in the previous section. EL+ is the DL allowing for the top concept >, conjunction C u D, existential restriction 9r:A, general concept inclusion axioms (GCIs) C v D and role inclusion axioms (RIs) r1 rn v s, where A is an atomic concept, r an atomic role, and C; D concept descriptions. RIs are interpreted as r1I rnI sI , where denotes composition of binary relations.
In [9, 8] Brandt has shown that the tractability result in [
In [
In the following, we present an algorithm based on the linear closure algorithm introduced in the previous section. We exploit the similarity between computing closure under a set of functional dependencies and computing the set of subsumers of a concept. In its simplest form, one can view a GCI that consists of conjunctions of concept names on both sides as an FD. In this case, computing the subsumers of a concept w.r.t. a set of such GCIs trivially boils down to computing the closure of that concept under that set of GCIs, and classifying the TBox boils down to computing the closure of every concept name occurring in the TBox. For the general case, where TBox contains RIs, and where GCIs contain existential restrictions, the inferences due to these should of course also be taken into account.
As in the existing algorithm, we rst transform the TBox into a normal
form. Our normal form slightly di ers from the original one introduced in [
Given a TBox T we write CNT and CNT> to denote the sets of concept names occurring in T with and without the top concept, respectively. Likewise we write RNT to denote the set of role names occurring in T . We say that T is in normal form if 1. all GCIs in T are of the form
C1 u : : : u Cn v D1 u : : : u Dm
where Ci is either a concept name from CNT> or is of the form 9r:A, and Dj
is either a concept name from CNT or is of the form 9r:A where A 2 CNT>
and r 2 RNT .
2. all role inclusions are of the form r v s or r1 r2 v s where r1; r2; s 2 RNT .
Basically, a normalized GCI consists of conjunctions on both sides where
conjuncts are either concept names or existentially quanti ed concept names. Role
inclusion axioms are normalized exactly the same way as in [
In addition to these, for every concept name we keep an index pointing to the list of GCIs that contain this concept name on the left handside. This information is stored in list(A) for A 2 CNT . As in the original algorithm we keep a subsumer list S(B) for each concept name B. Unlike the original algorithm in addition to concept names this list also contains concept descriptions of the form 9r:A where A 2 CN>. Therefore we do not have the data structure R( ; ) in the
T original algorithm for storing relations.
Having explained the data structures we are now ready to give the algorithm. The rst procedure properly initializes the data structures count[ ][ ], list( ), q( ), and S( ).
Algorithm 2 initialize the data structures Procedure: Initialization 1: for all GCI = dfC1; : : : ; Cng v dfD1; : : : ; Dmg 2 T do 2: for all A 2 CNT do 3: count[A][ ] = n 4: end for 5: for all C 2 fC1; : : : ; Cng do 6: list(C) = list(C) [f g 7: end for 8: end for 9: for all A 2 CNT do 10: q(A) = fA; >g 11: S(A) = fA; >g 12: end for
Next we describe the processing of the stacks. Upon popping an entry (a normalized concept description) C from q(A) we call process-concept-name if C is a concept name, and process-existential-restriction if C is an existential restriction. Later we traverse the GCIs that have C on the left handside and decrement the counters for A. If the counter count[A][dfC1; : : : ; Cng v dfD1; : : : ; Dmg] becomes zero, we extend S(A) and q(A) with the new concept descriptions in fD1; : : : ; Dmg.
A concept name fetched from the stack of A is processed as in Algorithm 4, and an existential restriction popped from the stack of A is processed as shown in Algorithm 5. Here vT denotes the re exive transitive closure of the role hierarchy axioms in the normalized TBox. Processing of the stacks continues until Algorithm 3 process stack entry C popped from q(A) Procedure: process-stack-entry(A,C) 1: if C 2 CNT then 2: process-concept-name(A,C) 3: end if 4: if C = 9r:E then 5: process-existential-restriction(A,9r:E) 6: end if 7: for all GCI = dfC1; : : : ; Cng v dfD1; : : : ; Dmg 2 list(C) do 8: count[A][ ] = count[A][ ] - 1 9: if count[A][ ] = 0 then 10: q(A) = q(A) [ fDi j Di 62 S(A)g 11: S(A) = S(A) [ fDi j Di 62 S(A)g 12: end if 13: end for Algorithm 4 process the concept name B popped from q(A) Procedure: process-concept-name(A,B) 1: for all D 2 CNT s.t. 9r:A 2 S(D) and 9r:B 62 S(D) do 2: q(D) = q(D) [ f9r:Bg 3: S(D) = S(D) [ f9r:Bg 4: end for all stacks q( ) are empty. Note that our algorithm di ers from the \re ned" algorithm introduced in [5, 6] only in the way how the stacks (there queues) are processed, and how axioms that apply at a particular step are detected. In principle it still performs exactly the same operations in the \abstract" algorithm introduced there. That is, it still performs the completion rules in [5, 6]. In fact, the lines 9-11 of Algorithm 3 implement the completion rules R1, R2 and part of R3 in [6]. Lines 2-4 of Algorithm 5 implement rest of R3, and the whole process-existential-restricton procedure implement rules R4 and R5. Since we do not modify the original abstract algorithm in [5, 6] we do not need to give proof of correcteness of our algorithm here.
It has been shown in [6, 20] that the re ned algorithm there makes at most n4 additions to the subsumer list S( ) and to the queues used, where n is the size of the normalized TBox. For every addition to S( ) this algorithm performs a subset check in order to decide whether the fetched axiom from the queue is applicable at that step or not. This subset check brings an overhead which in the worst-case is n, thus the overall runtime of the original algorithm is O(n5).
The counters used by our algorithm allow us to check whether an axiom applies without doing the subset check mentioned above, thus avoid the n-step overhead in the worst-case. Basically, this is how our algorithm achieves a better worst-case complexity O(n4) instead of the O(n5) worst-case complexity of the original algorithm.
Algorithm 5 process the existential restriction 9r:E fetched from q(A) Procedure: process-existential-restriction(A,9r:E) 1: for all s 2 RNT s.t. r vT s do 2: for all D 2 CNT s.t. D 2 S(E) and 9s:D 62 S(A) do 3: q(A) = q(A) [ f9s:Dg 4: S(A) = S(A) [ f9s:Dg 5: end for 6: for all D 2 CNT s.t. 9x:A 2 S(D) and 9y:E 62 S(D) and x; y 2 RNT s.t.
x s v y 2 T do 7: q(D) = q(D) [ f9y:Eg 8: S(D) = S(D) [ f9y:Eg 9: end for 10: for all D 2 CNT s.t. 9x:D 2 S(E) and 9y:D 62 S(A) and x; y 2 RNT s.t.
s x v y 2 T do 11: q(A) = q(A) [ f9y:Dg 12: S(A) = S(A) [ f9y:Dg 13: end for 14: end for 4
In order to evaluate the runtime behaviour of our modi ed algorithm, we have implemented it and performed a series of tests on large bio-medical knowledge bases: Foundational Model of Anatomy3 (FMA) is a large but simple TBox that contains 75139 concept names. Similarly, the Gene Ontology 4 (GO) and National Cancer Institute Thesaurus 5 (NCI) are large knowledge bases with shallow hierarchies. The GO contains 25070 concept names, and the NCI contains 27652 concept names. We have stripped down Galen 6 by removing functionalities and inverse roles to obtain the knowledge base Galen , which contains 23136 concept names. Finally we have also used the very large knowledge base SNOMED 7, which contains 293707 concept names. We have implemented the algorithm in the C programming language due to its speed and e cient use of the memory, which is important for dealing with these large knowledge bases. Currently our implementation can only read E L+ knowledge bases written in OWL 2 Functional-Style Syntax. We have implemented the parser for this syntax using the tools lex and yacc, which are used for generating lexical analyzer and parser for a given grammar.
In order to evaluate its performance, we have implemented the modi ed algorithm presented above, in our prototypical reasoner cheetah8. We have 3 http://sig.biostr.washington.edu/projects/fm/AboutFM.html 4 http://www.geneontology.org/ 5 http://www.cancer.gov/cancertopics/cancerlibrary/terminologyresources 6 http://www.co-ode.org/galen/ 7 http://www.nlm.nih.gov/research/umls/Snomed/snomed main.html 8 http://code.google.com/p/cheetah
FMA GO NCI SNOMED Galen
compared its performance with the performance of the simple algorithm that
performs subset checks instead of maintaining counters in order to decide when
to apply an axiom. The simple algorithm still uses the normalization rules
introduced in Section 3.1, and stacks for keeping track of concepts still to be processed,
but does not use counters. Instead, for a concept name B popped from q(A), it
compares the left handsides of axioms containing B with the current subsumers
of A, and applies an axiom if the former is a subset of the later. In our
comparison we have also involved the CB Reasoner9 that has been introduced in [15].
The underlying algorithm of the CB Reasoner extends the E L++ classi cation
algorithm in [
The results of our experiments were surprising. Despite its better worst-case complexity, in practice our modi ed algorithm performed worse than our implementation of the simple algorithm. The results of our experiments are shown in Table 1, where cheetah represents the implementation of our modi ed algorithm, and cheetah the implementation of the simple algorithm. The experiments are run on a computer with an Intel Core i3 processor running at 2.1 GHz, 8 GB of main memory and on the Linux operating system with 2.6.38 kernel. As seen in Table 1, the modi ed algorithm performs always worse than the simple algorithm. A closer look into the input knowledge bases reveals that the worst-case, i.e., axioms with very long conjunctions on the left handsides do not occur in practice. In fact, in SNOMED the longest conjunction on the left handside of a GCI is 12, for the Galen version we used it is 5, for FMA, GO and NCI it is just 1. When it comes to average size of conjunctions on the left hand side, for SNOMED it is 1.30 and for Galen it is 1.29, which are very small compared to the number of concept names occurring in these knowledge bases. This explains the poor performance of the modi ed algorithm. The worst-case, i.e., large conjunctions on the left handsides, does not occur in any of the knowledge bases we have used in our experiments. In practice the conjunctions on the left handsides are so small that even plain subset check is fast enough compared to the overhead of maintaining the counters.
According to the table the CB Reasoner performs in general better than both cheetah and cheetah . This is due to our unoptimized implementation of the processing of stacks. CB spends a big portion of the runtime for loading 9 http://code.google.com/p/cb-reasoner and normalizing the knowledge base however it is very e cient in computing the subsumer lists. For instance for SNOMED in our experiments it took CB 13.99 seconds to load and normalize the knowledge base, and only 21.47 seconds to compute the subsumer lists. On the other hand for cheetah loading and normalizing the knowledge base took 3.9 seconds, and computing the subsumer lists took 84.13 seconds. 5
We have investigated a modi cation to the E L+ classi cation algorithm for improving its worst-case complexity. It turned out the modi ed algorithm performs worse in practice. However, there is some room for further improvement of both the modi ed and the simple algorithm. During the execution of both algorithms, some axioms are applied several times, which in principle could be avoided. For instance if we are processing the stack of concept name A and nd out that A is subsumed by B, we can skip the axioms already applied while computing the subsumers of B and just extend the subsumer list of A with that of B. This would bring the overhead of keeping track of which axioms have already been applied for which concept name, but save the e ort of applying those axioms again. One other possible improvement is to make use of the axioms that have only one concept name or existential restriction, i.e., no conjuction on the left handside. One can apply such axioms immediately before the execution of the algorithm, thus pre- lling the stacks and subsumer lists with told-subsumers appropriately.
As future work we are going to implement and test these further improvements. In addition to this, we are going to extend the cheetah reasoner to support the OWL2 EL Pro le and improve its usability by providing a platform independent Java interface and a Protege plugin for it.
Acknowledgements: We would like to thank Yevgeny Kazakov for giving his remarks and providing information about the CB Reasoner. 5. F. Baader, C. Lutz, and B. Suntisrivaraporn. CEL|a polynomial-time reasoner for life science ontologies. Proceedings of the 3rd International Joint Conference on Automated Reasoning (IJCAR'06), volume 4130 of Lecture Notes in Arti cial Intelligence, pages 287{291. Springer-Verlag, 2006. 6. F. Baader, C. Lutz, and B. Suntisrivaraporn. Is tractable reasoning in extensions of the description logic EL useful in practice? In Journal of Logic, Language and Information, Special Issue on Method for Modality (M4M), 2007. To appear. 7. C. Beeri and P. A. Bernstein. Computational problems related to the design of normal form relational schemas. ACM Transactions on Database Systems, 4(1):30{ 59, 1979. 8. S. Brandt. On subsumption and instance problem in ELH w.r.t. general tboxes.
Proceedings of the 2004 International Workshop on Description Logics, (DL2004), volume 104 of CEUR Workshop Proceedings. CEUR-WS.org, 2004. 9. S. Brandt. Polynomial time reasoning in a description logic with existential restrictions, gci axioms, and - what else? Proceedings of the 16th Eureopean Conference on Arti cial Intelligence, (ECAI 2004), pages 298{302. IOS Press, 2004. 10. E. F. Codd. A relational model of data for large shared data banks. Communications of ACM, 13(6):377{387, 1970. 11. T. G. O. Consortium. Gene ontology: Tool for the uni cation of biology. Nature
Genetics, 25:25{29, 2000. 12. R. Cote, D. Rothwell, J. Palotay, R. Beckett, and L. Brochu. The systematized nomenclature of human and veterinary medicine. Technical report, International, North eld, IL: College of American Pathologists, 1993. 13. K. Dentler, R. Cornet, A. ten Teije, and N. de Keizer. Comparison of reasoners for large ontologies in the owl 2 el pro le. Semantic Web Journal, 2011. To appear. 14. W. F. Dowling and J. H. Gallier. Linear-time algorithms for testing the satis ability of propositional Horn formulae. Journal of Logic Programming, 3:267{284, 1984. 15. Y. Kazakov. Consequence-driven reasoning for horn shiq ontologies. Proceedings of the 21st International Joint Conference on Arti cial Intelligence, (IJCAI 2009), pages 2040{2045, 2009. 16. M. Lawley and C. Bousque. Fast classi cation in protege: Snorocket as an owl2 el reasoner. In Proceedings of Australasian Ontology Workshop, 2010. 17. D. Maier. The Theory of Relational Databases. Computer Science Press, Maryland, 1983. 18. J. Mendez and B. Suntisrivaraporn. Reintroducing CEL as an OWL 2 EL reasoner.
Proceedings of the 22nd International Workshop on Description Logics (DL 2009), volume 477 of CEUR Workshop Proceedings. CEUR-WS.org, 2009. 19. A. Rector and I. Horrocks. Experience building a large, re-usable medical ontology using a description logic with transitivity and concept inclusions. In Proceedings of the Workshop on Ontological Engineering, AAAI Spring Symposium (AAAI'97).
AAAI Press, 1997. 20. B. Suntisrivaraporn. Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies. Ph.D. dissertation, Institute for Theoretical Computer Science, TU Dresden, Germany, 2009. 21. E. Thomas, J. Z. Pan, and Y. Ren. Trowl: Tractable owl 2 reasoning infrastructure. The Semantic Web: Research and Applications, 7th Extended Semantic Web Conference, (ESWC 2010), volume 6089 of Lecture Notes in Computer Science, pages 431{435. Springer-Verlag, 2010.