<figure><img src="image_1.png" /></figure>

HAL
open science

# Reasoning Theory for D3L with Compositional Bridge Rules

Xiaofei Zhao, Dongping Tian, Limin Chen, Zhongzhi Shi

► To cite this version:

Xiaofei Zhao, Dongping Tian, Limin Chen, Zhongzhi Shi. Reasoning Theory for D3L with Compositional Bridge Rules. 7th International Conference on Intelligent Information Processing (IIP), Oct 2012, Guilin, China. pp.106-115, 10.1007/978-3-642-32891-6_15. hal-01524961

HAL Id: hal-01524961

https://inria.hal.science/hal-01524961

Submitted on 19 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Reasoning Theory for D3L with Compositional Bridge Rules

Zhao Xiaofei¹, Tian Dongping¹, Chen Limin², and Shi Zhongzhi¹

¹ Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
zhaoxf@ics.ict.ac.cn
² Research Institute of China Unicom, Beijing, China

**Abstract.** The semantic mapping in Distributed Dynamic Description Logics(D3L) allows knowledge to propagate from one ontology to another. The current research for knowledge propagation in D3L is only for a simplified case when only two ontologies are involved. In this paper we study knowledge propagation in more complex cases. We find in the case when more than two ontologies are involved and bridge rules form chains, knowledge does not always propagate along chains of bridge rules even if we would expect it. Inspired by Package-based description Logics, we extend the original semantics of D3L by imposing so called compositional consistency condition on domain relations in D3L interpretations. Under this semantics knowledge propagates along chains of bridge rules correctly. Furthermore we provide a distributed Tableaux reasoning algorithm for deciding satisfiability of concepts which is decidable in D3L under compositional consistency. Compared with original one, the extended D3L provides more reasonable logic foundation for distributed, dynamic system such as the information integration system and the Semantic Web.

**Keywords.** Distributed Dynamic Description Logics(D3L), Knowledge Propagation, Compositional Consistency, Bridge Rule Chain

# 1 Introduction

As the distributed extension of traditional dynamic description logics(DDL)[1][2], distributed dynamic description logics(D3L)[3][4] enables reasoning with multiple heterogeneous DDL ontologies interconnected by directional semantic mapping. D3L captures the idea of importing and reusing knowledge between several ontologies. This idea combines well with the basic assumption of the distributed and dynamic system such as the Semantic Web and the heterogeneous information integration system.

An important innovation of D3L is to describe the semantic mapping between heterogeneous ontologies through bridge rules[3]. Bridge rules can assert that the concept/relation/action, local to ontology $T_1$, is mapped to an independent ontology $T_2$ as a subconcept/relation/action or superconcept/relation/action. Bridge rules are
directed, and hence if there is a bridge rule with direction from $T_1$ to $T_2$, then $T_2$ reuses knowledge from $T_1$ but not necessarily the other way around. Bridge rules lead to the important characteristic--knowledge dissemination which makes D3L different from DDL. Knowledge propagation theory of D3L has been studied in our early work, but only for a simplified case when only two DDL ontologies are involved and bridge rules doesn't construct chain. Because D3L is presented primarily as the logical foundation for complex distributed dynamic ontology, the research for knowledge propagation in more complex cases has important theoretical value and practical value.

In this paper we study subsumption propagation theory in more complex cases, when bridge rules in multiple DDL ontologies construct chains. We discover that original semantics of D3L can't assure knowledge propagate correctly in that situations even if we would expect it. Inspired by Package-based description Logics, we extend the original semantics of D3L by imposing so called compositional consistency condition on domain relations in D3L interpretations. Under this semantics knowledge propagates along chains of bridge rules correctly. Then we study the general laws of knowledge propagation under the new semantics. At last, we study the decidability for reasoning satisfiability of concepts in D3L under compositional consistency and provide a distributed Tableaux reasoning algorithm for deciding it. The algorithm can reason with acyclic D3L knowledge bases build on top of D-ALC as the local language.

## 2 Demonstrations of the Problem

By two examples, this section will illustrate the problem which occurs in D3L knowledge propagation in the case of bridge rule chains exist.

