How to Select One Preferred Assertional-Based Repair from Inconsistent and Prioritized DL-Lite Knowledge Bases?

1 Introduction

Description Logics (DLs) are formal frameworks for representing and reasoning with ontologies. A DL knowledge base (KB) is built upon two distinct components: a terminological base (called TBox), representing generic knowledge, and an assertional base (called ABox), containing the facts that instantiate the TBox. DL-Lite [Calvanese et al., 2007] is a family of tractable DLs specifically tailored for applications that use huge volumes of data, in which query answering is the most important reasoning task. DL-Lite guarantees a low computational complexity. This fact makes DL-Lite especially well suited for Ontology-Based Data Access (OBDA).

A crucially important problem that arises in OBDA is how to manage inconsistency. In such setting, inconsistency is defined with respect to some assertions that contradict the terminology. Typically, a TBox is usually verified and validated while the assertions can be provided in large quantities by various and unreliable sources and may contradict the TBox. Moreover, it is often too expensive to manually check and validate all the assertions. This is why it is very important in OBDA to reason in the presence of inconsistency. Many works (e.g. [Lembo et al., 2010; Bienvenu and Rosati, 2013]), basically inspired by database approaches (e.g. [Bertossi, 2011]), tried to deal with inconsistency in DL-Lite by adapting several inconsistency-tolerant inference methods. These latter are based on the notion of assertional (or ABox) repair which is closely related to the notion of database repair. An ABox repair is simply a maximal assertional subbase which is consistent with respect to a given TBox [Lembo et al., 2010].

In many applications, assertions are often provided by several and potentially conflicting sources having different reliability levels. Moreover, a given source may provide different sets of uncertain assertions with different confidence levels. Gathering such sets of assertions gives a prioritized or a stratified assertional base. The role of priorities in handling inconsistency is very important and it is largely studied in the literature within propositional logic setting (e.g. [Baral et al., 1992; Benferhat et al., 1995]). Several works (e.g. [Martinez et al., 2008; Staworko et al., 2012; Du et al., 2013]) studied the notion of priority when querying inconsistent databases or DL KBs. Unfortunately, in the OBDA setting, there are only few works, such as the one given in [Bienvenu et al., 2014] for dealing with reasoning under prioritized DL-Lite ABox.

The main question addressed in this paper is how to select one preferred repair. Selecting only one preferred repair is important since it allows an efficient query answering once the repair is computed. In this paper, we first review main existing inconsistency-tolerant reasoning methods for prioritized KBs. It is important to note that some inference relations are specific to DL-Lite even if they are inspired by other formalisms. One of the main contributions of the paper consists in providing new strategies to define a single preferred repair based on the use of the so-called non-defeated assertional base, plus with one/several of the following four ingredients: priorities, deductive closure, cardinality and consistency. Interestingly enough, several of these strategies are suitable for the DL-Lite setting in the sense that they allow efficient handling of inconsistency, by producing a single preferred assertional repair. Our experimental results show the benefits of handling priorities when reasoning under inconsistency in DL-Lite.

2 DL-Lite Logic: A Brief Refresher

This section briefly recalls DL-Lite logics. For the sake of simplicity, we only consider DL-Litecore language [Calvanese et al., 2007] and we will simply use DL-Lite instead of DL-Litecore. However, results of this paper can be easily extended to any tractable DL-Lite where an ABox conflict involves at most two assertions, in particular DL-LiteR and DL-LiteF . The DL-Lite language is defined as follows:

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 (KB) is a pair K=〈T ,A〉 where T is the TBox and A is the ABox. A TBox includes a finite set of inclusion axioms on concepts of the form: B⊑C. The ABox contains a finite set of assertions on atomic concepts and roles respectively of the form A(a) and P (a, b) where a and b are two individuals.

