# nonobjection_inference_for_inconsistencytolerant_query_answering__4a195b89.pdf

Non-Objection Inference for Inconsistency-Tolerant Query Answering

Salem Benferhat Univ Artois, France

benferhat@cril.fr

Zied Bouraoui Aix-Marseille Univ, France zied.bouraoui@univ.amu.fr

Madalina Croitoru Univ Montpellier, France

croitoru@lirmm.fr

Odile Papini Aix-Marseille Univ, France

odile.papini@univ.amu.fr

Karim Tabia Univ Artois, France

tabia@cril.fr

Repair based techniques are a standard way of dealing with inconsistency in the context of ontology based data access. We propose a novel non-objection inference relation (along with its variants) where a query is considered as valid if it follows from at least one repair and it is consistent with all the repairs. These inferences are strictly more productive than universal inference while preserving the consistency of its set of conclusions. We study the productivity and properties of the new inferences. We also give experimental results of the proposed non-objection inference.

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

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.

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

2 Preliminaries

In this section, we recall DL-Lite logic (namely DL-Lite R, 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:

B ! A | 9R C ! B | B R ! P | P E ! R | R

where P represents the inverse of P. A DL-Lite knowledge base (KB) is a pair K=h T , 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: Bv C and Rv E. 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 a I2 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|=Bv C (resp. I|=Rv E), iff BI CI (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 a I2AI (resp. (a I, b I)2P I). An interpretation I is said to satisfy a KB K=h T , 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 CI=;. 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=h T , Ai be a DL-Lite KB. A subset R A is said to be a repair iff (i) h T , Ri is consistent, and (ii) 8R0:R R0, h T , R0i 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=h T , 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 universal (or AR) consequence of K,

denoted by K |=AR q, iff 8R 2 R(K),h T , Ri |= q. q is said to be a credulous (or existential) consequence

of K, denoted by K |=9 q, iff 9R 2 R(K),h T , Ri |= q. q is said to be a safe (or IAR) consequence of K, denoted

by K |=IAR q, iff

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=h T , 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=h T , 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 h T , 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 Teach To be a role, where Teach To(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=h T , Ai where T ={9Teach Tov 9Teach To } and A={Teach To(Alice, Bob),Teach To(Bob, Celine)}. We have R1={Teach To(Alice, Bob)} and R2 = {Teach To (Bob, Celine)} two repairs. Consider the following query

q1 9y.Teach To(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

CR(K)={R:R2R(K) and @R0,R02R(K) s.t |R0|>|R|}.

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=h T , 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 h T , Ri|=q(~e), and (2) 8R02CR(K),h T , R0i is consistent with q(~e).

Example 2. Let K=h T , Ai be a DL-Lite KB where T ={Bv D, Bv C, Dv E, 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|=cno E(a) since h T , 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

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=h T , 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 h T ,Ri|=q(~e) and (2) 8R02CR(K),h T ,R0i is consistent with q(~e).

Example 3. Let K = h T , 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 h T , 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 [Bien-

venu 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=h T , 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

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:

Label Xi( i)={e:e2A and h T [{Div Xi},{e, Di( i)}i is

inconsistent} where Di is a new concept (resp. a new role if Xi is a role) associated with Xi. Intuitively, Label Xi( 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=h T , Ai be a DL-Lite KB. Then Xi( i) is entailed by at least one repair R of K (h T , Ri|=Xi( i)) iff Label Xi( i) is not empty.

Proof. Assume that from some repair R, we have h T , Ri |=Xi( i). This means h T [{Div Xi},R[{Di( i)}i is inconsistent. Hence there exists a conflict in h T [ {Di v Xi}, R [ {Di( i)}i. This conflict necessarily contains Di( i) and an element e from R (since h T , Ri is consistent by definition of a repair). Hence Label Xi( i) is not empty. For the converse, assume that @R, s.t h T , Ri|=Xi( i). This means that 8R,h T [ {Di v Xi}, R [ {Di( i)}i is consistent. Hence 8R, @e2R s.t h T [{Div Xi},{e,Di( i)}i is inconsistent. Since S

R2R(K) R=A, then Label Xi( i) 6= ;.

Proposition 1 can be easily generalized for GQ as follows. Proposition 2. Let K=h T , Ai be a DL-Lite KB and q be a GQ. Then q is entailed by at least a repair R, namely h T , Ri|=q, iff there exists a tuple (e1, ..., en)1 of A such that 8i,ei2Label Xi( i) and {e1, ..., en} is consistent with T .

Proof. If there is no (e1,...,en)2Label X1( 1) ... Label Xn( n) which is consistent, this means that whatever is the considered repair R, there is some Xi( i) such

1the ei s are not required to be distinct.

that h T , Ri is consistent with Xi( i). Hence, there is no repair R where h T , 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 h T ,Ri is consistent but inconsistent with each Xi( i), then h T , Ri|=q.

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 h T , Si is consistent. Moreover the following result holds. Proposition 3. Let K=h T , Ai be a DL-Lite KB and q be a GQ. Assume that h T ,{X1( 1),...,Xn( n)}i is consistent. Then 8R,h T ,R[{X1( 1),...,Xn( n)}i is consistent iff there

is no e2A and no Xi( i) s.t h T , {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 h T , {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 h T ,R[{Xi( i)}i is inconsistent, and hence, 8R,h T ,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 h T , {e, Xi( i)}i is conflicting. Then whatever is the repair R, we have h T ,R[{X1( 1), ..., Xn( n)}i is consistent (recall that by definition h T , Ri is consistent and h T ,{X1( 1),...,Xn( n)}i is consistent by assumption).

Of course, in Proposition 3 if h T ,{X1( 1),...,Xn( n)}i is inconsistent, then trivially 8R,h T ,R[{X1( 1), ..., Xn( n)}i is consistent does not hold. Proposition 4. Let K=h T , 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 h T , 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 Label X1( 1) ... Label Xn( n) by removing at each step i the conflicting tuples (e1,...,ei) from Label X1( 1) ... Label Xi( i). Since computing conflicts is done in polynomial time and since the size of the query is bounded, then checking whether q follows from h T , 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

h T , {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 h T , 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=h T , 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 h T , Ai. Then we have the following result:

Proposition 5. Let K=h T , 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=h T , 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 from G 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=h T , 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=h T [{Dv X}, 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 from GK by first adding a new node D and drawing and arc between D and a node e of GK iff h T [{Dv X},{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 from GK. Hence, there is a repair R0 from K0 which contains D( ) and a repair R from K. This means that h T [ {D v X}, R [ {D( )}i is consistent, hence h T [ {D v X}, R [ {D( ), X( )}i is consistent and consequently h T , 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

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 2

Proposition 9. Let K=h T , 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 2

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=h T , Ai a KB and A , Aβ two sets of facts s.t h T , A i and h T , Aβi are consistent, we say that Aβ is a consequence of A w.r.t K, denoted by A | s Aβ, if h T , A [ A i|=s Aβ. 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-Lite R 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 LUBM920 ontology (i.e. TBox), which corresponds to the DL-Lite R 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.,

ABox IC Q1 Q3 Q5 Q6 A1 857833 858213 1161829 1137525 1148324 2434 927 1188/1239 1226/1693 1223/1564 1151/1535 A2 858113 1241762 1278691 1279259 1239672 8263 1207 3096/2618 3450/2460 2273/2277 2298/2845 A3 859031 1274355 1288147 1292443 1287621 18431 2125 4694/3159 4295/3273 4685/4593 6565/6411 A4 860381 1268866 1289858 1286326 1272157 30033 3475 7362/4763 6553/4929 7068/6582 9506/9173

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 Label Xi( 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 = h T , A1i is 1161829ms with 1226ms to compute Label Xi( 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 Label Xi( 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 Label Xi( 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): Ani Age (High Dimensional Heterogeneous Data based Animation Techniques for Southeast Asian Intangible Cultural Heritage.

[Artale et al., 2009] A. Artale, D. Calvanese, R. Kontchakov, and

M. Zakharyaschev. The DL-Lite family and relations. J. Artif. Intell. Res. (JAIR), 2009.

[Baget et al., 2016] Jean-Franc ois Baget, Salem Benferhat, Zied

Bouraoui, Madalina Croitoru, Marie-Laure Mugnier, Odile Papini, Swan Rocher, and Karim Tabia. A general modifier-based framework for inconsistency-tolerant query answering. In The fifteenth International Conference on Principles of Knowledge Representation and Reasoning, KR2016, 2016.

[Baral et al., 1992] C. Baral, S. Kraus, J. Minker, and V. S. Subrah-

manian. Combining knowledge bases consisting of first-order analysis. Computational Intelligence, 8:45 71, 1992.

[Benferhat et al., 1993] Salem Benferhat, Claudette Cayrol, Didier

Dubois, J erˆome Lang, and Henri Prade. Inconsistency management and prioritized syntax-based entailment. In IJCAI, pages 640 647, 1993.

[Benferhat et al., 1997] Salem Benferhat, Didier Dubois, and Henri

Prade. Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study part 1: The flat case. Studia Logica, 58(1):17 45, 1997.

[Benferhat et al., 2015] Salem Benferhat, Zied Bouraoui, and Karim

Tabia. How to select one preferred assertional-based repair from inconsistent and prioritized DL-Lite knowledge bases? In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, pages 1450 1456, 2015.

[Bertossi, 2011] Leopoldo E. Bertossi. Database Repairing and

Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.

[Bienvenu and Rosati, 2013] Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 2013.

[Bienvenu et al., 2014] Meghyn Bienvenu, Camille Bourgaux, and

Franc ois Goasdou e. Querying inconsistent description logic knowledge bases under preferred repair semantics. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 996 1002, 2014.

[Bienvenu et al., 2016] Meghyn Bienvenu, Camille Bourgaux, and

Franc ois Goasdou e. Querying inconsistent description logic

knowledge bases under preferred repair semantics. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (To appear), 2016. [Bienvenu, 2012] Meghyn Bienvenu. On the complexity of consis-

tent query answering in the presence of simple ontologies. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012. [Calvanese et al., 2007] D. Calvanese, G. De Giacomo, D. Lembo,

M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3):385 429, 2007. [Calvanese et al., 2010] Diego Calvanese, Evgeny Kharlamov,

Werner Nutt, and Dmitriy Zheleznyakov. Evolution of dl-lite knowledge bases. In The Semantic Web - ISWC 2010 - 9th International Semantic Web Conference, ISWC 2010, Shanghai, China, November 7-11, 2010, Revised Selected Papers, Part I, pages 112 128, 2010. [Chomicki, 2007] Jan Chomicki. Consistent query answering: Five

easy pieces. In Database Theory - ICDT 2007, 11th International Conference, Barcelona, Spain, January 10-12, 2007, Proceedings, pages 1 17, 2007. [Garey and Johnson, 1979] M. R. Garey and David S. Johnson.

Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman, 1979. [Kraus et al., 1990] Sarit Kraus, Daniel J. Lehmann, and Menachem

Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell., 44(1-2):167 207, 1990. [Lembo et al., 2010] Domenico Lembo, Maurizio Lenzerini, Ric-

cardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant semantics for description logics. In Web Reasoning and Rule Systems - Fourth International Conference, RR 2010, pages 103 117, 2010. [Lembo et al., 2015] Domenico Lembo, Maurizio Lenzerini, Ric-

cardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant query answering in ontology-based data access. J. Web Sem., 33:3 29, 2015. [Lukasiewicz et al., 2012] Thomas Lukasiewicz, Maria Vanina Mar-

tinez, and Gerardo I. Simari. Inconsistency handling in datalog+/- ontologies. In ECAI 2012 - 20th European Conference on Artificial Intelligence, pages 558 563, 2012. [Lukasiewicz et al., 2015] Thomas Lukasiewicz, Maria Vanina Mar-

tinez, Andreas Pieris, and Gerardo I. Simari. From classical to consistent query answering under existential rules. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 1546 1552, 2015. [Lutz et al., 2013] C. Lutz, I. Seylan, D. Toman, and F. Wolter. The

combined approach to OBDA: taming role hierarchies using filters. In The Semantic Web - ISWC, volume 8218 of Lecture Notes in Computer Science, pages 314 330. Springer, 2013. [Nebel, 1994] B. Nebel. Base revision operations and schemes: Semantics, representation and complexity. In ECAI, pages 341 345, 1994. [Rosati, 2011] Riccardo Rosati. On the complexity of dealing with

inconsistency in description logic ontologies. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pages 1057 1062, 2011. [Wan et al., 2016] Hai Wan, Heng Zhang, Peng Xiao, Haoran

Huang, and Yan Zhang. Query answering with inconsistent existential rules under stable model semantics. In Proceedings of the Thirtieth Conference on Artificial Intelligence, (To appear), 2016.