On the Parameterised Complexity of Tree-Shaped Ontology-Mediated Queries in OWL 2 QL M. Bienvenu1, S. Kikot2, R. Kontchakov2, V. Ryzhikov3 , and M. Zakharyaschev2 1 CNRS & University of Montpellier, France (meghyn@lirmm.fr) 2 Birkbeck, University of London, UK ({kikot,roman,michael}@dcs.bbk.ac.uk) 3 Free University of Bozen-Bolzano, Italy (ryzhikov@inf.unibz.it) Abstract. We discuss the parameterised complexity of answering tree-shaped ontology-mediated queries (OMQs) in OWL 2 QL under various restrictions on their ontologies and conjunctive queries (CQs). In particular, we construct an ontology T such that answering OMQs (T , q) with tree-shaped CQs q is W[1]- hard if the number of leaves in q is regarded as the parameter. The number of leaves has previously been identified as an important characteristic of CQs as bounding it leads to tractable OMQ answering. Our result shows that treating it as a parameter does not make the problem fixed-parameter tractable, even for a fixed ontology. 1 Introduction Our concern here is the computational complexity of answering ontology-mediated queries (OMQs, for short) (T , q), where T is an OWL 2 QL ontology (aka DL-LiteR [7] or DL-LiteH core TBox [2]) and q a tree-shaped Boolean conjunctive query (CQ). The classical OMQ answering problem T REE OMQ Instance: T , q and an ABox A, Problem: decide whether T , A |= q is known to be NP-complete [15]. On the other hand, the restriction of T REE OMQ to tree-shaped CQs with at most ` leaves, for some fixed number ` ≥ 2—we de- note this problem by T REE OMQ[leaves ≤ `]—is L OG CFL-complete [5]. If we fur- ther bound the existential depth of T by some fixed d ≥ 0, then the resulting problem T REE OMQ[leaves ≤ `, depth ≤ d] turns out to be NL-complete [5]. Results of this kind prompt a few additional interesting questions. For example, what is the parameterised complexity of the following problem depth-T REE OMQ? Instance: T of finite depth, q and A, Parameter: the depth of T , Problem: decide whether T , A |= q. What is the parameterised complexity of a similar problem leaves-T REE OMQ, which takes the number of leaves in q as the parameter? Or what if we fix an ontology T in T REE OMQ and consider the problem T REE OMQ[T ]? Note that this problem re- flects a typical ontology-based data access scenario, where the users are provided with a fixed ontology designed by a domain expert. Furthermore, we can consider the leaf- parameterisation leaves-T REE OMQ[T ] of T REE OMQ[T ]. In this paper, we summarise and discuss our recent results answering some of the questions above and presented in [4]. We also prove a new theorem by constructing an ontology T2 (of infinite depth) for which the problem leaves-T REE OMQ[T2 ] is W [1]- hard. 2 Preliminaries To make the ontology axioms in Section 3 more compact and readable, we use the syntax of first-order rather than description logic. Thus, an OWL 2 QL ontology, T , is a finite set of sentences of the form ∀x (τ (x) → τ 0 (x)), ∀x (τ (x) ∧ τ 0 (x) → ⊥), 0 ∀xy (%(x, y) → % (x, y)), ∀xy (%(x, y) ∧ %0 (x, y) → ⊥), ∀x %(x, x), ∀x (%(x, x) → ⊥), where τ (x) and %(x, y) are defined, using unary predicates A and binary predicates P , by the grammars τ (x) ::= > | A(x) | ∃y %(x, y), %(x, y) ::= > | P (x, y) | P (y, x). When writing ontology axioms, we omit the universal quantifiers. Denote by RT the set of binary predicates P occurring in T and their inverses P − , assuming that P −− = P . An ABox, A, is a finite set of unary or binary ground atoms. We denote by ind(A) the set of individual constants in A. A conjunctive query (CQ) q(x) is a formula of the form ∃y ϕ(x, y), where ϕ is a conjunction of (unary A(u) or binary P (u, v)) atoms S(z) all of whose variables are among x ∪ y. We assume, without loss of generality, that CQs contain no constants. We often regard a CQ as the set of its atoms.With every CQ q, we associate its Gaifman graph G whose vertices are the variables of q and whose edges are the pairs {u, v} such that P (u, v) ∈ q, for some P (note that the atoms P (u, u) do not add any edges to G). We call q connected if G is connected; q is tree-shaped if G is a tree, and linear if G is a tree with two leaves. An ontology-mediated query (OMQ) is a pair Q(x) = (T , q(x)), where T is an ontology and q(x) a CQ. A tuple a in ind(A) is a certain answer to (T , q) over an ABox A if I |= q(a) for all models I of T and A; in this case we write T , A |= q(a). For a Boolean q, in which case x = ∅, a certain answer to Q over A is ‘yes’ if T , A |= q and ‘no’ otherwise. Every consistent knowledge base (KB) (T , A) has a canonical model (or chase in database theory) [1] CT ,A with the property that T , A |= q(a) iff CT ,A |= q(a), for all CQs q(x) and a in ind(A). In our constructions, we use the following definition of CT ,A , where without loss of generality we assume that T contains no binary pred- icates P such that T |= ∀xy P (x, y). The domain, ∆CT ,A , consists of ind(A) and the witnesses (or labelled nulls) of the form w = a%1 . . . %n , for n ≥ 1, such that – a ∈ ind(A) and T , A |= ∃y %1 (a, y); – T 6|= %i (x, x), for 1 ≤ i ≤ n; – T |= ∃x%i (x, y) → ∃z%i+1 (y, z) but T 6|= %i (x, y) → %i+1 (y, x), for 1 ≤ i < n. We denote by WT the set consisting of the empty word ε and all non-empty words % 1 . . . %n ∈ R + T satisfying the last two conditions. Every a ∈ ind(A) is interpreted in CT ,A by itself, and unary and binary predicates are interpreted as follows: – CT ,A |= A(u) iff either u ∈ ind(A) and T , A |= A(u), or u = w% and we have T |= ∃y %(y, x) → A(x); – CT ,A |= P (u, v) iff one of the following three conditions holds: (i) u, v ∈ ind(A) and T , A |= P (u, v); (ii) u = v and T |= P (x, x); (iii) T |= %(x, y) → P (x, y) and either v = u% or u = v%− . We say that T is of depth 0 ≤ d < ∞ if d is the maximum length of the words in WT , and of depth ∞ if WT is infinite. (Note that the depth of T is computable in NL; cf. [12, 6] for related results on chase termination for tgds.) We consider various parameterisations and restrictions of the decision problem T REE OMQ defined above. As parameters, we can take the following1 : query: a tree-shaped CQ q, leaves: the number of leaves in the Gaifman graph of a tree-shaped CQs q, ontology: an OWL 2 QL ontology T , depth: the depth of T . Restrictions can take the forms leaves ≤ `: we consider only CQs with ≤ ` leaves, for some ` ≥ 2, depth ≤ d: we consider only ontologies of depth ≤ d, for some d ≥ 0, query = q: we fix the tree-shaped CQ q, ontology = T : we fix the ontology T . The decision problems we are interested in look as follows: parameter-T REE OMQ[restriction1 , . . . , restrictionn ], where parameter is one of the parameters above or blank, and each restrictioni , if any, is one of the restrictions above. To simplify notation, instead of [ontology = T ] we write [T ] and similarly for [query = q]. For example, leaves-T REE OMQ[T ] is the problem Instance: q and A, Parameter: the number of leaves in q, Problem: decide whether T , A |= q. We now construct an ontology T for which this problem is W [1]-hard; for any results from parameterised complexity theory we use below, consult, e.g., [11]. 1 Following Downey [9], our parameters are not necessarily numerical. 3 leaves-T REE OMQ[T ] can be W [1]-hard Theorem 1. There is an ontology T2 such that leaves-T REE OMQ[T2 ] is W [1]-hard. Proof. The proof is by reduction of the W [1]-hard problem SquareTiling [11], which is defined as follows: Instance: a set T of tile types painted in colours from a set C, a positive integer k, Parameter: k, Problem: decide whether T tiles a k × k-grid. Suppose C = {0, . . . , n}, for n ≥ 1, and T = {S1 , . . . , Sm }. Denote by right(t), left(t), top(t) and bottom(t) the right, left, top and bottom colour of St , respectively. Given a binary predicate name R, we denote by Ri a sequence of i-many predicates R. We represent each colour c ≤ n by the following two sequences of binary predicates: encc = P 3n−c F c of length 3n, 2c 2(n−c) cnec = N M N of length 2n + 1. Examples of encc and cnec , for n = 4 and c = 3, are shown in Figs. 2a and 2d, respectively. Each tile St is represented by the following sequence of binary predicates: tilet = B cneright(t) encleft(t) cnetop(t) encbottom(t) E of length 10n + 4. Since the length of encc does not depend on c, we use |enc| to denote the length of some (any) encc , and similarly for |cne| and |tile|. We shall also require the following sequences segm = tile1 tile2 . . . tilem S of length m · |tile| + 1, spring = (XY I)n of length |enc|, probelt = I |cne|+|enc|+2 spring I |tile|+1 I 2n M − of length 2 · |tile| + 1, probedn = I 2 spring I (|tile|+1)k I 2n M − of length 5n + 3 + (|tile| + 1)k. The first sequence will be called a segment and the second a spring. The Boolean CQ q (see Fig. 1) is now defined by taking the following set of atoms (assuming that all variables are existentially quantified): [ [ {A(x0 )} ∪ segm(x0 , x1,1 ) ∪ segm(xi−1,j , xi,j ) ∪ segm(xk,j−1 , x1,j ) ∪ 2≤i≤k 2≤j≤k 1≤j≤k [ [ probelt(xi,j , yi,j ) ∪ probedn(xi,j , zi,j ), 2≤i≤k 1≤i≤k 1≤j≤k 2≤j≤k where R1 . . . Rl (x, y) stands for {R1 (x, x1 ), R2 (x1 , x2 ), . . . , Rl (xl−1 , y)} with fresh variables x1 , . . . , xl−1 . It can be seen that q is a tree-shaped CQ with 2(k − 1)k leaves. Let T2 be an ontology with the following axioms:  A(x) → ∃y BI(x, y) ∧ Right(y) , A(x) → ∃u Sink (x, u), y2,k y3,k yk,k probelt probelt probelt segm x1,k x2,k x3,k xk−1,k xk,k segm segm probedn probedn probedn probedn probedn z1,k z2,k z3,k zk−1,k zk,k y2,3 y3,3 yk,3 probelt probelt probelt segm x1,3 x2,3 x3,3 xk−1,3 xk,3 segm segm probedn probedn probedn probedn probedn z1,3 z2,3 z3,3 segm zk−1,3 zk,3 y2,2 y3,2 yk,2 probelt probelt probelt segm x1,2 x2,2 x3,2 xk−1,2 xk,2 segm segm probedn probedn probedn probedn probedn z1,2 z2,2 z3,2 segm zk−1,2 zk,2 y2,1 y3,1 yk,1 probelt probelt probelt segm x1,1 x2,1 x3,1 xk−1,1 xk,1 segm segm segm x0 Fig. 1. The structure of the CQ q. Right(x) → ∃z MI (x, z) ∧ Right 0 (z) ,   Right(x) → ∃y NI (x, y) ∧ Right(y) , Right 0 (x) → ∃y NI (x, y) ∧ Right 0 (y) , Right 0 (x) → Left(x),  Left(x) → ∃z FI (x, z) ∧ Left 0 (z) ,   Left(x) → ∃y PI (x, y) ∧ Left(y) , Left 0 (x) → ∃y FI (x, y) ∧ Left 0 (y) , Left 0 (x) → Top(x),  Top(x) → ∃z MI (x, z) ∧ Top 0 (z) ,   Top(x) → ∃y NI (x, y) ∧ Top(y) , Top 0 (x) → ∃y NI (x, y) ∧ Top 0 (y) , Top 0 (x) → Bot(x),  Bot(x) → ∃z FI (x, z) ∧ Bot 0 (z) ,   Bot(x) → ∃y PI (x, y) ∧ Bot(y) , Bot 0 (x) → ∃y FI (x, y) ∧ Bot 0 (y) , Bot 0 (x) → ∃z EI (x, z) ∧ A2 (z) ,    A2 (z) → ∃x SI (z, x) ∧ A(x) , A2 (z) → ∃u Sink (z, u), Left 0 (x) → ∃y XȲ (x, y), Bot 0 (x) → ∃y XȲ (x, y), P (x, y) → X(y, x), P (x, y) → Y (y, x), XȲ (x, y) → X(x, y), XȲ (x, y) → Y (y, x),  where C(x) → ∃y Q(x, y) ∧ D(y) abbreviates three axioms C(x) → ∃y QD (x, y), QD (x, y) → Q(x, y) and QD (x, y) → D(y). In addition, T2 contains the axioms – QI (x, y) → Q(x, y) and QI (x, y) → I(y, x), for all predicates of the form QI ; – Sink (x, y) → Q(x, y) and Sink (x, y) → Q(y, x), for all binary predicates Q except I and S. A path in the canonical model CT2 ,{A(a)} where q can be homomorphically mapped is shown in Fig. 2 sandwiched between segm(x0 , x1,1 ) ∪ segm(x1,1 , x2,1 ) on the left and bottom and probelt(x2,1 , y2,1 ) on the right and top (most predicate names are omitted). We show that T2 , {A(a)} |= q iff T tiles a k × k-grid. Here, we only prove (⇒) and leave the converse direction to the reader. For two sequences w = R1 . . . Rl and w0 = R10 . . . Rl0 of binary predicate names, we write w v w0 if T2 |= Ri (x, y) → Ri0 (x, y), for all i (1 ≤ i ≤ l). Let h be a homomorphism from q to C = CT2 ,{A(a)} such that h(x0 ) = v0 (cf. the definition of labelled nulls in Section 2). Then v0 ∈ AC and h(x1,1 ) = v1,1 ∈ AC with v1,1 of the form v0 w1,1 S, for some w1,1 that begins with B but does not contain S. Since (v0 , v0 Sink ) ∈ / S C and |tile| is even, it follows that there is a unique tile t1,1 such that – |w1,1 | = |tile| and w1,1 v tilet1,1 , – the subquery of segm(x0 , x1,1 ) for the sequence tile1 . . . tilet1,1 −1 is mapped to the Sink arrow at v0 (i.e., forwards and backwards between v0 and v0 Sink ); – the subquery for the sequence tilet1,1 +1 . . . tilem is mapped to a Sink arrow at v0 w1,1 (see Fig. 2). Consider now any subquery segm(xi−1,1 , xi,1 ), for 2 ≤ i ≤ k. By the same argument, we obtain h(xi,1 ) = vi,1 , for vi,1 = vi−1,1 wi,1 S, and wi,1 v tileti,1 , for a unique 1 ≤ ti,1 ≤ m. Next, h(x1,2 ) = v1,2 for v1,2 = vk,1 w1,2 S with w1,2 v tilet1,2 and, eventually, every subquery segm(xi−1,j , xi,j ), for 1 ≤ i ≤ k and 1 ≤ j ≤ k, is mapped in such a way that  vi−1,j wi,j S, if i ≥ 2,  h(xi,j ) = vk,j−1 wi,j S, if i = 1, j ≥ 2, with wi,j v tileti,j , for a unique ti,j ,  v0 w1,1 S, if i = 1, j = 1.  We prove now that the tiles Sti,j placed at (i, j) of the k × k-grid form a tiling. First, we show that left(ti,j ) = right(ti−1,j ), for 2 ≤ i ≤ k and 1 ≤ j ≤ k. As we observed above, h(xi,j ) is of the form v wi−1,j S wi,j S. Consider the subquery probelt(xi,j , yi,j ) and recall that wi,j v B cneright(ti,j ) encleft(ti,j ) cnetop(ti,j ) encbottom(ti,j ) E. By the structure of T2 , the subqueries I |enc|+|cne|+2 (xi,j , vi,j ) and spring(vi,j , ui,j ) of probelt(xi,j , yi,j ) are mapped by h in such a way (see Fig. 2) that h(vi,j ) v v wi−1,j S B cneright(ti,j ) encleft(ti,j ) , h(ui,j ) v v wi−1,j S B cneright(ti,j ) P 2c , for c = left(ti,j ). On the other hand, the last element in probelt is M − , and so we must have 0 h(yi,j ) v v B N 2c , for c0 = right(ti−1,j ), tile1 Sink A ... v0 d) e) f) B N x0 y2,1 R N N I− cnec N M M− N N I− N N N N I− P 2c P N N I− enc F X L N N I− |tile| + 2n + 1 tilet1,1 F X N N N I− y2,1 |tile| + 1 N cne M M I− M− M N T N N I− I 2n − 2c N P N N I− I P enc F X B spring v0 w1,1 Sw2,1 S |cne| + |enc| + 1 F X ... E tilem Sink R L T B A x2,1 S v0 w1,1 S X X X S P P A B Sink F F F E Sink cne encc cne enc x1,1 tile1 . . . tilet2,1 ... tilem 3n − 2c Y Y Y X X X c) 2c I Y X I I I Y− Y− Y− X X X P P P P P P P P P F F F b) I− I− I− I− I− I− I− I− I− I− I− I− X− X− X− X− X− X− X− X− X− c Y− Y− Y− Y− Y− Y− Y− Y− Y− P P P P P P P P P F F F a) 3n Fig. 2. Matching the first two segments, segm(x0 , x1,1 ) and segm(x1,1 , x2,1 ), of q and probelt(x2,1 , y2,1 ) in the canonical model C, and the magnified fragments for encc and cnec with n = 4 and c = 3: a) subsequence encc of tilet in q; b) a path in C where encc is mapped; c) matching the spring subquery of probelt in C; d) subsequence cnec of tilet in q; e) a path in C where cnec is mapped; f) mapping variable y2,1 of the subquery probelt(x2,1 , y2,1 ) in C. which is only possible if right(ti−1,j ) = left(ti,j ); see Fig. 2. That down(ti,j ) = up(ti,j−1 ), for 2 ≤ j ≤ k and 1 ≤ i ≤ k, is proved similarly by considering the mapping of the subquery probedn(xi,j , zi,j ). 4 Complexity Landscape In this concluding section, we summarise what is known about the complexity of the decision problems introduced in Section 2. In the table below, parameters are listed hor- izontally, while restrictions on ontologies and CQs vertically in the first two columns, where ‘—’ means no restriction or parameter, FPT† indicates that FTP follows from tractability, while in the grey areas, the problems are trivial. restrictions on parameter T q — query leaves ontology depth (combined complexity) — NP-complete FPT W[1]-hard paraNP W[2]-hard see (∗) — fixed NL-complete FPT† FPT† leaves≤ ` L OG CFL-complete FPT† FPT† FPT† in NP W[1]-hard — NP-hard FPT for some T for some T (∗) fixed fixed in AC0 in L OG CFL leaves≤ ` L OG CFL-hard FPT† for some T , ` = 2 depth≤ d — L OG CFL-complete FPT† FPT† FPT† fixed NL-complete FPT† leaves≤ ` NL-complete FPT† FPT† Recall first that the basic problem T REE OMQ of answering tree-shaped OMQs is NP- complete [15], while standard evaluation of tree-shaped CQs—that is, T REE OMQ[∅]— is L OG CFL-complete [13]. On the other hand, T REE OMQ[T , q] is in AC0 , for any T and q [7, 2], which matches T REE OMQ[∅, q]. Observe also that NL-completeness of T REE OMQ[q] matches the complexity of reasoning in OWL 2 QL [7, 2]. The pa- rameterised problem query-T REE OMQ is fixed-parameter tractable [16, Theorem 21], which means that T REE OMQ can be solved in time f (|q|) · poly(|T |, |A|), for some computable f (here | · | is the size of an encoding of ·). The intractability result for T REE OMQ has recently been refined in [4, Theorem 20], which constructed an ontology T† (of infinite depth) such that T REE OMQ[T† ] is NP- complete. It follows that—unless P = NP—no algorithm can solve T REE OMQ in time poly(|q|, |A|)f (|T |) , for any computable function f . Such a complexity bound would usually be regarded as an indication that, in practice, T REE OMQ could be solved ef- ficiently for small T . Thus, ontology-T REE OMQ (actually, with any parameter deter- mined by the ontology) cannot be FPT. Tractability can be restored by restricting the number of leaves in q and/or the depth of T : as shown in [5], both T REE OMQ[leaves ≤ `] and T REE OMQ[depth ≤ d] are L OG CFL-complete, while T REE OMQ[leaves ≤ `, depth ≤ d] is NL-complete. (In fact, for ontologies of bounded depth, tree-shaped CQs can be generalised to CQs of bounded treewidth.) Moreover, [4] presented an ontology T‡ such that the problem T REE OMQ[T‡ , leaves ≤ 2] is L OG CFL-complete. Yet, leaves-T REE OMQ turns out to be W[1]-hard and depth-T REE OMQ W[2]-hard [4]. In Section 3, we have sharpened the former result by constructing T2 (of infinite depth) such that leaves-T REE OMQ[T2 ] is W[1]-hard. In fact, answering OMQs (T , q) with q having at most ` leaves can be done in time poly(|T |, |q|` , |A|` ) [4]. The W[1]-hardness results mean, however, that this up- per bound cannot be improved—unless W [1] = FPT—to f (`) · poly(|q|, |T |, |A|) or even to f (`) · poly(|q|, |A|)g(|T |) , as Theorem 1 suggests. Answering OMQs (T , q) with T of depth d < ∞ can be done in time poly(|T |d , |q|, |A|) [4]. However—unless W [2] = FPT—it is impossible to improve this to f (d) · poly(|q|, |T |, |A|). Thus, we can expect reasonable efficiency for ontologies of small depth, but no general scala- bility. This does not appear to be a serious restriction as our experience shows that ontologies used for real-world ontology-based data access are of depth at most 5 (see also [8]). On another positive note, the tractable problems T REE OMQ[leaves ≤ `], T REE OMQ[depth ≤ d] and T REE OMQ[leaves ≤ `, depth ≤ d] can be solved using theoretically optimal resources (L OG CFL or NL) by means of OMQ rewriting to non- recursive datalog queries; for details and experiments, consult [4]. A challenging open problem is to classify OWL 2 QL ontologies T according to the combined complexity of answering OMQs (T , q) with tree-shaped or arbitrary CQs q. In particular, are there interesting conditions on T that ensure tractability of T REE OMQ[T ]? Is it the case that, for every T , the problem T REE OMQ[T ] is either in P or NP-complete? In a more general setting, dichotomies of this kind have been considered in [3, 14, 10]. Acknowledgements. This work was supported by the UK EPSRC grant EP/M012670/ ‘iTract: Islands of Tractability in Ontology-Based Data Access’. References 1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995) 2. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and re- lations. Journal of Artificial Intelligence Research (JAIR) 36, 1–69 (2009) 3. Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. ACM Transactions on Database Systems 39(4), 33:1–44 (2014) 4. Bienvenu, M., Kikot, S., Kontchakov, R., Podolskii, V.V., Ryzhikov, V., Zakharyaschev, M.: The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries. In: Proc. of the 36th ACM Symposium on Principles of Database Systems, PODS 2017, pp. 201–216. ACM (2017) 5. Bienvenu, M., Kikot, S., Podolskii, V.V.: Tree-like queries in OWL 2 QL: succinctness and complexity results. In: Proc. of the 30th Annual ACM/IEEE Symposium on Logic in Com- puter Science, LICS 2015. pp. 317–328. IEEE Computer Society (2015) 6. Calautti, M., Gottlob, G., Pieris, A.: Chase termination for guarded existential rules. In: Proc. of the 34th ACM Symposium on Principles of Database Systems, PODS 2015. pp. 91–103. ACM (2015) 7. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: the DL-Lite family. Journal of Automated Reasoning 39(3), 385–429 (2007) 8. Cuenca Grau, B., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.: Acyclicity notions for existential rules and their application to query answering in ontologies. Journal of Artificial Intelligence Research (JAIR) 47, 741–808 (2013) 9. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer (2013) 10. Feier, C., Kuusisto, A., Lutz, C.: Rewritability in monadic disjunctive datalog, MMSNP, and expressive description logics. CoRR abs/1701.02231 (2017). 11. Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Sci- ence. An EATCS Series, Springer (2006) 12. Gogacz, T., Marcinkowski, J.: All-instances termination of chase is undecidable. In: Proc. of the 41st Int. Colloquium Automata, Languages, and Programming (ICALP 2014), Part II. Lecture Notes in Computer Science, vol. 8573, pp. 293–304. Springer (2014) 13. Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. Journal of the ACM 48(3), 431–498 (2001) 14. Hernich, A., Lutz, C., Ozaki, A., Wolter, F.: Schema.org as a description logic. In: Proc. of the 28th Int. Workshop on Description Logics (DL 2015). CEUR Workshop Proceedings, vol. 1350. CEUR-WS (2015), 15. Kikot, S., Kontchakov, R., Zakharyaschev, M.: On (in)tractability of OBDA with OWL 2 QL. In: Proc. of the 24th Int. Workshop on Description Logics (DL 2011). CEUR Workshop Proceedings, vol. 745, pp. 224–234. CEUR-WS (2011) 16. Kikot, S., Kontchakov, R., Podolskii, V.V., Zakharyaschev, M.: On the succinctness of query rewriting over shallow ontologies. In: Proc. of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS’14. pp. 57:1–57:10. ACM (2014)