M Bienvenu

S Kikot
email: kikot@dcs.bbk.ac.uk

R Kontchakov

V Ryzhikov
email: ryzhikov@inf.unibz.it

M Zakharyaschev

Optimal Nonrecursive Datalog Rewritings of Linear TGDs and Bounded (Hyper)Tree-Width Queries

Our concern is answering ontology-mediated queries (O, q), where O is a set of linear tgds and q a conjunctive query (CQ) of bounded hypertree width. Assuming that the arity of predicates is bounded, we show that polynomial-size nonrecursive Datalog rewritings can be constructed and executed in (i) LOGCFL for OMQs with ontologies of bounded existential depth; (ii) NL for OMQs with ontologies of bounded depth and CQs whose hypertree decompositions have a bounded number of leaves; (iii) LOGCFL for OMQs with acyclic CQs whose join trees have a bounded number of leaves.

Introduction

As shown in [START_REF] Bienvenu | The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries[END_REF][START_REF] Bienvenu | Tree-like queries in OWL 2 QL: succinctness and complexity results[END_REF][START_REF] Kikot | On the succinctness of query rewriting over shallow ontologies[END_REF], the optimal combined complexity (LOGCFL and NL) of answering ontology-mediated queries (OMQs) with OWL 2 QL ontologies of bounded depth and conjunctive queries (CQs) of bounded treewidth can be achieved by means of rewriting them into nonrecursive datalog (NDL) queries, though not via positiveexistential rewritings. (Note that in these cases the complexity of OMQs matches the complexity of evaluating the underlying CQs.) Our recent experiments have demonstrated that such NDL rewritings, reformulated as Spark SQL queries with views, are efficiently executed by Apache Spark taking advantage of their parallelisable structure.

The aim of this paper is to extend the above mentioned results to ontologies and CQs with predicates of arbitrary fixed arity. We consider ontologies that consist of linear TGDs (linear existential rules or atomic-hypothesis rules) [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Gottlob | Polynomial Rewritings for Linear Existential Rules[END_REF][START_REF] Gottlob | Query rewriting and optimization for ontological databases[END_REF], which are instances of finite unification sets [START_REF] Thomazo | Compact rewriting for existential rules[END_REF][START_REF] König | Sound, complete and minimal UCQrewriting for existential rules[END_REF][START_REF] König | Query rewriting for existential rules with compiled preorder[END_REF]. Our interest in this problem is also motivated by the system ETAP [START_REF] Boguslavsky | Semantic analysis and question answering: a system under development[END_REF] designed to answer natural language questions by translating them into SPARQL and executing-along with background knowledgeover RDF data extracted from texts. To illustrate, suppose that the data contains the atoms Purchased(j, c) and Car(c) representing the sentence 'John purchased a car'. To answer the question 'has a car been sold?' ETAP utilises the ontology rules (with omitted universal quantifiers) Purchased(x, y) → ∃vz Purchase(v) ∧ hasAgent1(v, x) ∧ hasObject(v, y) ∧ hasAgent2(v, z) ,

Purchase(v) ∧ hasAgent1(v, x) ∧ hasObject(v, y) ∧ hasAgent2(v, z) → ∃v Sale(v ) ∧ hasAgent1(v , z) ∧ hasObject(v , x) ∧ hasAgent2(v , y) ,
where v and v represent the acts of purchase and sale, respectively. The rules are clearly beyond the limitations of OWL 2 QL ; however, the knowledge they represent can also be captured by means of linear TGDs with ternary predicates:

Purchased(x, y) → ∃z Purchase(x, y, z), Purchase(x, y, z) → Sale(z, y, x), which are enough to answer the query ∃xyz (Car(y) ∧ Sale(x, y, z)).

We classify OMQs Q = (O, q) with linear TGDs and predicates of any fixed arity n < ω along three axes: [START_REF] Abiteboul | Foundations of Databases[END_REF] the existential depth d of O, that is, the maximal depth of Skolem terms in the chases of O over arbitrary data (cf. [START_REF] Grau | Acyclicity notions for existential rules and their application to query answering in ontologies[END_REF]), [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF] the hypertree width t of q, and (3) the number of leaves in the tree underlying a hypertree decomposition of q. Thus, OMQ(p 1 , p 2 , p 3 ) denotes the class of OMQs in which parameter (i) is bounded by p i ∈ N ∪ {∞}. We show that, for any fixed d, t, < ω, answering OMQs in the classes OMQ(d, t, ∞) and OMQ(∞, 1, ) can be done in LOGCFL (for combined complexity) by means of NDL-rewritings, and even in NL for OMQ(d, t, ). On the other hand, one can show that answering OMQs in OMQ(∞, t, ), for t, ≥ 2, is NP-hard by observing that the sequence of tree-shaped CQs from the proof of [START_REF] Bienvenu | The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries[END_REF]Theorem 20] is of path width 2. Thus, we obtain a full classification of the classes OMQ(p 1 , p 2 , p 3 ), for p i ∈ N ∪ {∞}, with respect to combined complexity.

