Query Answering in Description Logics with Transitive Roles

1 Introduction

One of the main applications of ontologies in computer science is in data access, where an ontology formalizes conceptual information about data that is stored in one or multiple data sources, and this information is used to derive answers when querying the sources. This general setup plays a central role e.g. in ontology-based information integration and in peer-to-peer data management. In all these areas, Description Logics (DLs) and in particular those of the OWL standard by the W3C are popular ontology languages, and conjunctive queries (CQs) are used as a fundamental querying mechanism; cf. [Tessaris, 2001; Glimm et al., 2008b; Ortiz et al., 2008a] and references therein and below.

In spite of prominent applications, studying the computational complexity of answering CQs over OWL ontologies has only recently gained momentum. In particular, it was shown that inverse roles have an impact on complexity: (a) CQ entailment (the decisional variant of CQ answering) over ontologies in the primary OWL fragment SHIQ is 2EXPTIME-complete [Glimm et al., 2008b; Lutz, 2008], thus harder than standard reasoning tasks such as satisfiability and subsumption which are EXPTIME-complete; and (b) the complexity drops to EXPTIME-complete if inverse roles are disallowed (SHIQ is replaced with SHQ) and, additionally, the use of transitive roles in queries is disallowed or seriously restricted, cf. [Lutz, 2008; Ortiz et al., 2008b].

∗This work has been partially supported by the Austrian Science Fund (FWF) grant P20840, the Mexican National Council for Science and Technology (CONACYT) grant 187697, and the EU project OntoRule (IST-2009-231875).

While dropping inverse roles was known to be crucial for obtaining an EXPTIME upper bound, the restriction on transitive roles was not. From an application perspective, such a restriction is unsatisfactory as transitive roles play a central role in many ontologies and are used to represent fundamental relations such as "part of" [Sattler, 2000]. However, algorithms for CQ entailment with unrestricted transitive roles in the query are much more intricate than without, see e.g. [Glimm et al., 2008b; Calvanese et al., 2007].

The aim of this paper is to study the computational complexity of CQ entailment in fragments of SHIQ with no restrictions on transitive roles in queries. Our main contribution is to identify two novel sources of complexity: (1) the combination of transitive roles and role hierarchies and (2) to a lesser degree, transitive roles alone. More precisely, we first show that CQ entailment in SH (SHIQ without inverse roles and number restrictions) is 2-EXPTIME-hard, and thus 2-EXPTIME-complete. Thus, inverse roles are not the only reason why CQ entailment in SHIQ is hard. Interestingly, 2-EXPTIME-hardness is hit already with a single role inclusion (or alternatively with a single left identity r ◦ t ⊑ t) and with an empty ABox (which contains the data). Secondly, we prove that CQ entailment in S (SH without role hierarchies) is CO-NEXPTIME-hard. The lower bound applies already to the case where the TBox (conceptual information) is empty.

On the other hand, we show that CQ entailment in S ontologies where the ABoxes have a tree-shaped relational structure is in EXPTIME, and thus EXPTIME-complete. This result is interesting for three reasons. Firstly, it is the first EXPTIME result for CQ entailment in an expressive DL with unrestricted transitive roles in queries. Secondly, to the best of our knowledge, this is the first case where CQ entailment for tree-shaped ABoxes is easier than the general case: in all existing lower bounds for CQ entailment in fragments of SHIQ, the ABox contains no role assertions at all. Thirdly, EXPTIME membership may be viewed as an indication that the complexity in the general case is likely to be below 2EXPTIME; a tight upper bound is currently open. Full proofs can be found in [Eiter et al., 2009].

2 Preliminaries

