# modular_structures_and_atomic_decomposition_in_ontologies__96e604b8.pdf

Journal of Artiﬁcial Intelligence Research 69 (2020) 963 1021 Submitted 05/2020; published 11/2020

Modular Structures and Atomic Decomposition in Ontologies

Chiara Del Vescovo chiara.delvescovo@bbc.co.uk British Broadcasting Corporation Data Management Team, Platform Data Media City UK, Salford, M50 2BH, UK

Matthew Horridge matthew.horridge@stanford.edu Stanford Center for Biomedical Informatics Research Stanford University California, 94305, USA

Bijan Parsia bijan.parsia@manchester.ac.uk Uli Sattler uli.sattler@manchester.ac.uk School of Computer Science University of Manchester Manchester M13 9PL, UK

Thomas Schneider thomas.schneider@uni-bremen.de Fachbereich 3 Mathematik/Informatik Universität Bremen Postfach 330 440, 28334 Bremen, Germany

Haoruo Zhao haoruo.zhao@manchester.ac.uk School of Computer Science University of Manchester Manchester M13 9PL, UK

With the growth of ontologies used in diverse application areas, the need for module extraction and modularisation techniques has risen. The notion of the modular structure of an ontology, which comprises a suitable set of base modules together with their logical dependencies, has the potential to help users and developers in comprehending, sharing, and maintaining an ontology. We have developed a new modular structure, called atomic decomposition (AD), which is based on modules that provide strong logical properties, such as locality-based modules. In this article, we present the theoretical foundations of AD, review its logical and computational properties, discuss its suitability as a modular structure, and report on an experimental evaluation of AD. In addition, we discuss the concept of a modular structure in ontology engineering and provide a survey of existing decomposition approaches.

1. Introduction

In artiﬁcial intelligence, knowledge representation is a prominent research topic that employs logic-based formalisms to make machines able to memorise, access, and process knowledge. In the past decades, the term ontology began to be widely used to denote a computerprocessable description of the knowledge about a domain of interest, its concepts, and their interrelations. A major class of ontology languages is based on description logics, for short

2020 AI Access Foundation. All rights reserved.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

DLs (Baader, Calvanese, Mc Guinness, Nardi, & Patel-Schneider, 2007), which generally are decidable fragments of ﬁrst-order logic. Hence, an ontology can be viewed as a ﬁnite set of ﬁrst-order formulas, called axioms. In particular, DLs provide the logical basis for the popular web ontology language OWL (Horrocks, Patel-Schneider, & van Harmelen, 2003; Cuenca Grau, Horrocks, Motik, Parsia, Patel-Schneider, & Sattler, 2008), which is a renowned standard (World Wide Web Consortium, 2012). Ontologies are used in manifold applications in areas such as knowledge representation and management, the semantic web, biology, medicine, linguistics, and economics (Poli, Healy, & Kameas, 2010), where they deﬁne unambiguous vocabularies, represent background knowledge, and facilitate knowledge sharing and integration. Particularly in medicine, large and comprehensive ontologies have been developed, prominent examples being SNOMED CT, the Systematized Nomenclature of Medicine Clinical Terms (Spackman, Campbell, & Côté, 1997) containing over 400,000 logical axioms, and NCIT, the National Cancer Institute s Thesaurus (Golbeck, Fragoso, Hartel, Hendler, Oberthaler, & Parsia, 2003) with more than 200,000 logical axioms. Both these ontologies cover a wide range of subjects, such as diseases, symptoms, operations, treatments, devices and drugs. Large ontologies pose serious challenges not only to the best optimised reasoners, but to all constituents of the ontology development process, such as navigation, editing, comprehension, and debugging. In addition, large ontologies are simply too broad for many purposes: for example, a user might be interested only in one medical speciality, say cardiology. It is therefore desirable to design speciﬁc applications, such as diagnostic decision support for cardiologists, in a way that they focus only on the relevant part of the ontology. For this reason, and following the design principle separation of concerns borrowed from modular programming, strong eﬀorts have been made to develop, maintain, and release ontologies organised into a modular structure, that is, a decomposition of an ontology into coherent fragments that may, or may not, loosely interact in a well-deﬁned, meaningful way. Module extraction and modularisation for ontologies have received great attention in recent years, in both theory and practice (Stuckenschmidt, Parent, & Spaccapietra, 2009). A-priori approaches aim at imposing a modular structure on an ontology to foster its modular development (Bao, Voutsadakis, Slutzki, & Honavar, 2009; Seraﬁni & Tamilin, 2009; Cuenca Grau, Parsia, & Sirin, 2009), while a-posteriori approaches provide techniques for module extraction and modularisation of existing monolithic ontologies (see, e.g., Cuenca Grau, Parsia, Sirin, & Kalyanpur, 2006; Konev, Lutz, Walther, & Wolter, 2008; Cuenca Grau, Horrocks, Kazakov, & Sattler, 2009; Konev, Lutz, Ponomaryov, & Wolter, 2010).1 The scenario described above and many similar ones clearly require a-posteriori approaches, simply because large ontologies currently exist in a monolithic, i.e., non-modular form. The a-posteriori approaches usually solve one of two tasks: Get One, i.e., the extraction of a single module, or Get All, i.e., the extraction of all modules or, more economically, the computation of the modular structure of an ontology, which comprises a representative subset of all modules together with their logical interactions. This modular structure has the potential to help users better understand the ontology, to aid ontology engineers in collaboratively developing it, and to optimise tool support, such as (incremental) reasoning. In this article,

1. Throughout this article, we use the term module in a strict sense, assuming that a module provides logical guarantees such as coverage, i.e., the preservation of entailments over a given signature (Ghilardi, Lutz, & Wolter, 2006; Konev, Lutz, Walther, & Wolter, 2009).

Modular Structures and Atomic Decomposition in Ontologies

we are concerned with a-posteriori approaches of the Get All category, i.e, the computation of the modular structure of a monolithic ontology. The search for a semantically grounded modular structure can be traced back to the 1980s, when the fundamental concepts of update and belief revision of a logical theory were investigated (Alchóurron, Gärdenfors, & Makinson, 1985). In the classical belief revision task, the input is a theory, given by a ﬁnite set of axioms (formulas in propositional logic), and an update: a single axiom that is possibly inconsistent with the theory. The goal is to modify the theory such that the inconsistency is resolved, and to add the update. In this context, the following natural question arises: which part of the theory is aﬀected by the update? Parikh (1999) deﬁned the notion of a signature decomposition for a logical theory, which partitions the signature (i.e., the non-logical vocabulary) of the theory and thereby induces a partition of the theory into signature-disjoint parts. The last condition guarantees that parts which do not share terms with the update can remain unchanged. Intuitively, the parts can be regarded as distinct, independent topics of the theory. Signature decomposition was reﬁned by Konev et al. (2010) for OWL ontologies, triggered by the observation that certain terms occur in many axioms of an ontology, thus prohibiting a decomposition into signature-disjoint parts. For example, the role (binary relation) has Part is typically used to deﬁne concepts belonging to various topics, such as anatomy, substances, vehicles, events. Konev et al. s approach allows to treat terms like has Part as logical symbols by manually grouping them into a separate signature , and to then decompose the remainder of the theory s signature, coining the name signature -decomposition for this technique. Both approaches decompose the signature and not the ontology itself. They induce a decomposition of the ontology s axioms, but that decomposition is of limited value as a modular structure: (1) due to the signature disjointness, there is no (Parikh) or very little (Konev et al.) logical connection between the parts; hence the strict requirement of signature disjointness leads to rather shallow modular structures; (2) the parts are not necessarily subsets of the input ontology, i.e., rewriting of axioms is allowed and even required; (3) algorithms for computing the signature decomposition and its ontology decomposition are restricted to rather inexpressive logics (i.e., DL-Lite and EL) but can still lead to an exponential number of parts compared to the size of the input ontology (Konev et al., 2010). An approach to decomposing the ontology itself was introduced by Cuenca Grau et al. (2006); it consists in computing the ﬁnest possible E-connection (Kutz, Lutz, Wolter, & Zakharyaschev, 2004) that is equivalent to the input ontology O (under certain assumptions). The result is a partition of the axioms of O with links between them, and an assignment of the terms in O to the parts of the partition. These parts are not necessarily signature-disjoint, but they have models of a certain shape: the extensions of any two terms assigned to distinct parts are disjoint, which nicely captures the intuition of distinct topics and the logical interactions between those, in the sense that the set of terms assigned to one part constitutes the topic of that part and the links indicate that the knowledge in O about one topic depends on knowledge in O about other topics. While this decomposition approach does not suﬀer from problems (2) and (3) described above, it still does not always yield a useful modular structure because certain modelling patterns allow only coarse-grained, topic-unaware decompositions. In the search for a modular structure that does not suﬀer from the previously encountered problems, we (Parsia & Schneider, 2010) started to investigate locality-based modules, for

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

short LBMs (Cuenca Grau, Horrocks, Kazakov, & Sattler, 2008) as a possible basis for a ﬁne-grained, well-connected, and easily computable modular structure. We chose LBMs because they provide strong logical guarantees and can be computed eﬃciently. The most important logical guarantee is coverage: given an ontology and a user-selected set of terms Σ, called a seed signature, an LBM for Σ preserves all the ontology s entailments formulated in Σ. The seed signature can thus be seen as determining a speciﬁc topic , and the corresponding LBM covers the ontology for this topic (but, in general, not for any diﬀerent topic). LBMs share coverage with other module notions, but unlike those, the syntactic variants of LBMs can be computed eﬃciently in logics up to the DL underlying OWL. The extraction of an LBM given Σ is a typical instance of the task Get One. In order to use LBMs in Get All, the most naïve approach would be to extract modules for all possible seed signatures. This is clearly unfeasible because the number of seed signatures is exponential in the size of the input ontology, and so is the number of modules: even though modules for distinct seed signatures often coincide, the exponential behaviour cannot be avoided in existing ontologies (Parsia & Schneider, 2010). It is hard to see how a modular structure of exponential size could help with any task that is complicated for medium-to-large ontologies. In order to obtain a useful modular structure despite these observations, we can distinguish fake modules i.e., those that are simply unions of other modules from genuine ones. As we have shown (Del Vescovo, Parsia, Sattler, & Schneider, 2011), there are only linearly many genuine modules, and they can be computed eﬃciently. While genuine modules can still overlap, they induce a partition of the input ontology together with a dependency relation between the parts, in a natural way. The resulting decomposition, as well as the overall technique, is called atomic decomposition (AD); in previous work we laid its theoretical foundations (Del Vescovo, Parsia, Sattler, & Schneider, 2011) and discussed some aspects of its usefulness in practice (Del Vescovo, Gessler, Klinov, Parsia, Sattler, Schneider, & Winget, 2011). This article gives a detailed account of AD and compares it with the preceding approaches to obtaining a modular structure. Its main contributions consist of

(Section 3) a qualitative analysis of the modular structures obtained by the previously described approaches, preceded by a discussion of the concept of a modular structure in ontology engineering and of the properties that a good modular structure should have;

(Section 4) a detailed presentation of the theoretical foundations of AD, extending our previous work (Del Vescovo, Parsia, Sattler, & Schneider, 2011) with a discussion of the modular structure induced by AD and with comments on using module notions other than LBMs as the basis of AD;

(Section 5) an experimental evaluation of AD, updating our previous empirical study (Del Vescovo, Gessler, Klinov, Parsia, Sattler, Schneider, & Winget, 2011) with a representative up-to-date ontology corpus, and a corrected implementation.

In addition, we deﬁne the basic concepts around modules in Section 2 and conclude in Section 6. This work is an extension to earlier work on atomic decomposition and modular structures of ontologies by some of the same authors: decompositions using E-connections were described

Modular Structures and Atomic Decomposition in Ontologies

and investigated by Cuenca Grau et al. (2009), and Cuenca Grau, Parsia, and Sirin (2006); Del Vescovo, Parsia, Sattler, and Schneider (2011) laid the theoretical foundations of ADs; Del Vescovo, Gessler, Klinov, Parsia, Sattler, Schneider, and Winget (2011) described an early analysis of the structure of ADs of existing ontologies; Klinov, Del Vescovo, and Schneider (2012) discussed an approach to persist the AD; Del Vescovo s dissertation (2013) discussed both the theoretical foundations and early experimental evaluation of ADs, but both have been signiﬁcantly advanced in this paper. In particular, Section 2 and 5 are new, and Sections 3 and 4 have been completely reworked.

2. Preliminaries

We assume the reader to be familiar with description logic, in particular to have a good understanding of the description logics ALC or SROIQ (Baader, Horrocks, Lutz, & Sattler, 2017; Horrocks, Kutz, & Sattler, 2006) including their syntax and semantics, ontologies, interpretations and models, and entailment relation. In this section, we only ﬁx the core notations of description logics and repeat some well-established key notions around module extraction (Ghilardi et al., 2006; Konev et al., 2009; Kontchakov, Pulina, Sattler, Schneider, Selmer, Wolter, & Zakharyaschev, 2009; Cuenca Grau et al., 2009).

2.1 Conservative Extensions, Inseparability, and Modules

We start with the basic deﬁnitions underlying most logic-based notions of modules. Let O denote an ontology, i.e., a ﬁnite set of axioms. An axiom can be a general concept inclusion, a role inclusion, a concept assertion or a role assertion. We use NC for a set of concept names and NR a set of role names. A signature is a set Σ NC NR of terms. Given a concept, role, axiom, or ontology X, the set of all terms occurring in X is called the signature of X, and denoted by e X. We use SOL for second-order logic, and use L for a description logic or a subset of SOL. For an interpretation I and an ontology O, we write I |= O if I is a model of O, and we use I|Σ to denote the restriction of I to the signature Σ. The consequence relation of SOL and standard DLs is known to be monotonic, i.e., extending an ontology with additional axioms preserves its previous consequences.

Deﬁnition 2.1 (Ghilardi et al., 2006; Konev et al., 2009). Let O be an L-ontology, M O, and Σ a signature. We say that

1. O is a deductive Σ-conservative extension (Σ-d CE) of M w.r.t. L if, for all L-axioms α with eα Σ, it holds that M |= α if and only if O |= α;

2. O is a model Σ-conservative extension (Σ-m CE) of M if {I|Σ | I |= M} = {J |Σ | J |= O};

3. M is a m CE-based (d CE-based) module for Σ of O (w.r.t. L) if O is a Σ-m CE (Σ-d CE) of M (w.r.t. L);

4. If M is a d CE-based module for Σ w.r.t. L, we also say that M covers or provides coverage to O for Σ.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Since M O, the monotonicity of L implies that the only if direction of Point 1 in Deﬁnition 2.1 holds trivially. Furthermore, for a description logic or subset of SOL L, every m CE-based module is also a d CE-based module w.r.t. L; the converse is not necessarily the case unless L is equally expressive as SOL.

In order to abstract from the requirement that M is a subset of O, the notion of an inseparability relation has been introduced.

Deﬁnition 2.2 (Konev et al., 2009). Let L be a logic, O1 and O2 two L-ontologies, and Σ a signature. We say that

1. O1 and O2 are model inseparable w.r.t. Σ, written O1 m CE Σ O2, if {I|Σ | I |= O1} = {I|Σ | I |= O2};

2. O1 and O2 are deductively inseparable w.r.t. Σ in L, written O1 d CE-L Σ O2, if, for all L-axioms η over Σ, we have that O1 |= η if and only if O2 |= η.

The equivalence relations R Σ are deﬁned upon the notion R {m CE, d CE-L}, and R is called an inseparability relation. Whenever L is clear from the context, we will omit it.

Please note that other notions of inseparability relations can be deﬁned (Konev et al., 2009; Sattler, Schneider, & Zakharyaschev, 2009; Kontchakov, Wolter, & Zakharyaschev, 2010), though for the purposes of this paper we will consider only the inseparability relations R {m CE, d CE-L}.

The following property of monotonicity is of crucial importance for the inseparability relations just deﬁned, and will have a deep impact on the properties of modules of interest in this paper.

Deﬁnition 2.3 (Kontchakov et al., 2009). An inseparability relation R is called monotonic if, for all ontologies O1, O2 and O3 and each signature Σ, it satisﬁes the following conditions.

(Msig) if O1 R Σ O2, then O1 R Σ O2 for each Σ Σ;

(Maxs) if O1 O2 O3 and O1 R Σ O3, then O1 R Σ O2.

The inseparability relation R = m CE is monotonic, which is an easy consequence of the monotonicity of SOL. Analogously, for every monotonic DL L, R = d CE-L is monotonic.

Inseparability relations induce modules, while abstracting away from the above restriction to m CE and d CE, from a concrete language L, and from the requirement M O:

Deﬁnition 2.4. Let R be an inseparability relation, M and O two ontologies, and Σ a signature. We call M

1. an RΣ-module of O if M R Σ O;

2. a self-contained RΣ-module of O if M R Σ f M O;

3. a depleting RΣ-module of O if O \ M R Σ f M .

Modular Structures and Atomic Decomposition in Ontologies

M is called a minimal (self-contained, depleting) RΣ-module of O if M, but no proper subset of M, is a (self-contained, depleting) RΣ-module of O.

Deﬁnition 2.4 is a generalisation of the original deﬁnition by Kontchakov et al. (2009), which additionally assumed M O. We have dropped this assumption because some of the decomposition approaches introduced later will induce modules that are, in general, not subsets of the input ontologies. However, the notion of a minimal module will be used in this article only in connection with modules that are subsets. To ease notation, we will omit the symbol Σ from the notion R of an inseparability relation whenever the speciﬁc signature Σ is irrelevant.

2.2 Computational Issues: a Summary

Unfortunately, deciding whether a fragment M of an ontology O is an RΣ-module for R {m CE, d CE-L}, and thus the computation of a module, is computationally hard except for very lightweight ontology languages: while m CEs can be decided in PTime for acyclic ELI ontologies (Konev et al., 2008), they are decidable and co NExp-hard for some fragments of DL-Lite (Kontchakov et al., 2010), and undecidable already for general EL ontologies (Lutz & Wolter, 2010) and acyclic ALC ontologies (Konev, Lutz, Walther, & Wolter, 2013). Restricting the signature Σ to contain only concept names may lower the complexity somewhat or regain decidability for EL and ALC, see Konev et al. s Table 1 (2013). The computational behaviour of d CEs is slightly better but still prohibitive: deciding d CEs is Exp Time-complete for EL (Lutz & Wolter, 2010), 2Exp Time-complete for ALC (Ghilardi et al., 2006) and ALCQI (Lutz, Walther, & Wolter, 2007), and undecidable already for ALCQIO (Lutz et al., 2007) and thus for SROIQ. In face of the high computational complexity of identifying modules in general, various lines of research have been pursued which either restrict the ontology language, or provide useful approximations; the next subsection provides an overview.

2.3 Existing Module Notions

Specialised methods have been developed for inexpressive DLs; the MEX approach (Konev et al., 2008) extracts, under certain conditions, minimal self-contained and depleting modules from acyclic ELI terminologies in polynomial time; the method described by Kontchakov et al. (2009) does the same for DL-Lite ontologies, whereas the AMEX approach (Gatens, Konev, & Wolter, 2014) describes a closely related method for acyclic ALCQI terminologies. Approximation methods have been designed for DLs as expressive as SROIQ: the family of locality-based modules, for short LBMs (Cuenca Grau et al., 2008) are self-contained, depleting modules which are possibly non-minimal, i.e., may contain axioms that are not relevant to preserve entailments over the given seed signature Σ or the module s signature. There are various ﬂavours of locality-based modules: there are syntacticand semanticmodules as well as syntacticand semanticones, as well as their nested version like the syntacticmodule and more. For various expressive description logics, syntactic locality-based modules can be extracted in polynomial time (Cuenca Grau et al., 2008). In more recent work, the notion of (syntactic) locality has been extended in at least two directions by introducing interesting data structures which, for a given ontology, represent relevant dependencies between terms and underlie the process of extracting a module. The

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

