We investigate the size of rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of a new hypergraph formalism for computing Boolean functions. Both positive and negative results are obtained. All conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; treeshaped queries have polynomial-size positive existential rewritings; however, for some queries and ontologies of depth 1, positive existential rewritings can only be of superpolynomial size. Both positive existential and nonrecursive datalog rewritings of conjunctive queries and ontologies of depth 2 su er an exponential blowup in the worst case, while rst-order rewritings can grow superpolynomially unless NP P=poly.
This paper is a continuation of the series [
The problem we address in this paper is whether the depth of TBoxes (that is, the maximal depth of the canonical models with single-individual ABoxes) has any impact on the size of rewritings. (The TBoxes Tn mentioned above are of depth n.) In particular, what happens if we restrict the depth of TBoxes to 1 or 2? (PE-rewritings over TBoxes of depth 0 are trivially polynomial.) The obtained results are summarised below: (1) For any CQ and TBox of depth 1, there is a polynomial-size NDL-rewriting. (2) PE-rewritings of some CQs and TBoxes of depth 1 are of superpolynomial size. (3) All tree-shaped CQs and TBoxes of depth 1 have polynomial-size PErewritings. (4) For TBoxes of depth 2, both NDL- and PE-rewritings can su er an exponential blowup, while FO-rewritings can su er a superpolynomial blowup (unless NP P=poly).
We begin by observing that the tree-witness PE-rewritings, representing possible
homomorphisms of subqueries of a given CQ to the canonical models with one
ABox individual, give rise to a class of monotone Boolean functions associated
with hypergraphs and called hypergraph functions. In particular, hypergraphs H
of degree 2 (every vertex in which belongs to at most 2 hyperedges) correspond
to Boolean CQs qH and TBoxes TH of depth 1 such that answering qH over TH
and single-individual ABoxes amounts to computing the hypergraph function
for H. We show then that representing Boolean functions as hypergraphs of
degree 2 is polynomially equivalent to representing them by nondeterministic
branching programs (NBP) [
OWL 2 QL and the Tree-Witness Rewriting In this paper, we use the following (simpli ed) syntax of OWL 2 QL. It contains individual names ai, concept names Ai, and role names Pi (i 1). Roles R and basic concepts B are de ned by the grammar:
R ::=
Pi j
Pi ;
B ::= ? j
Ai j 9R: A TBox, T , is a nite set of inclusions of the form
B1 v B2;
B1 u B2 v ?;
R1 v R2;
R1 u R2 v ?:
An ABox, A, is a nite set of atoms of the form Ak(ai) or Pk(ai; aj). The set
of individual names in A is denoted by ind(A). T and A together form the
knowledge base (KB) K = (T ; A). The semantics for OWL 2 QL is de ned in the
usual way based on interpretations I = ( I ; I ) [
For every role name R in T , we take two fresh concept names AR, AR and add to T the axioms AR 9R and AR 9R . We say that the resulting TBox is in normal form and assume, without loss of generality, that every TBox in this paper is in normal form. We denote by vT the subsumption relation induced by T and write S1 vT S2 if T j= S1 v S2, where S1, S2 are both concepts or roles. We say that an ABox A is H-complete with respect to T in case R2(a; b) 2 A
A2(a) 2 A if if
R1(a; b) 2 A and R1 vT R2;
A1(a) 2 A and A1 vT A2; for all concept names Ai (including the AR) and roles Ri. We write R(a; b) 2 A for P (a; b) 2 A if R = P and for P (b; a) if R = P ; also, we write AR(a) 2 A if R(a; b) 2 A, for some b.
A conjunctive query (CQ) q(x) is a formula 9y '(x; y), where ' is a conjunction of atoms of the form Ak(z1) or Pk(z1; z2) with zi 2 x [ y (without loss of generality, we assume that CQs do not contain constants). A tuple a ind(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). If x = ;, the CQ q is called Boolean; a certain answer to such a q over K is `yes' if K j= q and `no' otherwise. Where convenient, we regard a CQ q as the set of its atoms.
Suppose T is a TBox and q(x) a CQ. An FO-formula q0(x) with free variables x and without constants is an FO-rewriting of q and T over H-complete ABoxes if, for any H-complete (with respect to T ) ABox A and any a ind(A), we have (T ; A) j= q(a) i A j= q0(a). If an FO-rewriting q0 is a positive existential formula (with only 9, ^, _), we call it 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, , is a nite set of Horn clauses 8x ( 1 ^ ^ m ! 0), where each i is an atom of the form P (x1; : : : ; xl) with xi 2 x. The atom 0 is called the head of the clause, and 1; : : : ; m its body. All variables in the head must also occur in the body. A predicate P depends on a predicate Q in if contains a clause whose head is P and whose body contains Q. is called nonrecursive if this dependence relation for is acyclic. For a nonrecursive Datalog program and an atom q0(x), we say that ( ; q0) is an NDL-rewriting of q(x) and T over H-complete ABoxes in case (T ; A) j= q(a) i ; A j= q0(a), for any H-complete ABox A and any a ind(A). Rewritings over arbitrary ABoxes are de ned by dropping the condition that the ABoxes are H-complete. They can be obtained from rewritings over H-complete ABoxes at the price of a polynomial blowup.
Recall [
CTR1 (a1) a1 : AR1
CTR1 (a2)
CTR2 (a2) P1; P2
P2 a2 : AR1 ; AR2 a3 We say that T is of depth ! if at least one of CTR(a) is in nite; T is of depth d, 0 d < !, if there is a chain of the form aR0w1 : : : wd 1Rd 1wd (for distinct wi) in the trees CTR(a), R a role in T , but there is no such chain of greater length.
By de nition, CT ;A j= q(a) i there is a homomorphism h : q(a) ! CT ;A. Such a homomorphism h splits q into the subquery mapped by h to ind(A) and the subquery mapped to the trees CTR(a). We can think of a rewriting of q and T as listing possible splits of q into such subqueries.
Suppose q0 is a subset of the atoms of q and there is a homomorphism thr :=q0h!1(CaTR)(aan),dfolertstoi mbee ath,esurcehmtahinaitnhg smetaposf a(ellxaisntsewnteiralvlayrqiaubalnestiinedq)0 vtoaraia.bLleest in q0. We call the pair t = (tr; ti) a tree witness for q and T generated by R if ti 6= ; and q0 is a minimal subset of q such that, for any y 2 ti, every atom in q containing y belongs to q0. In this case, we denote q0 by qt. By de nition, qt =
S(z) 2 q j z tr [ ti and z 6 tr : Note that the same tree witness t = (tr; ti) can be generated by di erent roles R. We denote the set of all such roles by t and de ne the formula _ twt = 9z AR(z) ^ ^ (x = z) : x2tr (1) Tree witnesses t and t0 are consistent if qt \ qt0 = ;. Each consistent set of tree witnesses (in which any pair of distinct tree witnesses is consistent) determines a subquery q of q that comprises all atoms of qt, for t 2 . The subquery q is to be mapped to the CTR(a), whereas the remainder, q nq , obtained by removing the atoms of q from q, is mapped to ind(A). The following PE-formula qtw is called the tree-witness rewriting of q and T over H-complete ABoxes: qtw(x) =
_ 9y (q n q ) ^ consistent ^ twt : t2 (2) Example 1. Consider the KB K = (T ; fA(a)g), where
T = fA v 9R; A v 9R ; AR 9R; AR 9R g; and the CQ q(x1; x4) = fR(x1; y2); R(y3; y2); R(y3; x4)g shown in the picture below alongside the canonical model CT ;A (with AR and AR omitted). t1 x1
y2 R
R y3
R x4 t2
CT ;A R a
A
R There are two tree witnesses for q and T : t1 = (tr1; ti1) generated by R and t2 = (tr2; ti2) generated by R , with tr1 = fx1; y3g; tr2 = fy2; x4g; ti1 = fy2g; ti2 = fy3g; twt1 = 9z (AR(z) ^ (x1 = z) ^ (y3 = z)); twt2 = 9z (AR (z) ^ (x4 = z) ^ (y2 = z)): We have qt1 = fR(x1; y2); R(y3; y2)g and qt2 = fR(y3; y2); R(y3; x4)g, so t1 and t2 are inconsistent. Thus, we obtain the following tree-witness rewriting: qtw(x1; x4) = 9y2; y3 (R(x1; y2) ^ R(y3; y2) ^ R(y3; x4)) _
(R(y3; x4) ^ twt1 ) _ (R(x1; y2) ^ twt2 ) : Theorem 1. For any ABox A that is H-complete with respect to T and any a ind(A), we have CT ;A j= q(a) i A j= qtw(a). 3
The tree-witness rewriting qtw above gives rise to monotone Boolean functions
we call hypergraph functions. For the complexity theory of monotone Boolean
functions the reader is referred to [
Let H = (V; E) be a hypergraph with vertices v 2 V and hyperedges e 2 E, E 2V . We call a subset X E independent if e \ e0 = ;, for any distinct e; e0 2 X. The set of vertices that occur in the hyperedges of X is denoted by VX . With each vertex v 2 V and each hyperedge e 2 E we associate propositional variables pv and pe, respectively. The hypergraph function fH for H is given by the Boolean formula fH =
_ X independent v2V nVX ^ pv ^ ^ pe : e2X (3) The rewriting qtw of q and T de nes a hypergraph whose vertices are the atoms of q and hyperedges are the sets qt, for tree witnesses t for q and T . We denote this hypergraph by Hq . The formula (3) de ning fHq is basically the same as
T T the rewriting (2) with the atoms S(z) in q and tree-witness formulas twt treated as propositional variables. We denote these variables by pS(z) and pt (rather than pv and pe), respectively.
Example 2. Consider again the CQ q and TBox T from Example 1. The hypergraph HTq and its hypergraph function fHq are shown below:
T
R(y3; y2) t1
t2 R(x1; y2)
R(y3; x4) fHq = (pR(x1;y2) ^ pR(y3;y2) ^ pR(y3;x4)) _
T (pR(y3;x4) ^ pt1 ) _ (pR(x1;y2) ^ pt2 ).
Suppose the function fHq is computed by some Boolean formula Hq . Consider the FO-formula bHq oTbtained by replacing each pS(z) in Hq witTh S(z),
T T each pt with twt, and adding the pre x 9y. By comparing (3) and (2), we see that the resulting FO-formula is a rewriting of q and T over H-complete ABoxes.
Thus, the problem of constructing short rewritings is reducible to the problem
of nding short Boolean formulas computing the hypergraph functions.
Hypergraphs of degree 2, in which every vertex belongs to at most two hyperedges,
are of particular interest to us because (i ) TBoxes of depth 1 have hypergraphs
of degree 2, and (ii ) their hypergraph functions are the functions computed
by nondeterministic branching programs (NBPs), also known as
switching-andrecti er networks [
We remind the reader (see, e.g., [
Given n and k as above, let Hn;k be a hypergraph with the vertices
Informally, the vertices vi of Hn;k represent a k-clique in a given graph with n vertices. The vertices wjj0 represent the edges of the complete graph with n vertices; they can be turned `on' or `o ' by means of the Boolean variables ejj0 . The vertex ujj0 together with the hyperedge hjj0 represent the `half' of the edge connecting j and j0 that is adjacent to j. The hyperedges gij correspond to the choice of the jth vertex of the graph as the ith element of the clique. For example, the hypergraph H4;2 looks as follows:
Denote by v, u, w, g and h the vectors of the vi, ujj0 , wjj0 , gij and hjj0 , respectively. Thus, we can think of the hypergraph function for Hn;k as having the form fHn;k (v; u; w; g; h).
Theorem 3. Cliquen;k(e) = fHn;k (0; 1; e; 1; 1), for all e 2 f0; 1gn(n 1)=2. 4
The Size of Rewritings over TBoxes of Depth 1 and 2 We use these complexity-theoretic results on the hypergraph functions to investigate the size of rewritings over TBoxes of depth 1 and 2.
Theorem 4. For any CQ q and any TBox T of depth 1, there is an NDLrewriting of q and T of polynomial size.
The proof of this theorem is based on the following facts. First, for any CQ q and TBox T of depth 1, the hypergraph HTq is of degree 2, and the number of distinct tree witnesses for q and T does not exceed the number of variables in q. Second, each hypergraph function given by a hypergraph of degree 2 is computed by a polynomial-size monotone NBP, and so by a polynomial size monotone Boolean circuit. Thus, it remains to use Theorem 2.
Theorem 5. There is a sequence of CQs qn and TBoxes Tn of depth 1 such that any PE-rewriting of qn and Tn (over H-complete ABoxes) is of size 2 (log2 n).
In the proof of this result, we use a sequence of Boolean functions fn(x)
that are computable by polynomial-size monotone NBPs, but any monotone
Boolean formulas computing fn are of size 2 (log2 n). (For example, Grigni
and Sipser [
Now, we call a hypergraph H representable if there are a CQ qH and a TBox TH such that H is isomorphic to HqH . To show that any hypergraph of degree
TH 2 is representable, take any such H = (V; E) and assume, to simplify notation, that any vertex in H belongs to exactly 2 hyperedges, so H comes with two xed maps i1; i2 : V ! E such that i1(v) 6= i2(v), v 2 i1(v) and v 2 i2(v), for any v 2 V . For every e 2 E, we take an individual variable ze and denote by z the vector of all such variables. For every v 2 V , we take a role name Rv and set: qH = 9z ^ Rv(zi1(v); zi2(v)); v2V For every hyperedge e 2 E, let Ae be a concept name and Se a role name. Consider the TBox TH with the following inclusions, for e 2 E:
Ae
9Se; Se v Rv ; Se v Rv; for v 2 V with i1(v) = e; for v 2 V with i2(v) = e: We claim that H is isomorphic to HTqHH and illustrate the proof by an example. Example 3. Let H = (V; E) with V = fv1; v2; v3; v4g and E = fe1; e2; e3g, where e1 = fv1; v2; v3g, e2 = fv3; v4g, e3 = fv1; v2; v4g. Suppose also that i1 : v1 7! e1; v2 7! e3; v3 7! e1; v4 7! e2; i2 : v1 7! e3; v2 7! e1; v3 7! e2; v4 7! e3: The hypergraph H is shown below, where each vertex vi is represented by an edge: i1(vi) is indicated by the circle-shaped end of the edge and i2(vi) by the diamond-shaped one; the hyperedges ej are shown as large grey squares: ypergraph h tree witness te1
Ae1 qH = 9ze1 ze2 ze3 Rv1 (ze1 ; ze3 ) ^ Rv2 (ze3 ; ze1 ) ^ Rv3 (ze1 ; ze2 ) ^ Rv4 (ze2 ; ze3 ) and the TBox TH contains the following inclusions:
Ae1 Ae2 Ae3 9Se1 ; 9Se2 ; 9Se3 ;
Se1 v Rv1 ; Se2 v Rv3 ; Se3 v Rv1 ;
Se1 v Rv2 ; Se2 v Rv4 ; Se3 v Rv2 ;
Se1 v Rv3 ;
Se3 v Rv4 :
Se1 (a) is shown on the right-hand side of the picture above.
The canonical model CTH We observe now that each variable ze uniquely determines the tree witness te fwoiltlohwqsteth=atfRHv(iszii1s(ovm); zoir2p(hv)i)c jtov 2HTqeHHg;. qte and qte0 are consistent i e \ e0 6= ;. It jq0nj
j nj
We take the sequence of CQs qn and TBoxes Tn associated with the
hypergraphs of degree 2 for the sequence fn of Boolean functions chosen above.
Then we show that a PE-rewriting q0n of qn and Tn can be transformed (using
quanti er elimination over single-individual ABoxes [
Theorem 6. There exists a sequence of CQs qn and TBoxes Tn of depth 2 such that any PE- and NDL-rewriting of qn and Tn is of exponential size, while any F O-rewriting of qn and Tn is of superpolynomial size (unless NP P=poly). To prove this theorem, we show that the hypergraphs Hn;k computing Cliquen;k qn;k for suitable qn;k and Tn;k, and then use are representable as subgraphs of HTn;k quanti er elimination over single-individual ABoxes as above.
The CQ qn;k and the TBox Tn;k of polynomial size (in n) that `compute' Cliquen;k are de ned as follows. The Boolean CQ qn;k contains the atoms: Tij (vi; zij ); Pjj0 (wjj0 ; xjj0 ); Pj0j (wjj0 ; xj0j ); Q(ujj0 ; xjj0 ); U (ujj0 ; zij ); for 1 for 1 for 1 i The picture below illustrates the fragments of qn;k centred around zij and xjj0 : c0ij cij j 0 i R j i R Aij A0ij Bjj0 Bj0 j0
zij j i T vi j0 i T 9Rij ; 9Ri0j ; 9Sjj0 ; 9Sj0j0 ; xjj0 0 j j P
Q ujj0 U d0jj0 0 j 0 j
S djj0 0 j j
S Rij v Q ;
9Rij v A0ij zij for all i
9Sjj0 v Bj0 j0 ; U
U for j0 6= j ujj0 Q xjj0 wjj0 j 0 j
P xj0j Rij v Tij0 ; Ri0j v Tij ; Sjj0 v Pj0j ; Sj0j0 v Pjj0 ; Rij v U ; Ri0j v U; Sjj0 v U ; Sj0j0 v Q:
for j06=j for i06=i
The TBox Tn;k mimics the arrangement of atoms in the layers depicted above and contains the following inclusions: for 1 i k and 1 j 6= j0 n, The picture above also shows the elements and `generating roles' of the models CTRni;jk (a) and CTSnjj;k0 (a). The horizontal dashed lines show possible ways of embedding the fragments of qn;k into the respective canonical models. These embeddings give rise to the following tree witnesses for qn;k and Tn;k: { tij = (trij ; tiij ) generated by Rij , for 1 i k and 1 j n, where trij = fzij0 ; xjj0 j 1 j0 n; j0 6= jg [ fzi0j j 1 i0 k; i 6= i0g; tiij = fvi; zij g [ fujj0 j 1 j0 n; j0 6= jg; { sjj0 = (srjj0 ; sijj0 ) and sj0j = (srj0j ; sij0j ), generated by Sjj0 and Sj0j , where sjj0 = fxj0j g [ fzij j 1 r sijj0 = fwjj0 ; ujj0 ; xjj0 g; i kg; sj0j = fxjj0 g [ fzij0 j 1 r sij0j = fwjj0 ; uj0j ; xj0j g: i kg;
The tree witnesses tij , sjj0 and sj0j are uniquely determined by their most remote (from the root) variable, zij , xjj0 and xj0j , respectively, and correspond to the hyperedges f ij , hjj0 , hj0j of the hypergraph Hn;k; their internal variables of the form vi, wjj0 and ujj0 correspond to the vertices in the respective hyperedge. 5
Tree-Shaped Queries and TBoxes of Depth 1 In this section, we consider one particular equivalent transformation of the treewitness rewriting. Let q be a CQ and z a subset of the set of existentially quanti ed variables in q. By a z-partition of q we understand any disjoint sets of atoms q1; : : : ; qk, called z-components, that cover q and are such that if, for i = 1; 2, each of Si(zi) 2 q contains a variable zi 2 z and z1 is connected to z2 by a path coming through variables in z only, then both Si(zi) are in the same component. Note that, for any z-partition of q, every tree witness for 9z q and any T is contained in some z-component of the partition.
Given a TBox T and a CQ q(x) = 9y '(x; y), we de ne a CQ qy(x) = 9y qy, where qz is computed recursively as follows: we take a z-partition q1; : : : ; qk of q, take zj to be the set of the variables in z that occur in qj , for each 1 j k, (z1; : : : ; zk form a partition of z) and set qz = q1z1 ^ ^ qkzk , where 8>(qj )zjnfzjg qjzj = < >:qj ;
_ _ twt ^ (qj n qt)zjn(tr[ti) ; if there is zj 2 zj ; tree witness t for 9zj qj and T with zj2ti otherwise.
i twt1 ^ R(y3; x4) : h qy(x1; x4) = 9y2; y3
R(x1; y2) ^
R(y3; y2) ^ R(y3; x4) _ twt2 _ Note that qz depends on the choice of q1; : : : ; qk and zj 2 zj , which can be arbitrary. Intuitively, the rst disjunct of qz re ects the situation where zj is mapped to an ABox element; so we treat zj as a free variable when rewriting qj . The other disjuncts re ect the case when zj is mapped to the non-ABox part of the canonical model, in which case zj belongs to the internal part ti of a tree witness t = (tr; ti) for 9zj qj and T . As the variables in tr must be mapped to ABox elements, this leaves the set qj n qt of atoms with existentially quanti ed zj n (tr [ ti) for further rewriting (this set of variables does not contain zj ). Theorem 7. For any ABox A that is H-complete with respect to T and any a ind(A), we have CT ;A j= q(a) i A j= qy(a).
Example 4. Take q and T from Example 1. The only fy2; y3g-component of q is q. Then we pick, say y2, and obtain qfy2;y3g = qfy3g _ twt1 ^ R(y3; x4); . Now, q has two fy3g-components, fR(x1; y2)g and q1 = fR(y3; y2); R(y3; x4)g. The former gives R(x1; y2), while in the latter we have to pick y3 and obtain q1; _ twt2 , assuming that the empty set of atoms is >. This gives the rewriting:
A CQ q is said to be tree-shaped if its primal graph (whose vertices are the variables in q and edges are pairs ft; t0g such that R(t; t0) 2 q) is a tree. In each component qj of a tree-shaped CQs q, we can choose a variable zj that splits it in half. More formally, we have the following: Proposition 1. For any tree T = (V; E), there is a vertex v 2 V such that each connected component obtained by removing v from T contains jV j=2 vertices.
By Proposition 1, any tree-shaped CQ can be split into components, each of which contains less than a half of the existentially quanti ed variables of the CQ. By applying this argument recursively and using the fact that, if a TBox T is of depth 1 then, for any variable z in q, the number of tree witnesses t = (tr; ti) for q and T with z 2 ti does not exceed 2, we obtain our nal result: Theorem 8. Any tree-shaped CQ over any TBox of depth 1 has a polynomial PE-rewriting.