Introduction

Bidirectional reachability-based modules

Riku Nortje

nortjeriku@gmail.com 0 2

Katarina Britz

0 2

Thomas Meyer

0 1 0 CSIR Meraka Institute , Pretoria , South Africa 1 University of KwaZulu-Natal , Durban , South Africa 2 University of South Africa , Pretoria , South Africa

We introduce an algorithm for MinA extraction in E L based on bidirectional reachability. We obtain a significant reduction in the size of modules extracted at almost no additional cost to that of extracting standard reachability-based modules. Bidirectional modules are related to nested locality modules, but are aimed specifically at MinA extraction and are generally smaller. For acyclic E L TBoxes consisting of only primitive concept inclusions, all MinAs can be extracted without the need for subsumption testing.

Introduction

Module extraction plays an important role in the design, reuse and maintenance of ontologies as well as aiding in the optimization of reasoning services [ 9 ]. When used to optimize reasoning services such as subsumption testing and MinA extraction, reachability-based modules have been criticized for only considering the subsumee of a subsumption entailment during the module extraction process [ 2 ], thus not sufficiently reducing the size of modules.

In this paper we address this shortcoming of reachability-based modules, with the aim of improving MinA extraction, as follows: We introduce a topdown heuristic which considers only the subsumer of an entailment and then combine it with standard reachability-based modules to form a bidirectional version of reachability. This new bidirectional version of the heuristic thus considers both the subsumee and subsumer in a subsumption entailment between concept names. For relatively sparse graphs this significantly reduces the size of modules extracted with almost no additional cost to that of extracting standard reachability-based modules.

Given a subsumption statement between single concept names, we show that every MinA is in fact a bidirectional reachability-based module in terms of itself. Using this property we implement very fast algorithms to extract all MinAs for acyclic E L TBoxes consisting of only primitive concept inclusions without performing a single subsumption test, thereby significantly reducing the runtime complexity of MinA extraction for these TBoxes.

In Section 2 we give a brief introduction to description logics and the notations as used in this paper. Section 3 introduces reachability-based modules [ 9 ], the new top-down reachability heuristic and finally defines bidirectional reachability-based modules. Then in Section 4 we investigate the relationship between MinAs and the inexpressive Horn DL HL and extend the findings to EL TBoxes consisting of primitive concept inclusions. Lastly in Section 5 we provide empirical results of the various algorithms presented as tested on three generally large real world biomedical ontologies. 2

Preliminaries

In the standard set-theoretic semantics of concept descriptions, concepts are interpreted as subsets of a domain of interest, and roles as binary relations over this domain. An interpretation I consists of a non-empty set ΔI (the domain of I) and a function ·I (the interpretation function of I) which maps each atomic concept A to a subset AI of ΔI , and each atomic role r to a subset rI of ΔI × ΔI . The interpretation function is extended to arbitrary concept and role descriptions, with the specifics depending on the particular description logic under consideration.

A DL knowledge base consists of a TBox which contains terminological axioms and an ABox which contains assertions; for the purposes of this paper we concern ourselves only with Tbox statements, or general concept inclusions (GCIs) of the form C ⊑ D, where C and D are (possibly complex) concept descriptions. Here C is referred to as the subsumee and D as the subsumer. An interpretation I satisfies C ⊑ D, written I C ⊑ D, iff CI ⊆ DI . In this paper, when the left hand side of a GCI consists of only a single concept name, the statement is referred to as a primitive concept inclusion.

An interpretation I satisfies a DL TBox T iff it satisfies every statement in T . A TBox T entails a DL statement φ, written as T |= φ, iff every interpretation that satisfies T also satisfies φ.

