Non-Objection Inference for Inconsistency-Tolerant Query Answering

1 Introduction

Inconsistency-Tolerant Query Answering is one of the challenging problems that received a lot of attention in recent years, e.g. [Lukasiewicz et al., 2015; Benferhat et al., 2015; Bienvenu et al., 2016; Wan et al., 2016; Baget et al., 2016]. Inconsistency may arise due to several reasons: merging, integration, revision, etc. In this paper, we place ourselves in the context of Ontology-Based Data Access (OBDA), where the ontological knowledge is assumed to be satisfiable and fully reliable. In such a setting, inconsistency comes from the data, i.e. occurs when some assertional facts contradict some constraints imposed by the ontological knowledge. As ontology language we use DL-Lite, a lightweight family of description logics, well suited for OBDA thanks to the so-called firstorder rewritability property that ensures the efficient handling of queries [Calvanese et al., 2007].

Existing works in this area, e.g. [Lukasiewicz et al., 2012; Lembo et al., 2015], have studied different inconsistencytolerant query answering (well-known as semantics) closely related to works on consistent query answering from inconsistent Databases (e.g. [Chomicki, 2007; Bertossi, 2011]) or inference from inconsistent propositional logic knowledge bases, e.g. [Baral et al., 1992; Benferhat et al., 1993; Nebel, 1994; Benferhat et al., 1997]. Ontology-based consistent query answering (AR-semantics) [Lembo et al., 2010] comes down first to compute the set of repairs (i.e. all maximally consistent subsets of facts consistent with the ontology) and then checking if a query can be entailed using these repairs. As shown

Madalina Croitoru

Univ Montpellier, France croitoru@lirmm.fr

Karim Tabia

Univ Artois, France tabia@cril.fr

in [Lembo et al., 2010; Bienvenu, 2012], the AR entailment (also called universal entailment) is a hard task (co-NP complete) for DL-Lite and also for other lightweight DLs [Rosati, 2011]. Several approximations of AR entailment have been proposed, e.g. IAR, ICAR, ICR [Bienvenu, 2012], k-sup and k-def [Bienvenu and Rosati, 2013], etc.

We propose a new inconsistency-tolerant inference relation, called non-objection inference, where a query is considered as valid if it is entailed by at least one repair and it is consistent with all the other repairs. The intuition behind is that no repair has an objection veto to the acceptance of the query. If query entailment from repairs is seen as posing a vote for, against or abstaining to a query then, in this semantics, some repairs are "voting" for a query (i.e. the query is entailed) and the rest of the repairs are not against (i.e the query body atoms together with the atoms in the repair are consistent with the terminology) then the query is accepted without any objections. In addition, two variants of non-objection inference based on a selection of repairs (that can be against a query) are also considered. Consider the axiom stating that the teachers cannot be taught. Consider people getting some courses as statements. Statement 1 ("Alice is teaching Bob") and statement 2 ("Bob is teaching Celine") are two inconsistent statements since Bob is both a teacher and being taught. Let us consider Q ("Is Celine a student?"). Statement 1 is not inconsistent with Q (it has no objection to the acceptance of Q). As statement 2 entails Q we can say that asking if Celine is a student is a non-objection conclusion that follows from the two inconsistent statements. This makes intuitively sense as the main inconsistency arose from Bob. Please note that existing works (excepting for existential semantics) return the empty set. However, existential semantics are returning non intuitive results as even the query Q ("Is Bob a student?") is existentially accepted (with Bob being the cause of the inconsistency). With non-objection inference this is not accepted.

The main salient points of the newly introduced semantics is its efficiency (more efficient than universal entailment) and the fact that the set of conclusions it yields are consistent (unlike credulous entailment). Interestingly enough, we show that query answering with non-objection inference is achieved in polynomial time. The inferences are strictly more productive than universal inference while preserving the consistency of its set of conclusions. We study the productivity, properties and complexity of the new inferences.

2 Preliminaries

In this section, we recall DL-Lite logic (namely DL-LiteR, which underlies OWL2-QL ontology language designed for applications that use huge volumes of data) and we review the main existing inconsistency-tolerant inference relations proposed to deal with inconsistency.

DL-Lite syntax and semantics. The starting points are NC, NR and NI , three pairwise disjoint sets of atomic concepts, atomic roles and individuals respectively. Let A2NC, P2NR, three connectors '≻', '9' and '-' are used to define complex concepts and roles. Basic concepts (resp. roles) B (resp. R) and complex concepts (resp. roles) C (resp. E) are defined in DL-Lite as follows:

