This short paper studies the problem of merging of different independent data sources linked to a lightweight ontology under the incommensurability assumption. In general, data are often provided by several and potentially conflicting sources of information having different levels of priority. To encode prioritized assertional bases, we use possibilistic DLLite logic. We investigate an egalitarist merging strategy that minimize dissatisfaction between the source involved in the merging process. We provide a safe way to merge incommensurable possibilistic DL-Lite assertional bases using the notion of compatible scales.
Description Logics (DLs) are a well-known family of logicbased formalisms used to represent knowledge of a particular domain and make it available for reasoning. DLs are recognized as powerful frameworks that support ontologies. A DL knowledge base is formed by a terminological base, called TBox, and an assertional base, called ABox. The TBox contains intentional (or generic) knowledge of the application domain whereas the ABox stores data (individuals or constants) that instantiate terminological knowledge.
In the last years, there has been an increasingly interest in Ontology-based Data Access (OBDA) that studies how to query a set of data linked to a unified TBox (ontology). A lot of attention was given to DL-Lite, a family of lightweight DLs specifically dedicated for applications that use huge volumes of data, in which query answering is the most important reasoning task. DL-Lite offers a very low computational complexity for the reasoning process.
In many applications, data are often provided by several
and potentially conflicting sources having different
reliability levels. Moreover, a given source may provide
different sets of uncertain data with different confidence
levels. In such situation, there are two main attitudes that
may be followed: the first attitude consists first in
gathering sets of assertions provided by each sources which
gives generally an inconsistent (prioritized or flat)
assertional base and then coping with inconsistencies when
performing inference using different inconsistency-tolerant
inference strategies (e.g.
Knowledge bases merging or belief merging (e.g.
In
This paper goes one step further by extending the
minbased possibilistic merging operator in the case where
uncertainty scales used by different sources are
incommensurable. We will follow the idea of egalitarist merging operator
proposed in
A compatible scale is a re-assignment of certainty degrees to assertional facts such that the initial plausibility ordering inside each ABox (source) is preserved. We show, in particular, that merging a set of ABoxes under incommensurable assumption comes down to apply min-based possibilistic merging of ABox with respect to each compatible scale.
The rest of the paper is organized as follows: Section 2 gives brief preliminaries on DL-Lite. Section 3 recalls DLLite an extension of DL-Lite within a possibility theory setting. Section 4 investigates min-based merging of multiple and uncertain DL-Lite ABoxs under the incommensurability assumption. Section 5 concludes the paper.
For the sake of simplicity, we only present DL-Litecore
the core fragment of all the DL-Lite family
R ! P jP B ! Aj9R C ! Bj:B where A is an atomic concept, P is an atomic role and P is the inverse of P . B (resp. C) is called basic (resp. complex) concept and role R is called basic role. A DL-Lite knowledge base (knowledge base) is a pair K=hT ; Ai where T is the TBox and A is the ABox. The TBox T includes a finite set of inclusion assertions of the form B v C where B and C are concepts. The ABox A contains a finite set of assertions on atomic concepts and roles of the form A(a) and P (a; b) where a and b are two individuals.
The semantics of a DL-Lite knowledge base is given in term of interpretations. An interpretation I = ( I ; :I ) consists of a non-empty domain I and an interpretation function :I that maps each individual a to aI 2 I , each A to AI I and each role P to P I I I . Furthermore, the interpretation function :I is extended in a straightforward way for complex concepts and roles: (:B)I = I n BI , (P )I = f(y; x)j(x; y) 2 P I g and (9R)I = fxj9y s.t. (x; y) 2 RI g. An interpretation I is said to be a model of a concept inclusion axiom, denoted by I j= B v C, iff BI CI . Similarly, we say that I satisfies a concept (resp. role) assertion, denoted by I j= A(a) (resp. I j= P (a; b)), iff aI 2AI (resp. (aI ; bI ) 2 P I ).
An interpretation I is said to be a model of K=hT ; Ai, denoted by I j= K, iff I j= T and I j= A where I j= T (resp. I j= A) means that I is a model of all axioms in T (resp. A). A knowledge base K is said to be consistent if it admits at least one model, otherwise K is said to be inconsistent. A DL-Lite TBox T is said to be incoherent if there exists at least a concept C such that for each interpretation I which is a model of T , we have CI =;. Note that within a DL-Lite setting, the inconsistency problem is always defined with respect to some ABox since a TBox may be incoherent but never inconsistent.
In this section, we recall the main notions of possibilistic
DL-Lite framework
Possibility Distribution over DL-Lite Interpretation Let be a universe of discourse composed by a set of DLLite interpretations (I=( ; :I ) 2 ). The semantic counterpart of a DL-Lite is given by a possibility distribution, denoted by , which is a mapping from to the unit interval [0; 1] that assigns to each interpretation I 2 a possibility degree (I) 2 [0; 1] that represents its compatibility or consistency with respect to the set of available knowledge. When (I)=0, we say that I is impossible and it is fully inconsistent with the set of available knowledge, whereas when (I)=1, we say that I is totally possible and it is fully consistent with the set of available knowledge. For two interpretations I and I0, when (I) > (I0) we say that I is more consistent or more preferred than I0 w.r.t available knowledge. Lastly, is said to be normalized if there exists at least one totally possible interpretation, namely 9I 2 ; (I)=1, otherwise, we say that is sub-normalized. The concept of sub-normalization reflects the presence of conflicts in the set of available information.
Given a possibility distribution defined on a set of interpretations , one can define two measures on a DL-Lite axiom ': A possibility measure (')=maxf (I) : I j= 'g I2 that evaluates to what extent an axiom ' is compatible with the available knowledge encoded by and a necessity measure N (')=1 maxf (I) : I 6j= 'g that evaluates to what
I2 extent ' is certainty entailed from available knowledge encoded by .
DL-Lite
Let L be a DL-Lite description language, a DL-Lite knowledge base is a set of possibilistic axioms of the form ('; W (')) where ' is an axiom expressed in L and W (') 2 ] 0; 1] is the degree of certainty/priority of '. Namely, a DLLite knowledge base K is such that K=f('i; W ('i)) : i = 1; :::; ng. Only somewhat certain information are explicitly represented in a DL-Lite knowledge base. Namely, axioms with a null weight (W ('i) = 0) are not explicitly represented in the knowledge base. The weighted axiom ('; W (')) means that the certainty degree of ' is at least equal to W ('i). A DL-Lite knowledge base K will also be represented by a couple K=hT ; Ai where both elements in T and A may be uncertain. It is important to note that, if we consider all W ('i) = 1 then we found a classical DLLite knowledge base: K =f'i : ('i; W ('i)) 2 Kg.
Given K=hT ; Ai a DL-Lite knowledge base, we define the -cut of K (resp. T and A), denoted by K (resp. T and A ), the subbase of K (resp. T and A) composed of axioms having weights at least greater than .
We say that K is consistent if the standard knowledge base obtained from K by ignoring the weights associated with axioms is consistent. In case of inconsistency, we attach to K an inconsistency degree. The inconsistency degree of a DLLite knowledge base K, denoted by Inc(K), is syntactically defined as follow: Inc(K)=maxfW ('i):K W ('i) is inconsistentg.
Given a DL-Lite knowledge base K, one can associate to K a joint possibility distribution, denoted by K, defined over the set of all interpretations I=( ; :I ) by associating to each interpretation its level of consistency with the set of available knowledge, that is, with K. Namely: Definition 1. The possibility distribution induced from a DL-Lite is defined as follows: 8I 2 :
1 if 8 ('i; W ('i)) 2 K; I j= 'i K(I)=
1-maxfW ('i):('i,W ('i))2K,I6j='ig otherwise A DL-Lite knowledge base K is said to be consistent if its joint possibility distribution K is normalized. If not, K is said to be inconsistent and its inconsistency degree is defined semantically as follow: Inc(K)=1 maxf K(I)g. I2
It was shown in
Example 1. Let K=hT ; Ai be a DL-Lite knowledge base where T =f(AvB; 1), (Bv:C; :9)g and A=f(A(a); :6), (C(b); :5)g. The possibility distribution K associated to K is computed using Definition 1 as follows where =fa; bg: possibility distribution i that encodes Ki = hT ; Aii is normalized. For the sake of simplicity, we use Ai instead of
Ki to denote the possibility distribution associated to each Ki = hT ; Aii
Given n commensurable ABoxes, merging aims to
compute T (A), an ABox representing the result of the fusion
of these ABoxes. In the literature, different methods for
merging have been proposed. In this section, we perform
merging of A1,...,An a set of ABoxes with respect to a TBox
T using min-based merging operator proposed to aggregate
DL-Lite knowledge bases. This operator is a direct
extension of the well-known idempotent conjunctive operator
(e.g.
We first introduce the notion of profile associated with an interpretation I, denoted by A(I), and defined by
A(I) =< A1 (I); :::; An (I) > :
Namely, A(I) represents the possibility values of an interpretation I with respect to each source.
From a semantics point of view, the result of merging is a possibility distribution T (A) obtained using two steps: i) the possibility degrees Ai (I)’s are first combined with a merging operator (here we use the minimum operator), and the interpretations with height degrees are kept. This leads to define an order relation, denoted by /Min, between interpretations as follows: an interpretation I is preferred to another interpretation I0 if the minimum element of the profile of I is higher than the minimum element of the profile of I0. More formally: Definition 2 (Definition of /Min). Let A = fA1; :::; Ang be a set of ABoxes linked to a TBox T . Let I and I0 be two interpretations and A(I), A(I0) be their associated profiles. Then:
I /Amin I0 ()
M in( A(I)) > M in( A(I0))
M in( A(I)) = M inf Ai (I) : i 2 f1; :::; ngg: The result of the merging min(A) is a DL-Lite knowledge base whose models areTinterpretations which are models of a constraint T and which are maximal with respect to /Min. More formally: Definition 3 (Min-based merging operator). Let A = fA1; :::; Ang be a set of ABoxes and T be an integrity constraint. Let f A1 ; :::; An g possibility distributions associated with (hT ; A1i ; :::; hT ; Ani). The result of merging is a DL-Lite knowledge base, denoted by min(A) where its model are defined by: T M od( Tmin(A))=fI2M od(T ):@I02M od(T ),I0/AMinIg
In general, merging two DL-Lite normalized possibility distributions may lead to a sub-normalized possibility distribution. The normalization process comes down to set the degrees of interpretations in M od( min(A)) to 1. T
From a syntactic point of view, the min-based merging operator, denoted by min(A) is the union of all ABox. Namely: T One can observe that K(I2)=1 meaning that ized, and thus, K is consistent.
K is normalwhere
This section studies min-based possibilistic merging operator in the case where uncertainty scales used by the different sources are incommensurable. Throughout this section, we assume that the TBox is coherent and fully certain and only assertional facts (ABoxes) may be somewhat certain. We first present merging using min-based operator of DL-Lite assertional bases under commensurability assumption.
Let A = fA1; :::; Ang be a set of n uncertain ABoxes issued from n distinct sources, and let T be a DL-Lite TBox representing the integrity constraints to be satisfied. Let us assume that 1; :::; n are possibility distributions provided by n sources of information that share the same domain of interpretations (namely 1I = ::: = In), and that all possibility distributions use the same scale to represent uncertainty. We suppose that each ABox is consistent with T , namely each min(A)=hT ; A1 [ A2 [ : : : [ Ani.
T
The aggregation of ABoxs is not guaranteed to be consistent. Namely, the resulting knowledge base T ; Tmin(A) may be inconsistent. To restore the consistency of the resulting knowledge base a normalization step is required. The following definition gives the formal logical representation of the normalized knowledge base.
Definition 4. Let T be a TBox and Tmin(A) be the aggregation of A1; :::An, n ABox using classical min-based operator. Let x= min(A). Then, the normalized knowledge base, denoted mT in(K) is such that:
T min(K)=f(fij ; W (fij )):(f; W (fij )2 Tmin(A) and T
W (fij ) > xgi Example 2 (continued). Let us continue with the TBox T =fA v B; B v :Cg presented in Example 1 while assuming that the certainty degree of each axioms is set to 1. Let us consider the following set of ABoxes to be linked to T : A1=f(A(a); :6), (C(b); :5)g, A2=f(C(a); :4), (B(b); :8), (A(b); :7)g. We have:
One can check that the resulting possibility distribution ( min(A)) is sub-normalized. To normalize min(A), it iTs enough to set I3 = :5 to 1. At syntactiTc level, we have min(A)=hT ; f(A(a); :6); (C(b); :5); (C(a); :4),
T (B(b); :8), (A(b); :7)gi. We have Inc( Tmin(A))=.5 and min(K)=T ; f(A(a); :6); (B(b); :8); (A(b); :7)g.
T
In the next section, we investigate min-based merging under incommensurability assumption.
The min-based merging operator presented in the previous section is defined over the assumption that all the sources providing the ABoxs use the same scale to encode uncertainties between facts. In Example 2, when dealing with assertions, we assumed that the weight attached to f 2 Ai can be compared to the weight associated with g 2 Aj with j 6= i. In this section, we drop this assumption and we suppose that sources are incommensurable.
We investigate a min-based fusion operator to merge incommensurable DL-Lite assertional bases. To make sources using different scale commensurable, we use the notion of "compatible scale" on existing scales used by each source.
A ranking scale is said to be compatible with all sources if it preserves original order relations between assertions of each ABox. The new ranking, denoted by R, defines a new ranking relations for each ABox to be merged. More formally, Definition 5 (Compatible ranking scale). Let A = fA1; :::; Ang where Ai = f(fij ; WAi (fij ))g. Then a ranking R is defined by:
R: A1 [ ::: [ An ! ]0; 1]
(fij ; WBi (fij )) 7! R(fij )
A ranking R is said to be compatible with WA1 ; :::; WAn if and only if: 8Ai 2 A; 8f; WAi (f )); (f 0; WAi (f 0)) 2 Ai;
WAi (f ) WAi (f 0) () R(f ) R(f 0):
Definition 5 is basically the adaptation of the one given
in
Example 3 (continued). Let us consider again the following set of ABoxes to be linked to T given in Example 2: A1=f(A(a); :6),(C(b); :5)g, A2=f(C(a); :4), (B(b); :8), (A(b); :7)g. The following table gives examples of ranking scales.
A1 A2 fij A(a) C(b) C(a) B(b) A(b)
WAi (fij ) .6 .5 .4 .8 .7
The scaling R1 is a compatible one, because it preserves the order inside each ABox. However, the scaling R2 is not a compatible one since it inverses priorities inside A1 and A2.
According to Example 3, it is obvious that a compatible ranking scale is not unique. Let us denote by R(A) the set of compatible scaling associated with A = fA1; :::; Ang. The set R(A) is non-empty and an immediate way to obtain a ranking relation over A is to consider R(fij ) = WAi (fij ) (For instance, the scale R3(fij ) given in Example 3). Note that this ranking is compatible in the sense that it permits to preserve the relative ordering between assertions of each Ai.
Given a compatible scales R, we denote by AiR the assertional base obtained from Ai by replacing each assertion (fij ; WAi (fij )) by (fij ; R(fij )). Similarly, we denote by AR the set obtained from A by replacing each Ai in A by AiR.
Now, given the set of all compatible scales R(A), different possibilities may exist in order to merge the ABoxs. For instance, one can only select one scale to perform merging or one can consider all the compatible ranking in R(A), etc. To avoid an arbitrary choice, we consider all compatible rankings to perform merging. (namely, I /AMRin I0). More precisely,
We first introduce the notion of preference between interpretation according to the notion of compatible scales. An interpretation I is then said to be preferred to I0, if for each compatible scale R, I is preferred to I0 using Definition 2 Definition 6 (Ordering between interpretations). Let A = fA1; :::; Ang be a set of DL-Lite ABoxs and R(A) be the set of all compatible scalings associated with A. Let I, I0 be two interpretations. Then:
I <8A I0 ()
8R 2 R(A); I /AMRin I0 where /AMRin is the result of applying Definition 2 on AR.
According to Definition 6, we have models of 8 (A) are T those which are models of T and minimal for <A, namely: 8 M od( 8T (A))=fI2M od(T ): @I02M od(T ), I0<8AIg:
AMRin(A). More formally: Note that <A is only a partial order. The following propo8 sition shows that an interpretation I is a model of 8 (A) if T and only if there exists a compatible scaling where this interpretation belongs to the result fusion, namely it is a model of Proposition 1. Let A be a set of ABoxes linked to the same TBox T . Then I 2 M od( 8T (A)), if and only if there exists a compatible scaling R such that I 2 M od( min(AR)): T
The following example illustrates the fusion based on all compatible scalings.
Example 4 (continued). Let us consider again the following set of ABoxes given in Example 2: A1=f(A(a); :6), (C(b); :5)g, A2=f(C(a); :4), (B(b); :8), (A(b); :7)g. Let us consider again R1 where A1R1 = f(A(a); :8); (C(b); :4))g and A2R1 = f(C(a); :2); (B(b); :9); (A(b); :6)g and a scaling R2 where A1R2 = f(A(a); :4); (C(b); :2))g and A2R2 = f(C(a); :3); (B(b); :6); (A(b); :5)g. Both of them are compatible. Table 4 presents the profile of each interpretation for each scaling.
Once preferred models are computed, query answering from a set of uncertain ABox under incommensurability assumption, is defined as follows: Definition 7. Let A = A1; :::; An be a set of ABoxes linked to the same TBox T . A query q is said to be consequence of A under incommensurability assumption if 8I; I 2 M od( Tmin(AR)); I j= q.
Example 5 (continued). From Example 4, we have M od( Tmin(AR))=fI3g where AI3 = fa; bg, BI3 = fa; bg and CI3 = fg. Let q1(x) A(x) ^ B(x) be a conjunctive query. One can easily check that < b > is an answer of q1(x) using min(AR). Similarly, let B(a) be
T an instance query, one can check that B(a) follows from min(AR).
T
Using the set of all compatible scales may lead to a very cautious merging operation. One way to get rid of incommensurability assumption is to use some normalization function in the spirit of the ones used in clustering methods for gathering attributes having incommensurable domains. Let Ai be an ABox and Ai be the set of different certainty degrees used in Ai. Let minAi and maxAi be respectively the minimum and maximum certainty degrees associated with assertional facts in Ai . Then an example of a normalization function is (1) N ( i) =
i maxAi (minAi (minAi ) )
Where i is a certainty degree belonging to Ai and is a very small number (lower than minAi ).
The main advantage of only having one normalization function is that one can have an immediate syntactic counterpart. More precisely, it is enough to replace for each fact (fij ; WAi (fij )) by (fij ; N (WAi (fij ))) where N is the normalization function given by Equation 1.
Example 6 (continued). From Example 2, we have A1=f(A(a); :6), (C(b); :5)g, A2=f(C(a); :4), (B(b); :8), (A(b); :7)g. We have minA1 = :5, minA2 = :4, maxA1 = :6 and maxA2 = :8. Let = :01, then applying Equation 1 on A1 and A2, gives: A1=f(A(a); 1), (C(b); :09)g, and A2=f(C(a); 0; 02), (B(b); 1), (A(b); :75)g.
Once the syntactic computation of normalized assertional bases is done, it is enough the reuse merging of commensurable possibilistic knowledge bases for query answering. Example 7 (continued). From Example 6, we have min(A)=hT ; f(A(a); 1); (C(b); :09); (C(a); :02), T (B(b); 1); (A(b); :75)gi. We have Inc( Tmin(A))=.09 and min(K)=T ; f(A(a); 1); (B(b); 1); (A(b); :75)g.
T
Consider now q1(x) A(x) ^ B(x) and q2 B(a), queries given in Example 5. One can check that < b > is an answer of q1(x) from the and B(a) holds from the resulting knowledge bases.
This paper proposed a min-based possibilistic merging operation of uncertain assertional facts under incommensurability assumption. The idea is to reuse standard min-based merging, over a set of compatible scales. Future work includes developing a syntactic counterpart of incommensurable merging operation. A natural question is whether one can extend a polynomial time complexity algorithm, defined for query answering from a standard uncertain ABox, to the case where uncertainty scales are incommensurable.
This work has been supported by the French National Research Agency. ASPIQ project ANR-12-BS02-0003