Roughly speaking, DLs are defined by the constructors they provide. In this paper we consider the DLs HL and EL. The constructors allowed for EL are conjunction (⊓ ) and existential restriction (∃), with semantics defined as follows: (C ⊓ D)I = CI ∩ DI ; (∃r.C)I = {x ∈ ΔI | ∃y ∈ ΔI : (x, y) ∈ rI ∧ y ∈ CI }. The only concept constructor allowed for HL is conjunction, with semantics as for EL. Both HL and EL also have the distinguished top concept ⊤ with semantics ⊤ I = ΔI . Normalization for HL only allows GCIs of the form A ⊑ B and A1 ⊓ A2 ⊑ B. For EL, GCIs of the form A ⊑ ∃ r.B and ∃r.A ⊑ B are also allowed. Given any concept description or subsumption statement α, Sig(α) is defined as the union of all concept and role names occurring in α. Definition 1. (Module) Let L be an arbitrary description language, O an L ontology, and σ a statement formulated in L. Then, O′ ⊆ O is a module for σ in O(a σ-module in O) whenever: O |= σ if and only if O′ |= σ. We say that O′ is a module for a signature S in O (an S-module in O) if, for every L statement σ with Sig(σ) ⊆ S, O′ is a σ-module in O. Given the statement σ, if there is no O′ ⊂ O′ such that O′ |= σ then O′ is a minimal σ-module.

Given a subsumption statement σ = A ⊑ B, a MinA is defined as a minimal set of axioms O′ such that O′ |= A ⊑ B. Though these are not usually referred to as modules in the literature, MinAs are by definition minimal modules for a specific statement of interest. 3

Bidirectional Reachability-based Modules for E L Extracting modules aims to preserve both subsumption and non-subsumption relationships in a subset of an ontology. This can be understood as the reachability problem in a directed graph [ 1 ], considering concept names as nodes and explicit subsumption relationships as edges in the graph, where each inclusion axiom αL ⊑ αR ∈ O essentially specifies a collection of hyperedges from the connected node Sig(αL) to each of the symbols in Sig(αR).

Definition 2. (Bottom-up reachability-based modules [ 9 ])1 Let O be an E L ontology and S ⊆ Sig(O) a signature. The set of S-reachable names in O is defined inductively as follows: (i) x is S-reachable in O, for every x ∈ S; and (ii) for all inclusion axioms αL ⊑ αR, if x is S-reachable in O for every x ∈ Sig(αL), then y is S-reachable in O for every y ∈ Sig(αR). We call an axiom αL ⊑ αR S-reachable in O if every element of Sig(αL) is S-reachable in O. The bottom-up reachability-based module for S in O, denoted by OSreach, consists of all S-reachable axioms in O.

When S is the single concept A, we write A-reachable and OAreach. For E L, axioms of the form ⊤ ⊑ αR are such that Sig(⊤ ) = ∅, thus they will form part of every reachability-based module extracted. Bottom-up reachability-based modules are in fact equivalent to ⊥-locality based modules [ 4, 8 ].

A criticism that may be raised against these bottom-up reachability-based modules is that they contain many irrelevant axioms and in some cases do not reduce the size of the ontology at all [ 2 ]. This stems from the fact that OAreach considers only the subsumee A in O |= A ⊑ B; the subsumer B is never used to eliminate unwanted axioms. For example: Example 1. Given the ontology O = {A ⊑ ∃ r.D, ∃r.D ⊑ B, E ⊑ B, A ⊑ F }, as well as the entailment O |= A ⊑ B, OAreach consists of axioms {A ⊑ ∃ r.D, ∃r.D ⊑ B, A ⊑ F }. A ⊑ F is irrelevant in terms of O |= A ⊑ B, yet it is included in OAreach.

For large ontologies many such irrelevant axioms may be included in a bottomup reachability-based module. We introduce modules based on the subsumer of an entailment namely top-down reachability-based modules. Formally: 1 The original definition by Suntisrivaraporn does not have the qualifier ‘bottomup’, but because we introduce ‘top-down’ reachability-based modules later on in Definition 3, the qualifier is used to avoid confusion.

Definition 3. (Top-down reachability-based module) Let O be an EL ontology and S ⊆ Sig(O) a signature. The set of ←S -reachable names in O is defined inductively as follows: (i) x is ←S -reachable in O, for every x ∈ S; and (ii) for all inclusion axioms αL ⊑ αR, if x is ←S -reachable in O for some x ∈ Sig(αR), then y is ←S -reachable in O for every y ∈ Sig(αL). We call an axiom αL ⊑ αR ←S -reachable in O if some element of Sig(αR) is ←S -reachable. The top-down reachability-based module for S in O, denoted by Or←Seach, consists of all ←S -reachable axioms from O.