where P - represents the inverse of P . A DL-Lite knowledge base (KB) is a pair K=hT ↪ Ai where T is called the TBox and A is called the ABox. A TBox includes a finite set of inclusion axioms on concepts and on roles respectively of the form: BvC and RvE. The ABox contains a finite set of assertions (facts) of the form A(a) and P(a↪ b) where A2NC, P2NR and a↪ b2NI .

The semantics is given in terms of interpretations I=(∆I ↪ ▷I ) which consist of an non-empty domain ∆I and an interpretation function ▷I that assigns to each a2NI an element aI 2∆I , to each A2NC a subset AI ✓∆I and to each P2NR an P I ✓∆I ⇥∆I . The function ▷I is extended in a straightforward way for complex concepts and roles, e.g (≻B)I =∆I ∩ BI , (P -)I =¶(y↪ x)2∆I ⇥∆I-(x↪ y)2P I ♦ and (9R)I =¶x2∆I-9y2∆I-(x↪ y)2RI ♦. An interpretation I is said to be a model of a concept (resp. role) inclusion axiom, denoted by I♣=BvC (resp. I♣=RvE), iff BI ✓ C I (resp. RI ✓ EI ). Similarly, we say that I satisfies a concept (resp. role) assertion, denoted by I♣=A(a) (resp. I♣=P(a↪ b)), iff aI 2AI (resp. (aI ↪ bI )2P I ). An interpretation I is said to satisfy a KB K=hT ↪Ai, denoted I♣=K, iff I♣=T and I♣=A. Such interpretation is said to be a model of K. Lastly, a TBox T is said to be incoherent if there exists a concept C s.t 8I:I ♣=T , we have C I =;. A DL-Lite KB K is said to be inconsistent if it does not admit any model.

Query answering. A query is a first-order logic formula, denoted q=¶~x ♣φ(~x)♦, where ~x=(x1,...,xn) are free variables, n is the arity of q and atoms of φ(~x) are of the form A(ti) or P(ti↪ tj) with A2NC and P2NR and ti, tj are terms, i.e. constants of NI or variables. When φ(~x) is of the form 9~y▷conj(~x↪ ~y) where ~y are bound variables called existentially quantified variables, and conj(~x↪ ~y) is a conjunction of atoms of the form A(ti) or P(ti↪ tj) with A2NC and P2NR and ti, tj are terms, then q is said to be a conjunctive query (CQ). When n=0, then q is called a boolean query (BQ). A BQ with no bound variables is called a ground query (GQ). Lastly, when q only contains one atom with no free variables, then it is called an instance query (IQ) (i.e. instance checking). For a BQ q, we have I♣=q iff (φ)I =true and K♣=q iff 8I:I♣=K)I♣=q. For a CQ q with free variables ~x=(x1,...,xn), a tuple of constants ~a=(a1↪ ▷▷▷↪ an) is said to be the certain answer for q over K if the BQ q(~a) obtained by replacing each variable xi by ai in q(~x), evaluates to true for every model of K. Hence CQ answering can be reduced to BQ answering. For more details, see [Artale et al., 2009].

Inconsistency-tolerant consequence relations. Coping with inconsistency can be done by first computing the set of inclusion-maximal consistent subsets, called repairs, then using them to perform inference. A repair is defined as follows:

Definition 1. Let K=hT ↪Ai be a DL-Lite KB. A subset R✓ A is said to be a repair iff (i) hT ↪Ri is consistent, and (ii) 8R0 :R R0 , hT ↪R0 i is inconsistent.

Let us denote by R(K) the set of repairs of K. The following definition formally introduces the most common inconsistencytolerant inferences.

Definition 2. Let K=hT ↪ Ai be a DL-Lite KB. Let R(K) be the set of repairs of K and q be a query. Then:

• q is said to be a credulous (or existential) consequence of K, denoted by K ♣=9 q, iff 9R 2 R(K),hT ↪Ri ♣= q.
• q is said to be a universal (or AR) consequence of K, denoted by K ♣=AR q, iff 8R 2 R(K),hT ↪Ri ♣= q.
• q is said to be a safe (or IAR) consequence of K, denoted by K ♣=IAR q, iff DT ↪ TR2R(K) RE ♣= q.