**Example 1.** In DDL ontology $T_1$ there are action *BuyVehicle* and its subaction *BuyCar*. There is also another DDL ontology $T_2$ with action *Buy* and *BuyFord*. An into-action bridge rule maps from *BuyVehicle* to *Buy* and states that *BuyVehicle* is a subaction of *Buy*. An onto-action bridge rule maps from *BuyCar* to *BuyFord* and states that *BuyCar* is a superaction of *BuyFord*. Thanks to action subsumption propagation theorem[4], the knowledge that *BuyCar* is a subaction of *BuyVehicle* propagates to $T_2$ and we infer that *BuyFord* is a subaction of *Buy* and other inferences such as action realizability.

Consider a change in the situation, $T_1$ is divided into $T_1$ and $T_1'$, as depicted in Figure 1, $T_1'$ contains *BuyCar*, and there is an into-action bridge rule from $T_1'$ to $T_1$ stating that *BuyCar* is a subaction of *BuyVehicle*. Actions in $T_2$ are unchanged, but the two bridge rules now map, first: from $T_1$ to $T_2$ asserting *BuyVehicle* a subaction of *Buy*, and second from $T_1'$ to $T_2$: asserting *BuyCar* a superaction of *BuyFord*. In D3L we no longer infer that *BuyFord* is a subaction of *Buy*.
<figure><img src="image_3.png" /><figcaption>Fig. 1. Depiction of distributed ontologies in example 1</figcaption></figure>

*Example 2.* There are three DDL ontologies *T*<sub>1</sub>, *T*<sub>2</sub>, *T*<sub>3</sub> in D3L knowledge base, as depicted in Figure 2(a), by applying concept subsumption propagation theorem repeatedly we can infer that *MyMastiff* is a kind of *DangerousAnimal*. This situation can be extended to another one where there are many similar intermediate ontologies as *T*<sub>2</sub> between *T*<sub>1</sub> and *T*<sub>3</sub>. In such cases knowledge can be correctly propagated along bridge rule chains. However, the restriction condition in above cases is too strict, if conditions are violated, *Carnivore* and *HouseDog* are located in different ontology, as depicted in Figure 2(b), we can't infer that *MyMastiff* is a subconcept of *DangerousAnimal* although the superconcept-subconcept relation between *Canidae* and *Canis* should be propegated to *Carnivore* and *HouseDog*, and then to *DangerousAnimal* and *MyMastiff* again.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Depiction of distributed ontologies in example 2</figcaption></figure>

From above two examples we can see, the traditional semantics of D3L does not
guarantee the knowledge that we hope to import into the target ontology spreads
along the bridge rule chains correctly. In section 4, we will give a detailed analysis of
the reasons, and extend D3L to solve this problem.

3 Distributed Dynamic Description Logics