The semantics of a DL-Lite KB 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 ∈∆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 \BI , (P -)I ={(y, x)|(x, y)∈P I } and (∃R)I ={x|∃y s.t. (x, y)∈RI }. An interpretation I is said to be a model of a concept inclusion axiom, denoted by I|=B⊑C, iff BI ⊆ C I . Similarly, we say that I satisfies a concept (resp. role) assertion, denoted by I|=A(a) (resp. I|=P(a, b)), iff aI ∈AI (resp. (aI , bI )∈P I ). Note that we only consider DL-Lite with unique name assumption. A KB K is said consistent if it admits at least one model, otherwise K is said inconsistent. A TBox T is said incoherent if there exists at least a concept C such that for each interpretation I which is a model of T , we have C I =∅. In the rest of this paper, we denote by q a query. The semantics of such query is given for instance in [Calvanese et al., 2007].

3 Existing Assertional-Based Preferred Repairs

This section reviews approaches dealing with inconsistent DL-Lite KB that either have been proposed in a DLs setting or have been proposed in a propositional logic setting but need a slight adaptation to be suitable for DL-Lite.

A DL-Lite KB K=〈T ,A〉 with a prioritized assertional base is a DL-Lite KB where A is partitioned into n layers (or strata) of the form A=S1∪. . .∪Sn where each layer Si contains the set of assertions having the same level of priority i and they are considered as more reliable than the ones present in a layer Sj when j>i. Within the OBDA setting, we assume that T is stable and hence its elements are not questionable in the presence of conflicts. Throughout this paper and when there is no ambiguity we simply use "prioritized DL-Lite KB K=〈T , A〉" to refer to a DL-Lite KB with a prioritized assertional base of the form A=S1∪. . . ∪Sn.

Example 1. Let K=〈T ,A〉 such that T ={A⊑¬B} and assume that assertional facts of A come from three distinct sources A=S1∪S2∪S3 such that: S1={B(a),A(b)}, S2={A(a)} and S3={B(c)}. S1 contains the most reliable assertions. S3 contains the least reliable assertions.

In Example 1, it is easy to check that the KB is inconsistent. Coping with inconsistency can be done by first computing the set of repairs, then using them to perform inference. In order to compute the repairs, we use the notion of conflict sets.

3.1 Conflict Sets

Within the OBDA setting, the inconsistency problem is always defined with respect to some ABox, since a TBox may be incoherent but never inconsistent. We now introduce the notion of a conflict as a minimal inconsistent subset of assertions that contradict the TBox.

Definition 1. Let K=〈T ,A〉 be a DL-Lite KB. A subbase C⊆A is said to be a conflict of K iff 〈T , C〉 is inconsistent and ∀ f∈C, 〈T , C \ {f}〉 is consistent.

From Definition 1, removing any fact f from C restores the consistency of 〈T , C〉. When the TBox is coherent, a conflict involves exactly two assertions. Roughly speaking, when priorities are available, restoring the consistency of a conflict comes down to ignoring the facts with the lowest level of priority.

3.2 Preferred Inclusion-Based Repair

In the flat case 1 , one of the main strategies for handling inconsistency comes down to computing the ABox repair of an inconsistent DL-Lite KB. A repair is a maximal subbase of the ABox, denoted by MAR, that is consistent with the TBox.

Definition 2. Let K=〈T ,A〉 be an flat DL-Lite KB. A subbase R⊆A is said to be a maximal assertional-based repair, denoted MAR, of K if: i) 〈T ,R〉 is consistent, and ii) ∀R′ : R⊊R′ ,〈T ,R′ 〉 is inconsistent.

Example 2. Consider T ={A⊑¬B} and A={A(a),B(a), A(b)}. We have C(A)={A(a),B(a)}. The set of MAR is: R1={A(a), A(b)} and R2={B(a), A(b)}.

According to the definition of MAR, adding any assertion f from A\R to R entails the inconsistency of 〈T , R ∪ {f}〉. Moreover, the maximality in MAR is used in the sense of set inclusion. We denote by MAR(A) the set of MAR of A with respect to T . The definition of MAR coincides with the definition of ABox repair proposed in [Lembo et al., 2010]. A query is said to be a universal consequence (or ARconsequence [Lembo et al., 2010]) iff it can be derived from every MAR. The following definition extends the definition of MAR when the DL-Lite ABox is prioritized.