ﬁrst such extension uses (hyper)graphs to describe dependencies between signatures of sets of axioms, i.e., seed signatures of modules. This approach and the resulting reachability-based modules (RBMs) have been developed by Suntisrivaraporn (2008) and extended to SRIQ and SROIQ by Nortjé, Britz, and Meyer (2013). Similarly to LBMs, RBMs come in three ﬂavours , , and . While, for ontologies in a certain normal form, -RBMs coincide with -LBMs, the other two variants are usually subsets of the corresponding LBM variant and are neither self-contained nor depleting; however, all variants are robust under a number of interesting operations such as vocabulary restrictions and extensions (Nortjé et al., 2013). Furthermore, a diﬀerent hypergraph representation and the same normal form have been used by Martín-Recuerda and Walther (2014) to compute -LBMs more eﬃciently. The second extension of locality-based modules represents dependencies between terms in a datalog program. This approach, developed by Armas Romero, Kaminski, Cuenca Grau, and Horrocks (2016) for DLs up to SROIQ, provides a whole suite of module notions covering a wide range of inseparability relations. Some of these notions have been shown to be depleting and self-contained, and to satisfy further useful properties, such as the preservation of justiﬁcations (Armas Romero et al., 2016). Projection and subsumption modules (Chen, Ludwig, & Walther, 2018; Chen, Ludwig, Ma, & Walther, 2019b) diﬀer from the above mentioned kinds of modules in that they aim at preserving speciﬁc kinds of entailments (over a signature) rather than all entailments, and at minimality. Deductive modules (Koopmann & Chen, 2020), in contrast, aim at preserving all entailments in a given language and signature, and even all justiﬁcations for these entailments; they are computed using uniform interpolation and thus use only the terms from the speciﬁed signature. In some sense orthogonal to the module notions discussed so far, E-connections (Kutz et al., 2004) give rise to another notion of self-contained modules, which will be discussed in more detail in Section 3.3.3. As a result, we have various notions of modules with diﬀerent properties, and various algorithms to extract these: some run in polynomial time, some only work on input ontologies of a restricted form but ensure minimality, some work on SROIQ ontologies but do not guarantee minimality. In general, these properties are mostly incompatible: a module notion that guarantees minimality can usually not guarantee uniqueness, depletingness, or selfcontainedness. In addition to the theoretical work, various studies have investigated how the choice of a module notion aﬀects the relative size of modules in practice (Konev et al., 2008; Kontchakov et al., 2009; Del Vescovo, Klinov, Parsia, Sattler, Schneider, & Tsarkov, 2013; Nortjé et al., 2013; Gatens et al., 2014; Chen et al., 2018, 2019b; Koopmann & Chen, 2020), and indeed it turns out that locality-based modules are often larger than other kinds of modules. Algorithms for extracting AMEX modules, LBMs, RBMs, and DBMs have been implemented in various tools, such as AMEX, the OWL API, CEL, and Pris M; links are provided in the original articles.

All module notions discussed so far are based on the requirement that a module of an ontology O be a subset of O. However, in this article we also discuss modules in a broader sense, i.e., ontologies obtained by rewriting (parts of) O. The signature decomposition approaches discussed in Sections 3.3.1 and 3.3.2 implicitly yield such modules, whose existence is ensured by certain interpolation properties of the underlying logic (Konev et al., 2010). In particular, uniform interpolants (UIs) can be used to yield (non-subset) modules with

Modular Structures and Atomic Decomposition in Ontologies

very similar logical guarantees, including Σ-inseparability. UIs have been studied widely for DLs of various expressivity (e.g., by ten Cate, Conradie, Marx, & Venema, 2006; Wang, Wang, Topor, Pan, & Antoniou, 2009b; Lutz & Wolter, 2011; Lutz, Seylan, & Wolter, 2012; Nikitina & Rudolph, 2014; Koopmann & Schmidt, 2014, 2015) and are closely related to (in fact, they are the dual notion of) forgetting (Reiter & Lin, 1994; Lang, Liberatore, & Marquis, 2003; Eiter, Ianni, Schindlauer, Tompits, & Wang, 2006; Konev, Walther, & Wolter, 2009; Wang, Wang, Topor, Pan, & Antoniou, 2009a; Zhao & Schmidt, 2017, 2018b; Chen, Alghamdi, Schmidt, Walther, & Gao, 2019a).

The signature decomposition approaches discussed in Sections 3.3.1 and 3.3.2 are related to UIs, but we are not aware of any work that addresses the computation of modules from a signature decomposition directly. All other decomposition approaches discussed in this article are concerned with modules that are subsets of the input ontology. Furthermore, the precise relationship between module-speciﬁc properties and UIs/forgetting-based modules are not yet known, except for the insight that module extraction can be used as an optimisation to forgetting (Chen et al., 2019a). For this reason, a further discussion of UIs is beyond the scope of this article.

2.4 General Remarks

In the following sections, we will focus mainly on description logics, and mainly on logics without nominals: this is due to the fact that nominals are rather ill-behaved in general for example, they lead to the loss of nice model properties such as the tree model property and the property that models are closed under disjoint union which causes serious problems for module extraction.

As indicated above, we consider module notions where each module is a subset of the ontology, and module notions where this is not necessarily the case. Please note that the former preserves the integrity of axioms, which is important for some applications, e.g., where axioms are annotated with their provenance. This preservation comes, however, at a cost: it is well known that the TBox O = {Ci D | 1 i n} is equivalent to its singleton counterpart O = { d 1 i n Ci D}, yet O has 2n subsets all of which are -locality based modules, whereas O only has two subsets, and itself, and thus at most two subset modules. Hence subset-based module notions are syntax dependent, i.e., equivalent ontologies may lead to diﬀerent, non-equivalent modules.

3. Qualitative Analysis of Existing Modular Structures

In this section we discuss the concept of modular structure in ontology engineering, in particular the properties that a good modular structure of an ontology should have so that it supports various knowledge engineering tasks. We start with a general discussion of these points in analogy to software engineering. Then we focus on the modular structure of ontologies, where some interesting problems arise from the fact that entailments behave like side eﬀects that are diﬃcult to control. Finally, we discuss existing approaches to modular structures and their behaviour with respect to the above mentioned properties.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

3.1 Core Concepts in Modular Engineering

Before looking at modular design in knowledge engineering, we discuss modularity in software design to clarify relevant concepts. In software engineering, the decomposition of pieces of code into suitable modules has been studied since the late 1960s. Parnas (1972) recommends the use of functional modules, i.e., modules incorporating a function, rather than sequential modules, i.e., modules determined by the temporal sequence of actions to perform. These modules are combined via interacting with the modules interfaces, i.e., their input and output parameters. This allows for a separation of concerns where distinct modules implement distinct, independent functionalities. The system obtained is then independent of the speciﬁc implementation inside each of its modules; in other words, a module has a functional core which is (relatively) independent of other parts of the code. Nowadays this property is called encapsulation. A closely related concept is that of information hiding: not only is the system agnostic as to how a given module implements its functionality, it also cannot aﬀect this implementation. That is, the module s functionality is protected from changes outside the module, and the rest of the system knows of the module s interface only. Furthermore, a good module should implement one functionality rather than several independent ones; thus a good module has a high cohesion, with all its parts being strongly related. A system with a module of low cohesion can usually be improved by splitting this module into several ones. Consequently, modules need to be able to contain (or import) others, which naturally leads to a dependency structure between modules: module A depends on module B if A imports B or requires B s presence via some other mechanism to function correctly. The advantages of a good modular design are clear: a module is usually a small part of the whole (software) system, and thus easier to work with; diﬀerent people can work on diﬀerent modules independently and only need to agree on changes to interfaces or functionality; and modules can be reused, i.e., used in diﬀerent software systems. The main focus in software engineering was placed on the mechanisms to realise encapsulation and specify/work with interfaces, on methodologies to build systems in a suitable modular way where modules are of suitable size and structure, in particular of a hierarchical or nested structure, and on reusability of existing modules. There has been some work on automated support for code refactoring, in particular for refactoring spaghetti code (monolithic code) into suitable modules, and state-of-the-art IDEs provide this kind of tool support. This support, however, usually leaves existing classes intact and only moves these into other packages, i.e., it starts from an existing modular structure and rearranges it without introducing new modules or merging modules.

In logic-based knowledge engineering, a modular design has potentially the same beneﬁts as in software engineering, so we are discussing the concepts developed for modular software systems in the context of ontology engineering. For modules of ontologies, various properties have been introduced in the literature (Cuenca Grau et al., 2009; Konev et al., 2009; Kontchakov et al., 2009), see Section 2.1. We now relate these to those developed for modular software systems. First, throughout this paper, we focus on the problem of refactoring a given ontology into a suitable set of modules, i.e., on the problem of automatically turning a monolithic spaghetticode ontology into one that exhibits a good modular structure. One of the problems here is that an ontology itself exhibits very little structure: instead of variables, functions, classes,

Modular Structures and Atomic Decomposition in Ontologies

methods, loops, or function calls, we only have a set of axioms, without an order, in which terms (co-)occur. In addition, there are many ways to rewrite axioms into equivalent ones and change the cooccurrence relation between terms, e.g., A (B C) is equivalent to A B, A C. As we have seen in Section 2.2, the extraction of a single minimal module for a given signature is a complex problem which may not even be computable, depending on the exact properties of the desired module and the underlying logic. The task of computing a suitable range of modules for a given ontology is even more diﬃcult but will be at the heart of the envisaged refactoring support; thus its complexity needs to be considered. Second, let us discuss the notion of a module s interface: from the above understanding of an interface as a set of parameters that ensures encapsulation, an obvious candidate for an interface of an ontology module is the set of terms Σ such that M is RΣ-inseparable from O. In this case, M encapsulates the full functionality of O regarding terms from Σ. There are, however, two problems with this idea. Firstly, this interface would not be unique. Example 3.1. Consider the following ontology O:

α : A B (C D) β : C D γ : B D

Then, M = {α, β} preserves all entailments over both Σ1 = {A, B} and Σ2 = {A, C, D}, and so it would make sense to consider Σ1 and/or Σ2 as interfaces for M. However, M does not preserve all entailments over Σ1 Σ2; e.g., the entailment B D is lost. Secondly, we would need to record, or reconstruct, for each module, the sets of terms it covers: this would either lead to a more complex structure (of sets of axioms with their interfaces) or be computationally costly. As an alternative, we can require modules to be self-contained, i.e., to cover all the terms they mention. In Example 3.1, the smallest self-contained subset of O that preserves all entailments over Σ1 is O itself. The notion of modules with explicit interfaces has been discussed in the literature (Bao et al., 2009; Cuenca Grau et al., 2009; Seraﬁni & Tamilin, 2009); here, we will concentrate on self-contained modules since, to the best of our knowledge, there is no logically sound approach to decomposing or refactoring ontologies that yields explicit interfaces. Coverage guarantees that, for a given signature, we can use its module instead of the whole ontology because the module preserves all entailments over this signature. That is, coverage is closely related to encapsulation: a covering module does not rely on external information to fulﬁl its functionality. Modules being depleting is also closely related to encapsulation: modules providing (only) coverage are called weak modules by Konev et al. (2008) because coverage alone does not guarantee encapsulation: it can happen that the same logical consequences of a module M are entailed also by O \ M, as described in the following example. Example 3.2. Consider the following ontology.

Sea = { has Fin. Fish, Dolphin has Caudal Fin. , has Caudal Fin has Fin } Dolphin, where

Dolphin = { Dolphin Fish, Mammal Fish, Dolphin Mammal }

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Clearly, the ontology Dolphin is a logical module of the ontology Sea for the signature Σ = {Dolphin}, and thus preserves the entailment η : Dolphin . Now consider that we want to repair this unsatisﬁability: we remove the axiom α : Dolphin Fish from Dolphin to yield Dolphin and Dolphin no longer entails η. However, replacing Dolphin with Dolphin in Sea results in an ontology that still entails η, i.e., our modular repair did not work globally. This is due to the fact that Dolphin is not a depleting module and thus does not encapsulate all our knowledge about Dolphins.

The deﬁnition of a depleting module would need to be adapted for cases where a module M is not a subset of O: we would need to deﬁne an alternative to the extraction of a module, i.e., to O \ M, via a suitable rewriting mechanism. Self-containment, which has already been mentioned above, guarantees that all terms in a module are equal, regardless of whether they are in the seed signature of this module or not. Given the above observations regarding a module s interface, a module needs to be self-contained to ensure that all its terms can reasonably be used as its interface. In other words, if a module is not self-contained, then it is only functional with respect to its seed signature, but possibly not for other terms. Finally, it is not hard to see that modules in particular when they are subsets of an ontology can contain other modules, and thus may form a nested structure. One module containing another one can be seen as the former depending on the latter, and thus this containment relation induces a natural dependency relation between modules. Alternatively, in case where modules are subsets of an ontology, we can consider the partition induced by such nested modules. This partition consists of a set of atoms that we can combine to form our original set of modules. In OWL, we can store each atom as an OWL document and combine our modules via suitable imports statements. There is a direct one-to-one relation between this imports relation and the above mentioned dependency relation.

Next, we discuss two notions from software engineering that are more diﬃcult to transfer to ontology modules. Cohesion is a notion that depends on what we mean by a module s parts and their relatedness. For ontology modules, we could say that a module is of low cohesion if it contains axioms that are not strongly related. While it is diﬃcult to deﬁne precisely what strong (logical) relatedness means, it is possible to illustrate some extreme cases. For example, the weakest relatedness possible occurs between modules sharing neither axioms nor terms. But even if two axiom-disjoint modules share signature to some extent, they may still be widely unrelated, e.g., when the shared terms are only top-level concepts. Even two modules sharing axioms may be widely unrelated, e.g., when they share only tautologies. Consequently, it is reasonable to consider the union of two axiomand term-disjoint modules to be of very low cohesion, and the union of two substantially diﬀerent (for example, axiombut not term-disjoint) modules to be of low cohesion. Regarding information hiding, we ﬁrst note that, if modules are mere sets of axioms, we have no way to specify which terms are private to a module; see above the discussion of interfaces. Hence in this setting, there can be no true support for information hiding. We can still ask, however, whether terms from a module are used safely in the rest of the ontology, i.e., whether they are only used (but not changed) or whether their meaning is changed in axioms outside the module. The following example shows how information hiding or safe usage of terms can be tricky.

Modular Structures and Atomic Decomposition in Ontologies

Example 3.3. Let us consider the following ontology.

Dolphin = { Dolphin ( has Part.Caudal Fin), Fish Vertebrate }

Now suppose we now want to add Dolphin to our own ontology Fish:

Fish = { Fin ( has Part .Fish), Caudal Fin Fin }

Looking only at the signature and observing that our Fish ontology does not relate terms from Dolphin with each other, it might seem that the Fish ontology uses the terms from Dolphin in a safe way. However, taking the logical interactions into account, it turns out that Dolphin Fish |= Dolphin Fish, i.e., adding Dolphin to Fish causes new entailments over the signature of Dolphin , and thus Fish does not use the terms from Dolphin safely.

Fortunately, inseparability can also be used to formulate safety: given an inseparability relation R, we can say that O can safely use M if O R f M , i.e., if O does not know anything about the terms in M (Jiménez-Ruiz et al., 2008).

3.2 Core Notions of Modular Ontology Structures

Motivated by the discussion in the previous section, we will brieﬂy summarise the core notions related to modular structures of ontologies. In what follows, we use R for an inseparability relation and say that an R-module M of an ontology O is an ontology that is R-inseparable w.r.t. f M from O. In other words, M is self-contained, but not necessarily a subset of O, i.e., a module can be obtained by rewriting some axioms in O: for example, one could split an axiom A B1 B2 O into two axioms/modules A Bi Mi. Also, depending on the module notion, there does not have to be a seed signature Σ that determines M. If there is a seed signature, then diﬀerent seed signatures Σ = Σ may lead to the same module, which is then said to cover both these signatures, as well as f M given that M is self-contained. As discussed in Section 2, various notions of modules fall into this category, including any form of semantic or syntactic locality-based modules, MEX modules, or nested modules like the module. Let O be an ontology and x a module notion, which can be understood as a function that assigns an RΣ-module MΣ O to every signature Σ, for a ﬁxed inseparability relation R. We call MΣ the x-Σ-module of O; it does not need to be the smallest RΣ-module of O. Ideally, there is an algorithm for computing MΣ given Σ and O (see, e.g., Cuenca Grau et al., 2008; Konev et al., 2008). A modular structure for x of O is a pair (G, ) where G is a set of modules of O and is a binary dependency relation between elements of G. A modular structure is also associated with a module generation mechanism that describes how to generate, for a given signature Σ the x-Σ-module M of O from (G, ). The simplest form of the dependency relation is the subset relation and this is also the one taken in all notions of modular structures discussed in this paper. In this case, and where modules are subsets of the ontology, G gives rise to a partition of O into atoms where

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

each module is a (disjoint) union of atoms. The module generation mechanism can be rather simple, for example, by taking the union of all those Mi G with g Mi Σ = . It could also be a complex mechanism, with the extreme being the computation of the x-Σ-module from scratch. We call the modules in G basic modules, and those x-modules that are not basic derived. As discussed earlier, the basic modules should be of high cohesion and are thus likely to be small; thus modular structures should tend to have a high granularity. Given that the basic modules should form a reasonable basis for all x-modules, we expect G to be minimal, i.e., to contain only those modules that cannot be derived via the module generation mechanism.

3.3 Existing Approaches to Determining the Modular Structure

In this subsection we describe three existing approaches to specifying the modular structure of an ontology that provide logical guarantees such as coverage. These approaches are Parikh s signature splitting (Parikh, 1999), signature -decomposition (Konev et al., 2010), and decomposition based on E-connections (Cuenca Grau et al., 2006). All these approaches consist in computing a partition of either the ontology (i.e., its set of logical axioms) or the ontology s signature (i.e., the set of all entities occurring in it). The last two of these approaches additionally include a non-trivial dependency relation between the modules. We will also discuss a fourth approach, namely an early attempt at identifying a modular structure based on all x-Σ-modules of an ontology (Parsia & Schneider, 2010) for a given module notion x, which has eventually led us to the notion of atomic decomposition as described in Section 4. We describe each of these approaches and discuss some examples; then we discuss its relevant properties: the properties of the (basic and derived) modules, the cohesion of the basic modules, the dependency relation and thus granularity of the structure, the module generation mechanism, and the computational properties of identifying a modular structure. We also discuss how the diﬀerent approaches relate to each other.

3.3.1 Parikh s Signature Splitting

