=Paper=
{{Paper
|id=None
|storemode=property
|title=Non-Uniform Data Complexity of Query Answering in Description Logics
|pdfUrl=https://ceur-ws.org/Vol-745/paper_35.pdf
|volume=Vol-745
|dblpUrl=https://dblp.org/rec/conf/dlog/LutzW11
}}
==Non-Uniform Data Complexity of Query Answering in Description Logics==
https://ceur-ws.org/Vol-745/paper_35.pdf
Non-Uniform Data Complexity of Query Answering in
Description Logics
Carsten Lutz1 and Frank Wolter2
1
Department of Computer Science, University of Bremen, Germany
2
Department of Computer Science, University of Liverpool, UK
clu@uni-bremen.de,Wolter@liverpool.ac.uk
1 Introduction
In recent years, the use of ontologies to access instance data has become increasingly
popular. The general idea is that an ontology provides a vocabulary or conceptual model
for the application domain, which can then be used as an interface for querying instance
data and to derive additional facts. In this emerging area, called ontology-based data
access (OBDA), it is a central research goal to identify ontology languages for which
query answering scales to large amounts of instance data. Since the size of the data is
typically very large compared to the size of the ontology and the size of the query, the
central measure for such scalability is provided by data complexity—the complexity of
query answering where only the data is considered to be an input, but both the query
and the ontology are fixed.
In description logic (DL), ontologies take the form of a TBox, instance data is stored
in an ABox, and the most important class of queries are conjunctive queries (CQs).
A fundamental observation regarding this setup is that, for expressive DLs such as
ALC and SHIQ, the complexity of query answering is coNP-complete [12] and thus
intractable (when speaking of complexity, we always mean data complexity). The most
popular strategy to avoid this problem is to replace ALC and SHIQ with less expres-
sive DLs that are Horn in the sense that they can be embedded into the Horn fragment
of first-order (FO) logic and have minimal models that can be exploited for PT IME
query answering. Horn DLs in this sense include, for example, logics from the EL and
DL-Lite families as well as Horn-SHIQ, a large fragment of SHIQ for which CQ-
answering is still in PT IME [12]. While CQ-answering in Horn-SHIQ and the EL
family of DLs is also hard for PT IME, the problem has even lower complexity in DL-
Lite. In fact, the design goal of DL-Lite was to achieve FO-rewritability, i.e., that any
CQ q and TBox T can be rewritten into an FO query q 0 such that the answers to q
w.r.t. T coincide with the answers that a standard database system produces for q 0 [6].
Achieving this goal requires CQ-answering to be in AC0 .
It thus seems that the data complexity of query answering in a DL context is well-
understood. However, all results discussed above are on the level of logics, i.e., each
result concerns a class of TBoxes that is defined syntactically through expressibility in a
certain logic, but no attempt is made to identify more structure inside these classes. The
aim of this paper is to advocate a fresh look on the subject, by taking a novel approach.
Specifically, we advocate a non-uniform study of the complexity of query answering
by considering data complexity on the level of individual TBoxes. For a TBox T , we
say that CQ-answering w.r.t. T is in PT IME if for every CQ q, there is a PT IME algo-
rithm that, given an ABox A, computes the answers to q in A w.r.t. T . In a similar way,
we can define coNP-hardness and FO-rewritability on the TBox level. The non-uniform
perspective allows us to investigate more fine-grained questions regarding the data com-
plexity of query answering such as: given an expressive DL L such as ALC or SHIQ,
how can one characterize those L-TBoxes T for which CQ-answering is in PT IME?
How can we do the same for FO-rewritability? Is there a dichotomy for the complexity
of query answering w.r.t. TBoxes formulated in L, such as: for any L-TBox T , CQ-
answering w.r.t. T is either in PT IME or coNP-hard?
In this paper, we consider TBoxes formulated in the expressive DL ALCF I, answer
some of the above questions, and take some steps towards others. Our main results are:
1. there is a dichotomy between PT IME and coNP-complete for CQ-answering w.r.t.
ALC-TBoxes if, and only if, Feder and Vardi’s dichotomy conjecture that “con-
straint satisfaction problems (CSPs) with finite template are in PT IME or NP-
complete” [10] is true; the same holds for ALCI-TBoxes;
2. there is no dichotomy between PT IME and coNP-complete for CQ-answering w.r.t.
ALCF-TBoxes, unless PT IME = NP; moreover, PT IME-complexity of CQ an-
swering and many related problems are undecidable for ALCF.
3. there is a dichotomy between PT IME and coNP-complete for CQ-answering w.r.t.
ALCF I-TBoxes of depth one, i.e., TBoxes where concepts have role depth ≤ 1;
4. FO-rewritability is decidable for Horn-ALCF I-TBoxes of depth two and all Horn-
ALCF-TBoxes;
It should be noted that there has been steady progress regarding the dichotomy con-
jecture of Feder and Vardi over the last fifteen years and though the problem is still
open, a solution does not seem completely out of reach [4, 5]. Our proof of Point 1 is
based on a novel connection between CSPs and query answering w.r.t. ALCI-TBoxes
that can be exploited to transfer numerous results from the CSP world to query answer-
ing w.r.t. ALCI-TBoxes and related problems. For example, together with [16, 5] we
obtain the following results on ‘FO-rewritability of ABox consistency’:
5. Given an ALCI-TBox T , it can be decided in NE XP T IME whether there is an FO-
sentence ϕT such that for all ABoxes A, A is consistent w.r.t. T iff A viewed as an
FO-structure satisfies ϕT . Moreover, such a sentence ϕT exists iff ABox consis-
tency w.r.t. T can be decided in non-uniform AC0 . Finally, if no such sentence ϕT
exists, then ABox consistency w.r.t. T is L OG S PACE-hard (under FO-reductions).
To prove our results, we introduce some new notions that are relevant for studying
the questions raised and prove some additional results of general interest. A central
such notion is materializability of a TBox T , which formalizes the existence of mini-
mal models as known from Horn-DLs. We show that, in the case of TBoxes of depth
one, materializability characterizes PT IME CQ-answering, which allows us to establish
Point 2 above. For TBoxes of unrestricted depth, non-materializability still provides a
sufficient condition for coNP-hardness of CQ-answering. We also develop the notion
of unraveling tolerance of a TBox T , which provides a sufficient condition for query
answering to be in PT IME. The resulting upper bound strictly generalizes the known
result that CQ-answering in Horn-ALCF I is in PT IME. Our framework also allows
to formally establish some common intuitions and beliefs held in the context of CQ-
answering in description logics. For example, we show that for any ALCF I-TBox T ,
CQ-answering is in PT IME iff answering positive existential queries is in PT IME iff
answering ELI-instance queries is in PT IME and likewise for FO-rewritability. An-
other observation in this spirit is that an ALCF I-TBox is materializable (has minimal
models) iff it is convex (a notion related to the entailment of disjunctions).
Most proofs in this paper are deferred to the (appendix of the) long version, which
is available at http://www.csc.liv.ac.uk/∼ frank/publ/publ.html.
2 Preliminaries
We use standard notation for the syntax and semantics of ALCF I and other well-
known DLs. Our TBoxes are finite sets of concept inclusions C v D, where C and D
are potentially compound concepts, and functionality assertions func(r), where r is a
potentially inverse role. ABoxes are finite sets of assertions A(a) and r(a, b) with A a
concept name and r a role name. We use Ind(A) to denote the set of individual names
used in the ABox A and sometimes write r− (a, b) ∈ A instead of r(b, a) ∈ A. For the
interpretation of individual names, we make the unique name assumption.
A first-order query (FOQ) q(x) is a first-order formula with free variables x con-
structed from atoms A(t), r(t, t0 ), and t = t0 (where t, t0 range over individual names
and variables) using negation, conjunction, disjunction, and existential quantification.
The variables in x are the answer variables of q. A FOQ without answer variables is
Boolean. We say that a tuple a ⊆ Ind(A) is an answer to q(x) in an interpretation I if
I |= q[a], where q[a] results from replacing the answer variables x in q(x) with a. A
tuple a ⊆ Ind(A) is a certain answer to q(x) in A given T , in symbols T , A |= q(a),
if I |= q[a] for all models I of A and T . Set certT (q, A) = {a | T , A |= q(a)}.
A positive existential query (PEQ) q(x) is a FOQ without negation and equality and
a conjunctive query (CQ) is a positive existential query without disjunction. If C is
an ELI-concept and a ∈ NI , then C(a) is an ELI-query (ELIQ). EL-queries (ELQs)
are defined analogously. Note that ELI-queries and EL-queries are always Boolean. In
what follows, we sometimes slightly abuse notation and use FOQ to denote the set of
all first-order queries, and likewise for CQ, PEQ, ELIQ, and ELQ.
Definition 1. Let T be an ALCF I-TBox. Let Q ∈ {CQ, PEQ, ELIQ, ELQ}. Then
– Q-answering w.r.t. T is in PT IME if for every q(x) ∈ Q, there is a polytime algo-
rithm that computes, given an ABox A, the answer certT (q, A);
– Q-answering w.r.t. T is coNP-hard if there is a Boolean q ∈ Q such that, given an
ABox A, it is coNP-hard to decide whether T , A |= q;
– T is FO-rewritable for Q iff for every q(x) ∈ Q one can effectively construct an
FO-formula q 0 (x) such that for every ABox A, certT (q, A) = {a | IA |= q 0 (a)},
where IA denotes A viewed as an interpretation.
The above notions of complexity are rather robust under changing the query language:
as we show next, neither the PT IME bounds nor FO-rewritability depend on whether
we consider PEQs, CQs, or ELIQs.
Theorem 1. For all ALCF I-TBoxes T , the following equivalences hold:
1. CQ-answering w.r.t. T is in PT IME iff PEQ-answering w.r.t. T is in PT IME iff
ELIQ-answering w.r.t. T is in PT IME;
2. T is FO-rewritable for CQ iff it is FO-rewritable for PEQ iff it is FO-rewritable
for ELIQ.
If T is an ALCF-TBox, then we can replace ELIQ in Points 1 and 2 with ELQ.
The proof is based on Theorems 2 and 3 below. Theorem 1 allows us to (sometimes)
speak of the ‘complexity of query answering’ without reference to a query language.
3 Materializability
An important tool we use for analyzing the complexity of query answering is the notion
of materializability of a TBox T , which means that computing the certain answers to
any query q and ABox A w.r.t. T reduces to evaluating q in a single model of A and T .
Definition 2. Let T be an ALCF I-TBox and Q ∈ {CQ, PEQ, ELIQ, ELQ}. T is Q-
materializable if for every ABox A that is consistent w.r.t. T , there exists a model I of
T and A such that I |= q[a] iff T , A |= q(a) for all q(x) ∈ Q and a ⊆ Ind(A).
We show that PEQ, CQ, and ELIQ-materializability coincide (and for ALC-TBoxes, all
these also coincide with ELQ-materializability). Materializability is also equivalent to
the following disjunction property (sometimes also called convexity): a TBox T has the
ABox disjunction property if for all ABoxes A and ELIQs C1 (a1 ), . . . , Cn (an ), from
T , A |= C1 (a1 ) ∨ . . . ∨ Cn (an ) it follows that T , A |= Ci (ai ), for some i ≤ n.
Theorem 2. Let T be an ALCF I-TBox. The following equivalences hold: T is PEQ-
materializable iff T is CQ-materializable iff T is ELIQ-materializable iff T has the
ABox disjunction property.
If T is an ALC-TBox, the above are equivalent to ELQ-materializability.
Because of Theorem 2, we sometimes use the term materializability without reference
to a query language. We call an interpretation I that satisfies the condition formulated
in Definition 2 for PEQs a minimal model of T and A. Note that in many cases, only an
infinite minimal models exists. For example, for T = {A v ∃r.A} and A = {A(a)}
every minimal model I of T and A comprises an infinite r-chain starting at aI . Every
TBox that is equivalent to an FO Horn sentence (in the general sense of [7]) is mate-
rializable: to construct a minimal model for such a TBox T and some ABox A, one
can take the direct product of all at most countable models of T and A (for additional
information on direct products in DLs, see [17]). Conversely, however, there are simple
materializable TBoxes that are not equivalent to FO Horn sentences.
Example 1. Let T = {∃r.(A u ¬B u ¬E) v ∃r.(¬A u ¬B u ¬E)}. One can easily
show that T is not preserved under direct products; thus, it is not equivalent to a Horn
sentence. However, one can construct a minimal model I for T and any ABox A by
taking the interpretation IA obtained by viewing A as an interpretation and then adding,
for any a ∈ Ind(A) with a ∈ (∃r.(A u ¬B u ¬E))IA , a fresh da such that (a, da ) ∈ rI
and da is not in the extension of any concept name. PEQ-answering w.r.t. T is FO-
rewritable since for any PEQ q, certT (q, A) consists of precisely the answers to q in IA
(i.e., no query rewriting is necessary). Thus, PEQ-answering w.r.t. T is also in PT IME.
We show that materializability is a necessary condition for query answering being in
PT IME.
Theorem 3. If an ALCF I-TBox T (ALCF-TBox T ) is not materializable, then ELIQ-
answering (ELQ-answering) is coNP-hard w.r.t. T .
The proof uses the violation of the ABox disjunction property stated in Theorem 2 and
generalizes the reduction of 2+2-SAT used in [19] to prove that instance checking in a
variant of EL is coNP-hard.
Materializability is not a sufficient condition for query answering to be in PT IME. In
fact, we show that for any non-uniform constraint satisfaction problem, there is a mate-
rializable ALC-TBox for which Boolean CQ-answering has the same complexity, up to
complementation of the complexity class. For two finite relational FO-structures R and
R0 over relation symbols Σ, we write Hom(R0 , R) if there is a homomorphism from
R0 to R. The non-uniform constraint satisfaction problem for R, denoted by CSP(R),
is the problem to decide, for every finite R0 over Σ, whether Hom(R0 , R). Numer-
ous algorithmic problems, among them many NP-complete ones such as k-SAT and
k-colourability of graphs, can be given in the form CSP(R). It is known that every
problem of the form CSP(R) is polynomially equivalent to some CSP(R0 ) with R0 a
digraph [10]. Thus, in what follows we can restrict ourselves to considering CSPs of
the form CSP(I), where I is a DL interpretation. A signature Σ is a set of concept and
role names. The signature sig(T ) of a TBox T is the set of concept and role names that
occur in T . A Σ-TBox is a TBox that uses symbols from Σ only. Similar notation is
used for ABoxes, concepts, and interpretations. For an ABox A, we denote by AΣ the
subset of A containing symbols from Σ only. We will often not distinguish between
ABoxes and finite interpretations.
Theorem 4. For every non-uniform constraint satisfaction problem CSP(I), one can
compute in polytime a materializable ALC-TBox T such that for all ABoxes A,
1. Hom(AΣ , I), with Σ = sig(I), iff A is consistent w.r.t. T ;
2. for any Boolean CQ q, answering q w.r.t. T is polynomially reducible to the com-
plement of CSP(I).
The proof Theorem 4 relies on the existence of ALC-concepts H whose value H I in
interpretations I cannot be detected directly using CQs, but which can be used in a
TBox to influence the values AI of concept names A and, therefore, have an indirect
effect on the answers to CQs. From the viewpoint of CQ query answering, they thus
behave similarly to second-order variables. More precisely, let, for a finite set V of
indices, Zv , rv , sv be concept and role names, respectively. Let
TV = {> v ∃rv .>, > v ∃sv .Zv | v ∈ V }, Hv = ∀rv .∃sv .¬Zv .
Lemma 1. For any ABox A and sets Iv ⊆ Ind(A), v ∈ V , one can construct a minimal
model I of (TV , A) such that HvI = Iv for all v ∈ V . TV is FO-rewritable for PEQ.
To prove Theorem 4, one extends the TBox TV . Assume CSP(I) is given. Let V = ∆I
and assume, for simplicity, that sig(I) = {r}. Define
T = TV ∪ {Hv u ∃r.Hw v ⊥ | v, w ∈ V, (v, w) 6∈ rI } ∪
l
{Hv u Hw v ⊥ | v, w ∈ V, v 6= w} ∪ { ¬Hv v ⊥}
v∈V
Based on Lemma 1, it is possible to verify Points 1 and 2 of Theorem 4. For Point 2, it
can be seen that for all Boolean CQs q and ABoxes A, (T , A) |= q iff (TV , A) |= q or
not Hom(AΣ , I); since TV is FO-rewritable, the former can be checked in PT IME.
4 (Towards) Dichotomies
We start with a reduction of Boolean CQ-answering w.r.t. ALCI-TBoxes to CSPs that
yields, together with Theorem 4, a proof of Point 1 in the introduction: the dichotomy
problem for CSPs is equivalent to the dichotomy problem for CQ answering w.r.t. ALC-
(and ALCI-) TBoxes.
Theorem 5. Let T be an ALCI-TBox and C(a) an ELIQ. Then one can construct, in
time exponential in |T | + |C|,
1. a Σ-interpretation I, Σ = (sig(T ) ∪ sig(C)) ] {P }, with P a concept name, such
that for all ABoxes A,
(a) there is a polynomial reduction of answering C(a) w.r.t. T to the complement
of CSP(I);
(b) there is a polynomial reduction from the complement of CSP(I) to Boolean
CQ-answering w.r.t. T ;
2. a Σ-interpretation I, Σ = sig(T ), such that for every ABox A, A is consistent
w.r.t. T iff Hom(AΣ , I).
For Point 1, I is in fact the interpretation that is obtained by the standard type elimi-
nation procedure for ALCI-TBoxes T and concepts C. More specifically, let S be the
closure under single negation of all subconcepts of T and C. A type t is a maximal
subset of S that is satisfiable w.r.t. T . Then ∆I is the set of all types, t ∈ AI iff A ∈ t,
and (t, t0 ) ∈ rI iff ∀r.D ∈ t implies D ∈ t0 and ∀r− .D ∈ t0 implies D ∈ t. For the
special concept name P , set P I = {t | C ∈ / t}. With the type elimination algorithm, I
can be constructed in exponential time. The mentioned reductions are then as follows:
(a) (T , A) |= C(a) iff not Hom(AΣ P (a) , I), where AP (a) results from A by adding
P (a) to A and removing all other assertions using P from A;
(b) not Hom(AΣ , I) iff (T , A) |= ∃v.(P (v) ∧ C(v)).
Result 1 from the introduction can be derived as follows. Let CSP(I) be an NP-inter-
mediate CSP, i.e., a CSP that is neither in PT IME nor NP-hard. Take the TBox T
from Theorem 4. By Point 1 of that theorem and since consistency of ABoxes w.r.t. T
can trivially be reduced to the complement of answering Boolean CQs w.r.t. T , CQ-
answering w.r.t. T is not in PT IME. By Point 2, CQ-answering w.r.t. T is not coNP-
hard either. Conversely, let T be a TBox for which CQ-answering w.r.t. T is neither in
PT IME nor coNP-hard. Then by Theorem 1 and since every ELIQ is a CQ, the same
holds for ELIQ-answering w.r.t. T . Thus, there is a concrete ELIQ C(a) such that an-
swering C(a) w.r.t. T is coNP-intermediate. Let I be the interpretation constructed
in Point 1 of Theorem 5 for T and C(a). By Point 1a, CSP(I) is not in PT IME; by
Point 1b, it is not NP-hard either.
Result 5 from the introduction can be derived as follows. It is proved in [16, 5] that
the problem to decide whether the class of structures {I 0 | Hom(I 0 , I)} is FO-definable
is NP-complete. We obtain a NE XP T IME upper bound since the template I associated
with T can be constructed in exponential time. The claims for AC0 and L OG S PACE
follow in the same way from other results in [16, 5].
We now develop a condition on TBoxes, called unraveling tolerance, that is suf-
ficient for PT IME CQ-answering and strictly generalizes Horn-ALCF I, the ALCF I-
fragment of Horn-SHIQ. For the case of TBoxes of depth one, we obtain a PT IME/coNP
dichotomy result. The notion of unraveling tolerance is based on an unraveling oper-
ation on ABoxes, in the same spirit as the well-known unraveling of an interpretation
into a tree interpretation. This is inspired by (i) the observation that, in the proof of
Theorem 3, the non-tree-shape of ABoxes is essential; and (ii) by Theorem 5 together
with the known fact the non-uniform CSPs are tractable when restricted to tree-shaped
input structures. The unraveling Au of an ABox A is the following ABox:
– the individual names Ind(Au ) of Au are sequences b0 r0 b1 · · · rn−1 bn , b0 , . . . , bn ∈
Ind(A) and r0 , . . . , rn−1 (possibly inverse) roles such that for all i < n, we have
ri (bi , bi+1 ) ∈ A and bi+1 6= bi−1 (whenever i > 0);
– for each C(b) ∈ A and α = b0 r0 b1 · · · rn−1 bn ∈ Ind(Au ) with bn = b, we have
C(α) ∈ Au ;
– for each b0 r0 b1 · · · rn−1 bn ∈ Ind(Au ), we have rn−1 (bn−1 , bn ) ∈ Au .
For all β = b0 r0 · · · rn−1 bn ∈ Ind(Au ), we write tail(β) to denote bn . Note that the
condition bi+1 6= bi−1 is needed to ensure that functional roles can still be interpreted
in a functional way after unraveling, despite the UNA.
Definition 3. A TBox T is unraveling tolerant if for all ABoxes A and ELIQs q, we
have that T , A |= q implies T , Au |= q.
It is not hard to prove that the converse direction ‘T , Au |= q implies T , A |= q’
is true for all ALCF I-TBoxes. We now show that the class of unraveling tolerant
ALCF I-TBoxes generalizes Horn-ALCF I. This is based on the original and most
general definition of Horn-SHIQ in [12] and thus also captures weaker variants as
used e.g. in [13, 9]. The TBox in Example 1, which is unraveling tolerant but not a
Horn-ALCF I-TBox, demonstrates that the generalization is strict.
Lemma 2. Every Horn-ALCF I-TBox is unraveling tolerant.
It is interesting to note that unraveling tolerance implies materializability. We shall see
that the converse is, in general, not true.
Lemma 3. Every unraveling-tolerant ALCF I-TBox is materializable.
We now show that unraveling tolerance yields a class of ALCF I-TBoxes for which
query answering is in PT IME. By Lemma 2 and since we actually exhibit a uniform
algorithm for query answering w.r.t. unraveling tolerant TBoxes, this also reproves the
known PT IME upper bound for CQ-answering in Horn-ALCF I [9]. This result is not
a consquence of Theorem 4 and known results for CSPs since we capture full ALCF I.
Theorem 6. If an ALCF I-TBox T is unraveling tolerant, then PEQ-answering w.r.t.
T is in PT IME.
To see that unraveling tolerance does not capture all ALCF I-TBoxes for which query
answering is in PT IME, we can invoke Theorem 4. For example, taking a CSP for
2-colorability, we obtain a TBox T for which CQ-answering is in PT IME and such
that an ABox A with sig(A) = {r} is consistent w.r.t. T iff A is 2-colorable. Thus,
A, T |= X(a), X a fresh concept name, iff A is not 2-colorable. It follows that T is not
unraveling tolerant. We conjecture that it is possible to generalize Theorem 6 to larger
classes of TBoxes by relaxing the operation of ABox unraveling such that it yields
ABoxes of bounded treewidth instead of tree-shaped ABoxes. Such a generalization
would still not capture 2-colorability.
We now turn to TBoxes of depth one. The central observation is that for this special
case, we can prove a converse of Lemma 3.
Lemma 4. Every materializable ALCF I-TBox of depth one is unraveling tolerant.
This brings us into the position where we can establish the announced dichotomy result
for ALCF I-TBoxes of depth one. If such a TBox T is materializable, then Lemma 4
and Theorem 6 yield that PEQ-answering w.r.t. T is in PT IME. Otherwise, ELIQ-
answering w.r.t. T is coNP-complete by Theorem 3. We thus obtain the following.
Theorem 7 (Dichotomy). For every ALCF I-TBox T of depth one, one of the follow-
ing is true:
– Q-answering w.r.t. T is in PT IME for any Q ∈ {PEQ,CQ,ELIQ};
– Q-answering w.r.t. T is coNP-complete for any Q ∈ {PEQ,CQ,ELIQ}.
5 Deciding FO-Rewritability
The results of this section are based on the observation that for materializable TBoxes of
depth one, FO-rewritability for CQ follows from FO-rewritability for atomic concepts,
i.e., concept names and ⊥. We say that an atomic concept A is FO-rewritable w.r.t. a
TBox T and a signature Σ if there exists an FO-formula ϕA such that for all Σ-ABoxes
A and a ∈ Ind(A): T , A |= A(a) iff IA |= ϕA [a]. Clearly, if T is FO-rewritable
for CQ, then every atomic concept is FO-rewritable w.r.t. T and any signature. For
materializable TBoxes of depth one, the converse is also true.
Lemma 5. A materializable ALCF I-TBox of depth one is FO-rewritable for CQs iff
all atomic concepts are FO-rewritable w.r.t. T and sig(T ).
Based on Lemma 5, we can use Theorem 5 and results from [16] to obtain the following
result, in a similar (but slightly more involved) way as in the proof of Result 5 from the
introduction.
Theorem 8. FO-rewritability for CQs is decidable in NE XP T IME, for any of the fol-
lowing classes of TBoxes: materializable ALCI-TBoxes of depth one, Horn-ALC-
TBoxes, and Horn-ALCI-TBoxes of depth two.
Theorem 5 does not apply to DLs with functional roles. To analyze FO-rewritability
in the presence of functional roles, we associate with every materializable TBox T of
depth one a monadic datalog program ΠT such that T and ΠT give the same answers
to queries A(a), A atomic. We then show that T is FO-rewritable if, and only if, ΠT is
equivalent to a non-recursive datalog program. The latter property is known as bound-
edness of a datalog program and has been studied extensively for fixpoint logics [3, 18]
and datalog programs [8]. Using existing decidability results for boundedness, we can
then establish a counterpart of Theorem 8 for the case of ALCF I.
For our purposes, a monadic datalog program Π consists of rules A(x) ← X,
where A is a concept name and X is a finite set consisting of assertions of the form
B(x), r(x1 , x2 ), and inequalities x1 6= x2 , where B is a concept name, r a role, and
x, x1 , x2 range over variables. Inequalities are required to model functional roles. We
also use a special unary predicate ⊥ and rules ⊥(x) ← X stating that X is inconsistent.
For an ABox A, we denote by Π i (A) the set of all assertions S A(a) that can be derived
using i applications of rules from Π to A. We set Π ∞ (A) = i≥0 Π i (A).
Definition 4 (Boundedness). Let Π be a datalog program and Σ a signature. An
atomic concept A is bounded in Π for Σ-ABoxes if there exists a k > 0 such that
for all Σ-ABoxes A and all a ∈ sig(A): A(a) ∈ Π ∞ (A) iff A(a) ∈ Π k (A).
Let T be a materializable TBox of depth one. A Σ-neighbourhood ABox (Σ-NH) con-
sists of a Σ-ABox A with a distinguished individual name f such that A consists of
assertions of the form r(f, a) with r a role and a 6= f and A(b) such that
– for each b 6= f with b ∈ Ind(A) there is exactly one r such that r(f, b) ∈ A;
– if r(f, b1 ) and r(f, b2 ) ∈ A and b1 6= b2 , then there exists A(b1 ) ∈ A with A(b2 ) 6∈
A or vice versa.
The ABox A in which each individual b is replaced by a variable xb is denoted by Ax .
Now define a monadic datalog program associated with T , where Σ = sig(T ):
ΠT = {A(xa ) ← Ax | A is a Σ-NH, a ∈ Ind(A), A ∈ Σ, (T , A) |= A(a)} ∪
{⊥(x) ← Ax | A is a Σ-NH that is not consistent w.r.t. T } ∪
{⊥(x) ← r(y, y1 ), r(y, y2 ), y1 6= y2 | func(r) ∈ T } ∪
{A(x) ← ⊥(x) | A ∈ Σ}.
The following lemma states that ΠT behaves as intended.
Lemma 6. For every materializable ALCF I-TBox T of depth one, every A ∈ sig(T ),
every ABox A, and every a ∈ Ind(A), (T , A) |= A(a) iff A(a) ∈ ΠT∞ (A). Moreover,
⊥(a) ∈ ΠT∞ (A) iff A is not consistent w.r.t. T .
Using unfolding tolerance of materializable TBoxes of depth one, one can show the
following equivalence for FO-rewritability and boundedness.
Lemma 7. For every materializable ALCF I-TBox T of depth one and signature Σ:
an atomic concept A is bounded in ΠT for Σ-ABoxes iff A is FO-rewritable w.r.t. T
and Σ.
Unfortunately, decidability results for boundedness of monadic datalog programs are
not directly applicable to ΠT since they assume programs without inequalities [8, 11].
However, using unfolding tolerance, one can employ instead recent decidability results
on boundedness of least fixed points over trees [18] to obtain the following theorem.
Theorem 9. FO-rewritability for CQs is decidable, for any of the following classes
of TBoxes: materializable ALCF I-TBoxes of depth one, Horn-ALCF-TBoxes, and
Horn-ALCF I-TBoxes of depth two.
6 Non-Dichotomy and Undecidability in ALCF
The aim of this section is to show that the addition of functional roles significantly com-
plicates the problems studied in the previous sections. More precisely, we show that
(i) for CQ-answering w.r.t. ALCF-TBoxes, there is no dichotomy between PT IME and
coNP unless PT IME = NP; and (ii) CQ-answering in PT IME is undecidable for ALCF-
TBoxes, and likewise for coNP-hardness, materializability and FO-rewritability. Point (i)
is a consequence of the following result.
Theorem 10. For every language L in coNP, there is an ALCF-TBox T and query
rej(a), rej a concept name, such that the following holds:
1. there exists a polynomial reduction of deciding v ∈ L to answering rej(a) w.r.t. T ;
2. for every ELIQ q, answering q w.r.t. T is polynomially reducible to deciding v ∈ L.
Ladners theorem [15] states that unless PT IME = NP, coNP intermediate problems
exist. Suppose to the contrary of Point (i) that for every ALCF-TBox T , CQ answering
w.r.t. T is in PT IME or coNP-hard. Take a coNP-intermediate language L and let T
be the TBox from Theorem 10. By Point 1 of the theorem, CQ-answering w.r.t. T is
not in PT IME. Thus it must be coNP-hard. By Theorem 1 and since a dichotomy for
CQ-answering w.r.t. T also implies a dichotomy for ELIQ-answering w.r.t. T , ELIQ-
answering w.r.t. T is also coNP-hard. By Point 2 of Theorem 10, this is impossible.
The proof of Theorem 10 combines the ‘hidden’ concepts Hv from the proof of
Theorem 4 with ideas from a proof in [1] which establishes undecidability of a certain
query emptiness problem in ALCF. Using a similar strategy, we establish the undecid-
ability results announced as Point (ii) above, summarized by the following theorem.
Theorem 11. For ALCF-TBoxes T , the following problems are undecidable (Points 1
and 2 are subject to the side condition that PT IME 6= NP):
1. CQ-answering w.r.t. T is in PT IME;
2. CQ answering w.r.t. T is coNP-hard;
3. T is materializable.
In the appendix, we also prove that FO-rewritability for CQ is undecidable in ALCF,
for a slightly modified definition of FO-rewritability that only considers consistent
ABoxes.
7 Conclusions
We have have introduced non-uniform data complexity of query answering w.r.t. de-
scription logic TBoxes and proved that it enables a more fine-grained analysis than the
standard approach. Many questions remain. In particular, the newly established CSP-
connection should be exploited further. We believe that the techniques introduced in
this paper can be extended to richer DLs such as SHIQ.
Acknowledgments. C. Lutz was supported by the DFG SFB/TR 8 “Spatial Cognition”.
References
1. F. Baader, M. Bienvenu, C. Lutz, and F. Wolter. Query and predicate emptiness in description
logics. In Proc. of KR2010. AAAI Press, 2010.
2. F. Baader, S. Brandt, and C. Lutz. Pushing the EL envelope. In Proc. of IJCAI05, pages
364–369. Professional Book Center, 2005.
3. J. Barwise and Y. N. Moschovakis. Global inductive definability. J. Symb. Log., 43(3):521–
534, 1978.
4. A. A. Bulatov. A dichotomy theorem for constraints on a three-element set. In Proc. of
FOCS02, pages 649–658, 2002.
5. A. A. Bulatov, A. A. Krokhin, and B. Larose. Dualities for constraint satisfaction problems.
In Complexity of Constraints, pages 93–124, 2008.
6. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reason-
ing and efficient query answering in description logics: The DL-Lite family. J. of Autom.
Reasoning, 39(3):385–429, 2007.
7. C. C. Chang and H. J. Keisler. Model Theory, volume 73 of Studies in Logic and the Foun-
dations of Mathematics. Elsevier, 1990.
8. S. S. Cosmadakis, H. Gaifman, P. C. Kanellakis, and M. Y. Vardi. Decidable optimization
problems for database logic programs (preliminary report). In Proc. of STOC88, pages 477–
490, 1988.
9. T. Eiter, G. Gottlob, M. Ortiz, and M. Simkus. Query answering in the description logic
Horn-SHIQ. In Proc. of JELIA08, volume 5293 of LNCS, pages 166–179. Springer, 2008.
10. T. Feder and M. Y. Vardi. Monotone monadic snp and constraint satisfaction. In Proc. of
STOC93, pages 612–622, 1993.
11. H. Gaifman, H. G. Mairson, Y. Sagiv, and M. Y. Vardi. Undecidable optimization problems
for database logic programs. In Proc. of LICS87, pages 106–115, 1987.
12. U. Hustadt, B. Motik, and U. Sattler. Reasoning in description logics by a reduction to
disjunctive datalog. J. Autom. Reasoning, 39(3):351–384, 2007.
13. Y. Kazakov. Consequence-driven reasoning for horn SHIQ ontologies. In Proc. of IJCAI09,
pages 2040–2045, 2009.
14. M. Krötzsch. Efficient inferencing for OWL EL. In Proc. of JELIA10, volume 6341 of
LNCS, pages 234–246. Springer, 2010.
15. R. E. Ladner. On the structure of polynomial time reducibility. JACM, 22(1):155171, 1975.
16. B. Larose, C. Loten, and C. Tardif. A characterisation of first-order constraint satisfaction
problems. Logical Methods in Computer Science, 3(4), 2007.
17. C. Lutz, R. Piro, and F. Wolter. Description logic tboxes: Model-theoretic characterizations
and rewritability. In Proc. of IJCAI11, 2011.
18. M. Otto, A. Blumensath, and M. Weyer. Decidability results for the boundedness problem.
Technical report, TU Darmstadt, 2010.
19. A. Schaerf. On the complexity of the instance checking problem in concept languages with
existential quantification. J. of Intell. Inf. Sys., 2:265–278, 1993.