Introduction

Ontologies are widely used for sharing and reasoning over domain knowledge, and their underlying formalisms are often description logics (DLs). To effectively answer queries, ontologies from heterogeneous sources and contributed by various authors are often needed. However, ontologies developed by multiple authors under different settings may contain overlapping, conflicting and incoherent domain knowledge. The ultimate goal of ontology merging is to obtain a single consistent ontology that preserves as much knowledge as possible from two or more heterogeneous ontologies. This is in contrast to ontology matching [5], whose goal is to align entities (with different name) between ontologies, and which is often a pre-stage of ontology merging.

Existing merging systems often adopt formula-based approaches to deal with logical inconsistencies [10; 9; 14]. Most of such approaches can be described as follows: the system first combine the ontologies by taking their union; then, if any inconsistency is detected (through a standard reasoning), it pinpoints the axioms which (may) cause inconsistency; and finally, remove certain axioms to retain consistency. However, such an approach is sometimes unsatisfactory because it is not fine-grained either in the way it measures the minimality of changes, and thus it is often unclear how close the result of merging is to the source ontologies semantically; or in the way it resolve inconsistency. In [12], an attempt is made to provide some semantic justification for the minimality of changes, however, the result of merging is still syntax-dependant and is often a set of ontologies.

On the other hand, model-based merging operators have been intensively studied in propositional logic, which are syntax-independent and usually satisfy more rationality postulates than formula-based ones. However, a major challenge in adapting model-based merging techniques to DLs is that DL models are generally infinite structures and the number of models of a DL ontology is infinite. Several notions of model distance are defined on classical DL models for ontology revision [13]. Mathematically, it is possible to define a distance o classical DL models. Such a distance is computationally limited as it is unclear how to develop an algorithm for the resulting merging operator. A desirable solution is to define ontology merging operators based on a suitable finite semantic characterisation instead of classical DL models.

In this paper, we focus on merging ontologies expressed as DL-Lite TBoxes, which can be also accompanied with the ontology-based data access (OBDA) framework for data integration [2]. We propose a novel approach for merging ontologies by adapting a classical model-based belief merging approach, where the minimality of changes is realised via a semantic notion, model distance. Instead of using classical DL models, which may be infinite structures in general, we define our merging operator based on the notion of types. We show that subclass relation w.r.t. the result of merging can be checked efficiently via a QBF reduction, which allows us to make use of the off-the-shelf QBF solvers [8]. We present our system OntoMerge, which effectively answers subclass queries on merging results, without first computing the merging results. Our system can be used to answer subclass queries on multiple ontologies.

A New Semantic Characterisation

In our approach, it is sufficient to consider a finite yet large enough signature. A signature S is a union of four disjoint finite sets S C , S R , S I and S N , where S C is the set of atomic concepts, S R is the set of atomic roles, S I is the set of individual names and S N is the set of natural numbers in S. We assume 1 is always in S N .

Formally, given a signature S, a DL-Lite N bool language has the following syntax [1]:

R ← P | P − S ← P | ¬P B ← | A | n R C ← B | ¬C | C 1 C 2 where n ∈ S N , A ∈ S C and P ∈ S R .

B is called a basic concept and C is called a general concept. B S denotes the set of basic concepts on S. We write ⊥ for ¬ , ∃R for ≥ 1 R, and C 1 C 2 for ¬(¬C 1 ¬C 2 ). Let R + = P , where P ∈ S R , whenever R = P or R = P − . A TBox T is a finite set of concept axioms of the form C 1 C 2 , where C 1 and C 2 are general concepts. An ABox A is a finite set of membership assertions of the form C(a) or S(a, b), where a, b are individual names. In this paper, an ontology is represented as a DL TBox.

