Inconsistency Measures for Repair Semantics in OBDA

1 Introduction

In this paper we place ourselves in the OBDA setting and investigate query answering over a set of fact bases enriched by the ontology [Poggi et al., 2008]. One of the main challenges of reasoning in OBDA applications is handling the inherent inconsistency that might occur amongst independently built data sources partially describing the same knowledge of interest [Benferhat et al., 1997; Lukasiewicz et al., 2015; Lembo et al., 2015; Hecham et al., 2017b]. Classically inconsistent tolerant semantics consider all maximally consistent subsets of a fact base (called repairs) that they manipulate using a modifier (expansion, splitting, etc.) and an inference strategy (intersection, universality, etc.) [Baget et al., 2016a].

Using all repairs might be inappropriate for certain applications that would rather focus on particular sources of knowledge. For instance, when considering more reliable knowledge (i.e. sensor information, provenance data etc.) one could only consider repairs using mostly facts from such sources. Preferences on facts have been used for inconsistency tolerant reasoning in [Staworko et al., 2012]. In that setting, the authors suppose that the preference order on the facts is given but unfortunately, this is not always the case. In such cases we propose to use the inconsistency of the elements of the knowledge base (KB) as an intrinsic preference on the facts. Such inherent preference on the facts (i.e. facts that are more or less guilty for the inconsistencies) generates a preference on the repairs that are containing these facts (i.e. repairs that contain more or less controversial facts). In this paper, we propose a framework that takes into consideration the inconsistency on the facts when using the repairs for query answering and restricts the set of repairs to the "best" with respect to inconsistency values. Since we consider a subset of repairs we obtain more answers than classical inconsistency tolerant query answering.

In this paper, we characterise desirable properties of such frameworks like free facts entailment, syntax independence and reliability preservation. We also provide an implementation of our approach and discuss its performance. The salient point of this paper lies in it being the first approach in the literature capable of ranking repairs using only the inherent structure of the KB. This is a significant result as our approach is applicable on a large variety of domains without requiring additional preference information. Furthermore, we show the significance and the practical interest of our approach using the real data collected in the framework of the Pack4Fresh project for reducing food wastes. During this project, we collected data using an online poll from a set of professionals of the food industry, including wholesalers, quality managers, floorwalkers and warehouse managers, about food packagings and their characteristics. The framework was able to rank the repairs efficiently and the results were then analysed and evaluated by experts from the packaging industry.

2 Background Notions