Preliminaries

Ontology-mediated queries. Let Σ be a relational schema with the maximum arity ar(Σ) of its predicates bounded by n. By writing P (x), for a predicate name P and an n-tuple x of variables (with possible repetitions), we mean that P is n-ary. By writing γ(x), we mean that the free variables of formula γ are x, where x contains no repetitions. If the meaning is clear from the context, we use set-theoretic notation for lists.

A data instance, D, over Σ is any finite set of ground atoms P (a) with predicate symbols P from Σ. We denote by ind(D) the set of individual constants in D. An ontology is any finite set, O, of sentences of the form

∀x (γ 0 (x) → ∃y γ 1 (x , y)) and ∀x (γ 0 (x) → γ 2 (x )),
where γ 0 , γ 1 and γ 2 are atoms with predicate symbols from Σ and x ⊆ x, for disjoint sets x and y of variables. When writing rules, we omit the universal quantifiers. An ontology-mediated query (OMQ) Q(x) is a pair (O, q(x)), in which O is an ontology and q(x) a conjunctive query (CQ), that is, a formula of the form ∃y ϕ(x, y), where ϕ is a conjunction of atoms

P (z) over Σ with z ⊆ x ∪ y. A tuple a ∈ ind(D) |x| is a certain answer to Q(x) over D if M |= q(a), for every model M of O ∪ D; in this case we write O, D |= q(a). If the list x of answer variables is empty, a certain answer to Q over D is 'yes' if M |= q, for
every model M of O∪D, and 'no' otherwise. OMQs and CQs without answer variables are called Boolean. We often regard CQs as sets of their atoms. We abuse notation and use sets of variables in place of sequences assuming that they are ordered in some (fixed) way. Also, given c ∈ ind(D) |z| and z ∈ z, we write c(z) to refer to the component of c that corresponds to z. Canonical models. An important property of tgds is the fact [START_REF] Abiteboul | Foundations of Databases[END_REF] that, for any O and D, there is a (possibly infinite) canonical (or universal) model C O,D such that, for every CQ q(x) and a ∈ ind(D) |x| , we have O, D |= q(a) iff C O,D |= q(a). Such a canonical model can be constructed by the following (oblivious) chase procedure that, intuitively, 'repairs' D with respect to O (though not in the most economical way). With each rule of the form γ 0 (x) → ∃y γ 1 (x , y), where x = (x 1 , . . . , x n ), y = (y 1 , . . . , y k ) and k > 0, we associate the k-tuple s = (s 1 , . . . , s k ) of distinct n-ary Skolem function symbols. An application of to D under a map h : x → ind(D) such that h(γ 0 ) ∈ D adds h (γ 1 ) to D, where h is defined by taking h (x i ) = h(x i ), for 1 ≤ i ≤ n, and h (y j ) = s j (h(x)), for 1 ≤ j ≤ k. An application of a rule γ 0 (x) → γ 2 (x ) to D under such an h adds h(γ 2 ) to D.

(γ 0 ← γ 1 ∧ • • • ∧ γ m ),
where each γ i is an atom Q(y) with y ⊆ z or an equality (z = z ) with z, z ∈ z. (As usual, we omit ∀z from clauses.) The atom γ 0 is the head of the clause, and γ 1 , . . . , γ m its body. All variables in the head must occur in the body, and = can only occur in the body. The predicates in the heads of clauses in Π are IDB predicates, the rest (including =) EDB predicates. A predicate Q depends on P in Π if Π has a clause with Q in the head and P in the body. Π is a nonrecursive datalog (NDL) program if the (directed) dependence graph of the dependence relation is acyclic. The size |Π| of Π is the number of symbols in it. An NDL query is a pair (Π, G(x)), where Π is an NDL program and G a predicate. A tuple a ∈ ind(D) |x| is an answer to (Π, G(x)) over a data instance D if G(a) holds in the first-order structure with domain ind(D) obtained by closing D under the clauses in Π; in this case we write Π, D |= G(a). The problem of checking whether a is an answer to (Π, G(x)) over D is called the query evaluation problem. The depth of (Π, G(x)) is the length, d(Π, G), of the longest directed path in the dependence graph for Π starting from G.