A basic form of D3L knowledge base dubbed *Tbox*, includes a set of local *Tboxes* each over its own DDL language and a set of bridge rules that provides mappings between local *Tboxes*. In this work, we use the formal definition as follows.
**Definition 1.** Assume a DDL language DDL<sub>X</sub>, a non-empty index set *I*, a set of concept names *N*<sub>C</sub>=*U*<sub>i∈I</sub>*N*<sub>Ci</sub>, a set of relation names *N*<sub>R</sub>=*U*<sub>i∈I</sub>*N*<sub>Ri</sub> and a set of action names *N*<sub>A</sub>=*U*<sub>i∈I</sub>*N*<sub>Ai</sub>. A Distributed Tbox over DDL<sub>X</sub> is a pair <{*T*<sub>i</sub>}*<sub>i∈I</sub>, BR> such that: each local Tbox *T*<sub>i</sub> is a collection of general inclusions over *N*<sub>Ci</sub>, *N*<sub>Ri</sub> and *N*<sub>Ai</sub> in the local language of *T*<sub>i</sub>, a sub-language of DDL<sub>X</sub>; the set of bridge rules BR divides into sets of bridge rules BR=<{*U*<sub>i</sub>, *j*∈I, *i*≠*j*><BR>BR<sub>ij</sub>. Each BR<sub>ij</sub> is a collection of bridge rules in direction from *T*<sub>i</sub> to *T*<sub>j</sub> which are of four forms:

i: $C \stackrel{\sqsubseteq}{\rightarrow} j: E$ (into-concept (relation) bridge rule);

i: $C \stackrel{\sqsupset}{\rightarrow} j: E$ (onto- concept (relation) bridge rule);

i: $\alpha \stackrel{\sqsubseteq}{\rightarrow} j: \beta$ (into-action bridge rule);

i: $\alpha \stackrel{\sqsupset}{\rightarrow} j: \beta$ (onto-action bridge rule).

As we have already mentioned in the introduction, the direction of bridge rules matters and hence $B_{ij}$ and $B_{ji}$ are possibly and expectedly distinct. The bridge graph $G_{DTB} = \langle V, E \rangle$ of a distributed Tbox DTB is defined as follows: $V=I$ and $\langle i, j \rangle \in E$ if $BR_{ij} \neq \emptyset$. We say that DTB is acyclic if $G_{DTB}$ is acyclic.

Given a Tbox *T*, a hole is an interpretation *I*<sup>*ε*</sup> = <*Ø*<sub>*</sub>, •*ε*<sub>*</sub>\> with empty domain.
Holes are used for fighting propagation of inconsistency. A distributed interpretation
DI = <{*I*<sub>*i*</sub>}*<sub>*i*∈I</sub>, {*r*<sub>*ij*</sub>}<sub>*i*, *j*∈I, *i*≠*j*</sub>\> of a distributed Tbox DTB consists of a set of local
interpretations {*I*<sub>*i*</sub>}<sub>*i*∈I</sub> and a set of domain relations {*r*<sub>*ij*</sub>}<sub>*i*, *j*∈I, *i*≠*j*</sub>. For each *i*∈I, either
*I*<sub>*i*</sub> = (*Δ*<sup>*li*</sup>, •*li*) is an interpretation of local Tbox or *I*<sub>*i*</sub> = *I*<sup>*ε*</sup> is a hole. Each domain
relation *r*<sub>*ij*</sub> is a subset of *Δ*<sup>*li*</sup>×*Δ*<sup>*li*</sup>. We denote by *r*<sub>*ij*</sub> (*d*) the set {*d'*|<*d*, *d*'∈*r*<sub>*ij*</sub>} and by *r*<sub>*ij*</sub> (*D*) the set *U*<sub>*d*∈D</sub> *r*<sub>*ij*</sub> (*d*).

**Definition 2.** For every *i*, *j*∈I, a distributed interpretation DI satisfies the elements of a distributed Tbox DTB (denoted by DI|=<sub>d</sub>●) according to the following clauses:

1. DI|=<sub>d</sub> i: C --[E]--> j: E if r<sub>ij</sub> (C<sup>li</sup>)subseteqE<sup>li</sup>;

2. DI|=<sub>d</sub> i: C --[D]--> j: E if r<sub>ij</sub> (C<sup>li</sup>) ⊇E<sup>li</sup>;

3. DI|=<sub>d</sub> i: α --[E]--> j: β if r<sub>ij</sub> (α<sup>li</sup>) ⊆ β<sup>li</sup>;

4. DI|=<sub>d</sub> i: α --[D]--> j: β if r<sub>ij</sub> (α<sup>li</sup>) ⊇ β<sup>li</sup>;

5. DI|=<sub>d</sub> i: C ⊆ E if I<sub>i</sub> = C ⊆ E;

6. DI|=<sub>d</sub> i: α ⊆ β if I<sub>i</sub>=α ⊆ β;

7. DI|=<sub>d</sub> T<sub>i</sub> if I<sub>i</sub>=T<sub>i</sub>;

8. DI|=<sub>d</sub> BR if DI|=<sub>d</sub> br for every br∈BR;

9. DI|=<sub>d</sub> DTB if DI|=<sub>d</sub> T<sub>i</sub> and DI|=<sub>d</sub> BR for every i∈I;

10. DTB|=<sub>d</sub> i: C ⊆ E if DI|=<sub>d</sub> DTB implies DI|=<sub>d</sub> i: C ⊆ E for every DI;

11. DTB|=<sub>d</sub> i: α ⊆ β if DI|=<sub>d</sub> DTB implies DI|=<sub>d</sub> i: α ⊆ β for every DI.
If $DI \models_d DTB$ then we say that $DI$ is a distributed model of $DTB$.

Among the properties of D3L we find the characterization of subsumption propagation, which formally describes the mechanism of knowledge reuse of D3L. Theorem 1 constitutes the most basic version of this property: thanks to a pair of one into-bridge rule and one onto-bridge rule local subsumption relationship is propagated from the source ontology of these bridge rules to the target ontology.

**Theorem 1.** In each distributed Tbox DTB, if $i: C \mathrel{\substack{
\overline{=} \\ \underline{=} }} j: G \in BR$ and $i: D \mathrel{\substack{
\overline{=} \\ \underline{=} }} j: H \in BR$, then the following holds: $DTB \models_d i: C \subseteq D \Rightarrow DTB \models_d j: G \subseteq H$; if $i: \alpha \mathrel{\substack{
\overline{=} \\ \underline{=} }} j: \beta \in BR$ and $i: \pi \mathrel{\substack{
\overline{=} \\ \underline{=} }} j: \rho \in BR$, then the following holds: $DTB \models_d i: \alpha \subseteq \pi \Rightarrow DTB \models_d j: \beta \subseteq \rho$. (Subsumption propagation theorem)

Theorem 1 states subsumption propagation property, one of the D3L properties. So far subsumption propagation laws in more complex cases have been studied. However all these cases do not extend the case captured by Theorem 1 in that aspect that only two local DDL ontologies that are directly connected with bridge rules are studied. The reader is kindly redirected to reference [4] for all details and discussion.

# 4 Knowledge Propagation in D3L under Compositional Consistency

Why does not the knowledge propagate along bridge rule chains as we would expect in the examples shown in section 2? In the following we will give the detailed analysis from semantic perspective. There are three bridge rules in Example 1: $1'$: $BuyCar \mathrel{\substack{
\overline{=} \\ \underline{=} }} 2: BuyFord \in BR$, $1: BuyVehicle \mathrel{\substack{
\overline{=} \\ \underline{=} }} 2: Buy \in Br$ and $1'$: $BuyCar \mathrel{\substack{
\overline{=} \\ \underline{=} }} 1: BuyVehicle \in BR$. Given a model of DTB, we get some semantic constraints within $\Delta^{I2}$, particularly $BuyFord^{I2} \subseteq r_{1'2} (BuyCar^{II'})$ and $r_{12} (BuyVehicle^{II}) \subseteq Buy^{I2}$ thanks to two of the bridge rules. However, the third bridge rule does not help anyhow to establish relation between $r_{1'2} (BuyCar^{II'})$ and $r_{12} (BuyVehicle^{II})$. In Example 2, in each distributed model DI of DTB the interpretations of the two concepts "on the way"-- HouseDog$^{I2}$ and Carnivore$^{I2}$ --are totally unrelated. By composition of the bridge rules that are available here we derive the inclusions: $MyMastill^{I3} \subseteq r_{2'3} (HouseDog^{I2'}) \subseteq r_{2'3} (r_{12'} (Canis^{II}))$ and $r_{23} (r_{12} (Canidae^{II})) \subseteq r_{23} (Carnivore^{I2}) \subseteq DangerousAnimal^{I3}$. However $r_{2'3} (r_{12'} (Canis^{II}))$ and $r_{23} (r_{12} (Canidae^{II}))$ are not related in $\Delta^{I3}$, it does not help that $Canis^{II} \subseteq Canidae^{II}$ in $\Delta^{II}$.

