This paper further investigates the succinctness landscape of query rewriting in OWL 2 QL. We clarify the worst-case size of positive existential (PE), non-recursive Datalog (NDL), and first-order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries up to bounded treewidth queries. More specifically, we establish a superpolynomial lower bound on the size of PE-rewritings that holds already for linear queries and TBoxes of depth 2. For NDL-rewritings, we show that polynomial-size rewritings always exist for tree-shaped queries with a bounded number of leaves (and arbitrary TBoxes), and for bounded treewidth queries and bounded depth TBoxes. Finally, we show that the succinctness problems concerning FO-rewritings are equivalent to well-known problems in Boolean circuit complexity. Along with known results, this yields a complete picture of the succinctness landscape for the considered classes of queries and TBoxes.
For several years now, conjunctive query (CQ) answering has been a major focus of
description logic (DL) research (cf. survey [19]), due to the growing interest in using
description logic ontologies to query data. Formally, the problem is to compute the
certain answers to a CQ q(x) over a knowledge base (T ; A), that is, the tuples of
individuals a that satisfy T ; A j= q(a). Much of the work on CQ answering focuses on
lightweight DLs of the DL-Lite family [
It is not difficult to see that exponential-size rewritings are unavoidable if rewritings
are given as UCQs (consider for instance the CQ q(x) = B1(x)^: : :^Bn(x) and TBox
fAi v Bi j 1 i ng). A natural (and non-trivial) question is whether an exponential
blowup can be avoided by moving to other standard query languages, like positive
existential (PE) queries, non-recursive datalog (NDL) queries, or first-order (FO-) queries4.
More generally, under what conditions can we ensure polynomial-size rewritings? A
first (negative) answer was given in [
While existing results go a fair ways towards understanding the succinctness
landscape of query rewriting in OWL 2 QL, a number of questions remain open:
– What happens if we consider tree-shaped queries and bounded depth TBoxes?
– What happens if we consider generalizations or restrictions of tree-shaped CQs?
In this paper, we address these questions by providing a complete picture of the
succinctness of rewritings for tree-shaped queries, their restriction to linear and bounded
branching queries (i.e. tree-shaped CQs with a bounded number of leaves), and their
generalization to bounded treewidth queries. More specifically, we establish a
superpolynomial lower bound on the size of PE-rewritings that holds already for linear
queries and TBoxes of depth 2. For NDL-rewritings, we show that polynomial-size
rewritings always exist for bounded branching queries (and arbitrary TBoxes), and for
bounded treewidth queries and bounded depth TBoxes. Finally, we show that the
succinctness problems concerning FO-rewritings are equivalent to well-known problems
in Boolean circuit complexity: NL=poly NC1 in the case of linear and bounded
branching queries, and SAC1 NC1 in the case of tree-shaped and bounded treewidth
queries and bounded depth TBoxes. Along with known results, this yields a complete
picture of the succinctness landscape for the considered classes of queries and TBoxes.
To prove our results, we establish tight connections between Boolean functions induced
by queries and TBoxes and the non-uniform complexity classes NL=poly and SAC1,
reusing and further extending the machinery developed in [
Many proofs have been omitted for lack of space. We invite the interested reader to
consult the long version [
OWL 2 QL In this paper, we use the simplified DL syntax of the OWL 2 QL profile [18]. As usual, we assume countably infinite, mutually disjoint sets NC, NR, and NI of concept names, role names, and individual names. Roles R and basic concepts B are defined by the grammar:
R ::= r j r
B ::=
A j 9R where A 2 NC and r 2 NR. We use NR to refer to the set of all roles.
A TBox (typically denoted T ) is a finite set of inclusions of the forms B1 v B2
B1 v :B2
R1 v R2
R1 v :R2 The signature of a TBox T , written sig(T ), is the set of concept and role names that appear in T . An ABox (typically denoted A) is a finite set of assertions the form A(a) or r(a; b), where A 2 NC, r 2 NR, and a; b 2 NI. The set of individual names in A is denoted Inds(A).
A TBox T and ABox A together form a knowledge base (KB) K = (T ; A). The
semantics of KBs is defined in the usual way based on interpretations I = ( I ; I ) [
9y '(x; y), where ' is a conjunction of atoms of the form A(z1) or r(z1; z2) with zi 2 x [ y. The free variables x are called answer variables. Note that we assume w.l.o.g. that CQs do not contain individual names, and where convenient, we regard a CQ as the set of its atoms. We use vars(q) (resp. avars(q)) to denote the set of variables (resp. answer variables) of q. The signature of q, denoted sig(q), is the set of concept and role names in q. To every CQ q, we associate the undirected graph Gq whose vertices are the variables of q, and which contains an edge fu; vg whenever q contains an atom r(u; v) or r(v; u). We call a CQ q tree-shaped if the graph Gq is a tree5.
A tuple a Inds(A) is a certain answer to q(x) over K = (T ; A) if I j= q(a) for all I j= K; in this case we write K j= q(a). By first-order semantics, I j= q(a) iff there is a mapping h : vars(q) ! I such that (i) h(z) 2 AI whenever A(z) 2 q, (ii) (h(z); h(z0)) 2 rI whenever r(z; z0) 2 q, and (iii) h maps avars(q) to aI . If the first two conditions are satisified, then h is a homomorphism from q to I, and we write h : q ! I. If (iii) also holds, then we write h : q(a) ! I.
To every ABox A, we associate the interpretation IA whose domain is Inds(A) and
whose interpretation function makes true precisely the assertions from A. We say that
an FO-formula q0(x) with free variables x and without constants is an FO-rewriting of
CQ q(x) and TBox T if, for any ABox A and any a Inds(A), we have T ; A j= q(a)
iff IA j= q0(a). If q0 is a positive existential formula (i.e. it only uses 9, ^, _), then
it is called a PE-rewriting of q and T . We also consider rewritings in the form of
nonrecursive Datalog queries. We remind the reader that a Datalog program (typically
denoted ) is a finite set of rules 8x ( 1 ^ ^ m ! 0), where each i is an atom
5 Tree-shaped conjunctive queries also go by the name of acyclic queries, cf. [
For R 2 fPE, NDL, FOg, we say that queries from Q and TBoxes from T have polysize R-rewritings if there exists a polynomial p such that every q 2 Q and T 2 T has a R-rewriting q0 with jq0j p(jqj + jT j).
Canonical model We recall that every consistent OWL 2 QL KB (T ; A) possesses a canonical model CT ;A with the property that T ; A j= q(a) iff CT ;A j= q(a), for every CQ q and tuple a Inds(A). The domain of CT ;A consists of all individual names from A and all sequences aR1R2 : : : Rn (n 1) such that – T ; A j= 9R1(a); – for every 1 i < n: T j= 9Ri v 9Ri+1 and T 6j= Ri v Ri+1.
Concept and role names are interpreted as follows:
ACT ;A = fa 2 Inds(A) j T ; A j= A(a)g [ fwR 2 CT ;A j T j= 9R v Ag rCT ;A = f(a; b) j r(a; b) 2 Ag [ f(w; wS) 2 CT ;A
CT ;A j T j= S v rg [ f(wS; w) 2
CT ;A
CT ;A j T j= S v r g Every individual name a 2 Inds(A) is interpreted as itself: aCT ;A = a.
We say that a TBox T is of depth ! if there is an ABox A such that CT ;A has an infinite domain; T is of depth d, 0 d < !, if d is the greatest number such that some CT ;A contains an element of the form aR1 : : : Rd. The depth of T can be computed in polynomial time, and if T is of finite depth, then its depth cannot exceed 2jT j. 3
In this section, we introduce different representations of Boolean functions that will
play an important role in our results. We assume that the reader is familiar with Boolean
circuits [
Non-deterministic branching programs (NBP) are another well-known model for
the representation of Boolean functions [
We recall hypergraph functions and programs from [
^ _
pv ^ ind. E0 E v2V n[E0 ^ pe : e2E0 (1) A hypergraph program HGP P consists of a hypergraph HP = (V; E) and a function lP that labels every vertex with 0, 1, pi or :pi (here the pi are propositional variables, distinct from the pv; pe above). An input for P is a valuation of the propositional variables in P ’s labels. We say that the hypergraph program P computes a Boolean function f in case, for any input , we have f ( ) = 1 if and only if there is an independent subset of E that covers all zeros—that is, contains all the vertices in V labelled with 0 under . A hypergraph program is monotone if there are no negated variables among its vertex labels. The size, jHj, of a hypergraph program H is the number of its vertices and hyperedges. Observe that each hypergraph program that is based upon the hypergraph H computes the Boolean function that is obtained from the hypergraph function fH by substituting vertex labels for vertex variables and 1 for edge variables. Conversely, it is not hard to construct for a given hypergraph H, a hypergraph program that computes fH . Sometimes it is convenient to consider hypergraph programs whose labels are conjunctions of variables and their negations, rather than single literals. It is not hard to see that this does not change the power of such programs. 3.2
The upper bounds in [
To every CQ q and TBox T , we can naturally associate the hypergraph whose vertices are the atoms of q and whose hyperedges are the sets qt, for tree witnesses t for q and T . We denote this hypergraph by Hq and call the corresponding function fHq the
T T tree witness hypergraph function of q and T . It is known that the circuit complexity of fHq provides an upper bound on the size of rewritings of q and T .
T
Theorem 1 (from [
If fHq is computed by a monotone Boolean circuit C then there is an NDL-rewriting of q andTT of size O(jCj jqj jT j).
Observe that fHq contains a variable pt for every tree witness t. For this reason, it can only be used tTo show polynomial upper bounds in cases where j Tq j is bounded polynomially in jqj and jT j. This motivates us to consider a variant of fHq : T f H0q =
T _
q independTent
^ %2qnq p% ^ ^ t2
^ z;z02t pz=z0 ^ _
^ pzR R2NR ; z2t t2 Tq [R] (2) where q = St qt. Intuitively, pz=z0 enforces that variables z and z0 are mapped to elements of CT ;A that begin by the same ABox individual; the variable pzR states that z is mapped to an element that begins by an individual a satisfying T ; A j= 9R(a).
We observe that the number of variables in f H0q is polynomially bounded in jqj and T jT j, but f H0q retains the same properties as fHq regarding upper bounds.
T T Theorem 2. Theorem 1 continues to hold if fHq is replaced by f H0q .
T T 3.3
In order to obtain lower bounds on the size of rewritings, it will prove convenient to associate to each pair (q; T ) a third function fqP;T that describes the result of evaluating q on single-individual ABoxes. Given Boolean vectors : NC \ (sig(T ) [ sig(q)) ! f0; 1g and : NR \ (sig(T ) [ sig(q)) ! f0; 1g, we let
A( ; ) = fA(a) j (A) = 1g [ fr(a; a) j (r) = 1g and set fqP;T ( ; ) = 1 iff T ; A( ; ) j= q(a), where a is a tuple of a’s of the required length. We call fqP;T the primitive evaluation function for q and T .
Theorem 3 (implicit in [
If ( ; G) is an NDL-rewriting of q and T , then fqP;T is computed by a monotone Boolean circuit C of size O(j j). 4
It is known from [
It is not hard to see that every linear query induces a tree witness hypergraph that is isomorphic to an interval hypergraph, i.e. a hypergraph H = (V; E) where V = f[i; i+ 1] j 1 i < ng for some finite n and E is a set of intervals of the form [i; j] = f[k; k + 1] j 1 k < jg where 1 i < j n. Since the hypergraph functions of interval hypergraphs can be computed by polynomial-size NBPs, the same holds for the tree witness hypergraph functions of linear queries. In fact, the following result shows that we can construct polysize NBPs not only for linear queries, but also for bounded branching queries: Theorem 4. Fix a constant ` > 1. Then there exists a polynomial p such that for every tree-shaped CQ q with at most ` leaves and every OWL 2 QL TBox T , there is an NBP of size at most p(jqj + jT j) that computes fHq .
T We next give a polynomial translation from NBPs into interval hypergraph programs, thereby establishing the polynomial equivalence of these formalisms: Theorem 5. Every function f that is computable by an NBP P is also computable by an interval hypergraph program of size polynomial in jP j.
To complete the chain, we show how to compute hypergraph functions for interval hypergraphs using primitive evaluation functions of linear CQs and TBoxes of depth 2. To every interval hypergraph H, we associate the linear CQ qH pictured below: ^ [i;i+1]2V qH = 9y
(ri(yi; yi0) ^ ri0(yi0; yi+1)): The TBox TH contains the following axioms (on the left) for each edge [i; j] 2 E: Bij v 9sij ; 9sij v 9s0ij ; s0ij v rk0; sij v ri; sij v r0 ;
j for every i s0ij v rk ; for every i < k
j k < j s013 s13 r10 r2
r20 r3 r1 r0 3 B13 To the right, we illustrate the canonical model generated by B13. Observe how the axioms ensure that the subquery of qH lying between y1 and y4 can be mapped onto it. Theorem 6. For every interval hypergraph H = (V; E) and for all : V ! f0; 1g and : E ! f0; 1g we have fH ( ; ) = 1 iff fqPH ;TH ( ) with defined as follows: (Bij ) = ([i; j]), (ri) = (ri0) = ([i; i + 1]), and (sij ) = (s0ij ) = 0. 4.2
We now apply the results from Section 4.1 to derive bounds on rewriting size. It is
known that there is a sequence fn of monotone Boolean functions that are computable
by polynomial-size monotone NBPs, but all monotone Boolean formulas computing fn
are of size n (log n) [
Theorem 7. There is a sequence of linear CQs qn and TBoxes Tn of depth 2, both of polysize in n, such that any PE-rewriting of qn and Tn is of size n (log n).
We obtain a positive result for NDL-rewritings using Theorems 1 and 4 and the fact that NBPs are representable as polynomial-size monotone circuits [22]. Theorem 8. Fix a constant ` > 1. Then all tree-shaped CQs with at most ` leaves and arbitrary TBoxes have polynomial-size NDL-rewritings.
Finally, we use Theorems 1,3, 5, and 6 to show that the existence of polysize FOrewritings is equivalent to the open problem of whether NL=poly NC1. Theorem 9. The following are equivalent: 1. There exist polysize FO-rewritings for all linear CQs and depth 2 TBoxes; 2. There exist polysize FO-rewritings for all tree-shaped CQs with at most ` leaves and arbitrary TBoxes (for any fixed `); 3. There exists a polynomial function p such that every NBP of size at most s is computable by a formula of size p(s). Equivalently, NL=poly NC1. 5
In Section 4, we gave bounds on the size of rewritings for restricted classes of
treeshaped CQs. In the present section, we consider arbitrary tree-shaped queries and their
natural generalization to bounded treewidth queries [
Polynomial image property Let T be an OWL 2 QL TBox, and let q be a CQ. Then the set Wq;T of relevant words for q and T consists of all words w of length at most jT j+jqj such that there exists an ABox A that is consistent with T and a homomorphism h : q ! CT ;A whose image contains an element of the form aw. The length bound is motivated by the following well-known fact: Lemma 1. If A is consistent with T and T ; A j= q(a), then there is some h : q(a) ! CT ;A whose image is contained in faw j a 2 Inds(A); w 2 Wq;T g.
We say that a class T of TBoxes has the polynomial image property if there is a polynomial p such that for every TBox T 2 T and every CQ q, jWq;T j p(jT j + jqj). Observe that if d 0 is fixed, then the class of TBoxes of depth at most d has the polynomial image property. Another relevant class of TBoxes with this property is the class of TBoxes that do not contain role inclusions. 5.1
As in Section 4, our first step will be to relate Boolean functions induced by the query and TBox with hypergraph programs. The main difference is that in lieu of interval hypergraph programs, we will use tree hypergraph programs.
To formally define tree hypergraph programs, we must first introduce some definitions related to trees. Given a tree T with vertices u and v, the interval hu; vi is the set of edges that appear on the simple path connecting u and v. If v1; : : : ; vk are vertices of T , then the generalized interval hv1; : : : ; vki is defined as the union of intervals hvi; vj i over all pairs (i; j). A hypergraph H = (VH ; EH ) is a tree hypergraph if there is a tree T = (VT ; ET ) such that VH = ET and every hyperedge in EH is a generalized interval of T . A hypergraph program is a tree hypergraph program (TreeHGP) if it is based on a tree hypergraph.
From f H0q to TreeHGP. We show how to construct a TreeHGP that computes f H0q ,
T T
given a TBox T , a CQ q, and a tree decomposition (T; ) of Gq of width t. We
may suppose w.l.o.g. that T contains at most (2jqj 1)2 nodes, cf. [
The basic idea underlying the construction is as follows: for each node N in the tree decomposition of q, we select an abstract description of the way the variables in (N ) are homomorphically mapped into the canonical model, and we check that the selected descriptions respect the subqueries of each node and are consistent with each other. Formally, these abstract descriptions are given by the set t(q; T ) consisting of all t-tuples w = (w1; : : : ; wt) of words from Wq;T . Intuitively, the words in w specify, for each variable x in (N ), the path of roles that lead from the ABox to the image of x in the canonical model. We say that w 2 t(q; T ) is consistent with a node N in T if: – if A( i(N )) 2 q, then either w[i] = " or w[i] = w0R and 9R – if r( i(N ); j (N )) 2 q, then one of the following holds: w[i] = w[j] = " w[j] = w[i] R with R vT r w[i] = w[j] R with R vT r vT A We call a pair of tuples (w1; w2) compatible with the pair of nodes (N1; N2) if: –
i(N1) = j (N2) implies that w1[i] = w2[j] We assume that the elements of t(q; T ) are numbered from 1 to M , and use i to refer to the i-th element. We define a tree T 0 that replaces each edge fNi; Nj g in T by the following sequence of edges: fNi; ui1j g; fui1j ; vi1j g; fvi1j ; ui2j g; fui2j ; vi2j g; : : : fuiMj ; viMj gfviMj ; vjMi g fujMi ; vjMi g : : : fuj2i; vj2ig; fvj1i; uj2ig; fuj1i; vj1ig; fNj ; uj1ig The desired TreeHGP (Hq;T ; lq;T ) is based upon T 0 and contains the hyperedges: – Eik = huikj1 ; : : : ; uikjn i, for every k 2 t(q; T ) that is consistent with Ni, where
Nj1 ; : : : ; Njn are the neighbours of Ni – Eikjm = hvikj ; vjmi i, for every pair of tuples ( k; m) that is compatible with (Ni; Nj ) Vertices of the hypergraph (i.e. the edges in T 0) are labeled by lq;T as follows: – every edge of the form fNi; ui1j g, fvi`j ; ui`j+1g, or fviMj ; vjMi g is labelled 0 – every edge fui`j ; vi`j g with ` = w is labelled by the conjunction of: p%, if vars(%) (Ni) and g(Ni) 2 vars(%) implies w[g] = " pzR, if vars(%) = fzg (Ni), z = g(Ni), and w[g] = Rw0 pzR, pzR0 , and pz=z0 , if vars(%) = fz; z0g (Ni), z = g(Ni), z0 = and either w[g] = Rw0 or w[g0] = Rw0 g0 (Ni), If q has treewidth t, then jHq;T j
8 jqj2 jWq;T j2t.
Theorem 10. For every TBox T and CQ q, the TreeHGP (Hq;T ; lq;T ) computes f H0q . T From TreeHGP to fqP;T . Consider a tree hypergraph H = (V; E) that is based upon the tree T whose vertices are v1; : : : ; vn. Let T # be the directed tree obtained from T by fixing v1 as the root and orienting edges away from v1.
We wish to construct a tree-shaped query qH and TBox TH of depth 2 whose primitive evaluation function fqPH ;TH can be used to compute fH . The construction generalizes the one from the preceding section for linear queries. The query qH is obtained by doubling the edges in T #: The TBox TH is defined as the union of Te over all hyperedges e 2 E. Consider some hyperedge e = hvi1 ; : : : ; vim i 2 E, and suppose w.l.o.g. that vi1 is the vertex in e that is highest in T #. Then Te contains Be v 9se, 9se v 9s0e, and the axioms: se v ri1;k se v rj0`;i` s0e v rj;k s0e v rj0;k if fvi1 ; vkg 2 e if 1 < `
n and (vj` ; vi` ) 2 T # (so, fvj` ; vi` g 2 e) if fvj ; vkg 2 e, (vj ; vk) 2 T #, and vj 6= vi1 if fvj ; vkg 2 e, (vj ; vk) 2 T #, and vk 6= vi` for any 1 < ` m Observe that both qH and TH are of polynomial size in jHj.
Theorem 11. For every tree hypergraph H = (V; E) and for all : V ! f0; 1g and : E ! f0; 1g, fH ( ; ) = 1 iff fqPH ;TH ( ) = 1 where is defined as follows: (Be) = (e), (rij ) = (ri0j ) = (fvi; vj g), and (se) = (s0e) = 0.
To characterize the power of tree hypergraph programs, we consider semi-unbounded fan-in circuits in which NOT gates are applied only to the inputs, AND gates have fan-in 2, and OR gates have unbounded fan-in. The complexity class SAC1 [27] is defined by considering circuits of this type having polynomial size and logarithmic depth; SAC1 is the non-uniform analog of the class LOGCFL of all languages logspacereducible to context-free languages [26].
We consider semi-unbounded fan-in circuits of size and depth log , where is
a parameter, and show that they are polynomially equivalent to TreeHGP by providing
reductions in both directions (details can be found in [
Theorem 12. There exist polynomial functions p and p0 such that: – Every semi-unbounded fan-in circuit of size at most s and depth at most log is computable by a TreeHGP of size p( ). – Every TreeHGP of size is computable by semi-unbounded fan-in circuit of size at most p0( ) and depth at most log p0( ). 5.3
Theorems 10 and 12 together show us how to construct a polysize monotone SAC1 circuit that computes f H0q . Thus, by applying Theorem 2, we obtain:
T Theorem 13. Fix a constant t > 0, and let T be a class of OWL 2 QL TBoxes with the polynomial image property. Then all CQs of treewidth at most t and TBoxes in T have polynomial-size NDL-rewritings.
In the case of FO-rewritings, we can show that the existence of polysize rewritings corresponds to the open question of whether SAC1 NC1.
Theorem 14. The following are equivalent: 1. There exist polysize FO-rewritings for all tree-shaped CQs and depth 2 TBoxes; 2. There exist polysize FO-rewritings for all CQs of treewidth at most t and TBoxes from a class T with the polynomial image property (for any fixed t); 3. There exists a polynomial function p such that every semi-unbounded fan-in circuit of size at most and depth at most log is computable by a formula of size p( ).
Equivalently, SAC1 NC1. 6
In this paper, we filled some gaps in the succinctness landscape for query rewriting in
OWL 2 QL by providing new bounds on the worst-case rewriting size for various forms
of tree-like queries. In doing so, we closed one of the open questions from [
In future work, we plan to consider additional dimensions of the succinctness landscape. For example, all existing lower bounds rely on sequences (qn; Tn) in which the number of roles in qn and Tn grows with n. Moreover, Tn often contains a large number of role inclusions. Thus, an interesting and practically relevant problem is to explore the impact of restricting the number of roles and/or the use of role inclusions. Acknowledgments. This work was partially supported by ANR grant 12-JS02-007-01, Russian Foundation for Basic Research and the programme “Leading Scientific Schools”. 18. B. Motik, B. Cuenca Grau, I. Horrocks, Z. Wu, A. Fokoue, and C. Lutz. OWL 2 Web Ontology Language profiles. W3C Recommendation, 11 December 2012. Available at http://www.w3.org/TR/owl2-profiles/. 19. M. Ortiz and M. Simkus. Reasoning and query answering in description logics. In Reasoning
Web, volume 7487 of Lecture Notes in Computer Science, pages 1–53. Springer, 2012. 20. H. Pe´rez-Urbina, B. Motik, and I. Horrocks. A comparison of query rewriting techniques for DL-Lite. In Proc. of the 22nd Int. Workshop on Description Logics (DL 2009), volume 477.
CEUR-WS, 2009. 21. H. Pe´rez-Urbina, E. Rodr´ıguez-D´ıaz, M. Grove, G. Konstantinidis, and E. Sirin. Evaluation of query rewriting approaches for OWL 2. In Proc. of SSWS+HPCSW 2012, volume 943.
CEUR-WS, 2012. 22. A. Razborov. Lower bounds for deterministic and nondeterministic branching programs. In Proc. of the 8th Int. Symposium on Fundamentals of Computation Theory (FCT’91), volume 529 of Lecture Notes in Computer Science, pages 47–60. Springer, 1991. 23. M. Rodr´ıguez-Muro, R. Kontchakov, and M. Zakharyaschev. Ontology-based data access: Ontop of databases. In Proc. of the 12th Int. Semantic Web Conf. (ISWC 2013), volume 8218 of Lecture Notes in Computer Science, pages 558–573. Springer, 2013. 24. R. Rosati. Prexto: Query rewriting under extensional constraints in DL-Lite. In Proc. of the 9th Extended Semantic Web Conf. (EWSC 2012), volume 7295 of Lecture Notes in Computer Science, pages 360–374. Springer, 2012. 25. R. Rosati and A. Almatelli. Improving query answering over DL-Lite ontologies. In Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2010), pages 290–300. AAAI Press, 2010. 26. H. Venkateswaran. Properties that characterize LOGCFL. J. Computer and System Sciences, 43(2):380–404, 1991. 27. H. Vollmer. Introduction to circuit complexity - a uniform approach. Texts in theoretical computer science. Springer, 1999. 28. M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of the 7th Int. Conf. on Very Large Data Bases (VLDB’81), pages 82–94. IEEE Computer Society, 1981.