An NDL query (Π, G(x)) is an NDL-rewriting of an OMQ Q(x) = (O, q(x)) in case O, D |= q(a) iff Π, D |= G(a)
, for any D and any a ∈ ind(D) |x| . Every OMQ is known to have an NDL-rewriting [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF]. Tree decomposition. A tree decomposition of a CQ q with variables var(q) is a pair (T, λ) of an (undirected) tree T = (V, E) and λ : V → 2 var(q) such that -for any atom P (z) ∈ q, there exists v ∈ V with z ⊆ λ(v); -for any variable z in q, the set of vertices {v ∈

V | z ∈ λ(v)} is connected in T . We call λ(v) the bag for v. The width of (T, λ) is max v∈V |λ(v)| -1.
The treewidth of q is the minimum width over all tree decompositions of q. It is known [START_REF] Gottlob | Hypertree decompositions: Questions and answers[END_REF] that, for CQs of bounded arity n, the notions of bounded treewidth and bounded hypertree width [START_REF] Gottlob | Hypertree decompositions and tractable queries[END_REF] are interchangeable. Indeed, in this case, every hypertree decomposition of width t induces a tree decomposition of width t • n. A CQ q is called acyclic if it has a join tree whose nodes are the atoms of q and, whenever atoms γ 1 and γ 2 share a variable, this variable occurs in all atoms along the (unique) path in the tree linking γ 1 and γ 2 . It is known [START_REF] Gottlob | Hypertree decompositions and tractable queries[END_REF] that a CQ q is acyclic iff q is of hypertree width 1.

NL and LogCFL Fragments of NDL

In this section we present two classes of NDL queries that enjoy NL-and LOGCFLcomplete evaluation. First, observe that if the number of variables in each clause of an NDL query is bounded, then the size of its grounding (obtained by replacing variables by all possible combinations of constants) is polynomial. So, evaluation of such NDL queries is tractable. However, if we bound the number of variables in clauses of NDL rewritings of OMQs, then we will also effectively impose a bound on the number of answer variables in their CQs. To avoid this limitation, we treat answer variables of the CQs (and the predicate positions they occur in) differently from all other variables in the NDL-rewritings. Intuitively, answer variables get their values fixed by a candidate certain answer and thus do not cause an exponential blowup of groundings.

Formally, an NDL query (Π, G(x)) is called ordered if each of its IDB predicates Q has a fixed list of variables x Q ⊆ x, the parameters of Q, such that -the parameters of G are x and, in every clause, the parameters of the head include all the parameters of the predicates in the body; -the parameters x Q of each Q occupy the last |x Q | positions in every occurrence of Q in Π; they can, however, occur in other positions too.

The width w(Π, G) of an ordered (Π, G(x)) is the maximum number of non-parameter variables in a clause of Π. Observe that Boolean NDL queries are trivially ordered (their IDB predicates have no parameters), and the width of such queries is simply the maximum number of variables in a clause of Π. As all the NDL-rewritings we construct are ordered, with their parameters being the answer variables, in the sequel we will consider only ordered NDL queries. We say that a class of NDL queries is of bounded width if there is w > 0 such that w(Π, G) ≤ w, for all (Π, G(x)) in the class. As we observed above, evaluation of NDL queries of bounded width is P-complete.

Our first subclass of NDL queries is based on linear rules. An NDL program is linear [START_REF] Abiteboul | Foundations of Databases[END_REF] if the body of its every clause contains at most one IDB predicate.

Theorem 1. Evaluation of linear NDL queries of bounded width is NL-complete for combined complexity.

Our second subclass was inspired by semi-unbounded fan-in circuits. Recall that the class LOGCFL of problems reducible in logarithmic space to context-free languages can equivalently be defined in terms of L-uniform families of semi-unbounded fanin circuits (where OR-gates have arbitrarily many inputs, and AND-gates two inputs) of polynomial size and logarithmic depth. Alternatively, LOGCFL can be defined using nondeterministic auxiliary pushdown automata (NAuxPDAs) [START_REF] Cook | Characterizations of pushdown machines in terms of time-bounded computers[END_REF], which are nondeterministic Turing machines with an additional work tape constrained to operate as a pushdown store. Sudborough [START_REF] Sudborough | On the tape complexity of deterministic context-free languages[END_REF] proved that LOGCFL coincides with the class of problems that are solved by NAuxPDAs in logarithmic space and polynomial time (the space on the pushdown tape is not subject to the logarithmic bound). Moreover, there is an algorithm that, given a semi-unbounded fan-in circuit C and an input, computes the output using an NAuxPDA in logarithmic space in the size of C and exponential time in the depth of C [19, pp. 392-397]. Using these results, it can be shown that any (Π, G(x)) with at most two atoms in the body of any clause can be evaluated on a data instance D by an NAuxPDA in space log |Π| + w(Π, G) • log |D| and time 2 O(d(Π,G)) (thus, in LOGCFL provided the query width is bounded and its depth is logarithmic).