Knowledge Bases. We assume standard notation for the syntax and semantics of SH knowledge bases [Glimm et al., 2008b]. In particular, NC, NR, and NI are countably infinite and disjoint sets of concept names, role names, and individual names. Concepts are inductively defined: (a) each A∈NC is a concept, and (b) if C, D are concepts and r ∈NR is a role, then C⊓D, C⊔D, ¬C, ∀r.C and ∃r.C are concepts. A TBox is a set of concept inclusions C ⊑ D, role inclusions r⊑s, and transitivity statements trans(r). An ABox is a set of assertions C(a) and r(a, b). A knowledge base (KB) is a pair (T ,A) consisting of a TBox T and an ABox A. We use I to denote an interpretation, ΔI for its domain, and CI and rI for the interpretation of a concept C and of a role r, respectively. We denote by Ind(A) the set of all individual names in an ABox A. S is the fragment of SH that disallows role inclusions.

Conjunctive Query Answering. Let NV be a countably infinite set of variables. A conjunctive query (CQ) over a KB K is a finite set of atoms of the form A(v) or r(v, v′ ), where v, v′ ∈NV, A is a concept name and r is a role, both occurring in K. 1 For a CQ q over K, let Var(q) denote the variables occurring in q. A match for q in an interpretation I is a mapping π : Var(q) → ΔI such that (i) π(v)∈AI for each A(v) ∈ q, and (ii) (π(v), π(v′ )) ∈ rI for each r(v, v′ ) ∈ q. We write I |= q if there is a match for q in I. If I |= q for every model I of K, then K entails q, written K |= q. The query entailment problem is to decide, given K and q, whether K |= q.

Forest Models. When studying CQ answering in the SHIQ family of DLs, it suffices to consider models that have a forest-like shape; informally, such a model I consists of two parts: an ABox part that consists of the interpretations aI of the individuals a in K and has an unrestricted relational structure, and a forest part that is a collection of trees whose roots are elements of the ABox part and that are otherwise disjoint from the ABox part. The following result can be found e.g., in [Glimm et al., 2008b].

Proposition 1. For every SH-knowledge base and CQ q, if K ̸|= q, then K has a forest model I such that I ̸|= q.

3 Query Answering in SH

It follows from a number of existing results that CQ entailment in SH is in 2-EXPTIME [Calvanese et al., 2007; Glimm et al., 2008a; Ortiz et al., 2008b]. We provide a matching lower bound.

Theorem 1. CQ entailment in SH is 2-EXPTIME-complete.

It is well-known that there is an exponentially space bounded Alternating Turing Machine (ATM) M whose word problem is 2-EXPTIME-hard [Chandra et al., 1981]. To prove the lower bound from Theorem 2, we reduce this word problem.

Recall that the state set Q of an ATM is partitioned into existential (Q∃) and universal (Q∀) states. An ATM with only existential states can be viewed as a standard nondeterministic TM, which accepts a word iff there exists a sequence of successive configurations that starts in the initial configuration, with initial state q0 and the input word w on the tape, and ends in an accepting state qacc. For general ATMs, these sequences become trees of configurations, where branching is caused by universal states (there is a successive configuration for each transition in δ(q, a) with q ∈ Q∀). Such a computation tree is accepting if qacc is reached on all paths. For details, see [Chandra et al., 1981].

1 Individuals in q can be simulated and queries with answer variables can be reduced to the considered Boolean CQs as usual.

For each input w to M, we define a KB Kw and a query qw such that M accepts w iff Kw ̸|= qw. In fact, forest models I of Kw with I ̸|= qw will represent an accepting computation of M on w. More precisely, I is an accepting computation tree each of whose nodes is the root of a configuration tree. The latter are binary trees of depth m := |w| (length of w) that represent configurations using their 2m leaves to store the tape contents. This is illustrated in Figure 1; the initial configuration tree is existential and thus has a single successor configuration tree. This (magnified) successor is universal and has two successor configuration trees.

To enforce this structure, we need some technical tricks. In particular, each configuration tree will represent two configurations: the current configuration Kh and the previous configuration Kp. We use Kw to ensure locally at each configuration tree that Kh is indeed a successor configuration of Kp. The query qw is then used to globally guarantee that the Kp value of each configuration tree is identical to the Kh value of the predecessor in the computation tree. We will call a computation tree proper if it satisfies the latter condition.

