=Paper=
{{Paper
|id=None
|storemode=property
|title=Inconsistency-Tolerant Conjunctive Query Answering for Simple Ontologies
|pdfUrl=https://ceur-ws.org/Vol-846/paper_29.pdf
|volume=Vol-846
|dblpUrl=https://dblp.org/rec/conf/dlog/Bienvenu12
}}
==Inconsistency-Tolerant Conjunctive Query Answering for Simple Ontologies==
https://ceur-ws.org/Vol-846/paper_29.pdf
Inconsistency-Tolerant Conjunctive Query
Answering for Simple Ontologies
Meghyn Bienvenu
LRI - CNRS & Université Paris-Sud, France
www.lri.fr/∼meghyn/ meghyn@lri.fr
1 Introduction
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. [13]). However, such an approach requires the ability to
modify the data and the necessary domain knowledge to determine which part
of the data is erroneous. When these conditions are not met (e.g. in information
integration applications), an alternative is to adopt an inconsistency-tolerant
semantics in order to obtain reasonable answers despite the inconsistencies.
The related problem of querying databases which violate integrity constraints
has long been studied in the database community (cf. [1] and the survey [6]),
under the name of consistent query answering. The semantics is based upon 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 query answering
corresponds to evaluating the query in each of the repairs, and then intersecting
the results. This semantics is easily adapted to the setting of ontology-based data
access, by defining repairs as the inclusion-maximal subsets of the data which
are consistent with the ontology.
Consistent query answering for the DL-Lite family of lightweight DLs was
investigated in [10, 11]. The obtained complexity results are rather disheartening:
the problem was shown in [10] to be co-NP-hard in data complexity, even for
instance queries; this contrasts sharply with the very low AC0 data complexity for
(plain) conjunctive query answering in DL-Lite. Similarly discouraging results
were recently obtained in [14] for another prominent lightweight DL EL⊥ [3]. In
fact, we will see in Example 1 that if we consider conjunctive queries, only a single
concept disjointness axiom is required to obtain co-NP-hard data complexity.
In the database community, negative complexity results spurred a line of re-
search [8, 9, 15] aimed at identifying cases where consistent query answering is
feasible, and in particular, can be done using first-order query rewriting tech-
niques. The idea is to use targeted polynomial-time procedures whenever possi-
ble, and to reserve generic methods with worst-case exponential behavior for dif-
ficult cases (see [9] for some experimental results supporting such an approach).
A similar investigation for DL-Lite ontologies was initiated in [4], where general
conditions were identified for proving either first-order expressibility or coNP-
hardness of consistent query answering for a given TBox and instance query.
The main objective of the present work is to gain a better understanding
of what makes consistent conjunctive query answering in the presence of on-
tologies so difficult. To this end, we conduct a fine-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 sim-
ple 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 quantified variables in the query as an important factor in
determining the complexity of consistent query answering. Specifically, we show
that consistent query answering is always first-order expressible for conjunctive
queries with at most one quantified variable; the problem has polynomial data
complexity (but is not necessarily first-order expressible) when there are two
quantified variables; and it may become coNP-hard starting from three quan-
tified variables. For queries having at most two quantified variables, we further
identify a necessary and sufficient condition for first-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 finer approximation than the ap-
proximate semantics proposed in [10]). We show that under this semantics, first-
order expressibility of consistent query answering is guaranteed for all conjunc-
tive queries. Finally, in order to treat more expressive ontologies, and to demon-
strate the applicability of our techniques, we show how our positive results can
be extended to handle DL-Litecore ontologies without inverse roles.
Full proofs can be found in a long version available on the author’s website.
2 Preliminaries
Syntax. All the ontology languages considered in this paper are fragments of
DL-Litecore [5, 2]. We recall that DL-Litecore knowledge bases (KBs) are built
up from a set NI of individuals, a set NC of atomic concepts, and a set NR of
atomic roles. Complex concept and role expressions are constructed as follows:
B → A | ∃P C → B | ¬B P → R | R−
where A ∈ NC and R ∈ NR . A TBox is a finite set of inclusions of the form
B v C (B, C as above). An ABox is a finite set of (ABox) assertions of the
form A(a) (A ∈ NC ) or R(a, b) (R ∈ NR ), where a, b ∈ 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 ∈ 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. (¬A)I = ∆I \ AI and (∃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 α. An
interpretation I is a model of K = (T , A) if I satisfies 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 |= α, if every model of K is a model of α.
We say that a set of concepts {C1 , . . . , Cn } is consistent w.r.t. a TBox T
if there is a model I of T and an element e ∈ ∆I such that e ∈ Ci for every
1 ≤ i ≤ n. Entailment of a concept from a set of concepts is defined in the obvious
way: T |= S v D if and only if for every model I of T , we have ∩C∈S C I ⊆ DI .
Queries A (first-order) query is a formula of first-order logic with equality,
whose atoms are of the form A(t) (A ∈ NC ), R(t, t0 ) (R ∈ NR ), or t = t0 with t, t0
terms, i.e., variables or individuals. Conjunctive queries (CQs) have the form
∃y ψ, 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 quantified 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 |= q when q holds in the interpretation I, and K |= q when I |= 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 |= 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. [5] proved that for everyDL-Litecore
TBox T and CQ q, there exists a first-order query q 0 such that for every ABox
A and tuple a: T , A |= q[a] ⇔ IA |= q 0 [a], where IA denotes the interpretation
with domain Ind(A) that makes true precisely the assertions in A.
3 Consistent Query Answering for Description Logics
In this section, we formally recall the consistent query answering semantics,
present some simple examples which illustrate the difficulty of the problem, and
introduce the main problem which will be studied in this paper. For readability,
we will formulate our definitions 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.
Definition 1. A repair of a DL ABox A w.r.t. a TBox T is an inclusion-
maximal subset B of A consistent with T . We use RepT (A) to denote the set of
repairs of A w.r.t. T .
Consistent query answering can be seen as performing standard query an-
swering on each of the repairs and intersecting the answers. For Boolean queries,
the formal definition is as follows:
Definition 2. A query q is said to be consistently entailed from a DL KB
(T , A), written T , A |=cons q, if T , B |= q for every repair B ∈ 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.
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 iff IA |= q 0 .
As mentioned in Section 1, consistent query answering in DL-Litecore is
co-NP-hard in data complexity, even for instance queries [10], which means in
particular that consistent rewritings need not exist. All known reductions make
crucial use of inverse roles, and indeed, we will show in Section 7 that consistent
instance checking is first-order expressible for DL-Litecore ontologies without in-
verse. However, in the case of conjunctive queries, the absence of inverses does
not guarantee tractability. Indeed, the next example shows that only a single
concept disjointness axiom can yield coNP-hardness.
Example 1. We use a variant of UNSAT, called 2+2UNSAT, proved coNP-hard
in [7], in which each clause has 2 positive and 2 negative literals, where literals
involve either regular variables or the truth constants true and false. Consider
an instance ϕ = c1 ∧ . . . ∧ cm of 2+2-UNSAT over v1 , . . . , vk , true, and false.
Let T = {T v ¬F }, and define A as follows:
{ P1 (ci , u), P2 (ci , x), N1 (ci , y), N2 (ci , z) | ci = u ∨ x ∨ ¬y ∨ ¬z, 1 ≤ i ≤ m}
∪ { T (vj ), F (vj ) | 1 ≤ j ≤ k } ∪ {T (true), F (false)}
Then one can show that ϕ is unsatisfiable just in the case that (T , A) consistently
entails the following query:
∃xy1 ... y4 P1 (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 first two variables must be
assigned false and the last two variables must be assigned true. The existence of
such a configuration 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 quantified variables.
In this paper, we aim to gain a better understanding of what makes consistent
conjunctive query answering so difficult (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 |=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 quantified variables in the query q.
In the next three sections, we focus on simple ontologies, consisting of inclu-
sions of the forms A1 v A2 and A1 v ¬A2 where A1 , A2 ∈ 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 Tractability for Queries with At Most Two Quantified
Variables
In this section, we investigate the complexity of consistent query answering in the
presence of simple ontologies for CQs having at most two quantified variables.
We show this problem has tractable data complexity, and we provide necessary
and sufficient conditions for FO-expressibility.
We begin with queries with at most one quantified variable, showing that a
consistent rewriting always exists.
Theorem 1. Let T be a simple ontology, and let q be a Boolean CQ with at
most one quantified variable. Then ConsEnt(q, T ) is first-order expressible.
Proof (Sketch). We show how to construct the desired consistent rewriting of q
in the case where q has a single quantified variable x. First, for each t ∈ terms(q),
we set Ct = {A | A(t) ∈ q}, 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 |= U v Ct . Intuitively,
Σt defines the possible circumstances under which the conjunction of concepts
in Ct is consistently entailed. We can express this condition with the first-order
formula ψt : _ ^ ^
ψt = ( A(t) ∧ ¬A(t))
S∈Σt A∈S A∈NC \S
0
Now using the ψt , we construct q :
^ ^
q 0 = ∃x R(t, t0 ) ∧ ψt
R(t,t0 )∈q t∈terms(q)
It can be shown that q 0 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 quantified variables.
A A
A A
... A A A A A A
... A A A
B B B B B B B B B B B B
A A
A A
... A A A A A A A
... A A
B B B B B B B B B B B B B B
A1 A2
Fig. 1: ABoxes for Example 2. Arrows indicate the role R, and each of the four
R-chains has length exceeding 2k .
Example 2. Consider q = ∃xy A(x)∧R(x, y)∧B(y) and T = {A v ¬B}. Suppose
for a contradiction that q 0 is a consistent rewriting of q w.r.t. T , and let k be the
quantifier rank of q 0 . In Fig. 1, we give two ABoxes A1 and A2 , each consisting
of two R-chains of length > 2k . It can be verified 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
configuration 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 satisfies q 0 , whereas IA2 does not. However, one can show using standard
tools from finite model theory (cf. Ch. 3-4 of [12]) that no formula of quantifier
rank k can distinguish IA1 and IA2 , yielding the desired contradiction.
We can generalize the preceding example to obtain sufficient conditions for
the inexistence of a consistent rewriting.
Theorem 2. Let T be a simple ontology, and let q be a Boolean CQ with two
quantified variables x, y. Assume that there do not exist CQs q1 and q2 , each with
less than two quantified variables, such that q ≡ q1 ∧ q2 . Denote by Cx (resp. Cy )
the set of concepts A such that A(x) ∈ q (resp. A(y) ∈ q). Then ConsEnt(q, T )
is not first-order expressible if there exists S ⊆ NC such that:
- for v ∈ {x, y}, there is a maximal subset Dv ⊆ S consistent with T s.t.
T 6|= Dv v Cv
- for every maximal subset D ⊆ S consistent with T , either T |= D v Cx or
T |= D v Cy
Proof (Sketch). The proof generalizes the argument outlined in Example 2. In-
stead 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 {A, B}.
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 quantified variables
is used in the proof of T , A2 6|=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-Fraı̈ssé games,
rather than Hanf locality, since the latter is inapplicable when there is a role
atom containing a constant and a quantified variable.
The following theorem shows that whenever the conditions of Theorem 2 are
not met, a consistent rewriting exists.
Theorem 3. Let T be a simple ontology, and let q be a Boolean CQ with two
quantified variables x, y. Then ConsEnt(q, T ) is first-order expressible if q is
equivalent to a CQ with at most one quantified variable, or if there is no set S
satisfying the conditions of Theorem 2.
Proof (Sketch). When q is equivalent to a query q 0 with at most one quantified
variable, then Theorem 1 yields a consistent rewriting of q 0 , 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 different potential query matches to be treated independently.
Together, Theorems 2 and 3 provide a necessary and sufficient 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 |=cons q,
for T = {A v ¬B} and q = ∃xy 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) ∈ A
but A(b) 6∈ A, then delete A(a) from A, and (2) if R(a, b), A(a), A(b), B(b) ∈ A
but B(a) 6∈ 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 finished, we check whether there are a, b such that A(a), R(a, b), B(b) ∈ A,
B(a) 6∈ A, and A(b) 6∈ A. If so, we return ‘yes’ (to indicate T , A |=cons q), and
otherwise, we output no’ (for T , A 6|=cons q). Note that in the latter case, for all
pairs a, b with A(a), R(a, b), B(b) ∈ 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 tract-
ability result which covers all queries having at most two quantified variables.
Theorem 4. Let T be a simple ontology, and let q be a CQ with at most 2
quantified variables. Then ConsEnt(q, T ) is polynomial in data complexity.
5 An Improved coNP Lower Bound
The objective of this section is to show that the tractability result we obtained
for queries with at most two quantified variables cannot be extended further
AC BC AC
vi c2� c3�
a�
B b� B
vj d� C
AC vk
AC BC e�
Fig. 2: Abox Ac` for clause c` = ¬vi ∨ ¬vj ∨ ¬vk
to the class of conjunctive queries with three quantified variables. We will do
this by establishing coNP-hardness for a specific conjunctive query with three
quantified variables, thereby improving the lower bound sketched in Example 1.
Specifically, we will reduce 3SAT to ConsEnt(q, T ) where:
T = {A v ¬B, A v ¬C, B v ¬C}
q = ∃x, y, z A(x) ∧ R(x, y) ∧ B(y) ∧ R(y, z) ∧ C(z).
The first component of the reduction is a mechanism for choosing truth values
for the variables. For this, we create an ABox Avi = {A(vi ), C(vi )} for each
variable vi . It is easy to see that there are two repairs for Avi w.r.t. T : {A(vi )}
and {C(vi )}. 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 satisfied by the
valuation associated with a repair of ∪i Avi . 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 definition 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 first note that by maximality of repairs, B
must contain all of the assertions A(vj ), R(vj , a` ), B(a` ), and R(a` , c2` ). It follows
that including C(c2` ) in B would cause q to hold, which means we must choose to
include B(c2` ) 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(c3` ) to block A(c3` ). However, this is a contradiction, since we have
identified a match for q in B with x = vi , y = c2` , z = c3` . The above argument
(once extended to the other possible forms of Ac` ) is the key to showing that
the unsatisfiability of ϕ implies T , Aϕ |= 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 satisfied. It follows that C(vj ) ∈ B, hence A(vj ) 6∈ B,
which means we can keep C(c2` ) rather than B(c2` ), thereby blocking the match
at (vi , c2` , c3` ). By showing this property holds for the different 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 satisfiability of ϕ implies
T , Aϕ 6|= q. We thus have:
Theorem 5. ConsEnt(q, T ) is coNP-hard in data complexity for T = {A v
¬B, A v ¬C, B v ¬C} and q = ∃x, y, z A(x) ∧ R(x, y) ∧ B(y) ∧ R(y, z) ∧ C(z).
6 Tractability through Approximation
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 quantified 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 [10]. We recall that this
semantics (denoted by |=IAR ) can be seen as evaluating queries against the ABox
corresponding to the intersection of the repairs. Conjunctive query answering
under IAR semantics was shown in [11] tractable for general CQs in the presence
of DL-Lite ontologies (and a fortiori simple ontologies) using query rewriting.
To obtain a finer approximation of the consistent query answering semantics,
we propose a new inconsistency-tolerant semantics which corresponds to clos-
ing repairs with respect to the TBox before intersecting them. In the following
definition, we use clT (B) to denote the set of assertions entailed from T , B.
Definition 4. A Boolean query q is said to be entailed from (T , A) under ICR
semantics (“intersection
T of closed repairs”), written T , A |=ICR q, if T , D |= q,
where D = B∈RepT (A) clT (B).
The following theorem, which is easy to prove, establishes the relationship
among the three semantics.
Theorem 6. For every Boolean CQ q and TBox T :
T , A |=IAR q ⇒ T , A |=ICR q ⇒ T , A |=cons q
The reverse implications do not hold.
The next example illustrates the difference between IAR and ICR semantics:
Example 4. Let T = {A v C, B v C, A v ¬B} and A = {A(a), B(a)}. 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.
Theorem 7. Let T be a simple ontology and q a Boolean CQ. Then there exists
a first-order query q 0 such that for every ABox A: T , A |=ICR q iff IA |= q 0 .
Proof (Sketch). We first compute, using standard techniques, a union of conjunc-
tive queries ϕ such that for every A, we have T , A |= q if and only if IA |= ϕ.
Next we use Theorem 1 to find a consistent rewriting ψA(t) of each concept atom
A(t) ∈ ϕ, and we let q 0 be the first-order query obtained by replacing each oc-
currence of A(t) in ϕ by ψA(t) . It can be shown that the query q 0 is such that
T , A |=ICR q if and only if IA |= q 0 .
7 Extension to Inverse-Free DL-Litecore
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 first result shows that the analogues of Theorems 1 and 4 hold for
DL-Liteno− ontologies. The main technical difficulty 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.
Theorem 8. Consider a DL-Liteno− ontology T , and a Boolean CQ q with
at most two quantified variables. Then ConsEnt(q, T ) is polynomial in data
complexity, and first-order expressible if there is at most one quantified variable.
We can also extend the general first-order expressibility result for the new
ICR semantics (Theorem 7) to the class of DL-Liteno− ontologies.
Theorem 9. Let T be a DL-Liteno− ontology, and let q be a Boolean CQ. Then
there exists a first-order query q 0 such that for every ABox A: T , A |=ICR q if
and only if IA |= q 0 .
As noted earlier, consistent query answering in (full) DL-Litecore is coNP-
hard 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 Conclusion and Future Work
The detailed complexity analysis we conducted for consistent query answering
in the presence of simple ontologies provides further insight into previously ob-
tained negative complexity results [10, 14], by making clear how little is needed to
obtain first-order inexpressibility or intractability. Our investigation also yielded
some positive results, including the identification of novel tractable cases, such
as inverse-free DL-Litecore ontologies coupled with CQs with at most two quan-
tified variables (or coupled with arbitary CQs, under the new ICR semantics).
There are several natural directions for future work. First, it would be in-
teresting 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 [15]. It would
also be interesting to try to build upon the results in this paper in order to
obtain a criterion for first-order expressibility (or tractability) which applies to
all conjunctive queries, regardless of the number of quantified variables.
Finally, we view the present work as a useful starting point in the develop-
ment of sound but incomplete consistent query answering algorithms for popular
lightweight DLs like (full) DL-Litecore and EL⊥ . 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 [4]) to classes of CQs.
References
1. Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent
databases. In: Proc. of PODS. pp. 68–79. ACM Press (1999)
2. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family
and relations. Journal of Artificial Intelligence Research 36, 1–69 (2009)
3. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Proc. of IJCAI. pp.
364–369 (2005)
4. Bienvenu, M.: First-order expressibility results for queries over inconsistent DL-
Lite knowledge bases. In: Proc. of DL (2011)
5. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable
reasoning and efficient query answering in description logics: The DL-Lite family.
Journal of Automated Reasoning 39(3), 385–429 (2007)
6. Chomicki, J.: Consistent query answering: Five easy pieces. In: Proc. of ICDT. pp.
1–17 (2007)
7. Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: Deduction in concept lan-
guages: From subsumption to instance checking. Journal of Logic and Computation
4(4), 423–452 (1994)
8. Fuxman, A., Miller, R.J.: First-order query rewriting for inconsistent databases.
In: Proc. of ICDT. pp. 337–351 (2005)
9. Grieco, L., Lembo, D., Rosati, R., Ruzzi, M.: Consistent query answering under
key and exclusion dependencies: algorithms and experiments. In: Proc. of CIKM.
pp. 792–799 (2005)
10. Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant
semantics for description logics. In: Proc. of RR. pp. 103–117 (2010)
11. Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Query rewriting for
inconsistent DL-Lite ontologies. In: Proc. of RR. pp. 155–169 (2011)
12. Libkin, L.: Elements of Finite Model Theory. Springer (2004)
13. Nikitina, N., Rudolph, S., Glimm, B.: Reasoning-supported interactive revision of
knowledge bases. In: Proc. of IJCAI. pp. 1027–1032 (2011)
14. Rosati, R.: On the complexity of dealing with inconsistency in description logic
ontologies. In: Proc. of IJCAI. pp. 1057–1062 (2011)
15. Wijsen, J.: On the first-order expressibility of computing certain answers to con-
junctive queries over uncertain databases. In: Proc. of PODS. pp. 179–190 (2010)