Algorithm 1 extracts a top-down reachability based module, given an EL TBox O and a signature S as input. active-axioms(x) are all those, and only those axioms (αL ⊑ αR) ∈ O such that x ∈ Sig(αR), thus every such axiom is also by definition top-down reachable. For a signature S we define active-axioms (S) := Sx∈Sactive-axioms(x).

Algorithm 1 (Extract top-down reachability-based module) Procedure extract-top-down-module(O, S) Input: O - EL ontology; S - signature Output: OS : top-down reachability-based module for S in O 1: OS := ∅; queue := active-axioms(S) 3: while not empty(queue) do 4: (αL ⊑ αR) := fetch(queue) 5: OS := OS ∪ {αL ⊑ αR} 6: queue := queue ∪ (active-axioms(Sig(αL)) \OS) 7: return OS Theorem 1. [ 5 ] Let O be an EL ontology, n the number of axioms in O, and S ⊆ Sig(O) a signature. Algorithm 1 terminates after O(n) steps and returns the top-down reachability-based module for S in O.

It is easy to show that top-down reachability-based modules are equivalent to a subset of ⊤ -locality modules [ 4, 8 ]. These modules can be criticized in a similar manner to bottom-up reachability-based modules, in that they include many irrelevant axioms. Combining ⊥-locality modules with ⊤ -locality based modules allows us to extract so called nested locality modules denoted by ⊤⊥ or ⊥⊤ [ 8 ]. We introduce a slightly different form of module called bidirectional reachabilitybased modules, aimed towards finding small modules preserving subsumption relationships between single concept names.

Definition 4. (Bidirectional reachability-based module [ 6 ]) The bi-directional reachability-based module, denoted OAre↔acBh, for the statement A ⊑ B in terms of O, is defined as the set of all axioms αL ⊑ αR ∈ O such that: for every xi ∈ Sig(αL), xi is A-reachable in terms of O, and αR is ←B-reachable in terms of O. Any non-empty subset O′ ⊆ OAre↔acBh such that O′ rAe↔acBh = O′ is called a bidirectional reachability-based sub-module of O for the statement A ⊑ B. O′ rAe↔acBh is minimal if there exists no O′ ⊂ O′ such that O′ rAe↔acBh = O′ .

These modules differ from nested locality modules as follows: Given a subsumption statement A ⊑ B, and the ⊥⊤ module O′ , then O′ will contain all axioms for the signature S = {A, B}, thus it will include all the axioms for the entailments O′ |= A ⊑ B and O′ |= B ⊑ A. A bidirectional reachability-based module O′ , however, only contains axioms for the entailment O′ |= A ⊑ B. Using the notation that ⊥{A, B} represents the ⊥ locality module for the signature {A, B} the relationship between these modules can be illustrated as follows: OAre↔acBh ⊆ ⊥{A}⊤{ B} ⊆ ⊥{A}⊤{ B} ∪ ⊥{B}⊤{ A} ⊆ ⊥⊤{ A, B} ⊆ ⊥{A, B}

The following example shows the relationship between a bidirectional reachability-based module, bidirectional reachability-based sub-modules and minimal bidirectional reachability-based modules.

Example 2. Given the ontology O consisting of the set of axioms: {α1 : A ⊑ C1, α2 : A ⊑ D, α3 : D ⊑ C3, α4 : C1 ⊑ ∃ R.C2, α5 : C2 ⊑ C3, α6 : C3 ⊓ C4 ⊑ B, α7 : ∃r.C3 ⊑ C4, α8C3 ⊑ B, α9 : C2 ⊑ E, α10 : E ⊑ F }, as well as the statement O |= A ⊑ B, we have that: – OAreach = O, – (OAreach)r←each = OAre↔acBh consist of axioms: {α1, α2, α3, α4, α5, α6, α7, α8}

B – Given that the sets O0, O1, O2 and O3 are defined as follows: O0 = {α1, α4, α5, α6, α7}, O1 = {α2, α3, α8}, O2 = {α1, α4, α5, α8}, O3 = {α1, α2, α3, α4, α5, α6, α7}, then • O0, O1, O2 and O3 are bidirectional reachability-based sub-modules