The logical formalisation of this ﬁrst notion of modular structure was introduced by Parikh (1999) in the context of belief revision. Its application scenario can be described generally as follows. One wants to revise an ontology2 O by adding a new piece of knowledge that contradicts (some entailment of) O. Parikh s splitting approach is intended to address the following question: to identify contradictions, do we have to check the new knowledge against all of O, or can we make use of some kind of safety guarantee that allows us not to touch those parts that are irrelevant for this new ﬁnding? The approach is based on the simple observation that, under certain conditions, two logical formulas (or axioms of an ontology) that have disjoint signatures cannot logically interact with each other. Consequently, if O can be split into signature-disjoint parts, these parts do not logically interact with each other, and not all parts are relevant for freshly added knowledge. Parikh devises a principled way to perform such a splitting.

2. Parikh s original deﬁnition applies to logical theories in SOL. It should be clear that we can continue to use the notion of an ontology instead.

Modular Structures and Atomic Decomposition in Ontologies

Deﬁnition 3.4 (Parikh, 1999). Let L be a fragment of SOL, O an ontology in L, and {Σ1, . . . , Σn} a partition of e O. We say that Σ1, . . . , Σn split O in L if there are ontologies O1, . . . , On in L with f Oi = Σi, i n, whose union is logically equivalent3 to O. We then call {Σ1, . . . , Σn} an O-splitting and O1, . . . , On a realisation of {Σ1, . . . , Σn}.

Clearly, every ontology O has at least one O-splitting, { e O}. In general and if no further assumptions are made, any O can have several splittings. However, in SOL there is always a unique ﬁnest O-splitting: the component-wise intersection of two splittings is ﬁner and has again a realisation; the latter is not guaranteed in all fragments of SOL, see also the discussion in Section 3.3.2. More precisely, a splitting {Σ1, . . . , Σn} reﬁnes a splitting {Π1, . . . , Πm} if both are distinct and every Πi is the union of one or more Σj. For example, {Σ1, Σ2, Σ3, Σ4} reﬁnes {Σ1 Σ2 Σ3, Σ4}. A ﬁnest O-splitting is an O-splitting that reﬁnes every other O-splitting.

Theorem 3.5 (Parikh, 1999). Every ontology O has a unique ﬁnest O-splitting in SOL.

Modules and their properties. In Parikh s splitting approach, a logical module of O is an ontology O1 such that the signature partition { e O1, e O \ e O1} splits O. We call the Oi from Deﬁnition 3.4 the Parikh modules of O and their collection {O1, . . . , On} the Parikh modularisation of O. It has to be pointed out that the Oi are not required to be subsets of O. Furthermore, they have to be considered modulo logical equivalence, which we do from here on. Since Parikh s original work is focusing on SOL, any ontology (ﬁnite set of formulae) can be equivalently expressed by a single formula. Hence, it may be the case that the set O is a singleton, but Parikh s splitting is non-trivial. Example 3.6. Let us consider the singleton ontology:

One = { ( A1 B1) ( A2 B2) ( An Bn)}

One can be rewritten into the logically equivalent ontology

All = {A1 B1, A2 B2, . . . , An Bn}

Hence, the signature partition Σ1 = {A1, B1}, . . . , Σn = {An, Bn} splits One. It is easy to see that every Parikh module Oi of an ontology O provides coverage and is self-contained: this immediately follows from Deﬁnition 3.4: f Oi is disjoint from the signatures of the remaining Oj, and the union of all Oj is logically equivalent to O. In general, the Oi are not depleting because they are not necessarily subsets of O; see the remark in Section 3.1. To discuss cohesion, we use two simple example ontologies. Example 3.7. Let us consider the following ontology.4

Tree = { Tree is Made From.Seed, Seed is Made From.Fruit, Fruit is Made From.Flower, Flower is Made From.Branch, Branch is Made From.Tree, Mountain is Made From.Soil }

3. In the following, we use equivalent for logically equivalent, i.e., for having the same models. 4. This ontology is an adaptation and translation into DL of some fragments from the Italian song Ci vuole un ﬁore (It requires a ﬂower), by G. Rodari, L. Enriquez, and S. Endrigo.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Parikh s splitting consists of a single part containing all the terms in Tree. However, there is a clear logical diﬀerence between the set of terms Σ1 = {Tree, Seed, Fruit, Flower, Branch} and the set Σ2 = {Mountain, Soil}: by interpreting Tree as the empty set, all the other terms in Σ1 are unsatisﬁable, whilst there is no constraint in the interpretation of the terms in Σ2. Similarly, by interpreting Soil as the empty set we get that Mountain is unsatisﬁable, whilst there is no constraint in the interpretation of the terms in Σ1. However, we cannot separate these two sets because they share the term is Made From, so that Tree cannot be rewritten as the union of two signature-disjoint ontologies. Example 3.7 shows that the induced notion of cohesion is rather loose. Indeed, two terms A and B belong to the same module if there is an arbitrarily long sequence of intermediate terms {Ai | i n, n N} such that A interacts (in the model-theoretic sense described above) with A0, Ai interacts with Ai+1 for all i {0, . . . n}, and An interacts with B. However, A and B may still not directly interact with each other; see the following example. Example 3.8. Let us consider the family Zigzag of ontologies, deﬁned by

Zigzagn = {A1 B1, A2 B1, A2 B2, . . . , An Bn, An+1 Bn},

with the following graphical representation.

For n 1, the concepts A1 and An+1 are completely unrelated since Zigzagn has only trivial entailments over the signature {A1, An+1}. However, A1 and An+1 still belong to the same Parikh module. Regarding information hiding, we note that, under certain circumstances,5 distinct Parikh modules are completely unrelated, i.e., they share neither axioms nor terms. As a consequence, we can take the union of diﬀerent modules and this will not aﬀect the meaning of any terms described in any of them, and thus they can always import/be imported safely.

Modular structure and its properties. Thanks to Theorem 3.5, we can deﬁne a modular structure of an ontology O as follows: the basic modules are those Oi that determine the ﬁnest O-splitting; the derived modules are their unions. The latter coincide with the Parikh modules; hence the basic modules are indeed representative of all Parikh modules. The module generation mechanism is simple: given an ontology O with the basic modules O1, . . . , On and a signature Σ, the Parikh-Σ-module of O is the union of all Oi with f Oi Σ = . There is no logical interaction between any two distinct basic modules because of their disjoint signatures. Hence the dependency relation is empty (i.e., the dependency graph consists of n isolated nodes). Furthermore, the granularity of the modular structure varies in the same way as the cohesion of its modules does, see the examples above.

Computational properties. Parikh s work (1999) does not study computational properties of signature decomposition or of computing a module. However, some insights can be transferred from the analysis of signature -decompositions (Konev et al., 2010), which generalise Parikh splittings and are discussed in the following subsection.

5. This is true for propositional logic and all DLs where models are preserved under disjoint unions, i.e., for the SHIQ family or DLs without nominals.

Modular Structures and Atomic Decomposition in Ontologies

3.3.2 Signature -Decomposition

The modules induced by the ﬁnest O-splitting in Parikh s approach have proved to be too coarse-grained for both Tree and Zigzagn: both ontologies have only one module that contains all axioms although, intuitively, each ontology consists of several independent fragments. Consequently, Parikh splittings may suﬀer from low cohesion. This problem can be overcome by imposing that any (part of an) ontology is coherent if its signature cannot be decomposed into disjoint subsets by discarding some special, common terms. These common terms can be distinctive for the whole domain underlying the knowledge represented in the ontology, but they can be used in diﬀerent contexts, thereby representing substantially diﬀerent logical relations. In Example 3.7, is Made From is such a special term: it is obviously distinctive for the whole domain, but it is used in two diﬀerent contexts one related with plants and the other with landforms. Ponomaryov (2008) has proposed and formalised this idea by introducing signature - decompositions. The approach has been further investigated by Konev et al. (2010). Its main diﬀerence compared to Parikh s O-splittings consists in considering an additional signature that comprises the special, common terms and treating all these terms as if they were logical symbols. That is, the signature of an ontology O (originally: a ﬁnite set of SOL formulas) is decomposed into disjoint sub-signatures Σi, such that there exist ontologies Oi over the signatures Σi whose union is equivalent to O.

Deﬁnition 3.9 (Konev et al., 2010). Let L be a fragment of SOL, O an ontology in L, and e O. A partition Σ1, . . . , Σn of e O \ is called a signature -decomposition of O in L if there are ontologies O1, . . . , On in L such that

f Oi Σi for i = 1, . . . , n and

O1 . . . On O.

O1, . . . , On is called an L-realisation of Σ1, . . . , Σn for O.

In SOL a signature -decomposition always exists and, as in Parikh s approach, is unique.

Theorem 3.10 (Konev et al., 2010). Every ontology O has a unique ﬁnest -decomposition of O in SOL.

As in Parikh s approach, the main reason for Theorem 3.10 being true is the fact that, given two distinct -decompositions, one can always construct a ﬁner partition by intersecting their components pairwise. In SOL, that partition always has a realisation and is thus a -decomposition; this need not be the case in fragments of SOL. Even though there is always a unique ﬁnest -decomposition in SOL, the ontologies realizing it need not be uniquely determined, even modulo logical equivalence, since diﬀerent realisations can spread O s knowledge about in diﬀerent ways across the Ois. To reﬂect the intuition that is a set of special, common terms , Konev et al. introduce realisations O1, . . . , On for O where each Oi includes complete knowledge about the terms from , i.e., Oi Oj and Oi O in L for all i, j n. We call these realisations -encapsulating. Konev et al. prove that being -encapsulating is a suﬃcient condition for the uniqueness of realisations for many fragments L of SOL, including several DLs.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Deﬁnition 3.11 (Konev et al., 2010). A fragment L of SOL has unique decomposition realisations (UDR) if, for all consistent L-ontologies O, all -decompositions Σ1, . . . , Σn of O, and all -encapsulating L-realisations O1, . . . , On and O 1, . . . , O n of Σ1, . . . , Σn for O, we have Oi O i for all i n.

UDR thus guarantees that two realisations of the same -decomposition are identical up to logical equivalence; the underlying decomposition does not need to be a ﬁnest or the ﬁnest. Konev et al. establish the parallel interpolation property (PIP)6 as a suﬃcient condition for UDR which additionally ensures the existence of a unique ﬁnest -decomposition in L.

Theorem 3.12 (Konev et al., 2010). Let L be a fragment of SOL with PIP. Then the following hold.

(1) L-decompositions coincide with SOL-decompositions.

(2) L has UDR.

In particular, every L-ontology O has a unique ﬁnest -decomposition in L.

Remark 3.13 (Konev et al., 2010). A number of DLs have PIP, including EL, ELH, ALC, ALCI, ALCQ, ALCQI. However, PIP fails already for the extension of ALC with role inclusions, and neither is (1) known for this DL. Although PIP can be restored for expressive DLs with role inclusions by including all role and individual names in , this would not allow for the conclusion that they have UDR.

Modules and their properties. Analogously to Parikh s modules, we have to consider the Oi that realise a -decomposition Σ1, . . . , Σn of O modulo logical diﬀerence. The Oi need not be modules: although the Σi are pairwise disjoint, the Oi can logically interact via ; hence they no longer encapsulate the knowledge about their Σi, unlike Parikh modules:

Example 3.14. Let O = {A B, B B , B B }. If we take = {B}, then {A}, {B } is a -decomposition, realised by O1, O2 with O1 = {A B} and O2 = {B B , B B }. This realisation is not -encapsulating because B is entailed by O2, but not by O1. Hence O1 is not a logical module: O |= A , but O1 |= A . If we replace O1 with O 1 = O1 {B }, then O 1, O2 is a -encapsulating realisation.

-encapsulating L-realisations ensure that all information about is accessible in each single Oi. Consequently, if L has UDR, then the Oi of a -encapsulating L-realisation are logical modules of O (Konev et al., 2010). It is reasonable to consider an additional module O with e O = and O d CE O, if it exists, and assume w.l.o.g. that O is contained in all Oi. In Example 3.14, a natural such O would be {B }. In case O d CE , we have O = . We call the Oi and O the -modules, and their collection {O , O1, . . . , On} the - modularisation of O. Like Parikh modules, the Oi are not necessarily subsets of O. It has been observed by Konev et al. that, given UDR, each Oi provides coverage for Σi and is even self-contained. By deﬁnition, O too provides coverage for and is self-contained.

6. For a detailed introduction and discussion of PIP as a property of a logic L, we refer the reader to Konev et al. (2010).

Modular Structures and Atomic Decomposition in Ontologies

In general, the Oi and O are not depleting because they are not necessarily subsets of O; see the remark in Section 3.1. To measure cohesion, we revisit the ontologies from Examples 3.7 and 3.8.

Example 3.15. Consider the Zigzagn family of ontologies from Example 3.8 for n 3. If we choose = {Ai} with 2 i n, then the -decomposition obtained consists of two parts: {A1, . . . , Ai 1, B1, . . . , Bi 1} and {Ai+1, . . . , An+1, Bi, . . . , Bn}. Similarly, if = {Bi} with 1 i n, the corresponding -decomposition is {A1, . . . , Ai, B1, . . . , Bi 1} and {Ai+1, . . . , An+1, Bi+1, . . . , Bn}. If we analyse all these cases, we notice that, for all i {1, . . . , n} the terms Ai and Bi are always either in the same part, or in related parts. The same happens for the terms Ai+1 and Bi. In contrast with this situation, all the other pairs of terms can be separated by a suitable choice of , so it is clear that the logical relation between these pairs is looser than the one between the pairs listed before. Hence, the -decomposition reveals stronger logical relations between the terms of an ontology.

Example 3.16. Consider the ontology Tree from Example 3.7. For = {is Made From} we get the decomposition Σ1 = {Tree, Seed, Fruit, Flower, Branch} and Σ2 = {Mountain, Soil}. It captures exactly the desired logical relation as described in Example 3.7.

Modular structure and its properties. Analogously to Parikh s approach, the modular structure can be based on a -encapsulating L-realisation of the ﬁnest -decomposition O1, . . . , On, plus the additional O , if it exists. In order for modules to be uniquely determined, we assume that L has PIP, although this is not a small restriction, given Remark 3.13. The basic -modules are the Oi and O ; the derived modules are their unions. As in Parikh s approach, -modules and derived modules coincide, and the module generation mechanism is the same. Because all modules contain O , they logically interact with each other unless O d CE . However, since the Oi are -inseparable and the Σi are pairwise disjoint, the only dependencies are between the Oi and the O , if it exists. More precisely, each Oi depends on O , but not vice versa. The dependency graph is thus a tree of depth 1 and width n, or it consists of n isolated nodes. The choice of strongly aﬀects the granularity of the decomposition: In the extreme case = e O, the set e O \ is empty and thus has only the empty partition.7 We exclude this pathological case from the subsequent considerations. On the other extreme, if O d CE (including the case = ), then the unique ﬁnest -decomposition coincides with the unique ﬁnest Parikh splitting, except for the additional O in its realisation. It seems reasonable to expect the following behaviour of the unique ﬁnest -decomposition: (i) it is at least as ﬁne as the unique ﬁnest Parikh splitting and (ii), which implies (i), the number of its parts increases monotonically with . While this expected behaviour can be observed in Example 3.17, it does not occur in general, as Example 3.18 shows.

Example 3.17. The -decomposition from Example 3.16 is ﬁner than the Parikh splitting. If we increase to, e.g., = {is Made From, Tree, Fruit}, then the -decomposition becomes even ﬁner: Σ1 = {Seed}, Σ2 = {Flower, Branch}, and Σ3 = {Mountain, Soil}.

7. Note that partitions are usually deﬁned to consist of non-empty parts.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Example 3.18. Let O consist of two signature-disjoint axioms, such as O = {A1 B1, A2 B2}. Then the unique ﬁnest Parikh splitting is Σ1, Σ2 with Σi = {Ai, Bi}, i = 1, 2, realised by O1, O2 with Oi = {Ai Bi}, i = 1, 2. Also, Σ1, Σ2 is the unique ﬁnest -decomposition for = and for = {A1} (or any other singleton ). If we increase to = {A1, B1}, then the part Σ1 vanishes and Σ2 remains, i.e., we get the singleton -decomposition consisting of Σ2, realised by O2 (and O = O1).

Hence, -decompositions are incomparable with Parikh splittings in general. In particular, because Property (ii) above fails, the selection of a suitable in practice is non-trivial and constitutes the major challenge for -decomposing an ontology. Konev et al. (2010) do not expect signature decompositions to be a push-button technique, but rather envision an iterative and interactive process of understanding and improving the structure of an ontology, where the designer repeatedly chooses sets and analyses the impact on the resulting decomposition . Hence, this method does not produce any stable, intrinsic modular structure at least, we do not yet have conditions to ensure such a property.

Computational properties. Konev et al. (2010) analysed the computability of signature -decompositions for those languages that have PIP. In particular, ﬁnding the ﬁnest - decomposition is polynomial in DL-Lite, and in EL with further constraints (either = or O is role-acyclic, i.e., O has no entailments of the form C r1. rn.C where C is an EL-concept, the ri are role names, and n 1); Exp Time-complete in ALC, ALCI, ALCQ or ALCQI, and in ALCH or ALCHI under the condition that contains all role names from e O. For languages without PIP the existence of a ﬁnest -decomposition, and thus of a modular structure as described above, is not guaranteed.

3.3.3 Decomposition Based on E-Connections

An orthogonal approach to decomposing an ontology into modules aims at identifying distinct subdomains present in an ontology, and making explicit how the ontology describes entities from one subdomain in terms of entities of others. For example, a medical ontology might deal with the non-overlapping subdomains of anatomy, diseases, and drugs, referring to anatomy concepts in order to deﬁne diseases and to concepts from both anatomy and diseases to deﬁne drugs. In order to model non-overlapping subdomains and the logical interactions between them, the notion of an E-connection has been deﬁned (Kutz, Wolter, & Zakharyaschev, 2002; Kutz et al., 2004). E-connections are based on a principled approach to combining several logics. To ensure that the combined formalism is computationally well-behaved, the constituent logics are required to fall under the general notion of an abstract description system (ADS), introduced by Baader, Lutz, Sturm, and Wolter (2002) to study fusions of logics. The semantics of fusions is designed to merge the involved interpretation subdomains, whereas that of E-connection keeps them separate. ADSs include most of the commonly used DLs, but also modal and (propositional) temporal logics. In the special case of DLs, an E-connection is a set of ontologies its parts that are semantically interconnected via link properties (LPs).8 The intuitive idea is that every part

8. Diﬀerently from our presentation of the other formalisms for decomposition, we omit here the formal deﬁnition of E-connections since it is rather lengthy; we refer the interested reader to the literature (Baader et al., 2002; Cuenca Grau et al., 2006).

Modular Structures and Atomic Decomposition in Ontologies

covers a separate domain, and LPs allow to transfer information between these domains in the sense indicated above. More precisely, concepts from one application domain (e.g., in a medical ontology, certain drugs) can be deﬁned in terms of concepts from other domains (e.g., certain diseases and body parts). To capture this intuition, the semantics of E-connections is based on DL interpretations whose domains consist of pairwise disjoint subdomains. Given an E-connection O with the parts O1, . . . , On, each Oi is associated with one of the subdomains; each concept name or individual in O is associated with one Oi and interpreted within the respective subdomain; the same holds for some of the role names in O; each of the remaining role names in O becomes a LP that is associated with a pair (Oi, Oj) and interpreted as a binary relation between the respective subdomains. In the above example, three subdomains are needed, and the extensions of, e.g., the concept name Body Part and the role name has Location are restricted to the anatomy subdomain. In contrast, the LP affects is interpreted as a binary relation that links the disease subdomain with the anatomy one. Cuenca Grau et al. (2006) describe a procedure for decomposing an ontology into an Econnection. This procedure yields a partition of the set of an ontology s axioms, together with connections between the parts, modelled as link properties. Despite being nondeterministic, the procedure yields the unique ﬁnest partition of the input ontology that is an E-connection (where reﬁnes and ﬁnest are deﬁned in the beginning of Section 3.3.1). Not every such partition is equivalent to the original ontology under the E-connection semantics. In order to guarantee this kind of equivalence between the input and output ontology, it is necessary to assume that the input ontology is safe, which means that the satisfaction of its axioms does not depend on the existence of domain elements that do not participate in extensions of concept, role, or individual names. This notion is also known as domain independence in the database context (Abiteboul, Hull, & Vianu, 1995). For example, the axiom α = A B is not safe because, if a model I of α is extended by a domain element that does not occur in the extension of A or B, then α ceases to be satisﬁed.