Definition 3. Let K=〈T ,A〉 be a prioritized DL-Lite KB. A preferred inclusion-based repair (PAR) P=P1∪. . .∪Pn of A is such that there is no a MAR P ′=P ′1∪. . .∪P ′n of S1 ∪ . . . ∪ Sn, and an integer i where:

• Pi is strictly included in P ′ i , and
• ∀j = 1..(i -1), Pj is equal to P ′ j

A query q is said to be a PAR-consequence of K, denoted K |=PAR q, iff ∀P∈PAR(A),〈T ,P〉|=2 q where PAR(A) denotes the set of PAR of A.

1 By a flat knowledge base, we mean a base where all the assertions have the same priority.

2 |= denotes the standard entailment used from flat and consistent DL-Lite KB [Calvanese et al., 2007]

This definition of PAR has been largely used in a propositional logic setting (e.g. [Brewka, 1989; Benferhat et al., 1998]) and has been recently used in a DL-Lite framework [Bienvenu et al., 2014]. Definition 3 states that a query q is a universal consequence iff it can be deduced from every preferred inclusion-based repair. Note that the PAR-entailment extends the definition of AR-entailment proposed in [Lembo et al., 2010] when the ABox is prioritized. A PAR of A is obtained by first computing the MAR of S1, then enlarging this MAR as much as possible by assertions of S2 while preserving consistency, and so on.

Example 3. Consider T ={A⊑¬B} and A = S1 ∪S2 where S1={A(a)} and S2 = {B(a),A(b)}. There is exactly one PAR which is: P1={A(a), A(b)}.

Priorities reduce the number of MAR as one can see in Example 3 in comparison with Example 2. Indeed, within a prioritized setting, the notion of PAR operates as a selection function among possible MAR. An important feature in restoring consistency in DL-Lite, when the ABox is layered, is that when there is no conflict in A involving two assertions having the same priority level, then there exists only one PAR.

Proposition 1. Let K=〈T ,A〉 be a prioritized DL-Lite. Let C(A) be the set of conflicts in A. Then if ∀C=(f, g)∈C(A) we have f∈Si, g∈Sj and i̸=j then there exits exactly one PAR.

When a conflict involves two assertions having the same priority level, restoring consistency often leads to several PAR.

3.3 Lexicographic Preferred-Based Repair

This subsection rewrites the cardinality-based or lexicographic inference or prioritized removed set repair, defined in [Benferhat et al., 2014], to the context of inconsistency handling. The lexicographic inference has been widely used in the propositional setting (e.g. [Benferhat et al., 1998]). In fact, one of the major problems of PAR-entailment is the large number of PAR that can be computed from an inconsistent DL-Lite KB. In order to better choose a PAR, one can follow a lexicographic-based approach. We introduce a preferred lexicographic-based repair which is based on the cardinality criterion instead of the set inclusion criterion.

Definition 4. Let PAR(A) be the set of PAR of A. Then L=L1∪. . .∪Ln is said to be a lexicographical preferredbased repair, denoted by PARlex, iff:

1. ∀P=P1∪. . .∪Pn∈PAR(A): there is no i s.t |Pi|>|Li|,
2. ii) ∀j<i,|Pj|=|Lj|.

where |X| is the cardinality of the set X.

A query q is said to be Lex-consequence of K, denoted by K |=lex q, iff ∀L∈PARlex(A):〈T , L〉|=q where PARlex(A) is the set of PARlex of A.

Clearly, using a lexicographic-based approach comes down to select among the set of repairs in PAR(A) the ones having the maximal number of elements. We propose in the two next subsections inconsistency-tolerant inferences based only on selecting one preferred repair.

3.4 Possibilistic-Based Repair