From above analysis we can see the main reason why the subsumption does not always propagate to remote ontologies in more complex cases as we would intuitively expect is all the semantic constraints generated by remote bridge rules do not propagate to remote parts of the system. In Package-based Description Logics(P-DL)[5][8], so called compositional consistency semantics is imposed on the importing relation in a distributed ontology environment so that knowledge can be propagated
along importing relation chains uninterruptedly. The problem in our work is similar to
that in P-DL. Inspired by this, we apply compositional consistency semantics on the
D3L framework to try to solve the problem.

**Definition 3.** Given a distributed interpretation DI, we say that domain relation $r$ (and also DI) satisfies compositional consistency if for each $i, j, k \in I$ and for each $x \in \Delta^{li}$ with $r_{ij}(x) = d$ we have $r_{jk}(d) = r_{ik}(x)$.

We say that D3L is under compositional consistency if only domain relations that satisfy the compositional consistency condition are allowed in distributed interpretations. We denote by D3L<sub>ccy</sub> D3L under compositional consistency. Accordingly, D3L under original semantics is denoted by D3L<sub>(orl)</sub>.

Let us now reconsider what happens in the examples shown in section 2 if the compositional consistency semantics is enforced. In Example 2, by composition of the bridge rules that are available in the example we derive the inclusions: $MyMastill^1 \subseteq r_{2'3} (HouseDog^{12'}) \subseteq r_{2'3} (r_{12'} (Canis^{II}))$ and $r_{23} (r_{12} (Canidae^{II})) \subseteq r_{23} (Carnivore^{12}) \subseteq DangerousAnimal^3$. Compositional consistency implies $r_{2'3} (r_{12'} (Canis^{II})) = r_{13} (Canis^{II})$ and $r_{13} (Canidae^{II}) = r_{23} (r_{12} (Canidae^{II}))$. Finally, since $DTB \models_d I$: Canis $\subseteq$ Canidae we are now able to derive $r_{13} (Canis^{II}) \subseteq r_{13} (Canidae^{II})$ and $MyMastill^3 \subseteq DangerousAnimal^3$, and hence we can derive that *MyMastill* is a kind of *DangerousAnimal* according to Definition 2. Similar case also occurs in Example 1, due to space limitations we omit the discussion for it. From above analysis we can see the problem of subsumption propagation between ontologies which are connected indirectly can be solved by our extension. In the following we will give a in-depth theoretical analysis and provement for our extension.