Example 3.19. Consider the (safe) example ontology Koala2 given in Figure 1, created in the spirit of the toy ontology Koala.9 Figure 2 provides the ﬁnest partition into an equivalent E-connection. The nodes are labelled with the axioms contained in them, together with an informal name summarising their contents. The edges are labelled with the respective LP. The E-connection in Figure 2 comprises of two connected components: an isolated part containing only axiom α14 and the remainder of the ontology, decomposed into 5 parts. The largest part consists of the 6 axioms describing animals and their subconcepts, and the ranges of the has Habitat and has Gender relations. These axioms cannot be further separated because of the fundamental property of E-connections to be closed under subconcepts : e.g., due to the axiom Marsupial Animal, both concept names Marsupial and Animal must be associated with the same part and so must the respective axioms α3 and α4. The remaining parts of this component contain the axioms describing habitats (including forests), climate, vegetation, and genders. The edges and their respective LPs capture the logical interaction between the axioms in the ontology in an intuitive way: animals are described in terms of their habitat and gender; habitats are described in terms of their climate and vegetation; climate and vegetation aﬀect each other. Finally, the isolated part correctly represents the fact that α14 does not logically interact with the remainder of the ontology.

9. http://protege.stanford.edu/plugins/owl/owl-library/koala.owl

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Koala2 = { α1: Koala Marsupial has Habitat.Dry Eucalypt Forest, α2: Quokka Marsupial, α3: Marsupial Animal, α4: Animal has Gender. has Habitat. , α5: has Habitat.Habitat, α6: has Gender.Gender, α7: Dry Eucalypt Forest Forest, α8: Forest Habitat, α9: Habitat has Climate.Climate has Vegetation.Vegetation, α10: Climate controls.Vegetation, α11: Vegetation depends On.Climate, α12: Gender(female), α13: Gender(male), α14: Continent(australia) }

Figure 1: Toy ontology Koala2.

α1 α2 α3 α4 α5 α6 α12 α13

has Habitat

has Climate

has Vegetation

controls depends On

Figure 2: E-connection resulting from partitioning the ontology Koala2.

In general, every E-connection O = (O1, . . . , On) of an ontology O induces a directed graph GO called the E-connection graph whose nodes are the Oi and whose edges are determined by the LPs. An edge from Oi to Oj indicates that Oi imports vocabulary from Oj, i.e., the meaning of the concepts in Oi depends on that in Oj. Based on this imports relation, the Oi can be divided into three types:

light/red: parts with outgoing edges ( importing parts ),

medium/blue: parts with incoming but no outgoing edges ( imported parts ), and

dark/green: isolated parts (they indicate subdomains unrelated to the rest of the ontology and could be maintained in a separate ontology).

Unlike the two approaches described previously, decomposition based on E-connections splits the set of the input ontology s axioms. As a consequence, two equivalent ontologies may have diﬀerent E-connections, as we can see in the next example.

Example 3.20. Consider the ontology O = {A1 B1, A2 B2}: its E-connection has two parts with a single axiom each. Now O is equivalent to O = { ( A1 B1) ( A2 B2)} whose E-connection only has a single part, O itself.

Although we can associate a partition of the signature of an ontology with an E-connection, diﬀerent parts of an E-connection can share terms, i.e., the set of terms associated with a part is only a subset of its signature; we will discuss this in the following. Furthermore, the process of partitioning is completely automatic.

Modular Structures and Atomic Decomposition in Ontologies

Modules and their properties. A single part of an E-connection is not necessarily logically closed: its outgoing LPs point to parts on which it logically depends. In the initial example, the drugs part depends on the other two, and the diseases part depends on the anatomy part. The modules of an E-connection are thus obtained by following the logical dependencies, modelled by the LPs. More precisely, in an E-connection O = (O1, . . . , On) of an ontology O, each sub-collection (Oi1, . . . , Oim) of its parts determines an E-module Mi1,...,in, which is the union of all the Oij and all Oℓthat are reachable from some Oij in GO (if nominals occur, then predecessors in GO need to be added). Koala2 (Figure 2) has 13 E-modules: (1) Gender, (2) Climate Vegetation, (3) Habitat Climate Vegetation, (4) the union of 1 and 2 with Animal, (5) australia, and (6 13) any union of two or more of 1 5. Cuenca Grau et al. (2006) show that all E-modules provide coverage and are self-contained. The property of being depleting is not discussed; however, every E-module Mi determined by a single part Oi is shown to satisfy additional, similar encapsulation properties:

(i) For every concept name A associated with Oi, the module Mi entails the same subsumptions A B and B A as O, where B is an arbitrary concept name from O.

(ii) O does not entail any subsumptions between concept names occurring in Mi and concept names not occurring in Mi.

Unlike in the previous two approaches, all Oi, and thus all modules, are subsets of O. Even though every concept and role name is associated with exactly one Oi (or one pair), the signatures of the Oi are typically not disjoint. The cohesion of an E-module can vary greatly from ontology to ontology. Due to conditions (i) and (ii), the size of the partition and thus the number of basic modules is bounded by the number of top-level concepts in the original ontology.10 Consequently, E-modules of some ontologies combine axioms that are related not logically but because they involve sub-concepts of the same (generic) top-level concept.

Modular structure and its properties. The basic modules are those E-modules Mi that are determined by a single part Oi; the derived modules are their unions. As in the previous two approaches, E-modules Mi1,...,in and derived modules coincide, and the generation mechanism is the same. The edges of the E-connection graph GO induce a dependency relation between the parts Oi of the partition: if there is a path from Oi to Oj in GO, then the following property holds.

For every basic module Mk, if Oi Mk, then Oj Mk.

In other words, the axioms in Oi logically depend on the axioms in Oj because the former need the latter to form modules that encapsulate knowledge but not necessarily vice versa. Dependencies between the parts imply inclusions between basic modules: if Oi, Oj are part of a cycle, then Mi = Mj; if there is a path from Oi to Oj but not vice versa, then Mj Mi; otherwise Mi, Mj are orthogonal (but not necessarily disjoint). In the case of Koala2 (Figure 2) the modules determined by Climate and Vegetation coincide, and are strictly contained in the module for Habitat.

10. The same holds with respect to the bottom-level concepts, but their number is usually much larger.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

E-connections capture a further type of logical dependency between their modules: the overlapping of two distinct Mi, Mj. In this case, the two modules share one or more parts Ok. This is represented in GO by the Ok being reachable from both Oi and Oj. The granularity of the modular structure induced by an E-connection can vary greatly from ontology to ontology, see the observations related to cohesion above. As a consequence, some ontologies do not decompose well into an E-connection due to certain modelling practices:

Example 3.21. Robert Stevens ontology Periodic,11 which describes the elements of the periodic table and their properties, has a single top-level concept Domain Entity. Thus the ﬁnest E-connection consists of a single node containing all axioms, although the domain modelled by Periodic is naturally partitioned and the ontology expresses this separation.

Example 3.22. The ﬁnest E-connection for each of the ontologies Tree and Zigzagn from Examples 3.7 and 3.8 consists of a single node, too (for all n). The reason for Tree is that all axioms share the role is Made From, and among the ﬁrst ﬁve axioms, each two consecutive axioms share a concept, which prevents the role is Made From from being an LP. The reason for Zigzagn is that for each i {1, . . . , n}, both Ai and Bi belong to the same part since Zigzagn |= Ai Bi. The same holds for Ai+1 and Bi.

The other extreme is possible, too: it is easy to compose ontologies where every node in the E-connection graph consists of exactly one axiom. Furthermore, E-connections are incomparable in terms of granularity with Parikh splittings:

Example 3.23. Revisit the ontologies O and O from Example 3.20: both the ﬁnest Parikh splitting and the ﬁnest E-connection of O have two parts, one for each axiom. The equivalent ontology O cannot be split by E-connections, but the ﬁnest Parikh splitting remains the same. The reason is that every part of an E-connection must be a subset of the original ontology, whereas a realisation of a Parikh splitting does not need to consist of subsets.

However, if one considers a restricted variant of Parikh splittings that admits only realisations that partition the original ontology O, then the ﬁnest Parikh splitting of O always yields an E-connection: since the n parts of its realisation are pairwise signaturedisjoint and subsets of O, they constitute an E-connection with n isolated parts. Consequently, the ﬁnest E-connection is at least as ﬁne as the ﬁnest Parikh splitting (in this variant).

Computational properties. The ﬁnest E-connection for a given ontology O in DLs up to SHOIQ can be computed using Cuenca Grau et al. s (2006) algorithm in time polynomial in the size of O. This algorithm only guarantees structural compatibility of the resulting Econnection with O and not logical equivalence under the E-connection semantics (see above). The safety check can be performed in polynomial time as a preprocessing step. Altogether every safe SHOIQ ontology can be partitioned into a ﬁnest logically equivalent E-connection in polynomial time. Jongebloed and Schneider (2018) give a linear-time algorithm for the same task in DLs up to SROIQ. They have also extended the safety check to SROIQ minus the universal role, and argued why the latter is a strict boundary to the safety check. In the meantime, a prototype has been implemented and tested in Jongebloed s Master s thesis (2020). The performance turns out to be outstanding, but most of the observed E-connections are discouragingly coarse-grained. Additional heuristics are needed to ﬁnd out whether this approach is useful at all.

11. http://www.cs.man.ac.uk/~stevensr/ontology/periodic.zip

Modular Structures and Atomic Decomposition in Ontologies

3.3.4 Early Attempts to Identify a Modular Structure for Σ-Modules

The extraction of a module M for a given signature Σ from an ontology O is a well-studied task, see Section 2 (Konev et al., 2008, 2009; Cuenca Grau et al., 2009; Sattler et al., 2009). RΣ-modules, for a ﬁxed inseparability relation R, are designed to preserve the entailments (if R is deﬁned deductively) or the models (if R is deﬁned model-theoretically) over a given signature Σ and, because of self-containment, over the signature f M of M itself. However, M does not guarantee to preserve any entailments between the terms in Σ f M and the remaining terms in O; it therefore does not capture any information on the logical relationship between the terms in M and those outside. This observation makes the determination of the signature of interest Σ more diﬃcult than one might expect, and as long as a user is unsure about the signature to specify, the ability to extract a single module is of little help to them. As a simple (abstract) example, suppose an ontology user or engineer wants to extract from an ontology O a module M that captures how a concept name A is described in O, but they do not know which other terms in O are related to A. The most obvious choice for a signature Σ that determines M would be Σ = {A}. However, for most sound ontologies, M = will be a module for Σ because the only interesting non-tautologous entailments that can be formulated using only A are A and A and they are both unlikely to follow from O (they mean that A is unsatisﬁable w.r.t. O or a top-level concept). Indeed, if we consider the ontology Tree from Example 3.7 and are interested in the concept name Tree, then the empty ontology is a module of Tree for Σ. One might argue that existing module-extraction approaches for expressive ontology languages, including locality-based modules, do not guarantee to generate a minimal module. However, it would certainly not help to try and rely on modules containing a bit more than they should. In the case of Tree, the -module for Σ is indeed empty. If we want to support our ontology user/editor in ﬁnding a module (for A) that is appropriate for their needs, we could try providing them with a list of all possible modules of O (containing) to choose from. However, this naïve approach is infeasible as O may have exponentially many modules:

Example 3.24. Let us consider the ontology All = {A1 B1, A2 B2, . . . , An Bn}. Then every subset of All is a -module for some signature Σ f All.

One might hope that the exponential behaviour observed for this artiﬁcial ontology does not tend to occur for real-life ontologies. This hope was had by Parsia and Schneider (2010), who attempted to compute a modular structure for an ontology based on the set of all its RΣ-modules, based on a ﬁxed inseparability relation R and module extraction approach x (in particular, locality-based modules). Before coming back to these early attempts, we will ﬁrst discuss the resulting modular structures and the requirements to the module notion x.

Modules and their properties. We consider an inseparability relation R and a module notion x which, for every O and Σ, yields an RΣ-module x-mod(Σ, O) for Σ in O that is

(M0) self-contained,

(M1) uniquely determined, and

(M2) a subset of O.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Property (M0) is advisable given the discussion about self-containment and interfaces in Section 3.1, and (M1) and (M2) reﬂect the fact that module extraction approaches are to be used, which typically yield uniquely determined subsets.12 It should be noted that coverage is provided by RΣ-modules by deﬁnition; we do not require that they are depleting. The module notion x does not need to have been designed with a notion of a modular structure or basic and derived modules in mind. As a prominent example for x, we will often refer to locality-based modules (Section 2) throughout this section, in particular -modules: they comprise perhaps the most widely known language-independent and computationally well-behaved module notion, and they are readily usable via the OWL API. As explained in the last paragraph of Section 2, all module notions satisfying (M2) are necessarily syntax dependent, i.e., two equivalent ontologies can lead to two diﬀerent, non-equivalent modules for the same seed signature and thus to diﬀerent modular structures.

Example 3.25. Consider the ontology O = {A1 A2, A2 A3, A3 A4} and let Σ1 = {A1, A2}, Σ2 = {A3, A4}, and Mi = x-mod(Σi, O) for i = 1, 2. If x is , then M1 = -mod(Σ1, O) = {A1 A2} and M2 = -mod(Σ2, O) = {A3 A4}. However, M = M1 M2 is not a module: its signature contains both A2 and A3, but M does not contain the second axiom, thus violating self-containment.

Hence, if we were to deﬁne the derived modules to be exactly those that are the union of two basic modules, then (a) the distinction between basic and derived modules would be arbitrary and unintuitive (there could be very large basic modules containing derived modules), and (b) union as a derivation mechanism would not be meaningful for inseparability relations such as m CE and d CE because it sometimes produces a module and sometimes it does not. The last problem could be repaired by considering the following derivation mechanism: given modules M1, . . . , Mn of an ontology O, the module derived from M1, . . . , Mn is x-mod(Σ, O) where Σ is the union of the signatures of the Mi. One could then deﬁne derived modules to be exactly those that can be obtained this way; all other modules would be basic. However, this choice is unintuitive, too: (a) determining whether a module M is basic or derived would be highly complex because one would have to check M against every union over a subset {M1, . . . , Mn} of the set of all modules; (b) an ontology O could have a chain M1 Mn of basic modules, e.g., when the signatures of O s axioms are monotonously increasing w.r.t. the subset relation. Cohesion may vary greatly, depending on the module notion x. In the worst case, x can be such that x-mod(Σ, O) = O for every signature Σ. Then obviously the only module O is of the lowest possible cohesion; see, e.g., the discussion in the previous subsection where Tree did not decompose. In the best case, take x to be the minimal RΣ-module for every Σ.13 Then the basic modules are of very high cohesion: two axioms occurring in a -minimal module M are strongly related in a logical sense because separating them is likely to compromise entailments over the signature covered by M.

Modular structure and its properties. In order to obtain a modular structure from a family of x-modules, we denote with Fx(O) the set of all x-modules in O. When no ambiguity may arise, we drop x and write F(O). We set G = Fx(O) and to be the set inclusion

12. The so-called projection and subsumption modules (Chen et al., 2018, 2019b) are not unique, thus do not satisfy (M1) and are therefore not further discussed here. 13. In this case, we need to use a suitable notion of minimality to ensure uniqueness (M1).

Modular Structures and Atomic Decomposition in Ontologies

relation . Under certain assumptions to the module notion x, this dependency relation can be represented by the complete join-semilattice whose 1-element is O, whose 0-element is the module for Σ = ,14 and where the join of any two modules M1 and M2 is the smallest module containing both M1 and M2. For the latter to be well-deﬁned, we need to require two additional properties.

(M3) The function x-mod( , ) is monotonic in the ﬁrst argument, i.e., if Σ Σ , then x-mod(Σ, O) x-mod(Σ , O).

(M4) For all x-modules M of O, it holds that M = x-mod( f M, O).

Property (M4) is the operational variant of the assumption that RΣ-modules are selfcontained, as discussed at the beginning of Section 3.2. Although x-modules do not need to be minimal, (M4) ensures that M covers O for its own signature but not more. Interestingly, (M4) does not follow from self-containment and depletingness of x-modules (see Def. 2.4) since the module extraction function x-mod( , ) could add diﬀerent extraneous axioms depending on the ﬁrst parameter. All known variants of locality-based modules (whether syntactic or semantic, top or bottom, nested or unnested), however, satisfy (M0) (M4) (Konev et al., 2009; Sattler et al., 2009). If the module notion x satisﬁes properties (M1) (M4), then for all modules M1, M2 of O there is a unique -minimal x-module of O that contains both M1, M2, namely x-mod(g M1 g M2, O). Unlike in the previous approaches, G does not partition the input ontology; the modules in G typically overlap. The granularity can vary greatly depending on the module notion x and the ontology O, analogously to the variability of cohesion: if x generates only large modules from O, then the resulting modular structure (Fx(O), ) will be coarse-grained; if x generates smaller modules, then the granularity of (Fx(O), ) will be ﬁner.

Computational properties. As already seen in Example 3.24, every subset of an ontology O may be an x-module for some signature. Thus, even when x-modules can be computed eﬃciently (as is the case for MEX or locality-based modules), the size of the modular structure is exponential in the worst case. Our previous study (Parsia & Schneider, 2010) shows that the situation is not signiﬁcantly diﬀerent for existing ontologies: the experiment on a number of well-designed and suﬃciently diverse ontologies shows that (a) the number of modules is so large that a complete extraction is possible only for ontologies with up to 50 axioms; and (b) for a ﬁxed ontology, the number of modules extracted from a sub-ontology grows exponentially with the size of the sub-ontology. The latter suggests that the number of modules of an ontology indeed grows exponentially with the size of the ontology. Even attempts to reduce the prohibitively large set of R-modules to a reasonable subset did not help: we observed (Parsia & Schneider, 2010) that a large proportion of the modules is of distinctively low cohesion, called fake , but the number of the remaining genuine modules still exhibits an exponential growth, too. A fake module falls apart into smaller modules which are logically independent because their signatures are (almost) disjoint a predecessor variant of the notion of genuine and fake modules introduced in Section 4.

14. Note that the module mod( , O) is not necessarily empty. For example, the axiom A B A B is neither - nor -local w.r.t. any signature.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

4. Atomic Decomposition