We now give a precise definition of how configuration trees and computation trees are represented as a model. A single, non-transitive role r is used for the edges of computation trees and of configuration trees. Observe that, as shown in Figure 1, we use two r-edges between two consecutive configuration trees. We also use a transitive role t, to be explained later. The alphabet symbols Σ of M and the states Q are used as concept names. We also use the concept names from B := {B1, . . ., Bm} to encode addresses of tape cells in binary. For a node n of a forest model I and i < 2m, we write adrI (n) = i if the truth values of BI 1 , . . . , BIm at n encode the number i. A tape cell with address i and content a ∈ Σ is represented by a node n with adrI (n) = i that satisfies the concept name a. If the head is currently on the cell andM's state is q, then n also satisfies q; otherwise, n satisfies the concept name nil.

To later on ensure properness using the query, we use additional nodes and concept names. The latter are Eh, Ep, Fh, Fp, Gh, and Gp, used as markers; and the concept names from Z := {Za,q | a ∈ Γ and q ∈ Q ∪ {nil}}. The additional nodes are attached to the leaves of configuration trees, as indicated on the left-hand side of Figure 1 and detailed in the subsequent definition. Intuitively, nodes labeled Eh store the current configuration and nodes labeled Ep the previous.

Definition 1 (i-cell). Let I be an interpretation and i < 2m. We call n ∈ ΔI an i-cell if the following hold:

• (a) n has r-successors np and nh that respectively satisfy Ep and Eh, with adrI (np)=adrI (nh)=i, and such that both satisfy exactly one a ∈ Σ and exactly one q ∈ Q ∪ {nil}.
• (b) np (resp., nh) has an r-successor n′p (resp., n′h ) that satisfies Fp (resp., Fh), with adrI (n′p) = adrI (n′h ) the bit-wise complement of i, and such that for all a∈Σ, q ∈Q∪{nil}:
• (i) nh satisfies Za,q iff nh does not satisfy both a and q;
• (ii) n′p satisfies Za,q iff np does not satisfy both a and q;
• (iii) n′h and np satisfy Za,q;
• (c) n′p (resp., n′h ) has a t-successor n′′ p satisfying Gp (resp., n′′h satisfying Gh) such that n′′ p (resp., n′′h ) is also a tsuccessor of np (resp., nh).

We simply speak of a cell if i is unimportant. Note that the ability of SH to express (c) in Definition 1 via the axioms r⊑t and trans(t) is crucial for the reduction. The same condition can be expressed via a so-called left identity r ◦ t ⊑ t.

We now define (q, a, i)-configuration nodes, which are the roots of configuration trees, and (models that encode) computation trees. A node n′ is an rm-successor of a node n, if n′ is reachable from n by traveling m r-edges.

Definition 2 ((q, a, i)-configuration node, Computation tree). Let I be an interpretation. We call n ∈ ΔI a (q, a, i)-configuration node if (1) it has an sm-successor that is a j-cell, for each j < 2m and (2) the Eh-node of the icell satisfies q and a, and all other j-cells have nil in their Eh-nodes.

We call I a computation tree for w if I is tree-shaped and

1. the root ϵ of I has an r-successor n that is a (q0, a, 0)- configuration node whose i-cells describe the initial configuration for input w;
2. for each (q, a, p)-configuration node n, if q ∈Q∃ (resp., q ∈Q∀), then for some (resp., for each) tuple (q′ , a′ ,M) ∈ δ(q, a) we have:
3. (i) there exists an r2 -successor node n′ that is an (q′ , a′′ , p′ )-configuration node with p′ = p +M, where M ∈ {-1, +1} is the executed move,
4. (ii) the Eh node of the p-cell of n′ satisfies a′ , and,
5. (iii) for all j-cells c of n′ where j ̸= p, if the Ep node of c satisfies a∈Σ, then the Eh node of c also satisfies a.