One of the interesting aspects of possibilistic KBs, and more generally weighted KBs, is the ability of reasoning with partially inconsistent knowledge [Dubois and Prade, 1991]. As shown in [Benferhat and Bouraoui, 2013], the entailment in possibilistic DL-Lite, an adaptation of DL-Lite entailment within a possibility theory setting, is based on the selection of one consistent, but not necessarily maximal, subbase of K. This subbase is induced by a level of priority called the inconsistency degree. The following definition reformulates the definition of inconsistency degree to fit the case where A is prioritized.

Definition 5. Let K=〈T ,A〉 be an inconsistent prioritized DL-Lite KB.

• The inconsistency degree of K, denoted Inc(K), is defined as follows: Inc(K)=i + 1 iff 〈T , S1 ∪ . . . ∪ Si〉 is consistent and 〈T , S1 ∪ . . . ∪ Si+1〉 is inconsistent.
• A query q is said to be a π-consequence of K, denoted K |=π q, iff 〈T , π(A)〉|=q where π(A) is the repair of A defined by π(A)=S1∪. . .∪S(Inc(K)-1).

The subbase π(A) is made of the assertions having priority levels that are strictly less than Inc(K). If K is consistent then we simply let π(A)=A. The π-entailment is cautious in the sense that assertions from A\π(A) that are not involved in any conflict are inhibited because of their low priority levels.

3.5 Linear-Based Repair

One way to recover the inhibited assertions by the possibilistic entailment is to define the linear-based repair fromA. The following definition introduces the notion of linear subset. Linear entailment has been used in a propositional logic setting in [Nebel, 1994] and has been applied for a DL setting (e.g. [Qi et al., 2011]).

Definition 6. Let K=〈T , A〉 be a prioritized DL-Lite KB. The linear-based repair of A, denoted ℓ(A), is defined as follows:

1. For i=1: ℓ(S1)=S1 if 〈T , S1〉 is consistent. Otherwise ℓ(S1)=∅.
2. ii) For i>1: ℓ(S1∪. . .∪Si)=ℓ(S1∪. . .∪Si-1)∪Si if 〈T , ℓ(S1∪. . .∪Si-1)∪Si〉 is consistent. Otherwise ℓ(S1∪. . .∪Si)=ℓ(S1∪. . .∪Si-1).

A query q is a linear consequence (ℓ-consequence) from K, denoted K |=ℓ q, iff 〈T , ℓ(A)〉 |= q.

Clearly, ℓ(A) is obtained by discarding a layer Si when its facts conflict with the ones involved in the previous layer. The subbase ℓ(A) is unique and consistent with T . The following proposition gives the complexity of π-entailment and ℓ-entailment which are in P.

Proposition 2. The computational complexity of πentailment is in O(cons) where cons is the complexity of consistency checking of standard DL-Lite. The complexity of ℓ-entailment is in O(n ∗ cons) where n is the number of strata in the KB.

The ℓ-entailment is more productive than π-entailment, but incomparable with PAR-entailment and Lex-entailment. However from Definitions 5 and 6, both π(A) and ℓ(A) are not guaranteed to be maximal.

4 Sensitivity to the Prioritized Closure

Before presenting new strategies that only select one preferred repair, we briefly introduce the concept of a prioritized closure and check which among existing approaches is sensitive to the use of the deductive closure. In fact, the inference relations given in the previous section can be either defined on 〈T ,A〉 or on 〈T , cl(A)〉 where cl denotes the deductive closure of a set of assertions. Let us first define the notion of a deductive closure in DL-Lite.

Definition 7. Let K=〈T ,A〉 be a flat DL-Lite KB. Let Tp be the set of all positive inclusion axioms of T 3 . We define the deductive closure of A with respect to T as follows: cl(A)={B(a): 〈Tp,A〉|=B(a) where, B is a concept of T and a is an individual of A}∪{R(a, b): 〈Tp,A〉|=R(a, b), where R is a role of T and a,b are individuals of A}.