**Theorem 2.** Given a distributed Tbox DTB and a subsumption formula $\phi$, if $DTB \models_d \phi$ in D3L<sub>(orl)</sub>, then $DTB \models_d \phi$ also holds in D3L<sub>ccy</sub> , i.e. the subsumption propagation property is satisfied in D3L<sub>(ccy)</sub>.

*Proof.* This follows from the fact that each model that satisfies compositional consistency is also a model in the original D3L semantics. If a formula $\phi$ is satisfied in each model from the set of models of DTB according to the original semantics, it is also satisfied by each model from its subset--the set of models of DTB that we obtain under compositional consistency. Hence we can derive that if $DTB \models_d \phi$ in D3L<sub>(orl)</sub>, then $DTB \models_d \phi$ also holds in D3L<sub>(ccy)</sub>. $\square$

Subsumption relations that can be propagated in D3L<sub>(orl)</sub> can also be propagated in D3L<sub>ccy</sub>. The only difference is that in the adjusted semantics possibly some more subsumption relations which can not be propagated along bridge rule chains in the former can be propagated correctly in addition, thus Theorem 1 must be extended for D3L<sub>(ccy)</sub>. Theorem 3 gives the general form of subsumption propagation in D3L<sub>(ccy)</sub> (take action subsumption for example):

**Theorem 3.** Given a distributed Tbox DTB=<{T<sub>0</sub>, T<sub>1</sub>, ..., T<sub>n</sub>}, BR>, action $\pi$, $\rho \in T_0$, $\alpha_i, \beta_i \in T_i$, $1 \le i \le n$, $1 \le k \le n$ such that
1. $DTB \models_i \alpha_i \subseteq \beta_i$, $1 \le i \le n$,

2. $i+1: \alpha_{i+1} \stackrel{\sqsupset}{\longrightarrow} i: \beta_i \in BR$, $1 \le i < k$,

3. $i: \beta_i \stackrel{\sqsubseteq}{\longrightarrow} i+1: \alpha_{i+1} \in BR$, $k \le i < n$,

4. $1: \alpha_1 \stackrel{\sqsupset}{\longrightarrow} 0: \pi \in BR$ and $n: \beta_n \stackrel{\sqsubseteq}{\longrightarrow} 0: \rho \in BR$.

In D3L<sub>ccy</sub> it follows that $DTB \models_d \emptyset: \pi \subseteq \rho$.

*Proof.* The chain of bridge rules $i+1: \alpha_{i+1} \stackrel{\sqsupset}{\longrightarrow} i: \beta_i \in BR$, $1 \le i < k$ together with the local subsumptions in $T_1, T_2, T_3, \dots, T_k$ in the assumptions allows us to relate $r_{10} (\alpha_1^{II}) \subseteq r_{10} (r_{21} (\dots r_{k k-1} (\alpha_k^{Ik}) \dots))$. From compositional consistency we derive $r_{10} (r_{21} (\dots r_{k k-1} (\alpha_k^{Ik}) \dots)) = r_{k 0} (\alpha_k^{Ik})$. For the other chain of bridge rules alike. Now it is easy to see that $\pi^{I0} \subseteq r_{10} (\alpha_1^{II}) \subseteq r_{k 0} (\alpha_k^{Ik}) \subseteq r_{k 0} (\beta_k^{Ik}) \subseteq r_{10} (\beta_1^{II}) \subseteq \rho^{I0}$, hence we can derive $DTB \models_d \emptyset: \pi \subseteq \rho$. $\square$