We call I accepting, if q = qacc in each (q, a, i)-configuration for which there are no successor configurations. I is proper, if for each pair of successive configuration nodes n1, n2 and each i < 2m, the i-cell of n1 has the same (q, a)-label in its Eh-node as the i-cell of n2 in its Ep-node.

It is not hard to verify that there is a one-to-one correspondence between accepting proper computation trees for w and accepting computations of M on w.

Proposition 2. M accepts w iff there exists an accepting proper computation tree for w.

It is not too difficult to show the following.

Proposition 3. Given w, we can build in polynomial time a KB Kw whose forest models are exactly the accepting computation trees for w.

As already mentioned, we use the query qw to test whether the tree is proper. More precisely, qw should have a match in a computation tree iff that tree is not proper. We start with a characterization of (im)properness in terms of the auxiliary concept names from above. In the following, we say that two cells n and n′ are A-conspicuous, with A a concept name, if

• (†) A is true at the Eh-node of n and the Ep-node of n′ , or
• (‡) A is true at the Fh-node of n and the Fp-node of n′ .

Proposition 4. A computation tree I is not proper iff (⋆) there exists a cell n in some configuration K and a cell n′ in a successor configuration of K such that for all A ∈ B ∪ Z, n and n′ are A-conspicuous.

The above proposition holds due to the way auxiliary labels are defined. First note that if n, n′ are cells of two successive configurations in I, then the conditions imposed on adrI (·) in Definition 1 imply that adrI (n) = adrI (n′ ) iff for all A ∈ B, n and n′ are A-conspicuous; this is because bit-wise complement is used for the addresses of Fp- and Fh-nodes.

Now suppose that I is proper and let n, n′ be cells of two successive configurations. If they are not A-conspicuous for some A∈B then, as required, (⋆) is violated. If there is no such A ∈ B, then adrI (n) = adrI (n′ ). As I is proper, the Eh-node of n and the Ep-node of n′ satisfy the same q ∈ Q and a ∈ Σ. By (b.i), Za,q is false at the Eh-node of n; by (b.ii), Za,q is false at the Fp-node of n′ . Hence, n, n′ are not Za,q-conspicuous and (⋆) is violated. Conversely, let I be improper. Then there exist two j-cells n and n′ of two successive configurations such that the Eh-node of n and the Ep-node of n′ satisfy different pairs (q, a) and (q′ , a′ ). As adrI (n) = adrI (n′ ), n and n′ are A-conspicuous for all A ∈ B. By (b.iii), Zq,a is true at the Fh-node of n; by (b.ii) and since (q, a) ̸= (q′ , a′ ), Zq,a is also true at the Fp-node of n′ . We can argue symmetrically that za′ ,q′ is true at the Eh-node of n and the Ep-node of n′ . For (q′′ , a′′ ) /∈ {(q, a), (q′ , a′ )}, Za′′ ,q′′ holds at the Eh-, Ep-, Fh-, and Fp-nodes of both n and n′ . In summary, n and n′ are A-conspicuous for all A ∈ Z and thus (⋆) is satisfied.

It thus remains to find a query qw that has a match iff (⋆) is satisfied. The structure of qw is displayed in Figure 2(II).

We obtain qw by taking, for each A ∈ B∪Z, a copy of the basic query q(A, u, v) in Figure 2(I) such that the different copies share only the variables u and v, and then taking the union. Intuitively, q(A, u, v) deals with A-conspicuousness, and the shared variables u, v ensure that the different component queries speak about the same cells n, n′ . In more detail, let n, n′ be cells of two successive configurations that are Aconspicuous for all A ∈ B ∪ Z. We can find a match for qw as follows: start with matching u on the Gh-node of n and v on the Gp-node of n′ . Now take an A ∈ B∪Z. If (†) applies, then match yAm+1 on the Eh-node of n and zAm+1 on the Epnode of n′ ; if (‡) applies, then match yAm+1 on the Fh-node of n and zAm+1 on the Fp-node of n′ . The matches of all other variables are now uniquely determined by the (non-transitive) role edges in the query. In particular, the lengths of the role chains in the query ensure that xA will be matched to the root of n in case (‡) and to the root's predecessor in case (†). Observe that the paths labeled with z-variables are exactly two steps longer than those labeled with y-variables, and thus the query only relates n and n′ if they belong to successor configurations. In summary, it is possible to show that Proposition 5. A computation tree I is proper iff I ̸|= qw.