In the rewritings we propose in Sections 5 and 7, however, the number of atoms in the clauses is not bounded. We require the following to generalise the idea. A function ν from the predicate names in Π to non-negative integers N is called a weight function for an NDL query (Π, G(x)) if, for any clause

Q(z) ← P 1 (z 1 ) ∧ • • • ∧ P k (z k ) in Π, we have ν(Q) > 0 and ν(Q) ≥ ν(P 1 ) + • • • + ν(P k ),
Note that ν(P ) can be 0 for an EDB predicate P . To illustrate, we consider NDL queries with the following dependency graphs:

The one on the left has a weight function bounded by the number of predicates (i.e., linear in the size of the query); intuitively, this function corresponds to the number of directed paths from a vertex to the leaves. In contrast, any NDL query with the dependency graph on the right can only have a weight function whose values (numbers of paths) are exponential. Linear NDL queries have weight functions bounded by 1.

Let e Π be the maximum number of EDB predicates in a clause of Π. The skinny depth sd(Π, G) of (Π, G(x)) is the minimum value of 2d(Π, G) + log ν(G) + log e Π over possible weight functions ν. One can show, using Huffman coding, that any NDL query (Π, G(x)) can be transformed into an equivalent skinny NDL query (Π , G(x)) of depth not exceeding sd(Π, G) and such that |Π | = O(|Π| 2 ) and w(Π , G) ≤ w(Π, G). We say that a class of NDL queries has logarithmic skinny depth if there is c > 0 such that sd(Π, G) ≤ c log |Π|, for all (Π, G(x)) in the class. We now obtain: Theorem 2. Evaluation of NDL queries of logarithmic skinny depth and bounded width is LOGCFL-complete for combined complexity.

NDL Rewritings over (Complete) Data

We say that a data instance D is complete for an ontology O if O, D |= P (a) implies P (a) ∈ D, for any ground atom P (a), where P in Σ and a ⊆ ind(D). An NDL query (Π, G(x)) is an NDL-rewriting of an OMQ Q(x) = (O, q(x)) over complete data in case O, D |= q(a) iff Π, D |= G(a), for any D complete for O and any a ⊆ ind(D).

Given an NDL-rewriting (Π, G(x)) of Q(x) over complete data, we denote by Π * the result of replacing each EDB predicate P in Π with a fresh IDB predicate P * of the same arity and adding the clauses P * (z) ← γ for every atom γ with a predicate symbol from O such that O |= γ → P (z), where z is a tuple of variables (with possible repetitions). Clearly, (Π * , G(x)) is an NDL-rewriting of Q(x) over arbitrary data instances and

|Π * | ≤ |Π| + ar(Σ) ar(Σ) • |O| 2 .
We say that a class of OMQs is skinny-reducible if there are c > 0 and w > 0 and an L LOGCFL -transducer that, given any OMQ Q(x) in the class, computes its NDLrewriting (Π, G(x)) over complete data with sd(Π, G) ≤ c log |Π| and w(Π, G) ≤ w. Theorem 2 and the transformation * give the following: Corollary 1. Answering OMQs is in LOGCFL for combined complexity for any skinnyreducible class.

The transformation * , however, does not preserve linearity because it replaces occurrences of EDB predicates P by IDB predicates P * . A more involved 'linear' construction is given in the proof of the following, where a possible increase of the width is due to the 'replacement' of atoms P (z) by atoms γ whenever O |= γ → P (z): Lemma 1. Fix any w > 0. There is an L NL -transducer that, for a linear NDL-rewriting (Π, G(x)) of an OMQ Q(x) over complete data with w(Π, G) ≤ w, computes its linear NDL-rewriting (Π , G(x)) over arbitrary data with w(Π , G) ≤ w + ar(Σ).

Conditional Rewritings

Let Q(x) = (O, q(x)) be an OMQ with an ontology of finite depth. Intuitively, we recursively split q(x) into subqueries q D based on subtrees D of a tree decomposition of q and combine the rewritings of q D into a rewriting of q. To guarantee 'compatibility' of the rewritings of the subqueries, we take account of the types of points on the boundaries of the q D . So, for each D and each type w, we take a fresh IDB predicate G w D to represent the conditional rewriting of q D provided that its boundary satisfies the type. We now give formal definitions.