Extending Theorem 3 to the case of concept (relation) bridge rule chains, similarly we can draw concept (relation) subsumption propagation theorem, due to space limitations we omit the discussion for it.

# 5 Distributed Tableaux Algorithm for D3L<sub>ccy</sub>

In this section, we introduce a distributed Tableaux algorithm for deciding satisfiability of concepts with respect to an acyclic distributed Tbox for D3L<sub>ccy</sub> over D-ALC. We use the formal definition as follows:

**Definition 4.** Assume a distributed Tbox $DTB = \{T_i\}_{i \in I}, BR\rangle$ over D-ALC with index set $I$, concept names $N_C = \cup_{i \in I} N_{ci}$, relation names $N_R = \cup_{i \in I} N_{Ri}$ and action names $N_A = \cup_{i \in I} N_{Ai}$. Let $CC_i$ be the set of all (atomic and complex) concepts over $N_{ci}$, $N_{Ri}$ and $N_{Ai}$ in negation normal form. A distributed completion tree $T = \{T_i\}_{i \in I}$ is a set of labeled trees $Ti = \langle V_i, E_i, L_i, r_i \rangle$, such that for each $i \in I$:

1. the members of $\{V_i\}_{i \in I}$ are mutually disjoint;

2. the members of $\{E_i\}_{i \in I}$ are mutually disjoint;

3. the labeling function $L_i$ labels each node $x \in V_i$ with $L(x) \subseteq 2^{CC_i}$ and each edge $\langle x, y \rangle \in E_i$ with $L(\langle x, y \rangle) \in N_{Ri}$;

4. the labeling function $r_i$ labels each node $x \in V_i$ with a set of references to its r-images $r_i(x) \subseteq \{j: y \mid j \in I \land y \in V_j\}$.

During the run of the tableaux algorithm, tableaux expansion rules are applied on the completion tree and the tree is expanded by each rule application. If no more rules are applicable any more, we say that the tree is complete. There is a clash in the completion tree $T$ if for some $x \in V_i$ and for some $C \in N_{ci}$ we have $\{C, \neg C\} \subseteq L_i(x)$. Given a distributed completion tree $T = \{T_i\}_{i \in I}$, a node $x \in V_i$ is blocked, if it has an ancestor $y \in V_i$ such that $L_i(x) \subseteq L_i(y)$. In such a case we also say that $x$ is blocked
by y. Node $y \in V_i$ is said to be an R-successor of $x \in V_i$, if $\langle x, y \rangle \in E_i$ and $L_i(\langle x, y \rangle) = R$.

Taking a distributed Tbox DTB and a concept C in NNF as its inputs, the distributed tableaux algorithm continues in three steps:

(1) Create new distributed tree $T=\{T_j\}_{j \in I}$ such that $T_j=\langle\{s_0\}, \emptyset, \{s_0 \to C\}\rangle$, $\emptyset$ for $j=i$ and $T_j=\langle\emptyset, \emptyset, \emptyset, \emptyset\rangle$ for $j \neq i$.

(2) Apply the following tableaux expansion rules exhaustingly:

(a) $\sqcap$-rule: If $C_1 \sqcap C_2 \in L_i(x)$ for some $x \in V_i$ and $\{C_1, C_2\} \notin L_i(x)$, and $x$ is not blocked, then set $L_i(x) = L_i(x) \cup \{C_1, C_2\}$.

(b) $\sqcup$-rule: If $C_1 \sqcup C_2 \in L_i(x)$ for some $x \in V_i$ and $\{C_1, C_2\} \cap L_i(x) = \emptyset$, and $x$ is not blocked, then either set $L_i(x) = L_i(x) \cup \{C_1\}$ or set $L_i(x) = L_i(x) \cup \{C_2\}$.