Together with Propositions 2 and 3, this yields the desired reduction, establishing the lower bound from Theorem 2.

4 Query Answering in S

The reduction in the previous section crucially exploits the presence of role inclusions and transitive roles. In particular, the structure shown on the left-hand side of Figure 1 cannot be enforced if either of these expressive means is dropped. Role hierarchies alone do not suffice to make CQ entailment harder than satisfiability checking and other EXPTIME-complete standard reasoning tasks: it is known that CQ entailment in ALCH, which is SHwithout transitive roles, is only EXPTIME-complete [Lutz, 2008; Ortiz et al., 2008b]. In contrast and as we show next, transitive roles alone suffice to make CQ answering harder than standard reasoning.

Theorem2. CQentailment inS is CO-NEXPTIME-hardeven without TBoxes and with acyclic ABoxes.

This result is shown by a reduction to CQ non-entailment from a NEXPTIME-complete variant of the tiling problem where the task is to tile a 2n ×2n-torus. The reduction uses only a single transitive role and no other role, no TBox, and an ABox whose relational structure is a directed acyclic graph, but not a tree. Because of space limitation, we refer to [Eiter et al., 2009] for a detailed construction and give only a rough idea why transitive roles make CQ entailment hard. Viewed on a high level of abstraction, most algorithms for CQ entailment exploit forest models and work by splitting the problem into a number of subproblems: one for each individual a in the input ABox A. This splitting also involves splitting the input query q into subqueries: a match of q in a forest model I may send some variables to the subtree below a and some variables to other parts of I, and we obtain a subquery by including only variables of the former kind. Now, the crucial observation is as follows: without transitive roles, only polynomially many subqueries are generated for each a whereas exponentially many subqueries have to be considered when transitive roles are admitted.

As we show next, the described effect vanishes in the case of tree-shaped ABoxes. This case is relevant, e.g., when the ABox is obtained by translating an XML document. An ABox A is tree-shaped if the directed graph with nodes Ind(A) and edges {(a, b) | r(a, b)∈A} is a tree and r(a, b), r′ (a, b) ∈ A imply r = r′ . We aim to show

Theorem 3. CQ entailment in S is EXPTIME-complete if ABoxes are tree-shaped.

It is well-known that CQ entailment in S is EXPTIME-hard even with empty ABoxes and thus it remains to show the upper bound. We start with a simple observation.

Proposition 6. For a KB K=(T ,A), where A is treeshaped, we can build in polynomial time a KB K′ = (T , {CA(a)}) such that K |=q iff K′ |=q for every CQ q.

It thus suffices to give an EXPTIME algorithm for CQ entailment in S with ABoxes of the form {C0(a)}. From now on, let K = (T , {C0(a)}) be a KB and q a CQ for which we decide K |= q.

We set Tr(K) := {r ∈ NR | trans(r) ∈ T }. We assume w.l.o.g. that C0 is in negation normal form (NNF), i.e. negation is only applied to concept names, and that T has the form {⊤ ⊑ CT } with CT in NNF. We may also assume w.l.o.g. that CQs are connected (a disconnected query can be answered by separately posing each connected subquery).

We can limit our attention to certain canonical models and a certain kind of query that we call a pseudo-tree query.

Definition 3 (Canonical Model). We use sub(K) to denote the set of all subconcepts of concepts occurring in K. A canonical model for K is a model I of A such that (i) I satisfies all concept inclusions in T (but not necessarily the transitivity axioms); (ii) (ΔI , ⋃r∈NR rI ) is a tree with root aI and whose out-degree is bounded by the cardinality of sub(K); (iii) rI ∩ sI = ∅ whenever r ̸= s; (iv) for all ∀t.C ∈ sub(K) with t ∈ Tr(K) and all (d, e) ∈ tI , d ∈ (∀t.C)I implies e ∈ (∀t.C)I .