The use of a deductive closure of an ABox fully makes sense in DL languages, while for instance in propositional logic the closure of an inconsistent KB trivially leads to produce the whole language. The following definition extends Definition 7 to the prioritized case.

Definition 8. Let K=〈T , A〉 be a prioritized DL-Lite KB. We define the prioritized closure of A with respect to T , simply denoted cl(A), as follows: cl(A) = S ′1 ∪ . . . ∪ S ′n where:

Example 4. Consider T = {A ⊑ B, B ⊑ C, C ⊑¬D} and A = S1 ∪ S2 where S1 = {A(a), D(a)} and S2 = {B(b)}. Using Definition 8, we have cl(A) = S ′1 ∪ S ′2 where S ′1 = {A(a), B(a), C(a), D(a)} and S ′2 = {B(b), C(b)}.

An important feature of π-inference and ℓ-inference is that they are insensitive to the deductive closure. This is not the case with PAR-entailement or Lex-entailment, more precisely:

Proposition 3. Let K=〈T ,A〉 be a prioritized DL-Lite KB. Then ∀q: i) 〈T ,A〉 |=π q iff 〈T , cl(A)〉 |=π q, ii) 〈T ,A〉 |=ℓ q iff 〈T , cl(A)〉 |=ℓ q, and iii) PAR-entailment and Lexentailment applied to 〈T ,A〉 are incomparable with the one applied to 〈T , cl(A)〉.

Example 5 (Counterexample for PAR-entailment). Let T = {A⊑¬B,A⊑D,D⊑¬E} and A=S1∪S2 where S1={A(a), B(a)} and S2={E(a)}. We have P1={A(a)} and P2= {B(a),E(a)}. Consider now the deductive closure: we have cl(S1)={A(a),B(a),D(a)} and cl(S1 ∪ S2)={E(a)}. We also have: P1={A(a),D(a)} and P2={B(a),D(a)}. One can check that i)D(a) is a PAR-entailment of 〈T , cl(A)〉 while it does not follow from 〈T , A〉, ii) E(a)∨A(a) is a PARentailment of 〈T , A〉 while it does not follow from 〈T , cl(A)〉.

Example 6 (Counterexample Lex-entailment). Let us consider the following cases:i) T ={A⊑¬B,A⊑C} and A= S1={A(a),B(a)}. We have 〈T ,A〉̸|=lexC(a) while 〈T , cl(A)〉|=lexC(a). ii) T ={A⊑¬B,B⊑F,F⊑¬A,C⊑¬B } and S1={A(a),B(a)} and S2={C(a)}. We only have a lexicographic subbase of 〈T , S1 ∪S2〉 which is L={A(a),C(a)} hence 〈T ,L〉|=lexC(a). Besides cl(S1)={A(a),B(a), F(a)} and cl(S2)={C(a)}. We also have one lexicographic subbase of 〈T , cl(A)〉 which is L={B(a), F (a)} hence 〈T , cl(A)〉̸|=lexC(a).

3 Positive inclusion axioms are of the form B1 ⊑ B2.

5 New Strategies for Selecting One Repair

This section presents new strategies that only select one preferred repair. Selecting only one repair is important since it allows efficient query answering once the preferred repair is computed. These strategies are based on the so-called nondefeated entailment, described in the next section, by adding different criteria: deductive closure, cardinality, consistency and priorities.

5.1 Non-Defeated Repair

One way to get one preferred repair is to iteratively apply, layer per layer, the intersection of maximally assertionalbased repairs (i.e. MAR). More precisely:

Definition 9. Let K=〈T ,A〉 be a prioritized DL-Lite KB. We define the non-defeated reapir, denoted by nd(A)=S ′1∪. . .∪S ′n , as follows:

A query q is a non-defeated consequence (nd-consequence) of K, denoted K |=nd q, iff 〈T , nd(A)〉 |= q.