(c) $\exists$-rule: If $\exists R.C \in L_i(x)$ for some $x \in V_i$ with no R-successor y s.t. $C \in L_i(y)$, and $x$ is not blocked, then add new node z to $V_i$, add the edge $\langle x, z \rangle$ to $E_i$, and set $L_i(z) = \{C\}$ and $L_i(\langle x, z \rangle) = \{R\}$.

(d) $\forall$-rule: If $\forall R.C \in L_i(x)$ for some $x \in V_i$, and there is R-successor y of x s.t. $C \notin L_i(y)$, and $x$ is not blocked, then set $L_i(y) = L_i(y) \cup \{C\}$.

(e) Action $\alpha$-rule: If $[\alpha]C \in L_i(x)$ for some $x \in V_i$, $\alpha = (P_\alpha, E_\alpha)$, then set $L_i(x) = L_i(x) \cup \{\text{all conditions in } P_\alpha\} \cup \{\text{all conclusions in } E_\alpha\} \cup \{C\}$

(f) $\sqsupseteq$-rule: If $G$ (or $\beta$) $\in L_j(x)$ for some $x \in V_j$, $i: C$ (or $\alpha$) $\to j: G$ (or $\beta$) $\in BR$, and there is no $y \in V_i$ s.t. $C$ (or $\alpha$) $\in L_i(y)$ and $j: x \in r_i(y)$, and $x$ is not blocked, then add new node y to $V_i$ and set $L_i(y) = \{C$ (or $\alpha$) $\}$, and set $r_i(y) = \{j: x\} \cup r_j(x)$.

(g) $\sqsubseteq$-rule: If $D$ (or $\pi$) $\in L_i(x)$ for some $x \in V_i$, $i: D$ (or $\pi$) $\to j: H$ (or $\rho$) $\in BR$ and there is $y \in V_j$ s.t. $j: y \in r_i(x)$ and $H$ (or $\rho$) $\notin L_j(y)$, then set $L_j(y) = L_j(y) \cup \{H$ (or $\rho$) $\}$.

(3) If none of the tableaux expansion rules is applicable any more (i.e., the distributed tree is now complete), answer “C is satisfiable” if a clash-free completion tree has been constructed. Answer “C is unsatisfiable” otherwise.

**Theorem 4.** The satisfiability problem of concept in D3L<sub>(ccy)</sub> is decidable.

*Proof.* To determine whether the concept is satisfiable is to check whether the completion tree includes clash. In D3L<sub>(ccy)</sub>, a distributed tree can be expanded by applying tableaux rules, as described in above algorithm. Now we ought to prove that the algorithm, once starts with input, eventually terminates. We will consider each step of the algorithm separately:

It is obvious that the establishment of a new tree in the first step eventually terminates for both $j=i$ and $j \neq i$.

In the second step, tree is expanded by applying seven tableaux rules. Only $\sqcup$-rule
is uncertain, but at worst complete binary tree is constructed which can be finished in
exponential time. □-rule, ∃-rule and ∀-rule which can be finished in polynomial time
are all terminable. Action α-rule has no effect on the decidability of D3L<sub>(ccy)</sub> too, for
detailed discussion please refer to [1]. The terminability of $\overline{\sqsupset}\rightarrow$-rule and $\overline{\sqsubseteq}\rightarrow$-rule is discussed as follows: If there are onto-bridge rules ingoing into $T_i$ then possibly
in some $x \in V_i$ such that $C$ (or $\alpha$) $\in L_i(x)$ and $C$ (or $\alpha$) appears on a right hand
side of an onto-bridge rule, say $k: D$ (or $\pi$) $\overline{\sqsupset}\rightarrow i: C$ (or $\alpha$), then the
$\overline{\sqsupset}\rightarrow$-rule is applied and computation is triggered in $T_k$. By structural subsumption
we assume that this computation eventually terminates (the length of the longest
incoming path of into-bridge rules decreased for $T_k$ compared to $T_i$, and all such paths
are finite because of acyclicity). During this process we possibly get some new
concepts in $L_i(x)$ that are introduced thanks to incoming into-bridge rules that
trigger the $\overline{\sqsubseteq}\rightarrow$-rule--but only finitely many. The computation now continues in $x$
and its descendants and possibly the $\overline{\sqsupset}\rightarrow$-rule is triggered again in some $y \in V_i$, a
descendant of $x$. But thanks to subset blocking, this happens only finitely many times.
Hence $\overline{\sqsupset}\rightarrow$-rule and $\overline{\sqsubseteq}\rightarrow$-rule eventually terminate.