Due to the non-transitivity of transitive roles in canonical models I, we have to work with a relaxed version of a match that becomes a match when, for every r ∈ Tr(K), rI is replaced with its transitive closure.

Definition 4 (Pre-match). Let I be a canonical model of K. We call π : Vars(q)→ΔI a pre-match for q in I if (a)

π(u)∈AI for each A(u)∈q, (b) (π(u), π(v))∈rI for each r(u, v)∈q with r ̸∈Tr(K), and (c) for each t(u, v)∈q with t∈Tr(K), there is a sequence d0, . . . , dn ∈ΔI such that d0 =π(u), dn =π(v) and (di , di+1)∈tI for all i < n. We write I |=pre q, if there is a pre-match for q in I.

We now define pseudo-tree queries.

Definition 5 (Role Cluster, Pseudo-tree Query). Let q be a CQ. For each t ∈ Tr(K), ∼t denotes the smallest equivalence relation over Var(q) such that t(v, v′ ) ∈ q implies v ∼t v′ . An equivalence class ct of ∼t is called a (transitive) cluster of q. For each non-transitive role s, a (non-transitive) cluster of q is a set cs ={u, v} with s(u, v) ∈ q. Now, a connected CQ q is a pseudo-tree query if it satisfies:

• (a) if cr is a cluster of q and s(u, v), s′ (u′ , v′ )∈q with v, v′ ∈cr and s, s′ ̸= r, then s=s′ , u=u′ , v=v′ ;
• (b) q is acyclic, i.e., it does not contain atoms r0(v0, v1), . . . , rn(vn , vn+1) with vn+1 = v0.

A cluster cr of q is initial if no v∈cr has an incoming edge r′ (v′ , v) ∈ q with r ̸= r′ .

Intuitively, a pseudo-tree can be viewed as a tree of clusters with an additional root; the root is a predecessor of every initial cluster (there can be more than one) and there is an edge between two clusters if they share an element. It is easy to see that clusters cannot share more than one element. Each transitive cluster in a pseudo-tree query describes a subquery that is an acyclic directed graph.

Definition 6. Let q, q′ be conjunctive queries. Then q′ is obtained from q by fork elimination, if q′ results from q by one of the following operations:

• select r(u, v), r(u′ , v) ∈ q with u̸=u′ and r ̸∈Tr(K), and identify u and u′ ;
• select r(u, v), r(u′ , v′ ) ∈ q with v ̸=v′ and v, v′ in a cluster cs of q with s ̸= r, and identify v and v′ .

We say that q′ is a maximal fork rewriting of q if q′ is obtained from q by exhaustive fork elimination.

It can be shown that the maximal fork rewriting is unique and computable in polynomial time. Moreover, it can be checked in polynomial time whether a query is a pseudo-tree query. Hence, the following proposition allows us to restrict our attention to canonical models and pseudo-tree queries.

Proposition 7. Let q be a CQ, and let q′ be the maximal fork rewriting of q. Then K ̸|= q iff (i) q′ is not a pseudo-tree query, or (ii) I ̸|=pre q′ for some canonical model I of K.

In what follows, assume that the input query q is a pseudotree query. We want to decide whether there is a canonical model I of K such that I ̸|=pre q. Our approach is based on knots [Ortiz et al., 2008c].

Definition 7 (Knot). A T -type is a set τ ⊆sub(T ) that satisfies, for all C,D∈sub(T ): (a) C∈τ implies ¬C ̸∈τ, (b) if C⊓D∈τ, then {C,D}⊆τ, (c) if C⊔D∈τ, then C∈τ or D∈τ, and (d) CT ∈τ. A knot for T is a pair κ=(τ, S) with τ a T -type and S a set of pairs (r, τ ′ ) such that r is a role name that occurs in T , τ ′ is a T -type, and in addition:

1. if ∃r.C∈τ, then C∈τ ′ for some (r, τ ′ )∈S;
2. if ∀r.C∈τ, then C∈τ ′ for all (r, τ ′ )∈S;
3. if ∀r.C∈τ ∧ r∈Tr(K), then ∀r.C∈τ ′ for all (r, τ ′ )∈S;
4. |S| ≤ |sub(K)|.

A knot κ=(τ, S) can be viewed as describing a fragment of a canonical model that consists of a node which satisfies the concepts in τ and its successors, as described by S. Our algorithmwill represent canonical models as a set of knots. In fact, it is not hard to come up with conditions which guarantee that a given set of knots can be assembled into a canonical model. The difficulty is to ensure that, in the represented canonical model, there is no pre-match of q.

The general idea to overcome this difficulty is as follows. Consider a top-down walk though a (tree-shaped!) canonical model I. To avoid a pre-match of the pseudo-tree query q, we 'track' q through the tree, switching to a subquery of q whenever we are able to match at least one variable. For example, if q = {A(v0),B(v′0), r(v0, v1), r(v′0, v1)} with r transitive and we are currently considering an element d ∈ ΔI such that d ∈ AI \ BI , then we switch from q to q′ := {B(v′0 ), r(v′0 , v1)} because v0 (but not v′0 ) can be matched to d; we then track q′ starting from all r-successors of d in I; if e is such a successor with e /∈ BI , condition (c) of prematches forces us to continue to track q′ (without any modifications since v′0 cannot be matched at e) at the r-successors of e; and so on. When we are left with a query that consists of only one variable, we ensure that this variable matches nowhere. In summary, we thus use an eager matching approach (matching variables as early as possible) to ensure that q matches nowhere in I. This general idea is complicated by the mixture of transitive and non-transitive roles in the query, and by the fact that we have to implement it in terms of knots rather than directly in terms of models.

To track subqueries of q, we need a means to identify such subqueries.

Definition 8 (Query Pointer). A query pointer for q is a pair (cr , V ) with cr a cluster of q and V ⊆ cr nonempty. If cr is a cluster of q, v ∈ cr, and there is an s(v, v′ )∈q with s ̸=r, then the query pointer (cs , cs) is possible from v, where cs is the (unique!) s-cluster in q with v, v′ ∈ cs.

Intuitively, a query pointer P = (cr , V ) represents the subquery of q generated by the variables that are reachable from the variables in V . By definition of clusters, there are two types of query pointers (cr , V ): (i) r non-transitive and |V | ∈ {1, 2}; and (ii) r transitive and V of any cardinality ≥ 1.

Clearly, a pre-match of a query can concern more than a single knot. To implement the tracking of queries based on knots, we thus extend knots with bookkeeping information.

Definition 9 (Marked Knot). A q-marking for q is a set Γ of query pointers such that for all clusters cr of q, there is at most one pointer (cr , V ) ∈ Γ. A marked knot is a pair (κ, ν), where κ=(τ, S) is a knot and ν assigns a q-marking to each element in S ∪ {ε}.

As a convention, ν(ε) is the marking of the root of κ. Intuitively, (cr , V ) ∈ ν(ε) means that we are currently tracking the subquery of q identified by (cr , V ) at the element of the model that is identified by the root node of the knot, and similarly for (cr , V ) ∈ ν(s, τ).

procedure Knot-Elim(K, q) with K = (T , {C0(a)}) Compute the set K0 of marked q-avoiding knots i := 0 repeat i := i +1 Ki := Ki-1 \ {(κ, ν) ∈ Ki-1 | (κ, ν) bad in Ki-1} until Ki = Ki-1 if there is a (κ, ν) ∈ Ki with κ = (τ, S) s.t. C0 ∈ τ then return "K does not entails q" else return "K entails q"

