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.
As shown in [
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) [
where v and v0 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:
which are enough to answer the query 9xyz (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: (1) the existential depth d of O, that is, the maximal depth of
Skolem terms in the chases of O over arbitrary data (cf. [
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 8x ( 0(x) ! 9y 1(x0; y)) and 8x ( 0(x) ! 2(x0)); where 0, 1 and 2 are atoms with predicate symbols from and x0 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 9y '(x; y), where ' is a conjunction of atoms P (z) over with z x [ y. A tuple a 2 ind(D)jxj is a certain answer to Q(x) over D if M j= q(a), for every model M of O [ D; in this case we write O; D j= q(a). If the list x of answer variables is empty, a certain answer to Q over D is ‘yes’ if M j= 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 2 ind(D)jzj and z 2 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 [
The domain CO;D of CO;D consists of terms built from the constants in D using Skolem functions sj%, for % 2 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 CO;D contains no terms of depth > k, for any data D. For an ontology O and a ground atom P (a), we set termO(P (a)) = CO;fP (a)g n a. We denote by termO the union of termO(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 termO is finite. By counting the number of possible linear derivations of Skolem terms, we see that, for O of depth k, j termO j (ar( )ar( )jOj)k . We assume that any constant a occurring in termO has a twin variable a and denote by a the result of replacing all constants in a with their e e twin variables. Given a tuple b ind(D), we denote by a=b(ae) the substitution that maps each a in a to the corresponding b(ea) in b.
NDL-rewritings. A datalog program, , is a finite set of Horn clauses of the form
8z ( 0 1 ^ ^ m), where each i is an atom Q(y) with y z or an equality
(z = z0) with z; z0 2 z. (As usual, we omit 8z 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 j j 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 2 ind(D)jxj 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 j= 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 j= q(a) iff ; D j= G(a), for any D and any a 2 ind(D)jxj. Every OMQ is
known to have an NDL-rewriting [
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 ! 2var(q) such that – for any atom P (z) 2 q, there exists v 2 V with z – for any variable z in q, the set of vertices fv 2 V j z 2 (v); (v)g is connected in T .
We call (v) the bag for v. The width of (T; ) is maxv2V j (v)j 1. The treewidth
of q is the minimum width over all tree decompositions of q. It is known [
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 xQ 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 xQ of each Q occupy the last jxQj 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 [
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) [
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) P1(z1) ^ ^ Pk(zk) in , we have (Q) > 0 and (Q) (P1) + + (Pk); 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 ( 0; G(x)) of depth not exceeding sd( ; G) and such that j 0j = O(j j2) and w( 0; 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 j j, for all ( ; G(x)) in the class. We now obtain:
is LOGCFL-complete for combined complexity. 3.1
NDL Rewritings over (Complete) Data We say that a data instance D is complete for an ontology O if O; D j= P (a) implies P (a) 2 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 j= q(a) iff ; D j= 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 j= ! 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 j j j j + ar( )ar( ) jOj2.
We say that a class of OMQs is skinny-reducible if there are c > 0 and w > 0 and an LLOGCFL-transducer that, given any OMQ Q(x) in the class, computes its NDLrewriting ( ; G(x)) over complete data with sd( ; G) c log j j and w( ; G) w. Theorem 2 and the transformation give the following:
reducible 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 j= ! P (z): Lemma 1. Fix any w > 0. There is an LNL-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 ( 0; G(x)) over arbitrary data with w( 0; G) w + ar( ). 4
Let Q(x) = (O; q(x)) be an OMQ with an ontology of finite depth. Intuitively, we recursively split q(x) into subqueries qD based on subtrees D of a tree decomposition of q and combine the rewritings of qD 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 qD. So, for each D and each type w, we take a fresh IDB predicate GDw to represent the conditional rewriting of qD 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 termO [f"g; 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 = (z1; : : : ; zn) dom(s), we denote the tuple (s(z1); : : : ; s(zn)) by s(z). A type s is compatible with a bag (t) if s(x) = ", for all x 2 x \ dom(s), and, for every S(z) 2 q with z (t) \ dom(s), one of the following applies: (d) s(z)
f"g; (b) there is P (a) such that s(z)
s(z) termO(P (a)); (i) there is P (a) such that s(z) termO(P (a)) [ f"g but neither s(z) f"g nor termO(P (a)) and S(s(z)) 2 CO;fP (a)g.
Given a type s, we take a tuple of variables var(s) that contains, for z 2 dom(s) n x, variable z; if s(z) = "; and variables a; if s(z) 2 termO(P (a)): e Denote the answer variables that occur in dom(s) by xs. Our rewritings use conjunctions Ats(var(s); xs) of the following formulas, for all S(z) 2 q with z dom(s): (d0) S(z) if s(z) (b0) the disjunction f"g; _
h g : z0 ! a
P (a) ^ e z2z0 and g(z)=a ^ (z = a)i e over grounding functions g : z0 ! a such that z0 = fz 2 z j s(z) = "g 6= ;, z00 = fz 2 z j s(z) 2 termO(P (a))g =6 ; and CO;fP (a)g contains the result of replacing z0 and z00 in S(z) by g(z0) and s(z00), respectively; (i0) P (ae) if s(z)
termO(P (a)).
Strictly speaking, the resulting rewritings will not be NDL programs because of disjunctions in (b0), 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. 5
LOGCFL Rewritings for OMQ(d; t; 1) We now construct skinny-reducible NDL rewritings for the CQs of bounded treewidth. Theorem 3. For any d 0 and t
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 ft; t0g with t0 2= D. We denote by @D the union of all (t) \ (t0) for boundary nodes t of D and its neighbours t0 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 D1; : : : ; Dk if the Di partition D without t: each node of D except t belongs to exactly one Di.
If deg(D) = 2, then there is a node t splitting D into subtrees of size 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 n=2 and 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 2 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 D1; : : : ; Dk. We set (D) = (t) and, for 1 i k, add Di to R and set Di D; then, we apply the procedure to each of D1; : : : ; Dk. For each D 2 R, we recursively define a set of atoms qD = Let xD be the set of variables from x that occur in qD. By the definition of tree decomposition, qT = q and xT = x.
We now define an NDL-rewriting of Q(x) = (O; q(x)). Fix D 2 R and a type w with dom(w) = @D. Let GDw(var(w); xD) be a fresh IDB predicate with parameters xD. 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 D0 is a subtree resulting from splitting D, then the domain of the extended type, s [ w, includes @D0, and thus @D0 coincides with the domain of the restriction of s [ w to @D0, denoted (s [ w) @D0 . 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 QLOG contains GDw(var(w); xD)
Ats(var(s); xs) ^ ^D0 DG(Ds0[w) @D0 (var((s [ w) @D0 ); xD0 ): By induction on , one can now show that ( QLOG; G"T ) is a rewriting of Q(x). Example 1. Let q(x0; x3) = 9x1x2 S(x0; x1)^R(x1; x2)^R(x2; x3) and O consist of the following linear rules: % :
U (x; y) ! 9v T (x; v; y); T (x; v; y) ! R(y; v);
T (x; v; y) ! R(v; x); T (x; v; y) ! S(x; y): The subtree structure of the tree decomposition of q(x0; x3) and the canonical model are as follows: x1
S x0
D1
D x2
R x1
D2 x3
R x2 f%(a1; a2) R
R S
U a1 a2 The goal predicate for the rewriting of q(x0; x3) is G"D(x0; x3) with parameters x0 and x3. For the type s for the middle bag sending x1 to " and x2 to f%(a1; a2), we have G"D(x0; x3)
GxD117!"(x1; x0) ^ U (a1; ea2) ^ (x1 = a2) ^ GxD227!f%(a1;a2)(a1; ea2; x3);
e e e where and a1 and a2 are the twin variables in var(s). Note that the type for GxD227!f%(a1;a2) e e has no non-twin variables, and we have the following rule for this predicate GxD227!f%(a1;a2)(a1; ea2; x3) e
U (a1; ea2) ^ (x3 = a1): e e Lemma 3. For any D complete for O, any predicate GDw and any b 2 ind(D)jvar(w)j+jxDj, we have QLOG; D j= GDw(b) iff there is a homomorphism h : qD ! CO;D such that for all z 2 @D with w(z) 2 termO(P (a)): 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 LNL-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 yn the union of all bags (t) for a node t in the n-slice. For 1 n M , let zn be the union of all (t) \ (t0) for a node t in the n-slice and its predecessor t0 in T (which is in (n 1)-slice), and let z0 = ;. By definition, zn+1 yn+1 \ yn and, clearly, jznj jynj `(t + 1). Denote by qn(z9n; x n) the query consisting of all atoms S(z) of q with z Sk n yk, where z9n = zn n x and x n = x \ Sk n yk. These queries and sets of variables for the CQ from Example 1 are shown below: q0 x1
S x0 q1 x2
R x1 q2 x3
R x2 y2 = fx2; x3g z2 = fx2g x2 = fx3g y1 = fx1; x2g z1 = fx1g x1 = ; y0 = fx0; x1g z0 = ; x0 = fx0g A type for zn is a total map w from zn to termO [f"g. Likewise, a type for yn is a total map s from yn to termO [f"g. We say s compatible with yn if it is compatible with every bag (t) in the n-slice.
Consider the NDL program QLIN defined as follows. For every 0 n < M and every type w for zn, we introduce a new IDB predicate Gnw(var(w); x n) with parameters x n. For each type s for yn such that s is compatible with yn and agrees with w on zn, the program QLIN contains the clause
Gnw(var(w); x n)
Ats(var(s); xs) ^ Gsn+z1n+1 (var(s zn+1 ); x n+1): For every type w for zM and every type s for yM such that s is compatible with yM and agrees with w on zM , we include the clause
GwM (var(w); x M )
Ats(var(s); xs): Finally, we use G0" with parameters x as the goal predicate (note that z0 = ;, and so the domain of any type for z0 is empty).
Lemma 4. For any D complete for O, any predicate Gnw, any b 2 ind(D)jvar(w)j+jx nj, we have QLIN; D j= Gnw(b) iff there is a homomorphism h : qn ! CO;D such that for all z 2 x n and all z 2 z9n with w(z) = "; for all z 2 z9n with w(z) 2 termO(P (a)):
It should be clear that QLIN is a linear NDL program of width `(t + 1) and containing jqj j termO j`(t+1) predicates. Moreover, it takes only logarithmic space to store a type w, which allows us to show that QLIN can be computed by an LNLtransducer. 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. 7
LOGCFL Rewritings for OMQ(1; 1; `) Unlike the previous two classes, answering OMQs from the class OMQ(1; 1; `) can be harder—LOGCFL-complete—than evaluating their CQs, which can be done in NL.
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 [
Let Q(x) = (O; q(x)) be an OMQ, let s = (sr1; : : : ; srn; si) be a tuple of disjoint sets of variables in q(x) such that si 6= ; and si \ x = ;, and let sr = sr1 [ [ srn, qs = If qs is a minimal subset of q containing every atom of q with at least one variable from si and such that there is a homomorphism h : qs ! CO;fP (a)g with a = (a1; : : : ; an) and h 1(aj ) = srj 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 CO;fP (a)g consisting of Skolem terms: the variables in sr are mapped to constants from a and the variables in si to Skolem terms in termO(P (a)).
The logarithmic-depth NDL-rewriting for OMQ(1; 1; `) is based on the following:
dn=2e.
Let Q(x0) = (O; q0(x0)) be an OMQ with an acyclic CQ having a join tree T0. 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 q0(x0) and the following CQs, for every q(x) 2 Q with at least one existentially quantified variable: (1) the CQs qi(xi) corresponding to the connected components Ti with root qi adjacent to q of the result of removing q from T , where xi consists of the restriction of x to the variables in qi together with the common variables of qi and q; (2) for each Skolem witness s for (O; q(x)) with sr 6= ; and q 2 qs, the CQs qs(xs1); : : : ; qsk(xs ) that correspond to the connected components Tis of the re1 k sults of removing qs from T (note that qs is connected in T ), where each xis is the set of variables in x [ sr that occur in qis.
The NDL program QSW uses IDB predicates Gq(x), for q(x) 2 Q, whose parameters are the variables in x0 that occur in q(x). For each q(x) 2 Q that has no existentially quantified variables, we include the clause Gq(x) q(x). For any q(x) 2 Q with existential variables, we include
Gq(x) q ^ ^ 1 i n
Gqi (xi); where q1(x1); : : : ; qn(xn) are the subqueries obtained by splitting q by q in (1), and, for any Skolem witness s of (O; q(x)) with sr 6= ; and q 2 qs and any P (a) generating s, the clause
Gq(x)
P (a) ^ ^ e z2srj (z = aj ) ^ e ^ 1 i k
Gqis (xis); where qs1; : : : ; qsk are the connected components of q without qs. Finally, if q0 is Boolean, then we include Gq0 P (ae) for all atoms P (a) such that O; fP (a)g j= q0.
q(x) 2 Q and any b 2 ind(D)jxj, we have QSW; D j= Gq(b) iff there is a homomorphism h : q ! CO;D with h(x) = b.
Now fix ` > 1 and consider Q(x) = (O; q0(x)) from the class OMQ(1; 1; `) (remember that we have fixed arity n). The size of the program QSW is polynomially bounded in jQj since q0 has polynomially-many subtrees of Tq0 and O(jq0j`) Skolem witnesses (there are at most O(jq0j` j j nn) pairs of a Skolem witness s and its generating atom P (a)). It is readily seen that the function defined by (Gq) = jqj, for each q 2 Q, is a weight function for ( QSW; Gq0 (x)) with (Gq0 ) jQj. Moreover, by Lemma 5, d( QSW; Gq0 ) log (Gq0 )+1; also, w( QSW; Gq0 ) `+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; fP (a)g j= 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 ( QSW; Gq0 (x)) can be generated by an LLOGCFL-transducer. By Corollary 1, the obtained NDL-rewritings can be evaluated in LOGCFL. 8
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 [