In recent years, there has been growing interest in using description logic (DL)
ontologies to query instance data. An important issue which arises in this setting
is how to handle the case in which the data (ABox) is inconsistent with the
ontology (TBox). Ideally, one would like to restore consistency by identifying and
correcting the errors in the data (using e.g. techniques for debugging or revising
DL knowledge bases, cf. [
The related problem of querying databases which violate integrity constraints
has long been studied in the database community (cf. [
Consistent query answering for the DL-Lite family of lightweight DLs was
investigated in [
In the database community, negative complexity results spurred a line of
research [
The main objective of the present work is to gain a better understanding of what makes consistent conjunctive query answering in the presence of ontologies so di cult. To this end, we conduct a ne-grained complexity analysis which aims to characterize the complexity of consistent query answering based on the properties of the ontology and the conjunctive query. We focus on simple ontologies, consisting of class subsumption (A1 v A2) and class disjointness (A1 v :A2) axioms, since the problem is already far from trivial for this case. We identify the number of quanti ed variables in the query as an important factor in determining the complexity of consistent query answering. Speci cally, we show that consistent query answering is always rst-order expressible for conjunctive queries with at most one quanti ed variable; the problem has polynomial data complexity (but is not necessarily rst-order expressible) when there are two quanti ed variables; and it may become coNP-hard starting from three quanti ed variables. For queries having at most two quanti ed variables, we further identify a necessary and su cient condition for rst-order expressibility.
To obtain positive results for arbitrary conjunctive queries, we propose a
novel inconsistency-tolerant semantics which is a sound approximation of the
consistent query answering semantics (and a ner approximation than the
approximate semantics proposed in [
Full proofs can be found in a long version available on the author's website. 2
Syntax. All the ontology languages considered in this paper are fragments of
DL-Litecore [
C ! B j :B
P ! R j R where A 2 NC and R 2 NR. A TBox is a nite set of inclusions of the form B v C (B; C as above). An ABox is a nite set of (ABox) assertions of the form A(a) (A 2 NC) or R(a; b) (R 2 NR), where a; b 2 NI. We use Ind(A) to denote the set of individuals in A. A KB consists of a TBox and an ABox. 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. (:A)I = I n AI and (9S)I = fc j 9d : (c; d) 2 SI g. I satis es G v H if GI HI ; it satis es A(a) (resp. P (a; b)) if aI 2 AI (resp. (aI ; bI ) 2 P I ). We write I j= if I satis es inclusion/assertion . An interpretation I is a model of K = (T ; A) if I satis es all inclusions in T and assertions in A. We say a KB K is consistent if it has a model, and that K entails an inclusion/assertion , written K j= , if every model of K is a model of .
We say that a set of concepts fC1; : : : ; Cng is consistent w.r.t. a TBox T if there is a model I of T and an element e 2 I such that e 2 Ci for every 1 i n. Entailment of a concept from a set of concepts is de ned in the obvious way: T j= S v D if and only if for every model I of T , we have \C2S CI DI . Queries A ( rst-order) query is a formula of rst-order logic with equality, whose atoms are of the form A(t) (A 2 NC), R(t; t0) (R 2 NR), or t = t0 with t; t0 terms, i.e., variables or individuals. Conjunctive queries (CQs) have the form 9y , where y denotes a tuple of variables, and is a conjunction of atoms of the forms A(t) or R(t; t0). Instance queries are queries consisting of a single atom with no variables (i.e. ABox assertions). Free variables in queries are called answer variables, whereas bound variables are called quanti ed variables. We use terms(q) to denote the set of terms appearing in a query q.
A Boolean query is a query with no answer 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. For a non-Boolean query q with answer variables v1; : : : ; vk, a tuple of individuals (a1; : : : ; ak) is said to be a certain answer for q w.r.t. K just in the case that K j= q[a1; : : : ; ak], where q[a1; : : : ; ak] is the Boolean query obtained by replacing each vi by ai. Thus, conjunctive query answering is straightforwardly reduced to entailment of Boolean CQs.
First-order rewritability Calvanese et al. [
In this section, we formally recall the consistent query answering semantics, present some simple examples which illustrate the di culty of the problem, and introduce the main problem which will be studied in this paper. For readability, we will formulate our de nitions and results in terms of Boolean CQs, but they can be straightforwardly extended to general CQs.
The key notion underlying consistent query answering semantics is that of a repair of an ABox A, which is an ABox which is consistent with the TBox and as similar as possible to A. In this paper, we follow common practice and use subset inclusion to compare ABoxes.
Consistent query answering can be seen as performing standard query answering on each of the repairs and intersecting the answers. For Boolean queries, the formal de nition is as follows:
(T ; A), written T ; A j=cons q, if T ; B j= q for every repair B 2 RepT (A).
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.
q w.r.t. a TBox T if for every ABox A, we have T ; A j=cons q i IA j= q0.
As mentioned in Section 1, consistent query answering in DL-Litecore is
co-NP-hard in data complexity, even for instance queries [
Example 1. We use a variant of UNSAT, called 2+2UNSAT, proved coNP-hard
in [
k g [ fT (true); F (false)g Then one can show that ' is unsatis able just in the case that (T ; A) consistently entails the following query: 9xy1... y4P1(x; y1)^F (y1)^P2(x; y2)^F (y2)^N1(x; y3)^T (y3)^N2(x; y4)^T (y4) Essentially, T v :F forces the choice of a truth value for each variable, so the repairs of A correspond exactly to the set of valuations. Importantly, there is only one way to avoid satisfying a 2+2-clause: the rst two variables must be assigned false and the last two variables must be assigned true. The existence of such a con guration is checked by q.
We remark that the query in the preceding reduction does not have a particularly complicated structure (in particular, it is tree-shaped). Its only notable property is that it has several quanti ed variables.
In this paper, we aim to gain a better understanding of what makes consistent conjunctive query answering so di cult (and conversely, what can make it easy). To this end, we will consider the following decision problem:
ConsEnt(q; T ): Is A such that T ; A j=cons q? and we will try to characterize its complexity in terms of the properties of the pair (q; T ). We will in particular investigate the impact of limiting the number of quanti ed variables in the query q.
In the next three sections, we focus on simple ontologies, consisting of inclusions of the forms A1 v A2 and A1 v :A2 where A1; A2 2 NC. As Example 1 demonstrates, the problem is already non-trivial in this case. All obtained lower bounds transfer to richer ontologies, and we will show in Section 7 that positive results can also be extended to DL-Litecore ontologies without inverse roles. 4
In this section, we investigate the complexity of consistent query answering in the presence of simple ontologies for CQs having at most two quanti ed variables. We show this problem has tractable data complexity, and we provide necessary and su cient conditions for FO-expressibility.
We begin with queries with at most one quanti ed variable, showing that a consistent rewriting always exists.
Proof (Sketch). We show how to construct the desired consistent rewriting of q in the case where q has a single quanti ed variable x. First, for each t 2 terms(q), we set Ct = fA j A(t) 2 qg, and we let t be the set of all S NC such that every maximal subset U S consistent with T is such that T j= U v Ct. Intuitively, t de nes the possible circumstances under which the conjunction of concepts in Ct is consistently entailed. We can express this condition with the rst-order formula t: t = _ ( ^ S2 t A2S
A(t) ^
^ A2NCnS :A(t)) Now using the t, we construct q0: q0 = 9x
^ R(t;t0)2q
R(t; t0) ^
^ t2terms(q) t It can be shown that q0 is indeed a consistent rewriting of q w.r.t. T . To see why this is so, it is helpful to remark that the repairs of (T ; A) contain precisely the role assertions in A, together with a maximal subset of concept assertions consistent with T for each individual.
The next example shows that Theorem 1 cannot be extended to the class of queries with two quanti ed variables. A A A A . . . A A A B B B B B B B
A1
A A A A . . . A A A
B B B B B B A A A A . . . A A B B B B B B B
A2
Example 2. Consider q = 9xy A(x)^R(x; y)^B(y) and T = fA v :Bg. Suppose
for a contradiction that q0 is a consistent rewriting of q w.r.t. T , and let k be the
quanti er rank of q0. In Fig. 1, we give two ABoxes A1 and A2, each consisting
of two R-chains of length > 2k. It can be veri ed that q is consistently entailed
from T ; A1. This is because in every repair, the upper chain will have A at one
end, B at the other, and either an A or B at all interior points; every such
con guration makes q true somewhere along the chain. On the other hand, we
can construct a repair for T ; A2 which does not entail q by always preferring A
on the top chain and B on the bottom chain. It follows that the interpretation
IA1 satis es q0, whereas IA2 does not. However, one can show using standard
tools from nite model theory (cf. Ch. 3-4 of [
We can generalize the preceding example to obtain su cient conditions for the inexistence of a consistent rewriting.
quanti ed variables x; y. Assume that there do not exist CQs q1 and q2, each with less than two quanti ed variables, such that q q1 ^ q2. Denote by Cx (resp. Cy) the set of concepts A such that A(x) 2 q (resp. A(y) 2 q). Then ConsEnt(q; T ) is not rst-order expressible if there exists S NC such that: - for v 2 fx; yg, there is a maximal subset Dv
T 6j= Dv v Cv - for every maximal subset D
T j= D v Cy
S consistent with T , either T j= D v Cx or Proof (Sketch). The proof generalizes the argument outlined in Example 2. Instead of having a single role connecting successive elements in the chains, we establish the required relational structure for each pair of successive points. We then substitute the set Dy for A, the set Dx for B, and the set S for fA; Bg. The properties of S ensure that if S is asserted at some individual, then we can block the satisfaction of Cx using Dy, and we can block Cy using Dx, but we can never simultaneously block both Cx and Cy. The assumption that q cannot be rewritten as a conjunction of queries with less than two quanti ed variables is used in the proof of T ; A2 6j=cons q to show that the only possible matches of q involve successive chain elements (and not constants from the query). To show IA1 and IA2 cannot be distinguished, we use Ehrenfeucht-Frasse games, rather than Hanf locality, since the latter is inapplicable when there is a role atom containing a constant and a quanti ed variable.
The following theorem shows that whenever the conditions of Theorem 2 are not met, a consistent rewriting exists.
quanti ed variables x; y. Then ConsEnt(q; T ) is rst-order expressible if q is equivalent to a CQ with at most one quanti ed variable, or if there is no set S satisfying the conditions of Theorem 2.
Proof (Sketch). When q is equivalent to a query q0 with at most one quanti ed variable, then Theorem 1 yields a consistent rewriting of q0, and hence of q. Thus, the interesting case is when there is no such equivalent query, nor any set S satisfying the conditions of Theorem 2. Intuitively, the inexistence of such a set S ensures that if at some individual, one can block Cx, and one can block Cy, then it is possible to simultaneously block Cx and Cy (compare this to Example 2 in which blocking A causes B to hold, and vice-versa). This property is key, as it allows di erent potential query matches to be treated independently.
Together, Theorems 2 and 3 provide a necessary and su cient condition for the existence of a consistent rewriting. We now reconsider T and q from Example 2 and outline a polynomial-time method for solving ConsEnt(q; T ). Example 3. Suppose we have an ABox A, and we wish to decide if T ; A j=cons q, for T = fA v :Bg and q = 9xy A(x) ^ R(x; y) ^ B(y). The basic idea is to try to construct a repair which does not entail q. We start by iteratively applying the following rules until neither rule is applicable: (1) if R(a; b); A(a); B(a); B(b) 2 A but A(b) 62 A, then delete A(a) from A, and (2) if R(a; b); A(a); A(b); B(b) 2 A but B(a) 62 A, then delete B(b). Note that since the size of A decreases with every rule application, we will stop after a polynomial number of iterations. Once nished, we check whether there are a; b such that A(a); R(a; b); B(b) 2 A, B(a) 62 A, and A(b) 62 A. If so, we return `yes' (to indicate T ; A j=cons q), and otherwise, we output no' (for T ; A 6j=cons q). Note that in the latter case, for all pairs a; b with A(a); R(a; b); B(b) 2 A, we have both B(a) and A(b). Thus, we can choose to always keep A, thereby blocking all remaining potential matches.
By carefully generalizing the ideas outlined in Example 3, we obtain a tractability result which covers all queries having at most two quanti ed variables.
5
The objective of this section is to show that the tractability result we obtained for queries with at most two quanti ed variables cannot be extended further AC vi vjAC a
B to the class of conjunctive queries with three quanti ed variables. We will do this by establishing coNP-hardness for a speci c conjunctive query with three quanti ed variables, thereby improving the lower bound sketched in Example 1. Speci cally, we will reduce 3SAT to ConsEnt(q; T ) where:
T = fA v :B; A v :C; B v :Cg q = 9x; y; z A(x) ^ R(x; y) ^ B(y) ^ R(y; z) ^ C(z).
The rst component of the reduction is a mechanism for choosing truth values for the variables. For this, we create an ABox Avi = fA(vi); C(vi)g for each variable vi. It is easy to see that there are two repairs for Avi w.r.t. T : fA(vi)g and fC(vi)g. We will interpret the choice of A(vi) as assigning true to vi, and the presence of C(vi) to mean that vi is false.
Next we need some way of verifying whether a clause is satis ed by the valuation associated with a repair of [iAvi . To this end, we create an ABox Ac` for each clause c`; the ABox A' encoding ' will then simply be the union of the ABoxes Avi and Ac` . The precise de nition of the ABox Ac` is a bit delicate and depends on the polarity of the literals in c`. Figure 2 presents a pictorial representation of Ac` for the case where c` = :vi _ :vj _ :vk (the ABoxes Avi , Avj , and Avk are also displayed).
Let us now see how the ABox Ac` pictured in Fig. 2 can be used to test the satisfaction of c`. First suppose that we have a repair B of A' which contains A(vi); A(vj ), and A(vk), i.e. the valuation associated with the repair does not satisfy c`. We claim that this implies that q holds. Suppose for a contradiction that q is not entailed from T ; B. We rst note that by maximality of repairs, B must contain all of the assertions A(vj ); R(vj ; a`); B(a`), and R(a`; c`2). It follows that including C(c`2) in B would cause q to hold, which means we must choose to include B(c`2) instead. Using similar reasoning, we can see that in order to avoid satisfying q, we must have C(d`) in B rather than B(d`), which in turn forces us to select C(c`3) to block A(c`3). However, this is a contradiction, since we have identi ed a match for q in B with x = vi; y = c`2; z = c`3. The above argument (once extended to the other possible forms of Ac` ) is the key to showing that the unsatis ability of ' implies T ; A' j= q.
Conversely, it can be proven that if one of c`'s literals is made true by the valuation, then it is possible to repair Ac` in such a way that a match for q is avoided. For example, consider again Ac` from Figure 2, and suppose that the second literal vj is satis ed. It follows that C(vj ) 2 B, hence A(vj ) 62 B, which means we can keep C(c`2) rather than B(c`2), thereby blocking the match at (vi; c`2; c`3). By showing this property holds for the di erent forms of Ac` , and by further arguing that we can combine \q-avoiding" repairs of the Ac` without inducing a match for q, we can prove that the satis ability of ' implies T ; A' 6j= q. We thus have: Theorem 5. ConsEnt(q; T ) is coNP-hard in data complexity for T = fA v :B; A v :C; B v :Cg and q = 9x; y; z A(x) ^ R(x; y) ^ B(y) ^ R(y; z) ^ C(z). 6
The positive results from Section 4 give us a polynomial algorithm for consistent query answering in the presence of simple ontologies, but only for CQs with at most two quanti ed variables. In order to be able to handle all queries, we explore in this section alternative inconsistency-tolerant semantics which are sound approximations of the consistent query answering semantics.
One option is to adopt the IAR semantics from [
To obtain a ner approximation of the consistent query answering semantics, we propose a new inconsistency-tolerant semantics which corresponds to closing repairs with respect to the TBox before intersecting them. In the following de nition, we use clT (B) to denote the set of assertions entailed from T ; B.
semantics (\intersection of closed repairs"), written T ; A j=ICR q, if T ; D j= q, where D = TB2RepT (A) clT (B).
The following theorem, which is easy to prove, establishes the relationship among the three semantics.
T ; A j=IAR q )
T ; A j=ICR q )
T ; A j=cons q
The next example illustrates the di erence between IAR and ICR semantics: Example 4. Let T = fA v C; B v C; A v :Bg and A = fA(a); B(a)g. Then C(a) is entailed from (T ; A) under ICR semantics, but not under IAR semantics.
Finally, we show that under ICR semantics, we can answer any conjunctive query in polynomial time using query rewriting.
Proof (Sketch). We rst compute, using standard techniques, a union of conjunctive queries ' such that for every A, we have T ; A j= q if and only if IA j= '. Next we use Theorem 1 to nd a consistent rewriting A(t) of each concept atom A(t) 2 ', and we let q0 be the rst-order query obtained by replacing each occurrence of A(t) in ' by A(t). It can be shown that the query q0 is such that T ; A j=ICR q if and only if IA j= q0. 7
In this section, we show how the techniques we developed for simple ontologies can be used to extend our positive results to DL-Litecore ontologies which do not contain inverse roles (we will use DL-Liteno to refer to this logic).
Our rst result shows that the analogues of Theorems 1 and 4 hold for DL-Liteno ontologies. The main technical di culty in adapting the proofs of Theorems 1 and 4 is that role assertions may now be contradicted, which means repairs need not have the same set of role assertions as the original ABox.
at most two quanti ed variables. Then ConsEnt(q; T ) is polynomial in data complexity, and rst-order expressible if there is at most one quanti ed variable.
We can also extend the general rst-order expressibility result for the new ICR semantics (Theorem 7) to the class of DL-Liteno ontologies.
there exists a rst-order query q0 such that for every ABox A: T ; A j=ICR q if and only if IA j= q0.
As noted earlier, consistent query answering in (full) DL-Litecore is coNPhard in data complexity even for instance queries, which means that neither of the preceding theorems can be extended to the class of DL-Litecore ontologies. 8
The detailed complexity analysis we conducted for consistent query answering
in the presence of simple ontologies provides further insight into previously
obtained negative complexity results [
There are several natural directions for future work. First, it would be
interesting to explore how far we can push our positive results. We expect that
adding Horn inclusions and positive role inclusions should be unproblematic, but
role disjointness axioms will be more challenging. In order to handle functional
roles, we might try to combine our positive results with those which have been
obtained for relational databases under functional dependencies [
Finally, we view the present work as a useful starting point in the
development of sound but incomplete consistent query answering algorithms for popular
lightweight DLs like (full) DL-Litecore and E L?. For example, our results could
be extended to identify some CQ-TBox pairs in these richer logics for which
consistent query answering is tractable. Another idea is to use the new ICR
semantics to lift tractability results for IQs (like those in [