The inference consequence relations given in Definition 2 are based on repairs computed using the initial ABox. However, one can define these entailments using closed ABox instead of the initial ABox (like the ICAR-entailment and the CAR-entailment [Lembo et al., 2010]) or using closed repairs instead of repairs themselves (like the ICR-entailment [Bienvenu, 2012]). The IAR-inference is the most cautious one and the credulous entailment is the most productive one. The universal entailment (or AR-semantics) can be considered as safe since a query is accepted if it can be deduced from each repair using standard DL-Lite semantics. Query answering within the AR-semantics is co-NP-complete even for simple DL-Lite languages such as DL-Litecore [Lembo et al., 2010]. The credulous entailment is often considered as adventurous. It is so adventurous that the set of conclusions may be inconsistent w.r.t the TBox. If one views each repair as a consistent set of assertions provided by a distinct source of information, then credulous entailment just says whether there is a source or a reason, that supports a given query.

3 Non-Objection Inference and its Variants

In this section, we propose three inference relations more productive than the universal entailment but less adventurous than the credulous one: non-objection inference (no), cardinalitybased non-objection (cno) and limited-based non-objection inference (lno).

3.1 Non-Objection Inference: no

Let us first define the statement of a query being consistent with a repair. Note that within DLs q is often restricted to a conjunctive query (CQ).

Definition 3. Let K=hT ↪ Ai be a DL-Lite KB, q be a CQ, and ~e=(e1↪ ▷▷▷↪ en) be a tuple of constants. A repair R of K is said to be consistent with q(~e) w.r.t to a TBox T iff there exists an interpretation I that satisfies both q(~e), R and T .

We can now introduce the non-objection (no for short) inference as follows:

Definition 4. Let K=hT ↪ Ai be a DL-Lite KB and let R(K) be the set of repairs of K. Let q be a CQ and ~e=(e1↪ ▷▷▷↪ en) be a tuple of constants. A query q(~e) is said to be a non-objection consequence of K, denoted by K♣=noq(~e), iff (1) there exists at least a repair R of K such that hT ↪Ri♣=q(~e), (2) for each repair R02R(K), R0 is consistent with q(~e).

The term non-objection is understood in the sense that none of the repairs is against accepting query. If a repair is compared to an expert/source/voter, then a conclusion is accepted if at least one expert/source/voter supports the conclusion and none is against or has an objection.

Example 1. Let Alice, Bob, Celine be three individuals. Let TeachTo be a role, where TeachTo(x,y) means that the individual x is the teacher of the individual y. Assume that we have the following inconsistent DL-Lite KB K=hT ↪Ai where T =¶9TeachTov≻9TeachTo-♦ and A=¶TeachTo(Alice↪Bob),TeachTo(Bob↪Celine)♦. We have R1=¶TeachTo(Alice↪Bob)♦ and R2 = ¶TeachTo (Bob↪Celine)♦ two repairs. Consider the following query q1 9y.TeachTo(y↪Celine). Clearly, K♣=noq1 since q1 follows from R2 and q1 is consistent with R1 and T .

3.2 Adding Cardinality to no Inference: cno

We now investigate a new inference obtained by adding a cardinality criterion to no. We basically restrict the application of the no-inference to a selection of repairs. Here we consider the largest (in the sense of cardinality) repairs. This might make sense in certain practical settings. Consider a retail use case and two products, one liked by women and not by men and the other liked by men and not by women. If the number of women is greater than the number of men, then we might decide selling the first product. Let

be the set of largest repairs of K where ♣R♣ is the size of R (i.e. the number of facts in R). Then, the cardinality-based nonobjection (cno for short) inference relation, is simply obtained from Definition 4 by only considering the largest repairs. More formally:

Definition 5. Let K=hT ↪Ai be a DL-Lite KB, q be a CQ and ~e=(e1↪ ▷▷▷↪ en) be a tuple of constants. A query q(~e) is said to be a cardinality-based non-objection consequence of K, denoted K♣=cnoq(~e), iff (1) 9R2CR(K) s.t hT ↪Ri♣=q(~e), and (2) 8R02CR(K),hT ↪R0 i is consistent with q(~e).