Oi ⊆ OAre↔acBh, that is, Oi = OirAe↔acBh. • O1 and O2 are both minimal bidirectional reachability-based modules with O1 being the only one of these sets that is both a minimal bidirectional reachability-based module and a MinA for the statement A ⊑ B such that O1 |= A ⊑ B. • O3 is a MinA for the statement A ⊑ B such that O3 |= A ⊑ B but O3 is not a minimal bidirectional reachability-based module.

The algorithms for both bottom-up and top-down reachability based modules extraction methods may now be applied in any order and in sequence to extract bidirectional reachability-based modules. Since Or←each is in general very large, B we prefer to extract (OAreach)r←each.

An interesting property of bidirectional reachability-based modules for E L is that every MinA for a subsumption statement is a bidirectional reachabilitybased module in terms of itself. Formally: Theorem 2. [ 5 ] Given an E L TBox T and the statement A ⊑ B such that T |= A ⊑ B. Let M1 ⊆ T be a MinA such that M1 |= A ⊑ B, then M1rAe↔acBh = M1. 4

MinA extraction

By Theorem 2 every MinA is a bidirectional reachability-based module. In this section we show that for the DL HL every MinA is a minimal bidirectional reachability-based module and that this property can be extended to acyclic E L TBoxes consisting of only primitive concept definitions. We also provide algorithms to compute and extract all MinAs for the given TBoxes.

Every MinA in HL is a minimal bidirectional reachability-based module in terms of itself. This is quite a subtle point, because MinAs are already minimal. Note, however, that MinAs are minimal with respect to the property of entailing a given statement of interest, whereas bidirectional reachability-based sub-modules are minimal with respect to the syntactic requirement for both bottom-up reachability and top-down reachability.

Theorem 3. [ 5 ] Given a acyclic HL TBox T in normal form, the statement A ⊑ B and a MinA M1 such that M1 |= A ⊑ B, then M1 is a minimal bidirectional reachability-based module M1rAe↔acBh in terms of M1.

Next we show that every minimal bidirectional reachability-based module in HL for a statement A ⊑ B corresponds to a MinA.

Theorem 4. [ 5 ] Given an acyclic HL TBox T in normal form, the statement A ⊑ B and a minimal bidirectional reachability-based module M1rAe↔acBh, then M1 |= A ⊑ B.

Theorems 3 and 4 allows us to conclude that there is a one-to-one correspondence between minimal bidirectional reachability-based modules and MinAs in HL.

Corollary 1. There is a one-to-one correspondence between MinAs and minimal bidirectional reachability-based modules in HL.

In order to extract all minimal bidirectional reachability-based modules we propose an algorithm originally inspired by the Earley [ 3 ] algorithm for parsing Context Free Grammars (CFG). Given a string to parse and a CFG the algorithm computes all possible parse trees in polynomial time. We employ a variation of the algorithm in order to compute a representation of all possible bidirectional reachability-based modules in HL. A CFG consists of a set of CFG production rules formally defined as: Definition 5. (CFG production rules) Let X represent a single non-terminal, the symbol ’a’ represents a single terminal and α and σ represent mixed strings of terminals and non-terminals, including the null string. CFG production rules have the form X → ασ or X → a.

Any HL TBox can be transformed to an equivalent CFG by step by step transformation process [ 6, 5 ], with the reachability preserving CFG for an HL TBox is defined as: Definition 6. Reachability preserving CFG for a HL TBox. Let T be an HL TBox in normal form and A ⊑ B a statement such that T |= A ⊑ B, then the reachability preserving CFG, denoted CF GT , is a minimal set of CFG production rules such that for each axiom αL ⊑ αR ∈ T : if Sig(αL) = ∅ the rule xi → A ∈ CF GT for each xi ∈ Sig(αR); for all other axioms the rule xi → Sig(αL) ∈ CF GT ; where the symbol A represents the only terminal symbol and the set Sig(T )\A represents the set of non-terminals.

The conversion process may be illustrated by the following example: Example 3. Given the acyclic HL TBox T in normal form: T = {A ⊑ B1, A ⊑ B2, B1 ⊑ C1, B1 ⊑ D, B2 ⊓ C1 ⊑ D, ⊤ ⊑ B2}. Then CFGT is given by: { B1 → A, B2 → A, C1 → B1, D → B1, D → B2C1}