In the previous section, we have seen a variety of existing approaches to decompose an ontology resulting in diﬀerent kinds of modular structures with diﬀerent properties all of which provide strong logical guarantees. None of these approaches, however, results in a modular structure that would be suitable for modular ontology engineering, i.e., one that has a suitable number of basic modules with strong cohesion, a dependency relation which allows us to work with modules of a varying granularity, a suitable module generation mechanism, and whose computation is of acceptable complexity. In this section, we assume we have ﬁxed a notion of modules where each module is unique for a given seed signature, a subset of the ontology, and depleting. We introduce a new modular structure based on the notion of a genuine module, i.e., a module that cannot be decomposed into smaller modules. In this sense, genuine modules are the basic modules of our structure and of all derived modules. The new modular structure will be based on two fundamental notions: (a) an atom of the input ontology O is a maximal subset of axioms that are never separated by any module of O. Consequently, O s atoms partition O into highly cohesive subsets, and the number of atoms is bounded by the number of O s axioms. (b) The dependency relation between atoms of O captures a further kind of cohesion and allows for a natural deﬁnition of basic modules of O. We will see that both the set of atoms and the dependency relation can be computed in quadratic time with a linear number of calls to a subroutine extracting x-modules. Before we deﬁne these new terms, we clarify the requirements to the underlying module notion x.

4.1 Requirements

From now on, we ﬁx a monotonic inseparability relation R and a module notion x which, for any given ontology O and signature Σ, yields an RΣ-module x-mod(Σ, O). The function x-mod( , ) must satisfy the following properties; the ﬁrst ﬁve have already been ﬁxed in Section 3.3.4, but we repeat them for readability.

(M0) x-mod(Σ, O) is a self-contained RΣ-module of O.

(M1) x-mod(Σ, O) is uniquely determined.

(M2) x-mod(Σ, O) is a subset of O.

(M3) The function x-mod( , ) is monotonic in the ﬁrst argument.

(M4) For all x-modules M of O, it holds that M = x-mod( f M, O).

(M5) For all α O: if α x-mod(Σ, O) for some Σ e O, then α x-mod(eα, O).

Properties (M1) (M5) are necessary for the soundness of the technical development in this section, and they ensure that the AD of a given ontology can be computed eﬃciently, see Section 4.3.3. In contrast, Property (M0) is not necessary from a strict technical point of view, but we consider it an essential requirement to a meaningful module notion; see the discussion on self-containment and interfaces in Section 3.1. In this connection, it should be noted that x-modules are not required to be depleting.

Modular Structures and Atomic Decomposition in Ontologies

Property (M5) is a technical subtlety to ensure that any axiom α that occurs in some module of O also occurs in the module for its own signature; see the proof of Lemma 4.11. For example, if α = A A B and α x-mod({A, B, C}, O), then α x-mod({A, B}, O). Although (M5) speaks about all possible axioms α, it is not a strong restriction for module notions x that are depleting in this case, (M5) is relevant only for axioms α that are tautologies modulo R and their own signature, i.e., {α} R eα : all other α occur in x-mod(eα, O) anyway, due to depletingness and monotonicity of R.15

Properties (M0) (M5) are satisﬁed by locality-based and MEX modules; the suitability of the remaining module notions mentioned in Section 2.3 is discussed in Section 4.5. It is not hard to see, however, that some module notions based on implication inseparability (Konev et al., 2009; Armas Romero et al., 2016) do not satisfy (M5). All of the following deﬁnitions and theoretical results apply to any module notion x with these properties. Only soft parameters such as cohesion and granularity, as well as computational properties depend on the choice of x. We will get back to this last observation in Section 4.4; in the meantime we will often omit x when no confusion can arise. We continue to use the notion Fx(O) = {x-mod(Σ, O) | Σ e O} from Section 3.3.4 and write F(O) when x is clear from the context or we do not have a speciﬁc x in mind.

4.2 Atoms, Dependency, and the Atomic Decomposition

Atoms are deﬁned via the equivalence relation O, which captures that axioms always co-occur in modules.

Deﬁnition 4.1. Let O be an ontology and α, β O. Then α O β if, for all M F(O), we have α M if and only if β M.

It is immediate that O is indeed an equivalence relation. Atoms are maximal subsets of axioms that are not separated by any module.

Deﬁnition 4.2. The atoms of an ontology O are the equivalence classes of O. The set of atoms of O is denoted by A(O).

We denote atoms by a, b, . . . The following observation is immediate.

Observation 4.3. For every ontology O, the following hold.

1. A(O) is a partition of O.

2. #A(O) #O (i.e., the number of atoms is bounded by the number of axioms in O).

3. Every module M F(O) is a disjoint union of atoms.

While every module of O is partitioned into one or several atoms, it is not necessarily the case that every axiom occurs in some module. By (M5), these are exactly those α with α / x-mod(eα, O), which is the case, e.g., for some tautologies. We can think of such axioms α as obvious tautologies.16 If O contains such axioms, then by deﬁnition they constitute

15. In fact, a weaker variant of depletingness already suﬃces, namely O \ M R Σ . This requirement follows from depletingness as in Deﬁnition 2.4 and monotonicity of R. 16. Strictly speaking, the term tautologies is only justiﬁed if x-modules are depleting; see the remarks on (M5) in Section 4.1.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

a single atom, which we call t; otherwise t is empty and thus not an atom. To make the following considerations more readable, and without loss of generality, we assume that t = ; we can always employ a preprocessing step that identiﬁes t and removes it from O, resulting in an ontology O with O R e O O. Next, we deﬁne a binary relation between atoms that captures the dependencies between atoms in terms of co-occurrence in modules: if a b, then every module that contains a must contain b too.

Deﬁnition 4.4. Let a, b be atoms of an ontology O. We say that a depends on b (written a b or b a) if, for every M F(O), a M implies b M. The relation is called the dependency relation of O.

The relation is obviously a partial order: reﬂexivity and transitivity are immediate, and antisymmetry follows from the observation that, if both a b and b a hold, then α O β for all axioms α a and β b; consequently a = b. As usual, we use for the strict partial order underlying , i.e., a b if a b and a = b. Since (A(O), ) is a strict poset (partially ordered set), we can represent it by means of a Hasse diagram. Furthermore, we can make use of the standard notions of a principal ideal17

and an antichain:

Deﬁnition 4.5. Let O be an ontology.

1. The poset (A(O), ) is called the atomic decomposition (AD) of O.

2. The principal ideal of an atom a A(O) is the set a := S{b | a b}.

3. An antichain of atoms is a set B A(O) such that a b for any two distinct a, b B.

In case the module notion matters, we will explicitly mention x and speak of the x-atomic decomposition of O, for short x-AD, denoted by (Ax(O), x) .

Example 4.6. Let us consider the Dog ontology deﬁned as follows.

Dog = { α1 : Poodle Dog has Coat.Curly, α2 : Dog Mammal has Part.Tail, α3 : Mammal Animal has Part.Hair }

The three popular notions of locality , , and give rise to the following sets of x-modules.

F (Dog) = { , {α3}, {α2, α3}, Dog}

F (Dog) = { , {α1}, {α1, α2}, Dog}

F (Dog) = { , {α1}, {α2}, {α3}, {α1, α2}, {α2, α3}, Dog}

In each of the three corresponding x-ADs, the atoms are {α1}, {α2}, and {α3}. The dependency relations diﬀer and are given by the Hasse diagrams in Figure 3. In the -AD, the principal ideal of {α1} is {α1} = {α1, α2, α3}; in the other two ADs, we have {α1} = {α1}. In the -AD, the three atoms form an antichain of size 3; the other ADs have singleton antichains only.

Modular Structures and Atomic Decomposition in Ontologies

Figure 3: -, -, and -AD of the Dog ontology. Arrows represent the relation.

We can see that both in the -AD and in the -AD all atoms are comparable. This is in contrast with the -AD, which is totally disconnected since each atom is incomparable with any other atom. Please note that not every dependency-closed set of atoms forms a module: for example, {α1, α3} is not a -module (the smallest module containing both α1 and α3 is the whole ontology). We see that the -AD shows the dependence of axioms related to more speciﬁc concepts (e.g., Poodle) on axioms related to more general concepts (e.g., Mammal). Dually, the -AD shows the dependence of axioms related to more general concepts on axioms related to more speciﬁc concepts. The -AD, instead, shows none of these dependencies. To sum up, the - and the -AD reveal a subsumption-preserving kind of dependence, whilst the -AD shows a ﬁner notion of independence than those revealed by the other kinds of ADs. We will further investigate this phenomenon in Subsection 4.3.2. In general, the - and -ADs of an ontology and its E-connection are pairwise incomparable in terms of granularity: typically, some -AD atoms are unions of -AD atoms, but there can be -AD atoms that overlap with several -AD atoms; see the following example.

Example 4.7. The -AD of the ontology Koala2 (from Figure 1) consists of 11 atoms in 1 connected component and is displayed in Figure 4a (solid lines only). The nodes are labelled with their axioms αi, together with an informal description of the contents in this case the terms described by the axioms. Arrows represent the depends on relation . The -AD yields a very ﬁne-grained decomposition of Koala2 since most atoms consist of one axiom only. For example, it is intuitive that the atoms describing Forest and Habitat are separated: the topic of forests depends on the topic of habitats (because of α8) but not vice versa. To additionally capture the ontology s knowledge about animals, its knowledge about the has Habitat relation (α5) has to be included. In the case of Koala2, the -AD happens to coincide with the -AD, and the -AD consists of only 5 atoms in 2 connected components. It is superimposed on the -AD in Figure 4 a (dashed lines). Except for the splitting of the bottom-most atom, the -AD is a coarsening of the -AD, and all dependencies are reversed. This eﬀect is caused by the property of -modules being closed under subconcepts , while -modules are closed under superconcepts (Cuenca Grau et al., 2008). Figure 4b shows the E-connection of Koala2 (from Figure 2) superimposed on the -AD. It divides the two bottom-most atoms and is otherwise a coarsening of the -AD that is orthogonal to the -AD. The reasons for the coarseness of the E-connection have been discussed in Example 3.19.

17. Throughout this paper, we use the term (principal) ideal for the downwards closed subset of a partially ordered set (generated by a single element); alternative terms are lower sets, down set, etc.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

α12 α13 α14

Koala Quokka

Dry Euc Forest

has Habitat

Vegetat. female, male,

α12 α13 α14

Koala Quokka

Dry Euc Forest

has Habitat

Veg. female, male,

Figure 4: -AD of the ontology Koala2 (solid lines) with a) the -AD superimposed (dashed lines) and b) the ﬁnest E-connection superimposed. Arrows in ADs represent the relation.

Unlike the -AD and the E-connection, the -AD does not separate axiom α14 from α12 and α13. This is an unintended consequence of the properties of -modules: the concept assertions α12 α14 are part of every -module because concept assertions are never -local, regardless of the signature Σ. Had the continent Australia been modelled as a concept, α14 would have formed a separate isolated atom because no other axiom refers to the terms Continent and australia. Modelling the genders female and male as concepts would have no such eﬀect because axioms α12 and α13 share the concept Gender with each other and the remaining ontology.

Altogether, Example 4.7 shows that -AD, -AD and decompositions based on Econnections are pairwise incomparable. We will examine the relationship between the three main notions of ADs based on syntactic locality more systematically in Section 4.5. The following observation is an immediate consequence of Deﬁnition 4.4: modules are downwards closed under the dependency relation .

Lemma 4.8. If an atom a M and a b, then b M.

4.3 Properties of the Atomic Decomposition

We will discuss relevant properties of the atomic decomposition and its relation to modules, and start with a formal deﬁnition of genuine modules. We remind the reader that we have ﬁxed a module notion x with the properties stated in Section 4.1. For the sake of convenience, we will omit x when referring to the set F(O) of all modules of an ontology O, its atom set A(O), or the module mod(Σ, O) for a signature Σ. We continue to assume that t = (i.e., every axiom occurs in some module).

Modular Structures and Atomic Decomposition in Ontologies

Deﬁnition 4.9. Given an ontology O, we say that a module M F(O) is fake if there are n 2 modules M1, . . . , Mn F(O) such that

M = M1 . . . Mn and

Mi Mj for each i = j.

A module is called genuine if it is not fake. The set of all genuine modules is written G(O).

Deﬁnition 4.9 captures the requirement formulated in Section 4.1: a module is genuine if it is not just the union of two or more other modules that are incomparable w.r.t. set inclusion. The distinction between genuine and fake modules is legitimated by the observation that fake modules are less cohesive and thus less representative than genuine modules.

Example 4.10. For an illustration, consider the following simple Person ontology.

{ α1 : Vegetarian Person, α2 : Student Person, α3 : Person Animal }

Every subset of Person is a module for its own signature. In particular, the singleton modules are genuine and separate the three axioms from each other, capturing the intuition that the three axioms touch on separate topics: vegetarians, students, and animals. Consequently, the concepts Vegetarian, Student, and Animal can be interpreted independently; if the ontology were to be extended, additional knowledge for each of the three topics could be added to the respective module. All three modules depend on the concept Person, which mirrors the customary situation of modules with common dependencies in software engineering. The remaining, larger modules of Person are fake and have a diﬀerent status they decompose into the smaller modules and are thus less cohesive and less representative than those.

Next we develop a 1-1 correspondence between genuine modules and atoms.

4.3.1 Atoms vs. Genuine Modules

We start our investigation by considering modules for seed signatures of individual axioms in an ontology: clearly, an ontology gives rise to only a linear number of such seed signatures. In the following observations and results, we consider an arbitrary ontology O. For any axiom α O, let Mα := mod(eα, O). We call Mα an axiom module. We will ﬁrst show that axiom modules play a major role among all modules, which we will then exploit in order to compute all genuine modules.

Lemma 4.11. For every atom a A(O) and every axiom α a, we have that Mα is the smallest module of O that contains a.

Proof. Let a A(O) and α a. We ﬁrst show that a Mα. Since we have adopted the assumption that t = , there is some module M = mod(Σ, O) that contains α. Property (M5) implies α mod(eα, O). To show that Mα is minimal with a Mα, consider any module M = mod(Σ, O) of O with a M. Then we have

Mα = mod(eα, O) mod( f M eα, O) = mod( f M, O) = M,

where the inclusion is due to monotonicity (M3), the subsequent equality follows from eα f M (since α a M), and the last equality is due to (M4).

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Analogously to axiom modules, we can deﬁne the notion of an atom module: given a A(O), let Ma := mod(ea, O). Interestingly, axiom and atom modules coincide, which easily follows from Lemmas 4.8 and 4.11, the deﬁnition of atoms and Mα, and (M3) and (M4):

Corollary 4.12. For all atoms a, b A(O), the following hold.

1. Ma = Mα for every axiom α a.

2. a depends on all the atoms contained in Ma \ a.

3. a b if and only if Ma Mb.

4. For every axiom β O, we have that β a if and only if Mβ = Ma .

5. For all axioms α, β O, we have that Mα = Mβ if and only if there is an atom b such that {α, β} b.

6. We have that a = {α | Mα = Ma}.

Clearly, the set of all modules F(O) of an ontology O determines the AD (A(O), ) of O. We now provide an argument that, vice versa, the AD is a representation of the (genuine) modules of O. We start by considering the principal ideal a of an atom a A(O) (Def. 4.5).

Theorem 4.13. For each atom a A(O), a = Ma .

Proof. For the direction, observe that a Mα = Ma for some (any) axiom α a, due to Lemma 4.11 and Corollary 4.12, Point 1. Thus, by the deﬁnition of the dependency relation, we have a Ma. The direction follows from Corollary 4.12, Point 2.

As an immediate consequence of Corollary 4.12 and Theorem 4.13, there is a 1-1 correspondence between axiom modules and atoms:

Corollary 4.14. For every module M the following are equivalent.

1. M is an axiom module.

2. M is an atom module.

3. There is an atom a M such that M = a.

Given the AD of O, we can thus easily identify each axiom module Mα by ﬁrst identifying its atom, i.e., by ﬁnding a with α a, and then taking a. Next, we show that each module can be assembled from atoms; we will come back to this in Section 4.4.

Lemma 4.15. Every module M is the union of principal ideals of atoms from an antichain in A(O), i.e., there is an antichain {a1, . . . , an} A(O) such that

Proof. By Observation 4.3, every module M is a disjoint ﬁnite union of atoms {a | a M}. Let a1, . . . , ak be all maximal elements among those atoms. Then, clearly, {a1, . . . , ak} is an antichain, and M = Sk i=1 ai follows with Lemma 4.8.

Modular Structures and Atomic Decomposition in Ontologies

Lemma 4.15 says that each module M has a unique decomposition into incomparable principal ideals. In this sense, we can say that the set of axiom modules forms a base for the set F(O) for all modules of O. In Deﬁnition 4.9 we have already introduced the set G(O) of genuine modules as a base for all modules of O. Next, we see that these two notions coincide, i.e., there is a 1-1 correspondence between genuine modules and axiom modules.

Theorem 4.16. A module is an axiom module if and only if it is a genuine module.

Proof. Due to Corollary 4.14, it suﬃces to show that a module is a principal ideal if and only if it is a genuine module. For the only if direction, assume to the contrary that M is principal ideal a for some atom a and that M is fake. Then by Deﬁnition 4.9 there are n 2 pairwise -incomparable modules M1, . . . , Mn with M = M1 Mn and w.l.o.g. a M1. Since M = a, all atoms in M2 depend on a. Since by Observation 4.3, M2 is the union of certain atoms and M1 is closed under the dependency relation (Lemma 4.8), we obtain M2 M1, which contradicts the incomparability of M1 and M2. For the if direction, we show the contrapositive. Assume that M is not a principal ideal. Due to Lemma 4.15, M = Sn i=1 ai for an antichain {a1, . . . an} A(O). Since M is not a principal ideal, we must have n 2; since the ai form an antichain, the modules ai are pairwise -incomparable. Hence M is fake.

The following is a summary of all our ﬁndings and an extension of Corollary 4.14.

Corollary 4.17. There is a 1-1 correspondence between atoms and genuine modules. In particular, for every module M the following are equivalent.

1. M is a genuine module.

2. M is an axiom module.

3. M is an atom module.

4. There is an atom a M such that M = a.

The relations between genuine modules, atoms, and axiom modules captured in Theorem 4.16 and Corollary 4.17 will be exploited in Section 4.3.3 for the eﬃcient computation of all genuine modules of an ontology.

We saw in Lemma 4.15 that each module is the union of the principal ideals of a suitable set of atoms. However, not all unions of principal ideals are modules:

Example 4.18. Consider the following ontology Girl and its -AD.

Girl = { α1 : Female Person,

α2 : Child Person,

α3 : Female Child Girl }

The union of the principal ideals {α1} and {α2} is not a module since it includes both terms Female, Child and thus needs to include the axiom α3 too (since α3 is not -local w.r.t. any signature containing Female, Child).

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

4.3.2 Chains of Conservative Extensions