Example 2. Let K=hT ↪Ai be a DL-Lite KB where T =¶Bv≻D, BvC, DvE, Av≻B, Av≻C, Av≻D♦ and A=¶A(a), B(a), C(a), D(a)♦. We have R(K) = ¶¶A(a)♦, ¶B(a)↪C(a)♦, ¶D(a)↪C(a)♦♦ and CR(K) = ¶R1 = ¶B(a)↪C(a)♦, R2 = ¶D(a)↪C(a)♦♦. Clearly K♣=cnoE(a) since hT ↪ R2i♣=E(a) and R1[¶E(a)♦ is consistent with T .

The cno-inference relation is a completely new inconsistencytolerant inference which has neither been proposed in a propositional logic setting nor in the description logics setting. Restricting the set of repairs aims to increase the productivity of the inference and the cardinality criterion is a natural way

♣=9

Figure 1: Productivity comparison of inference relations. where X ! Y means that each conclusion of X is also a conclusion of Y

to select the set of the repairs used in inference. If rejecting an assertion from a repair can be seen as "the price to pay" then the cardinality criterion aims to reduce the price of the rejected assertions.

3.3 Limited Non-Objection Inference: lno

Last, we introduce an alternative inference more productive than the no and cno inference relations. The intuition is that when some answers to a query are obtained from a repair, then only repairs from CR(K) can make objections against the query answers. To comment on the practical relevance, recall the Obama administration that did not manage to pass certain motions (queries) as the elders (the repairs with the biggest cardinality) voted against.

Definition 6. Let K=hT ↪Ai be a DL-Lite KB. Let q be a CQ and ~e=(e1↪ ▷▷▷↪ en) be a tuple of constants. Then q(~e) is a limited non-objection consequence relation, denoted K♣=lnoq(~e), iff (1) 9R2R(K) where hT ,Ri♣=q(~e) and (2) 8R02CR(K),hT ,R0 i is consistent with q(~e).

Example 3. Let K = hT ↪Ai be a DL-Lite KB where T = ¶A v E↪ A v ≻B↪ A v ≻D↪ C v B↪ D v ≻B↪ D v ≻E♦ and A = ¶A(a)↪B(a)↪C(a)↪D(a)♦. We have R(K) = ¶R1 = ¶A(a)♦↪R2 = ¶D(a)♦↪R3 = ¶B(a)↪C(a)♦♦ and CR(K) = ¶R3 = ¶B(a)↪C(a)♦♦. We have K ♣=lno E(a) since hT ↪ R1i♣=E(a) and R3[¶E(a)♦ is consistent with T .

The difference between ♣=no and ♣=lno concerns item 2 of Definitions 4 and 6, where in ♣=no all the repairs are considered while in ♣=lno only the largest ones are taken into account. Similarly, the difference between ♣=cno and ♣=lno concerns item 1 of Definitions 5 and 6, where in ♣=lno all the repairs are used while in ♣=cno only the largest ones are used. Again if we view repairs as experts/sources/voters then a limited non-objection conclusion is considered as accepted if there is an expert/source/voter that accepts the conclusion and none of the oldest/wise expert/source/voter is against.

3.4 Productivity of no, cno and lno Inferences

From a productivity point of view, no-entailment is between the universal entailment (i.e. ♣=AR) and the credulous entailment. Figure 1 gives productivity relations between different inference relations described in this paper. The arrow "A ! B" means that each query which is considered as valid by the inference relation A is also considered as valid by B. Note that the no-inference is different from the AR, IAR, ICR and CAR entailments. There is also a difference between no and the k-support and k-defeater inferences given in [Bienvenu and Rosati, 2013]. In particular, our approach does not depend on a parameter k.

4 Complexity Analysis

In this section we study the data complexity of query answering under the inference relations proposed in this paper. Recall that we assumed that the TBox T is stable. Besides, we also recall that computing the set of conflicts can be done in polynomial time and that each conflict is a pair of assertions (a single fact if T is incoherent) [Calvanese et al., 2010].

4.1 Data Complexity of no Inference

Let K=hT ↪Ai be a DL-Lite KB, q(~x) be a CQ and ~e be a tuple of constants of K. To establish the data complexity of no-inference, we focus on the following question. Given a KB K and a CQ q(~x) does there exist a tuple of constants ~e of A such that K ♣=no q(~e)? We show that the data complexity of the query answering under no semantics is polynomial. Firstly,

let us consider ground query (GQ) of the form q nV i=1Xi(↵i)

where Xi(↵i) is either of the form A(ti) or P(ti↪ tj) with A is a concept, P is a role and ↵i is either a term (if Xi is a concept) or a pair of terms (if Xi is a role). For each Xi(↵i) we define:

where Di is a new concept (resp. a new role if Xi is a role) associated with Xi. Intuitively, LabelXi(↵i), represents the set of all supports for the instance Xi(↵i). The following proposition concerns the case where the query just concerns one instance (instance query).

Proposition 1. Let K=hT ↪ Ai be a DL-Lite KB. Then Xi(↵i) is entailed by at least one repair R of K (hT ↪Ri♣=Xi(↵i)) iff LabelXi(↵i) is not empty.

Proof. Assume that from some repair R, we have hT ↪Ri ♣=Xi(↵i). This means hT [¶Div≻Xi♦,R[¶Di(↵i)♦i is inconsistent. Hence there exists a conflict in hT [ ¶Di v ≻Xi♦↪R[ ¶Di(↵i)♦i. This conflict necessarily contains Di(↵i) and an element e from R (since hT ↪Ri is consistent by definition of a repair). Hence LabelXi(↵i) is not empty. For the converse, assume that @R, s.t hT ↪Ri♣=Xi(↵i). This means that 8R,hT [ ¶Di v ≻Xi♦↪ R [ ¶Di(↵i)♦i is consistent. Hence 8R, @e2R s.t hT [¶Div≻Xi♦,¶e,Di(↵i)♦i is inconsistent. Since SR2R(K) R=A, then LabelXi(↵i) 6= ;.

Proposition 1 can be easily generalized for GQ as follows.

Proposition 2. Let K=hT ↪Ai be a DL-Lite KB and q be a GQ. Then q is entailed by at least a repair R, namely hT ↪Ri♣=q, iff there exists a tuple (e1↪ ▷▷▷↪ en)1 of A such that 8i,ei2LabelXi(↵i) and ¶e1↪ ▷▷▷↪ en♦ is consistent with T .

Proof. If there is no (e1,...,en)2LabelX1(↵1)⇥▷▷▷⇥ LabelXn(↵n) which is consistent, this means that whatever is the considered repair R, there is some Xi(↵i) such that hT ↪Ri is consistent with ≻Xi(↵i). Hence, there is no repair R where hT ↪Ri♣=q. For the converse, assume that ¶e1,...,en♦ is consistent with T . Then it is enough to build a repair R that contains ¶e1,...,en♦. Since hT ,Ri is consistent but inconsistent with each ≻Xi(↵i), then hT ↪Ri♣=q.

1 the ei's are not required to be distinct.

If q is a CQ, we first explicit the FOL-rewritability of DLLite. Indeed, q can be expressed as a disjunction of queries: Rw(q)=q1_..._qn (Rw(q) can be computed using PERFECTREF algorithm proposed in [Calvanese et al., 2007]). Each query qi in Rw(q) implicitly represents different possible supports of q where the size of these supports is equal to the size of qi. Now, computing the set of all the supports of q comes down to compute for each query qi in Rw(q) = q1 _ ▷▷▷ _ qn the set of facts of A that implies it. Then to check if there exists a repair that entails q comes down to verify whether there is a consistent maximal support of q. More precisely, we first compute minimal supports for q denoted by S(q). Then q is entailed from a repair iff 9S 2S(q) such that hT ↪ Si is consistent. Moreover the following result holds.

Proposition 3. Let K=hT ↪Ai be a DL-Lite KB and q be a GQ. Assume that hT ,¶X1(↵1),...,Xn(↵n)♦i is consistent. Then 8R,hT ,R[¶X1(↵1),...,Xn(↵n)♦i is consistent iff there is no e2A and no Xi(↵i) s.t hT ↪ ¶e↪ Xi(↵i)♦i is inconsistent.

Proof. Assume for some Xi(↵i) of the query, there exists an assertional fact e from A, such that hT ↪ ¶e↪Xi(↵i)♦i is inconsistent. Then let R be a repair that contains e. Such R is not necessarily unique but always exists. It is enough to start with R=¶e♦ and add as much as possible elements from A while preserving consistency. Then hT ,R[¶Xi(↵i)♦i is inconsistent, and hence, "8R,hT ,R[¶X1(↵1)↪ ▷▷▷↪Xn(↵n)♦i is consistent" does not hold. For the converse, assume that there is no e2A and no Xi(↵i) such that hT ↪ ¶e↪Xi(↵i)♦i is conflicting. Then whatever is the repair R, we have hT ,R[¶X1(↵1)↪ ▷▷▷↪Xn(↵n)♦i is consistent (recall that by definition hT ↪Ri is consistent and hT ,¶X1(↵1),...,Xn(↵n)♦i is consistent by assumption).

Of course, in Proposition 3 if hT ,¶X1(↵1),...,Xn(↵n)♦i is inconsistent, then trivially "8R,hT ,R[¶X1(↵1)↪ ▷▷▷↪Xn(↵n)♦i is consistent" does not hold.

Proposition 4. Let K=hT ↪Ai be a DL-Lite KB and q be a GQ. Then the data complexity of the query evaluation problem under non-objection semantics is polynomial.

Proof. From Proposition 1, checking whether there exists a repair where an instance Xi(↵i) follows from hT ↪Ri, can be achieved in polynomial time, since computing conflicts is done in polynomial time. A naive algorithm for implementing Proposition 2 is to progressively compute consistent elements of LabelX1(↵1)⇥... ⇥LabelXn(↵n) by removing at each step i the conflicting tuples (e1,...,ei) from LabelX1(↵1)⇥...⇥LabelXi(↵i). Since computing conflicts is done in polynomial time and since the size of the query is bounded, then checking whether q follows from hT ↪Ri, where R is a repair of K, is achieved in polynomial time w.r.t the size of the ABox. Lastly, checking whether q is consistent with each repair is also achieved in polynomial time. It is enough to first check whether hT ↪ ¶X1(↵1)↪ ▷▷▷↪Xn(↵n)♦i is consistent (which is done in PTime). If it is the case, then one needs to compute the set of conflicts C of hT ↪A[ ¶X1(↵1)↪ ▷▷▷↪Xn(↵n)♦i (which is done in polynomial time) and check whether there is a pair (f↪ g) of C such that f2A and g2¶X1(↵1)↪ ▷▷▷↪ Xn(↵n)♦.

Note that considering coherent ontologies is not a restriction. In case where T is incoherent then a preprocessing step is needed. If A is an empty concept (resp. P is an empty role), then one should remove from the ABox all assertions of the form A(a) (resp. P(a↪ b)), where a,b are individuals. Queries q where some Xi(↵i) is an empty concept or role cannot be considered as no-consequences.

4.2 Data Complexity of cno and lno Inferences

Contrarily to no-inference, cno and lno inferences are hard. We first analyze the following complexity problem: CP1. Is the size of the largest repair of an inconsistent DL-Lite KB K is at least equal to k? To analyze the computational complexity of CP1, we will for instance use complexity results known in graph theory regarding the problem of Maximum Independent Sets (MIS) or stables sets. Let us recall k-MIS, the following decision problem: "Given a symmetric graph G, is there an independent set (or stable set), denoted by IS, of size at least equal to k?" The computational complexity of k-MIS is known to be NP-complete [Garey and Johnson, 1979]. We will denote by Prov-k-MIS a call to a prover that solves a k-MIS problem. The following gives transformations between graphs and DLLite KBs.

A transformation from an inconsistent DL-Lite KB to G: Let K=hT ↪ Ai be an inconsistent KB. Let C(A) be the set of all conflicts in A. Recall that when T is coherent, then all conflicts of C(A) are pairs of elements of A and are computed in PTime. We define a graph associated with K as follows: (1) The set of nodes is simply the set of assertions in A (one assertion = one different node), and (2) A non-oriented arc is drawn from f to g if there is f2A, g2A such that (f↪ g) is a conflict of hT ↪ Ai. Then we have the following result:

Proposition 5. Let K=hT ↪ Ai be a DL-Lite KB, and G be its associated graph as it is defined above. Let R✓A be a subset of A and GR be the set of nodes associated to R. Then R is a maximal consistent subset of A iff GR is a MIS of G.

Proof. Assume that R is a maximal consistent subset of A but GR is not a MIS of G. This means that there exists a node f (namely a fact of A) s.t f ◁2GR and 8g2GR, there is no arc between f and g. Said differently, there exists an assertion f2A s.t f ◁2R and 8g2R, there is no conflict C2C(A) of the form (f↪ g). This means that R[¶g♦ is consistent and this contradicts the fact that R is a maximally consistent subset of A. Similarly, assume that GR is a MIS of G and let us show that R (the subset of assertions present in GR) is a maximally consistent subset of A. Clearly, R is consistent, since 8f2R,8g2R, we have (f↪ g)◁2C where C is a conflict (otherwise, there would be an arc between f and g). R is maximal, since 8h◁2R there is an arc between h and a node from GR. Hence there is a conflict between h and an element of R, namely R[¶h♦ is inconsistent. Hence R is maximal.

Let us now give the converse transformation: Let G be a non-oriented graph. The DL-Lite KB associated with G is defined as follows: (1) We associate to each node e a concept also denoted by e (two different nodes have two distinct associated concepts), (2)We use "a" as the unique individual used in A, (3) For each non-oriented arc e-!f, we add (ev ≻f) to T , namely the TBox associated with G is defined by: T =¶ev ≻f:e-!f is an arc of G♦, and (4) The ABox is simply the set of nodes with the same individual "a", namely A=¶e(a):a is an individual and e is a node of G♦. The DL-Lite KB associated with a graph only involves one individual. It neither contains positive axioms nor relation symbols.

Proposition 6. Let G be a non-oriented graph, and K=hT ↪ Ai be the DL-Lite KB associated with G, as it is defined above. Then, 8e(a)2A,8f(a)2A,(e(a)↪ f(a))2C(A) iff there is an non-oriented arc between f and e.

The proof is immediate. Since there is no relation symbols nor positive axioms, then the negative closure of T is simply T . Besides, for each ev ≻f of T (namely, an arc fromG by construction), there exists exactly one conflict (e(a)↪ f(a)) from A (since there is exactly one individual a). Using Propositions 5 and 6, the following proposition gives the complexity of computing the cardinality of the largest repair of A.

Proposition 7. Let K=hT ↪Ai be a DL-Lite KB. The complexity of computing the cardinality of the largest maximal consistent subset of K is O(log2(♣A♣))⇤Prov-k-MIS, namely there is an O(log2(♣A♣) calls to a prover of a k-MIS problem.

It is enough to apply a dichotomic search between 1 and ♣A♣, and for each value 1k♣A♣ we call a k-MIS prover. The following complexity problem will be helpful to analyze the complexity of ♣=lno and ♣=cno.

CP2. Determine whether there exists a repair from CR(K) which is consistent with a fact X(↵).

To implement CP2, we consider K0=hT [¶DvX♦, A[¶X(↵)♦i where D is a new concept (or role) associated with X. K0 is the result of adding to K the assumption that X(↵) is true. Let GK (resp. GK0 ) be the graph associated with K (resp. K0 ) using the transformation given in CP1 and ISK be the size of the largest repair of CR(K) (resp. the largest IS of GK using CP1). Hence, we have:

Proposition 8. GK0 has an independent set of size (ISK+1) iff 9R2CR(K) which is consistent with X(↵).

Proof. Note first that GK0 is obtained fromGK by first adding a new node D and drawing and arc between D and a node e of GK iff hT [¶DvX♦,¶D(↵)↪ e♦i is conflicting. If GK0 has an IS0 of size (ISk + 1) then IS0 necessarily contains the node D plus ISk nodes from GK0 . Namely, IS0 contains D plus an IS of size ISk fromGK. Hence, there is a repair R0 from K0 which contains D(↵) and a repair R from K. This means that hT [ ¶D v X♦↪ R [ ¶D(↵)♦i is consistent, hence hT [ ¶D v X♦↪ R [ ¶D(↵)↪ X(↵)♦i is consistent and consequently hT ↪R[ ¶X(↵)♦i is consistent.

The above proposition can be easily generalized for ground queries. Now it remains to provide a procedure that checks if a GQ is consistent with some cardinality-based maximal repair. This is quite straightforward. Let q nV i=1Xi(↵i) be a GQ. Let D be a new concept and R be a new role. Let T 0=T [ ¶D v Xi: if Xi is a concept♦[¶R v Xi:if Xi is a role♦ and A0=A[¶D(↵i): if Xi(↵i) 2 q and Xi is a concept♦ [ ¶R(↵i): if Xi(↵i) 2 q and Xi is a role ♦. Then q is entailed from a repair R 2 CR(K) iff there exists a MIS of size (kmax+n) in GK0 . Clearly, ♣=cno and ♣=lno are hard problems since their associated decision problems belong to ∆2p class.

Proposition 9. Let K=hT ↪Ai be a DL-Lite KB and q be a GQ. Then the data complexity of the query evaluation problem under cno and lno semantics is in ∆2p .

5 Rationality Properties and Experimental Evaluation

We now briefly analyze some properties of no inference and provide preliminary experimental evaluation results showing the scalability of no-inference. For logical properties, we focus on the situation where the considered conclusions are sets of assertions, which can also be seen as conjunctions of ground queries. Namely, given K=hT ↪ Ai a KB and A↵, Aβ two sets of facts s.t hT ↪A↵i and hT ↪Aβi are consistent, we say that Aβ is a consequence of A↵ w.r.t K, denoted by A↵ ♣⇠sAβ, if hT ↪A[A↵i♣=sAβ. In the following, we recall the KLM rationality properties [Kraus et al., 1990] rephrased within our framework: Reflexivity (R) means that A↵ has to be a consequence of A↵. Left Logical Equivalence (LLE) expresses the fact that if A↵ and Aβ are equivalent then they have the same consequences. Right Weakening (RW) says that if a A↵ is a consequence of Aγ and Aβ is logically implied by A↵ then Aβ is a consequence of Aγ too. Cut expresses the fact that if Aβ is a consequence of A↵ and Aγ is a consequence of A↵[Aβ then Aγ is a consequence of A↵. Cautious Monotony (CM) expresses that if Aβ and Aγ are consequences of A↵ then Aγ is a consequence of A↵ [ Aβ. And expresses that if Aβ and Aγ are consequences of A↵ then Aβ [ Aγ is also a consequence of A↵. It can be shown that no, cno and lno inferences satisfy R, LLE, RW, Cut but violate And. Moreover, no and cno inferences satisfy CM while lno inference violates this property. Note that the difference between the language representing the KB and the one expressing the queries only impacts R, CM and Cut properties. In LLE Aγ can be replaced by a CQ. In RW A↵ (resp. Aβ) can be replaced by a CQ q1 (resp. q2). In And Aγ (resp. Aβ) can be replaced by a CQ q1 (resp. q2).

For experimental evaluation, we implemented a tool that checks whether a query q is a no-consequence of a DL-LiteR KB K. Note that we restrict the form of the queries to ground queries. As benchmark (available at https://code.google.com/p/combo-obda/ ), we considered the LUBM9 20 ontology (i.e. TBox), which corresponds to the DL-LiteR version of the original LUBM ontology [Lutz et al., 2013], and we used the Extended University Data Generator (EUDG) in order to generate the ABox assertions. This ontology only contains 208 positive inclusion axioms. We added 1296 negated axioms in order to allow for inconsistency (the list of these axioms can be found in [Bienvenu et al.,

time unit: millisecond (ms).

Table 1: Preliminary experimental evaluation of no-inference.

2014]). To efficiently compute conflicting elements (needed to check no-consequence), we evaluate over the ABox (stored as a DB using SQLite engine) queries expressed from the negated closure of the TBox to exhibit whether the ABox contains or not conflicting elements. In our case computing the negated closure of the ontology is done in 856906 milliseconds (ms). Table 1 gives for four ABoxes their size, and the time taken to check inconsistency. In each cell of column "IC", we first give the time taken to check inconsistency (the whole operation including the one of computing the negated closure) and then only the time taken to evaluate over each ABox queries from the negated closure. For instance, the time taken to check consistency for an ABox containing 2434 facts takes 857833ms with only 927ms for the queries evaluation operation. Note that without using query evaluation, looking for conflicting elements takes 563940ms. Similarly, Table 1 gives for four queries of different sizes, the time taken to check whether Qi (with i is the size of the query) is a noconsequence (the whole operation) and then the time needed to compute LabelXi (↵i) and the time needed to check whether there exist elements of the ABox that conflict with the query. For example, the time taken to check whether Q3 is a noconsequence of K = hT ↪ A1i is 1161829ms with 1226ms to compute LabelXi (↵i) and 1693ms to verify whether there exist elements of A1 that conflict with Q3.

From Table 1, one can see that the most costly task is the one on computing the negated closure. Once done, checking inconsistency or no-consequence is efficiently done w.r.t the size of the ABox. One can also observe that checking no-inference slightly increases comparing to checking inconsistency. This is mainly due to the fact that we add new axioms in order to compute LabelXi (↵i). Of course this also depends on the size of the query (i.e. the number of added axioms). But once done, checking the existence of a repair that entails the query (by computing LabelXi (↵i)) and the existence of another repair against its entailment is done efficiently.

6 Conclusion

This paper introduced three new inconsistency-tolerant inferences. We gave productivity, properties and complexity results for the case where the ontology is expressed using DL-Lite. With respect to the state of the art, the salient point of our contribution lays in the fact that queries are handled, using noinference, in polynomial time (contrarily to AR-entailment)

and the set of conclusions is always consistent (contrarily to 9-entailment). This is not the case if one uses a propositional setting for instance. As a future work, one can investigate complexity results of no, lno and cno inferences for more expressive or other lightweight (for instance EL languages) ontology representation languages.

Acknowledgments

This work has been supported by the French National Research Agency. ASPIQ project ANR-12-BS02-0003. This work has also received support from the european project H2020 Marie Sklodowska-Curie Actions (MSCA) research and Innovation Staff Exchange (RISE): AniAge (High Dimensional Heterogeneous Data based Animation Techniques for Southeast Asian Intangible Cultural Heritage.