The classical DL semantics are given by models. A TBox T is consistent with an ABox A if T ∪ A has at least one model. A concept or role is satisfiable in T if it has a non-empty interpretation in some model of T . A TBox T is coherent if all atomic concepts and atomic roles in T are satisfiable. Note that a coherent TBox must be consistent. TBox T entails an axiom C D, written T |= C D, if all models of T satisfy C D. Two TBoxes T 1 , T 2 are equivalent, written T 1 ≡ T 2 , if they have the same models. Now, we introduce a semantic characterisation for DL-Lite TBoxes in terms of types. A type τ ⊆ B S is a set of basic concepts over S, such that ∈ τ , and n R ∈ τ implies m R ∈ τ for each pair m, n ∈ S N with m < n and each (inverse

) role R ∈ S R ∪ { P − | P ∈ S R }. Type τ satisfies basic concept B if B ∈ τ , ¬C if τ does not satisfy C, and C 1 C 2 if τ satisfies both C 1 and C 2 . Given a TBox T , type τ satisfies T if τ satisfies concept ¬C 1 C 2 for each axiom C 1 C 2 in T .

For a TBox T , define TM(T ) to be the maximal set of types satisfying the following conditions: (1) all the types in TM(T ) satisfy T ; (2) for each type τ ∈ TM(T ) and each ∃R in τ , there exists a type τ ∈ TM(T ) (possibly

τ = τ ) containing ∃R − . A type τ is called a type model (T-model) of T if τ ∈ TM(T ).

Note that TM(T ) is uniquely defined for each TBox T . Note that for a coherent TBox T , TM(T ) is exactly the set of all types satisfying T . Let Given a type τ , an individual a and an ABox A, we say τ is a type of a w.r.t. A if there is a model

TM(Π) = TM(T 1 ) × • • • × TM(T n ) for Π = T 1 , . . . , T n .I of A such that τ = {B | a I ∈ B I , B ∈ B S }. For example, given A = {A(a), ¬B(b), C(c)}, type τ = {A, B} is a type of a, but not a type of either b or c in A.

For convenience, we will say a type of a when the ABox A is clear from the context. Let TM a (A) be the set of all the types of a in A if a occurs in A; and otherwise, TM a (A) be the set of all the types. A set M of T-models satisfies an ABox A if there is a type of a in M , i.e., M ∩ TM a (A) = ∅, for each individual a in A.

Proposition 2. Given a TBox T and an ABoxA, T ∪ A is consistent iff TM(T ) ∩ TM a (A) = ∅ for each a in A.

Merging Operator

In this section, we introduce an approach to merging DL-Lite ontologies to obtain a coherent unified ontology.

An ontology profile is of the form Π = T 1 , . . . , T n , where T i is the ontology from the source n.o. i (1 ≤ i ≤ n). There are two standard definitions of integrity constraints (ICs) in the classical belief change literature [3], the consistencyand entailment-based definitions. We also allow two types of ICs for merging, namely the consistency constraint (CC), expressed as a set A c of data, and the entailment constraint (EC), expressed as a TBox T e . We assume the IC is selfconsistent, that is, T e ∪ A c is always consistent. For an ontology profile Π, a CC A c and a EC T e , an ontology merging operator is a mapping (Π,

T e , A c ) → ∇(Π, T e , A c ), where ∇(Π, T e , A c ) is a TBox, s.t. ∇(Π, T e , A c )∪A c is consistent, and ∇(Π, T e , A c ) |= T e .

In classical model-based merging approaches, merging operators are often defined by certain notions of model distances [11; 6]. We use S S to denote the symmetric difference between two sets S and S , i.e., S S = (S \ S ) ∪ (S \ S). Given a set S and a tuple S = S 1 , . . . , S n of sets, the distance between S and S is defined to be a tuple d(S, S) = S S 1 , . . . , S S n . For two n-element distances d and d , d d if d i ⊆ d i for each 1 ≤ i ≤ n, where d i is the i-th element in d. Given two sets S and S , define σ(S, S ) = S if S is empty, and otherwise, σ(S, S ) = { e 0 ∈ S | ∃e 0 ∈ S s.t. ∀e ∈ S, ∀e ∈ S , d(e, e ) ≺ d(e 0 , e 0 ) }. In [6], given a collection Ψ = {ϕ 1 , . . . , ϕ n } of propositional formulas, and some ECs expressed as a propositional theory µ, the result of merging ϕ 1 , . . . , ϕ n w.r.t. µ is the theory whose models are exactly σ(mod(µ), mod(Ψ )), i.e., those models satisfying µ and having minimal distance to Ψ .

