Axiom Dependency Hypergraphs for Fast Modularisation and Atomic Decomposition Francisco Martı́n-Recuerda1 and Dirk Walther2 1 Universidad Politécnica de Madrid, Spain fmartinrecuerda@fi.upm.es 2 TU Dresden, Theoretical Computer Science Center for Advancing Electronics Dresden, Germany Dirk.Walther@tu-dresden.de Abstract. In this paper we use directed hypergraphs to represent the locality-based dependencies between the axioms of an OWL ontology. We define a notion of an axiom dependency hypergraph, where axioms are represented as nodes and dependencies between axioms as hyper- edges connecting possibly several nodes with one node. We show that a locality-based module of an ontology corresponds to a connected compo- nent in the hypergraph, and an atom of an ontology to a strongly con- nected component. Collapsing the strongly connected components into single nodes yields a condensed axiom dependency hypergraph, which contains the atomic decomposition of the ontology. To condense the ax- iom dependency hypergraph we exploit linear time graph algorithms on its graph fragment. This optimization can significantly reduce the time needed to compute the atomic decomposition of an ontology. We provide an experimental evaluation for computing the atomic decomposition of large biomedical ontologies, and for computing syntactic locality-based modules using the condensed axiom dependency hypergraph. 1 Introduction An axiom dependency hypergraph (ADH) for OWL ontologies is a directed hy- pergraph which explicitly represents the locality-based dependencies between axioms. This graph can be used to compute the atomic decomposition (AD) of an ontology [5]. Different to other hypergraph representations of ontologies [12, 10], the nodes represent axioms that are connected by hyperedges which explic- itly describe the locality-based dependencies between axioms. These hyperedges mimic the order in which axiom are included in a locality-based module by the module extraction algorithm [7]. Due to this particular hypergraph repre- sentation the correspondence between atoms of an ontology and the strongly connected components (SCCs) of its hypergraph becomes apparent. This allows us to employ standard algorithms from graph theory to compute atoms. Simi- larly, modules can be characterized as connected components in an ADH. The The second author is funded by the German Research Foundation (DFG) via the Cluster of Excellence ‘Center for Advancing Electronics Dresden’. notion of an ADH provides a new perspective on previous work on locality and atomic decomposition from the point of view of graph theory. Computing all SCCs in a directed hypergraph is an inherently quadratic pro- cess [1], whereas in a directed graph, it can be done in linear time wrt. the size of the graph [11, 13]. For several well-known biomedical ontologies from the NCBO Bioportal,1 many (if not all) of the locality-based dependencies between axioms can be represented by simple edges [9]. In the case that all dependencies between axioms of an ontology can be represented using simple edges only, the ADH is a directed graph, and its SCCs can be computed very efficiently. For ontologies containing axioms that exhibit dependencies which can only be represented using complex hyperedges, we can still benefit from the use of linear-time algorithm for computing SCCs in the graph fragment of the ADH. We have implemented a Java prototype for computing the atomic decomposi- tion and syntactic locality-based modules. We confirm a significant improvement in running time for prominent biomedical ontologies from the NCBO Bioportal compared against state-of-the-art implementations [14, 15]. The paper is organised as follows. In Section 2, we introduce the notion of minimal non-locality signature of an axiom which can be used to check whether an axiom is non-local wrt. a signature. In Section 3, we introduce the notion of an axiom dependency hypergraph, and we show how to characterize locality-based modules as well as atoms together with their dependencies. We demonstrate the applicability of the hypergraph-based approach with an evaluation of our Java prototype in Section 4. The paper is concluded in a final section. 2 Non-locality of Axioms In this paper, we consider ontologies formulated in the expressive description logic SROIQ [8] which underlies the Web Ontology Language OWL 2.2 For the evaluation, we consider prominent biomedical ontologies that are formulated in the light-weight description logic EL++ [2] which is at the core of the OWL 2 EL profile.3 For a detailed introduction to description logics, we refer to [3]. A module M of an ontology O wrt. a signature Σ is a subset of O that preserves all entailments formulated using symbols from Σ only. More formally, M ⊆ O is a module of O wrt. Σ if for all axioms α with sig(α) ⊆ Σ: M |= α iff O |= α, where sig(α) denotes the signature of α. The notion of syntactic locality has been suggested as a practical approach to computing approximations of minimal modules in polynomial time [7]. Syntactic locality for a signature Σ defines a set of axioms that are syntactically local wrt. Σ. We consider the syntactic locality-based notions ⊥-locality and >-locality, and we do not consider any semantic locality notion. An axiom α is local wrt. Σ if α is equivalent to a tautology after all symbols in α that are not in Σ have been replaced by either > or ⊥, respectively. Intuitively, α is local wrt. Σ if it does not state anything 1 http://bioportal.bioontology.org/ 2 http://www.w3.org/TR/owl2-overview/ 3 http://www.w3.org/TR/owl2-profiles/#OWL_2_EL about the symbols in Σ. An ontology can safely be extended with α or it can safely import α, where ‘safe’ means not changing the meaning of terms in Σ. We denote with ModOx (Σ), for x ∈ {⊥,>}, the x-local module of ontology O wrt. the signature Σ consisting of axioms that are not x-local wrt. Σ. We can check for the state of syntactic non-locality of an axiom in terms of signature containment. To this end, we introduce the notion of minimal non- locality signature for SROIQ axioms. Definition 1. Let α be an axiom, and let x ∈ {⊥,>} denote a locality notion. A Minimal non-x-Locality Signature for an axiom α is a signature Σ ⊆ sig(α) such that α is not x-local wrt. Σ, and Σ is minimal (wrt. set inclusion) with this property. The set of minimal non-x-locality signatures of α is denoted by MLS x ( α). a The notion of minimal non-locality signature turns out to be equivalent to the notion of minimal globalising signatures, which where introduced specifically for computing modules from an atomic decomposition [4]. The following example shows that there can be exponentially many minimal non-locality signatures for axioms formulated in a simple concept description language using merely conjunction and disjunction as operators. Example 1. Let α = (X11 t X12 t · · · t X1m ) u · · · u (Xn1 t Xn2 t · · · t Xnm ) v Y be an axiom. The minimal non-⊥-locality signature MLS⊥ (α) of α is as follows: MLS⊥ (α) = {{X1i1 , X2i2 , . . . , Xnin } | i1 , i2 , . . . , in ∈ {1, ..., m}} Then: |MLS⊥ (α)| = mn .  However, exponentially many minimal non-locality signatures can be avoided if the axiom is normalised. An ontology O is normalised by applying the nor- malisation rules presented in [10], which are an extension of the normalisa- tion for EL in [12]. Axioms of a normalised ontology have one of the follow- ing forms, where Ai ∈ NC ∪ {>}, Bi ∈ NC ∪ {⊥}, Ri ∈ NR ∪ inv(NR ), X, Y ∈ {∃R.B, (≥ n R.B), ∃R.Self | B ∈ NC , R ∈ NR ∪ inv(NR ), n ≥ 0} and `, m ≥ 0: α1 : A1 u . . . u A` v B1 t . . . t Bm α5 : X v Y α2 : X v B1 t . . . t Bm α6 : R1 v R2 α3 : A1 u . . . u A` v Y α7 : Dis(R1 , R2 ) α4 : R1 ◦ . . . ◦ R` v R`+1 where NC , NR are mutually disjoint sets of concept names and role names, inv(NR ) is the set of inverse roles r− , for r ∈ NR , and ∃R.Self expresses the local re- flexivity of R. The normalisation of O runs in linear time in the size of O. The normalised ontology is a conservative extension of O wrt. sig(O) [10].4 The following proposition can readily be seen. 4 The normalisation in [10] can straightforwardly be extended to SROIQ-ontologies. Then a normalised axiom can be of the forms as described, where Ai and Bi addi- tionally range over nominals. However, nominals are not contained in any minimal non-locality signature of a normalised axiom. Proposition 1. Let α be a normalised axiom. Then: |MLS⊥ (α)| = 1 and |MLS> (α)| ≤ 2. a We can apply additional normalisation rules to reduce the number of symbols on the left- and right-hand side of normalised axioms. Bounding the number of symbols in an axiom results in bounding the size of the minimal non-locality signatures of the axiom. We now give simple conditions under which normalised axioms are not syn- tactic local. Similar non-locality conditions are presented in the notions of ⊥- and >-reachability in [10]. Proposition 2 (Non-locality via Signature Containment). Let α be a normalised axiom. Let Σ be a signature. Then: α is not ⊥-local wrt. Σ iff one of the following holds: – sig(LHS(α)) ⊆ Σ if α is of the form α1 , α2 , α3 , α4 , α5 , α6 ; – sig(α) ⊆ Σ if α is of the form α7 ; Then: α is not >-local wrt. Σ iff α is of the form α7 or one of the following holds: – sig(RHS(α)) ∩ Σ 6= ∅ if α is of the form α3 , α4 , α5 , α6 ; – sig(RHS(α)) ⊆ Σ if α is of the form α1 , α2 . a 3 Axiom Dependency Hypergraph A directed hypergraph [6] is a tuple H = (V, E), where V is a non-empty set of nodes (vertices), and E is a set of hyperedges (hyperarcs). A hyperedge e is a pair (T (e), H(e)), where T (e) and H(e) are non-empty disjoint subsets of V. H(e) (T (e)) is known as the head (tail ) and represents a set of nodes where the hyperedge ends (starts). A B-hyperedge is a directed hyperedge with only one node in the head. Directed Hypergraphs with only B-hyperedges are called Directed B-hypergraphs. This is the only type of hypergraphs that we consider in this paper. A node v is B-connected (or forward reachable) from a set of nodes V 0 (writ- ten V 0 ≥B v) if (i) v ∈ V 0 , or (ii) there is a B-hyperedge e such that v ∈ H(e) and all tail nodes in T (e) are B-connected from V 0 . For a set of nodes V 0 ⊆ V, we denote with ≥B (V 0 ) the set ≥B (V 0 ) = {v ∈ V | V 0 ≥B v} of B-connected nodes from V 0 . In a directed hypergraph H, two nodes v1 and v2 are strongly B-connected if v2 is B-connected to v1 and vice versa. In other words, both nodes, v1 and v2 , are mutually reachable. A strongly B-connected component (SCC) is the set of all nodes from H which are all mutually reachable [1]. We allow an SCC to be a singleton set as the reachability relation is reflexive, i.e., any axiom is mutually reachable from itself. Directed B-hypergraphs can be used to explicitly represent the locality-based dependencies between axioms. Axiom dependency hypergraphs for ontologies wrt. the locality-based modularity notions are defined as follows. We use sig(S) to denote the signature of a set S of axioms. Definition 2 (Axiom Dependency Hypergraph). Let O be an ontology. Let x ∈ {⊥,>} denote a locality notion. The Axiom Dependency Hypergraph x x HO for O wrt. x-locality (x-ADH) is defined as the directed B-hypergraph HO = x x (V , E ), where – V x = O; and – e = (T (e), H(e)) ∈ E x iff T (e) ⊆ V x and H(e) = {β}, for some β ∈ V x , such that: (i) β ∈ / T (e), and (ii) β is not x-local wrt. sig(T (e)). a The nodes of the axiom dependency hypergraph are the axioms in the on- tology. Hyperedges are directed and they connect possibly many tail nodes with one head node. Note that a head node of a hyperedge is not allowed to occur in its tail. Intuitively, the tail nodes of an hyperedge e correspond to axioms that provide the signature symbols wrt. which the axiom represented by the head node of e is non-local. We can think of walking along hyperedges to access B- connected nodes as part of the process of how the module extraction algorithm computes a module by successively including axioms into the module. The notion of ADH for ontologies depends on the notion of syntactic locality. Using Prop. 2, we can equivalently define this notion using minimal non-locality signatures by replacing Item (ii) of Def. 2 with: (iib) Σ ⊆ sig(T (e)), for some Σ ∈ MLS x (β). An ADH HO contains all locality-based dependencies between different ax- ioms of the ontology O. These dependencies are represented by the hyperedges in HO . Note that HO contains exponentially many hyperedges, many of which can be considered redundant in the following sense. Definition 3. A hyperedge e in a directed B-hypergraph H is called redundant if there is a hyperedge e0 in H such that H(e) = H(e0 ) and T (e0 ) ( T (e). a A compact version of a directed B-hypergraph H is obtained from H by removing all redundant hyperedges while the B-connectivity relation between axioms is preserved. In the remainder of the paper, we consider ADHs that are compact. Notice that compact ADHs are unique and they may still contain exponentially many hyperedges. The number of hyperedges can be reduced to polynomially many by first normalising the ontology as discussed in Section 2. In the following, we characterise modules and atoms together with their dependencies in terms of ADHs for which B-reachability is crucial. 3.1 Locality-based modules in an ADH B-connectivity in an ADH can be used to specify locality-based modules in the corresponding ontology. A locality-based module of an ontology O for the signature of an axiom α (or a subset of axioms O0 ⊆ O) corresponds to the B-connected component in the ADH for O from α (or O0 ) [9]. Proposition 3. Let O be an ontology, O0 ⊆ O and Σ = sig(O0 ). Let ≥B be the B-connectivity relation of the x-ADH for O, where x ∈ {⊥, >}. Then: ModOx (Σ) = ≥B (O0 ). a However, ADHs do not contain sufficient information for computing a module for an arbitrary signature as the following simple example shows. Example 2. Let O = {α1 = A v C, α2 = C u B v D, α3 = D v A} and Σ = {A, B}. We have that Mod⊥ O (Σ) = {α1 , α2 , α3 }. The ⊥-ADH for O contains no hyperedge e with H(e) = {α2 } and, consequently, α2 cannot be reached via a hyperedge.  The problem can be solved by incorporating the signature Σ into the ADH. x x The Σ-extension HO,Σ of an x-ADH HO for an ontology O wrt. x-locality, x ∈ {⊥,>}, is defined as the ADH according Def. 2 but with Item (ii) replaced with: (iii) β is not x-local wrt. Σ ∪ sig(T (e)). Intuitively, no symbol in Σ contributes to the dependencies between axioms. Consequently, less axioms in the tail are needed to provide the signature for non- locality of β. Note that hyperedges that are non-redundant in the original ADH may become redundant in the Σ-extended ADH. The remaining hyperedges represent the dependencies between axioms modulo Σ. Example 3. Let O and Σ as in Ex. 2. The Σ-extension of ⊥-ADH for O contains the edge e = {{α1 }, {α2 }}. Hence, α2 can be reached via the hyperedge e. Axiom α1 is the only axiom that is not-⊥ local wrt. Σ. The B-connected nodes from α1 are the axioms in Mod⊥ O (Σ).  Given the Σ-extension of an ADH for an ontology, B-connectivity can be used to determine the axioms that are not local wrt. to Σ and to compute the corresponding locality-based module. x Proposition 4. Let O be an ontology, Σ a signature and x ∈ {⊥,>}. Let OΣ be the set of axioms from O that are not x-local wrt. Σ. Let ≥B be the B-connectivity relation of the Σ-extension of the x-ADH for O. Then: ModOx (Σ) = ≥B (OΣ x ). a 3.2 ADH Atomic Decomposition Atoms represent sets of highly related axioms in the sense that they always co- occur in modules [5]. We denote with AtomsxO the set of all atoms of O wrt. x-locality modules, for x ∈ {⊥,>}. The atoms of an ontology partition the set of its axioms (i.e., every axiom occurs in exactly one atom). A dependency relation between atoms can be established: an atom a2 depends on an atom a1 in an ontology O (written a1 }: α, β ∈ a if, and only if, ModOx (sig(α)) = ModOx (sig(β)) [5]. Together with Proposition 3, we can now characterise the notion of an atom with a corre- sponding notion in axiom dependency hypergraphs. We have that two nodes in an ADH represent axioms that are contained in the same atom if, and only if, the nodes agree on the set of nodes that are B-connected from them. Formally: α, β ∈ a if, and only if, ≥B (α) = ≥B (β), where ≥B be the B-connectivity rela- tion of the ADH HO for O. It follows that all axioms of an atom are mutually B-connected in HO . Axioms that are mutually B-connected constitute strongly B-connected components of HO . Consequently, the set of atoms for an ontol- ogy O corresponds to the set of strongly B-connected components in the axiom x dependency hypergraph for O. Let SCCs(HO ) be the set of strongly connected x components of the hypergraph HO , where x ∈ {⊥, >}. Proposition 5. Let O be an ontology and let x ∈ {⊥,>} denote a locality no- tion. Then: AtomsOx = SCCs(HO x ). a The condensed ADH is formed by collapsing the strongly B-connected com- ponents into single nodes and turning hyperedges between axioms into hyper- edges between sets of axioms. The condensed ADH corresponds to the quotient hypergraph HO /'B of HO under the mutual B-connectivity relation 'B in HO . The 'B -equivalence classes are the strongly B-connected components of HO . The partition of a hypergraph under an equivalence relation is defined as fol- lows. Definition 4 (Quotient Hypergraph). Let H = (V, E) be a hypergraph. Let ' be an equivalence relation over V. The quotient of H under ', written H/' , is the graph H/' = (V/' , E' ), where – V/' = {[x]' | x ∈ V}; and – e = (T (e), H(e)) ∈ E' iff there is an e0 ∈ E such that T (e) = {[x]' | x ∈ T (e0 )}, H(e) = {[x]' | x ∈ H(e0 )} and T (e) ∩ H(e) = ∅. a We can now define the notion of a condensed ADH as the partition of the ADH under the mutual B-reachability relation. x Definition 5 (Condensed Axiom Dependency Hypergraph). Let HO = (V x , E x ) be the x-ADH for an ontology O, where x ∈ {⊥,>}. Let 'B be the x mutual B-connectivity relation in HO . The condensed axiom dependency hy- x pergraph for O wrt. x-locality (x-cADH) is defined as the quotient HO /'B of x HO under 'B . a The dependency relation }, is defined as follows [5]. For atoms a, b ∈ AtomsOx and axioms α ∈ a and β ∈ b: a }. Let ' be the mutual B-connectivity relation in the x-ADH for O and ≥ the B-connectivity relation in the x-cADH for O. Then: a }. Then: relation of the ModOx (Σ) = ≥B ({[α]' | α ∈ O0 }). a 4 Implementation and Evaluation For a collection of well-known biomedical ontologies from the NCBO Bioportal, we observe that for many (if not all) axioms, the locality-based dependencies to other axioms can be represented using only simple directed hyperedges (i.e., hyperedges with only one tail node) [9]. For instance, the ADH for ontologies like CHEBI can be seen as a directed graph without complex hyperedges (i.e., hyperedges with more than one tail node). Computing strongly connected com- ponents in a graph can be done in linear-time using standard algorithms from graph theory [11, 13]. That is, for ontologies like CHEBI we compute the strongly connected components of the respective ADH in linear time. For ADHs of ontologies O like SNOMED CT that contain both, simple and complex hyperedges, we compute the strongly connected components in four steps. First, we build the axiom dependency graph GO , which is the fragment of the ADH HO for O without complex hyperedges. Second, we compute the strongly connected components of GO using a linear-time algorithm [11, 13]. Note that the strongly connected components give rise to an equivalence relation 'GO on the nodes in GO . In the third step, we reduce HO by computing the quotient graph HO /'GO of HO using 'GO (cf. Def. 4). Finally, in step four, we obtain the strongly connected components of HO by determining for any two nodes in HO /'GO whether they are mutually reachable. Note that computing mutual reachability this way is a quadratic process. However, using HO /'GO instead of HO it is usually more efficient as the number of nodes is typically reduced. The number of hyperedges may be exponential in the size of the ontology, which makes it impractical to represent the entire ADH explicitly. We implement an ADH H = (V, E) as a directed labelled graph GH = (V, E 0 , L) containing the simple hyperedges of H and encoding the complex hyperedges in the node labels as follows. A node vα in GH for an axiom α is labelled with the pair L(vα ) = (MLS⊥ (α), sig(α)) consisting of the minimal non-⊥-locality signatures of α and the signature of α. Reachable nodes in GH can be computed by walking along the edges in E 0 and via signature containment checks. Condensed ADHs are implemented in a similar way with the difference that S nodes represent sets of axioms. For a set S of axioms, we set MLS⊥ (S) = α∈S MLS⊥ (α). We note that when computing modules for an arbitrary signature Σ using GH , it is not necessary to compute the Σ-extension of GH (cf. Prop. 4 and 7). Reachable nodes in the Σ-extension of GH can be computed via a modified signature containment check that accounts for Σ using the node labels in GH . We have implemented a Java prototype that computes the atomic decomposi- tion and locality-based modules of several prominent biomedical ontologies. The implementation takes an EL++ -ontology as an input and computes the atomic decomposition wrt. ⊥-locality, and the ⊥-local module of an arbitrary input signature. The current version of our prototype does not normalize the input ontology. For the evaluation of our prototype, we have selected nine well-known biomedical ontologies that are available (with the exception of Snomed CT) in the NCBO Bioportal and in the ORE 2013 repository.5 We divide the on- tologies into two groups. The first group of six ontologies only contains axioms whose dependencies wrt. ⊥-locality can be represented using simple hyperedges, whereas the second group of three ontologies requires both, simple and complex hyperedges. We compare the performance of our prototype against the performance of two systems for computing the atomic decomposition of OWL2 ontologies which implement the same algorithm [14]: FaCT++ v1.6.2 which is implemented in C++ [14]6 and OWLAPITOOLS v1.0.0 which is implemented in Java [15]7 as an extension of the OWLAPI.8 All experiments were conducted on an Intel Xeon E5-2640 2.50GHz with 100GB RAM running Debian GNU/Linux 7.3. We use Java 1.7.0 51 and the OWLAPI version 3.4.8. The following table lists the results, where each time is the average of 10 executions. Ontology O Properties of O AD time for O |sig(O)| #axioms #axioms #role FaCT++ OWLAPI ADH AvC C ≡ D axioms TOOLS CHEBI 37 891 85 342 0 5 137 s 1 619 s 4s FMA-lite 75 168 119 558 0 3 18 481 s 13 258 s 17 s Gazetteer 517 039 652 355 0 6 31 595 s – 24 s GO 36 945 72 667 0 2 47 s 1 489 s 4s NCBI 847 796 847 755 0 0 49 228 s – 66 s RH-Mesh 286 382 403 210 0 0 6 921 s 9 159 s 17 s CPO 136 090 306 111 73 461 96 9 731 s 26 480 s 2 283 s Full-Galen 24 088 25 563 9 968 2 165 640 s 781 s 115 s Snomed CT 291 207 227 698 63 446 12 16 081 s 57 282 s 2 540 s We applied a timeout of 24h, which aborted the executions of the OWLAPI- TOOLS on the ontologies Gazetteer and NCBI. Our prototype consistently outperforms FaCT++ which in turn (consider- ably) outperforms the OWLAPITOOLS, with the exception of FMA-lite. In the case of the first group of six ontologies, an over 1 000-fold speedup could be achieved compared to the performance of FaCT++ on FMA-lite and Gazetteer. For the smallest ontology in this group, which is GO, the prototype is 13 times faster than FaCT++. The prototype also scales better than the other systems. For the second group of three ontologies, the speedup is reduced but our proto- type is still 4–7 times faster than FaCT++, and 11–23 faster than the OWLAPI- TOOLS. Collapsing the strongly connected components of the graph fragment of 5 http://ore2013.cs.manchester.ac.uk/ 6 http://code.google.com/p/factplusplus/ 7 http://owlapitools.sourceforge.net/ 8 http://owlapi.sourceforge.net/ the ADH helps reducing the number of nodes by nearly 50% in some cases. The use of a tree datastructure to represent the set of reachable nodes computed for each node of the ADH reduces the time needed to identify mutually reachable nodes. We also compare the performance of our prototype for extracting ⊥-locality modules with the performance of FaCT++ and the OWLAPI. The following table presents for every implementation the time needed to extract a module from an ontology for a signature consisting of 500 symbols selected at random. Ontology O Time to compute Mod⊥ O (Σ) Speedup wrt. FaCT++ OWLAPI cADH FaCT++ OWLAPI CHEBI 38.6 ms 175.8 ms 2.1 ms 18.4 83.7 FMA-lite 326.9 ms 1 042.3 ms 3.4 ms 96.1 306.6 Gazetteer 177.9 ms 1 503.0 ms 15.9 ms 11.2 94.5 GO 512.2 ms 1 398.7 ms 6.1 ms 84.0 229.3 NCBI 236.2 ms 9 193.6 ms 16.3 ms 14.5 564.0 RH-Mesh 91.2 ms 1 811.3 ms 8.9 ms 10.2 203.5 CPO 564.7 ms 3 026.8 ms 51.6 ms 10.9 58.7 Full-Galen 75.2 ms 215.4 ms 2.9 ms 25.9 74.3 SNOMED CT 525.0 ms 2 841.3 ms 84.4 ms 6.2 33.7 Our prototype outperforms FaCT++ and the OWLAPI in all cases. For the first group of six ontologies, the best speedup of over 95 times wrt. FaCT++ was achieved in the case of FMA-lite. For the second group of three ontologies, the best performance improvement was realised in the case of Full-Galen with a speedup of over 25-times. The speedup wrt. the OWLAPI is even higher. 5 Conclusion We have introduced the notion of an axiom dependency hypergraph that repre- sents explicitly the locality-based dependencies between axioms. We have shown that locality-based modules of an ontology correspond to a set of connected nodes in the hypergraph, and atoms of an ontology to strongly connected com- ponents. We have implemented a prototype in Java that computes, based on axiom dependency hypergraphs, the atomic decomposition of EL++ -ontologies wrt. ⊥-locality. Our prototype outperforms FaCT++ and the OWLAPITOOLS in computing the atomic decomposition of all biomedical ontologies tested. In some cases a staggering speedup of over 1 000 times could be realised. Moreover, our prototype outperforms FaCT++ and the OWLAPI in extracting syntactic ⊥-locality modules. Here a speedup of over 95 times could be realised. We plan to extend the prototype implementation to support both >-locality and full SROIQ-ontologies. Moreover, it would be interesting to investigate the possibility of computing strongly connected components in hypergraphs in less than quadratic time. Such a result would improve the performance of computing mutual reachability in the axiom dependency hypergraph for ontologies whose locality-based dependencies can only be represented by complex hyperedges. References 1. Allamigeon, X.: Strongly connected components of directed hypergraphs. CoRR abs/1112.1444 (2011) 2. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope further. In: Proc. of OWLED’08 (2008) 3. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The description logic handbook: theory, implementation, and applications. Cambridge University Press (2007) 4. Del Vescovo, C., Gessler, D.D.G., Klinov, P., Parsia, B., Sattler, U., Schneider, T., Winget, A.: Decomposition and modular structure of bioportal ontologies. In: Proc. of ISWC’11, pp. 130–145. Springer-Verlag (2011) 5. Del Vescovo, C., Parsia, B., Sattler, U., Schneider, T.: The modular structure of an ontology: Atomic decomposition. In: Proc. of IJCAI’11, pp. 2232–2237 (2011) 6. Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and appli- cations. Discrete Applied Mathematics 42(23), 177–201 (1993) 7. Grau, B.C., Horrocks, I., Kazakov, Y., Sattler, U.: Modular reuse of ontologies: theory and practice. JAIR 31, 273–318 (2008) 8. Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: Proc. of KR’06, pp. 57–67. AAAI Press (2006) 9. Martı́n-Recuerda, F., Walther, D.: Towards fast atomic decomposition using axiom dependency hypergraphs. In: Proc. of WoMO’13. CEUR Workshop Proceedings, vol. 1081. CEUR-WS.org (2013) 10. Nortje, R., Britz, A., Meyer, T.: Reachability modules for the description logic SRIQ. In: Proc. of LPAR-13 (2013) 11. Sharir, M.: A strong connectivity algorithm and its applications to data flow anal- ysis. Computers & Mathematics with Applications 7(1), 67–72 (1981) 12. Suntisrivaraporn, B.: Polynomial time reasoning support for design and mainte- nance of large-scale biomedical ontologies. Ph.D. thesis, TU Dresden, Germany (2009) 13. Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972) 14. Tsarkov, D.: Improved algorithms for module extraction and atomic decomposi- tion. In: Proc. of DL’12. CEUR Workshop Proceedings, vol. 846. CEUR-WS.org (2012) 15. Tsarkov, D., Vescovo, C.D., Palmisano, I.: Instrumenting atomic decomposition: Software apis for owl. In: Proc. of OWLED’13. CEUR Workshop Proceedings, vol. 1080. CEUR-WS.org (2013)