Once the TBox has been converted to a CFG, we employ a parallel breadthfirst algorithm, adapted from the Earley [ 3 ] algorithm, further optimized and improved from an algorithm earlier presented in [ 6 ]. The algorithm computes and indexes a representation of all bi-direction sub-modules in polynomial time. Algorithm 2 (Sub-module computation) [ 5 ] The algorithm consists of two sub-parts, the predictor and completer. For each state in CHART, the state (X → αβ) is evaluated and the appropriate sub-part executed: Input: Reachability preserving CFG for an HL TBox; Output: Reference table CHART capturing a representation of all HL submodules. 1. Predictor: Given the state (X → Y1 . . . Yn), for all Yi such that (Yi → σ) ∈/ CHART, add all rules (Yi → σ) to CHART. 2. Completer: If state = (X → Z1 . . . Zm) with all Zi terminals, then – add a pointer to this state in the completion table for X ,and – if X is not a terminal symbol, then mark it a terminal symbol, and – if X is a new terminal symbol, then call the completer for each rule (Y → . . . X . . .) ∈CHART such that all symbols on the right hand side of the rule are terminal symbols.

The algorithm executes all states iteratively in a top-down manner until no new states are available for processing. Given the statement A ⊑ B, the production rule S → B is used to initialize CHART.

Theorem 5. Given a acyclic HL TBox T in normal form and the statement of interest such that T |= A ⊑ B, with CFGT the context free grammar associated with T . If n is the number of production rules in CFGT , then Algorithm 2 computes a representation of all possible bidirectional reachability-based modules in O(n2) worst case running time.

Once Algorithm 2 terminates, the chart returned contains a representation of all possible bidirectional reachability-based modules, and hence a representation of all MinAs. This set is essentially an indexed bidirectionally reachable module.

In order to obtain all individual MinAs from the CHART returned by Algorithm 2, we introduce an algorithm to extract all minimal bidirectional reachabilitybased modules from it. Due to the space limitations of this paper we do not give an implementation of the algorithm but refer the interested reader to [ 5 ]. Theorem 6. Given the indexed bidirectional reachability-based HL CFG for the statement A ⊑ B, CFGO and the reference table CHART returned by Algorithm 2, the algorithm to extract all individual MinAs will extract all MinAs Mi such that Mi |= A ⊑ B. Each Mi will be extracted in O(m2) worst case running time, where m = |Sig(CFGO )|.

The algorithm introduced may be extended to extract all MinAs for acyclic E L TBoxes consisting of only primitive concept definitions. However, we show that though all MinAs for these TBoxes are minimal bidirectional reachabilitybased modules, the converse does not hold.

Example 4. Let T be an acyclic E L TBox consisting of only primitive concept definitions. Further, let M1 be a minimal bidirectional reachability-based module for the statement A ⊑ B consisting of the axioms A ⊑ ∃ r.C and C ⊑ B. Then M1rAe↔acBh = M1 and M1 is minimal, but M1 6|= A ⊑ B unless M1 |= B ⊑ ⊥ . Hence M1 is not a MinA for T |= A ⊑ B.

Theorem 7. Let T be an E L TBox consisting of only primitive concept definitions in normal form, and let A ⊑ B be a statement such that T |= A ⊑ B. Then for every minimal bidirectional reachability-based module Ni such that αL ⊑ ∃ r.C ∈ Ni we have that Ni 6|= A ⊑ B. Further, for every minimal bidirectional reachability-based module Mi such that αL ⊑ ∃ r.C 6∈ Mi we have that Mi |= A ⊑ B.

Consequently, the algorithms presented may be used in order to extract all minimal modules and thus MinAs for acyclic E L TBoxes consisting of only primitive concept definitions. When a minimal module includes axioms containing existential restrictions this module may simply be discarded as not being a MinA. The algorithm is complete in that it will extract all MinAs. However, since not all minimal modules extracted are MinAs, it is no longer sound. Soundness may however be obtained by simply making the test for the inclusion of existential restrictions part of the algorithm. When extending the problem of finding MinAs to general E L TBoxes, a staight forward extraction process is no longer possible and every possible matching between symbols needs to be calculated by the algorithm. Thus a simple iteration of all minimal bi-directional reachability based modules in order to find a single MinA results in an algorithm that runs in exponential worst case time.

