We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded-leaf tree-shaped conjunctive queries, and (iii) arbitrary ontologies and bounded-leaf tree-shaped conjunctive queries, one can construct and evaluate nonrecursive datalog rewritings by, respectively, LOGCFL, NL and LOGCFL algorithms, which matches the optimal combined complexity.
Ontology-based data access (OBDA) via query rewriting [
In this paper, we consider OMQs in these three classes and construct NDL-rewritings
that are theoretically optimal in the sense that the rewriting and evaluation can be
carried out by algorithms of optimal combined complexity, that is, from the complexity
classes LOGCFL, NL and LOGCFL, respectively. Such algorithms are known to be space
efficient and highly parallelisable. We compared our optimal NDL rewritings with those
produced by query rewriting engines Clipper [
The full version is available at http://tinyurl.com/LogNDL-DL. (a) 1 2 h tp3 e d .y. . g o l tod n o arb.
poly NDL, but no poly PE poly FO iff NL/poly NC1 poly 4-PE poly PE poly NDL no poly PE poly FO
iff NL/poly
NC1 2 . . . ` number of leaves poly NDL no poly PE poly FO
iff LOGCFL/poly NC1 no poly NDL & PE trees 2 . . . bound. arb.
treewidth
1C
N
y
l/
o
p
P
N
iff
lpoy FO
(b)
1
An ABox, A, is a finite set of atoms of the form Ak(ai) or Pk(ai; aj ). We denote by
ind(A) the set of individual names in A, and by RT the set of role names occurring in T
and their inverses. We use A B for A v B and B v A. The semantics for OWL 2 QL
is defined in the usual way based on interpretations I = ( I ; I ) [
For every role R 2 RT , we take a fresh concept name AR and add AR 9R to T . The resulting TBox is said to be in normal form, and we assume, without loss of generality, that all our TBoxes are in normal form. The subsumption relation induced by T is denoted by vT : we write S1 vT S2 if T j= S1 v S2, where S1, S2 are both either concepts or roles. We write R(a; b) 2 A if P (a; b) 2 A and R = P , or P (b; a) 2 A and R = P ; we also write (9R)(a) 2 A if R(a; b) 2 A for some b. An ABox A is called H-complete with respect to T in case P (a; b) 2 A if R(a; b) 2 A; for roles P and R with R vT P;
A(a) 2 A if B(a) 2 A; for a concept name A and basic concept B with B vT A:
A conjunctive query (CQ) q(x) is a formula 9y '(x; y), where ' is a conjunction of atoms Ak(z1) or Pk(z1; z2) with zi 2 x [ y (without loss of generality, we assume that CQs do not contain constants). We denote by var(q) the variables x [ y of q and by avar(q) the answer variables x. An ontology-mediated query (OMQ) is a pair Q(x) = (T ; q(x)), where T is a TBox and q(x) a CQ. A tuple a in ind(A) is a certain answer to Q(x) over an ABox A if I j= q(a) for all models I of T and A; in this case we write T ; A j= q(a). If x = ;, then a certain answer to Q over A is ‘yes’ if T ; A j= q and ‘no’ otherwise. We often regard a CQ q as the set of its atoms.
Every consistent OWL 2 QL knowledge base (KB) (T ; A) has a canonical model
CT ;A with the property that T ; A j= q(a) iff CT ;A j= q(a), for any CQ q and any a
in ind(A). Thus, CQ answering in OWL 2 QL amounts to finding a homomorphism
from the given CQ into the canonical model. Informally, CT ;A is obtained from A by
repeatedly applying the axioms in T , introducing fresh elements as needed to serve as
witnesses for the existential quantifiers. According to the standard construction (cf. [
A datalog program, , is a finite set of Horn clauses 8z ( 0 1 ^ ^ m), where each i is an atom S(y) with y z or an equality (z = z0) with z; z0 2 z. (As usual, when writing clauses, we omit 8z.) The atom 0 is the head of the clause, and 1; : : : ; m its body. All variables in the head must also 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 S depends on S0 in if has a clause with S in the head and S0 in the body; is a nonrecursive datalog (NDL) program if the (directed) dependence graph of the dependence relation is acyclic.
An NDL query is a pair ( ; G(x)), where is an NDL program and G(x) a predicate. A tuple a in ind(A) is an answer to ( ; G(x)) over an ABox A if G(a) holds in the first-order model with domain ind(A) obtained by closing A under the clauses in ; in this case we write ; A j= G(a). The problem of checking whether a is an answer to ( ; G(x)) over A is called the query evaluation problem. The arity of is the maximal arity, r( ), of predicates in . The depth of ( ; G(x)) is the length, d( ; G), of the longest directed path in the dependence graph for starting from G. NDL queries are equivalent if they have exactly the same answers over any ABox.
An NDL query ( ; G(x)) is an NDL-rewriting of an OMQ Q(x) = (T ; q(x)) over H-complete ABoxes in case T ; A j= q(a) iff ; A j= G(a), for any H-complete ABox A and any tuple a in ind(A). Rewritings over arbitrary ABoxes are defined by dropping the condition that the ABoxes are H-complete. Let ( ; G(x)) be an NDL-rewriting of Q(x) over H-complete ABoxes. Denote by the result of replacing each predicate S in with a fresh predicate S and adding the clauses A (x) B0(x), for B vT A, and P (x; y) R0(x; y), for R vT P , where B0(x) and R0(x; y) are the obvious first-order translations of B and R (for example, B0(x) = 9y R(x; y) if B = 9R). It is easy to see that ( ; G (x)) is an NDL-rewriting of Q(x) over arbitrary ABoxes.
It is well-known [
We call an NDL query ( ; G(x1; : : : ; xn)) ordered if each of its IDB predicates S comes with fixed variables xi1 ; : : : ; xik (1 i1 < < ik n), called the parameters of S, such that (i) every occurrence of S in is of the form S(y1; : : : ; ym; xi1 ; : : : ; xik ), (ii) the xi are the parameters of G, and (iii) if x0 are all the parameters in the body of a clause, then the head has x0 among its parameters. The width w( ; G) of a ordered ( ; G) is the maximal number of non-parameter variables in a clause of . All our NDL-rewritings in Secs. 4–6 are ordered, so we now only consider ordered NDL queries.
NL and LOGCFL Fragments of Nonrecursive Datalog
In this section, we identify two classes of (ordered) NDL queries with the evaluation
problem in the complexity classes NL and LOGCFL for combined complexity. Recall [
Theorem 1. Fix some w > 0. The combined complexity of evaluating linear NDL queries of width at most w is NL-complete.
Proof. Let ( ; G(x)) be a linear NDL query. Deciding whether ; A j= G(a) is reducible to finding a path to G(a) from a certain set X in the grounding graph G( ; A; a) constructed as follows. The vertices of the graph are the ground atoms obtained by taking an IDB atom from , replacing each of its parameters by the corresponding constant from a, and replacing each non-parameter variable by some constant from A. The graph has an edge from S(c) to S0(c0) iff the grounding of contains a clause S0(c0) S(c) ^ E1(e1) ^ ^ Ek(ek) with Ej (ej ) 2 A, for 1 j k (we assume that (c = c) 2 A). The set X consists of all vertices S(c) with IDB predicates S being of in-degree 0 in the dependency graph of for which there is a clause S(c) E1(e1) ^ ^ Ek(ek) in the grounding of with Ej (ej ) 2 A (1 j k). Bounding the width of ( ; G) ensures that G( ; A; a) is of polynomial size and can be constructed by a deterministic Turing machine with separate input, write-once output and logarithmic-size working tapes. q
The transformation of NDL-rewritings over H-complete ABoxes into rewritings for arbitrary ABoxes in Section 2 does not preserve linearity. However, we can still show that it suffices to consider the H-complete case: Lemma 2. For any fixed w > 0, there is an LNL-transducer that, given a linear NDLrewriting of an OMQ Q(x) over H-complete ABoxes that is of width at most w, computes a linear NDL-rewriting of Q(x) over arbitrary ABoxes whose width is at most w + 1.
The complexity class LOGCFL can be defined in terms of nondeterministic auxiliary
pushdown automata (NAuxPDAs) [
We call an NDL query ( ; G) skinny if the body of any clause in has 2 atoms. Lemma 3. For any skinny NDL query ( ; G(x)) and ABox A, query evaluation can be done by an NAuxPDA in space log j j + w( ; G) log jAj and time 2O(d( ;G)). Proof. Let Aa be the set of ground clauses obtained by first replacing each parameter in by the corresponding constant from a, and then performing the standard grounding of using the constants from A. Consider the monotone Boolean circuit C( ; A; a) constructed as follows. The output of C( ; A; a) is G(a). For every atom occurring in the head of a clause in Aa , we take an OR-gate whose output is and inputs are the bodies of the clauses with head ; for every such body, we take an AND-gate whose inputs are the atoms in the body. We set an input gate to 1 iff 2 A. Clearly, C( ; A; a) is a semi-unbounded fan-in circuit (where OR-gates have arbitrarily many inputs, and ANDgates two inputs) with O(j j jAjw( ;G)) gates and depth O(d( ; G)). It is known that the nonuniform analog of LOGCFL can be defined using families of semi-unbounded fanin circuits of polynomial size and logarithmic depth. Moreover, there is an algorithm that, given such a circuit C, computes the output using an NAuxPDA in logarithmic space in the size of C and exponential time in the depth of C [20, pp. 392–397]. Observing that C( ; A; a) can be computed by a deterministic logspace Turing machine, we conclude that the query evaluation problem can be solved by an NAuxPDA in space log j j + w( ; G) log jAj and time 2O(d( ;G)). q
A function from the predicate names in to N is a weight function for an NDLquery ( ; G(x)) if (P ) > 0, for any IDB P in , and (P ) (Q1) + + (Qn), for any P (z) Q1(z1) ^ ^ Qn(zn) in .
Lemma 4. If ( ; G(x)) has a weight function , then it is equivalent to a skinny NDL query ( 0; G(x)) such that j 0j is polynomial in j j, d( 0; G) d( ; G) + log (G) and w( 0; G) w( ; G).
Proof. The proof is by induction on d( ; G). If d( ; G) = 0, we take 0 = .
Suppose contains a clause of the form G(z) P1(z1) ^ ^ Pk(zk) and, for
each 1 j k, we have an NDL query ( P0j ; Pj) which is equivalent to ( ; Pj) and
such that
d( P0j ; Pj)
d( Pj ; Pj) + log (Pj)
d( ; G)
1 + log (Pj):
(1)
We construct the Huffman tree [
maxjfdlog( (G)= (Pj))e + d( P0j ; Pj)g maxjflog( (G)= (Pj)) + d( ; G) + log (Pj)g = log (G) + d( ; G): Let 0 be the result of applying this transformation to each clause in with head G(z). It is readily seen that ( 0; G) is as required; in particular, j 0j = O(j j2). q Theorem 5. Fix c 1, w 1 and a polynomial p. Query evaluation for NDL queries ( ; G(x)) with a weight function such that (G) p(j j), w( ; G) w and d( ; G) c log (G) is in LOGCFL for combined complexity.
Proof. By Lemma 4, ( ; G) is equivalent to a skinny NDL query ( 0; G0) with j 0j polynomial in j j, w( 0; G) w, and d( 0; G0) (c + 1) log (G). By Lemma 3, query evaluation for ( 0; G0) over A is solved by an NAuxPDA in space log j 0j + w( 0; G) log jAj = O(log j j + log jAj) and time 2O(d( 0;G0)) 2O(log (G)) = ( (G))O(1) p0(j j), for some polynomial p0. q Corollary 6. Suppose there is an algorithm that, given any OMQ Q(x) from some class C, constructs its NDL-rewriting ( ; G(x)) over H-complete ABoxes having a weight function with (G) jQj and d( ; G) c log (G), and such that w( ; G) w and jQj j j p(jQj), for some fixed constants c, w and polynomial p. Then the evaluation problem for the NDL-rewritings ( ; G (x)) of the OMQs in C over arbitrary ABoxes (defined in Section 2) is in LOGCFL for combined complexity. 4
Bounded Treewidth CQs and Bounded-Depth TBoxes With every CQ q, we associate its Gaifman graph G whose vertices are the variables of q and edges are the pairs fu; vg such that P (u; v) 2 q, for some P . We call q tree-shaped if G is a tree; q is connected if the graph G is connected. A tree decomposition of an undirected graph G = (V; E) is a pair (T; ), where T is an (undirected) tree and a function from the set of nodes of T to 2V such that the following conditions hold: – for every v 2 V , there exists a node t with v 2 (t); – for every e 2 E, there exists a node t with e (t); – for every v 2 V , the nodes ft j v 2 (t)g induce a connected subtree of T . We call the set (t) V a bag for t. The width of (T; ) is maxt2T j (t)j 1. The treewidth of a graph G is the minimum width over all tree decompositions of G. The treewidth of a CQ is the treewidth of its Gaifman graph.
Example 7. Consider CQ q(x0; x7) depicted below (black nodes are answer variables):
R S R R S R R x0 x1 x2 x3 x4 x5 x6 x7 Its natural tree decomposition of treewidth 1 is based on the the chain T of 7 vertices, which are represented as bags as follows:
R x1 x0 x2 S x1
R x3 x2
R x4 x3
S x5 x4
R x6 x5
R x7 x6
Fix a connected CQ q(x) and a tree decomposition (T; ) of its Gaifman graph G = (V; E). Let D be a subtree of T . The size of D is the number of nodes in it. We call a node t of D boundary if T has an edge ft; t0g with t0 2= D, and let the degree deg(D) of D be the number of its boundary nodes. Note that T itself is the only subtree of T of degree 0. 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.
Lemma 8 ([
If deg(D) = 2, then there is a node t splitting D into subtrees of size degree 2 and, possibly, one subtree of size < m 1 and degree 1.
If deg(D) 1, then there is t splitting D into subtrees of size m=2 and degree 2.
In Example 7, t splits T into T1 and T2 depicted below:
R x1 x0 x2 S x1
T1
R x3 x2 x4 t R x3
S x5 x4
T2
R x6 x5
R x7 x6
We define recursively a set sub(T ) of subtrees of T , a binary relation on sub(T ) and a function on sub(T ) indicating the splitting node. We begin by adding T to sub(T ). Take D 2 sub(T ) that has not been split yet. If D is of size 1 then let (D) be the only node of D. Otherwise, by Lemma 8, we find a node t in D that splits it into D1; : : : ; Dk. We set (D) = t and, for each 1 i k, add Di to sub(T ) and set Di D; then, we apply the procedure recursively to each of D1; : : : ; Dk. In Example 7 with t splitting T , we have (T ) = t, T1 T and T2 T .
For each D 2 sub(T ), we recursively define a set of atoms qD by taking qD =
S(v) 2 q j v ( (D)) [ [
D0 D qD0 : By the definition of tree decomposition, qT = q. Denote by xD the subset of avar(q) that occur in qD. In our running example, xT = fx0; x7g, xT1 = fx0g and xT2 = fx7g. Denote by @D the union of all (t) \ (t0) for a boundary node t of D and its unique neighbour t0 in T outside D. In our example, @T = ;, @T1 = fx3g and @T2 = fx4g.
Let T be a TBox of finite depth k. A type is a partial map w from V to WT ; its domain is denoted by dom(w). By " we denote the unique partial type with dom(") = ;. We use types to represent how variables are mapped into CT ;A, with w(u) = w indicating that u is mapped to an element of the form aw (for some a 2 ind(A)), and with w(u) = " that u is mapped to an ABox individual. We say that a type w is compatible with a bag t if, for all u; v 2 (t) \ dom(w), we have – if v 2 avar(q), then w(v) = "; – if A(v) 2 q, then either w(v) = " or w(v) = wR with 9R vT A; – if R(v; u) 2 q, then w(v) = w(u) = ", or w(u) = w(v)R0 with R0 vT R, or w(v) = w(u)R0 with R0 vT R .
In the sequel, we abuse notation and use sets of variables in place of sequences assuming that they are ordered in some (fixed) way. For example, we use xD for a tuple of variables in the set xD (ordered in some way). Also, given a tuple a in ind(A) of length jxDj and x 2 xD, we write a(x) to refer to the element of a that corresponds to x (that is, to the component of the tuple with the same index).
Let Q be an NDL program that, for any D 2 sub(T ), types w and s such that dom(w) = @D, dom(s) = ( (D)), s is compatible with (D) and agrees with w on their common domain, contains the clause ^
D0 D
G(Ds0[w) @D0 (@D0; xD0 ); (2) where xD are the parameters of predicate GDw, (s [ w) @D0 is the restriction1 of the union s [ w of s and w to @D0, and Ats is defined as follows: Ats = ^ A(u) ^ ^ R(u; v) ^ ^ (u = v) ^ ^ AS (u): (3) A(u)2q s(u)="
R(u;v)2q s(u)=s(v)="
R(u;v)2q s(u)6=" or s(v)6=" s(u)=Sw0 for some w0 The first two conjunctions in Ats ensure that atoms all of whose variables are assigned " are present in the ABox. The third conjunction ensures that if one of the variables in a role atom is not mapped to ", then the images of the variables share the same initial individual. Finally, atoms in the final conjunction ensure that if a variable is to be mapped to aSw0, then the individual a satisfies 9S (so aSw0 is part of the domain of CT ;A). Example 9. Now we fix an ontology T with the following axioms:
A 9P;
P v S;
P v R ;
B 9Q;
Q v R;
Q v S : Since (t) = fx3; x4g, there are only three types compatible with t: s1 : x3 7! "; x4 7! "; s2 : x3 7! P; x4 7! " and s3 : x3 7! "; x4 7! Q: So, Ats1 = R(x3; x4), Ats2 = A(x3) ^ (x3 = x4), Ats3 = B(x4) ^ (x3 = x4). Thus, predicate G"T is defined by the following clauses, for s1, s2 and s3, respectively: G"T (x0; x7) G"T (x0; x7) G"T (x0; x7)
GxT317!"(x3; x0) ^ R(x3; x4) ^ GxT427!"(x4; x7); GxT317!P (x3; x0) ^ A(x3) ^ (x3 = x4) ^ GxT427!"(x4; x7);
GxT317!"(x3; x0) ^ B(x4) ^ (x3 = x4) ^ GxT427!Q(x4; x7):
on sub(T ), we show that ( Q; G"T ) is a rewriting of Q(x).
Lemma 10. For any ABox A, any D 2 sub(T ), any type w with dom(w) = @D, any b 2 ind(A)j@Dj and a 2 ind(A)jxDj, we have Q; A j= GDw(b; a) iff there is a homomorphism h : qD ! CT ;A such that h(x) = a(x); for x 2 xD; and
h(v) = b(v)w(v); for v 2 @D:
Fix now k and t, and consider the class of OMQs Q(x) = (T ; q(x)) with T of
depth k and q of treewidth t. Let T be a tree decomposition of q of treewidth t.
We take the following weight function: (GDw) = jDj. Clearly, (G"T ) jQj. By
Lemma 8, d( Q; G"T ) 2 log jT j = 2 log (G"T ) 2 log jQj. Since jsub(T )j jT j2
and there are at most jT j2tk options for w, there are polynomially many predicates GDw
and so, Q is of polynomial size. Thus, by Corollary 6, the obtained NDL-rewriting over
arbitrary ABoxes can be evaluated in LOGCFL. Finally, we note that a tree decomposition
of treewidth t can be computed using an LLOGCFL-transducer [
Bounded-Leaf CQs and Bounded-Depth TBoxes We next consider OMQs with tree-shaped CQs in which both the depth of the ontology and the number of leaves in the CQ are bounded. Let T be a TBox of finite depth k, and let q(x) be a tree-shaped CQ with at most ` leaves. Fix one of the variables of q as root, and let M be the maximal distance to a leaf from the root. For n M , let zn denote the set of all variables of q at distance n from the root; clearly, jznj `. We call the zn slices of q and observe that they satisfy the following: for every R(u; v) 2 q with u 6= v, there exists 0 n < M such that either u 2 zn and v 2 zn+1 or u 2 zn+1 and v 2 zn. For 0 n M , we denote by qn(z9n; xn) the query consisting of all atoms S(u) of q such that u Sn m M zm, where xn = var(qn) \ x and z9n = zn n x.
By type of a slice zn, we mean a total map w from zn to WT . Analogously to Section 4, we define what it means for a type (or pair of types) to be compatible with a slice (pair of adjacent slices). We call w locally compatible with zn if for every z 2 zn: – if z 2 avar(q), then w(z) = "; – if A(z) 2 q, then either w(z) = " or w(z) = wR with 9R – if R(z; z) 2 q, then w(z) = ". vT A; If w; s are types for zn and zn+1 respectively, then we call (w; s) compatible with (zn; zn+1) if w is locally compatible with zn, s is locally compatible with zn+1, and for every atom R(zn; zn+1) 2 q, one of the following holds: (i) w(zn) = s(zn+1) = ", (ii) s(zn+1) = w(zn)R0 with R0 vT R, or (iii) w(zn) = s(zn+1)R0 with R0 vT R .
Consider the NDL program Q0 defined as follows. For every 0 n < M and every pair of types (w; s) that is compatible with (zn; zn+1), we include the clause: Pnw(z9n; xn)
Atw[s(zn; zn+1) ^ Pns+1(z9n+1; xn+1); where xn are the parameters of Pnw and Atw[s(zn; zn+1) is the conjunction of atoms (3), as defined in Section 4, for the union w [ s of types w and s. For every type w locally compatible with zM , we include the clause:
PMw (z9M ; xM )
Atw(zM ): (Recall that zM is a disjoint union of zM and xM .) We use G, with parameters x, as 9 the goal predicate and include G(x) P0w(z0; x) for every predicate P0w(z0; x0) occurring in the head of one of the preceding clauses.
The following lemma (which is proved by induction) is the key step in showing that ( Q0; G(x)) is a rewriting of (T ; q) over H-complete ABoxes: Lemma 11. For any H-complete ABox A, any 0 b 2 ind(A)jz9nj and any a 2 ind(A)jxnj, we have homomorphism h : qn ! CT ;A such that n M , any predicate Pnw, any Q0; A j= Pnw(b; a) iff there is a h(x) = a(x); for x 2 xn; and
n h(z) = b(z)w(z); for z 2 z9 : (4)
It should be clear that Q0 is a linear NDL program of width at most 2`. Moreover, when ` and k are bounded by fixed constants, it takes only logarithmic space to store a type w, which allows us to show that Q0 can be computed by an LNL-transducer. We can apply Lemma 2 to obtain an NDL rewriting for arbitrary ABoxes, and then use Theorem 1 to conclude that the resulting program can be evaluated in NL.
Bounded-Leaf CQs and Arbitrary TBoxes
For OMQs with bounded-leaf CQs and ontologies of unbounded depth, our rewriting
utilises the notion of tree witness [
S(z) 2 q j z tr [ ti and z 6 tr : If qt is a minimal subset of q for which there is a homomorphism h : qt ! CTAR(a) such that tr = h 1(a) and qt contains every atom of q with at least one variable from ti, then we call t = (tr; ti) a tree witness for Q generated by R. Note that the same tree witness t = (tr; ti) can be generated by different roles R. By q n t we denote the query obtained from q by removing the atoms in qt and having x [ tr as answer variables, and for every v 2 var(q), we let TWQ(v) denote the set of all tree witnesses t for Q such that v 2 ti.
The logarithmic depth NDL-rewriting for bounded-leaf queries and ontologies of unbounded depth is based upon the following observation.
Lemma 12. Every tree T of size m has a node splitting it into subtrees of size m=2.
We will use repeated applications of this lemma to decompose the input CQ into smaller and smaller subqueries. Formally, for every tree-shaped CQ q, we use vq to denote a vertex in the Gaifman graph G of q that satisfies the condition of Lemma 12. Then, starting from an OMQ Q0 = (T ; q0(x0)), we define SQQ0 as the smallest set of queries that contains q0(x0) and is such that for every q(z) 2 SQQ0 with jvar(q)j > 1, the following queries also belong to SQQ0 : – for every ui that is adjacent to vq in G: the query qi(zi) consisting of all role atoms linking vq and ui, as well as all atoms whose variables cannot reach vq in G without passing by ui, and with zi equal to (z \ var(qi)) [ fvqg; – for every t 2 TWQ0 (vq) with tr 6= ;: the queries qt (zt1); : : : ; qtmt (ztmt ) correspond1 ing to the connected components of q n t, with zti equal to var(qti) \ avar(q n t). The NDL program Q00 0 uses IDB predicates Pq, for q 2 SQQ0 , with arity javar(q)j and parameters var(q) \ x. For each q(z) 2 SQQ0 with jvar(q)j > 1, we include the clause ^ A(vq) A(vq)2q
^ ^
R(vq; vq) R(vq;vq)2q ^
^ 1 i n
Pqi (zi); Pq(z)
Pq(z) where q1(z1); : : : ; qn(zn) are the subqueries induced by the neighbours of vq in G. We also include, for every t 2 TWQ(vq) with tr 6= ; and role R generating t, the clause ^ (u = u0) ^
^ AR(u) ^ u;u02tr u2tr
^ 1 i mt
Pqti (zti) where qt1; : : : ; qtmt are the connected components of q n t. For every q 2 SQQ0 with jvar(q)j = 1, we include the clause Pq(z) q. Finally, if q0 is Boolean, we include clauses Pq0 A(x) for all concept names A such that T ; fA(a)g j= q0.
The program Q00 0 is inspired by a similar construction from [
100 Lemma 13. For any tree-shaped OMQ Q0(x) = (T ; q0(x)), any q(z) 2 SQQ0 , any H-complete ABox A, and any tuple a in ind(A), Q00 0 ; A j= Pq(a) iff there exists a homomorphism h : q ! CT ;A such that h(z) = a.
Now fix ` > 1, and consider the class of OMQs Q(x) = (T ; q(x)) with tree-shaped
q(x) having at most ` leaves. The size of Q00 is polynomially bounded in jQj, since
bounded-leaf CQs have polynomially many tree witnesses and also polynomially many
tree-shaped subCQs. It is readily seen that the function defined by setting (Pq0 ) = jq0j
is a weight function for ( Q00 ; Pq) such that (Pq) jQj. Moreover, by Lemma 12,
d( ; G) log (Pq) + 1. We can thus apply Corollary 6 to conclude that the obtained
NDL-rewritings can be evaluated in LOGCFL. 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 12, and it is in LOGCFL to decide whether T ; fA(a)g j= q0 [
As shown above, for three important classes of OMQs, NDL-rewritings can be
constructed and evaluated by theoretically optimal NL and LOGCFL algorithms. To see
whether these rewritings are viable in practice, we generated three sequences of OMQs
with the ontology from Example 9 and linear CQs of up to 15 atoms as in Example 7. We
compared our NL and LOGCFL rewritings from Sections 5 and 4 (called LIN and LOG)
with those produced by Clipper [
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 25 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
We evaluated the rewritings over a few randomly generated ABoxes using off-the-shelf
datalog engine RDFox [