As it will be shown below, the non-defeated entailment corresponds to the definition of non-defeated subbase proposed in [Benferhat et al., 1998] within a propositional logic setting. However, contrarily to the propositional setting i) the non-defeated repair can be applied on A or its deductive closure cl(A) which leads to two different inference relations, ii) the non-defeated repair is computed in polynomial time in a DL-Lite setting while its computation is hard in a propositional logic setting. Let us now rephrase non-defeated repair (Equation 1) using the concept of free inference. First, we recall the notion of non-conflicting or free elements.

Definition 10. Let K=〈T ,A〉 be DL-Lite KB. An assertion f∈A is said to be free iff ∀C∈C(A):f /∈C.

Intuitively, free assertions are those assertions that are not involved in any conflict. Let S ∈ A be a set of assertions, we denote by free(S) the set of free assertions in S. The notions of free elements were originally proposed in [Benferhat et al., 1992] in a propositional logic setting. The definition of freeentailment is also equivalent to the IAR-entailment given in [Lembo et al., 2010] for flat DL-Lite KBs. The following proposition shows that the notion of free(A), extended to the prioritized case, leads to a non-defeated repair.

Proposition 4. The non-defeated repair, given in Definition 9, is equivalent to:

where ∀i : free(S1 ∪ . . . ∪ Si) denotes the set of free assertions in (S1 ∪ . . . ∪ Si).

The following proposition shows that the non-defeated repair is consistent and its computation is in P.

Algorithm 1 linear-based non-defeated repair

Input: K = 〈T , A〉 where A = S1 ∪ . . . ∪ Sn Output: ℓnd(A) 1: ℓnd(A) = free(S1) 2: for i = 2 to n do 3: if 〈T , ℓnd(A) ∪ Si〉 is consistent then 4: ℓnd(A) ← ℓnd(A) ∪ Si 5: else 6: ℓnd(A) ← ℓnd(A) ∪ f ree(Si ∪ ℓnd(A))

Proposition 5. Let K=〈T ,A〉 be a DL-Lite KB. Let nd(A) be its non-defeated repair. Then i) 〈T , nd(A)〉 is consistent, and ii) the complexity of computing nd(A) is in P.

5.2 Adding the Deduction Closure

The non-defeated inference, when it is defined on A, is safe since it only uses elements of A which are not involved is conflicts. One way to get a more productive inference is to use cl(A) instead of A. Namely, we define, a closed nondefeated repair, denoted clnd(A) = S ′1 ∪ . . . ∪ S ′n , such that:

Example 7. Consider T ={A⊑¬B,B⊑C} and A=S1∪ S2 where S1={A(a)} and S2={B(a)}. We have MAR(cl(S1))={A(a)} and MAR(cl(S1 ∪ S2))={(A(a), C(a)), (B(a), C(a))}. Then clnd(A)={A(a), C(a)}.

Contrarily to π-entailment and ℓ-entailment, the following proposition shows that nd-inference is sensitive to the use of the deductive closure.

Proposition 6. Let K=〈T ,A〉 be a DL-Lite KB. Then ∀q: if 〈T ,A〉 |=nd q then 〈T , cl(A)〉 |=nd q. The converse is false.

For the converse it is enough to consider T ={E⊑¬B, B⊑C,E⊑C} and A=S1={E(a), B(a)}. We have nd(A)=∅ and nd(cl(A))={C(a)}. Hence C(a) is an nd-consequence of 〈T , cl(A)〉 but it is not an nd-consequence of 〈T ,A〉.

5.3 Combining Linear Entailment and Non-Defeated entailment: Adding consistency

We present a new way to select a single preferred assertionalbased repair. It consists in slightly improving both linear entailment and nd-entailment, where rather to ignore a full stratum, in case of inconsistency, one can only ignore conflicting elements. The linear-based non-defeated repair, denoted by ℓnd(A), is given by Algorithm 1.