The dependency relation between (the atoms of) genuine modules has some interesting consequences for the models of these modules, which we will discuss next. We continue to assume that we have ﬁxed a monotonic inseparability relation R (Def. 2.3) and a corresponding module notion x with the properties (M0) (M5) listed in Section 4.1. We will omit both R and x unless we need to distinguish certain choices for them explicitly. Imagine a scenario where an ontology engineer Alice has an ontology O1 and an ontology O2 to be added to O1: for example, Alice has built O1 and now wants to extend it with O2 she found in a repository and which covers some important aspects of her domain. Another example is where Alice has been using O1 for a while and now Bob suggests to extend it with O2. A third example is where O1 is empty and Alice considers reusing O2 for her application. In all three scenarios, it is reasonable to require that O1 O2 conservatively extends O1, i.e., that O1 R f O1 O1 O2 for a suitable inseparability relation R. For example, if R = d CE, then the conservativity requirement means that all entailments of the extended ontology formulated in f O1 already follow from O1; hence Alice can safely restrict her attention to O1 when she is interested only in the topic of O1. Similarly, if R = m CE, then {I|f O1 | I |= O1} = {J |f O1 | J |= O1 O2}; thus Alice can assume that her extension of O1 preserves the models of O1 modulo its signature. Now assume that O2 is large and Alice wants to divide the extension into digestible parts. If O2 contains, say, 100 axioms and Alice looks at the (unordered) set O1 O2, then she will have a hard time to comprehend the changes and their logical eﬀects. Instead, she may want to spread the extension over several steps: O1 Ok 2 where Ok 2 contains the ﬁrst k axioms of O2, then O1 O2k 2 with the next k axioms, etc., up to O1 O2. It is reasonable to expect that many small steps are preferable over few large steps; e.g., 50 steps of 2 added axioms each are easier to comprehend than 2 steps of 50 added axioms each, provided that these 50 steps of 2 axioms come in a helpful order. We have already seen that an order where the newly added axioms conservatively extend those already considered is such a helpful order. The following deﬁnition captures these insights.

Deﬁnition 4.19. Let R be an inseparability relation. An R-chain of CEs is a ﬁnite sequence of ontologies (O1, . . . , Om) such that Oi Oi+1 and Oi R f Oi Oi+1 for every i < m.

The AD (of the ontology O resulting from all extensions) provides us with a straightforward mechanism for identifying chains of CEs:

Proposition 4.20. Let O be an ontology and a1 am a chain of atoms. Then ( am, . . . , a1) is a chain of CEs.

Proof. Let i < m. Then ai+1 ai is obvious from the deﬁnition of PIs and . Furthermore, we have ai+1 = Mai+1 due to Theorem 4.13; hence ai+1 ai+1 O. Since ai+1 ai O and R is monotonic, we also have ai+1 ai+1 ai.

We can even use the AD to identify maximal chains of CEs according to Proposition 4.20 in the following sense. Consider two atoms a1 a2 A(O) such that there is no atom a3 A(O) with a1 a3 a2, and let Mi = ai be the corresponding genuine modules in G(O). Since a1 a2, Proposition 4.20 ensures that M1 can be extended with the

Modular Structures and Atomic Decomposition in Ontologies

axioms in M2 \ M1 safely. Moreover, since there is no genuine module M3 G(O) with M1 M3 M2, this extension is minimal (relative to the module notion x), i.e., there is no reasonable alternative way to perform this extension in two stages. This observation shows that these chains of CEs identiﬁed via the AD are of maximal length (and thus correspond to minimal additions), as required in the above scenario.

Example 4.21. Figure 5 a) shows again the -AD of the Koala2 ontology (from Figures 1 and 4), with atoms numbered a, b, . . . , k; the longest chain of CEs induced by the AD is of size 7 and highlighted in the picture: (k, j, i, e, d, c, a). As observed above, this chain implies a suitable order for reading the axioms in Koala2, which consists of the 8 steps in Figure 5 b).

If the AD is based on locality, then the corresponding inseparability relation R is model conservativity; hence the induced axiom reading order can be used to build a model of the decomposed ontology strictly incrementally, i.e., without having to backtrack or reconsider the interpretation of terms. Someone who wants to understand (a part of) an ontology can construct a mental image (i.e., a model) incrementally following this reading order.

α12 α13 α14

Step Axioms Atoms Comments

1 {α12, α13, α14} k 2 {α10, α11} j 3 {α9} i 4 {α5} e 5 {α4, α6} d, f d f 6 {α3} c 7 {α1, α7, α8} a, g, h a g h 8 {α2} b

Figure 5: a) -AD of Koala2 (repeated from Figure 4) with longest chain of CEs; b) reading order implied by this chain.

4.3.3 Computational Properties

The results described in the previous sections, in particular Theorem 4.16 (stating the 1-1 correspondence between axiom modules and genuine modules) suggest that computing an AD is indeed feasible: provided that module extraction is in polynomial time (e.g., for MEX and syntactic locality based modules), it is not hard to see how to design a polynomial algorithm for the computation of the AD. We now present and discuss such an algorithm. A naïve algorithm for the computation can be designed to run in time quadratic in the number of axioms in the ontology using module extraction as an oracle by

extracting, for each axiom, its axiom module and then

pairwise comparing all axiom modules to determine atoms and the dependency relation.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

The second step is quadratic in the number of axioms and requires a record of modules of all axioms; this is clearly infeasible for large ontologies and suboptimal for ontologies with atoms of non-trivial size. In Algorithm 1 we give the pseudocode of an algorithm for the computation of the AD that interleaves the above two points by using so-called key axioms for which to record modules, and by ensuring that, for each genuine module/each atom, exactly one key axiom is identiﬁed.

Algorithm 1: Algorithm for computing the AD of an ontology.

input : An ontology O; a function x-mod( , ) satisfying (M0) (M5) output : The set G(O) of genuine modules; the poset of atoms (A(O), ); a set of key axioms Key Axs

Key Axs Tau Atom

F1 foreach α O do #Compute key axioms, modules & atoms

M Module(α) x-mod(eα, O) if α / Module(α) then #Is α an obvious tautology? Tau Atom Tau Atom {α} else #If not, new true #is there a key axiom β with Mα = Mβ? foreach β Key Axs do

if Module(α) = Module(β) then #If yes, add α to β s atom Atom(β) Atom(β) {α} new false

if new = true then #If not, make α key Key Axs Key Axs {α} Atom(α) {α} #and start assembling its atom

dep #Compute dependency via key axioms

F2 foreach α Key Axs do

foreach β Key Axs do

if β Module(α) then

dep dep {(Atom(β), Atom(α))}

Atoms {Atom(α) | α Key Axs} #Prepare output Gen Mods {Module(α) | α Key Axs} return [Gen Mods; (Atoms, dep); Key Axs]

The algorithm starts with an empty set Tau Atom to record the obvious tautologies in the atom t, and with an empty set Key Axs to record key axioms. It then iterates through all axioms in the ontology, extracts the module for each axiom in turn and, step by step, extends the set of key axioms and builds a record of their modules and atoms. To this end, when it considers an α O, it computes its axiom module Module(α) = Mα. If α / Module(α), then

Modular Structures and Atomic Decomposition in Ontologies

α is added to Tau Atom (see the remarks after Observation 4.3). Otherwise, the algorithm checks whether we already have a key axiom β Key Axs with the same module. If yes, α is simply added to that axiom s atom and we are done with considering α. Otherwise, we add α to the set of key axioms Key Axs and initialise α s atom with {α}. Finally, we compute the dependency relation by comparing all key axioms with all (key) axiom modules.

The correctness of this algorithm is an immediate consequence of the following observations: Corollary 4.12.4 ( ) implies that creating a new atom {α} for each new key axiom α is correct, i.e., α does not belong into the atom of an existing key axiom. Corollary 4.12.4 ( ) implies that adding axioms to the atoms of existing key axioms in case their modules coincide is correct. Then, upon termination, each axiom has been either added to Tau Atom, made a key axiom and added to its own atom, or added to the atom of a key axiom; hence we have partitioned the input ontology into correct atoms. Finally, Lemma 4.11 and Corollary 4.12.3 ensure that the dependency relation between atoms is computed correctly.

Next, we analyse the complexity of the algorithm. Let n be the number of axioms of O. The algorithm iterates through all n axioms and extracts for each an axiom module. In the ith iteration, and in case this axiom module is non-empty, it will also compare it with at most i 1 modules of key axioms. Hence the foreach loop F1 in Algorithm 1 is quadratic in n with n calls to the module extraction oracle (and this can be optimised further in case there are several axioms with the same signature). The subsequent loop F2 is quadratic in the number of key axioms, and thus at most quadratic in n. Overall, this results in a polynomial time algorithm provided that module extraction is polynomial. The fewer atoms there are in an ontology, the fewer key axioms are considered, and hence the closer we get to a linear runtime.

So far, we have treated the module extractor as an oracle. Next, we consider a concrete example, namely the algorithm for the extraction of (non-nested) syntactic locality-based modules as described by Tsarkov (2012), which runs in time that is linear in the size of an ontology. More precisely, to extract one module for a given signature, Tsarkov s module extraction considers each axiom α at most eα times, and thus runs in P α O |eα| steps. When used for module extraction in line M of Algorithm 1, this will thus result in a runtime of n(P α O |eα| + n) + n2. Now we can make one of two assumptions:

1. each axiom in O involves at most c terms, for some constant c. In this case, the runtime of Algorithm 1 is quadratic in the number of axioms in the ontology.

2. the number of terms in axioms is unbounded. In this case and for m the maximal number of terms per axiom in O, Algorithm 1 runs in time n2m and thus quadratic in the size of the ontology.

Algorithm 1 can be further optimised as described by Tsarkov (2012): if Mα contains an axiom β = α then we know that Mβ Mα, hence we only need to check the axioms in Mα when extracting Mβ. This optimisation, however, does not change the asymptotic complexity.

In Section 5 we evaluate the feasibility of computing the AD in practice.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

4.4 Atomic Decomposition as a Modular Structure

In this section, we discuss the Atomic Decomposition as a modular structure, considering the same properties as in our discussions of other modular structures in Section 3. Again, we assume we have ﬁxed a module notion x that satisﬁes (M0) (M5), for example semantic or syntactic locality (see Section 4.1), and omit x if it is clear from the context.

Modules and their properties. In this setting, genuine modules play the role of basic modules: any other x-module is a (not necessarily disjoint) union of genuine modules, see Lemma 4.15 and Corollary 4.17. Since genuine modules inherit the properties from the module notion x they are based on, they are usually not minimal in size, i.e., if one is after a module to cover all entailments over a given signature, there is usually a smaller module than one based on locality. On the other hand, they enjoy other, useful properties such as being self-contained and depleting, see the discussion in Sections 2.3 and 3.1. As observed in Section 3.3.4, the cohesion of modules depends on the choice of x: for locality-based and MEX modules, cohesion can be said to be good since axioms in the same M = x-mod(Σ, O) are likely to be the cause of some entailments over f M, i.e., if M is split into two parts, there are likely to be axioms entailed by M that are not entailed by either of these parts. As a consequence of Theorem 4.16, there are only linearly many genuine modules, and thus they yield a basis of possibly reasonable size especially when compared to that described for locality based modules earlier, see Section 3.3.4.

Modular structure and its properties. In the Atomic Decomposition, the dependency relation on atoms provides us indeed with a dependency relation on (genuine) modules, see Lemma 4.8. As seen in Section 4.3.2, for ADs based on locality, captures modeltheoretic dependencies that can be exploited for speciﬁc tasks such as determining a suitable reading order of axioms in an ontology together with an order on terms for incremental model construction; see also the remarks at the end of Section 4.3.2. In contrast to -decompositions, basic modules of the AD can reﬁne each other and thus we have modules at varying levels of granularity, possibly with overlap, to reﬂect diﬀerent aspects of a given ontology. In contrast to the decomposition based on E-connections, an element of a model of a given ontology can be an instance of concepts from the signature of diﬀerent basic modules, e.g., we can have an instance b of Animal, Marsupial, and Koala, and each of the three concept names is in the (seed) signature of diﬀerent atoms. This is illustrated in Figure 4. Of course, and similar to what we have explained in Section 3.3.4, the granularity and cohesion of the AD depends on the module notion x and the modelling style of the ontology: if x generates only few, large modules from O, then the resulting atomic decomposition will be coarse-grained and some modules will have low cohesion; if x generates smaller modules, then the granularity will be ﬁner and cohesion higher. The generation mechanism for ADs poses an interesting problem: given the AD (A(O), ) of O and a seed signature Σ, the only known mechanism to obtain mod(Σ, O) is to compute it from scratch, i.e., from O; see Del Vescovo, Gessler, Klinov, Parsia, Sattler, Schneider, and Winget (2011) or Del Vescovo (2013) for a discussion on how labels on atoms could be used to optimise the computation of mod(Σ, O) in a variety of scenarios. We illustrate the diﬃculties via a simple example: consider (A(O), ) with three atoms a0 a1 and a0 a2 and

Modular Structures and Atomic Decomposition in Ontologies

Σ = ea1 ea2. The AD carries no information as to whether (i) mod(Σ, O) = a1 a2 = a0 or (ii) mod(Σ, O) = a0. In case (i), Σ leads to a fake module which requires additional terms from ea0 to result in a genuine module. For example, consider the -AD and a1 = {A B}, a2 = {X Y }, and a0 = {C A X R.(B Y )}. Then Σ = {A, B, X, Y } and mod(Σ, O) = a1 a2 is fake, whereas mod(Σ {C}, O) = a0 = O is genuine, i.e., C is the required additional term . In case (ii), the terms in Σ pull in all terms in ea0 and thus lead to a genuine module a0. We obtain such a case by dropping C from the axiom in a0.

Computational Properties As seen in Section 4.3.3, we can compute the AD of an ontology O in time polynomial in the size of O modulo a subroutine for module extraction and, under modest assumptions w.r.t. the complexity of that subroutine, in quadratic time. In Section 5, we investigate the feasibility of computing the AD for existing ontologies.

4.5 AD for Particular Module Notions

In this subsection, we summarise observations relevant for the empirical evaluation of the atomic decomposition based on diﬀerent notions of locality in the next section. We also discuss other notions of modules and how they can be used as the basis for atomic decompositions; in particular we discuss reachabilityand datalog-based modules and MEX modules.

4.5.1 AD for Locality-Based Modules

There is a strong relationship between the ADs based on the three main notions of syntactic locality, which generalises the observation made in Figure 4:

Atoms of the - and -AD are unions of one or more atoms of the -AD (Prop. 4.22).

The dependency relation of the -AD is a reﬁnement of the dependency relations of the - and -ADs; it contains additional edges only between -atoms that are part of the same -atom, or -atom, respectively (Proposition 4.23).

In the following, we ﬁx an ontology O. Given an axiom α O, we write M α, M α , and M α for the axiom module Mα w.r.t. to -, -, or -locality, respectively.

Proposition 4.22. For every -atom a, there is a -atom b and a -atom c with a b and a c.

Proof. We prove only the -case; the -case is analogous. Let a be a -atom. From the deﬁnitions of atoms, axiom modules, and -modules it follows that a M α M α for every α a. Now consider two arbitrary axioms α, β a. Since M α is the smallest -module containing α (Lemma 4.11) and β a M α , every -module containing α contains β too. Since α, β were chosen arbitrarily, we also have that every -module containing β contains α too. Hence any two axioms from a occur in the same -atom, the desired b.

Proposition 4.23. Let a1, a2 be -atoms with a1 a2, and let b1, b2 (c1, c2) be the -atoms ( -atoms) containing a1 and a2. Then b1 = b2 or b1 b2, and c1 = c2 or c1 c2.

Proof. Again, we prove only the -case. Let α a1 and β a2. From the deﬁnition of -modules, we get M α M α. Since a1 a2, we have β M α. Now since M β is the smallest -module containing β (Lemma 4.11), it follows that M β M α. Now Points 1 and 3 of Corollary 4.12 imply b1 = b2 in case M β = M α and b1 b2 otherwise.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

4.5.2 AD for MEX Modules

The situation for MEX modules (Konev et al., 2008) is similar to that of locality-based modules: MEX modules satisfy Properties (M0) (M5) and are thus suitable as a base for the AD. However, we are not aware of any study of MEX-based AD.

4.5.3 AD for Reachability-Based Modules

Reachability-based modules (RBMs) violate (M0) in general (Nortjé et al., 2013), which means that RBMs do not have a meaningful interface, see Section 3.1. Furthermore, it remains to be examined whether they satisfy (M5), and even if this turns out to be the case, then the RBM-based AD would still be incomparable to the AD based on the previously mentioned module notions because the hypergraph-based procedure relies on the ontology being in a speciﬁc normal form. This normal form has been developed for expressive DLs, in particular SRIQ and SROIQ, together with a transformation from an arbitrary SROIQ ontology O into an ontology O in normal form that is a model-conservative extension w.r.t. e O (Nortjé et al., 2013). To the best of our knowledge, it is unclear how the AD of O relates to the AD of O: it is obvious that the AD of O may be far more ﬁne-grained than the AD of O, but the exact nature of this relationship remains open.

4.5.4 AD for Modules Based on Datalog Reasoning

It is also natural to ask whether AD can be based on the suite of module notions introduced by Armas Romero et al. (2016) and described in Section 2.3 from now on called datalogbased modules (DBMs) for short. Although DBMs generalise locality-based modules, we are aware of only very recent, unpublished work on deploying DBMs for AD (Nolte, 2020). This deployment is not straightforward since it has to identify which DBM variants satisfy all Properties (M0) (M5). For example, (M5) is problematic for DBM variants based on implication inseparability (Konev et al., 2009; Armas Romero et al., 2016). Moreover, DBMs rely on a strong form of normalisation for SROIQ diﬀerent from that for RBMs. Armas Romero et al. show that a module for a SROIQ ontology O can be recovered from one such module of the normalisation O of O; however, in order to guarantee that this module is uniquely determined (M1), a closer analysis of suitable denormalisation functions is required.

5. Experimental Evaluation

In this section, we complement the conceptual and theoretical contributions from the previous sections with an empirical study. For this purpose, we use an implementation of the decomposition algorithm described in Algorithm 1 using syntactic locality-based modules ( , , and ), run it on a suitable corpus of ontologies, and evaluate the feasibility of this algorithm as well as the structure and granularity of the resulting ADs.

5.1 Experimental Setting

Corpus To build our corpus, we started with the snapshot of the NCBO Bio Portal ontology repository18 by Matentzoglu and Parsia (2017), which contains 438 ontologies. In a ﬁrst step,

18. https://bioportal.bioontology.org/

Modular Structures and Atomic Decomposition in Ontologies

we removed all ABox axioms (concept and role assertions) from these 438 ontologies: since our re-use and reading scenarios are aimed at the TBox part of an ontology, we want to understand how the AD behaves on TBoxes. From the resulting ontologies, we removed, in a second step, 18 empty ontologies (i.e., these were ontologies that consisted of ABox axioms only) plus a further 69 ontologies that were not in OWL 2 DL (i.e., they were strictly in OWL 2 Full for a variety of reasons). This left us with a corpus of 351 ontologies. Table 1 shows the number of TBox axioms in the ontologies of our corpus ( size ) and the length of these ontologies. The length of an ontology is the number of characters needed to write it down in DL notation, where every term, logical operator, and quantiﬁed role counts as one character, and inclusion/equivalence symbols do not count; e.g., the axiom A R.B has length 3; for details see (Del Vescovo, 2013, page 24). We show percentiles to illustrate the range of ontologies in our corpus: for any given n and measure m, the percentile Pn is the highest m(O) among the n% ontologies Oi with the lowest m(Oi); in particular, P50 is also known as the median and P100 as the maximum.

Mean Std Dev P50 P90 P95 P99 P100 Size 27,806 136,675 1,076 16,347 107,829 806,772 1,700,233 Length 72,425 375,019 2,558 39,325 259,576 1,695,510 4,798,793

Table 1: A summary of our corpus of 351 ontologies. The 50th (median), 75th, 90th, 99th and 100th (maximum) percentiles are shown for the size (i.e. number of axioms) and for the length (i.e., sum of length of axioms) of ontologies.