A type is a partial map s from the variables of q to term O ∪{ε}; its domain is denoted by dom(s). The unique partial type with dom(ε) = ∅ is denoted by ε. We use types to represent how variables are mapped into the canonical model: s(z) = ε means that z is mapped to an individual constant and s(z) = f (a), for a Skolem term f (a), means that z is mapped to an element of the form f (c), for some c ⊆ ind(D). Given a type s and a tuple z = (z 1 , . . . , z n ) ⊆ dom(s), we denote the tuple (s(z 1 ), . . . , s(z n )) by s(z). A type s is compatible with a bag λ(t) if s(x) = ε, for all x ∈ x ∩ dom(s), and, for every S(z) ∈ q with z ⊆ λ(t) ∩ dom(s), one of the following applies: .

Denote the answer variables that occur in dom(s) by x s . Our rewritings use conjunctions At s (var(s), x s ) of the following formulas, for all S(z) ∈ q with z ⊆ dom(s): Strictly speaking, the resulting rewritings will not be NDL programs because of disjunctions in (b ), but we can get rid of them using an extra predicate and (if needed) the construction from the proof of Lemma 1 keeping the size and the execution time polynomial.

(d ) S(z) if s(z) ⊆ {ε}; (

LOGCFL Rewritings for OMQ(d, t, ∞)

We now construct skinny-reducible NDL rewritings for the CQs of bounded treewidth. Theorem 3. For any d ≥ 0 and t ≥ 1, the class OMQ(d, t, ∞) is skinny-reducible.

Fix a connected CQ q(x) and a tree decomposition (T, λ) of its Gaifman graph. Let D be a subtree of T . The size of D is the number of nodes in it. A node t of D is called boundary if T has an edge {t, t } with t / ∈ D. We denote by ∂D the union of all λ(t) ∩ λ(t ) for boundary nodes t of D and its neighbours t in T outside D. The degree deg(D) of D is the number of its boundary nodes (so, the only subtree of T of degree 0 is T itself). We say that a node t splits D into subtrees D 1 , . . . , D k if the D i partition D without t: each node of D except t belongs to exactly one D i . Lemma 2. Let D be a subtree of T of size n > 1.

If deg(D) = 2, then there is a node t splitting D into subtrees of size ≤ n/2 and degree ≤ 2 and, possibly, one subtree of size < n -1 and degree 1. If deg(D) ≤ 1, then there is t splitting D into subtrees of size ≤ n/2 and degree ≤ 2.

We define recursively a set R of subtrees of T , a binary 'predecessor' relation ≺ on R, and a function β on R indicating the bag of the splitting node. We begin by adding T to R. Take any D ∈ R that has not been split yet. If D is of size 1, then β(D) = λ(t) for the only node t of D. Otherwise, by Lemma 2, we find a node t in D that splits it into D 1 , . . . , D k . We set β(D) = λ(t) and, for 1 ≤ i ≤ k, add D i to R and set D i ≺ D; then, we apply the procedure to each of D 1 , . . . , D k . For each D ∈ R, we recursively define a set of atoms

q D = S(z) ∈ q | z ⊆ β(D) ∪ D ≺D q D .
Let x D be the set of variables from x that occur in q D . By the definition of tree decomposition, q T = q and x T = x.

We now define an NDL-rewriting of Q(x) = (O, q(x)). Fix D ∈ R and a type w with dom(w) = ∂D. Let G w D (var(w), x D ) be a fresh IDB predicate with parameters x D . As we described above, a node is selected in D to split it into smaller trees (provided that it contains more than one node). We extend the type w to cover the variables β(D) of the selected bag: more precisely, we consider types s with dom(s) = β(D) such that they are compatible with bag β(D) and agree with w on their common domain. Observe that, if D is a subtree resulting from splitting D, then the domain of the extended type, s ∪ w, includes ∂D , and thus ∂D coincides with the domain of the restriction of s ∪ w to ∂D , denoted (s ∪ w) ∂D . Now, for each type s with dom(s) = β(D) such that s is compatible with bag β(D) and agrees with w on their common domain, the NDL program

Π LOG Q contains G w D (var(w), x D ) ← At s (var(s), x s ) ∧ D ≺D G (s∪w) ∂D D (var((s ∪ w) ∂D ), x D ).
By induction on ≺, one can now show that

(Π LOG Q , G ε T ) is a rewriting of Q(x).
Example 1. Let q(x 0 , x 3 ) = ∃x 1 x 2 S(x 0 , x 1 )∧R(x 1 , x 2 )∧R(x 2 , x 3 ) and O consist of the following linear rules:

: U (x, y) → ∃v T (x, v, y), T (x, v, y) → R(v, x), T (x, v, y) → R(y, v), T (x, v, y) → S(x, y).
The subtree structure of the tree decomposition of q(x 0 , x 3 ) and the canonical model are as follows:

D D1 D2 x0 x1 x1 x2 x2 x3 S R R a1 a2 f (a1, a2) U R R S
The goal predicate for the rewriting of q(x 0 , x 3 ) is G ε D (x 0 , x 3 ) with parameters x 0 and x 3 . For the type s for the middle bag sending x 1 to ε and x 2 to f (a 1 , a 2 ), we have

G ε D (x 0 , x 3 ) ← G x1 →ε D1 (x 1 , x 0 ) ∧ U ( a 1 , a 2 ) ∧ (x 1 = a 2 ) ∧ G x2 →f (a1,a2) D2 ( a 1 , a 2 , x 3 ),
where and a 1 and a 2 are the twin variables in var(s). Note that the type for G x2 →f (a1,a2) D2

has no non-twin variables, and we have the following rule for this predicate

G x2 →f (a1,a2) D2 ( a 1 , a 2 , x 3 ) ← U ( a 1 , a 2 ) ∧ (x 3 = a 1 ).

NL Rewritings for OMQ(d, t, )

For OMQs based upon bounded leaf queries and bounded depth ontologies, we establish the following theorem: Theorem 4. Let d ≥ 0, t ≥ 1 and ≥ 2 be fixed. There is an L NL -transducer that, given any OMQ in OMQ(d, t, ), constructs its polynomial-size linear NDL-rewriting of width ≤ (t + 1).

Let O be an ontology of finite depth d and q(x) a CQ with a tree decomposition (T, λ) of width ≤ t having ≤ leaves. Fix one of the nodes of T as root, and let M be the maximum distance to a leaf from the root. For 0 ≤ n ≤ M , by an n-slice we mean the set of all nodes of T located at distance n from the root. Denote by y n the union of all bags λ(t) for a node t in the n-slice. For 1 ≤ n ≤ M , let z n be the union of all λ(t) ∩ λ(t ) for a node t in the n-slice and its predecessor t in T (which is in (n -1)-slice), and let z 0 = ∅. By definition, z n+1 ⊆ y n+1 ∩ y n and, clearly, |z n | ≤ |y n | ≤ (t + 1). Denote by q n (z n ∃ , x ≥n ) the query consisting of all atoms S(z) of q with z ⊆ k≥n y k , where z n ∃ = z n \ x and x ≥n = x ∩ k≥n y k . These queries and sets of variables for the CQ from Example 1 are shown below:

q 2 q 1 q 0 x0 x1 x1 x2 x2 x3 S R R y 2 = {x2, x3} z 2 = {x2} x 2 = {x3} y 1 = {x1, x2} z 1 = {x1} x 1 = ∅ y 0 = {x0, x1} z 0 = ∅ x 0 = {x0}
A type for z n is a total map w from z n to term O ∪{ε}. Likewise, a type for y n is a total map s from y n to term O ∪{ε}. We say s compatible with y n if it is compatible with every bag λ(t) in the n-slice.

Consider the NDL program Π LIN Q defined as follows. For every 0 ≤ n < M and every type w for z n , we introduce a new IDB predicate G w n (var(w), x ≥n ) with parameters x ≥n . For each type s for y n such that s is compatible with y n and agrees with w on z n , the program Π LIN Q contains the clause

G w n (var(w), x ≥n ) ← At s (var(s), x s ) ∧ G s z n+1 n+1 (var(s z n+1 ), x ≥n+1 ).
For every type w for z M and every type s for y M such that s is compatible with y M and agrees with w on z M , we include the clause

G w M (var(w), x ≥M ) ← At s (var(s), x s ).
Finally, we use G ε 0 with parameters x as the goal predicate (note that z 0 = ∅, and so the domain of any type for z 0 is empty). It should be clear that Π LIN Q is a linear NDL program of width ≤ (t + 1) and containing ≤ |q| • | term O | (t+1) predicates. Moreover, it takes only logarithmic space to store a type w, which allows us to show that Π LIN Q can be computed by an L NLtransducer. We apply Lemma 1 to obtain an NDL-rewriting for arbitrary data instances, and then use Theorem 1 to conclude that the resulting program can be evaluated in NL.

LOGCFL Rewritings for OMQ(∞, 1, )

Unlike the previous two classes, answering OMQs from the class OMQ(∞, 1, ) can be harder-LOGCFL-complete-than evaluating their CQs, which can be done in NL.

Theorem 5. For any fixed ≥ 2, the class OMQ(∞, 1, ) is skinny-reducible.

For OMQs with ontologies of unbounded depth and acyclic CQs whose join trees have a bounded number of leaves, our rewriting uses the notion of Skolem witness that generalises tree witnesses [START_REF] Kikot | Conjunctive query answering with OWL 2 QL[END_REF].

Let Q(x) = (O, q(x)) be an OMQ, let s = (s 1 r , . . . , s n r , s i ) be a tuple of disjoint sets of variables in q(x) such that s i = ∅ and s i ∩ x = ∅, and let s r = s

1 r ∪ • • • ∪ s n r , q s = S(z) ∈ q | z ⊆ s r ∪ s i and z ⊆ s r .
If q s is a minimal subset of q containing every atom of q with at least one variable from s i and such that there is a homomorphism h : q s → C O,{P (a)} with a = (a 1 , . . . , a n ) and h -1 (a j ) = s j r for 1 ≤ j ≤ n, then we call s a Skolem witness for Q(x) generated by P (a). Intuitively, s identifies a minimal subset of q that can be mapped to the Skolem part of the canonical model C O,{P (a)} consisting of Skolem terms: the variables in s r are mapped to constants from a and the variables in s i to Skolem terms in term O (P (a)).

The logarithmic-depth NDL-rewriting for OMQ(∞, 1, ) is based on the following: Lemma 5. Every tree T of size n has a node splitting it into subtrees of size ≤ n/2 .

Let Q(x 0 ) = (O, q 0 (x 0 )) be an OMQ with an acyclic CQ having a join tree T 0 . We repeatedly apply Lemma 5 to decompose the CQ into smaller and smaller subqueries. Formally, for an acyclic CQ q, we denote by γ q a vertex in the join tree T for q that satisfies the condition of Lemma 5. Let Q be the smallest set containing q 0 (x 0 ) and the following CQs, for every q(x) ∈ Q with at least one existentially quantified variable:

(1) the CQs q i (x i ) corresponding to the connected components T i with root γ q i adjacent to γ q of the result of removing γ q from T , where x i consists of the restriction of x to the variables in q i together with the common variables of γ q i and γ q ;

(2) for each Skolem witness s for (O, q(x)) with s r = ∅ and γ q ∈ q s , the CQs q s 1 (x s 1 ), . . . , q s k (x s k ) that correspond to the connected components T s i of the results of removing q s from T (note that q s is connected in T ), where each x s i is the set of variables in x ∪ s r that occur in q s i . The NDL program Π SW Q uses IDB predicates G q (x), for q(x) ∈ Q, whose parameters are the variables in x 0 that occur in q(x). For each q(x) ∈ Q that has no existentially quantified variables, we include the clause G q (x) ← q(x). For any q(x) ∈ Q with existential variables, we include

G q (x) ← γ q ∧ 1≤i≤n G q i (x i ),
where q 1 (x 1 ), . . . , q n (x n ) are the subqueries obtained by splitting q by γ q in (1), and, for any Skolem witness s of (O, q(x)) with s r = ∅ and γ q ∈ q s and any P (a) generating s, the clause G q (x) ← P ( a) ∧

z∈s j r (z = a j ) ∧ 1≤i≤k G q s i (x s i ),
where q s 1 , . . . , q s k are the connected components of q without q s . Finally, if q 0 is Boolean, then we include G q 0 ← P ( a) for all atoms P (a) such that O, {P (a)} |= q 0 . Lemma 6. For any OMQ with an acyclic CQ, any data D complete for O, any query q(x) ∈ Q and any b ∈ ind(D) |x| , we have Π SW Q , D |= G q (b) iff there is a homomorphism h : q → C O,D with h(x) = b. Now fix > 1 and consider Q(x) = (O, q 0 (x)) from the class OMQ(∞, 1, ) (remember that we have fixed arity n). The size of the program Π SW Q is polynomially bounded in |Q| since q 0 has polynomially-many subtrees of T q 0 and O(|q 0 | ) Skolem witnesses (there are at most O(|q 0 | • |Σ| • n n ) pairs of a Skolem witness s and its generating atom P (a)). It is readily seen that the function ν defined by ν(G q ) = |q|, for each q ∈ Q, is a weight function for (Π SW Q , G q 0 (x)) with ν(G q 0 ) ≤ |Q|. Moreover, by Lemma 5, d(Π SW Q , G q 0 ) ≤ log ν(G q 0 )+1; also, w(Π SW Q , G q 0 ) ≤ +1. Finally, we note that, since the number of leaves is bounded, it is in NL to decide whether a vertex satisfies the conditions of Lemma 5, and in LOGCFL to decide whether O, {P (a)} |= q(a), for bounded-leaf acyclic CQs q(x) (see the full version1 ), or whether a (logspace) representation of a possible Skolem witness is indeed a Skolem witness. This allows us to show that (Π SW Q , G q 0 (x)) can be generated by an L LOGCFL -transducer. By Corollary 1, the obtained NDL-rewritings can be evaluated in LOGCFL.

Conclusion

We presented NDL rewritings for three classes of OMQs with CQs of bounded (hyper)tree width and ontologies given as linear TGDs. These NDL rewritings can be constructed and evaluated in LOGCFL, NL and LOGCFL, respectively (provided that the arity of predicates is bounded). Since the three upper bounds match the lower bounds inherited from the OWL 2 QL setting [START_REF] Bienvenu | Tree-like queries in OWL 2 QL: succinctness and complexity results[END_REF], the proposed rewritings are theoretically optimal.

  For an ontology O and a ground atom P (a), we set term O (P (a)) = ∆ C O,{P (a)} \ a. We denote by term O the union of term O (P (a)), for all possible (up to renaming the constants) atoms P (a) with predicates in O (assuming that distinct P (a) do not share constants). It should be clear that O is of finite depth iff term O is finite. By counting the number of possible linear derivations of Skolem terms, we see that, for O of depth k, | term O | ≤ (ar(Σ) ar(Σ) |O|) k . We assume that any constant a occurring in term O has a twin variable a and denote by a the result of replacing all constants in a with their twin variables. Given a tuple b ⊆ ind(D), we denote by a/b( a) the substitution that maps each a in a to the corresponding b( a) in b. NDL-rewritings. A datalog program, Π, is a finite set of Horn clauses of the form ∀z

  (d) s(z) ⊆ {ε}; (b) there is P (a) such that s(z) ⊆ term O (P (a)) ∪ {ε} but neither s(z) ⊆ {ε} nor s(z) ⊆ term O (P (a)); (i) there is P (a) such that s(z) ⊆ term O (P (a)) and S(s(z)) ∈ C O,{P (a)} . Given a type s, we take a tuple of variables var(s) that contains, for z ∈ dom(s) \ x, variable z, if s(z) = ε, and variables a, if s(z) ∈ term O (P (a))

  b ) the disjunction g : z → a P ( a) ∧ z∈z and g(z)=a (z = a) over grounding functions g : z → a such that z = {z ∈ z | s(z) = ε} = ∅, z = {z ∈ z | s(z) ∈ term O (P (a))} = ∅ and C O,{P (a)} contains the result of replacing z and z in S(z) by g(z ) and s(z ), respectively; (i ) P ( a) if s(z) ⊆ term O (P (a)).

