In this paper we use directed hypergraphs to represent the locality-based dependencies between the axioms of an OWL ontology. We de ne a notion of an axiom dependency hypergraph, where axioms are represented as nodes and dependencies between axioms as hyperedges connecting possibly several nodes with one node. We show that a locality-based module of an ontology corresponds to a connected component in the hypergraph, and an atom of an ontology to a strongly connected 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 axiom dependency hypergraph we exploit linear time graph algorithms on its graph fragment. This optimization can signi cantly 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.
An axiom dependency hypergraph (ADH) for OWL ontologies is a directed
hypergraph which explicitly represents the locality-based dependencies between
axioms. This graph can be used to compute the atomic decomposition (AD) of
an ontology [
Computing all SCCs in a directed hypergraph is an inherently quadratic
process [
We have implemented a Java prototype for computing the atomic
decomposition and syntactic locality-based modules. We con rm a signi cant improvement
in running time for prominent biomedical ontologies from the NCBO Bioportal
compared against state-of-the-art implementations [
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 nal section. 2
In this paper, we consider ontologies formulated in the expressive description
logic SROIQ [
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 j= i
O j= , 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 [
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 nonlocality signature for SROIQ axioms.
De nition 1. Let be an axiom, and let x 2 f?;>g 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 speci cally for
computing modules from an atomic decomposition [
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 be an axiom. The minimal non-?-locality signature MLS?( ) of t Xnm) v Y is as follows:
MLS?( ) = ffX1i1 ; X2i2 ; : : : ; Xnin g j i1; i2; : : : ; in 2 f1; :::; mgg Then: jMLS?( )j = mn.
However, exponentially many minimal non-locality signatures can be avoided
if the axiom is normalised. An ontology O is normalised by applying the
normalisation rules presented in [
The following proposition can readily be seen.
4 The normalisation in [
Then a normalised axiom can be of the forms as described, where Ai and Bi additionally range over nominals. However, nominals are not contained in any minimal non-locality signature of a normalised axiom.
Then: holds:
be a normalised axiom. Then: jMLS?( )j = 1 and
jMLS>( )j 2.
Proposition 2 (Non-locality via Signature Containment). Let normalised axiom. Let be a signature. Then: is not ?-local wrt. of the following holds: is not >-local wrt.
i is of the form 7 or one of the following { sig(RHS( )) \ { sig(RHS( )) 6= ; if is of the form if is of the form
3, 4, 5, 6; 1; 2. a 3
A directed hypergraph [
A node v is B-connected (or forward reachable) from a set of nodes V 0 (written V0 B v) if (i) v 2 V 0, or (ii) there is a B-hyperedge e such that v 2 H(e) and all tail nodes in T (e) are B-connected from V 0. For a set of nodes V0 V, we denote with B(V0) the set B(V0) = fv 2 V j V 0 B vg of B-connected nodes from V0.
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 [
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 de ned as follows. We use sig(S) to denote the signature of a set S of axioms.
De nition 2 (Axiom Dependency Hypergraph). Let O be an ontology. Let x 2 f?;>g denote a locality notion. The Axiom Dependency Hypergraph x for O wrt. x-locality (x-ADH) is de ned as the directed B-hypergraph HOx = HO ( x V ; E x), where
Vx and H(e) = f g, for some 2 Vx, a { Vx = O; and { e = (T (e); H(e)) 2 E x i T (e) such that: (i) 2= T (e), and (ii) is not x-local wrt. sig(T (e)).
The nodes of the axiom dependency hypergraph are the axioms in the ontology. 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 Bconnected 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 de ne this notion using minimal non-locality signatures by replacing Item (ii) of Def. 2 with: (iib) sig(T (e)), for some
2 MLS x( ).
An ADH HO contains all locality-based dependencies between di erent axioms 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.
De nition 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 rst 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
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) [
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 2 f?; >g. Then: ModOx ( ) = B(O0). a
However, ADHs do not contain su cient information for computing a module for an arbitrary signature as the following simple example shows. Example 2. Let O = f 1 = A v C; 2 = C u B v D; 3 = D v Ag and = fA; Bg. We have that Mod?O( ) = f 1; 2; 3g. The ?-ADH for O contains no hyperedge e with H(e) = f 2g and, consequently, 2 cannot be reached via a hyperedge.
The problem can be solved by incorporating the signature into the ADH. The -extension HOx; of an x-ADH HOx for an ontology O wrt. x-locality, x 2 f?;>g, is de ned 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 nonlocality 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 = ff 1g; f 2gg. 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.
Proposition 4. Let O be an ontology, a signature and x 2 f?;>g. Let Ox 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(Ox ). a 3.2
Atoms represent sets of highly related axioms in the sense that they always
cooccur in modules [
O
the modular structure of the ontology [
In the previous section, we have established that locality-based modules of
an ontology O correspond to sets of B-connected nodes in the axiom
dependency hypergraph for O. An atom of O consists of axioms that share the same
modules wrt. the signature of . It holds that for every x-local atom a O with
x 2 f?;>g: ; 2 a if, and only if, ModOx (sig( )) = ModOx (sig( )) [
Proposition 5. Let O be an ontology and let x 2 f?;>g denote a locality notion. Then: AtomsOx = SCCs(HOx). a
The condensed ADH is formed by collapsing the strongly B-connected components into single nodes and turning hyperedges between axioms into hyperedges 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 de ned as follows.
De nition 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=' = f[x]' j x 2 Vg; and { e = (T (e); H(e)) 2 E' i there is an e0 2 E such that T (e) = f[x]' j x 2 T (e0)g, H(e) = f[x]' j x 2 H(e0)g and T (e) \ H(e) = ;. a We can now de ne the notion of a condensed ADH as the partition of the ADH under the mutual B-reachability relation.
De nition 5 (Condensed Axiom Dependency Hypergraph). Let HOx = ( x V ; Ex) be the x-ADH for an ontology O, where x 2 f?;>g. Let 'B be the x . The condensed axiom dependency hymutual B-connectivity relation in HO pergraph for O wrt. x-locality (x-cADH) is de ned as the quotient HOx='B of HOx under 'B. a
The dependency relation <xO between x-local atoms of O, for x 2 f?; >g, is
de ned as follows [
Mod?O( 1) = Mod?O( 4) = Mod?O( 5) = f 1; 4; 5g
Mod?O( 2) = Mod?O( 3) = f 1; 2; 3; 4; 5g
The resulting atoms in Atoms?O are a1 = f 2; 3g and a2 = f 1; 4; 5g, where a1 < a2, i.e. a2 depends on a1. The ADH HO? with the SCCs and the condensed ADH HO?='B is depicted in Figure 1.
SCC1 e3 2 3 e1 e4 1 e6
SCC2 e8 e2 e5 (a) HO? 5 4 e9 e7 scc1
e4=5 scc2 (b) HO?='B
The strongly connected components of HO? are SCC1 = f 2; 3g and SCC2 = f 1; 4; 5g. Moreover, SCC2 depends on SCC1 as any axiom in SCC2 is Bconnected from any axiom in SCC1. Note that the atoms a1 and a2 of O and their dependency coincide with the strongly connected components of HO?.
Analogously to the previous section, we can characterise modules in terms of B-reachability in condensed axiom dependency hypergraphs. Proposition 3 can be lifted to cADHs as follows.
Proposition 7. Let O be an ontology, O0 O and = sig(O0). Let ' be the mutual B-connectivity relation of the x-ADH for O and B the B-connectivity relation of the -extension of the x-cADH for O, where x 2 f?; >g. Then: ModOx ( ) = S B(f[ ]' j 2 O0g). a 4
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) [
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 [
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 di erence that nodes represent sets of axioms. For a set S of axioms, we set MLS?(S) = S 2S 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 modi ed signature containment check that accounts for using the node labels in GH.
We have implemented a Java prototype that computes the atomic decomposition and locality-based modules of several prominent biomedical ontologies. The implementation takes an E L++-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 ontologies into two groups. The rst 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 [
Properties of O AD time for O jsig(O)j #axioms #axioms #role FaCT++ OWLAPI ADH
A v C C D axioms TOOLS We applied a timeout of 24h, which aborted the executions of the OWLAPITOOLS on the ontologies Gazetteer and NCBI.
Our prototype consistently outperforms FaCT++ which in turn (considerably) outperforms the OWLAPITOOLS, with the exception of FMA-lite. In the case of the rst 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 prototype is still 4{7 times faster than FaCT++, and 11{23 faster than the OWLAPITOOLS. 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. Our prototype outperforms FaCT++ and the OWLAPI in all cases. For the rst 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
We have introduced the notion of an axiom dependency hypergraph that represents 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 components. We have implemented a prototype in Java that computes, based on axiom dependency hypergraphs, the atomic decomposition of E L++-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.