Modular ontologies have received much attention in the past decade; they are usually easier to maintain, comprehend, and reason over. If an ontology is given as a monolithic entity, the task of decomposing it into modules is the first step towards making it modular. Several decomposition approaches have been developed, among them partitionings based on E -connections [2] (henceforth: E -partitions). E -partitions have been developed for the purpose of automatically and e ciently decomposing an ontology into a graph whose nodes are (pairwise disjoint and mutually covering) components (i.e., subsets) of the ontology, and whose edges represent “semantic links” between the components in the style of E -connections [5]. The adoption of the E -connection framework ensures that the resulting partitions provide strong logical guarantees, such as encapsulation. E -Connections have been defined for abstract description systems (ADSs), a notion that generalises description logics (DLs) and further formalisms. An E -connection is a combination of (heterogeneous) logical theories via semantic links established by a designated set of relations, called link relations. The semantics of such a combination is given by interpretations consisting of pairwise disjoint components. In contrast to the general nature of E -connections, E -partitions have been defined specifically for the DL SHOIQ(D), a fragment of the latest OWL 2 ontology language. The partitioning procedure starts from a monolithic ontology O and attempts to turn it into an (as fine as possible) E -connection by identifying link relations among the roles in O. In [1,2] an e cient algorithm is given. To ensure that the resulting E -partition and the input ontology are equivalent under the E -connection semantics, an additional condition has to be imposed on the input ontology, which was called safety and coincides with domainindependence (DI), as known from first-order logic and database theory. Contrary to DI in first-order logic, DI for SHOIQ(D) is decidable. The partitioning algorithm was implemented as an experimental feature of the (discontinued) ontology editor Swoop. Initial experiments [2] showed that some ontologies admit useful E -partitions, sometimes revealing modelling deficiencies. On the other hand, some modelling patterns - e.g., the use of few top-level concepts - are notoriously problematic: they admit only coarse E -partitions. The limited success of E -partitions may be due to this observation, but may also lie in the preliminary nature of the implementation. Hence some observed “poor” (i.e., coarse-grained) E -partitions might be due to code bugs and not “features” of the general approach.
When pursuing this last question, we found a considerably simpler way of computing
E -partitions, based on the idea of creating an undirected graph G whose edges connect
concepts and/or roles that must be part of the same component, and reading the minimal
E -partition o G’s connected components. We were able to extend the underlying
framework to most of OWL 2, with the only exception of the universal role u. This
exception is unavoidable in some sense [
Our new approach o ers the following advantages over the original one:
– Ready applicability to the latest OWL 2 standard, under two restrictions ensuring
equivalence (domain-independence, absence of the universal role)
– A simplified notation of the theoretical foundations
– A new deterministic partitioning algorithm that is based on a simple idea and can be
implemented to run in linear time (the original one is quadratic)
– Simple rigorous proofs that the algorithm is correct and outputs the maximal
equivalent E -connection
In the light of these advantages, we predict an easy implementation of the algorithm and
plan experiments on an up-to-date corpus of existing ontologies. The work reported here
is therefore in progress. This extended abstract summarises the submission [
E -Connections and Partitionings for S ROI Q
We consider SROIQ, the description logic (DL) underlying OWL, minus the universal
role (see above). We omit datatypes and keys, discussing their addition (and of further
non-OWL features) in [
Let be a signature, i.e., a finite set of terms (concept, role, and individual names). Given a natural number n 1, an n-numbering of is a function that assigns to each concept and individual name a number (A); (a) 2 f1; : : : ; ng and to each role name a number (r) 2 f1; : : : ; ng2. Numberings are extended inductively to arbitrary concepts and axioms. A concept C (axiom ) is called an i-concept (i-axiom) if (C) = i ( ( ) = i).
Given an n-numbering , a -ontology is a tuple O = (O1; : : : ; On), each of whose components Oi is a nonempty set of i-axioms. The semantics of -ontologies is given by -interpretations, whose domain consist of n pairwise disjoint nonempty sets, and which interpret every i-concept name and i-individual name in the i-th component, and every (i; j)-role name as a relation between the i-th and j-th component. The interpretation function is extended in the obvious way to arbitrary concepts; satisfaction of i-axioms is defined as expected and denoted I j= . A -ontology I is a model of a -ontology O, written I j= O, if I j= for all axioms in O. O is consistent if it has a model.
The correspondence between simple and -ontologies is captured by compatibility and equivalence (the former being syntactic and the latter semantic).
Definition 1. Let O be an ontology, an n-numbering, and O = (O1; : : : ; On) a -ontol. 1. O and O are compatible, written O 2. O and O are equivalent, written O
O, if O = Si n Oi .
O if, for all -interpret. I: I j= O i I j= O.
Compatibility implies equivalence under an additional assumption: domain-independence
as known from the first-order and database worlds. A concept C (axiom ) is
domainindependent (DI) if CI = CJ (I j= i J j= ) for all interpretations I; J with
XI = XJ for all terms X. An ontology is DI if so are all its axioms. For (most of)
SROIQ, DI can be decided e ciently via a syntactic characterisation, called locality
in [
Theorem 2. Let O be an ontology, an n-numbering, O = (O1; : : : ; On) a -ontology. 1. (a) If O is DI and O O, then O O.
(b) If additionally O is consistent, then so is O. 2. If O is not DI and consistent and O O and O 3
O, then n = 1, i.e., O = O.
We now present the partitioning algorithm. As in [
For example, let O = fA v 9r:B; B v B0g. Then G has nodes A; 9r:B; r0; r1; B; B0, and edges fA; 9r:Bg; f9r:B; r0g; fr1; Bg; fB; B0g. Edges fA; 9r:Bg and fB; B0g are labelled A v 9r:B and B v B0, respectively. Now G has 2 connected components (CCs): G1 with nodes A; 9r:B; r0 and label ; G2 with r1; B; B0 and . Hence O = (fA v 9r:Bg; fB v B0g). 4
We have extended the original approach underlying E -partitions in [
For future work, we expect a straightforward implementation of our algorithm, as a basis for experiments on a representative up-to-date ontology corpus. We conjecture that existing ontologies generally decompose well when allowing slight deviations from (syntactic) compatibility, to circumvent the notorious problematic modelling patterns, see x1. We furthermore plan to revisit module extraction, extending the existing procedure 2 switch C do case :D do E case D u F do E case >m R:D do E case 9R:Self do E case fag do E 16 Function addAxiomEdges(G; ): 9 Function addSubConceptEdges(G; C):
E [ fC; Dg E [ ffC; Dg; fC; Fgg E [ ffC; R0g; fR1; Dgg E [ ffC; R0g; fC; R1gg
E [ ffC; agg 1 Function partition(O): input : O with signature
output: -ontology O V fC j C 2 sub(O)g [ fr0; r1 j r 2 Rg; E ;; L forall C 2 sub(O) do addSubConceptEdges(G; C) forall 2 O do addAxiomEdges(G; ) ; fG1; : : : ; Gng all connected components (CCs) of G with 1 axiom label forall i n do Oi f j L(v; v0) = for some edge (v; v0) in Gig O (O1; : : : ; On)
D do E E [ fC; Dg; S or Disjoint(R; S ) do
E E [ ffR0; S 0g; fR1; S 1gg;
L(C; D) L(R0; S 0) case R S v T case C(a) case R(a; b) case a b or a 0 b do E do E do E do E
E [ ffR1; S 0g; fR0; T0g; fS 1; T1gg; L(R0; T0) E [ fC; ag; L(C; a) E [ ffa; R0g; fR1; bgg; L(a; R0)
E [ ffa; bgg; L(a; b)
in [