Inspired by classical model-based merging, we introduce a merging operator in terms of T-models. For an ontology profile Π and an EC T e , we could define the T-models of the merging to be a subset of TM(T e ) (so that T e is entailed) consisting of those T-models which have minimal distance to Π, i.e., σ(TM(T e ), TM(Π)). However, this straightforward adoption does not take the CC into consideration, and the merging result obtained in this way may not be coherent. For example, let T 1 = {A ¬B}, T 2 = { B}, T e = ∅, and A c = {A(a), B(a)}. Then, σ(TM(T e ), TM( T 1 , T 2 )) consists of only one type {B}. Clearly, the corresponding TBox {A ⊥, B} does not satisfy the CC, and it is not coherent.

Note that in the above example, once the merging result satisfies the CC, then it is also coherent, because both concepts A and B are satisfiable. In general, it is also the case that coherency can be achieved by applying certain CC to merging. We introduce an auxiliary ABox A † in addition to the initial CC A c , in which each concept and each role is explicitly asserted with a member. That is,

A † = {A(a) | A ∈ S C , a ∈ S I is a fresh individual for A} ∪ {P (b, c) | P ∈ S R

, b, c ∈ S I are fresh individuals for P }. As assumed, S I is large enough for us to take these auxiliary individuals. From the definition of CCs, the merged TBox T must be consistent with all the assertions in A † , which assures all the concepts and roles in T to be satisfiable. Based on this observation, we have the following lemma.

Lemma 1. T is coherent iff T ∪ A † is consistent for any TBox T .

To ensure the coherence of merging, we only need to include A † into the CC.

For the merging to be consistent with the CC A c , from Proposition 2, the T-model set M of the merging needs to satisfy A c . That is, M needs to contain a type of a for each individual a in A c . However, σ(TM(T e ), TM(Π)) does not necessarily satisfy this condition, as can be seen from the above example: TM a (A c ) consists of a single type {A, B} and σ(TM(T e ), TM(Π)) ∩ TM a (A c ) = ∅. Intuitively, for the merging to satisfy the CC, type {A, B} need to be added to the T-models of merging. In general, the T-models of merging can be obtained by extending (if necessary) the set σ(TM(T e ), TM(Π)) with at least one type of a w.r.t. A c for each individual a in A c , and if there are multiple such types, choose those with minimal distances.

Based on the above intuitions, the definition of TBox merging is presented as follows.

Definition 1. Let Π be an ontology profile, T e be a TBox, and A c be an ABox. Denote A * = A c ∪ A † . The result of merging Π w.r.t. the EC T e and the CC A c , denoted ∇(Π, T e , A c ), is defined as follows

TM(∇(Π, T e , A c )) = σ(TM(T e ), TM(Π))∪ a occurs in A * σ(TM(T e ) ∩ TM a (A * ), TM(Π)).

From the definition, the T-models of the merging are constituted with two parts. The first part consists of those T-models of T e (for the satisfaction of the EC) with minimal distances to Π. The second part consists of types of a, for each individual a in A * , which are added to the first part for the satisfaction of the CC. These types are also required to be T-models of T e and have minimal distances to Π. It is clear from Proposition 1 that the result of merging is unique up to TBox equivalence.

QBF Reduction

In this section, we consider a standard reasoning problem for ontology merging, namely the subclass queries: whether or not the result of merging entails a subclass relation C D. We present a QBF reduction for this problem, which allows us to make use of the off-the-shelf QBF solvers [8]. We assume that every TBox in the ontology profile is coherent, and in this case, the T-models of a TBox T are exactly those satisfying T .