In Figure 6, we show the OWL 2 proﬁles that the ontologies in our corpus fall into: while this is only an indication of their logical richness, we notice that roughly 49% of our ontologies (171) do not belong to any proﬁle (i.e., are strictly in OWL 2 DL), and that 20% (69) are in all proﬁles, i.e., these are very close to atomic concept and role hierarchies.

Figure 6: The spread of OWL proﬁles across the corpus of 351 ontologies.

Compared to the corpus used by Del Vescovo, Gessler, Klinov, Parsia, Sattler, Schneider, and Winget (2011), we notice that our corpus has more than twice the number of ontologies, and also many more larger ones.

Implementation We evaluate the implementation of Algorithm 1 that is part of the OWL API, namely the one available via Maven Central (maven.org) with an artifact Id of owlapi-tools. We use OWL API Version 5.1.11 to compute -, -, and -AD. All experiments have been performed on Intel(R) Core(TM) i7-6700HQ CPU 2.60GHz RAM 8GB, running Java version 1.8 JDK with an initial heap size of 1 GB and a maximal heap size of 8 GB. Time is measured in CPU time.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

5.2 Feasibility

Regarding feasibility, we are interested in answering the following three questions:

1. Can we decompose all ontologies within a reasonable timeout?

2. How long does it take to decompose an ontology?

3. How does the size of an ontology aﬀect the time needed for decomposing it?

To answer these questions, we ran the AD implementation on all ontologies in our corpus and recorded the CPU time required. The answer to the ﬁrst question is no : 10 ontologies could not be decomposed due to a timeout. We set 6 hours as the timeout for computing each kind of AD, i.e., we used a total timeout of 18 hours for all three kinds of AD. If the ontology cannot be decomposed within 6 hours for at least one kind of AD, we say that this ontology could not be decomposed due to a timeout. In Table 2, we list these 10 ontologies, their characteristics, and the kind of AD whose computation timed out. We note that all 10 ontologies are large, i.e., have over 100k axioms, and that 6 of them are in EL plus possibly other proﬁles. Given the nature of the AD algorithm (see Algorithm 1) and module extraction algorithms, it is clear that logical richness should not have an eﬀect on AD computation performance: even in QL, a single axiom can involve many terms. As we will see next, there are various ontologies that are of similar or larger size and still decomposable. Among the 10 ontologies that could not be decomposed, there are 7 ontologies that can be decomposed by at least one kind of AD computation. From now on, we will ignore all these 10 ontologies and consider only the 341 completely decomposable ontologies.

Ontology Size Length Proﬁles Failed AD gaz 806,772 2,410,202 EL All ncbitaxon 847,755 1,695,510 QL, EL, RL , cco 282,683 565,366 QL, EL, RL , chebi 233,439 538,100 DL dron 874,945 2,655,978 DL , pxo 1,700,233 4,798,793 EL All reto 942,005 2,673,774 QL, EL All dinto 173,859 515,994 DL , ftc 145,425 461,319 EL biomodels 439,240 1,138,365 DL ,

Table 2: The size (the number of TBox axioms) of ontologies that are not decomposable (all due to time-out of 18 hours), their length, proﬁles of those ontologies that could not be decomposed, and the decompositions that failed (e.g. for gaz, the computation of all (three) kinds of AD failed).

Table 3 shows the CPU time (in seconds) required for computing all three kinds of AD for the 341 decomposable ontologies from the corpus. We see that half of our ontologies take less than 1 second to decompose, 95% take under 2 minutes, and 99% take under 1 hour.

Modular Structures and Atomic Decomposition in Ontologies

CPU time (seconds) AD type Mean Std Dev P50 P90 P95 P99 P100 -AD 92.51 676.76 0.11 8.67 55.66 1,919.22 9,066.98 -AD 134.10 998.71 0.16 14.44 72.11 3,034.89 13,764.84 -AD 201.04 1,743.97 0.13 17.75 94.36 1,443.83 18,388.84

Table 3: A summary of the CPU time required for computing the ADs of the 341 decomposable ontologies in our corpus. All time are shown in seconds. Pn represents the maximum time for the nth percentile.

To understand how ontology size aﬀects decomposition time, consider Figure 7: it shows scatter plots of the times for computing the three kinds of AD against ontology size, i.e., each point in each plot represents one of the 341 decomposable ontologies from our corpus, its size (x-axis) and the time it took for the computations of the AD in question (y-axis). All axes are scaled logarithmically. These plots show that the respective ADs can be computed in less than a second for almost all ontologies with up to 1,000 axioms. For the larger ontologies with up to 432,805 TBox axioms, computing the -AD, -AD and -AD requires up to 9,066 seconds ( 2.51h), 13,764 seconds ( 3.82h) and 18,388 seconds ( 5.11h) respectively. The diﬀerences between the three kinds of AD are modest, but we can we can see from the shape of the scatter plots that the computation of the -AD is often faster than that of the -AD. This can be explained by the fact that the computation of a -module is likely to be faster than that of a -module which, in turn, is due to the following facts: the signature of -modules is closed under subconcepts , whereas that of -modules is closed under superconcepts (see Page 993); usually far more concepts are in the lower portion of the concept hierarchy than in the higher one; the locality-based module extraction algorithm involves an outer loop that extends the signature to terms from axioms that were found to be non-local w.r.t. the current signature, and which is thus likely to take longer to include the (longer) chain of superconcepts than the shorter chains of subconcepts. Since this eﬀect does not occur for all ontologies, the point cloud in Figure 7 c is wider and sparser than the ones in Figure 7 a and b, but all three have the same height (for some very large ontologies the -AD requires even more time than the -AD). The plots in Figure 7 seem to indicate a linear growth of the computation time with respect to the ontology size, but the logarithmic scales used can be misleading. Table 4 shows trendlines and conﬁdence intervals of the CPU time for computing the three kinds of AD. We conclude that the computation times for -AD and -AD grow quadratically with the size of the ontology with a high conﬁdence (R2 = 96% and R2 = 93%, respectively), acceptable margins (roughly 1.2 minutes and 3.1 minutes, respectively),19 and tiny coeﬃcients of n2; hence we could call these two behaviours almost linear . We also notice, however, that the conﬁdence of linear trendlines results in a low conﬁdence, and we checked that using cubic trendline functions do not aﬀect them. Unsurprisingly, the conﬁdence for the -AD is rather low and does not improve by choosing polynomials of higher degree: computation times simply vary too widely.

19. Roughly speaking, the conﬁdence interval describes the area above and below the trendline into which other computations will fall with a probability of 95%.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

(a) -AD (b) -AD (c) -AD

Figure 7: Plots of the runtime of AD computation against ontology size.

AD type Degree R2 Trendline function 95% CI -AD 2 0.96 3.88 10 8n2 + 4.11 10 3n 8.43 [20.68, 164.34] 1 0.86 1.64 10 2n 66.39 -AD 2 0.93 6.06 10 8n2 + 4.49 10 3n 4.71 [15.89, 386.15] 1 0.82 2.36 10 2n 95.12 -AD 2 0.33 1.34 10 7n2 + 6.03 10 2n 164.60 [28.09, 240.10] 1 0.16 1.81 10 2n + 35.29

Table 4: A summary of the trendline functions, their determination coeﬃcient (R2) and the 95% conﬁdence interval (CI) of CPU time required for computing the AD against ontology size for the 341 ontologies in our corpus.

5.3 Analysis of the Structure

To understand the stucture of the diﬀerent ADs, we aim at answering the following questions:

1. How many atoms do ADs have? I.e., how ﬁne-grained is the AD?

2. How large are atoms in the AD?

3. How many incomparable (w.r.t. the dependency relation) atoms do ADs have?

4. How much structure does the AD induce? I.e., how often do we ﬁnd ADs with large and/or incomparable atoms?

As in the previous section, all experiments are run on our corpus of 341 decomposable ontologies, as described in Section 5.1.

To answer Question 1, Figure 8 shows scatter plots of the number of atoms in each of the three kinds of AD against ontology size, i.e., each point in each diagram represents an ontology from the corpus and its size (x-axis) and the number of atoms in its AD (y-axis).

Modular Structures and Atomic Decomposition in Ontologies

Number of atoms

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

(a) -AD (b) -AD (c) -AD

Figure 8: Plots of the number of atoms against ontology size.

All axes are, again, scaled logarithmically; the diagonal line marks the ratio 1 case, i.e., the extreme case with one atom per axiom. The -AD (Figure 8 a) is very ﬁne-grained, with many ontologies having ratio 1 or nearby, but there are also outliers, e.g., an ontology with 476 axioms and only 6 atoms. The -AD (Figure 8 b) is even more ﬁne-grained: more points lie on the ratio 1 line, and most other points are closer, except for the outliers. The granularity of the -AD (Figure 8 c) is quite diﬀerent: it is more varied and more coarse-grained than the other two cases, i.e., there are only 3 ontologies (all of them small) with a ratio close to 1, and almost all other ontologies have at least twice as many axioms as atoms.20 Moreover, 27 ontologies have a single -atom, shown by the points on the x-axis.

Atom Size AD type Mean Std Dev P50 P90 P95 P99 P100 -AD 1 10 1 3 4 6 13,064 -AD 1 9 1 2 3 5 13,064 -AD 17 1,201 2 9 15 60 382,519

Table 5: A summary of the all atom size of the 341 ontologies in our corpus. Pn represents the maximum time for the nth percentile.

To answer Question 2, we consider how the size of atoms varies across the ontologies in our corpus, see Table 5. For this table, we count the number of axioms in each atom in the ADs of our ontologies, regardless of the ontology it is a part of. For -AD and -AD, almost all atoms are singletons: 71.67% (for -AD) and 87.76% (for -AD) of atoms in this corpus have only 1 axiom. Additionally, 99% of atoms have at most 6 axioms (6 for -AD and 5 for -AD). For -AD, atoms tend to be larger than for -AD and -AD. Still, 99% atoms have no more than 60 axioms. There are, however, some very large atoms: the -AD yields an atom with 382,519 axioms.

20. This does not imply that we have few singleton atoms: the spread of axioms across atoms may be uneven.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Maximal atom size

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

(a) -AD (b) -AD (c) -AD

Figure 9: Plots of maximal atom size against ontology size.

Finally, Figure 9 shows scatter plots of the size of the maximal atom in each of the three kinds of AD against ontology size, i.e., each point in each diagram represents an ontology from our corpus and its size (x-axis) and the size of the maximal atom in its AD (y-axis). All axes are, again, scaled logarithmically. For -AD and -AD, the maximal atom size varies quite a bit; i.e., some ontologies have only small atoms (ontologies depicted on the x-axis have only singleton atoms), others have some medium-sized atoms, and others have a huge atom (ontologies on the diagonal have a single atom containing all axioms). As we have noticed when we considered the number of atoms in Figure 8 a and b, our corpus contains a non-trivial number of ontologies with only singleton atoms (depicted as points on the x-axis here). The -AD behaves quite diﬀerently to the other two kinds of AD since here, most ADs have a very large atom, and about a third of ontologies (29.6%) have an atom that contains almost all axioms of the ontology (at least 95%). Hence the answer to Question 2 is that, for -AD and -AD, the size of the largest atoms varies considerably but almost all atoms are tiny, whereas for -AD, most ontologies have at least one rather large atom.

To answer Question 3, we consider antichains of atoms in A(O), and use Width(O) to denote their maximal length. Computing maximal antichains is a known hard problem, and we use Dilworth s theorem (2009) and the Hopcroft Karp algorithm (1973) to do so.21

Figure 10 shows scatter plots of the width against the size of ontologies in our corpus.22

We ﬁnd that all three kinds of AD often lead to very wide decompositions. In fact, comparing the width with the number of atoms, we notice that, for most of our ontologies, more than half of their atoms form an antichain: this is the case for 297 out of 340 ontologies (around 87%) for -AD, for 303 out of 340 ontologies (around 89%) for -AD, and 315 out of 340 (around 92%) for -AD. For -AD, however, the presence of large atoms leads to a wider range of widths relative to the ontology size in Figure 10.

21. We implemented the computation of maximal antichains using the implementation of the Hopcroft Karp algorithm from the Java library JGraph T. 22. Our implementation was unable to compute the width of one ontology due to an out-of-memory exception.

Modular Structures and Atomic Decomposition in Ontologies

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

(a) -AD (b) -AD (c) -AD

Figure 10: Plots of AD width against ontology size.

To answer Question 4, we want to understand the joint eﬀect of the individual phenomena observed above on the overall structure of the ADs, in particular how the spread of atom size and number and the length of antichains combine in the ontologies of our corpus. To this end, we consider the partial order on axioms induced by the AD, and determine how close it is to a total order. The closer the induced partial order is to a total order, the fewer large atoms the AD has, and the more atoms are related to each other via the dependency relation, i.e., the smaller the width of the AD and the more structure it has. Also, the closer the induced partial order is to a total order, the more helpful that AD will be for determining a suitable reading order, see 4.3.2. To capture this distance, we follow the approach described by Cook, Kress, and Seiford (1986) to measure the distance between two orders but adapt it to our notation and simplify it (since we are not comparing two arbitrary orders). We start by computing the comparable pairs CPs(O) in the AD A(O) as follows:

For example, consider the ontologies O1, . . . , O4 with ADs as shown in Figure 11, and where each has 100 axioms: both A(O1) and A(O3) have 100 singleton atoms; in A(O1) they form a chain and in A(O3) they form a single antichain. In A(O2), we have one long chain of 50 singleton atoms that depend on the (large) atom a51 with 50 axioms. In A(O4), we have one antichain of 50 singleton atoms which depend on the atoms a26 and a52 with 25 axioms each. In A(O1), i 1 atoms depend on ai (namely those above it), for every i 100. Since all atoms are singletons, Equation (1) yields CPs(O1) = P100 i=1 1 (i 1) = P99 i=0 i = 99 100

2 = 4, 950, i.e., all of the 99 100

2 = 4, 950 pairs of axioms are comparable pairs. In contrast, since each atom in A(O3) depends on no other atom, there are 0 comparable pairs. In A(O2), it is again the case that i 1 atoms depend on ai. Hence (1) yields CPs(O2) = P50 i=1 1 (i 1) + 50 (51 1) = P49 i=0 i + 50 50 = 3, 725. Finally, since A(O4) contains 50

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

𝔄(𝒪1) 𝔄(𝒪2)

𝔞1 𝔞2 𝔞99 𝔞100

Figure 11: Four example ADs.

singleton atoms depending on 25 axioms each (and 2 atoms depending on nothing), (1) yields CPs(O4) = 50 25 = 1, 250. In a next step, the relative reading score RRS(O) is deﬁned as the relativised CPs:

RRS(O) = CPs(O) #O2 #O /2.

Thus, RRS(O) is the special case of the distance between the AD-induced order on axioms and a total order extending it, which has #O2 #O /2 comparable axiom pairs: the maximal axiom is comparable to #O 1 axiom, the next smallest one to #O 2, and so on, i.e. we have (#O 1) + (#O 2) + ... + 1 comparable pairs. Returning to our example ontologies in Figure 11, we see that RRS(O1) = 100%, reﬂecting the fact that the AD induces a total order. Next, RRS(O3) = 0% because its AD induces an empty order. Furthermore, RRS(O2) = 75.25% and RRS(O4) = 25.25%, and hence A(O2) is closer to a total order than A(O4). We have computed the RRS for all ontologies in our corpus, and Figure 12 shows scatter plots of the RRS(O) against the size of the ontology O. We ﬁnd that, for -AD and -AD, the RRS of almost all ontologies is below 20%, namely 298 out of 341 ontologies (around 87.39%) for -AD, and 307 out of 341 (around 90.03%) for -AD. For -AD, the RRS is more evenly distributed and generally higher than that of -AD and -AD. i.e. almost all ontologies have big atoms or/and many/large antichains w.r.t. -AD and -AD.

Now if we compare our RRS and Width, we ﬁnd that they behave similarly for -AD and -AD. For example, for -AD, 87.05% of ontologies have antichains containing at least

Modular Structures and Atomic Decomposition in Ontologies

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

Ontology size (number of TBox axioms)

(a) -AD (b) -AD (c) -AD

Figure 12: Plots of relative reading score (RRS) against ontology size.

half of the AD s atoms, and 87.39% of ontologies have a RRS below 20%. To understand better the causes of low reading scores, i.e., whether they are mainly caused by large atoms or long antichains, we consider the correlations between these metrics. To do so, we need to pick a suitable correlation coeﬃcient: we decide to use the wellknown Spearman s rank correlation coeﬃcient because we want to compare measures that grow quadratically with the ontology size like CPs with measures that are proportional to the ontology size like the Width. In general, we would expect the correlations between the reading score or number of comparable pairs and the width/maximal atom size to be negative but modest since high values of the latter two metrics cause the former two to be low. To compute these scores, we also introduce relativised metrics for the width, RW, and the maximal atom size, MA, so that we can compare them with the (relativised) reading score:

RW(O) = Width(O)

#A(O) , RMA(O) = MA(O)

In Table 6, we use Cor(m, n) to represent Spearman s rank correlation coeﬃcient between parameters m and n, and correlate the ontologies numbers of comparable pairs CPs with their width Width (maximal length of antichains of its AD) and the size of their largest atom MA, and also correlate the corresponding two pairs of relativised metrics.

Correlations AD type Cor(CPs, Width) Cor(RRS, RW) Cor(CPs, MA) Cor(RRS, RMA) -AD 0.6912 -0.4555 0.6922 0.7722 -AD 0.3447 -0.8223 0.8599 0.6534 -AD 0.6521 -0.3133 0.5945 -0.4012

Table 6: Spearman s rank correlation coeﬃcients for CPs and Width, RRS and RW, CPs and MA, RRS and RMA, respectively.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

In contrast to our expections, most correlations are positive. In particular, the nonrelativised metrics are all positive, for all three kinds of ADs. A reasonable explanation is that all three metrics are strongly dominated by the ontology size, i.e., the larger the ontology, the higher are CPs, Width, and MA, and thus we ignore these. As expected, Cor(RRS, RW) is negative for all three kinds of ADs and rather strong for -AD: the latter can be explained by the fact that many ontologies have a -AD with only tiny atoms in a huge antichain, see Fig. 10 and 9. In contrast, this correlation is weaker for -AD and -AD, which is due to these ADs having some large atoms (in particular -AD) and smaller width. Similarly, for -AD, Cor(RRS, RMA) is negative as expected, which can be again attributed to the prevalence of large atoms. In contrast and unexpectedly, this correlation is positive and relatively high for -AD and -AD, which reﬂects the fact that these two kinds of ADs lead to mostly tiny atoms and low RRS. We summarise all ﬁndings from this section in Table 7. In general, we see that many ontologies in our corpus contain many unrelated atomic subsumptions which causes their - and -AD to contain many tiny atoms in large antichains. We also notice that the AD computation is mostly feasible, with the -AD having the largest number of time outs and the -AD showing the largest performance variation. In general, only few of the ontologies in our corpus show a non-trivial structure by coincidence, the two best-structured ontologies (i.e., with the highest relative reading score RRS for all kinds of ADs) are among the oldest, most established ontologies in Bio Portal: both Drosophila Development Ontology and C. elegans Development Vocabulary have been maintained since 2008 and reach RRS values of 76% and 65%, respectively, for -AD. In general, however, the -AD is, among the three kinds of ADs, the most likely one to lead to a better structure as measured by the relative reading score.

