In recent years, there has been growing interest in ontology-based data access, in which
information in the ontology is used to derive additional answers to queries posed over
instance data. The DL-Lite family of description logics [
An important problem which arises in ontology-based data access is how to handle
inconsistencies. This problem is especially relevant in an information integration setting
where the data comes from multiple sources and one generally lacks the ability to
modify the data so as to remove the inconsistency. In the database community, the related
problem of querying databases which violate integrity constraints has been extensively
studied (cf. [
Consistent query answering for the DL-Lite family of description logics was
recently studied in [
The paper is organized as follows. After some preliminaries, we introduce in
Sections 3 and 4 the problem of consistent query answering and some useful notions and
terminology. Our main results are presented in Sections 4, 5, and 6, where we present
general conditions which yield co-NP-hardness, first-order inexpressiblity, or first-order
expressiblity of consistent instance checking in DL-Litecore. Finally, in Section 7, we
show that query rewriting is always possible if we adopt a previously studied alternative
semantics. Note that proofs have been omitted for lack of space but can be found in [
Syntax. DL-Litecore knowledge bases (KBs) are built up from a set NI of constants, called individuals, a set NC of unary predicates, called atomic concepts, and a set NR binary predicates, called atomic roles. Complex concept and role expressions are constructed using the following syntax:
B ! A j 9R
C ! B j :B
R ! P j P where A 2 NC and P 2 NR. Here B (resp. R) denotes a basic concept (resp. basic role), and C denotes a general concept. A TBox is a finite set of inclusions of the form B v C (with B; C as above). An ABox is a finite set of assertions of the form B(a) (B 2 NC) or R(a; b) (R 2 NR) where a; b 2 NI. A KB consists of a TBox and an ABox. Notational conventions We use lhs( ) (resp. rhs( )) to refer to the basic concept appearing on the left (resp. right) side of an inclusion , e.g. lhs(9P v :D) = 9P and rhs(9P v :D) = D. We sometimes use R to mean P if R = P 2 NR and P if R = P , and write R(a; b) to mean P (a; b) if R = P and R(b; a) if R = P . Semantics An interpretation is I = ( I ; I ), where I is a non-empty set and I maps each a 2 NI to aI 2 I , each A 2 NC to AI I , and each P 2 NR to P I I I . The function I is straightforwardly extended to general concepts and roles, e.g. (9S)I = fc j 9d : (c; d) 2 SI g. I satisfies G v H if GI HI ; it satisfies A(a) (resp. P (a; b)) if aI 2 AI (resp. (aI ; bI ) 2 P I ). We write I j= if I satisfies inclusion/assertion . I is a model of K = (T ; A) if I satisfies all inclusions in T and assertions in A. A KB K is satisfiable/consistent if it has a model; otherwise it is unsatisfiable/inconsistent (K j= ?). We say that K entails , written K j= , if every model of K is a model of . The closure of T , written cl(T ), consists of all inclusions which are entailed from T . Given an ABox A, we denote by IA the interpretation which has as its domain the individuals in A and which makes true precisely the assertions in A. Queries A query is a formula of first-order logic with equality (FOL), whose atoms are of the form A(t), P (t; t0), or t = t0 with t; t0 terms, i.e., variables or individuals. Conjunctive queries are queries which do not contain 8, :, or =. Instance queries (IQs) are queries consisting of a single atom with no variables (i.e. ABox assertions). A Boolean query is a query with no free variables. For a Boolean query q, we write I j= q when q holds in the interpretation I, and K j= q when I j= q for all models I of K. 3
The most commonly used approach to query answering over inconsistent KBs is known as consistent query answering and relies on the notion of a repair: Definition 1. A repair of a knowledge base K = (T ; A) is an inclusion-maximal subset B of A consistent with T . We use Rep(K) to denote the set of repairs of K.
Consistent query answering consists in performing standard query answering on each of the repairs and intersecting the answers. For Boolean queries, we have: Definition 2. A Boolean query q is said to be consistently entailed from K = (T ; A), written K j=cons q, if T ; B j= q for every repair B 2 Rep(K).
Just as with standard query entailment, we can ask whether consistent query entailment can be tested by rewriting the query and evaluating it over the data. Definition 3. A first-order query q0 is a consistent rewriting of a Boolean query q w.r.t. a TBox T if for every ABox A, we have T ; A j=cons q if and only if IA j= q0.
We illustrate the notion of consistent rewriting on an example.
Example 1. Consider the query q = R(a; b) and the TBox T = f 9R v :D; 9R v :9S ; 9R v :Bg. We claim q0 = R(a; b) ^ :D(a) ^ :9xS(x; a) ^ :B(b) is a consistent rewriting of q w.r.t. T . To see why, note that if a repair implies q, then it must contain R(a; b). Moreover, if the ABox A contains any assertion that contradicts R(a; b) then we can build a repair which does not contain R(a; b). Thus, R(a; b) is consistently entailed just in the case that R(a; b) 2 A and there are no assertions in A which conflict with R(a; b), which is precisely what q0 states.
The method used in Example 1 can be generalized to show that a consistent
rewriting exists for all role instance queries1. Unfortunately, the same is not true for concept
IQs. Indeed, in [
9N v :9U ; 9U v A g m g [ f P (ci; vj ) j vj 2 cig [ f N (ci; vj ) j :vj 2 cig It is not hard to verify that ' is unsatisfiable if and only if K j=cons A(a). The basic idea is that, because of the inclusion 9P v :9N , each repair corresponds to a valuation of the variables, with vj assigned true if it has an incoming P -edge in the repair.
The focus in this paper will be on distinguishing between hard and easy instances of the consistent query answering problem. More specifically, we will be interested in the problem of deciding for a given TBox and IQ whether a consistent rewriting exists. 4
In formulating our results, it will be convenient to introduce some terminology for referring to assertions which participate in the entailment of another assertion or its negation. 1 Obviously this is no longer the case if we consider a logic with role inclusions like DL-LiteR. Definition 4. Let ; be assertions and of) given , written an inclusion. We say . We say
causes (or is a cause conflicts with (or is a 7 ! conflict for) given , written ! j= B2(a) for some a. Sometimes we omit , if f g; f g j= , if = B1 v :B2 and j= B1(a) and
if its identity is not relevant.
The following straightforward proposition characterizes consistent instance checking in terms of causes and conflicts.
Proposition 1. Let K = (T ; A) be a DL-Litecore KB and an instance query. Then K 6j=cons if and only if there exists a subset A0 A which is consistent with T and such that for every 2 A which causes (given some axiom in cl(T )), there is 2 A0 which conflicts with (given some axiom in cl(T )).
In other words, consistent instance checking comes down to deciding existence of a consistent subset of the ABox which contradicts all causes of the instance query.
We now introduce the notion of a cause-conflict chain. The intuition is as follows. Suppose that we have an assertion 0 in the ABox which causes the IQ . Then to show K 6j=cons , Proposition 1 says we must select some assertion 0 which conflicts with 0. But if 0 conflicts with an assertion 1 which is a conflict of another cause 1, then this forces us to choose a different conflict 1 for 1 which is consistent with 0. The presence of 1 may in turn attack a conflict of a third cause 3, leading us to select a conflict 3 for 3, and so on.
Definition 5. A cause-conflict chain (for TBox T and IQ ) is a sequence 0 0 1 1 1 2 2 2 : : : n n n n+1 n+1 of distinct assertions, together with a sequence 0 0 1 1 1 1 2 : : : n n n n+1 n+1 n+1 of inclusions from cl(T ), which satisfy: – for every i: i 7 !i , i i! i, i – if j < i, then we do not have i ! j – f 0; 1; : : : ; ng is consistent with T i+1 ! i+1, and i i ! i Examples of cause-conflict chains can be found in Figure 1a(b) and 2(b). In the following sections, we will consider particular types of cause-conflict chains and see how they are related to the presence of a consistent rewriting. 5
In this section, we formulate a general condition which can be used to show co-NPhardness of consistent instance checking. We begin by giving a more elaborate reduction from UNSAT, and then we analyze what is needed to make the proof go through. Example 3. Consider the following TBox T : f 9R0 v A; 9R1 v A; 9R2 v A; 9R3 v A; 9R0 v :9S; 9S 9R1 v :D1; D1 v :B2; B2 v :9R2 ; 9R2 v :D2; D2 v :9T ; 9T v :9R3 g R1R2
B1D1B2D2 vj S S T ci+ R0 a ci−
R3 (a) ABox
B1D1B2D2
vk+i S T
R1R2
R0(a, b) S(b, c) B1(c) D1(c) ∃S− ¬B1
A(a) ∃ R0 A
∃ R3 A ∃ R1 A ∃ R2 A
R1(a, c) R2(a, c) ∃R0− ¬∃S B1 ¬∃R1− ∃R1− ¬D1 B2 ¬∃R2− ∃R2− ¬D2 ∃T ¬∃R3−
B2(c) D2(c)
T (d, c) conflicts
D1 ¬B2 (b) Cause-conflict chain
D2 ¬∃T−
R3(a, d) causes
We show using a reduction from UNSAT that deciding whether T ; A j=cons A(a) is co-NP-hard in data complexity. Given a propositional CNF ' = c1 ^ : : : ^ cm over v1; : : : ; vk, we define A as follows (see Figure 1(a) for a pictorial representation): f R0(a; ci+); R3(a; ci ) j 1 i m g [ f R1(a; vj ); R2(a; vj ) j 1 j k + m g [ f S(ci+; vj ) j vj 2 cig [ f T (ci ; vj ) j :vj 2 cig [ f S(ci+; vk+i) j 1 f T (ci ; vk+i) j 1 i mg [ f B1(vj ); B2(vj ); D1(vj ); D2(vj ) j 1 i j mg [ k + mg We show that ' j= ? if and only if T ; A j=cons A(a). For the first direction, suppose we have a satisfying valuation for ', and let V be the set of variables which are affected to true. We assume without loss of generality that if a variable vj appears only positively (resp. negatively) in ' then vj 2 V (resp. vj 62 V ). Define the subset B of A as follows: f S(ci+; vj ); D1(vj ); D2(vj ) 2 A j vj 2 V; 1 f T (ci ; vj ); B1(vj ); B2(vj ) 2 A j vj 62 V; 1 j j kg [ kg [ f T (ci ; vk+i); B1(vk+i); B2(vk+i) 2 A j 9vj 2 V with vj 2 cig [ f S(ci+; vk+i); D1(vk+i); D2(vk+i) 2 A j 8vj 2 V : vj 62 cig It is easy to check that B is consistent with T and that T ; B 6j= A(a). It can also be verified that adding any additional assertions from A to B leads to a contradiction. In particular, note that either a clause ci has some positive variable vj 2 V , in which case S(ci+; vj ); T (ci ; vk+i) 2 B, or it contains no such vj , in which case S(ci+; vk+i); T (ci ; vj ) 2 B. In either case, both R0(a; ci+) and R3(a; ci ) conflict with an assertion in B. Thus, B is a repair of A w.r.t. T which does not entail A(a).
For the other direction, let B be a repair with T ; B 6j= A(a). It follows that none of the role assertions in A involving R0; R1; R2; R3 appear in B. The absence of R1- and R2-assertions and the consistency of B with T together imply that for each vj , we have either B1 and B2 or both D1 and D2. This means each vj has either incoming S-edges or incoming T -edges, but not both. We create a valuation in which vj is affected to true if and only if vj has an incoming S-edge. Clearly if ci has a positive literal vj which is affected to true, then it will be satisfied by this valuation. If instead all of the positive literals in ci are affected to false, then the absence of R0(a; ci+) can only be explained by the presence in B of the assertion S(ci+; vk+i). But this implies in turn the absence of T (ci ; vk+i) in B. As R3(a; ci ) 62 B, there must be some assertion in B of the form T (ci ; v`) (1 ` k). This means v` will be affected to false by our valuation, and hence the clause will be satisfied. Thus, the formula ' is satisfiable.
To understand how the preceding reduction can be generalized, it is helpful to consider the cause-conflict chain pictured in Figure 1(b). This chain contains the essential structure used in the reduction, with individuals b, c, and d playing the roles of ci+, vj , and c` . We first notice that at the start and end of the chain, there is a switch of individuals, which corresponds to moving from ci+ to vj and then back to c` . Next remark that in order to show consistency of the constructed B, we needed consistency of the sets of “forward” assertions fS(b; c); D1(c); D2(c)g and “backward” assertions fB1(c); B2(c); T (d; c)g. Also note that in order to use a repair to construct a satisfying valuation, we had to prove that no vj had both incoming S- and T -edges. This involved showing that the only way to simultaneously contradict all Ri assertions while retaining consistency was to choose all of the forward (Di) or all of the backward (Bi) assertions. Key to this reasoning was the fact that for each Ri(a; vj ) assertion, we were forced to choose either Bi(vj ) or Di(vj ). If we could use some B`(vj ) or D`(vj ) with ` 6= j, the line of reasoning fails. Finally we note that none of the conflicts in the chain involves the query individual a. This is important because if we used some assertion C(a) to contradict Ri(a; vj ), then we would also contradict Ri(a; v`) when ` 6= j, making it impossible to independently choose truth values for each variable.
The preceding analysis leads us to define the notion of a position (to be able to talk about switching to a new individual) and the notion of type-1 cause-conflict chains. Definition 6. Concepts of the forms A or 9P (resp. 9P ) are said to have position 1 (resp. 2). An inclusion begins (resp. concludes) on position p, written bpos( ) = p (resp. cpos( ) = p), if p is the position associated with lhs( ) (resp. rhs( )). Definition 7. A cause-conflict chain for T and
0 0 1 1 : : : n n+1 n+1 and sequence of inclusions 0 0 1 1 1 : : : n+1 n+1 n+1 is said to be of type-1 if it satisfies the following conditions: defined by the sequence of assertions (C1) bpos( i) 6= bpos( i) and bpos( i) 6= cpos( i) for all i (C2) cpos( 0) 6= bpos( 1) (C4) f 1; : : : ; n+1g is consistent with T (C3) cpos( n+1) 6= bpos( n+1) (C5) if j > i, then we do not have i ! j
Condition C1 of the definition states that the query individual is not used in the conflicts, whereas C2 and C3 make sure there is a switch to a new individual at the start and end of the chain. Condition C4 guarantees consistency of the “backward” conflict assertions, and C5 ensures that when reading the chain from right to left all causes are relevant (i.e. not already contradicted by one of the previous choices).
Example 4. If B1 v :B2 were added to the TBox from Example 3, then the chain from Figure 1(b) would not be type-1, since B1(c) and B2(c) would conflict (violating C4).
The next result shows that the presence of a type-1 cause-conflict chain is sufficient to show co-NP-hardness (and a fortiori, the lack of a consistent rewriting). The proof generalizes the reduction from Example 3.
Theorem 1. If a type-1 cause-conflict chain for T and exists, then the problem of deciding whether T ; A j=cons is co-NP-hard in data complexity.
∃ R A
R(a, c) ∃ R A R(a, b)
S(b, c) ∃R− ¬∃S
B ¬∃R−
∃R− ¬∃S B ¬∃R−
B(c) S(c, d) ∃S− ¬B ∃S− ¬B (b) Cause-conflict chain ∃ R A R(a, d) B(d) In this section, we use Ehrenfeucht-Fra¨ısse´ games to prove nonexistence of a consistent rewriting. As in the previous section, we start with an illustrative example, before formulating the general condition.
Example 5. Consider the following DL-Litecore TBox T :
T = f 9R v A; 9R v :9S; 9R v :B; 9S v :B g We show using Ehrenfeucht-Fra¨ısse´ games that there is no consistent first-order rewriting of the query A(a) w.r.t. T . Consider some k 2 N, and let m = 2k + 1. We construct two ABoxes A1 and A2 as follows (A1 is pictured in Figure 2(a)):
A1 A2 = = f R(a; bi); R(a; ci); B(ci); S(ci; ci+1) j 1 f B(bi) j 2 i m g [ f S(bi; bi+1); j 1 i i mg [ m 1 g
A1 n fB(c1)g [ fB(b1)g We show that T ; A1 j=cons A(a) and T ; A2 6j=cons A(a). For the first point, suppose for a contradiction that there is a repair B of A1 w.r.t. T such that T ; B 6j= A(a). Then there can be no assertions in B of the form R(a; bi), and hence each such assertion must provoke a contradiction when added to B. In order for B [ fR(a; b1)g to be inconsistent with T , we must have S(b1; b2) 2 B, as S(b1; b2) is the only assertion in A which conflicts with R(a; b1). But this means that B(b2) 62 B, and hence that S(b2; b3) 2 B, or else we could add R(a; b2) to B without provoking a contradiction. Continuing in this manner, we find that S(bm 1; bm) 2 B, and so B(bm) 62 B. But in this case, B [ fR(a; bm)g is consistent with T , which contradicts the maximality of B. For the second point, we remark that the set B = fB(bi); S(ci; ci+1) j 1 i mg is a repair of A2 w.r.t. T such that T ; B 6j= A(a).
We now must show that duplicator has a k-round winning strategy in the
EhrenfeuchtFra¨ısse´ game based on interpretations IA1 and IA2 . The basic idea is as follows (we
defer the full argument to [
n
The following theorem states that type-2 cause-conflict chains witness nonexistence of a consistent rewriting. The proof generalizes the argument outlined in Example 5. Theorem 2. If there exists a type-2 cause-conflict chain for T and , then there is no consistent first-order rewriting for w.r.t. T .
We next establish the relationship between type-1 and type-2 chains.
Theorem 3. If there exists a type-1 cause-conflict chain for T and , then there also exists a type-2 cause-conflict chain. The converse does not hold (assuming P6=NP). Proof (Sketch). For the first point, the idea to take a second copy of the type-1 chain, reverse it, and append it to the original. For the second point, we show that consistent instance checking for the TBox and IQ from Example 5 can be done in polynomial time by iteratively applying the following rule: if R(a; c) 2 A and there is no S(c; d) 2 A, then delete all incoming S-edges to c. We continue until either we find R(a; c) 2 A such that neither B(c) nor any S(c; d) belongs to A (in which case A(a) is consistently entailed), or the rule is no longer applicable (and A(a) is not consistently entailed). 7
In this section, we develop a procedure which is guaranteed to produce a consistent rewriting whenever the TBox T and query = A(a) satisfy the following two criteria: Ordering There exists a total order < on CauseT(A) such that whenever a causeconflict chain begins with inclusion B1 v A, ends with inclusion B2 v A, and satisfies conditions C1 and C3, we have B2 < B1.
No loops Every cause-conflict chain for T ; of length n+1 which satisfies cpos( i) = bpos( i) for every 1 i n + 1 is such that i 6= j for all i 6= j < n + 1. where CauseT(A) = fD j D v A 2 cl(T )g is the set of cause-types of A. We define the set of conflict-types of A analogously: Con T(A) = fD j D v :A 2 cl(T )g. Algorithm 1 Rewrite Input: TBox T , IQ A(a) Output: a first-order query ' Initialize ' to ? and initialize G to the set of all tuples (C; D) which satisfy: (a) C = fC 2 CauseT(A) j 9D 2 D with D 2 Con T(C)g (b) for all D 2 D, there exists C 2 C such that D 2 Con T(C) (c) there do not exist D1; D2 2 D with D2 2 Con T(D1) For every (C; D) 2 G // choose which cause-types to treat globally
Let D = fB1; : : : ; Bk; 9P1; : : : ; 9P`; 9P`+1; : : : ; 9Pm g (Bi 2 NC, Pi 2 NR) S = fBi(a)gik=1 [ fPi(a; wi)gi`=1 [ fPi(wi; a)gim=`+1 // realize concepts in D at a // compute inequalities needed to ensure consistency (treating variables as individuals) I = fvi 6= vj j vi; vj 2 fa; w1; : : : ; wmg and T ; S [ fvi = vjg j= ?g U = CauseT(A) n C // cause-types not yet treated ' = ' _ 9w1:::wm V 2S ^ V 2I ^ VC2U (8x auxRewrite(T ; A(a); C; x; S)) Output :'
Our algorithm Rewrite creates a big disjunction, where each disjunct corresponds to a choice of a set of cause-types to be conflicted globally, i.e. one single assertion involving the query individual is used to conflict all causes of that type. For each disjunct, we first fix the assertions which realize these global conflicts, and then invoke subroutine auxRewrite to build one conjunct per untreated cause-type whose purpose is to see whether for each cause of that type there is an assertion which conflicts with it and can safely be added to the repair under construction. These conjuncts have a tree-like structure whose “paths” are cause-conflict chains which satisfy cpos( i) = bpos( i) for all i. Property No Loops can thus be applied to show that the recursion depth of auxRewrite is no more than jCauseT(A)j + 1, ensuring termination. The difficult step in the correctness proof is to show IA 6j= Rewrite(T , q) implies T ; A 6j=cons q. The basic idea is to use the way the negation of the formula is satisfied to direct our construction of a repair which conflicts with every cause of q. Ordering is used to decide in which order we should treat the causes. We illustrate this idea on a concrete example: Example 6. Let q = A(a) and T be the following TBox: f 9R0 v A; 9R1 v A; 9R2 v A; 9R0 v :9S; 9S 9R1 v :D1; D1 v :9T ; B1 v :9T ; 9T v :9R2 g It can be verified that the negation of Rewrite(T ; q) consists of a single disjunct: 8x R0(a; x) ! 9y(S(x; y) ^ (R1(a; y) ! D1(y))) ^ 8x R1(a; x) ! (B1(x) _ D1(x)) 8x R2(a; x) ! 9y(T (x; y) ^ :R1(a; y)) ^ We show that if this formula is satisfied in IA, then we can construct a repair B of A w.r.t. T which does not entail A(a). First we fix an order on CauseT(A) satisfying the conditions in Ordering: 9R0 < 9R2 < 9R1. This means we start by considering causes via 9R0. If R0(a; b) 2 A, then the first conjunct allows us to find c such that S(b; c) 2 A and R1(a; c) 2 A implies D1(c) 2 A. We add S(b; c) to B, and also add D1(c) if R1(a; c) 2 A. We then move on to the next cause-type in the order, 9R2. If we have R2(a; b) 2 A, then we use the third conjunct to find c such that T (b; c) 2 A Algorithm 2 auxRewrite Output Input: TBox T , IQ A(a), C 2 CauseT(A), variable x, S set of atoms Output: a first-order query If C 2 NC, output :C(a) Set = R(a; x), = : , and B = 9R where C = 9R // R basic role For each D 2 Con T(B) // Consider different ways to contradict on x
Set = D(x) if D 2 NC and = T (x; y) [y fresh variable] if D = 9T If is necessarily inconsistent with S given T , exit the for-loop Else, let be the inequalities needed to ensure f g [ S is consistent with T // Compute untreated causes which are affected by choice of Initialize to ; For all 9V 2 CauseT(A) such that T ; S [ f g [ fV (a; x)g 6j= ? and Con T(9V ) \ Con T(D) 6= ;
Add (9V; x) to // need to find conflict for cause V (a; x) If D = 9T , then for all 9V 2 CauseT(A) with T ; S [ f g [ fV (a; y)g 6j= ? and Con T(9V ) \ Con T(9T ) 6= ;
Add (9V; y) to // need to find conflict for cause V (a; y) = _ (9y)( ^ ^ V(H;v)2 auxRewrite(T ; A(a); H; v; S [ f g)) and R1(a; c) 62 A, and we add T (b; c) to B. Finally we turn to the final cause-type 9R1, and let R1(a; b) 2 A. Possibly we have already added D1(b) when dealing with the first conjunct, in which case we do nothing. Otherwise, because of the second conjunct, we have either B1(b) 2 A or D1(b) 2 A, which we can add to B. The set B is still consistent with T after this step, since if T (e; b) 2 B then we would have R1(a; b) 62 A, and if S(e; b) 2 B, then we would have already added a conflict for R1(a; b). We have thus found a set B which is consistent with T and contradicts every assertion which could cause entailment of A(a). By Proposition 1, we have T ; A 6j=cons A(a). Theorem 4. If a TBox T and IQ q satisfy conditions Ordering and No Loops, then Rewrite(T , q) terminates and outputs a consistent rewriting of q w.r.t. T . Theorem 4 can be used to derive simpler sufficient conditions, like the following: Corollary 1. Rewrite(T , A(a)) terminates with the correct output if there do not exist basic roles R; S with T j= 9R v A and T j= 9R v :9S. 8
In order to obtain a more generally applicable positive result, we consider a sound approximation of consistent query answering, which we term cautious query answering. K j=caut q, if T ; \B2Rep(K)B j= q.
Definition 9. A query q is cautiously entailed by a knowledge base K = (T ; A), written
In [
Example 7. If q = 9y B(x) ^ R(x; y) and T = fA v B; A v 9R; B v :D; 9R v :9S g, standard rewriting yields A(x) _ 9y B(x) ^ R(x; y). We then add :9zS(z; y) to the second disjunct and :D(x) to both to obtain the cautious rewriting.
Theorem 5 is easily extended to other DL-Lite logics enjoying FO-rewritability. 9
In this paper, we took a closer look at the problem of consistent instance checking in DL-Lite and identified some general conditions which can be used to prove the absence or existence of a consistent rewriting. While our results were formulated for DL-Litecore, we expect they can be easily lifted to more expressive DL-Lite dialects.
The main objective for future work is to strengthen our results so as to be able to
decide for every TBox and instance query whether a consistent rewriting exists. We
conjecture that the absence of a type-2 cause-conflict chain is both a necessary and
sufficient condition for existence of a consistent rewriting. Extending our investigation
to conjunctive queries would be interesting but quite challenging, as it would likely
involve confronting longstanding open problems from the database community, where
a full characterization of rewritable cases remains elusive [