Clash checking process of distributed completion tree in the third step is terminable. Either concept is unsatisfiable because there are clashes in the tree, or concept is satisfiable because there are not clashes. Hence the satisfiability problem of concept in D3L<sub>(ccy)</sub> is decidable. □

# 6 Conclusion and Future Work

Although knowledge propagation theory has been studied, only simple cases with two
DDL ontologies were involved. In this paper we focused on the general cases with
arbitrary number of ontologies and bridge rules chains. We found original semantics
of D3L could not ensure correct knowledge propagation because domain relations
were not transitive. Inspired by Package-based description Logics, we extended the
original semantics of D3L by imposing so called compositional consistency condition
on domain relations. Under this semantics knowledge propagates along chains of
bridge rules correctly. At last, we studied the decidability of satisfiability problem of
concepts in D3L under compositional consistency and provided a distributed Tableaux
algorithm for deciding it.

Extending presented algorithm for expressive D3L, analysing computational
complexity of the algorithm and developing corresponding reasoners are left for
future work.

# Acknowledgment

This work is supported by the Chinese National Natural Science Foundation(No.
61035003, No. 61072085, No. 60970088).
References

1. Shi Zhongzhi, Dong Mingkai, Jiang Yuncheng, et al.: A Logic Foundation for the Semantic Web. Science in China, Series F Information Sciences, 48(2):161-178 (2005)

2. Shi Zhongzhi, Jiang Yuncheng, Zhang Haijun, et al.: Agent service matchmaking based on description logic. Chinese Journal of Computers, 27(5): 625-635 (2004) (in Chinese)

3. Jiang Yuncheng, Shi Zhongzhi, Tang Yong, et al.: A Distributed Dynamic Description Logic. Journal of Computer Research and Development, 43(9): 1603-1608 (2006) (in Chinese)

4. Wang Zhuxiao.: Distributed Information Retrieval Oriented Automatic Reasoning. Doctor's thesis, Institute of Computing Technology, Chinese Academy of Sciences, Beijing (2010)

5. Bao, J., Caragea, D., Honavar, V.: On the semantics of linking and importing in modular ontologies. LNCS, vol. 4273, pp. 72-86. Springer, Heidelberg (2006)

6. Franz, B., Diego, C., Deborah, M., et al.: The description logic handbook: Theory, implementation, and applications. 2nd edition. Cambridge University Press, Cambridge (2007)

7. Aquin, M. D., Schlicht, A., Stuckenschmidt, H., et al.: Criteria and Evaluation for Ontology Modularization Techniques. LNCS, vol. 5445, pp.67-89. Springer, Heidelberg (2009)

8. Bao, J., Caragea, D., Honavar, V. G.: A distributed tableau algorithm for package-based description logics. In: 2nd International Workshop on Context Representation and Reasoning. IOS Press, Italy (2008)

9. Grau B. C., Parsia B., Sirin E.: Combining OWL ontologies using Ξ-connections. Journal of Web Semantics, 4(1): 40-59 (2006)

10. Grau B. C., Parsia B., Sirin E.: Ontology Integration Using Ξ-Connections. LNCS, vol. 5445, pp. 293-320. Springer, Heidelberg (2009)

11. Kutz O., Lutz C., Wolter F., et al.: Ξ-connections of abstract description systems. Artificial Intelligence, 156(1): 1-73 (2004)

12. Bao J., Voutsadakis G., Slutzki G., et al.: Package-Based Description Logics. LNCS, vol. 5445, pp. 349-371. Springer, Heidelberg (2009)

13. Lutz C., Walther D., Wolter F.: Conservative extensions in expressive description logics. In: Twentieth International Joint Conference on Artificial Intelligence(IJCAI'07), pp. 453-458. AAAI Press, California (2007)

14. Serafini L., Borgida A., Tamilin A.: Aspects of Distributed and Modular Ontology Reasoning. In: Tenth International Joint Conference on Artificial Intelligence(IJCAI'05), pp. 570-575. AAAI Press, California (2005)