AD Number of Size of Width of Reading type Feasibility atoms atoms AD Score -AD fastest, large many tiny, many wide mostly low almost linear some varied -AD most time-outs, large many tiny, mostly very mostly low almost linear some varied wide -AD slowest, varied varied, varied, varied largest variations some huge many narrow

Table 7: Summary of the empirical analysis of the ADs of ontologies in our corpus.

6. Conclusion and Outlook

We have introduced the atomic decomposition of an ontology and analysed its theoretical foundations, in particular the properties of the underlying module notion it relies on. We have discussed the core, general properties of a good modular structure of ontologies, for both the AD and related approaches. In particular, we have shown that the AD is computable in time polynomial in the size of the ontology, while its atoms provide a suitable basis for all modules,

Modular Structures and Atomic Decomposition in Ontologies

and its dependency relation has the potential to support various ontology engineering tasks, e.g., comprehension and module extraction. We have furthermore shown that the majority of ontologies from Bio Portal decompose well, i.e., we can indeed compute their AD in a reasonable time, and the resulting AD is of a reasonable form.

Regarding future work, and as an immediate consequence of our feasibility analysis, it is worthwhile to improve the implementation of AD. A straightforward yet promising optimisation is one aimed at ontologies that are mostly taxonomies, i.e., ontologies that mostly consist of atomic subsumptions. Since the AD of a pure taxonomy coincides with its (inferred) concept hierarchy, we should be able to further optimise the decomposition of mostly taxonomic ontologies by exploiting this relationship during parsing and thus avoiding most calls to the module extractor.

Other future work relates to applications and applicability of the AD in ontology engineering. For this purpose, we have identiﬁed two general goals, described in the following.

Goal 1 is the improvement of our understanding of the AD, which can be achieved in several ways. First, the current axiom-based labels of atoms (see, e.g., Figure 4) are not very informative for tasks such as comprehension and fast module extraction. The generation of labels for each of these tasks would improve the applicability of AD. Second, our granularity analysis showed that the number of atoms can easily be too large for manual inspection. It would be useful to devise heuristics that can be employed to coarsen the decomposition, thus providing a way to control the granularity (i.e., zoom in and out ). Third, if an ontology is being developed and its AD is to be maintained, then it would be practical to update the AD incrementally, rather than recompute it afresh after every change. Our ﬁrst steps in this direction are restricted to axiom additions (Klinov et al., 2012). Fourth, we would like to open the AD to module notions other than locality-based modules. The family of datalog-based modules (DBMs), which generalises locality, is a natural candidate, see also Section 4.5.4. Before the AD can be based on DBMs, however, it is necessary to identify members of the DBM family that satisfy all properties (M0) (M5). Once they are found, the AD based on them can be compared with the AD based on locality-based modules. Finally, the precise relationship of AD with related notions, such as forgetting (Zhao & Schmidt, 2018a), should be studied.

Goal 2 is the design and evaluation of methodologies that make use of AD for several tasks such as collaborative ontology development, ontology maintenance including maintaining a suitable AD and refactoring support for decomposing an OWL ontology into a suitable set of .owl ﬁles (Del Vescovo, Gessler, Klinov, Parsia, Sattler, Schneider, & Winget, 2011), ontology comprehension, the identiﬁcation of a suitable module for reuse/sharing, and automated reasoning and classiﬁcation optimisation (Zhao, Parsia, & Sattler, 2019).

Acknowledgments

We thank Robin Nolte, Sascha Jongebloed, and the anonymous reviewers for their constructive comments on the manuscript.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of Databases. Addison Wesley Publ. Co., Reading, Massachussetts.

Alchóurron, C. E., Gärdenfors, P., & Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions. The Journal of Symbolic Logic, 50, 510 530.

Armas Romero, A., Kaminski, M., Cuenca Grau, B., & Horrocks, I. (2016). Module extraction in expressive ontology languages via Datalog reasoning. Journal of Artiﬁcial Intelligence Research, 55, 499 564.

Baader, F., Calvanese, D., Mc Guinness, D., Nardi, D., & Patel-Schneider, P. F. (Eds.). (2007). The Description Logic Handbook: Theory, Implementation, and Applications (2nd edition). Cambridge University Press.

Baader, F., Horrocks, I., Lutz, C., & Sattler, U. (Eds.). (2017). An Introduction to Description Logic. Cambridge University Press.

Baader, F., Lutz, C., Sturm, H., & Wolter, F. (2002). Fusions of description logics and abstract description systems. Journal of Artiﬁcial Intelligence Research, 16, 1 58.

Bao, J., Voutsadakis, G., Slutzki, G., & Honavar, V. (2009). Package-based Description Logics. In Stuckenschmidt et al. (Stuckenschmidt et al., 2009), pp. 349 371.

Chen, J., Alghamdi, G., Schmidt, R. A., Walther, D., & Gao, Y. (2019a). Ontology extraction for large ontologies via modularity and forgetting. In Proceedings of the 10th International Conference on Knowledge Capture (K-CAP-19), pp. 45 52. ACM.

Chen, J., Ludwig, M., Ma, Y., & Walther, D. (2019b). Computing minimal projection modules for ELHr-terminologies. In Proceedings of the 16th European Conference on Logics in Artiﬁcial Intelligence (JELIA-2019), Vol. 11468 of Lecture Notes in Computer Science, pp. 355 370. Springer-Verlag.

Chen, J., Ludwig, M., & Walther, D. (2018). Computing minimal subsumption modules of ontologies. In Proceedings of the 4th Global Conference on Artiﬁcial Intelligence (GCAI-2018), Vol. 55 of EPi C Series in Computing, pp. 41 53. Easy Chair.

Cook, W. D., Kress, M., & Seiford, L. M. (1986). An axiomatic approach to distance on partial orderings. RAIRO-Operations Research, 20(2), 115 122.

Cuenca Grau, B., Horrocks, I., Kazakov, Y., & Sattler, U. (2008). Modular reuse of ontologies: Theory and practice. Journal of Artiﬁcial Intelligence Research, 31(1), 273 318.

Cuenca Grau, B., Horrocks, I., Kazakov, Y., & Sattler, U. (2009). Extracting modules from ontologies: A logic-based approach. In Stuckenschmidt et al. (Stuckenschmidt et al., 2009), pp. 159 186.

Cuenca Grau, B., Horrocks, I., Motik, B., Parsia, B., Patel-Schneider, P. F., & Sattler, U. (2008). OWL 2: The next step for OWL. Journal of Web Semantics, 6(4), 309 322.

Cuenca Grau, B., Parsia, B., & Sirin, E. (2006). Combining OWL ontologies using Econnections. Journal of Web Semantics, 4(1), 40 59.

Modular Structures and Atomic Decomposition in Ontologies

Cuenca Grau, B., Parsia, B., & Sirin, E. (2009). Ontology integration using E-connections. In Stuckenschmidt et al. (Stuckenschmidt et al., 2009), pp. 293 320.

Cuenca Grau, B., Parsia, B., Sirin, E., & Kalyanpur, A. (2006). Modularity and web ontologies. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR-06). AAAI Press/The MIT Press.

Del Vescovo, C. (2013). The Modular Structure of an Ontology: Atomic Decomposition and Its Applications. Ph.D. thesis, University of Manchester. Available at http: //www.cs.man.ac.uk/~delvescc/thesis.pdf.

Del Vescovo, C., Gessler, D., Klinov, P., Parsia, B., Sattler, U., Schneider, T., & Winget, A. (2011). Decomposition and modular structure of Bio Portal ontologies. In Proceedings of the 10th International Semantic Web Conference (ISWC-11), Vol. 7031 of Lecture Notes in Computer Science, pp. 130 145.

Del Vescovo, C., Klinov, P., Parsia, B., Sattler, U., Schneider, T., & Tsarkov, D. (2013). Empirical study of logic-based modules: Cheap is cheerful. In Proceedings of the 12th International Semantic Web Conference (ISWC-13).

Del Vescovo, C., Parsia, B., Sattler, U., & Schneider, T. (2011). The modular structure of an ontology: Atomic decomposition. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI-11), pp. 2232 2237.

Dilworth, R. P. (2009). A decomposition theorem for partially ordered sets. In Classic Papers in Combinatorics, pp. 139 144. Springer.

Eiter, T., Ianni, G., Schindlauer, R., Tompits, H., & Wang, K. (2006). Forgetting in managing rules and ontologies. In Proceedings of the 5th IEEE/WIC/ACM International Conference on Web Intelligence (WI-06), pp. 411 419. IEEE Computer Society.

Gatens, W., Konev, B., & Wolter, F. (2014). Lower and upper approximations for depleting modules of description logic ontologies. In Proceedings of the 21st European Conference on Artiﬁcial Intelligence (ECAI-14), Vol. 263 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 345 350. IOS Press.

Ghilardi, S., Lutz, C., & Wolter, F. (2006). Did I damage my ontology? A case for conservative extensions in description logics. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR-06), pp. 187 197. AAAI Press/The MIT Press.

Golbeck, J., Fragoso, G., Hartel, F., Hendler, J., Oberthaler, J., & Parsia, B. (2003). The National Cancer Institute s thesaurus and ontology. Journal of Web Semantics, 1(1), 75 80.

Hopcroft, J. E., & Karp, R. M. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4), 225 231.

Horrocks, I., Kutz, O., & Sattler, U. (2006). The even more irresistible SROIQ. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR-06), pp. 57 67.

Horrocks, I., Patel-Schneider, P. F., & van Harmelen, F. (2003). From SHIQ and RDF to OWL: The making of a web ontology language. Journal of Web Semantics, 1(1), 7 26.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Jiménez-Ruiz, E., Cuenca Grau, B., Sattler, U., Schneider, T., & Berlanga Llavori, R. (2008). Safe and economic re-use of ontologies: A logic-based methodology and tool support. In Proceedings of the 5th European Semantic Web Conference (ESWC-08), Vol. 5021 of Lecture Notes in Computer Science, pp. 185 199.

Jongebloed, S. (2020). Ontology Partitioning using E-Connections: Revisited. Master s thesis, University of Bremen. Available at http://jongebloed.me/mthesis.html.

Jongebloed, S., & Schneider, T. (2018). Ontology partitioning using E-Connections revisited. In DL-18, Vol. 2211. CEUR (http://ceur-ws.org/).

Klinov, P., Del Vescovo, C., & Schneider, T. (2012). Incrementally updateable and persistent decomposition of OWL ontologies. In Proceedings of the 9th International Workshop on OWL: Experiences and Directions (OWLED-12), Vol. 849 of CEUR-WS.org.

Konev, B., Lutz, C., Ponomaryov, D., & Wolter, F. (2010). Decomposing description logic ontologies. In Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR-10), pp. 236 246. AAAI Press/The MIT Press.

Konev, B., Lutz, C., Walther, D., & Wolter, F. (2008). Semantic modularity and module extraction in description logics. In Proceedings of the 18th European Conference on Artiﬁcial Intelligence (ECAI-08), pp. 55 59.

Konev, B., Lutz, C., Walther, D., & Wolter, F. (2009). Formal properties of modularization. In Stuckenschmidt et al. (Stuckenschmidt et al., 2009), pp. 25 66.

Konev, B., Lutz, C., Walther, D., & Wolter, F. (2013). Model-theoretic inseparability and modularity of description logic ontologies. Artiﬁcial Intelligence, 203, 66 103.

Konev, B., Walther, D., & Wolter, F. (2009). Forgetting and uniform interpolation in large-scale description logic terminologies. In Proceedings of the 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI-09), pp. 830 835.

Kontchakov, R., Wolter, F., & Zakharyaschev, M. (2010). Logic-based ontology comparison and module extraction, with an application to DL-Lite. Artiﬁcial Intelligence, 174(15), 1093 1141.

Kontchakov, R., Pulina, L., Sattler, U., Schneider, T., Selmer, P., Wolter, F., & Zakharyaschev, M. (2009). Minimal module extraction from DL-Lite ontologies using QBF solvers. In Proceedings of the 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI-09), pp. 836 841.

Koopmann, P., & Chen, J. (2020). Deductive module extraction for expressive description logics. In Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2020, pp. 1636 1643. ijcai.org.

Koopmann, P., & Schmidt, R. A. (2014). Count and forget: Uniform interpolation of SHQontologies. In Proceedings of the 7th International Joint Conference on Automated Reasoning (IJCAR-14), Vol. 8562 of Lecture Notes in Computer Science, pp. 434 448. Springer-Verlag.

Koopmann, P., & Schmidt, R. A. (2015). Uniform interpolation and forgetting for ALC ontologies with ABoxes. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI-15), pp. 175 181. AAAI Press.

Modular Structures and Atomic Decomposition in Ontologies

Kutz, O., Lutz, C., Wolter, F., & Zakharyaschev, M. (2004). E-connections of abstract description systems. Artiﬁcial Intelligence, 156(1), 1 73.

Kutz, O., Wolter, F., & Zakharyaschev, M. (2002). Connecting abstract description systems. In Proceedings of the 8th International Conference on the Principles of Knowledge Representation and Reasoning (KR-02), pp. 215 226.

Lang, J., Liberatore, P., & Marquis, P. (2003). Propositional independence: Formula-variable independence and forgetting. Journal of Artiﬁcial Intelligence Research, 18, 391 443.

Lutz, C., Seylan, İ., & Wolter, F. (2012). An automata-theoretic approach to uniform interpolation and approximation in the description logic EL. In Proceedings of the 13th International Conference on the Principles of Knowledge Representation and Reasoning (KR-12). AAAI Press.

Lutz, C., Walther, D., & Wolter, F. (2007). Conservative extensions in expressive description logics. In Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence (IJCAI-07), pp. 453 458.

Lutz, C., & Wolter, F. (2010). Deciding inseparability and conservative extensions in the description logic EL. Journal of Symbolic Computation, 45(2), 194 228.

Lutz, C., & Wolter, F. (2011). Foundations for uniform interpolation and forgetting in expressive description logics. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI-11), pp. 989 995.

Martín-Recuerda, F., & Walther, D. (2014). Fast modularisation and atomic decomposition of ontologies using axiom dependency hypergraphs. In Proceedings of the 13th International Semantic Web Conference (ISWC-14), Part II, Vol. 8797 of Lecture Notes in Computer Science, pp. 49 64. Springer-Verlag.

Matentzoglu, N., & Parsia, B. (2017). Bio Portal Snapshot 30 March 2017 (data set). Website. http://doi.org/10.5281/zenodo.439510.

Nikitina, N., & Rudolph, S. (2014). (Non-)succinctness of uniform interpolants of general terminologies in the description logic EL. Artiﬁcial Intelligence, 215, 120 140.

Nolte, R. (2020). Die Jagd nach Modul x: Analyse beschreibungslogischer Modulextraktionsverfahren auf ihre Anwendbarkeit zur Atomaren Dekomposition einer Ontologie. Master s thesis (in German), University of Bremen.

Nortjé, R., Britz, K., & Meyer, T. (2013). Reachability modules for the description logic SRIQ. In Proceedings of the 19th International Conference on Logic for Programming and Automated Reasoning (LPAR-19), Vol. 8312 of Lecture Notes in Computer Science, pp. 636 652. Springer-Verlag.

Parikh, R. (1999). Beliefs, belief revision, and splitting languages. In Moss, L. S., Ginzburg, J., & de Rijke, M. (Eds.), Logic, Language and Computation, Vol. 2, pp. 266 278. CSLI Publication, Cambridge University Press.

Parnas, D. L. (1972). On the criteria to be used in decomposing systems into modules. Communications of the ACM, 15(12), 1053 1058.

Del Vescovo, Horridge, Parsia, Sattler, Schneider, & Zhao

Parsia, B., & Schneider, T. (2010). The modular structure of an ontology: an empirical study. In Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR-10), pp. 584 586. AAAI Press/The MIT Press.

Poli, R., Healy, M., & Kameas, A. (Eds.). (2010). Theory and Applications of Ontology: Computer Applications. Springer-Verlag.

Ponomaryov, D. (2008). On decomposability in logical calculi. Bulletin of the Novosibirsk Computing Center, 28, 111 120.

Reiter, R., & Lin, F. (1994). Forget it!. In Proceedings of the AAAI Fall Symposium on Relevance, pp. 154 159.

Sattler, U., Schneider, T., & Zakharyaschev, M. (2009). Which kind of module should I extract?. In Proceedings of the 22nd International Workshop on Description Logics (DL-09), Vol. 477 of CEUR (http: // ceur-ws. org/ ).

Seraﬁni, L., & Tamilin, A. (2009). Composing modular ontologies with Distributed Description Logics. In Stuckenschmidt et al. (Stuckenschmidt et al., 2009), pp. 321 347.

Spackman, K. A., Campbell, K. E., & Côté, R. A. (1997). SNOMED RT: a reference terminology for health care. In Proceedings of the 1st American Medical Informatics Association Annual Symposium (AMIA-97).

Stuckenschmidt, H., Parent, C., & Spaccapietra, S. (Eds.). (2009). Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, Vol. 5445 of Lecture Notes in Computer Science. Springer-Verlag.

Suntisrivaraporn, B. (2008). Module extraction and incremental classiﬁcation: A pragmatic approach for EL+ ontologies. In Bechhofer, S., Hauswirth, M., Hoﬀmann, J., & Koubarakis, M. (Eds.), Proceedings of the 5th European Semantic Web Conference (ESWC-08), Vol. 5021 of Lecture Notes in Computer Science, pp. 230 244. Springer Verlag.

ten Cate, B., Conradie, W., Marx, M., & Venema, Y. (2006). Deﬁnitorially complete description logics. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR-06), pp. 79 89. AAAI Press.

Tsarkov, D. (2012). Improved algorithms for module extraction and atomic decomposition. In Proceedings of the 25th International Workshop on Description Logics (DL-12), Vol. 846. CEUR (http://ceur-ws.org/).

Wang, K., Wang, Z., Topor, R. W., Pan, J. Z., & Antoniou, G. (2009a). Concept and role forgetting in ALC ontologies. In Proceedings of the 8th International Semantic Web Conference (ISWC-09), Vol. 5823 of Lecture Notes in Computer Science, pp. 666 681. Springer-Verlag.

Wang, Z., Wang, K., Topor, R. W., Pan, J. Z., & Antoniou, G. (2009b). Uniform interpolation for ALC revisited. In Proceedings of the 22nd Australasian Joint Conference on Artiﬁcial Intelligence, Vol. 5866 of Lecture Notes in Computer Science, pp. 528 537. Springer Verlag.

World Wide Web Consortium (2012). OWL 2 Web Ontology Language. Website. https: //www.w3.org/TR/owl2-overview/.

Modular Structures and Atomic Decomposition in Ontologies

Zhao, H., Parsia, B., & Sattler, U. (2019). Avoiding subsumption tests during classiﬁcation using the atomic decomposition. In Proceedings of the 30th International Workshop on Description Logics (DL-19), Vol. 573. to appear.

Zhao, Y., & Schmidt, R. A. (2017). Role forgetting for ALCOQH( )-ontologies using an Ackermann-based approach. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI-17), pp. 1354 1361. ijcai.org.

Zhao, Y., & Schmidt, R. A. (2018a). FAME: an automated tool for semantic forgetting in expressive description logics. In Automated Reasoning - 9th International Joint Conference, IJCAR, Vol. 10900 of Lecture Notes in Computer Science, pp. 19 27. Springer-Verlag.

Zhao, Y., & Schmidt, R. A. (2018b). On concept forgetting in description logics with qualiﬁed number restrictions. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence (IJCAI-18), pp. 1984 1990. ijcai.org.