Lemma 3 .

 3 For any D complete for O, any predicate G w D and any b ∈ ind(D) |var(w)|+|x D | , we have Π LOG Q , D |= G w D (b) iff there is a homomorphism h : q D → C O,D such that h(z) = b(z), for all z ∈ x D and all z ∈ ∂D with w(z) = ε, w(z)[a/b( a)], for all z ∈ ∂D with w(z) ∈ term O (P (a)).

Lemma 4 .

 4 For any D complete for O, any predicate G w n , any b ∈ ind(D) |var(w)|+|x ≥n | , we have Π LIN Q , D |= G w n (b) iff there is a homomorphism h : q n → C O,D such that h(z) = b(z), for all z ∈ x ≥n and all z ∈ z n ∃ with w(z) = ε, w(z)[a/b( a)], for all z ∈ z n ∃ with w(z) ∈ term O (P (a)).

  The chase algorithm applies these two rules exhaustively to O and D in a breadth-first manner. More precisely, we set C 0 , h i ) such that i ∈ O with γ i on the left-hand side is applicable toC n-1 O,D under h i . If none of the atoms in the h i (γ i ) is of level n -1, then we set C n O,D = C n-1 O,D . Otherwise, we apply the i under h i to C n-1O,D one after the other and say that the newly added atoms are of (derivation) level n; the resulting extension ofC n-1 O,D is denoted by C n O,D . The canonical model C O,D is then the union of all C n O,D , for n < ω. The domain ∆ C O,D of C O,Dconsists of terms built from the constants in D using Skolem functions s j , for ∈ O. The depth of such a term is the maximal number of nested occurrences of function symbols in it. We say that O is of depth k ≤ ω if k is the minimal ordinal such that ∆ C O,D contains no terms of depth > k, for any data D.

	O,D = D and say that
	the atoms in C 0 O,D are of (derivation) level 0. Assuming that C n-1 O,D has already been constructed, we define C n O,D as follows. Take some enumeration of all distinct pairs
	(

i

http://www.dcs.bbk.ac.uk/ ˜kikot/DL17-1-full.pdf