We achieve the reduction in three steps. Firstly, we introduce a novel propositional transformation for DL-Lite TBoxes. The transformation is inspired by [1], which contains a transformation from a DL-Lite TBox into a theory in the one variable fragment of first order logic. Considering T-models instead of classical DL models allows us to obtain a simpler transformation to propositional logic than theirs to first order logic. Function φ(•) maps a basic concept to a propositional variable, and a general concept (resp., a TBox axiom) to a propositional formula.

φ(⊥) = ⊥, φ(A) = p A , φ( n R) = p nR , φ(¬C) = ¬φ(C), φ(C 1 C 2 ) = φ(C 1 ) ∧ φ(C 2 ), φ(C 1 C 2 ) = φ(C 1 ) → φ(C 2 ).

Here, p A and p nR are propositional variables. We use V S to denote the set of propositional variables corresponding to the basic concepts over S, and we omit the subscript S in what follows for simplicity. We can see that φ(•) is a bijective mapping between the set of DL-Lite N bool general concepts and the set of propositional formulas only referring to symbols in V S and boolean operators ¬, ∧ and →.

Naturally, given the mapping φ(•), an arbitrary propositional model may not correspond to a type. We define a formula η whose models are exactly the set of types. Let It is worth noting that the sizes of φ(T ) and φ(a, A) are both polynomial in the size of T ∪ A. The intuition behind φ(T ) and φ(a, A) can be shown by the following lemma.

η = R + ∈S R m,

Lemma 2. Given a coherent TBox T and an ABox A, then,

1. mod(φ(T )) = {φ(τ ) | τ ∈ TM(T )}; 2. mod(φ a (A) ∧ η) = {φ(τ ) | τ ∈ TM a (A)}.

This transformation essentially allows us to build a connection between our merging operator and propositional belief merging.

Secondly, as we have a transformation from T-models to propositional models, we can encode (minimal) distances between them using QBFs, by extending the encoding in [4], which was introduced for a different purpose. In particular, we need to encode the distances between the models of φ and the models of ϕ 1 , . . . , ϕ n (n ≥ 1), where φ and ϕ i 's are propositional formulas in signature V . We make n-fresh copies of V to, informally, encode the models of ϕ 1 , . . . , ϕ n , respectively; let V i = {p i | p ∈ V } for 1 ≤ i ≤ n where each p i is a fresh variable for p, and V N = 1≤i≤n V i . For a propositional formula ϕ and 1 ≤ i ≤ n, ϕ i denotes the formula obtained from ϕ by replacing each occurrence of p with p i . We also need another n-fresh copies of V , V i d = {p i d | p ∈ V } to represent the distances. An assignment to V i d is expected to capture the difference between a model of φ and a model of ϕ i , and in particular, p i d is assigned true if the truth values of p and p i are different. Let

V N d = 1≤i≤n V i d . Define F (φ, ϕ 1 , . . . , ϕ n ) = φ ∧ 1≤i≤n ϕ i i ∧ p∈V (p ↔ ¬p i ) → p i d .

A model M of F (φ, ϕ 1 , . . . , ϕ n ) consists of the assignments to three sets of variables V , V N and

V N d . For a set S ⊆ V ∪ V N ∪ V N d , m(S)

is the set obtained from S by eliminating the super-and subscripts. Then, M ∩ V is a model of φ, and m(M

∩V i ) is a model of ϕ i . From (p ↔ ¬p i ) → p i d , m(M ∩V i d )

subsumes the symmetric difference between the former two models. We use → instead of ↔ here, as we will further constraint the assignments of V N d to minimal distances. Furthermore, define a QBF

D(φ, ϕ 1 , . . . , ϕ n ) =(∃V ∃V N F (φ, ϕ 1 , . . . , ϕ n )) ∧ p∈V 1≤i≤n p i d → ¬∃V ∃V N F (φ, ϕ 1 , . . . , ϕ n ) ∧ (p ↔ p i ) ,

