Atomic decomposition of ontologies has been suggested as a tool to understand the modular structure of ontologies. It consists of a polynomial size representation of potentially exponentially many modules of an ontology. Tractable algorithms for computing the atomic decomposition for locality-based modules have been introduced, albeit leaving room for improvement in terms of running time. In this paper, we consider ontologies formulated in OWL-EL. We introduce a notion of an axiom dependency hypergraph for an ontology, which represents how axioms are included in locality-based modules. We use a standard algorithm from graph theory to compute strongly connected components of the axiom dependency hypergraph and show that such components correspond to atoms of the ontology. An empirical evaluation of the algorithm on large fragments of biomedical ontologies con rms a signi cant improvement in running time.
The atomic decomposition of an ontology provides a compact representation of all possible modules that can be extracted from a given ontology. It represents a signi cant contribution to a better understanding of the internal structure of the ontology.
In this paper, we introduce a novel representation model of OWL-EL ontologies based on directed hypergraphs that explicitly represent information for syntactic locality and atomic decomposition. We call this model Axiom Dependency Hypergraphs (ADHs). A directed hypergraph is a generalisation of a directed graph in which edges (in this case hyperedges) can connect two nonempty disjoint sets of nodes (or vertices). The nodes in such hypergraphs represent the axioms of an ontology, and hyperedges indicate subset relations between terms ? We thank the reviewers of the workshop WoMO 2013 for their comments. The rst author acknowledges the support of the EU project SEALS (FP7-ICT-238975), and the second author the support of the German Research Foundation (DFG) within the Cluster of Excellence `Center for Advancing Electronics Dresden'. in axioms. By using standard hyperpath search algorithms it is possible to e ciently extract locality-based modules (in linear time) and to compute the atomic decomposition of the ontology.
The use of hypergraph-based models for locality-based module extraction is
not new [
The paper is organised as follows. In Section 2, we review the main notions on syntactic ?-locality, atomic decomposition, and hypergraphs. In Section 3, we introduce axiom dependency hypergraphs and discuss their size, and evaluate the performance of atomic decomposition based on these graphs in Section 4. We conclude this paper in a nal section. 2
In this paper, we consider ontologies formulated in the description logic E L,
which allows for conjunction and existential restrictions. Large parts of, e.g.,
biomedical ontologies are expressed in E L. For notions on description logics, we
refer to [
The notion of ?-locality depends on whether or not a given signature covers all symbols occurring on the LHS of a general concept inclusion, or occurring on the LHS or RHS of a general concept equation. The following proposition makes that precise.3
with a tractable logic such as EL can be seen as too di cult in some cases, depending on the size of the input and the application requirements.
Proposition 1. Let be an E L-axiom. Let (i) if = (C v D), then (ii) if = (C D), then or sig(RHS( )) .
is not syntactic ?-local wrt. is not syntactic ?-local wrt.
i sig(LHS( )) i sig(LHS( ))
The following example illustrates the notion of ?-locality of axioms. Example 1. Let and be the axioms:4 ; a := A1 u 9r1:(A2 u 9r2:A3) v 9r3:A4 := A1 A2 u 9r1:A3 Axiom is syntactic ?-local wrt. if any of the symbols occurring in LHS( ) is not contained in , i.e., if satis es any of the following conditions: { Ai 2= { r1 2= , for some i 2 f1; 2; 3g; or or r2 2= .
Axiom is syntactic ?-local wrt. if there are two symbols, one occurring in LHS( ) and one in RHS( ), that are not contained in , i.e., if satis es any of the following conditions: { A1 2= { A1 2= and Ai 2= and r1 2= , for some i 2 f2; 3g; or . 2.1
Extracting modules based on locality
This is the module extraction algorithm from [
[ sig(Mm 1)g
The algorithm takes an ontology O and a signature as input and returns a subset M of O. The computed set M consists of axioms that are not xlocal wrt. [ sig(M), or equivalently, O n M consists of axioms that are local wrt. [ sig(M). The algorithm produces a nite sequence M0; : : : ; Mn, n 0, of subsets of the ontology O, where Mn is the ?-local module of O wrt.
Full-Galen.
[ sig(Mn) with being the initial signature. This sequence induces a relation on O representing the successive inclusion of the axioms into the module. Later we will represent this relation as hyperedges in an axiom dependency hypergraph. This is illustrated in the following example.
Example 2. The signature increases round-by-round due to axioms that are added to the module (line 5). In fact, the RHSs of the axioms introduce new symbols to the signature. Let i = Ai v Ai+1, for i 2 f1; :::; ng. Let O = f 1; :::; ng and = fA1g. We run the algorithm on the input O and . In the rst round of the do-until loop (lines 3-6), the axiom 1 is the only axiom in O that is not ?-local wrt. [ sig(M0) (line 5), where M0 = ; (line 2). So 1 is added to M1. In the second round, ?-locality is checked for the extended signature [ sig(M1) = fA1; A2g. Axioms 1 and 2 are now non-? local wrt. [ sig(M1) and both are added to M2. The algorithm proceeds this way until all axioms of O are added to Mn. As no more axioms are added the algorithm exits the do-until loop (line 6) and returns Mn+1 = O as the ?-local module of O wrt. (line 7). The following picture shows the module extraction process as a graph Gmod?(O; ) = (V; E), where V = f 1; :::; ng and E = f( i; Ai+1; i+1) j i 2 f1; :::; n 1gg, and the sequence M0; :::; Mn; Mn+1 produced by the module extraction algorithm. Additionally we indicate with a tilted arrow labelled with A1 to node 1 that the concept name A1 is provided by the initial signature. In this case, 1 is the rst axiom to be included by the module extraction algorithm.
M0 M1 2
M2 3
M3 A3
A4 :::
An
n Mn = Mn+1 2.2
Atomic decomposition
Atoms represent sets of highly related axioms in the sense that they always
co-occur in modules. A set a of axioms from an ontology O is an atom of O
if for every module M of O, it holds that a M or a \ M = ;. We denote
with AtomsO the set of all atoms of O. The atoms of an ontology partition the
set of its axioms (i.e., each axiom occurs in exactly one atom). A dependency
relation between pairs of atoms can be established: an atom a2 depends on an
atom a1 in an ontology O (written a1 <O a2) if a2 occurs in every module
of O containing a1. For a given ontology, the pair hAtomsO; <Oi consisting of
the set of atoms together with the dependency relation between them is called
Atomic Decomposition.5 It provides a compact representation of all modules of an
ontology as every module is composed of the axioms of certain atoms. Therefore,
the atomic decomposition contributes to a better understanding of the internal
structure of ontologies with possible implications in ontology engineering and
reasoner design. The representation of the modules in terms of atoms and their
5 Here we use atomic decomposition for ?-local modules denoted as hAtoms?O; <?Oi.
interdependencies is of linear size and it can be computed in polynomial time,
whereas there are exponentially many possible modules of an ontology. However,
not all modules of an ontology can be computed from its atomic decomposition.
The atomic decomposition was rst introduced in [
Directed hypergraphs
A directed hypergraph [
A node v2 is B-connected 6 (or forward reachable7) from v1 if (i) v2 = v1 (v2 is B-connected from itself), or (ii) there is a hyperedge e such that v2 2 H(e) and all the elements of T (e) are B-connected from v1. A B-hyperpath from node v1 to node v2 in a hypergraph H is a minimal (in terms of hyperedges and nodes) subhypergraph of H such that v2 is B-connected to v1.
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 a set of
nodes from H which are all are mutually reachable [
In the case of directed graph, it is possible to calculate all the strongly
connected components in linear time [
Axiom dependency hypergraphs are a representation model for ontologies based
on directed hypergraphs that explicitly represent information for locality and
atomic decomposition. The nodes in such graphs represent the axioms of an
ontology, and hyperedges indicate subset relationships between terms in axioms
6 There is a similar notion called F-connectivity [
i.e., any axiom is mutually reachable from itself. (cf. Proposition 1). By using standard hyperpath search algorithms it is possible to e ciently extract locality based modules (in linear time) and to compute the atomic decomposition of the ontology.
The ?-locality signatures ?-sig( ) of an axiom is the set of signatures ?-sig( ) = (fsig(LHS( ))g fsig(LHS( )); sig(RHS( ))g if if is of the form C v D; is of the form C D.
Intuitively, ?-sig( ) is a function assigning to an axiom the signatures ?-sig( ) that are relevant for deciding the ?-locality status of . More precisely, we have that is not ?-local wrt. S, for every S 2 ?-sig( ).
Axiom dependency hypergraphs for E L-ontologies are de ned as follows. De nition 1 (Axiom dependency hypergraph for ?-locality). Let O be an E L-ontology. The ?-locality axiom dependency hypergraph (ADH) HO? for O is de ned as HO? = (V; E ), where { V = O; and { e = (T (e); H(e)) 2 E i the following holds: (i) H(e) = f g, for some 2 V, and (ii) T (e) V n f g such that jT (e)j is minimal with the property S sig(T (e)), for some S 2 ?-sig( ). a Note that the axiom dependency hypergraph for an E L-ontology is de ned for the notion of ?-locality.9 The nodes are the axioms of the ontology, and the hyperedges are associating axioms 1; : : : ; n with a single axiom such that one of the ?-locality signatures of is contained in the signature of the axioms i. The minimality condition states that each of the axioms i is required and none of them is super uous for covering some of the ?-locality signatures of .10 Example 3. Let O = f 1; :::; 5g, where 1 := A v B 2 := B u C u D v E 3 := E v A u C u D 4 := A v X 5 := X v A The ADH HO? contains the hyperedges e1 = (f 1; 3g; f 2g), e2 = (f 1g; f 4g), e3 = (f 2g; f 3g), e4 = (f 3g; f 1g), e5 = (f 3g; f 4g), e6 = (f 4g; f 1g), e7 = (f 4g; f 5g), e8 = (f 5g; f 1g) and e9 = (f 5g; f 4g); see Example 4 for a visualisation of the graph. Now obtain O0 by replacing 2 with 20 := B uC uD E. Then the ADH HO?0 contains one additional edge e10 = (f 3g; f 2g).
B-connectivity (forward reachability) in axiom dependency hypergraphs can be used to specify ?-local modules in the corresponding ontology. Denote with Mod?O( ) the ?-local module of ontology O wrt. the signature of axiom . 9 Axiom dependency hypergraphs for the notion of >-locality can be de ned in a similar way. 10 Note that the minimality condition in Def. 1 is to avoid super uous hyperedges, but it is not required in terms of correctness.
Proposition 2. Let O be an EL-ontology and an EL-axiom. Then: Mod?O( ) =
f j is B-connected to in HO?g. a
Reachability-based modules have been de ned in other hypergraph
respresentations of ontologies in [
The set of atoms for an EL-ontology O corresponds to the set of strongly connected components in the axiom dependency hypergraph for O. Let SCCs(HO?) be the set of strongly connected components of the hypergraph HO?. Proposition 3. Let O be an EL-ontology. Then: Atoms?O = SCCs(HO?). a
The proposition can readily be seen as follows. As a corollary of Proposition 2, mutually reachable axioms are contained in the same modules, which is equivalent to the axioms forming an atom of the ontology. The nodes in a strongly connected component are all mutually reachable. Thus, both notions are equivalent.
The dependencies between atoms for an EL-ontology O (as given by the relation <?) correspond to a certain binary relation over the set of strongly con
O nected components of HO?, which is de ned as follows. For S1; S2 2 SCCs(HO?), we say that S2 depends on S1 (written S1 !?O S2) if there is an hyperedge e = (T (e); H(e)) in HO? such that T (e) S1 and H(e) S2. Let !?O be the re exive, transitive closure of !?O.
Proposition 4. Let O be an EL-ontology. Let a1; a2 2 Atoms?O and S1; S2 2 SCCs(HO?) such that a1 = S1 and a2 = S2. Then: a1 <?O a2 i S1!?O S2. a Example 4. Consider again the ontology O and its axiom dependency hypergraph HO? from Example 3. We obtain the following ?-local modules for the axioms:
Mod?O( 1) = f 1; 4; 5g Mod?O( 2) = f 1; 2; 3; 4; 5g Mod?O( 3) = f 1; 2; 3; 4; 5g
Mod?O( 4) = f 1; 4; 5g Mod?O( 5) = f 1; 4; 5g The resulting atoms in AtomsO are a1 = f 2; 3g and a2 = f 1; 4; 5g, where a1 < a2, i.e., a2 depends on a1. The ADH HO? and the atoms of O can be depicted as follows: a1 2 ? 3 * a2 1 YHHHHHHHHHHHHHHHHj 6 5 ? 4 Consider the strongly connected components of HO?. Axiom 1 is B-connected with the axioms 4 and 5, 4 is B-connected with 1 and 5, and 5 is Bconnected with 1 and 4. Axiom 2 is B-connected with 3 and vice versa. Axioms 2; 3 are each B-connected with 1; 4 and 5, but not vice versa. Hence, f 1; 2; 4g and f 2; 3g are the strongly connected components of HO?. Moreover, we say that the former component depends on the latter as any two axioms contained in them are unilaterally and not mutually B-connected. Note that the atoms a1 and a2 of O and their dependency coincide with the strongly connected components of HO? .
For ontologies consisting of axioms of the form A v C, where A is a concept
name, the locality dependencies between axioms can be represented in directed
graphs (i.e., hypergraphs in which the tail of any hyperedge contains only one
axiom). For such ontologies O, the de nition of the axiom dependency
hypergraph HO? = (V; E) can be simpli ed (cf. Def. 1). The condition for a hyperedge
e = (f g; f g), for ; 2 V, to be contained in E is now:
e = (f g; f g) 2 E i sig(LHS( ))
sig( )
The advantage of this representation is that we can directly use a standard
linear time algorithm for calculating strongly connected components of directed
graphs [
Size of axiom dependency hypergraphs (worst-case) We observe that axiom dependency hypergraphs may be of exponential size. Proposition 5. There exists ontologies O such that the axiom dependency hypergraph HO contains exponentially many hyperedges in the number of axioms of O. a We show the proposition with the following example.
Example 5. Let n; k be two natural numbers with n > 0 and k > 0. Ontology On;k is de ned as: Axiom is the only axiom in On;k with a complex LHS, which in turn is a conjunction of n many concept names X1; :::; Xn. The axioms ji state that each concept name Xi subsumes k many concept names Ai1; :::; Aik. The corresponding axiom dependency graph HOn;k is the the tuple HOn;k = (V; E), where V = On;k and
E = f(f 1; :::; ng; f g) j i 2 f 1i; :::; kig; i 2 f1; :::; ngg: It can readily be seen that HOn;k contains kn many hyperedges, where n; k are each bound by the number of axioms in On;k.
The axiom dependency hypergraph serves as a tool to determine the atoms of an ontology via calculating the strongly connected components of the graph. Example 5 illustrates a problem with the size of the axiom dependency hypergraphs as de ned in Def. 1. We note, however, that no hyperedge in HOn;k is needed for the purpose of determining the atoms for On;k. For every axiom in On;k, the ?-local module Mod?O( ) is a singleton set consisting of itself. Consequently, the atoms of On;k are singleton sets as well as are the strongly connected components of HOn;k . Note that we obtain the same strongly connected components after removing every hyperedge from HOn;k . This observation suggests a possible solution to avoid the exponential blow-up problem. The idea is to build the hypergraph using only the \necessary" hyperedges that are required for the computation of the strongly connected components which in turn correspond to atoms. We hypothesize that the hyperedges needed are the ones that preserve the mutual reachability relation between the axioms of the ontology. This means that no more incoming hyperedges are needed per axiom than the total number of axioms in the ontology. We leave a formal treatment of this idea for future work. 3.2
Size of axiom dependency hypergraphs for real ontologies Primitive concept inclusions, i.e. axioms of the form A v C, where A is a concept name and C a possibly complex concept, are of prime importance for biomedical ontologies. For instance, the majority of axioms in the biomedical ontologies from the Bioportal in the following table are primitive concept inclusions.11 Ontology
Signature #axioms percentage #axioms #role size A v C of all axioms C D axioms
in ontology CPO (12/2011) FMA-lite Full-Galen (v1.1) GO v1.1 (1986) NCBI (v1.2) RH-MeSH (08/2012) Snomed CT (2010a) Most ontologies contain other axioms as well such as concept equations and role axioms.12 The table shows the percentage of axioms of the form A v C to all axioms in each ontology. The ontologies NCBI and RH-Mesh are taxonomies (no logical operators); they consist entirely of axioms of the form A v B, where A; B are concept names. 11 http://bioportal.bioontology.org 12 Other axiom types are not shown here, e.g., disjointness axioms in CPO.
Ontology
Signat.
size
ADH #nodes #edges #SCCs
The di erence between the number of SCCs and the number of nodes in the axiom dependency hypergraph can be seen as a measure of cyclicity of the graph.
The following example illustrates the limitations of axiom dependency graphs. Axioms of the form C v D or C D (i.e. axioms whose ?-locality signatures contains more than one symbol) can cause many hyperedges to be included in the axiom dependency hypergraph.
Example 6. Consider this concept equation from the ontology Full-Galen: Incontinence
Transport u 9 actsOn:BodySubstance u 9 hasIntentionality:(Intentionality u 9 hasAbsoluteState:involuntary) u 9 hasUniqueAssociatedDisplacement:(Displacement
u 9 isDisplacementTo:GRAILExteriorOfBody) The axiom dependency hypergraph HF?ull-Galen contains up to 9:2 1012 many hyperedges of the form e = (T (e); f g), where T (e) is a set of axioms containing the 12 signature symbols from ?-sig( ).13 As indicated in Section 3.1, the number of hyperedges may be reduced while preserving the strongly connected components. The idea is that no more incoming hyperedges are needed per axiom as there are axioms in the ontology. In the case of Full-Galen, we have an upper bound of 37 696 many incoming hyperedges per axiom. In particular, for axiom from Example 6 we estimate up to 21 095 many hyperedges to preserve the mutual reachability relation involving . 4
We have implemented a Java program that takes an EL-ontology O (with axioms of the form A v C) as an input and builds the corresponding axiom dependency hypergraph HO?. Then it computes the set SCCs(HO?) of strongly connected components of HO? and the dependencies between these components. We compare the running times of atomic decomposition using FaCT++ with the times needed by the hypergraph-based approach. The following table lists the results.14 Ontology fragment with axioms of the form A v C
time FaCT++ time hypergraph-based approach load build comp. comp. total ont. ADH SCC deps.
speedup CPO (12/2011) 1 262:69 s 9:99 s 0:85 s 0:59 s 0:52 s 11:94 s 105:8 FMA-lite 19 991:92 s 9:50 s 0:49 s 6:43 s 0:20 s 16:62 s 1 202:9 Full-Galen (v1.1) 115:77 s 2:87 s 0:09 s 0:20 s 0:05 s 3:21 s 36:1 GO v1.1 (1986) 44:33 s 3:42 s 0:15 s 0:16 s 0:09 s 3:82 s 11:6 NCBI (v1.2) 49 227:86 s 73:72 s 1:42 s 0:87 s 1:19 s 77:22 s 637:5 RH-MeSH (08/2012) 6 921:62 s 15:24 s 1:31 s 0:63 s 0:66 s 17:84 s 388:0 Snomed CT (2010a) 4 538:65 s 14:47 s 0:48 s 0:31 s 0:32 s 15:58 s 291:3 The times for FaCT++ are the total times needed (2nd column), which includes loading the ontology, initialising the reasoner and computing the atoms (but not saving the atoms). For the hypergraph-based approach, we have listed the times needed for the OWL-API to load the ontology and to do some initialisation (3rd column), to build the axiom dependency hypergraph (4th column), to compute the strongly connected components of the graph (5th column), to compute the dependencies between the strongly connected components (6th column) and the total time needed (6th column). The last column shows for each ontology the speedup achieved for atomic decomposition using the hypergraphbased approach compared to FaCT++. On FMA-lite an over 1 000-fold speedup was realised.
FaCT++ improves upon the original algorithm for atomic decomposition [
We have suggested a hypergraph-based method for e cient atomic decomposition of E L-ontologies consisting of primitive concept inclusions. We have introduced the notion of an axiom dependency hypergraph, in which, di erent to other hypergraph representations of ontologies, axioms are nodes that are connected in a way mimicking how axioms are included in a module by the locality-based module extraction algorithm.
Modularisation and atomic decomposition has been suggested as a means to understand the internal structure of ontologies. Axiom dependency hypergraphs are an explicit representation of these notions. A module can be extracted from the hypergraph by collecting the nodes reachable from the nodes that are determined by the input signature. Moreover, it is possible to directly apply standard o -the-shelf graph algorithms for computing the atoms of certain E L-ontologies in linear time. For the atomic decomposition of FMA-lite, a staggering 1 000-fold speedup could be achieved compared to the reasoner FaCT++.
The disadvantage of the axiom dependency hypergraphs, as introduced in this paper, is their exponential size in the worst case for general concept inclusions. We have indicated that the blow-up in size can be avoided by omitting hyperedges while still preserving the mutual reachability relation between axioms. In this way, no more than quadratically many hyperedges are required for determining the atoms.
For future work, the idea of avoiding the exponential blow-up of the axiom dependency hypergraphs for general E L-ontologies needs to be formalised, implemented and evaluated. It would also be interesting to extend the current approach to other locality notions such as >- and ?> -locality and to richer languages such as SROIQ.