Clearly ℓnd(A) is consistent and it is more productive than π(A) and ℓ(A), but it remains incomparable with other approaches. Note that ℓnd(A)∪free(Si ∪ ℓnd(A))=⋂{R : R ∈ MAR(Si ∪ ℓnd(A)) and R ∪ ℓnd(A)} is consistent. Hence, ℓnd(A) extends nd(A) by only focusing on MAR(Si ∪ℓnd(A)) that are consistent with ℓnd(A). The nice feature of ℓnd-entailment is that the extension of ℓ-entailment and nd-entailment is done without extra computational cost. More precisely, computing ℓnd(A) is in P.

5.4 Introducing Consistency and Cardinality Criterion

A natural question is whether one can introduce a cardinality criterion, instead of set inclusion criterion, in the definition of non-defeated repair given by Equation 1. Namely, we define the cardinality-based non-defeated repair as follows:

Definition 11. Let K=〈T ,A〉 be a prioritized DL-Lite KB. The cardinality-based non-defeated repair, denoted by nd(A)card=S ′1∪. . .∪S ′n , is defined as follows:

where MARcard(S)={R:R∈MAR(S) and ∄R′∈ MAR(S) s.t |R′ |>|R|}.

One main advantage of this approach is that it produces more conclusions that the standard non-defeated inference relation. Namely, nd(A)⊆nd(A)card where nd(A) and nd(A)card are respectively given by Equations 1 and 3. The converse is false.

Let T ={A⊑¬B, B⊑¬C} and A=S1∪S2 where S1={A(a),B(a)} and S2={C(a)}. We have nd(A)=∅ while nd(A)card={A(a),C(a)}. The main limitation of nd(A)card is that it may be inconsistent with T as it is illustrated with the following example.

Example 9. Consider T ={A⊑¬B,A⊑¬C} and A=S1∪S2 where S1={A(a)} and S2={B(a),C(a)}. Using Equation 3, we have S ′1={A(a)} and S ′2={B(a),C(a)}. Clearly, nd(A)card=S ′1∪S ′2 contradicts T .

One way to overcome such limitation is to only select MARcard of (S1∪. . .∪Si) that are consistent with (S ′1∪. . .∪S ′ i-1 ), namely:

Definition 12. Let K=〈T ,A〉 be an prioritized DL-Lite KB. We define the "consistent cardinality-based non-defeated repair", denoted by consnd(A)card = S ′1∪. . .∪S ′n , as follows:

∀i = 2, .., n : S ′ i =⋂{R:R∈MARcard(S1∪. . .∪Si) and R is consistent with S ′1∪. . .∪S ′ i-1}

Contrarily to nd(A)card, consnd(A)card is always consistent.

Example 10. Consider the example where T ={A⊑¬B, A⊑¬C} and A=S1∪S2 where S1={A(a)} and S2={B(a), C(a)}. We have S ′1={A(a)} and S ′2=∅. Clearly consnd(A)card is consistent with T .

5.5 Adding Priorities

In the definition of nd-inference, given by Equation 1, a flat notion of MAR (maximally inclusion-based repair) has been used. A natural way to extend the nd-entailment is to use a prioritized version of MAR (i.e. PAR), namely:

Definition 13. Let K=〈T ,A〉 be an prioritized DL-Lite KB. We define the prioritized inclusion-based non-defeated repair, denoted by pind(A)=S ′1∪. . .∪S ′n , as follows:

The following proposition shows that there is no need to consider all S ′ i for i<n when computing pind(A), namely:

Besides, a cardinality-based version of Equation 4, denoted by pind(A)lex=S1∪. . .∪Sn, can be defined as follows:

Lastly, both pind(A) and pind(A)lex can be defined on cl(A) instead of A or be defined on closed repairs instead of repairs themselves. This leads to new inferences strategies that only select one preferred subbase.

6 Comparative Analysis and Experimental Evaluation

From a computational complexity point of view, πentailment, ℓ-entailment, nd-entailment and ℓnd-entailment and the entailments based on their closures, are the most promising ones since both computing the repair and query answering are tractable. For other strategies based on the ndinference, computing the repairs is a hard task, but it is done ONCE. Answering queries, when the single repair is computed, is efficiently computed since it has the same complexity as in standard DL-Lite.