where ∃V with V = {p 1 , . . . , p k } is an abbreviation for ∃p 1 . . . ∃p k . A model M d of D(φ, ϕ 1 , . . . , ϕ n ) is an assignment to V N d representing a minimal distance between the models of φ and the model tuples of ϕ 1 , . . . , ϕ n . The first conjunct of D(φ, ϕ 1 , . . . , ϕ n ) says that there is a model of φ and a model tuple of ϕ 1 , . . . , ϕ n such that the distance between them is subsumed by m(M d ).

The second conjunct checks that m(M d ) is minimal, i.e., there is no distance properly subsumed by m(M d ).

Lemma 3. Given propositional formulas φ and ϕ 1 , . . . , ϕ n , let M D(φ, ϕ 1 , . . . , ϕ n ) be the set of minimal distances (w.r.t. ) between φ and ϕ 1 , . . . , ϕ n (of the form M M 1 , . . . , M M n with M ∈ mod(φ) and M i ∈ mod(ϕ i )). Then,

mod(D(φ, ϕ 1 , . . . , ϕ n )) = {M d ⊆ V N d | ∃d ∈ M D(φ, ϕ 1 , . . . , ϕ n ) s.t. m(M d ∩ V i d ) = d i for each 1 ≤ i ≤ n}.

Finally, with the encoding of minimal distances, we can encode the T-models of the merging and we are ready to encode the entailment relation. Given an ontology profile Π = T 1 , . . . , T n and a TBox T e , all the types in σ(TM(T e ), TM(Π)) satisfy TBox axiom α if and only if QBF ¬∃V N d E(Π, T e , α) evaluates to true, with

E(Π, T e , α) = D(φ(T e ), φ(T 1 ), . . . , φ(T n ) ) ∧ ¬∀V ∃V N F (φ(T e ), φ(T 1 ), . . . , φ(T n ) ) → φ(α) .

This QBF can be understood as follows. A model M of E(Π, T e , α) is an assignment to V N d , and represents, by the first conjunct of E(Π, T e , α), a minimal distance between the T-models of T e and the T-model tuples of Π. The second conjunct states the non-entailment, that is, not all of the T-models of T e having such a distance satisfy α. The QBF as a whole essentially says that there does not exists a minimal distance d such that a type (in σ(TM(T e ), TM(Π))) selected with d fails to satisfy α. Similarly, given an ABox A and an individual a in A, all the types in σ(TM(T e ) ∩ TM a (A), TM(Π)) satisfy α iff QBF ¬∃V N d E a (Π, T e , A, α) evaluates to true, where E a (Π, T e , A, α) is obtained from E(Π, T e , α) by replacing φ(T e ) with φ(T e ) ∧ φ a (A). Now, we can reduce the subclass query answering for TBox merging to QBF as follows.

Theorem 1. Let Π be an ontology profile with coherent source TBoxes, T e be a TBox and A c be an ABox in DL-Lite N bool . Let A * = A c ∪ A † . Given a TBox axiom α, we have ∇(Π, T e , A c ) |= α iff the following QBF evaluates to true

¬∃V N d E(Π, T e , α) ∨ a occurs in A * E a (Π, T e , A * , α) .(1)

5 System Architecture

We have implemented the algorithm for answering subclass queries in ontology merging, called OntoMerge, and it is publicly available for test at http: //www.ict.griffith.edu.au/ ~kewen/OntoMerge/. The ultimate goal of our system OntoMerge is to transform the entailment over merged ontologies to the validity of QBFs as given in Eq.( 1). If the input ontologies are T 1 , . . . , T n and the query is α, then the corresponding QBF can be split into two parts: one is the formula E(Π, T e , α), and the other is a disjunction of formulas of the form E a (Π, T e , A * , α). The size of the first part is only determined by the sizes of the input ontologies, the input EC and the query α, and the size of α is often small compared to the ontologies. In the second part of the resulting QBF, the number of disjuncts is essentially determined by the number of unsatisfiable concepts in the union of input ontologies (as will be explained later) and the input CC. Thus, the number of unsatisfiable concepts plays a crucial role in the complexity of the reduction algorithm.

