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 [
It thus seems that the data complexity of query answering in a DL context is wellunderstood. 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 PTIME if for every CQ q, there is a PTIME algorithm 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 complexity 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 PTIME? 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 , CQanswering w.r.t. T is either in PTIME 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 PTIME and coNP-complete for CQ-answering w.r.t.
ALC-TBoxes if, and only if, Feder and Vardi’s dichotomy conjecture that
“constraint satisfaction problems (CSPs) with finite template are in PTIME or
NPcomplete” [
ALCF -TBoxes, unless PTIME = NP; moreover, PTIME-complexity of CQ answering and many related problems are undecidable for ALCF . 3. there is a dichotomy between PTIME 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 HornALCF -TBoxes;
It should be noted that there has been steady progress regarding the dichotomy
conjecture 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 [
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
We use standard notation for the syntax and semantics of ALCF I and other wellknown 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) 2 A instead of r(b; a) 2 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 constructed 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
I j= 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 j= q(a), if I j= q[a] for all models I of A and T . Set certT (q; A) = fa j T ; A j= q(a)g. 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 E LI -concept and a 2 NI, then C(a) is an E LI -query (ELIQ). E L-queries (ELQs) are defined analogously. Note that E LI -queries and E L-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.
– Q-answering w.r.t. T is in PTIME if for every q(x) 2 Q, there is a polytime algorithm 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 2 Q such that, given an
ABox A, it is coNP-hard to decide whether T ; A j= q; – T is FO-rewritable for Q iff for every q(x) 2 Q one can effectively construct an FO-formula q0(x) such that for every ABox A, certT (q; A) = fa j IA j= q0(a)g, 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 PTIME bounds nor FO-rewritability depend on whether we consider PEQs, CQs, or ELIQs.
for ELIQ.
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
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 .
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 j= C1(a1) _ : : : _ Cn(an) it follows that T ; A j= Ci(ai), for some i n.
materializable iff T is CQ-materializable iff T is ELIQ-materializable iff T has the ABox disjunction property.
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 = fA v 9r:Ag and A = fA(a)g
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 [
Example 1. Let T = f9r:(A u :B u :E) v 9r:(:A u :B u :E)g. 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 2 Ind(A) with a 2 (9r:(A u :B u :E))IA , a fresh da such that (a; da) 2 rI and da is not in the extension of any concept name. PEQ-answering w.r.t. T is FOrewritable 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 PTIME. We show that materializability is a necessary condition for query answering being in PTIME.
The proof uses the violation of the ABox disjunction property stated in Theorem 2 and
generalizes the reduction of 2+2-SAT used in [
Materializability is not a sufficient condition for query answering to be in PTIME. In
fact, we show that for any non-uniform constraint satisfaction problem, there is a
materializable 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).
Numerous 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 [
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 ;
The proof Theorem 4 relies on the existence of ALC-concepts H whose value HI 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 = f> v 9rv:>; > v 9sv:Zv j v 2 V g; Hv = 8rv:9sv::Zv:
To prove Theorem 4, one extends the TBox TV . Assume CSP(I) is given. Let V = and assume, for simplicity, that sig(I) = frg. Define T = TV [ fHv u 9r:Hw v ? j v; w 2 V; (v; w) 62 rI g [ fHv u Hw v ? j v; w 2 V; v 6= wg [ f l :Hv v ?g 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) j= q iff (TV ; A) j= q or not Hom(A ; I); since TV is FO-rewritable, the former can be checked in PTIME. v2V
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 jT j + jCj, 1. a -interpretation I, = (sig(T ) [ sig(C)) ] fP g, 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
For Point 1, I is in fact the interpretation that is obtained by the standard type elimination 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 2 AI iff A 2 t, and (t; t0) 2 rI iff 8r:D 2 t implies D 2 t0 and 8r :D 2 t0 implies D 2 t. For the special concept name P , set P I = ft j C 2= tg. With the type elimination algorithm, I can be constructed in exponential time. The mentioned reductions are then as follows: (a) (T ; A) j= C(a) iff not Hom(AP (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) j= 9v:(P (v) ^ C(v)).
Result 1 from the introduction can be derived as follows. Let CSP(I) be an NP-intermediate CSP, i.e., a CSP that is neither in PTIME 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 , CQanswering w.r.t. T is not in PTIME. By Point 2, CQ-answering w.r.t. T is not coNPhard either. Conversely, let T be a TBox for which CQ-answering w.r.t. T is neither in PTIME 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 answering 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 PTIME; by Point 1b, it is not NP-hard either.
Result 5 from the introduction can be derived as follows. It is proved in [
We now develop a condition on TBoxes, called unraveling tolerance, that is sufficient for PTIME CQ-answering and strictly generalizes Horn-ALCF I, the ALCF Ifragment of Horn-SHIQ. For the case of TBoxes of depth one, we obtain a PTIME/coNP dichotomy result. The notion of unraveling tolerance is based on an unraveling operation 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 b0r0b1 rn 1bn, b0; : : : ; bn 2 Ind(A) and r0; : : : ; rn 1 (possibly inverse) roles such that for all i < n, we have ri(bi; bi+1) 2 A and bi+1 6= bi 1 (whenever i > 0); – for each C(b) 2 A and = b0r0b1 rn 1bn 2 Ind(Au) with bn = b, we have
C( ) 2 Au; – for each b0r0b1
rn 1bn 2 Ind(Au), we have rn 1(bn 1; bn) 2 Au.
For all = b0r0 rn 1bn 2 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.
It is not hard to prove that the converse direction ‘T ; Au j= q implies T ; A j= 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 [
It is interesting to note that unraveling tolerance implies materializability. We shall see that the converse is, in general, not true.
We now show that unraveling tolerance yields a class of ALCF I-TBoxes for which
query answering is in PTIME. 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 PTIME upper bound for CQ-answering in Horn-ALCF I [
T is in PTIME.
To see that unraveling tolerance does not capture all ALCF I-TBoxes for which query answering is in PTIME, we can invoke Theorem 4. For example, taking a CSP for 2-colorability, we obtain a TBox T for which CQ-answering is in PTIME and such that an ABox A with sig(A) = frg is consistent w.r.t. T iff A is 2-colorable. Thus, A; T j= 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.
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 PTIME. Otherwise, ELIQanswering w.r.t. T is coNP-complete by Theorem 3. We thus obtain the following.
ing is true: – Q-answering w.r.t. T is in PTIME for any Q 2 fPEQ;CQ;ELIQg; – Q-answering w.r.t. T is coNP-complete for any Q 2 fPEQ;CQ;ELIQg. 5
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 2 Ind(A): T ; A j= A(a) iff IA j= '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.
Based on Lemma 5, we can use Theorem 5 and results from [
Theorem 8. FO-rewritability for CQs is decidable in NEXPTIME, for any of the following classes of TBoxes: materializable ALCI-TBoxes of depth one, Horn-ALC
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
boundedness of a datalog program and has been studied extensively for fixpoint logics [
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 A(a) that can be derived using i applications of rules from to A. We set 1(A) = Si 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 2 sig(A): A(a) 2 1(A) iff A(a) 2 k(A). Let T be a materializable TBox of depth one. A -neighbourhood ABox ( -NH) consists 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 2 Ind(A) there is exactly one r such that r(f; b) 2 A; – if r(f; b1) and r(f; b2) 2 A and b1 6= b2, then there exists A(b1) 2 A with A(b2) 62
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 = fA(xa) f?(x) f?(x) fA(x)
Ax j A is a -NH, a 2 Ind(A), A 2 , (T ; A) j= A(a)g [ Ax j A is a -NH that is not consistent w.r.t. T g [ r(y; y1); r(y; y2); y1 6= y2 j func(r) 2 T g [ ?(x) j A 2
g: The following lemma states that
T behaves as intended.
every ABox A, and every a 2 Ind(A), (T ; A) j= A(a) iff A(a) 2 T1(A). Moreover, ?(a) 2 T1(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.
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 [
6
Non-Dichotomy and Undecidability in ALCF The aim of this section is to show that the addition of functional roles significantly complicates 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 PTIME and coNP unless PTIME = NP; and (ii) CQ-answering in PTIME is undecidable for ALCF TBoxes, and likewise for coNP-hardness, materializability and FO-rewritability. Point (i) is a consequence of the following result.
rej(a), rej a concept name, such that the following holds:
Ladners theorem [
The proof of Theorem 10 combines the ‘hidden’ concepts Hv from the proof of
Theorem 4 with ideas from a proof in [
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.
We have have introduced non-uniform data complexity of query answering w.r.t. description logic TBoxes and proved that it enables a more fine-grained analysis than the standard approach. Many questions remain. In particular, the newly established CSPconnection 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”.