Theorem 8. Let T be an acyclic general E L TBox in normal form and A ⊑ B a statement of interest. Let CHART represent the resultant reference set returned by Algorithm 2. Let M1 be a MinA such that M1 |= A ⊑ B and P1 represent the set of production rules for M1. Now let mi be the number of times a symbol Ci occurs on the right hand side of all production rules in P1 and let ki be the number of entries in CHART[Ci]. Then for the n possible symbols in P1 there n j=mi≤ki C(jki ) bidirectional reachability-based modules. are a total of Qi=1 Pj=1

Though we believe that this theoretical worst case complexity will not pose a problem for real world E L medical ontologies, subsumption testing will be required once each minimal module have been extracted.

Empirical Results

In this section we test the algorithms presented in this paper and evaluate their performance in terms of three real world biomedical ontologies2: OSnomed - The Systematized Nomenclature of Medicine, Clinical Terms; ONci - The Thesaurus of the US National Cancer Institute and OGo - The Gene Ontology.

The algorithms presented were all implemented in Java as part of a plugin for the Prot´eg´e 4.1 (beta) ontology editor. All single threaded algorithms were tested on a Intel Quad Core based computer, with 6 Gig of RAM, running on Microsoft Windows 7 x64 and hosted in a 64 bit Java virtual machine. We did not implement nor utilise an optimized subsumption testing algorithm for inexpressive DLs. Subsumption testing were done by the standard HerMit3 reasoner where neccesary.

Table 1 show the results of all bidirectional reachability-based modules extracted. The columns in the table are organised as follows: Ontology – the ontology for which the modules are being extracted; | OAreach | – the number of axioms in the reachability-based modules for all concepts A ∈Sig(O); T(OAreach) – the average time, in seconds, required by the algorithm to extract all reachabilitybased modules; | OAre↔acBh | – the average number of axioms for all bidirectional reachability-based modules; T(OAre↔acBh) – the additional time, in seconds, required to extract the bidirectional reachability-based modules, i.e. Total time = T(OAreach) + T(OAre↔acBh).

Average Values Ontology | OAreach | T(OAreach) | OAre↔acBh | T(OAre↔acBh) OGo 13.16 0.000032 4.48 0.000006 ONci 25.68 0.000048 5.59 0.000006 OSnomed 27.70 0.040725 18.40 0.000175

Maximum Values Ontology | OAreach | T(OAreach) | OAre↔acBh | T(OAre↔acBh) OGo 68 0.000417 20.15 0.000666 ONci 398 0.001916 55.00 0.000569 OSnomed 254 0.217781 222.06 0.004843

Median Values Ontology | OAreach | T(OAreach) | OAre↔acBh | T(OAre↔acBh) OGo 10 0.000026 3.86 0.000005 ONci 11 0.000026 4.37 0.000005

OSnomed 16 0.001800 6.66 0.000008

From the table we see that bidirectional reachability-based modules are between 30% and 80% smaller than standard reachability-based modules and may 2 http://lat.inf.tu-dresden.de/systems/cel/ 3 http://hermit-reasoner.com/ be extracted at the additional cost of between 0.4% and 19.0% in the running time of the algorithm. The average runtime increases for the GO and NCI ontologies tested may seem excessively high. However, we note that the running times are measured in the low microsecond range. At these extremely small intervals the accuracy of our measuring tools is very low and the true runtime performance of the algorithms only becomes evident in relatively large ontologies. Therefore, the runtime performance of the algorithms for the SNOMED ontology gives a more accurate measure of the true performance of the algorithms. In terms of median values extracting bidirectional reachability-based modules results in very stable performance across all ontologies tested, with an approximate 59% decrease in the size of all modules extracted.

The MinA extraction algorithms were tested as follows: for every concept name A ∈ in Sig(O) we extracted OAreach, then Algorithm 2 was called for each concept name B ∈Sig(OAreach) in order to extract OAre↔acBh. For each of these indexed bidirectional reachability-based modules we then extracted all possible minimal bidirectional reachability-based modules Mi. The standard HerMit reasoner was then called to test if Mi |= A ⊑ B. This subsumption test is irrelevant and is only included for the sake of interest.