From productivity, Figure 1 summarizes the relationships between main entailments considered in the paper when the ABox is prioritized. Note that for the sake of simplicity, we do not make reference in Figure 1 to inferences defined on cl(A). From Figure 1, π-entailment is the most cautious relation. Adding priorities, cardinality and consistency to the definition of nd-entailment allow to provide more productive inference relations. However ℓ-entailment remains incomparable with the nd-entailment, since layers including non free assertions can be present in ℓ(A). Moreover, ℓnd(A) is incomparable with other approaches. Within the prioritized setting, nd(A) plays the same role with respect to PAR as free(A) for MAR in the flat case. As a consequence, each nd-consequence of A is also a PAR-consequence of A. The converse is false. Moreover, it is well-known that each PARentailment is also a Lex-entailment and the converse is false, since the Lex-entailment only uses subsets of prioritized repair (PAR).

We now provide an experimental evaluation where we considered a TBox containing 100 negative inclusion axioms with a proportion of conflicts at least equal to 1/5 per assertion. This TBox is adapted from the DL-LiteR university benchmark proposed in [Lutz et al., 2013]. We use the Extended University Data Generator (EUDG) 4 to generate the ABox assertions. Once the ABox is produced, we fit it to our setting using 4 strata until 7 strata. Moreover the computation of conflicts is performed layer per layer. Note that the time used for computing the conflicts is not included in the time used for computing the repairs, since this is done in a polynomial time. Said differently, computing conflicts is negligible with respect to computing repairs.

Table 1a gives the experimental results of the computation of MAR and MARcard. One can see that using the cardinality criterion instead of the set inclusion one refines the result and improves the computation time of the repairs. Moreover, an important influential parameter when computing the repairs is the number of occurrences of an assertion in conflicts. Namely, the more an assertion is recurring in conflicts the more the conflict resolution has better chances to be achieved. For instance, in Table 1a considering the case of 37 conflicts, by increasing the percentage of occurrences of some assertions in conflicts, we obtain 23082 MAR in 136ms instead of 16815986 in 206089ms. In such case, the number of Lex decreases also where we compute only 24 #MARcard having cardinality equal to 14 assertions. Similar results on the effect of the number of occurrences of assertions in conflicts are provided [Pivert and Prade, 2010; D.Deagustini et al., 2014].

Now, concerning PARlex, we also use the notion of minimal inconsistent subsets where the minimality refers to a lexicographic ordering. Table 1b gives the results on the computation of PARlex and the main repairs given in this paper. One can first observe that given an ABox A whatever is its size, computing π or ℓ does not need long computation time as needed by inconsistency checking. Regarding now the computation of the non-defeated repair, it depends on the number of conflicts in the ABox. Another parameter that also influences the results is the number of layers. This can be clearly seen when computing #PARlex. Indeed, the number of PARlex decreases as the number of layers increases. Clearly, more the stratification of the ABox is important more the conflicts resolution has better chances to be achieved.

7 Conclusion

This paper focuses on how to produce a single preferred repair from a prioritized inconsistent DL-Lite KB based on the notion of the non-defeated inference relation. We first reviewed some well-known approaches that select one repair (such as possibilistic repair or linear-based repair) or several repairs (such as preferred inclusion-based repairs or lexicographic-based repairs). Then, we presented different

4 available at https://code.google.com/p/combo-obda/

• (b) Number of conflicts, number of strata, time taken to compute π, ℓ, nd and PARlex and number of computed PARlex.

Table 1: Experimental evaluation of main inferences proposed in this paper.

strategies for selecting one preferred repair. These strategies have as starting point the non-defeated repair and mainly add one/several of the four main criteria: priorities, deductive closure, cardinality and consistency.

Acknowledgment

This work has been supported by the French National Research Agency. ASPIQ project ANR-12-BS02-0003