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 expressive 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 PTIME 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 CQanswering is still in PTIME [12]. While CQ-answering in Horn-SHIQ and the EL family of DLs is also hard for PTIME, 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 such that the answers to q w.r.t. T coincide with the answers that a standard database system produces for q [6]. Achieving this goal requires CQ-answering to be in AC 0 .

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" [10] is true; the same holds for ALCI-TBoxes; 2. there is no dichotomy between PTIME and coNP-complete for CQ-answering w.r.t.

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 Horn-ALCF-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 [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 answering 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 NEXPTIME whether there is an FOsentence ϕ 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 consistency w.r.t. T can be decided in non-uniform AC 0 . Finally, if no such sentence ϕ T exists, then ABox consistency w.r.t. T is LOGSPACE-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 minimal models as known from Horn-DLs. We show that, in the case of TBoxes of depth one, materializability characterizes PTIME 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 PTIME. The resulting upper bound strictly generalizes the known result that CQ-answering in Horn-ALCF I is in PTIME. Our framework also allows to formally establish some common intuitions and beliefs held in the context of CQanswering in description logics. For example, we show that for any ALCF I-TBox T , CQ-answering is in PTIME iff answering positive existential queries is in PTIME iff answering ELI-instance queries is in PTIME and likewise for FO-rewritability. Another 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.

Preliminaries

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 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 constructed from atoms A(t), r(t, t ), and t = t (where t, t 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 cert T (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 ∈ N I , 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 PTIME if for every q(x) ∈ Q, there is a polytime algo- rithm that computes, given an ABox A, the answer cert T (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 (x) such that for every ABox A, cert T (q, A) = {a | I A |= q (a)}, where I A 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.

Theorem 1. For all ALCF I-TBoxes T , the following equivalences hold:

1. CQ-answering w.r.t. T is in PTIME iff PEQ-answering w.r.t. T is in PTIME iff ELIQ-answering w.r.t. T is in PTIME; 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 Qmaterializable 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 C 1 (a 1 ), . . . , C n (a n ), from

T , A |= C 1 (a 1 ) ∨ . . . ∨ C n (a n ) it follows that T , A |= C i (a i ), for some i ≤ n.

Theorem 2. Let T be an ALCF I-TBox. The following equivalences hold: T is PEQmaterializable 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 ∃r.A} and A = {A(a)} every minimal model I of T and A comprises an infinite r-chain starting at a I . Every TBox that is equivalent to an FO Horn sentence (in the general sense of [7]) is materializable: 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 ¬B ¬E) ∃r.(¬A ¬B ¬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 I A obtained by viewing A as an interpretation and then adding, for any a ∈ Ind(A) with a ∈ (∃r.(A ¬B ¬E)) I A , a fresh d a such that (a, d a ) ∈ r I and d a is not in the extension of any concept name. PEQ-answering w.r.t. T is FOrewritable since for any PEQ q, cert T (q, A) consists of precisely the answers to q in I A (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.

Theorem 3. If an ALCF I-TBox T (ALCF-TBox T ) is not materializable, then ELIQanswering (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 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 R over relation symbols Σ, we write Hom(R , R) if there is a homomorphism from R to R. The non-uniform constraint satisfaction problem for R, denoted by CSP(R), is the problem to decide, for every finite R over Σ, whether Hom(R , 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(R ) with R 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 complement 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 A I 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, Z v , r v , s v be concept and role names, respectively. Let

T V = { ∃r v . , ∃s v .Z v | v ∈ V }, H v = ∀r v .∃s v .¬Z v .

Lemma 1. For any ABox A and sets

I v ⊆ Ind(A), v ∈ V , one can construct a minimal model I of (T V , A) such that H I v = I v for all v ∈ V . T V is FO-rewritable for PEQ.

To prove Theorem 4, one extends the TBox T V . Assume CSP(I) is given. Let V = ∆ I and assume, for simplicity, that sig(I) = {r}. Define

T = T V ∪ {H v ∃r.H w ⊥ | v, w ∈ V, (v, w) ∈ r I } ∪ {H v H w ⊥ | v, w ∈ V, v = w} ∪ { v∈V ¬H 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 (T V , A) |= q or not Hom(A Σ , I); since T V is FO-rewritable, the former can be checked in PTIME.

(Towards) Dichotomies

We start with a reduction of Boolean CQ-answering w.r. 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 [16,5] that the problem to decide whether the class of structures {I | Hom(I , I)} is FO-definable is NP-complete. We obtain a NEXPTIME upper bound since the template I associated with T can be constructed in exponential time. The claims for AC 0 and LOGSPACE follow in the same way from other results in [16,5].

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 A u of an ABox A is the following ABox:

-the individual names Ind(A u ) of A u are sequences b 0 r 0 b 1 • • • r n−1 b n , b 0 , . . . , b n ∈

Ind(A) and r 0 , . . . , r n−1 (possibly inverse) roles such that for all i < n, we have

r i (b i , b i+1 ) ∈ A and b i+1 = b i−1 (whenever i > 0); -for each C(b) ∈ A and α = b 0 r 0 b 1 • • • r n−1 b n ∈ Ind(A u ) with b n = b, we have C(α) ∈ A u ; -for each b 0 r 0 b 1 • • • r n−1 b n ∈ Ind(A u ), we have r n−1 (b n−1 , b n ) ∈ A u . For all β = b 0 r 0 • • • r n−1 b n ∈ Ind(A u )

, we write tail(β) to denote b n . Note that the condition b i+1 = b i−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 , A u |= q.

It is not hard to prove that the converse direction 'T , A u |= 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 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 [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 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) = {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. 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.

Theorem 7 (Dichotomy). For every ALCF I-TBox T of depth one, one of the following is true:

-Q-answering w.r.t. T is in PTIME for any Q ∈ {PEQ,CQ,ELIQ}; -Q-answering w.r.t. T is coNP-complete for any Q ∈ {PEQ,CQ,ELIQ}.

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 I A |= ϕ 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 NEXPTIME, for any of the following 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 boundedness 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(x 1 , x 2 ), and inequalities x 1 = x 2 , where B is a concept name, r a role, and x, x 1 , x 2 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 Π ∞ (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).Π T = {A(x a ) ← A x | A is a Σ-NH, a ∈ Ind(A), A ∈ Σ, (T , A) |= A(a)} ∪ {⊥(x) ← A x | A is a Σ-NH that is not consistent w.r.t. T } ∪ {⊥(x) ← r(y, y 1 ), r(y, y 2 ), y 1 = y 2 | 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.

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.

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 PTIME = 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 PTIME 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 PTIME. 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 , ELIQanswering 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 H v 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 undecidability 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 PTIME = NP):

1. CQ-answering w.r.t. T is in PTIME; 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.