=Paper=
{{Paper
|id=None
|storemode=property
|title=First-Order Expressibility Results for Queries over Inconsistent DL-Lite Knowledge Bases
|pdfUrl=https://ceur-ws.org/Vol-745/paper_38.pdf
|volume=Vol-745
|dblpUrl=https://dblp.org/rec/conf/dlog/Bienvenu11
}}
==First-Order Expressibility Results for Queries over Inconsistent DL-Lite Knowledge Bases==
https://ceur-ws.org/Vol-745/paper_38.pdf
First-Order Expressibility Results for Queries over
Inconsistent DL-Lite Knowledge Bases
Meghyn Bienvenu
CNRS & Université Paris Sud, France
meghyn@lri.fr
1 Introduction
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 [3, 2]) is considered especially
well-suited for such applications due to the fact that query answering can be performed
by first incorporating the relevant information from the ontology into the query, and
then posing the modified query to the bare data. This property, known as first-order
rewritability, means that query answering over DL-Lite ontologies has very low data
complexity, which is considered key to scalability.
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 mod-
ify 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. [4] for a survey) under the name of consistent query answering. The stan-
dard approach is based on the notion of a repair, which is a database which satisfies
the integrity constraints and is as similar as possible to the original database. Consistent
answers are defined as those answers which hold in all repairs. A similar strategy can
be used for description logics by replacing the integrity constraints with the ontology.
Consistent query answering for the DL-Lite family of description logics was re-
cently studied in [8, 7]. Unfortunately, the obtained complexity results are rather neg-
ative: consistent query answering is co-NP-hard in data complexity, even for instance
queries and the simplest dialect DL-Litecore . In the database community, negative re-
sults were also encountered, but this spurred a line of research [5, 6, 9] aimed at identi-
fying cases where consistent query answering is feasible, and in particular, can be done
using query rewriting. We propose to carry out a similar investigation for DL-Lite on-
tologies, with the aim of better understanding the cases in which query rewriting can be
profitably used. In this paper, we make some first steps towards this goal. Specifically,
we formulate general conditions which can be used to prove that a consistent rewriting
does or does not exist for a given DL-Litecore TBox and instance query.
The paper is organized as follows. After some preliminaries, we introduce in Sec-
tions 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 [1].
2 Preliminaries
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 con-
structed using the following syntax:
B → A | ∃R C → B | ¬B R → P | P−
where A ∈ NC and P ∈ 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 ∈ NC ) or R(a, b) (R ∈ NR ) where a, b ∈ NI . A KB consists of a TBox and an ABox.
Notational conventions We use lhs(Γ ) (resp. rhs(Γ )) to refer to the basic concept ap-
pearing on the left (resp. right) side of an inclusion Γ , e.g. lhs(∃P v ¬D) = ∃P and
rhs(∃P v ¬D) = D. We sometimes use R− to mean P − if R = P ∈ 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 ∈ NI to aI ∈ ∆I , each A ∈ NC to AI ⊆ ∆I , and each P ∈ NR to
P I ⊆ ∆I × ∆I . The function ·I is straightforwardly extended to general concepts and
roles, e.g. (∃S)I = {c | ∃d : (c, d) ∈ S I }. I satisfies G v H if GI ⊆ H I ; it satisfies
A(a) (resp. P (a, b)) if aI ∈ AI (resp. (aI , bI ) ∈ P I ). We write I |= α 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 unsat-
isfiable/inconsistent (K |= ⊥). We say that K entails α, written K |= α, 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. Con-
junctive queries are queries which do not contain ∀, ¬, 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 |= q when q
holds in the interpretation I, and K |= q when I |= q for all models I of K.
3 Consistent query answering
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 |=cons q, if T , B |= q for every repair B ∈ Rep(K).
Just as with standard query entailment, we can ask whether consistent query entail-
ment can be tested by rewriting the query and evaluating it over the data.
Definition 3. A first-order query q 0 is a consistent rewriting of a Boolean query q w.r.t.
a TBox T if for every ABox A, we have T , A |=cons q if and only if IA |= q 0 .
We illustrate the notion of consistent rewriting on an example.
Example 1. Consider the query q = R(a, b) and the TBox T = { ∃R v ¬D, ∃R v
¬∃S − , ∃R− v ¬B}. We claim q 0 = R(a, b) ∧ ¬D(a) ∧ ¬∃xS(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) ∈ A and there are no assertions in A
which conflict with R(a, b), which is precisely what q 0 states.
The method used in Example 1 can be generalized to show that a consistent rewrit-
ing exists for all role instance queries1 . Unfortunately, the same is not true for concept
IQs. Indeed, in [7], it was shown that consistent instance checking in DL-Litecore is
co-NP-hard in data complexity. We present the reduction in the following example.
Example 2. Consider an instance ϕ = c1 ∧ . . . ∧ cm of UNSAT, where each ci is a
propositional clause. Let v1 , . . . , vk be the propositional variables appearing in ϕ. We
define the DL-Litecore knowledge base K = (T , A) as follows:
T = { ∃P − v ¬∃N − , ∃P v ¬∃U − , ∃N v ¬∃U − , ∃U v A }
A = { U (a, ci ) | 1 ≤ i ≤ m } ∪ { P (ci , vj ) | vj ∈ ci } ∪ { N (ci , vj ) | ¬vj ∈ ci }
It is not hard to verify that ϕ is unsatisfiable if and only if K |=cons A(a). The basic idea
is that, because of the inclusion ∃P − v ¬∃N − , 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 Causes and conflicts
In formulating our results, it will be convenient to introduce some terminology for refer-
ring 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 Υ an inclusion. We say β causes (or is a cause
Υ
of) α given Υ , written β 7−→ α, if {Υ }, {β} |= α. We say β conflicts with (or is a
Υ
conflict for) α given Υ , written β •−−−→ α, if Υ = B1 v ¬B2 and β |= B1 (a) and
α |= B2 (a) for some a. Sometimes we omit Υ if its identity is not relevant.
The following straightforward proposition characterizes consistent instance check-
ing in terms of causes and conflicts.
Proposition 1. Let K = (T , A) be a DL-Litecore KB and α an instance query. Then
K 6|=cons α if and only if there exists a subset A0 ⊆ A which is consistent with T and
such that for every β ∈ A which causes α (given some axiom in cl(T )), there is γ ∈ 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 6|=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:
Υ i Γi Σi+1 Ωi
– for every i: µi 7−−→ α, µi •−−−→ ρi , ρi •−−−−−→ λi+1 , and µi •−−−→ λi
– if j < i, then we do not have µi •−→ ρj
– {ρ0 , ρ1 , . . . , ρn } is consistent with T
Examples of cause-conflict chains can be found in Figure 1a(b) and 2(b). In the follow-
ing sections, we will consider particular types of cause-conflict chains and see how they
are related to the presence of a consistent rewriting.
5 General co-NP-hardness result
In this section, we formulate a general condition which can be used to show co-NP-
hardness of consistent instance checking. We begin by giving a more elaborate reduc-
tion from UNSAT, and then we analyze what is needed to make the proof go through.
Example 3. Consider the following TBox T :
{ ∃R0 v A, ∃R1 v A, ∃R2 v A, ∃R3 v A, ∃R0 v ¬∃S, ∃S − v ¬B1 , B1 v ¬∃R1− ,
∃R1− v ¬D1 , D1 v ¬B2 , B2 v ¬∃R2− , ∃R2− v ¬D2 , D2 v ¬∃T − , ∃T − v ¬∃R3− }
A(a)
B1 D1 B2 D2 B1 D1 B2 D2 ∃R0 � A ∃R3 � A
vj vk+i ∃R1 � A ∃R2 � A
S
S S T R0 (a, b) R1 (a, c) R2 (a, c) R3 (a, d) causes
T
c+
i c−
i
∃R0− � ¬∃S B1 � ¬∃R1− ∃R1− � ¬D1 B2 � ¬∃R2− ∃R2− � ¬D2 ∃T � ¬∃R3−
R1 R2
R0 R3 R1 R2
S(b, c) B1 (c) D1 (c) B2 (c) D2 (c) T (d, c) conflicts
a ∃S − � ¬B1 D1 � ¬B2 D2 � ¬∃T −
(a) ABox (b) Cause-conflict chain
Fig. 1: ABox and type-1 cause-conflict chain for Example 3.
We show using a reduction from UNSAT that deciding whether T , A |=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):
−
{ R0 (a, c+
i ), R3 (a, ci ) | 1 ≤ i ≤ m } ∪ { R1 (a, vj ), R2 (a, vj ) | 1 ≤ j ≤ k + m } ∪
−
i , vj ) | vj ∈ ci } ∪ { T (ci , vj ) | ¬vj ∈ ci } ∪ { S(ci , vk+i ) | 1 ≤ i ≤ m} ∪
{ S(c+ +
{ T (c−
i , vk+i ) | 1 ≤ i ≤ m} ∪ { B1 (vj ), B2 (vj ), D1 (vj ), D2 (vj ) | 1 ≤ j ≤ k + m}
We show that ϕ |= ⊥ if and only if T , A |=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 ∈ V (resp. vj 6∈ V ). Define the subset B of A as follows:
i , vj ), D1 (vj ), D2 (vj ) ∈ A | vj ∈ V, 1 ≤ j ≤ k} ∪
{ S(c+
{ T (c−
i , vj ), B1 (vj ), B2 (vj ) ∈ A | vj 6∈ V, 1 ≤ j ≤ k} ∪
{ T (c−
i , vk+i ), B1 (vk+i ), B2 (vk+i ) ∈ A | ∃vj ∈ V with vj ∈ ci } ∪
i , vk+i ), D1 (vk+i ), D2 (vk+i ) ∈ A | ∀vj ∈ V : vj 6∈ ci }
{ S(c+
It is easy to check that B is consistent with T and that T , B 6|= A(a). It can also
be verified that adding any additional assertions from A to B leads to a contradic-
tion. In particular, note that either a clause ci has some positive variable vj ∈ V ,
−
in which case S(c+ i , vj ), T (ci , vk+i ) ∈ B, or it contains no such vj , in which case
− −
S(ci , vk+i ), T (ci , vj ) ∈ B. In either case, both R0 (a, c+
+
i ) 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 6|= 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, c+ i ) can only be explained
by the presence in B of the assertion S(c+ i , vk+i ). But this implies in turn the absence
of T (c− −
i , vk+i ) in B. As R3 (a, ci ) 6∈ 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 con-
sider 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 c+ i ,
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 c+ i to v j 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 {S(b, c), D1 (c), D2 (c)} and “backward” assertions
{B1 (c), B2 (c), T (d, c)}. 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 ∃P (resp. ∃P − ) 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 α defined by the sequence of assertions
µ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:
(C1) bpos(Υi ) 6= bpos(Γi ) and bpos(Υi ) 6= cpos(Ωi ) for all i
(C2) cpos(Γ0 ) 6= bpos(Σ1 ) (C4) {λ1 , . . . , λn+1 } 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 |=cons α is co-NP-hard in data complexity.
B B B
S S S S
b1 bm A(a)
...
∃R � A ∃R � A
R R ∃R � A
R R
a R(a, b) R(a, c) R(a, d)
R R
R R ∃R− � ¬∃S B � ¬∃R− ∃R− � ¬∃S B � ¬∃R−
...
c1 cm cm+1
S S S S S S(b, c) B(c) S(c, d) B(d)
B B B B ∃S − � ¬B ∃S − � ¬B
(a) ABox A1 (b) Cause-conflict chain
Fig. 2: ABox and Type-2 cause-conflict chain used in Example 5.
6 General first-order inexpressibility result
In this section, we use Ehrenfeucht-Fraı̈ssé games to prove nonexistence of a consis-
tent 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 = { ∃R v A, ∃R− v ¬∃S, ∃R− v ¬B, ∃S − v ¬B }
We show using Ehrenfeucht-Fraı̈ssé games that there is no consistent first-order rewrit-
ing of the query A(a) w.r.t. T . Consider some k ∈ N, and let m = 2k + 1. We construct
two ABoxes A1 and A2 as follows (A1 is pictured in Figure 2(a)):
A1 = { R(a, bi ), R(a, ci ), B(ci ), S(ci , ci+1 ) | 1 ≤ i ≤ m} ∪
{ B(bi ) | 2 ≤ i ≤ m } ∪ { S(bi , bi+1 ), | 1 ≤ i ≤ m − 1 }
A2 = A1 \ {B(c1 )} ∪ {B(b1 )}
We show that T , A1 |=cons A(a) and T , A2 6|=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 6|= 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 ∪ {R(a, b1 )} to be inconsistent
with T , we must have S(b1 , b2 ) ∈ B, as S(b1 , b2 ) is the only assertion in A which
conflicts with R(a, b1 ). But this means that B(b2 ) 6∈ B, and hence that S(b2 , b3 ) ∈ 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 ) ∈ B, and so B(bm ) 6∈ B. But in this case,
B ∪ {R(a, bm )} is consistent with T , which contradicts the maximality of B. For the
second point, we remark that the set B = {B(bi ), S(ci , ci+1 ) | 1 ≤ i ≤ m} is a repair
of A2 w.r.t. T such that T , B 6|= A(a).
We now must show that duplicator has a k-round winning strategy in the Ehrenfeucht-
Fraı̈ssé game based on interpretations IA1 and IA2 . The basic idea is as follows (we
defer the full argument to [1]). Whenever spoiler selects a point which is “closer” to
the side of bm /cm+1 in IA1 , duplicator responds with the identical point in IA2 . When
spoiler plays “closer” to the b1 /c1 side, then duplicator plays ci if bi was played, and bi
if ci was played. The important thing is to make sure there is sufficient distance between
the indices j where duplicator copies spoiler and those where he chooses differently.
This can be done by keeping track of the rightmost point where the choices differ and
the leftmost point where they coincide and ensuring that the distance between these
points is always at least 2k−i , where i is the the current round of play.
Figure 2(b) presents a cause-conflict chain for the preceding example. Most of the
conditions we identified in the previous section continue to hold for this chain. The only
exception is that we do not have a switch of individuals at the end of the chain. Instead,
we can remark that the initial cause-type is repeated further down the chain and can be
contradicted in the same way, and this is what we use to create the long chain structure
required in the proof. This leads us to define a second class of cause-conflict chains, in
which we replace C3 with a new condition which captures this repetition.
Definition 8. A cause-conflict chain for T and α whose sequence of inclusions is Υ0 Γ0
Σ1 Ω1 Υ1 . . . Σn+1 Ωn+1 Υn+1 is said to be type-2 if it satisfies C1, C2, C4, C5, and C6:
(C6) Υ0 = Υn and Γ0 = Γ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) ∈ A and there is no S(c, d) ∈ A,
then delete all incoming S-edges to c. We continue until either we find R(a, c) ∈ 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 Rewriting Procedure
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 cause-
conflict 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) = {D | D v A ∈ cl(T )} is the set of cause-types of A. We define
the set of conflict-types of A analogously: ConflT(A) = {D | D v ¬A ∈ cl(T )}.
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 = {C ∈ CauseT(A) | ∃D ∈ D with D ∈ ConflT(C)}
(b) for all D ∈ D, there exists C ∈ C such that D ∈ ConflT(C)
(c) there do not exist D1 , D2 ∈ D with D2 ∈ ConflT(D1 )
For every (C, D) ∈ G // choose which cause-types to treat globally
− −
Let D = {B1 , . . . , Bk , ∃P1 , . . . , ∃P` , ∃P`+1 , . . . , ∃Pm } (Bi ∈ NC , Pi ∈ NR )
k ` m
S = {Bi (a)}i=1 ∪ {Pi (a, wi )}i=1 ∪ {Pi (wi , a)}i=`+1 // realize concepts in D at a
// compute inequalities needed to ensure consistency (treating variables as individuals)
I = {vi 6= vj | vi , vj ∈ {a, w1 , . . . , wm } and T , S ∪ {vi = vj } |= ⊥}
U = CauseT(A) \ C V // cause-types V not yetVtreated
ϕ = ϕ ∨ ∃w1 ...wm β∈S β ∧ γ∈I γ ∧ C∈U (∀x 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 in-
volving 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 subrou-
tine 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 |CauseT(A)| + 1, ensuring termination. The difficult step
in the correctness proof is to show IA 6|= Rewrite(T , q) implies T , A 6|=cons q. The
basic idea is to use the way the negation of the formula is satisfied to direct our con-
struction 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:
{ ∃R0 v A, ∃R1 v A, ∃R2 v A, ∃R0− v ¬∃S, ∃S − v ¬B1 , B1 v ¬∃R1− ,
∃R1− v ¬D1 , D1 v ¬∃T − , B1 v ¬∃T − , ∃T v ¬∃R2− }
It can be verified that the negation of Rewrite(T , q) consists of a single disjunct:
∀x R0 (a, x) → ∃y(S(x, y) ∧ (R1 (a, y) → D1 (y)))
∧ ∀x R1 (a, x) → (B1 (x) ∨ D1 (x))
∧ ∀x R2 (a, x) → ∃y(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: ∃R0 < ∃R2 < ∃R1 . This means we start by considering
causes via ∃R0 . If R0 (a, b) ∈ A, then the first conjunct allows us to find c such that
S(b, c) ∈ A and R1 (a, c) ∈ A implies D1 (c) ∈ A. We add S(b, c) to B, and also add
D1 (c) if R1 (a, c) ∈ A. We then move on to the next cause-type in the order, ∃R2 . If
we have R2 (a, b) ∈ A, then we use the third conjunct to find c such that T (b, c) ∈ A
Algorithm 2 auxRewrite
Input: TBox T , IQ A(a), C ∈ CauseT(A), variable x, S set of atoms
Output: a first-order query χ
If C ∈ NC , output ¬C(a)
Set α = R(a, x), χ = ¬α, and B = ∃R− where C = ∃R // R basic role
For each D ∈ ConflT(B) // Consider different ways to contradict α on x
Set β = D(x) if D ∈ NC and β = T (x, y) [y fresh variable] if D = ∃T
If β is necessarily inconsistent with S given T , exit the for-loop
Else, let be the inequalities needed to ensure {β} ∪ S is consistent with T
// Compute untreated causes which are affected by choice of β
Initialize ∆ to ∅
For all ∃V ∈ CauseT(A) such that T , S ∪ {β} ∪ {V (a, x)} 6|= ⊥ and
ConflT(∃V − ) ∩ ConflT(D) 6= ∅
Add (∃V, x) to ∆ // need to find conflict for cause V (a, x)
If D = ∃T , then for all ∃V ∈ CauseT(A) with T , S ∪ {β} ∪ {V (a, y)} 6|= ⊥
and ConflT(∃V − ) ∩ ConflT(∃T − ) 6= ∅
Add (∃V, y) to ∆ V// need to find conflict for cause V (a, y)
χ = χ ∨ (∃y)(β ∧ ∧ (H,v)∈∆ auxRewrite(T , A(a), H, v, S ∪ {β}))
Output χ
and R1 (a, c) 6∈ A, and we add T (b, c) to B. Finally we turn to the final cause-type ∃R1 ,
and let R1 (a, b) ∈ 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) ∈ A or D1 (b) ∈ A, which we can add to B. The set B is still
consistent with T after this step, since if T (e, b) ∈ B then we would have R1 (a, b) 6∈ A,
and if S(e, b) ∈ 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 6|=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 |= ∃R v A and T |= ∃R− v ¬∃S.
8 Approximating Consistent Query Answering
In order to obtain a more generally applicable positive result, we consider a sound ap-
proximation of consistent query answering, which we term cautious query answering.
Definition 9. A query q is cautiously entailed by a knowledge base K = (T , A), written
K |=caut q, if T , ∩B∈Rep(K) B |= q.
In [7], cautious conjunctive query answering (there called Intersection ABox Repair
semantics) was shown to be tractable for DL-LiteR KBs. The proposed algorithm first
deletes all assertions involved in some conflict, and then queries the resulting ABox. It
was left open whether query rewriting techniques could be used instead. We answer this
question in the affirmative and thus obtain an improved upper bound of AC0 .
Theorem 5. Cautious conjunctive query answering is in AC0 for DL-Litecore .
Proof (Sketch). Given a DL-Litecore TBox T and a CQ q, we first compute (in the
standard manner) a UCQ q 0 = q1 ∨ ... ∨ qn such that for all ABoxes A, we have
T , A |= q if and only if IA |= q 0 . Then to each disjunct we add the negation of each
atomic query which could contradict one of the atoms in the disjunct.
Example 7. If q = ∃y B(x) ∧ R(x, y) and T = {A v B, A v ∃R, B v ¬D, ∃R− v
¬∃S − }, standard rewriting yields A(x) ∨ ∃y B(x) ∧ R(x, y). We then add ¬∃zS(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 Conclusion and Future Work
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 [9].
References
1. http://www.lri.fr/∼meghyn/BienvenuDL11-long.pdf.
2. Allessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev. The
DL-Lite family and relations. Journal of Artificial Intelligence Research, 36:1–69, 2009.
3. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Ric-
cardo Rosati. Tractable reasoning and efficient query answering in description logics: The
DL-Lite family. Journal of Automated Reasoning, 39(3):385–429, 2007.
4. Jan Chomicki. Consistent query answering: Five easy pieces. In Proc. of ICDT, pages 1–17,
2007.
5. Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. In
Proc. of ICDT, pages 337–351, 2005.
6. Luca Grieco, Domenico Lembo, Riccardo Rosati, and Marco Ruzzi. Consistent query answer-
ing under key and exclusion dependencies: algorithms and experiments. In Proc. of CIKM,
pages 792–799, 2005.
7. Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio
Savo. Inconsistency-tolerant semantics for description logics. In Proc. of RR (Web Reasoning
and Rule Systems), pages 103–117, 2010.
8. Domenico Lembo and Marco Ruzzi. Consistent query answering over description logic on-
tologies. In Proc. of RR (Web Reasoning and Rule Systems), pages 194–208, 2007.
9. Jef Wijsen. On the first-order expressibility of computing certain answers to conjunctive
queries over uncertain databases. In Proc. of PODS, pages 179–190, 2010.