In an earlier paper, we presented a logical framework for representing and reasoning with modular ontologies with a special focus on supporting localized reasoning and integrity in the face of changes. This framework while being based on a formal semantics, was not specific to a particular logic used to specify ontologies and links between modules. As a result, no system was provided that implemented the ideas presented in that paper. In this work, we close this gap by explaining, how the general framework for modular ontologies can be mapped onto distributed description logics and implemented using the DRAGO reasoning system. In particular, we refine the notion of modular ontologies to the case where local ontologies are represented in SHIQ. We define a sound and complete inference rule for modular ontologies based distributed decsription logic and analyze the worst case complexity of reasoning in the framework. We also briefly discuss the DRAGO system and describe how our framework can be mapped on the representations supported by DRAGO.
The benefits of modularization have been acknowledged in many area of
computer science. With the increasing use of ontologies in real applications, the need
for modular representations that support selective reuse, easier maintenance
and efficient localized reasoning has been recognized by a number of researchers
(e.g. [
This paper contains the following contributions that go beyond the work published in [12]: – We formally relate the notion of a modular ontology to distributed description logics – We formally characterize reasoning in modular ontologies in terms of the relation to DDL – We show that the worst-case complexity of reasoning in modular ontologies is the same as for reasoning in the local ontologies – We extend the compilation algorithm given in [12] to cover all possible inferences of subsumption relations – We explain how the approach can be implemented in the DRAGO system.
The paper is structured as follows: We first briefly recall basic definitions of
description logics and formally introduce the language SHIQ. We then recall
distributed description logics as introduced in [
In this paper, we consider ontologies represented in the description logic SHIQ.
This choice is motivated by the fact that SHIQ covers a large part of the
expressive power of the Web Ontology Language OWL [
Let C be a set of concept names and RN a set of role names. Further let there be a set R+ ⊆ RN of transitive roles (i.e. for each r ∈ R+ we have r(x, y) ∧ r(y, z) ⇒ r(x, z)). If now r− denotes the inverse of a role (i.e. r(x, y) ⇒ r−(y, x)) then we define the set of roles R as RN ∪{r−|r ∈ RN }. A role inclusion axiom is an expression r v s where r and s are roles. A role is called a simple role if it is not transitive and does not have transitive subroles with respect to the transitive closure of the role inclusion relation. Concept expressions are now formed by applying special operators to concept and role names. In particular, new concept expressions can be formed from existing ones using the Boolean operators or by imposing constraints on the type and number of objects related to objects of the described concept. The corresponding operators are summarized below.
¬C All objects that are not of type C C u D All objects that are of type C and of type D C t D All Objects that are of type C or of type D ∃r.C All Objects that related to some objects of type C via relation r ∀r.C All Objects that are only related to objects of type C via relation r (≥ n r.C) All objects that are related to at least n objects of type C via relation r (≤ n r.C) All objects that are related to at most n objects of type C via relation r
Formally, the set of concepts (or concept expressions) in SHIQ is the smallest set such that: – > and ⊥ are concept expressions for the most general concept and the unsatisfiable concept, respectively; – every concept name A is a concept expression; – if C and D are concept expressions, r is a role, s is a simple role and n is a non-negative integer, then ¬C, C u D, C t D,∀r.C, ∃r.C, (≥ n r.C) and (≤ n r.C) are concept expressions.
A general concept inclusion axiom is an expression C v D where C and D are concepts. A terminology is a set of general concept inclusion and role inclusion axioms.
The semantics of SHIQ is defined in terms of an interpretation I = (ΔI , .I ) where .I is a function that maps every concept on a subset of ΔI and every role on a subset of ΔI × ΔI such that for all concepts C and D and for roles r where #M denotes the cardinality of M and (rI )+ the transitive closure of rI we have: – >I = ΔI and ⊥I = ∅ – rI = (rI )+ for r ∈ R+ and r− = {(y, x)|(x, y) ∈ rI } – (¬C)I = ΔI − CI , (C u D) = CI ∩ DI and (C t D)I = CI ∪ DI – (∀r.C)I = {x|∀y.(x, y) ∈ rI ⇒ y ∈ CI } – (∃r.C)I = {x|∃y.(x, y) ∈ rI ∧ y ∈ CI } – (≥ n r.C)I = {x|#{y.(x, y) ∈ rI ∧ y ∈ CI } ≥ n} – (≤ n r.C)I = {x|#{y.(x, y) ∈ rI ∧ y ∈ CI } ≤ n}
An interpretation satisfies a terminology T if CI ⊆ DI for all general concept inclusions C v D in T and rI ⊆ sI for all role inclusion axioms r v s in T . In this case we call I a model for T . A concept D subsumes a concept C in T if C v D holds for all models of T . In the remainder of the paper we will focus on the task of deciding whether a concept subsumes another one. 3
Distributed Description Logics as proposed in [
Let I be a non-empty set of indices and {Ti}i∈I a set of terminologies. We prefix inclusion axioms with the index of the terminology they belong to (i.e. i : C denotes a concept in terminology Ti and j : C v D a concept inclusion axiom from terminology Tj ). Note that i : C and j : C are different concepts. Semantic relations between concepts in different terminologies are represented in terms of axioms of the following form, where C and D are concepts in terminologies Ti and Tj , respectively: – i : C −v→ j : D (into-rule) – i : C −w→ j : D (onto-rule) These axioms are also called bridge-rules. The into-rule states that concept C in terminology Ti is intended to be more specific than concept D in terminology Tj . Conversely, the onto-rule states that concept C in terminology Ti is intended to be more general than concept D in terminology Tj . An additional rule ≡ i : C −→ j : D is defined as the conjunction of the two rules above, stating that the two concepts are intended to be equivalent. A distributed terminology T is now defined as a pair ({Ti}i∈I , {Bij }i6=j∈I ) where {Ti}i∈I is a set of terminologies and {Bij }i6=j∈I is a set of bridge rules between these terminologies.
The semantics of distributed description logics is defined in terms of a global interpretation I = ({Ii}i∈I , {rij }i6=j∈I ) where Ii is an interpretation for terminology Ti as defined above and rij ⊆ ΔIi × ΔIj is a domain relation connecting elements of the interpretation domains of terminologies Ti and Tj . We use rij (x) to denote {y ∈ ΔIj |(x, y) ∈ rij } and rij (C) to denote Sx∈C rij (x).
A distributed interpretation I satisfies a distributed terminology T if: – Ii satisfies Ti for all i ∈ I – rij (CIi ) ⊆ DIj for all i : C −v→ j : D in Bij – rij (CIi ) ⊇ DIj for all i : C −w→ j : D in Bij In this case we call I a model for T. A concept i : D subsumes a concept i : C (i : C v D) if for all models of T we have CIi ⊆ DIi . 4
We can now define our notion of a modular ontology in terms of Distributed Description Logics. In fact, our notion of a modular ontology is a restricted form of distributed terminology as defined above. The restrictions we impose concern the architecture of the distributed terminology as well as the expressiveness of semantic relations between terminologies. These restrictions are motivated by the aims of (1) providing an alternative to the standard notion of import in OWL and (2) the goal of providing support for localized reasoning and maintenance of the modular ontology. In the following, we will first discuss the architecture of a modular ontology and then introduce the restrictions imposed on semantic relations. 4.1
As described above, DDL makes a clear distinction between terminologies and semantic mappings between them in terms of bridge rules, which in principle are independent of the terminologies. This makes the model quite flexible; for example, it permits having different sets of mapping rules connecting the same set of ontologies. In this way it is possible to encode different views on how the terminologies relate to each other. In contrast, our aim is to enable the use of external knowledge in a terminology similar to the ability of OWL to use concept and role names defined in different terminologies. This view is different from the model of Distributed Description Logics as it makes the semantic links to other models part of the terminology. Being part of the terminology implies that there is only one way of connecting to these external definitions which is assumed to be agreed on by the users of the local terminology.
We achieve this localization of semantic relations by introducing the notion of externally defined concepts in a terminology. We divide the set of concept names in a terminology into internally defined concepts CI and externally defined concepts CE resulting into the following description of the set of all concept names C (C = CI ∪ CE , CI ∩ CE = ∅).
We consider externally defined concepts to be concept names linked to a concept expression defined in another terminology using bridge rules. An external concept definition in terminology Ti is an axiom of the form: i : C ≡ Tj : D where C is a concept name in Ti, Tj is a terminology different from the one in which the external concept is defined and D is a concept expression in Tj . Note that although D is syntactically represented in Ti it actually represents a concept in Tj . In particular the expression D is only allowed to contain concepts defined in Tj . This definition is very close to the OWL mechanism of using concept and role names from other name spaces in definitions.
We give external concept definitions a semantics in terms of distributed description logics by defining external concept definitions to be an alternative notation for a pair of bridge rules:
i : C ≡ Tj : D ⇔ j : D −v→ i : C ∧ j : D −w→ i : C
The correspondence between external concept definitions and bridge rules allows us to base our further investigations on the formal results that have been established for distributed SHIQ terminologies. 4.2
In Distributed Description Logics, there are no restrictions on the the antecedent of a bridge rule—except that it has to be a valid concept of the source terminology. In our framework, we restrict this freedom for the sake of an easier maintenance of the semantic relations between terminologies. This restriction is motivated by our earlier work on keeping integrity in modular ontologies reported in [12]. In that work, we proposed a heuristic approach for determining the impact of changes in other modules on the correctness of local subsumption reasoning. The approach relied on the fact that changes were only monotonically propagated to other modules. In order to achieve this effect also in the framework of distributed description logics, we restrict the language used to specify externally defined concepts to a sublanguage of SHIQ that does not contain operators that can have a non-nonotonic effect, in particular negation, universal restrictions and qualified number restrictions that limit the number of related concepts. More precisely, we allow concept expressions that are defined in the following sublanguage of SHIQ:
C, D −→ > | ⊥ | A | C u D | C t D | ∃r.C | ∃r−.C | ≥ n r.C | ≥ n r−.C In order to restrict the semantic correspondences between terminologies in our model, we now only allow the concept expressions D in the definition of external concepts to be valid concepts over terminology Tj with respect to the sublanguage defined above. We denote such concepts as DQ and consider external concept expressions of the form i : C ≡ j : DQ. 5
The direct correspondence of our framework to Distributed Description Logic allows us to base inference in modular ontologies on known results for the corresponding DDL. In particular, we can provide completeness and complexity results for reasoning in modular ontologies. We extend the existing work on reasoning in DDL with the notion of compilation of implied subsumption relations. Specifically, we use reasoning methods for Distributed Description Logics to derive subsumption relations between externally defined concepts in modules and explicitly add the derived subsumption relations as axioms to the module. The results of [11] guarantee that after this compilation step reasoning can be performed locally without considering other modules unless there are changes in the system.
In the following, we first briefly review basic definitions of reasoning in distributed description logics and prove that it has the same worst-case complexity as reasoning in SHIQ. We then present the compilation of subsumption relations and discuss conditions for completeness and consistency. 5.1
Reasoning in DDL differs from reasoning in traditional Description Logics by the way knowledge is propagated between T-Boxes by certain combinations of bridge rules. The simplest case in which knowledge is propagated is the following: i:A−w→j:G,i:B−v→j:H,i:AvB
j:GvH
This means that the subsumption between two concepts in a T-Box can depend on the subsumption between two concepts in a different T-Box if the subsumed concepts are linked by the onto- and the subsuming concepts by an into rule. In languages that support disjunction, this basic propagation rule can be generalized to subsumption between a concept and a disjunction of other concepts in the following way: n i:A−w→j:G,i:Bk−v→j:Hk(1≤k≤n),i:AvkF=1 B
n j:GvkF=1 Hk
It has been shown that this general propagation rule completely describes reasoning in DDLs that goes beyond well known methods for reasoning in Description Logics. To be more specific, adding the inference rule in equation 2 to existing tableaux reasoning methods leads to a correct and complete method for reasoning in DDLs. A corresponding result using a fixpoint operator is given in [11]. Based on these results, we can define a general inference rule for the case of modular ontologies in the following way: n i:A≡j:G,i:Bk≡j:Hk(1≤k≤n),i:AvkF=1 B
n j:GvkF=1 Hk (1) (2) (3)
There are a number of consequences of this result for reasoning in modular ontologies.
Correctness and Completeness From the basic propagation rule, we can see that subsumption between externally defined concepts follows from subsumption of their definitions in the (same) external module. This is because each external concept definition corresponds to an into and an onto rule between the concept name and its definition. The language we consider is SHIQ and therefore we have to consider the general propagation rule because we have disjunction in our language. This means that it is not enough to simply check whether subsumption between the definitions of two externally defined concepts in the external module is complete, but we have to consider all subsets of the set of external concepts. We will discuss this point in more detail in the next section.
Complexity As we reduce reasoning in modular ontologies to reasoning in DDLs with SHIQ as a local language, complexity results can be derived from known results on reasoning in SHIQ and Distributed Description Logics. In particuar, reasoning in modular ontologies is at least as hard as reasoning in SHIQ: in the extreme case a modular ontology consists only of a single module without external concepts, thus reasoning in modular ontologies is equivalent to reasoning in SHIQ. Further, reasoning in modular ontologies is not harder than reasoning in SHIQ because we reduce reasoning in modular ontologies to reasoning in DDLs. There exists a reduction of reasoning in DDLs with SHIQ as a local language to SHIQ[?]. Both reductions are linear in the size of the resulting terminology and therefore do not change the complexity class. This shows that the complexity of reasoning in modular ontologies is not worse than reasoning in the web ontology language. Using the reduction of DDL to SHIQ it is even possible to use existing OWL reasoners for reasoning with modular ontologies. Although practical implementations of OWL reasoners have shown that good average case performance can be achieved, the worst case complexity is still very high and asks for further optimization. 5.2
Existing reasoners for expressive Description Logics are highly optimized with respect to deciding subsumption in the context of a single T-Box. Serafini and Tamilin present a distributed reasoning system that extends existing reasoners to distributed T-Boxes [10]. In theory, this system is complete with respect to the propagation rules described above and has—as we have argued—the same worst-case complexity. In practice, however, reasoning with multiple, possible distributed modules, brings some new problems with respect to completeness and reasoning performance. First of all the completeness of the distributed reasoners depends on the availability of local reasoners for all T-Boxes in the system. In a loosely coupled network without central control this cannot always be guaranteed as network nodes can be unreachable or even leave the network. In this case, necessary subsumption tests cannot be performed at these nodes leading to a possible incompleteness. Another problem currently not addressed in the work of Serafini and Tamilin are performance problems due to communication costs between the different nodes in the system. Work in the area of distributed databases has shown that communication costs often become serious bottlenecks in distributed systems.
In order to overcome these problems we propose to compute subsumption relations between external concepts offline and store them as explicit axioms in the local ontologies. If we compute these relations using the reasoner mentioned above we have the guarantee that reasoning about subsumption in each module can be done without caring about the availability of other nodes in the network. This also has the advantage that no communication costs occur as part of online reasoning.
Of course these runtime benefits have their price in terms of computational complexity of the compilation step. The completeness of the propagation rule given in equation 2 tells us that to be independent from other modules we only have to consider subsumption relations between externally defined concepts, as only such subsumption relations can be propagated from outside. What we have to check is subsumption between each external concept and the disjunction of all combinations of other external concepts. For a local module, this process is defined in algorithm 1.
end if end for end for
Require: An T-Box T with external concepts CE for all c ∈ CE do candidates := P(CE − {c}) for all d ∈ candidates do if I |= c v F e then
e∈d T := T ∪ {c v F e}
e∈d
If we denote the number of external concepts CE as n, the worst-time complexity of the compilation method is O(n · 2(n−1)) as can easily be seen from the algorithm. As deciding the subsumption relation in the conditional statement of the algorithm itself is already Exp-Time and this test has to be carried out an exponential number of times with respect to the number of external concepts, compiling all implied statements is computationally very expensive. We therefore do not want to perform the compilation step more often than absolutely necessary to guarantee that local reasoning is still complete.
While the results of Serafini and others [10] guarantee that local reasoning is correct and complete at the time the compilation is carried out, a problem occurs when changes are made to the system. Changes in the definitions of the external concepts, but also changes in the definitions of concepts and relations in other modules can make local reasoning incomplete or inconsistent. In order to prevent situations in which local reasoning is not correct and complete any more we introduce the notion of integrity of a modular ontology. Definition 1 (Integrity). Let T = ({Ti}i∈I , {Bij }i6=j∈I ) be a modular ontology with interpretation I = ({Ii}i∈I , {rij }i6=j∈I ) then we say that integrity holds for T if for all Ti0 = compile(Ti) with interpretation Ii0 we have:
Ii0 |= C v D ⇔ I |= i : C v D for any pair of legal concept expressions C and D in Ti0.
The notion of integrity gives us a criterion for deciding whether compiled results are still valid. What the definition does not provide is an operational account for checking it. A direct use of the definition would involve a complete check of all derivable subsumption relations. As we have argued above this approach is extremely expensive. In the following, we therefore present a heuristic approach for checking integrity in modular ontologies that is driven by changes made to the ontology. The approach is capable of determining situations in which changes to a modular ontology do not affect integrity and therefore no re-compilation is necessary. 6
DRAGO is a reasoning system for Distributed Ontologies that supports reasoning in distributed description logics with the limitation that bridge rules might only be specified between concept names. The DRAGO System consists of a set of reasoners each implemented as an independent peer. Each of the peers has a local ontology represented in the subset of OWL-DL that corresponds to the description logic SHIQ (i.e. OWL-DL without enumerated classes and datatypes). The different peers are connected to form a peer network by means of mappings (sets of bridge rules) connecting the individual ontologies and forming a distributed T-Box [10]. Given a distributed T-Box, T, the following reasoning services are available in the DRAGO system: – Local/global satisfiability: check if Ti |= C ≡ ⊥, and T |= i : C ≡ ⊥ – Local/global subsumption: check if Ti |= C v D, and T |= i : C v D – Local/global classification: Produce a classification on the atomic concepts of Ti. A classification on a set of atomic concepts C, is directed acyclic graph hC, ≺, ∼i, where C is the set of atomic concepts of the language of Ti and ≺ constitute a directed acyclic graph on C, and ∼ is an equivalence relation on C. And the following properties holds, C ∼ D iff Ti |= C ≡ D (resp T |= i : C ≡ D), C ≺ D if and only if Ti |= C v D and Ti 6|= C v D, (resp. T |= i : C v D and T 6|= i : C v D). Furthermore if C ≺ D then for no E ∈ C, C ≺ E ≺ D
Based on the correspondence between our notion of modular ontologies and a subset of distributed description logics, we can use the functionality of the DRAGO system to implement reasoning in modular ontologies. In the following, we briefly explain the steps necessary for implementing a modular ontology using the DRAGO system. step 1: Distributing Ontology Modules In the first step, we instantiate a reasoning peer for each module of the ontology. For each peer an ontology is created consisting of the internal concept definitions of the respective module. step 2: Create Mappings For each pair of modules Mi, Mj we create the mapping set. This is done by looking at the external concept definitions in module Mi. For each external defintion i : C ≡ Mj : D we create a new concept name D (note that in the external defintion D0 can be a complex concept expression) and add the two bridge rule i : C −v→ j : D0 and i : C −w→ j : D0 to the mapping set Bij. step 3: Enrich Local Ontologies For externally defined concept i : C ≡ Mj : D, we create a new concept definition D0 ≡ D and add it to the ontology created for module Mj. This step is necessary for cope with the limitation of DRAGO system to mappings between concept names. step 4: Connect Local Ontologies Finally, we connect the different modules by loading the mappings created in step 2 into the system thereby connecting the different modules.
This implementation of modular ontologies allows us to use the reasoning services provided by DRAGO to compute implied subsumption relations and to store them locally to support local reasoning as explained in the previous sections. If we restrict our approach to the simplified inference relation shown in equation 1 we can directly use the global classification method of DRAGO to compute all implied subsumption relations and store them locally. If the goal is completeness, we have to add another control structure that checks subsumption between a concept and all combinations of disjunctions of other concept names. This is computationally quite expensivem but can easily be done using the DRGAO API. 7
Reasoning in modular ontologies is complex. We have seen that the complexity is essentially the same as for reasoning in classical Description Logics which are the basis for OWL. We cannot escape this complexity, but we can move parts of the reasoning effort offline by compiling implied subsumption relations as described in Section 5.2. This approach, however, is only feasible if there are phases where the offline computation necessary to compile the implied relations can be done without affecting the performance of the system. Typically, such computations are done ‘overnight’ when the system load can be assumed to be low. An alternative for situations where this approach is not possible is to do the compilation on the fly. In particular, we can compile implied subsumption relations whenever they are computed in order to answer a user query to the system. This kind of ‘lazy compilation’ has the advantage that the enormous effort for compiling implied knowledge is done as part of the normal reasoning process. In the beginning, users will not benefit much from this approach, but the time savings increase with each query answered. In this way, we also prevent the compilation of knowledge that is never used.
The main problem connected with the compilation approach, is the integrity of the compiled knowledge. In general compilation approaches only pay off if the computation time saved by being able to use compiled knowledge is not larger than the effort of updating the compiled knowledge. This means that compilation only makes sense in rather stable systems. In principle, we can assume that knowledge on the terminological level as it is represented in ontologies is normally more stable than instance data as normally found in databases. While changes to ontologies will occur less frequently they can still have a significant impact on the system. For this reason, our work focussed on heuristics for efficiently updating the system when changes occur. In this context, the feasibility of the approach relies on the adequacy of the heuristics chosen.
A final point for discussion is the generality of the approach described. Throughout this paper, we based our discussions on Description Logics as a representation language for ontologies, Distributed Description Logics for providing the semantics of mappings as well as the equivalent of conjunctive queries for describing relations between different modules. All of these choices are carefully made and are motivated by practical as well as theoretical considerations. Probably the most uncontroversial choice is that of Description Logics for encoding ontologies. In the context of semantic web research, Description Logics have become the primary language for describing terminological knowledge mostly in terms of the Web Ontology Language OWL. Our approach covers most of the expressiveness of OWL-DL with the exception of nominals. As a result, most existing OWL ontologies will fit in our framework and could easily be turned into modular ontologies by adding external concepts.
A choice that is less obvious is Distributed Description Logics as a basis for
the semantics of mappings. In a recent survey, we compared different approaches
for describing mapping semantics [9]. One result of this comparison was that
Distributed Description Logics provide the highest degree of de-coupling
between different T-Boxes. This is important for our purposes as we want to
support localized reasoning. A generalization of Distributed Description Logics
in terms of a distributed version of first order logic has been described by
Serafini and Ghididi [
The most controversial choice is to restrict the language that can be used to define external concepts. The framework of Distributed Description Logic allows us to use arbitrary SHIQ expressions in the definitions. A corresponding more general approach would have the same properties with respect to logical consequence, compilation and local reasoning. The restriction to the sublanguage was motivated by the importance of the monotonicity property for the definition of update heuristics defined in [12]. This means that external concepts can be defined using a more expressive language. This, however, would come at the price that implied subsumption relations concerning this concept would have to be recomputed every time a change occurs. We believe that the restriction proposed in this paper is reasonable as it allows the use of update heuristics and also resembles view-based information integration, the dominant approach for describing mappings between database schemata. 9. L. Serafini, H. Stuckenschmidt, and H. Wache. A formal investigation of mapping languages for terminological knowledge. In Proceedings of the 19th International Joint Conference on Artificial Intelligence - IJCAI05, Edingurgh, UK, August 2005. 10. L. Serafini and A. Tamilin. DRAGO: Distributed reasoning architecture for the semantic web. In In Proceedings of the Second European Semantic Web Conference (ESWC’05). Springer-Verlag, 2005. 11. Luciano Serafini, Alex Borgida, and Andrei Tamilin. Aspects of distributed and modular ontology reasoning. In Proceedings of the International Joint Conference on Artificial Intelligence - IJCAI-05, Edinburgh, Scotland, 2005. 12. H. Stuckenschmidt and M. Klein. Integrity and change in modular ontologies.
In Proceedings of the International Joint Conference on Artificial Intelligence IJCAI’03, pages 900–905, Acapulco, Mexico, 2003. Morgan Kaufmann.