The columns in Table 2 are organised as follows: Ontology – the ontology for which the MinAs are being extracted; | OAre↔acBh | – the average number of axioms for all bidirectional reachability-based modules; | M in(OAre↔acBh) | – the average number of minimal bidirectional reachability-based modules; T(M in(OAre↔acBh)) – the additional time, in seconds, required to extract all minimal bidirectional reachability-based modules; %MinAs – the percentage of minimal bidirectional reachability-based modules that are MinAs; |MinA| – the average size of each MinA and T(MinA) – the additional time required to test subsumption for all minimal modules, i.e. to calculate the total time to extract all MinAs from the ontology = T(M in(OAre↔acBh)) + T(MinA).

On average there are between 2 and 3 minimal bidirectional reachabilitybased modules for each possible subsumption statement. From these, about 90% are MinAs, each of which contains between 3 and 4 axioms on average. The total additional time required to extract all minimal bidirectional reachability-based modules, and thus MinAs, is in the low microsecond range. The most expensive costs incurred was subsumption testing, with a total running time for testing all minimal modules in the low to mid millisecond range. This testing however is unnecessary and is only included to illustrate the costs involved in testing all minimal modules for subsumption.

Once a bottom-up reachability-based module has been extracted, the additional runtime costs incurred to extract a bidirectional reachability module together with all minimal bidirectional reachability-based modules, and thus MinAs, is less that 1% of the cost of performing a subsumption test on a single MinA. This makes MinA extraction, for acyclic E L TBoxes consisting of only primitive concept definitions, negligible. The average reduction of 59% in the number of axioms for bidirectional reachability-based modules tested here, over that of standard reachability-based modules, indicates that for more expressive DLs in the E L family, bidirectional reachability-based modules may yield a significant improvement during MinA extraction to standard black-box algorithms.

Extension of the techniques presented here to more expressive DLs using hypergraph grammars, and relating it to the techniques and complexity results presented in [ 7 ], are topics of further research. We thank the anonymous reviewers for their comments on related and further work.

1. Ausiello , G. , Franciosa , P.G. , Frigioni , D. : Directed hypergraphs: Problems, algorithmic results, and a novel decremental approach . In: Proceedings of the Seventh Italian Conference on Theoretical Computer Science (ICTCS) , LNCS , vol. 2202 , pp. 312 - 327 . Springer, London, UK ( 2001 )

2. Du , J. , Qi , G. , Ji , Q. : Goal-directed module extraction for explaining OWL DL entailments . In: Bernstein, A. , Karger , D.R. , Heath , T. , Feigenbaum , L. , Maynard , D. , Motta , E. , Thirunarayan , K . (eds.) Proceedings ISWC'09, LNCS , vol. 5823 , pp. 163 - 179 . Springer, Berlin Heidelberg ( 2009 )

3. Earley , J.: An efficient context-free parsing algorithm . Communications of the Association for Computing Machinery 13 ( 2 ), 94 - 102 ( 1970 )

4. Grau , B.C. , Horrocks , I. , Kazakov , Y. , Sattler , U. : Modular reuse of ontologies: Theory and practice . Journal of Artificial Intelligence Research 31 , 273 - 318 ( 2008 )

5. Nortj´e, R.: Module extraction for inexpressive description logics . Master's thesis , University of South Africa ( 2011 ), submitted.

6. Nortj´e, R., Britz , K. , Meyer, T.: Finding E L+ justifications using the Earley parsing algorithm . In: Meyer, T. , Taylor , K. (eds.) Australasian Ontology Workshop 2009 ( AOW 2009) . CRPIT, vol. 112 , pp. 27 - 35 . ACS, Melbourne, Australia ( 2009 )

7. Pen˜aloza, R., Sertkaya , B. : On the complexity of axiom pinpointing in the EL family of description logics . In: Lin, F. , Sattler , U. , Truszczynski , M. (eds.) Proceedings KR-10 . AAAI Press, Toronto, Canada ( 2010 )

8. Sattler , U. , Schneider , T. , Zakharyaschev , M. : Which kind of module should I extract ? In: Grau, B.C. , Horrocks , I. , Motik , B. , Sattler , U . (eds.) 22nd International Workshop on Description Logics (DL2009) . CEUR-WS , Oxford, UK ( 2009 )

9. Suntisrivaraporn , B. : Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies . Ph.D. thesis , Technical University of Dresden ( 2009 )