In OntoMerge, we first check whether the given ontologies can be simply jointed without causing any incoherency using an off-the-shelf DL reasoner (Her-miT [7] is used in the current program). The set of unsatisfiable concepts will be stored for being used later. If the union of input ontologies is coherent, the query answering can be done by the DL reasoner; otherwise, the system generates the QBF specified in Eq. (1). For this purpose, the system will first scan all input ontologies to obtain the set of basic concepts occurring in these ontologies and assign a propositional variable with each basic concept. Then the QBF is generated in QBF 1.0 format5 . The structure of OntoMerge is depicted in Figure 1. However, as most of efficient QBF solvers accept only input QBFs in the prenex normal form, the QBF generated in this way cannot be directly fed to a QBF solver. So we need to convert the QBF into the prenex normal form first. Unfortunately, the standard translation from a given QBF into its prenex normal form is very inefficient and thus several heuristics based on the specific QBF are used to optimize the efficiency in our implementation. For instance, from Eq.( 1), we can see that the major source for introducing a large number of new variables is from the construction of the ABox A * . So we introduce new variables for only those concepts that are unsatisfiable and add new assertions for such new variables to A * in the reduction algorithm. This optimization significantly reduces the number of new variables.

Once the QBF is generated, a publicly available program is used to convert it from QBF 1.0 format to QDIMACS format6 or ISCAS format 7 and then an efficient QBF solver is used to decide the validity of the QBF.

Experimental Results

To test the efficiency of OntoMerge, we used the DL-Lite N bool fragment of the medical ontology Galen8 , which is of medium size. Our experimental results show that the system is relatively efficient, while further optimization is still under way. Specifically, various randomly modified fragments of Galen were merged using OntoMerge and the following three types of experiments were conducted:

-Fixed total number of axioms in the input ontologies but varied number of unsatisfiable concepts. -Fixed total number of unsatisfiable concepts but varied total number of axioms in the input ontologies. -Fixed number of unsatisfiable concepts but varied total number of input ontology axioms.

A PC with Intel Core 2 Duo E8400, 4GB RAM, running Linux Mint 13 64bit, and CirQit QBF solver [8] were used in our tests. For each test, the time is limited to one hour (i. e. the program will be terminated after one hour no matter a result is returned or not). Figure 2 shows the experimental results in the first set of tests. In each test, 42 axioms were randomly selected from Galen ontology and they were separated into two sub-ontologies for merging. Then assertions were inserted into one of them so that some concepts became unsatisfiable in the union of these two ontologies. The number of unsatisfiable concepts varied from 1 to 18. From this figure we can see that the program is quite fast according to the time used for generating the QBF and the time used for deciding the validity of the QBF. This is because when the number of unsatisfiable concepts increases, the size of the QBF generated increases linearly. However, when the number of unsatisfiable concepts is over 18, OntoMerge can still generate the QBF but the QBF solver is unable to decide the validity of such a QBF. In the second set of tests, we fixed the number of unsatisfiable concepts to 1 but increased the total number of axioms from 26 to 174. Figure 3 shows that when the number of axioms is increased, the time cost for generating QBF increases faster than in the first set of tests. This is partly due to the fact that with the increase of the total axioms, the size of the QBF significantly increases too. Similar to the case for the first set of tests, when the total number of axioms is over 174, the QBF solver fails again. In the third set of tests, we fix the ratio of total number of axioms to the number of unsatisfiable concepts to around 0.15 but let the total number of axioms varied from 26 to 92 as well as the number of unsatisfiable concepts. Figure 4 shows a similar pattern to Figure 3. When the total number of axioms is over 92, the QBF solver failed to return an answer.

We have developed a novel approach for merging ontologies in DL-Lite, in terms of types instead of classical DL models. We have also presented algorithms to reduce subclass queries of DL-Lite merging to the evaluation of QBFs and thus provided a novel way of reasoning with the result of ontology merging using efficient QBF solvers. We have implemented a preliminary merging system On-toMerge, and reported some experimental results in the paper. Currently we are extending the approach in two directions: (1) merging DL-Lite ontologies with both TBoxes and ABoxes, and (2) merging ontologies in expressive DLs.