To ensure that the query is properly tracked, we propagate markings from the root of a knot to its successors. For V ⊆ Vars(q), we use min(V )⊆Vars(q) to denote the set of those v ∈V for which there exists no r(v′ , v) ∈ q with v′ ∈V .

Definition 10 (q-avoiding). A marked knot (κ, ν) with κ = (τ, S) is q-avoiding if (I) ν(ε) contains a query pointer (cr , V ) with cr initial; and (II) the following conditions hold for each (cr , V ) ∈ ν(ε):

1. If r ̸∈ Tr(K), V = {v, v′}, and r(v, v′ ) ∈ q, then either (a) for some A, we have A(v) ∈ q and A ̸∈ τ, or (b) (cr , {v′}) ∈ ν(r, τ ′ ) for all (r, τ ′ ) ∈ S; 2. If r ̸∈ Tr(K) and V ={v}, then either (a) for some A, we have A(v) ∈ q and A ̸∈ τ, or (b) P ′ ∈ ν(ε) for a query pointer P ′ possible from v;
2. If r∈Tr(K), then there is some set M ⊆ min(V ) s.t.:
3. (a) for each v∈min(V ) \ M, either (i) for some A, we have A(v) ∈ q and A ̸∈ τ, or (ii) P ′ ∈ ν(ε) for some query pointer P ′ possible from v, and
4. (b) there is a non-empty V ′ ⊆ V \ M with (cr , V ′ ) ∈ ν(r, τ ′ ) for all (r, τ ′ ) ∈ S.

Intuitively, Definition 10 implements the tracking of q described above. Conditions (1.b), (2.b), and (3.b) push the query to successor nodes. In Condition (3), M is the set of variables to be matched at the 'current' node, and (3.a) implements eager matching. The final avoidance of the query is implemented via Conditions (2) and (3) when |V | = 1. Condition (I) is needed to re-initiate the tracking process, e.g., when we have traveled a role that does not occur in the query.

Our algorithm is of the type elimination kind introduced in [Pratt, 1979], but works on marked knots instead of on types. It rests on the following definition.

Definition 11 (Bad). Let K be a set of marked knots and (κ, ν) ∈ K with κ = (τ, S). We say that (κ, ν) is bad in K, if there is some (r, τ ′ )∈S for which there is no (κs , νs) ∈ K with κs = (τs , Ss) such that τs =τ ′ and νs(ε)=ν(r, τ ′ ).

The algorithm is given in Figure 3. Soundness and completeness are established in [Eiter et al., 2009].

Proposition 8. The Knot-Elim algorithm is sound, complete, and terminates.

To establish Theorem 3, it remains to show that Knot-Elim runs in exponential time. For this, it clearly suffices to show that the number of marked knots is only exponential in the size of K and q. Let n be the size of K and m the size of q.

The number of T -types is bounded by 2n and the number of knots by 2O(n2) (note cond. 4 in Def.7); the number of query pointers is bounded by 2O(m) and the number of q-markings by 2O(m2) . It follows that there are 2O(n2m2 ) marked knots.

5 RelatedWork and Conclusions

We have shown that CQ entailment in the DL SH, which supports transitive roles and role hierarchies, is 2-EXPTIMEhard, and thus provably harder than standard reasoning tasks such as satisfiability and instance checking, which are EXPTIME-complete. We have also shown that the problem is in EXPTIME for S when ABoxes are tree-shaped, but CONEXPTIME-hard in general. A tight bound remains open, but we consider it likely that CQ entailment in S is simpler than 2-EXPTIME, with CO-NEXPTIME being a good candidate.

The 2-EXPTIME hardness for SH and for ALCI [Lutz, 2008] matches known upper bounds for unions of CQs in SHIQ [Glimm et al., 2008b] and for the even more expressive two-way positive regular path queries in ALCQIbreg [Calvanese et al., 2007]. This shows that once either inverse roles or role hierarchies and transitivity are allowed, both the query language and the DL can be significantly extended without further increase of the worst case complexity.