The existential rules language [Cal`ı et al., 2009] is composed of formulae built with the usual quantifiers (∃, ∀) and only two connectors: implication (→) and conjunction (∧) and is composed of facts, rules and negative constraints. A fact is a ground atom of the form p(t1, . . . , tk) where p is a predicate of arity k and ti, with i ∈ [1, . . . , k], constants. The set of all possible facts is denoted by A. An existential rule is of the form ∀-→X, -→Y H[-→X, -→Y ] → ∃-→ZC[-→Z , -→X] where H and C are existentially closed atoms or conjunctions of existentially closed atoms and -→X, -→Y , -→Z their respective vectors of variables. A rule is applicable on a set of facts F if and only if there exists a homomorphism [Baget et al., 2016b] from H to F. Applying a rule to a set of facts (also called chase) consists of adding the set of atoms of C to the facts according to the application homomorphism. Different chase mechanisms use different restrictions that prevent infinite redundancies [Baget et al., 2011]. Here, we use recognisable classes of existential rules where the chase is guaranteed to stop [Baget et al., 2011]. A negative constraint is a rule of the form ∀-→X, -→Y H[-→X, -→Y ] → ⊥ where H is an existentially closed atom or conjunctions of existentially closed atoms, -→X, -→Y , their respective vectors of variables and ⊥ is absurdum. Please note that the number of atoms in H is not bounded and that negative constraints generalise simple binary conflicts that can easily be translated between the two representations: ¬p( ⃗X) is transformed into np( ⃗X) and the negative constraint p( ⃗X) ∧np( ⃗X) → ⊥ is added to the rules.

We say that F1 entails F2 denoted by F1 |= F2 if and only if there is a homomorphism from the set of atoms in F2 to the set of atoms in F1 where F1 and F2 are two existentially closed conjunctions of atoms. A conjunctive query is an existentially quantified conjunction of atoms. For readability, we restrict ourselves to boolean conjunctive queries, which are closed formulas (the framework and the obtained results can be extended to general conjunctive queries). The set of all possible boolean conjunctive queries is denoted by Q.

Definition 2.1. A knowledge base K is a tuple K = (F,R,N) where F is a finite set of facts, R a set of existential rules and N a set of negative constraints.

The set of all KBs is denoted by Kbs. The saturation of F by R is the set of all possible atoms and conjunctions of atoms that are entailed, after using all possible rule applications from R over F until a fixed point. The output of this process is called the closure and is denoted by SatR(F). A set F is said to be R-consistent if no negative constraint hypothesis can be entailed, i.e. SatR(F) ̸|= ⊥. Otherwise, F is said to be R-inconsistent. The ground closure of a set F by R, denoted CℓR(F), is different from the closure of the saturation since it only keeps ground atoms. Namely, CℓR(F) = {ground atoms a | a ∈ SatR(F)}. The notion of ground closure is widely used in the literature and especially when dealing with inconsistency tolerant inference since computing the intersection of closures is ambiguous. Indeed, atoms resulting from the application of rules with existential variables contain null variables which makes the intersection of two closures undefined.

We assume that the existential rules are skolemized [Marnette, 2009], namely ∀-→X, -→Y H[-→X, -→Y ] → ∃-→Z C[-→Z , -→X] will be replaced with ∀-→X, -→Y H[-→X, -→Y ] → C[f(X), -→X] where f is a new symbol function. Using the above mentioned methodology in our setting enables us to have the closure equal to the ground closure and guarantees a finite saturation.

We recall the notion of minimal inconsistent sets and maximal consistent sets of a KB [Reiter, 1987].

Definition 2.2. Let K = (F, R, N) be a KB, we say that:

• Minimal R-inconsistent sets of K are defined as MI(K) = {X ⊆ F | SatR(X) |= ⊥ and ∀X′ ⊂ X, SatR(X′ ) ̸|= ⊥}. A fact f ∈ F is called a free fact if and only if there is no X ∈ MI(K) s.t. f ∈ X.
• Maximal for set inclusion R-consistent sets (repairs) of K are defined as Comax(K) = {X ⊆ F | SatR(X) ̸|= ⊥ and for every X ⊂ X′ , SatR(X) |= ⊥}

In the OBDA setting rules and constraints act as an ontology used to "access" different data sources. These sources are prone to inconsistencies. As it is common in the literature, we suppose that the rules are compatible with the negative constraints, i.e. the union of those two sets is satisfiable [Lembo et al., 2010]. Indeed, the ontology is believed to be reliable as it is the result of a robust construction by domain experts. However, as data can be heterogeneous due to merging and fusion, the data is assumed to be the source of inconsistency.

3 The Ranking-Based Inference Framework

In this section, we introduce the ranking-based inference framework (RIF) and its three main components: the inconsistency value, the lifting function and the inconsistency tolerant inference. It is similar to the work in argumentation by [Konieczny et al., 2015], where only the best extensions are used for reasoning. The section is organised as follows: in Section 3.1, we recall the notion of Drastic and MI Shapley inconsistency values, in Section 3.2, we give examples of lifting functions and in Section 3.3, we show how inconsistency tolerant inferences are modified in order to be used in the framework.

An inconsistency measure according to [Grant and Hunter, 2011] is a function that, given a KB K = (F,R,N), associates a number to each set of facts.

Definition 3.1. An inconsistency measure is a function I : Kbs × 2A → R such that for every K = (F,R,N) ∈ Kbs and C ∈ 2A, I(K,C) = 0 if and only if C is R-consistent, I(K,C ∪ C ′ ) ≥ I(C) and if α is a free fact of K, then I(K,F) = I(K,F\{α}). For readability purposes, we will use the notation I K(C) instead of I(K,C) and I(C) if the working KB K is obvious.

An inconsistency value is a function that associates a number to each fact of a KB K. Many inconsistency values were defined by [Hunter and Konieczny, 2010] using existing inconsistency measures and the Shapley value from coalitional game theory. We introduce a framework that makes use of these inconsistency values together with a lifting function and an inconsistency tolerant inference relation to improve the productivity of query answering for an inconsistent KB.

Our framework is based on three layers. First, an inconsistency value is used to calculate the score of each fact of K. We previously mentioned Shapley inconsistency values, but any function returning a score for each fact of K can be used.

Definition 3.2. An inconsistency value is a function S : Kbs× A → R. Let ⪰SA be the total, reflexive and transitive binary order on A with respect to K and S defined as: for every a, b ∈ A, a ⪰SA b if and only if S(K, a) ≤ S(K, b). For readability purposes, we write Sa(K) instead of S(K, a).

Second, we need a lifting function, i.e. a function that compares the set of repairs, based on the individual scores of facts with respect to an inconsistency value. A criterion of comparison would be to evaluate the "strongest" fact of each set. A generalisation of this criterion is the so-called leximax which, in the case where the best facts are equally strong, proceeds to compare the next best fact of each set. Please note that the set of all total, reflexive and transitive binary orders on X is denoted by ⪰X.

Definition 3.3. A lifting function is a function L : 2A× ⪰A→⪰2A. For readability purposes, we use the notation L⪰(X) for L(X,⪰). Furthermore, (E,E′ ) ∈ L⪰(X) means that E is better than or equal to E′ .

Third, we use an inconsistency tolerant inference relation restricted to the best repairs sets ranked by the lifting function to answer the query. At this step, one can use the usual inconsistency tolerant inference relations such as AR, IAR, ICR or any of the modifier-based semantics of [Baget et al., 2016a]

Definition 3.4. An inconsistency tolerant inference relation is a function |=: Kbs × Q → {T rue, F alse}.

Based on the previous notions, we define our framework.

Definition 3.5. A ranking-based inference framework (RIF) is a tuple RIF = (S, L, |=) where S is an inconsistency value, L is a lifting function and |= is an inconsistency tolerant inference. The top result of RIF = (S, L, |=) on a KB K = (F,R,N) is O(RIF,K) = {E ∈ Comax(K) | for all E′ ∈ Comax(K), (E, E′ ) ∈ L⪰SF (F)}.

3.1 RIF Inconsistency Value

An inconsistency value is a function that associates a value to each fact of the KB. This value is supposed to be higher the more a fact is conflicting with the other facts. In this paper, we make the choice to focus on the Shapley inconsistency value introduced by [Hunter and Konieczny, 2010] because it possesses many desirable properties as will be shown in Proposition 3.1 below. The Shapley inconsistency value uses notions from game theory to measure the responsibility of each fact to the overall inconsistency of the KB.

Definition 3.6. Let I be an inconsistency measure, K = (F, R, N) a KB and f ∈ F, the Shapley inconsistency value corresponding to I, noted SI is defined as:

Note that if one considers F as the vector (f1, f2, . . . , fn), then SI (K) is the vector of corresponding Shapley inconsistency values, i.e. SI (K) = (SIf1 (K), SIf2 (K), . . . , SIfn (K)).

Let K = (F,R,N) be a KB, the inconsistency values investigated by this paper are the following:

• The drastic Shapley inconsistency value is computed by using the following inconsistency measure:

• The MI Shapley Inconsistency value is computed by using the following inconsistency measure:

We now show that every Shapley inconsistency value satisfies Distribution, Symmetry and Minimality. The result and its proof are similar to that of [Hunter and Konieczny, 2010].

Proposition 3.1. Let I be an arbitrary inconsistency measure and K = (F,R,N) a KB, the Shapley inconsistency value corresponding to I satisfies:

• (Distribution) ∑ a∈F SIa (K) = I K(F)
• (Symmetry) If a, b ∈ F such that for all X′ ⊆ F, a, b /∈ X′ we have I K(X′ ∪{a}) = I K(X′ ∪{b}) then it holds that SIa (K) = SIb (K)
• (Minimality) If a is a free fact of K then SIa (K) = 0

In Example 3.1, we show how the MI and drastic inconsistent values are computed from a simple KB.

Example 3.1. Let us consider the KB K = (F, R, N) where F = {d(M), a(M), c(M), b(M, S)}, R = {∀x(c(x) ∧ b(x, S) → u(x))} and N = {∀x (d(x) ∧ a(x) → ⊥), ∀x (u(x) ∧ d(x) → ⊥), ∀x (u(x) ∧ a(x) → ⊥)}. We have that SId d(M) (K) = 4× 1 12 = 13 and SIMI d(M) (K) = 4× 1 12 + 14 ×2 = 5 6 . Thus, here we have that F = {d(M), a(M), c(M), b(M, S)} and SId (K) = ( 13 , 1 3 , 16 , 16 ) and SIMI (K) = ( 5 6 , 56 , 2 3 , 2 3 ). Since the higher score means being more inconsistent, the resulting ranking on facts, for both inconsistency values, is c(M) ∼ b(M, S) ≻ d(M) ∼ a(M).

We recall that we work with the total, reflexive and transitive ranking ⪰SF on F extracted from the inconsistency value.

3.2 RIF Lifting

A lifting function L⪰ compares sets of elements with respect to the ranking ⪰ and returns a total order on the sets.

Let us first introduce the sort relation that will be used in order to define the L⪰leximax notion below. Given a set of elements X = {x1, x2, . . . , xn} and a total, reflexive and transitive binary relation ⪰ on X, sort(X,⪰) returns a sorted vector (x1, x2, . . . , xn) such that for every xi, xj, we have that xi ⪰ xj if and only if i ≤ j. The element at position i in the vector sort(X, ⪰) is denoted by sorti(X, ⪰). Note that the returned vector is not necessarily unique due to the fact that some elements might be equivalent, i.e. xi ∼ xj.

In this paper, we consider two possible instantiations of the lifting function L. The L⪰max lifting function compares the subsets with respect to their maximal elements and L⪰leximax compares the elements after sorting them in decreasing order. Let Y be a set of elements, ⪰ a ranking on Y, E,E′ ∈ 2Y , sort(E,⪰) = (x1, x2, . . . , xn) and sort(E′ ,⪰) = (x′1 , x′2 , . . . , x′m). We say that:

• (E,E′ ) ∈ L⪰max (Y ) if and only if max(E) ⪰ max(E′ ), where max(X) = sort1(X, ⪰).
• (E,E′ ) ∈ L⪰leximax (Y ) if and only if one of the following holds: (1) m = n and for every i ∈ {1, . . . , n}, xi ∼ x′i , (2) there exists i ∈ {1, . . . ,min(m, n)} s.t. xi ≻ x′i and for every j ∈ {1, . . . , i - 1}, xj ∼ x′j or (3) n > m and for every i ∈ {1, . . . ,m}, xi ∼ x′i .

Example 3.2 (Ex 3.1 cont.). Let us consider the RIF RIF = (SId , L⪰leximax , |=). We have for every R ∈ Comax(K) \ {c(M), b(M, S)}, it holds that ({c(M), b(M, S)},R) ∈ L⪰leximax (F) but (R, {c(M), b(M, S)}) /∈ L⪰leximax (F) and thus, O(RIF, K) = {{c(M), b(M, S)}}

3.3 RIF Inference

Inconsistency-Tolerant Query Answering is a challenging problem that received a lot of attention recently. We recall that we place ourselves in the context of OBDA, where the ontology is assumed to be satisfiable and fully reliable. In the following, we recall some of the most well-known inconsistency tolerant inferences that have been proposed in the literature. Let K = (F,R,N) be a KB and q be a boolean conjunctive query. Then:

• q is said to be AR entailed by K denoted by K |=AR q if and only if for every R ∈ Comax(K), CℓR(R) |= q
• q is said to be IAR entailed by K denoted by K |=IAR q if and only if CℓR ( ⋂ R∈Comax(K) R) |= q
• q is said to be ICR entailed by K denoted by K |=ICR q if and only if ⋂ R∈Comax(K) CℓR(R) |= q

Example 3.3 (Ex 3.1 cont.). A query q = ∃x(c(x)) is not AR, IAR nor ICR entailed. Indeed, we cannot entail q from the closure of all the repairs, the intersection of the closure of all the repairs nor the closure of the intersection of all repairs.

We propose here to reuse AR, IAR, ICR by restricting them to the output of a RIF instead of the whole set of repairs.

Definition 3.7. Let x ∈ {AR, IAR, ICR}. |=RIF x denote the restriction of |=x to the output of RIF instead of the whole set of repairs.

For instance, the restricted version of AR will be denoted by |=RIF AR and defined as K |=RIF AR q if and only if for every R ∈ O(RIF, K), CℓR(R) |= q.

Example 3.4 (Ex 3.2 cont.). Let q be the query ∃x(c(x)). The query q is AR, IAR and ICR entailed with respect to RIF since O(RIF, K) = {{c(M), b(M, S)}}.

4 RIF Results

This section presents a characterisation of the framework in terms of properties and general productivity results. In Section 4.1, we show some desirable properties of the framework and how such component properties relate to framework properties. In Section 4.2, we show an algorithm for computing the output of the framework and its performance on a given set of data. In Section 4.3, we explicit the use of our framework on a real life scenario.

4.1 RIF Properties

In this section, we show that the desirable properties on the components can lead to desirable properties on the entire framework. First, we introduce desirable properties for general inconsistency values. The Minimality property states that a free fact should have the lowest score. The Flawed property conveys the idea that a non-free fact should have a strictly positive score. Lastly, the Bottom Facts property states that an R-inconsistent fact should have the score 1.

Minimality For any KB K and every free fact a of K, it holds that SIa (K) = 0.

Flawed For any KB K and every non free fact a of K, it holds that Sf (K) > 0.

Bottom Facts For any KB K = (F,R,N) and f ∈ F such that {f} is R-inconsistent, it holds that Sf (K) = 1

The R-Append and N-Append properties are satisfied if the addition of a rule or a negative constraint to a KB cannot decrease the score of any fact.

R-Append For any KB K = (F,R,N) and r /∈ R, if K′ = (F,R∪ {r},N) then for every f ∈ F, Sf(K) ≤ Sf (K′ ).

N-Append For any KB K = (F,R,N) and n /∈ N, if K′ = (F, R, N ∪ {n}) then for every f ∈ F, Sf (K) ≤ Sf (K′ ).

The Abstraction-I property states that an inconsistency value should not rely on the names of constants or predicates.

Abstraction-I For any KB K and any isomorphism 1 γ such that γ(K) = K′ , we have that for every f ∈ F, Sf (K) = Sγ(f)(K′ ).

The Cardinality-MI property says that the score is based on minimal inconsistent subsets. Namely, if the score of a fact is strictly inferior to the score of an other fact, it means that the number of minimal inconsistent sets the first fact belongs to is strictly lower than the number of minimal inconsistent sets the second facts belongs to.

Cardinality-MI For any KB K = (F,R,N) and f, f ′ ∈ F such that Sf(K) < Sf ′(K) then |{X ∈ MI(K) | f ∈ X}| < |{X ∈MI(K) | f ′ ∈ X}|

Proposition 4.1. It holds that:

• SIMI satisfies Minimality, Flawed, Abstraction-I, Bottom Facts and does not satisfy Cardinality-MI, RAppend and N-Append.
• SId satisfies Minimality, Flawed, Abstraction-I and does not satisfy Cardinality-MI, R-Append, N-Append and Bottom Facts.

The lifting function uses a ranking on elements in order to provide a ranking on sets. We introduce some basic desirable properties for lifting functions below.

The Data Sensitive property ensures that element ranking is taken into account by the lifting function. The AbstractionL states that the ranking returned by the lifting function should not be concerned with the names of the elements.

Data Sensitive For any set of elements Y such that |Y | > 1 and E,E′ ∈ 2Y , there exist two different total, reflexive and transitive binary relations ⪰,⪰′ on Y such that (E, E′ ) ∈ L⪰(Y ) and (E, E′ ) /∈ L⪰′ (Y ).

Abstraction-L For any set of elements Y , any total, reflexive and transitive binary relation ⪰ on Y , E,E′ ∈ 2Y and isomorphism γ such that γ(Y ) = Y ′ and γ(⪰ ) = ⪰′ , we have that (E,E′ ) ∈ L⪰(Y ) if and only if (γ(E), γ(E′ )) ∈ L⪰′ (Y ′ ).

Proposition 4.2. L⪰max , L⪰leximax satisfy Data Sensitive and Abstraction-L.

Please note that |=RIF x with x ∈ {AR, IAR, ICR} satisfies the QCE, QCI, Cons, ConsS, ConsC properties from [Baget et al., 2016b]. The next additional property states that if there is an isomorphism on KBs such that the output from the RIF is the same up to an isomorphism, then the answer to the query should remain the same too.

1 The isomorphism γ renames the predicates and the constants. We use an abuse of notation and apply γ to sets of facts, sets of rules, negative constraints and to KBs (meaning we apply to all three).

Abstraction-Q For any KB K, any RIF RIF , any query q and any isomorphism γ such that γ(K) = K′ and E ∈ O(RIF,K) if and only if γ(E) ∈ O(RIF,K′ ), it holds that K |=RIF q if and only if γ(K) |=RIF γ(q)

We now introduce some properties on the whole framework. A desirable property is the entailment of free facts (the Free property). The Supremacy property states that if a fact is strictly less controversial than any other fact, then it should be entailed. Non Entailment Ejection states that if a fact is only entailed by the closure of a repair which is not ranked amongst the best repairs, then it will not be entailed by the KB. The Abstraction property states that if there is a renaming of the constants and predicates in a KB, the answers of our framework should remain unchanged.

Free For any KB K and any free fact a of K, it holds that K |=RIF a.

Supremacy For any KB K, if there exists f ∈ F such that Sf(K) ̸= 1 and for every f ′ ∈ F \ {f}, we have Sf (K) < Sf ′ (K) then K |= f .

Non Entailment Ejection For any KB K, R ∈ Comax(K)\O(RIF,K) and f ∈ CℓR(R), if there is no R′ ∈ Comax(K) \ {R} with f ∈ CℓR(R′ ) then K ̸|= f .

Abstraction For any KB K, any RIF RIF, any isomorphism γ such that γ(K) = K′ and any query q, it holds that K |=RIF q if and only if γ(K) |=RIF γ(q).

Proposition 4.3. It holds that:

• Abstraction-I, Abstraction-L and Abstraction-Q imply Abstraction.
• Let RIF = (S, L⪰, |=RIF x ) where x ∈ {AR, IAR, ICR} then RIF satisfies Free and Non Entailment Ejection.
• Let RIF = (S, L⪰y , |=RIF x ) where x ∈ {AR, IAR, ICR}, y ∈ {leximax,max} and S satisfies Bottom Facts then RIF satisfies Supremacy.

Although it is not always better to be more productive for all applications, the following result shows that the RIF is more productive than the usual IAR, AR and ICR semantics.

Proposition 4.4. Let RIF be a RIF and q a query, then:

• If K |=x q then K |=RIF x q with x ∈ {AR, IAR, ICR}
• If K |=RIF IAR q then K |=RIF ICR q
• If K |=RIF ICR q then K |=RIF AR q

However, it is worth noting that our framework does not make every inconsistency tolerant inference relation more productive. For instance, that is not the case with the non objection semantics from [Benferhat et al., 2016].

4.2 Algorithmic Results

In this section, we show a simple recursive algorithm that uses minimal inconsistent sets to compute the output of our framework and we study the behaviour of this algorithm thanks to an experiment. Since finding each minimal inconsistent set has been proven to be practically feasible as it is polynomial for data complexity and exponential for combined complexity ([Lembo et al., 2010; Hecham et al., 2017a]), we make the assumption that this set is given. The output of our framework is obtained by calling Algorithm 1 with X and Z initialised to ∅ and M to the set of minimal inconsistent sets of K. The parameter X is the set considered for building the result and Z is the set used for avoiding redundancies by memorising encountered sets. In Algorithm 1, we begin by checking if the set considered was already encountered (see line l1). Then, we proceed by finding facts with a minimal score that can be added to X without triggering a minimal inconsistent set (see line l2). If such facts cannot be found, it means that the considered set X is indeed a repair and should be returned (see line l3). Otherwise, the above mentioned process is repeated by augmenting the set of the considered set X with the facts found in line l2 (see line l4). The set E contains repairs with maximal elements with respect to SIMI 2 . However, although these repairs contain maximal elements, they are not equivalent with respect to leximax and this is why we have to refine the set E (see line l5). Please note that an alternate definition of SIMI found in the work of [Hunter and Konieczny, 2010] can be used for a faster computation.

Data: Two sets of sets of facts M, Z and a set of facts X Result: A set of repairs O(RIF, K) where

end

Algorithm 1: The OFRecc algorithm

We ran the algorithm on the KBs described by [Yun et al., 2017] and compared its performance with a basic algorithm for computing the RIF, namely naively finding all repairs, computing the inconsistency values and refining them by using leximax. The KBs were split in two sets: A first set A of 108 KBs with 2 to 7 facts, 0 to 6 rules and 1 to 4 binary or ternary negative constraints and a second set B of 26 KBs with 8 facts, 6 rules and between 1 and 2 binary or ternary negative constraints. For further details about the KBs, the reader is invited to consult the original paper of [Yun et al., 2017]. The results were as follows:

2 The obtained set is similar to the notion of preferred subtheories of a stratification defined by [Brewka, 1989].

• For the set A, the average number of repairs per KB was 2.89 and the average number of repairs in the output of the RIF was 2.11. It means that the average number of repair was reduced by 26.92%. Moreover, it takes an average of 543ms per KB to find the output of the RIF with the basic algorithm whereas it takes an average of 601ms per KB to find the same output with our algorithm.
• For the set B, the average number of repairs per KB was 4.5 and the average number of repairs in the output of the RIF was 3.62. It means that the average number of repair was reduced by of 19.66%. Moreover, it takes an average of 1.764s per KB to find the output of the RIF with the basic algorithm whereas it takes an average of 1.617s per KB to find the output with our algorithm.

Although finding the set Y ′ and E′ (see l2 and l5) can be found in polynomial time, in the worst case scenario, we would still have to search throughout all the subsets of F which would be exponential with respect to |F|. All experiments were performed on a Mac machine running on macOS High Sierra with an Intel core i5 2.8 GHz and 8GB of RAM and were reproduced multiple times.

4.3 Application Scenario

We now consider an application scenario constructed in the setting of the Pack4Fresh project ([Yun et al., 2016]) which was aimed at choosing the best packaging for strawberries. In this project, an online poll consisting of 66 questions was submitted to an audience of 21 professionals from the food industry. We distinguished four kinds of professionals: the wholesalers, the floorwalkers, the quality managers and the warehouse managers. The questions were aimed at collecting the individual vision of each person about the characteristics of four packagings: the wooden packaging (WP), the plastic packaging with a plastic film (PPF), the plastic packaging with a rigid lid (PRL) and the opened plastic packaging without lid (OPL). The answers of this poll were formalised into a set of 50 facts and 160 rules. In our application scenario, the inconsistency of the KB comes from the fusion of the divergent visions of the several professionals about the four aforementioned packagings. These visions were explicitly expressed using the rules. For instance, the rule ∀x(PPF(x,wholesaler0) → cheapCost(x)) conveys the idea that the entity wholesaler0 believes that the PPF is cheap. A group of packaging experts constructed another set of 18 rules constituting expert knowledge. For instance, the rule ∀x(keepHumidity(x) → badFridgeConservation(x)) states that if x is a packaging that keeps humidity then x is a bad packaging for fridge conservation whereas the rule ∀x(accelerateDecaying(x) → badEffectOnFruits(X)) states that if x is a packaging that accelerates decay then it is considered as having a bad effect on fruits. Lastly, a set of 34 negative constraints representing conflicting atoms, such as ∀x(notBadEffectOnFruits(x)

↑⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐⏐

Table 1: Ranking on repairs. For simplicity, repairs are denoted by the packaging they are referencing

∧ badEffectOnFruits(x) → ⊥), and incompatibilities between packagings, such as ∀x, y, z, t(OPL(x, y) ∧ PRL(z, t) → ⊥), was added.

The formalisation yielded a set of 33 repairs where each repair corresponds to the vision of a collection of individuals about a single packaging. For instance, the repair OPL2 = {OPL(po, floorwalker0), OPL(po,wharehouse manager0)} corresponds to the vision of floorwalker0 and wharehouse manager0 about the OPL. Amongst the 33 repairs, 16 concerned the WP, 6 concerned the PRL, 9 concerned the PPF and 2 concerned the OPL. The different number of repairs is explained by the diverse quantity of disagreements amongst individuals. For instance, only two wholesalers disagreed about the characteristics of the OPL whereas eight wholesalers disagreed about the characteristics of WP. In our model, the size of the repair corresponds to the number of individuals that agreed on all the characteristics of a specific packaging. Please note that the repairs are not ranked solely based on their cardinality.

Surprisingly, the ranking on repairs was extremely clear as it showed that WP > PRL ∼ PPF > OPL (see Table 1). Indeed, the repairs about WP were ranked above the other repairs. The repairs about the PRL were ranked roughly equally with the repairs about PPF and the repairs about OPL were last. The ranking was evaluated by a group of packaging experts which confirmed that the ranking on packagings was intuitive with respect to the data of the KB. Indeed, the experts acknowledged that WP was ranked first because its characteristics were slightly less contested by the experts.

The KB in DLGP format as well as a JAVA implementation of the tool for computing the output of our framework is accessible at: https://gite.lirmm.fr/yun/IJCAI2018.

5 Discussion

In this paper, we presented a framework that takes into consideration the inconsistency on the facts when using the repairs for query answering and restricts the set of repairs to the best with respect to inconsistency values. Since we consider a subset of repairs, we obtain more answers than classical inconsistency tolerant query answering in most cases. We characterised the desirable properties of such framework with respect to the following properties: Abstraction, Free, Non Entailment Ejection and Supremacy. We also introduced an algorithm for computing the output of such a framework and showed its results on a real-life scenario about packagings.

Our framework is more abstract than the work of [Staworko et al., 2012]: we can consider an inconsistency value returning the same preferences on facts, a lifting function that uses these preferences such that the completion optimal repairs are ranked first, Globally optimal repairs second, Pareto optimal repairs third and followed by the other repairs.

Acknowledgments

Srdjan Vesic benefited from ANR-13-BS02-0004 AMANDE and CNRS PEPS 2018 APOLONIO.