State of the art formalisms for distributed ontology integration provide ways to express semantic relations between concepts belonging to different ontologies. However, the extensive usage of multiple distributed ontologies requires the capability for expressing different forms of mappings, which extend the semantic relations between concepts studied so far. In this paper, we propose an extension of the formalism of Distributed Description Logic (DDL) to represent mappings between concepts as well as mappings between relations, and an effective decision procedure for reasoning with multiple ontologies bridged with these mappings.
1 Introduction In the extensive usage of ontologies envisaged by the Semantic Web there is a compelling need for expressing mappings between heterogeneous ontologies. These mappings are of many different forms and involve the different components of ontologies.
Most of the formalisms for distributed ontology integration based on the p2p
architecture, usually called mapping languages [
The first goal of this paper is to study in depth the DDL obtained by considering
homogeneous mappings. We have decided to focus first on homogeneous mappings
because they are a very intuitive and popular form of mappings. The chapter on Ontology
Mappings of the OWL Web Ontology Language Guide [
The second goal of this paper is to define an effective decision procedure to
compute subsumption between classes and roles in ontologies connected by homogeneous
mappings, where the ontologies are expressed in the SHIQ language. This extension
is done in the style of DDL: first we define a bridge operator, which expresses how
subsumption migrates from an ontology O1 to an ontology O2 by means of the mappings,
and then we use this operator to sketch how the distributed tableaux algorithm for DDL
described in [
Role mapping primitives
Before introducing a new primitive, there are a number of questions that need to be
answered. The first and more important question is that of whether such a primitive
is expressible as a combination of already existing primitives, in our case mappings
between concepts. In the following we show that this is not the case and we base our
argument on the semantics of mappings described in [
Given two concepts C and D belonging to two ontologies O1 and O2
respectively, the mapping “C and D are equivalent” is satisfied when the first order formula
∀x(C(x) ≡ D(x)) is satisfied, where C(x) and D(x) are the translation in first
order logic of the concepts C and D, defined as in [
The second question we have to answer is why we provide an expressive mapping
language and a distributed decision procedure instead of encoding mappings as DL
assertions over a unique top global ontology. The main reasons to propose a “distributed”
semantics for DDL, which is based on multiple domains connected via domain relations
(rather than a single domain) concerns the capability of DDL to capture the properties
of localized inconsistency and directionality as shown in [
A language for mappings
Description Logic (DL) has been advocated as the suitable formal tool to represent
and reason about ontologies. Distributed Description Logic [
Given a non empty set I of indexes, used to identify ontologies, let {DLi}i∈I be a collection of description logics1. For each i ∈ I let us denote a T-box of DLi as Ti. In this paper, we assume that each DLi is weaker or at most equivalent to SHIQ.
We call T = {Ti}i∈I a family of T-Boxes indexed by I. Intuitively, Ti is the description logic formalization of the i-th ontology. To make every description distinct, we will prefix it with the index of ontology it belongs to. For instance, the concept C that occurs in the i-th ontology is denoted as i : C. Similarly, i : C ⊑ D denotes the fact that the axiom C ⊑ D is being considered in the i-th ontology.
Semantic mappings between different ontologies are expressed via bridge rules. The bridge rules we consider in this paper are defined as follows: Definition 1 (Bridge rules). A bridge rule from i to j is an expression of the form: ⊒ 1. i : X −→ j : Y (onto-bridge rule)
⊑ 2. i : X −→ j : Y (into-bridge rule) where X and Y are either concepts of DLi and DLj , or roles of DLi and DLj . The ≡ expression i : X −→ j : Y denotes the combination of onto and into bridge rules. Definition 2 (Distributed T-box). A distributed T-box (DTB) T = h{Ti}i∈I , Bi consists of a collection of T-boxes {Ti}i∈I , and a collection of bridge rules B = {Bij }i6=j∈I between them.
In [
Bridge rules from i to j express relations between i and j viewed from the subjective
point of view of the j-th ontology. Bridge rules between concepts have been introduced
1 We assume familiarity with Description Logic and related reasoning systems, described in [
⊒ i : Article −→ j : ConferencePaper expresses the fact that, according to ontology j, the concept Article in ontology i is more general than its local concept ConferencePapers. Bridge rules on roles formalize the analogous intuition for roles. Thus, the bridge rule:
⊑ i : marriedTo −→ j : partnerOf says that according to ontology j, the relation marriedTo in ontology i is less general than its own relation partnerOf.
The semantic of DDL, which is a customization of Local Models Semantics [
Definition 3 (Domain relation). A domain relation rij from ΔIi to ΔIj is a subset of ΔIi × ΔIj . We use rij (d) to denote {d′ ∈ ΔIj | hd, d′i ∈ rij }; for any subset D of ΔIi , we use rij (D) to denote Sd∈D rij (d); for any R ⊆ ΔIi × ΔIi we use rij (R) to denote Shd,d′i∈R rij (d) × rij (d′).
A domain relation rij represents a possible way of mapping the elements of ΔIi into its domain ΔIj , seen from j’s perspective. For instance, if ΔI1 and ΔI2 are the representation of time as Rationals and as Naturals, rij could be the round off function, or some other approximation relation. This function has to be conservative w.r.t., the order relations defined on Rationals and Naturals. Domain relations are used to interpret bridge rules according with the following definition.
Definition 4 (Satisfiability of bridge rules). The domain relation rij satisfies a bridge rule b w.r.t., Ii and Ij , in symbols hIi, rij , Ij i |= b, according with the following: 1. hIi, Ij , rij i
⊑ i : X −→ j : X, if rij (XIi ) ⊆ Y Ij 2. hIi, Ij , rij i
⊒ i : Y −→ j : Y , if rij (XIi ) ⊇ Y Ij where X and Y are either two concept expressions or two role expressions. Definition 5 (Distributed interpretation). A distributed interpretation I = h{Ii}i∈I , {rij }i6=j∈I i of a DTB T consists of local interpretations Ii for each Ti on local domains ΔIi , and families of domain relations rij between local domains. Definition 6 (Satisfiability of a Distributed T-box). A distributed interpretation I satisfies the elements of a DTB T according to the following clauses: for every i, j ∈ I 1. I 2. I 3. I 4. I i : A ⊑ B, if Ii A ⊑ B Ti, if I i : A ⊑ B for all A ⊑ B in Ti Bij , if hIi, rij , Ij i satisfies all the bridge rules in Bij
T, if for every i, j ∈ I, I Ti and I Bij Definition 7 (Distributed Entailment and Satisfiability). T i : C ⊑ D (read as “T entails i : C ⊑ D”) if for every I, I T implies I i : C ⊑ D. T is satisfiable if there exists a I such that I T. Concept i : C is satisfiable with respect to T if there is a I such that I T and CIi 6= ∅. 4
The effects of mappings In the previous section we have defined a declarative language (of mappings) which allows to state set-theoretic relations between the extensions of the concepts and roles in different ontologies (T-boxes). Mappings can be thought of as inter-theory axioms, which constrain the possible models of the theories representing the different ontologies. Thus, a set of mappings between two ontologies allows to combine the knowledge contained in the two ontologies in order to derive new knowledge. In this section we discuss the main effects of mapping in terms of the new ontological knowledge they allow to infer.
We characterize the effect of bridge rules in any distributed T-box, in two steps: first
we characterize the mappings of a simple DTB of the form hT1, T2, B12i, composed
of two T-boxes T1 and T2 and a set of bridge rules B12 from T1 to T2. This allows us
to define an operator B12(.) that encodes the propagation of knowledge provided by
B12. Following [
The first effect of mappings is a general property which allows to identify the
ontologies affected by given mappings. This property states that a mapping from a T-box
T1 to a T-box T2 only affects the target ontology T2:
Proposition 1. hT1, T2, B12i |= 1 : X ⊑ Y if and only if T1 |= X ⊑ Y .
The proof of this property is a trivial generalization of the one contained in [
In addition to this property, the effects of the bridge rules introduced in this paper can be divided in three main classes: (i) Propagation of the concept hierarchy; (ii) Propagation of the role hierarchy and of certain role properties; and (iii) Propagation of the role domain and of the range restriction. In the remaining of the section we describe these three forms of effects in detail. 4.1
Propagation of the concept hierarchy
The propagation of the concept hierarchy is forced by mappings between concepts and
is widely described in [
Propagation of the role hierarchy and of role properties The first effect of mappings between roles concern the propagation of the role hierarchy. Let us start with an example: Suppose that ontology O1 contains the role axioms IsTheBossOf ≡ HasBoss− IsTheBossOf ⊑ WorksWith
WorksWith ≡ WorksWith− Suppose also that ontology O2 contains the role IsSecretaryOf, representing the relation between the secretary and his/her boss, and the role KnowsTheNameOf representing the relations between two persons where the first knows the name of the second. Assume now that the roles of O1 and O2 are connected by the following mappings (1) (2) (3) (4) (5) ⊒ O1 : HasBoss −→ O2 : IsTheSecretaryOf
⊑
O1 : WorkWith −→ O2 : KnowsTheNameOf In this scenario we expect to be able to infer in O2 the axiom IsTheSecretaryOf ⊑ KnowsTheNameOf about the role hierarchy. In fact, if x is the secretary of y, then by mapping (4) y is the boss of x. Using the role hierarchy in O1, and in particular the fact (2), x works with y, which means that x knows the name of y because of mapping (5).
More in general, we can say that if R ⊑ S is a fact of the T-box T1, then the effect of ⊒ ⊑ the bridge rules R : 1 −→ T : 2 and S : 1 −→ U : 2 is that T ⊑ U and T − ⊑ U − are also facts in T2. Formally, we describe this effect by means of the following operator: T1 |= R ⊑ S, R12(T1) = T (−) ⊑ U (−) 1 : R −⊒→ 2 : T ∈ B12,
1 : S −⊑→ 2 : U ∈ B12 where each R, T and S, U is either a role or an inverse role, and the notation T (−) ⊑ U (−) denotes either T ⊑ U or T − ⊑ U −.
Additional effects of mappings between roles concern the propagation of the properties of relations across different ontologies. Let us consider first the property of symme⊑ try. If R is a symmetric relation and Symm(R) ∈ T1, then the mappings 1 : R −→ 2 : S ⊒ and 1 : R −→ 2 : S force S also to be a symmetric relation in T2. This effect is already described by the operator R12 defined above. In fact Symm(R) is equivalent to R ⊑ R−, and using R12 with the two bridge rules between R and S above, one can infer S ⊑ S− which states the symmetry of S in T2. If R is a transitive relation in T1, ⊑ ⊒ then the mappings 1 : R −→ 2 : S and 1 : R −→ 2 : S alone do not force S to be transitive in T2, and additional constraints are needed to enforce it. Since the propagation of transitivity seems a very intuitive requirement we are considering appropriate restrictions of the domain relation in order to obtain it from the bridge rules above. Finally, note that if the languages of T1 and T2 support the role union operator, then we obtain an extra propagation effect which is the analogous of the general concept propagation ⊒ rule. Suppose that T1 |= R ⊑ S1 ⊔ · · · ⊔ Sn, then the mappings 1 : R −→ 2 : T and ⊑ 1 : Sk −→ 2 : Uk for 1 ≤ k ≤ n impose that T ⊑ U1 ⊔ · · · ⊔ Un holds in T2. 4.3
Propagation of the role domain and of the range restriction The simplest effect of the combination of mappings between roles and mappings between concepts is the propagation of domain and range restriction. Again, consider an example obtained by extending the scenario presented above with the axiom in ontology O1 and the following mapping between concepts to the set of mappings: ∃HasBoss.⊤ ⊑ Subaltern
⊑
O1 : Subaltern −→ O2 : Employee In this case we expect that the subsumption ∃IsTheSecretaryOf−.⊤ ⊑ Employee holds in O2. Indeed, if x is the secretary of y, then by mapping (4) y is the boss of x, and by axiom (6) x is a subaltern. Thus, mapping (7) tells us that x is an employee.
More in general, if we assume that Domain(R) ⊑ C (resp. Range(R) ⊑ C) is a ⊒ ⊑ fact in T1, then the mappings 1 : R −→ 2 : S and 1 : C −→ 2 : D force Domain(S) ⊑ D (resp. Range(S) ⊑ D) in T2. The formalization of this effect is described by the operator CR12:
8>>> ˛˛˛T1 |= ∃R(−). `¬ Fph=1 Ah´ ⊑ `Fkm=1 Bk´, CR12(T1) = <>∃S(−). `¬ Fph=1 Gh´ ⊑ `Fkm=1 Hk´ ˛˛˛˛˛11 :: ARh−⊒−→⊑→22: S:G∈hB∈1B2, 12, for 1 ≤ h ≤ p > > :>> ˛˛1 : Bk −⊑→ 2 : Hk ∈ B12, for 1 ≤ k ≤ m 9 > > > > = > > > > ; where Ah, Gh, Bk and Hk are concepts, and R and S are roles or inverse roles. As before the notation R(−) and S(−) stands for either R and S, or their inverse.
Notice that, range and domain propagation is a special case of the propagation formalized by CR12. Indeed Domain(R) ⊑ C, corresponds to the axiom ∃R.⊤ ⊑ C. By (6) (7) ⊑ considering p = 0, n = 1, H1 = C, and the mapping 1 : C −→ 2 : D we can obtain ∃S.⊤ ⊑ D from ∃R.⊤ ⊑ C. 2 Similarly, the statement Range(R) ⊑ C is equivalent to the axioms ∃R− ⊑ C and it is translated into ∃S− ⊑ D by the CR12 operator. 4.4
Soundness and completeness
In this section we extend the proof given in [
Given a set of bridge rules B12 from DL1 to DL2, the operator B12(·), taking as input a T-box in DL1 and producing a T-box in DL2, is defined as B12(·) = C12(·) ∪ R12(·) ∪ CR12(·) Theorem 1. Let T12 = hT1, T2, B12i be a distributed T-box. where T1 and T2 are expressed in SHIQ descriptive language. Then:
T12 |= 2 : X ⊑ Y ⇐⇒ T2 ∪ B12(T1) |= X ⊑ Y (8) Proof (of Theorem 1). As far as the soundness, it is enough to prove that if I |= T = hT1, T2, B12i, then I2 |= B12(T1). Suppose that G ⊑ H1 ⊔ · · · ⊔ Hn ∈ C12, then there ⊒ ⊑ is a mapping 1 : A −→ 2 : G, and n mappings 1 : Bk −→ 2 : Hk. If x ∈ GI2 , then by satisfiability of the onto-mapping there is y ∈ AI1 with (y, x) ∈ r12. The fact T1 |= A ⊑ B1 ⊔ · · · ⊔ Bn, implies that y ∈ BI1 for some k, and by the intok mapping, x ∈ Hk, and therefore in H1 ⊔ · · · ⊔ Hn. Analogous reasoning can be done for proving the soundness of R12(T1). Finally, suppose that ∃S.¬G ⊑ H ∈ CR12 with G = ⊔ph=1Gk and H = ⊔km=1Hk. If x ∈ (∃S.¬G)I2 , then there is an x′ such that (x, x′) ∈ SI2 , and by the onto-mapping, (y, y′) ∈ RI1 for with (y, x), (y′, x′) ∈ r12. By the into mappings we have that y 6∈ AI1 , and since T1 |= ∃R.¬A ⊑ B, we have that y′ ∈ BI1 . This implies that x′ ∈ HI2 .
To prove completeness, the contrapositive is proved. If T2 ∪ B12(T1) 6|= X ⊑ Y then there exists a distributed interpretation I such that T12 6|= 2 : X ⊑ Y .
Let I2 be an interpretation of T2 ∪ B12(T1) such that I2 6|= X ⊑ Y . The rest of the proof is devoted to the construction of an interpretation I1 and a domain relation r12 such that hI1, I2, r12i is a distributed interpretation I such that I |= T12 and I 6|= 2 : X ⊑ Y . ⊒
Let β be a concept-onto-concept bridge rule of the form 1 : A −→ 2 : G. Starting
from I2 and β, we define an interpretation Iβ, and a domain relation rβ as follows: for
0
2 ¬ Fh=1 Gh is equivalent to ¬⊥ which is equivalent to ⊤
3 The concept of disjoint union of (distributed) interpretations used in the proofs is introduced
and studied in [
T-boxes I2 |= T2 by definition, I1 |= T1, as each Iβd and Iβ(d,d′) models T1.
⊒ Onto-bridge rules Let β′ = 1 : X −→ 2 : Y be some onto-rule. By construction, there is interpretation Iβ′ such that rβ′ (XIβ′ ) ⊇ Y I2 . Since AI1 = Uβ AIβ , and r12(AI1 ) contains Uβ (rβ (AIβ )) by construction, we have the desired result.
] 1 : A −⊒→d∈2G:IG2 ∈ B12
Id
1:A−⊒→2:G ] 1 : A −⊒→d∈2G:IG2 ∈ B12 rd 1:A−⊒→2:G
I(d,d′)
1:R−⊒→2:S
r(d,d′)
1:R−⊒→2:S
1 : R −⊒→ S : G ∈ B12
(d, d′) ∈SI2
]
]
1 : R −⊒→ S : G ∈ B12
(d, d′) ∈SI2
In this section we use the previous theoretical results to define a tableaux-based decision
procedure for T |= i : X ⊑ Y , for the case of simple distributed T-boxes of the
form hT1, T2, B12i. The generalization to the case of general acyclic DTBs is similar
to the one presented in [
We follow the approach proposed in [
Definition 8. The function DTab2 takes as input a concept X and tries to build a
representation of I2 with XI2 6= ∅ (called a completion tree [
The idea of these rules is inspired by the corresponding operators introduced in
Section 4.4. Rule Unsat-C12 corresponds to the operator C12(·), and was first introduced in
[
Rule Unsat-R12 corresponds to the operator R12(·). The idea behind this rule is that whenever DTab2 encounters a node x with a T -neighbour y, and T is a consequence ⊒ of a role-onto-role bridge rule 1 : R −→ 2 : T , then if T ⊑ U is entailed by the bridge rules, y is also a U -neighbour of x. To determine if T ⊑ U is entailed by the bridge rules R12, we simply check if S ⊑ R belongs to the role hierarchy of T1 for all 5 Non atomic mappings can easily be modeled by introducing names for the complex concepts.
⊒ if 1. G ∈ L(x), 1 : A −→ 2 : G ∈ B12, and
2. IsSat1(A ⊓ ¬ F B′) = False, for some H′ 6⊆ L(x), then L(x) −→ L(x) ∪ {F H′} New-C12-rule
⊒ if 1. G ∈ L(x), 1 : A −→ 2 : G ∈ B12, and
⊑ 2. B ⊆ {B|1 : B −→ 2 : H ∈ B12}, and 3. for no B′ ⊆ B is IsSat1(A ⊓ ¬ F B′) = False, and 4. for no B′ ⊇ B is IsSat1(A ⊓ ¬ F B′) = True , then if DTab1(A ⊓ ¬ F B) = Satisfiable then IsSat1(A ⊓ ¬ F B) = True else IsSat1(A ⊓ ¬ F B) = False
Rule Unsat-CR12 corresponds to the operator CR12(·). The idea behind this rule is that whenever DTab2 encounters a node x with a S-neighbour y, and S is a consequence ⊒ of a role-onto-role bridge rule 1 : R −→ 2 : S, then if y contains a label ¬Gi which is a consequence of a concept-into-concept bridge rule, then if ∃S.¬G ⊑ H is entailed by the bridge rules, the label H , is added to x. To determine if ∃S.G ⊑ H is entailed by the bridge rules B12, DTab2 invokes DTab1 on the satisfiability of the concept ∃R.¬A ⊓ ¬B. DTab1 will build (independently from DTab2) an interpretation I1, in a manner similar to the construction illustrated in Figure 2.
To avoid redundant calls, DTab2 caches the calls to DTab1 in a data structure IsSat1, which caches the subsumption propagations that have been computed so far. Theorem 2 (Termination,Soundness, and completeness). DTab2(X) terminates, and 2 : X is satisfiable in T12 if and only if DTab2(X) can generate a complete and clashfree completion tree.
Example 1. To clarify how the distributed tableaux works let us consider the DTBox T12 = hT1, T2, B12i where T1 contains the axioms ∃R.¬A1 ⊑ B1 and ∃R.¬A2 ⊑ B2, T2 does not contain any axiom, and B12 contains the following bridge rules: ⊒ 1 : R −→ 2 : S
⊑ 1 : A1 −→ 2 : G1
⊑ 1 : A2 −→ 2 : G2 (9) (10) (11)
⊑ 1 : B1 −→ 2 : H1
⊑ 1 : B2 −→ 2 : H2 (12) (13)
Let us show that T12 |=d 2 : ∃S.¬(G1 ⊔G2) ⊑ H1 ⊓H2, i.e. that for any distributed interpretation I = hI1, I2, r12i, (∃S.¬(G1 ⊔ G2))I2 ⊆ (H1 ⊓ H2)I2 . 1. Suppose that by contradiction there is an x ∈ Δ2 such that x ∈ (∃S.¬(G1 ⊔ G2))I2 and x 6∈ (H1 ⊓ H2)I2 . 2. Then there exists a y such that hx, yi ∈ SI2 and y 6∈ G1I2 , y 6∈ G2I2 , and either x 6∈ HI2 or x 6∈ H2I2 .
1 3. Because of the bridge rule (9) there is a pair hx′, y′i ∈ Δ1 such that hr12(x′), r12(y′)i = hx, yi and hx′, y′i ∈ RI1 . 4. Let us consider the case where x 6∈ H1I2 . From the fact that y 6∈ G1I2 , then by the bridge rule (10), y′ 6∈ A1I1 . 5. Since ∃R.¬A1 ⊑ B1 is an axiom of T1, then y′ ∈ B1I1 , and by bridge rule (12) y ∈ H1I1 . But this is a contradiction. 6. The case where x 6∈ H2I2 is analogous and we can conclude that T12 |=d 2 : ∃S.¬(G1 ⊔ G2) ⊑ H1 ⊓ H2.
The above reasoning can be seen as a combination of a tableau in T2 with a tableau in T1. In Figure 2 we depict the construction of a tableau for T2 where dotted arrow lines represent the evolution of the tree while solid lines represent connections between neighbouring nodes. For the sake of space we depict only the tableau Tab1(¬B1 ⊓ ∃R.¬A1). The tableau Tab1(¬B2 ⊓ ∃R.¬A2) is analogous. 6
Related Work
The semantics of mappings proposed in this paper is in line with the semantic of
mappings between relations proposed by Calvanese et al. in [
Role mappings can be encoded also in a unique top global ontology. To encode the semantics of role-mappings with heterogeneous domain, one needs to index each concept and role with the T-box it comes from, add concepts for local domains, and introduce a role R12 representing the domain relation from T-box 1 to T-box 2. The into⊑ mapping 1 : R −→ 2 : S can be encoded with the role-axioms R1−2 ◦ R1 ◦ R12 ⊑ S2. CLASH by applying bridge CLASH by applying bridge rules (9), (10) and (12) rules (9), (11) and (13) and tableau Tab1(¬B1 ⊓ and tableau Tab1(¬B2 ⊓ ∃R.¬A1) ∃R.¬A2) 1 : x′ ¬B1, ∃R.¬A1, ∀R.A1 1 : x′ ¬B1, ∃R.¬A1, B1
CLASH B121 : x′ ¬B1
R 1 : y′ ¬A1, A1
CLASH
⊒ Similarly the onto mapping 1 : R −→ 2 : S is encoded with S2 ⊑ R1−2 ◦ R1 ◦ R12. The main drawback of this translation is that it is based on role composition, which in the general case is undecidable.
The formalism of E -connections, proposed by Wolter et. al in, e.g., [
In comparing the formal setting described in this paper with ontology matching
system such as Ontology Mapping Tool OMEN [