An ontology language L is said to enjoy FO-rewritability if any conjunctive
query (CQ) q over any ontology T , given in L, can be transformed into an
FOformula q0 such that, for any data A, all answers to q over the knowledge base
(T ; A) can be found by querying q0 over A using a standard relational database
management system (RDBMS). Ontology languages with this property include
the OWL 2 QL pro le of OWL 2, which is based on description logics of the
DL-Lite family [
The idea of using languages with FO-rewritability for ontology-based data
access (OBDA) relies on the empirical fact that RDBMSs are usually very e cient
in practice. However, the rst rewritings of CQs over OWL 2 QL ontologies [
The aim of this paper is twofold. First, we investigate the worst-case size
of FO- and NDL-rewritings for CQs over OWL 2 QL ontologies. We distinguish
between `pure' rewritings, which can use the signature of the original query and
ontology as well as =, 6= (cf. [
PE-rewritings.
(3) Pure FO-rewritings can be superpolynomially more succinct than pure
PErewritings.
(4) Impure PE- and NDL-rewritings can always be made polynomial, and so
they are exponentially more succinct than pure PE- and NDL-rewritings,
respectively.
(1){(3) are proved by establishing connections between pure rewritings for CQs
over OWL 2 QL ontologies and circuits for monotone Boolean functions. In a
nutshell, we show that CQs and OWL 2 QL ontologies can encode such problems
as the existence of a k-clique in a graph with n vertices whose edges are given
by a single-element ABox. The polynomial PE-rewriting in (4) is similar to the
NDL-rewriting of [
Our second aim is to analyse the causes behind long rewritings and whether they occur in real-world queries and ontologies. As a result, we suggest some short rewritings that cover most practical cases.
Omitted proofs can be found in [
Queries over OWL 2 QL Ontologies The language of OWL 2 QL is de ned by the following grammar:5 R B C ::= ::= ::=
Pi ? B j j j
Pi ; Ai j 9R:B; 9R; where the Ai are concept names and the Pi are role names. An OWL 2 QL TBox, T , is a nite set of inclusions of the form B v C, R1 v R2, B1 u B2 v ? and R1 u R2 v ?. Note that concepts of the form 9R:B can only occur in the righthand side of concept inclusions. An ABox, A, is a nite set of assertions of the form Ak(ai) and Pk(ai; aj ), where ai, aj are individual names. T and A together form the knowledge base (KB) K = (T ; A). The semantics is de ned in the usual way, based on interpretations I = ( I ; I ) with domain I and interpretation function I . The set of individuals in A is denoted by ind(A); IA is the interpretation with domain ind(A) such that, for any concept or role E and any a ind(A), we have IA j= E(a) i E(a) 2 A. We write E1 vT E2 if T j= E1 v E2; and we set [E] = fE0 j E vT E0 and E0 vT Eg. 5 We do not consider data properties, attributes and role (ir)re exivity constraints.
A conjunctive query (CQ) q(x) is a formula 9y '(x; y), where ' is a conjunction of atoms of the form Ak(t1) and Pk(t1; t2), and each ti is a term (an individual or a variable from x, y). 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; then we write K j= q(a).
Query answering over OWL 2 QL KBs is based on the fact that, for any consistent KB K = (T ; A), there is an interpretation CK such that, for all CQs q(x) and a ind(A), we have K j= q(a) i CK j= q(a). The interpretation CK, called the canonical model of K, can be constructed as follows. For each pair [R]; [B] with 9R:B in T (we assume 9R is just a shorthand for 9R:>), we introduce a fresh symbol w[RB] and call it the witness for 9R:B. We write K j= C(w[RB]) if 9R vT C or B vT C. De ne a generating relation, ;, on the set of these witnesses together with ind(A) by taking: { a ; w[RB] if a 2 ind(A), [R] and [B] are vT -minimal such that K j= 9R:B(a) and there is no b 2 ind(A) with K j= R(a; b) ^ B(b); { w[R0B0] ; w[RB] if u ; w[R0B0], for some u, [R] and [B] are vT -minimal with
K j= 9R:B(w[R0B0]) and it is not the case that R0 vT R and K j= B(u). If a ; w[R1B1] ; ; w[RnBn], n 0, then we say that a generates the path aw[R1B1] w[RnBn]. Denote by pathK(a) the set of paths generated by a, and by tail( ) the last element in 2 pathK(a). CK is de ned by taking: CK = [ a2ind(A) pathK(a);
aCK = a; for a 2 ind(A); ACK = f 2
CK j K j= A(tail( ))g; P CK = f(a; b) 2 ind(A) f( ; f(
ind(A) j K j= P (a; b)g [
w[RB]) j tail( ) ; w[RB]; R vT P g [
w[RB]; ) j tail( ) ; w[RB]; R vT P g:
Theorem 1 ([
Given a CQ q(x) and a TBox T , a rst-order formula q0(x), possibly with = and 6=, is called an FO-rewriting for q(x) and T if, for any ABox A and any a ind(A), we have (T ; A) j= q(a) i IA j= q0(a). If q0 is an FO-rewriting of the form 9y '(x; y), where ' is built from atoms using only ^ and _, then we call q0(x) a positive existential rewriting for q(x) and T (or a PE-rewriting, for short). We say that q0 is pure if it does not contain constants that do not occur in q (such constants are interpreted by fresh individuals added to IA). The size jq0j of q0 is the number of symbols in q0.
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 (A1 ^ ^ Am ! A0); where each Ai is an atom of the form P (t1; : : : ; tl)
and each tj is either a variable from x or a constant. A0 is called the head of the
clause, and A1; : : : ; Am its body. All variables occurring 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. A nonrecursive Datalog query consists
of a nonrecursive Datalog program and a goal G, which is just a predicate.
A tuple a ind(A) is a certain answer to ( ; G) over A if ; A j= G(a). The
size j j of is the number of symbols in it. We distinguish between pure and
impure Datalog queries [
Given a CQ q(x) and an OWL 2 QL TBox T , a pure nonrecursive Datalog query ( ; G) is called a nonrecursive Datalog rewriting for q(x) and T (or an NDL-rewriting, for short) if, for any ABox A and any a ind(A), we have (T ; A) j= q(a) i ; A j= G(a). If does not contain constants that do not occur in q then we say that the NDL-rewriting ( ; G) is pure. 3
Query Rewritings and Boolean Circuits To establish results (1){(3) on the size of rewritings mentioned in the introduction, we show how the problem of constructing circuits that compute monotone Boolean functions can be reduced to the problem of nding pure FO- and NDLrewritings for CQs over OWL 2 QL ontologies.
Our reduction proceeds in three steps. First, we take any family f 1; f 2; : : : of
monotone Boolean functions in NP, where f n : f0; 1gn ! f0; 1g, a polynomial
p and a family C1; C2; : : : of polynomial-size circuits such that f n( ) = 1 i
Cn( ; ) = 1, for some 2 f0; 1gp(n). Using the Tseitin transformation [
= ( 1; : : : ; n) 2 f0; 1gn.
Let 'fn be 'fn for = (0; : : : ; 0). It should be clear that 'fn is obtained from 'fn by removing the clauses :xj for which the jth component of is 1.
The second step is to encode the 'fn by means of TBoxes Tfn and CQs qfn . Let p1; : : : ; pN be the propositional variables and C1; : : : ; Cd the clauses in 'fn . Then Tfn contains the following concept inclusions, for 1 i N , 1 j d: Ai 1 v 9P :Xi`; Zi;j v 9P:Zi 1;j; A0 u Ai v ?;
Xi` v Ai; for ` = 0; 1;
Xi0 v Zi;j if :pi 2 Cj;
Xi1 v Zi;j if pi 2 Cj; A0 u 9P v ?;
A0 u Zi;j v ?; if (i; j) 2= f(0; 1); : : : ; (0; n)g; and the CQ is de ned as follows:
h qfn = 9y 9z A0(y0) ^
N ^ P (yi; yi 1) ^ i=1 d ^ P (yN ; zN 1;j) ^ where y = (y0; : : : ; yN ) and z = (z0;1; : : : ; zN 1;1; : : : ; z0;d; : : : ; zN 1;d). The size of Tfn and qfn is O(jCnj2). Note that Tfn is acyclic and qfn is tree-shaped and has no answer variables. The canonical model C(Tfn ;fA0(a)g) of (Tfn ; fA0(a)g) and the query qfn are illustrated below.
C(Tfn ;fA0(a)g) qfn
Z0;1 a A0 Z0;2 y0
A0z0;1 Z0;1 Z0;2 z0;2
Z1;1 X11; A1 X10; A1
Z1;2 y1 z1;1 z1;2
X21; A2; Z2;1
X20; A2 X21; A2 X20; A2
Z2;2 y2 z2;1 z2;2 y3
X31; A3 X30; A3 X31; A3 X30; A3 X31; A3 X30; A3 X31; A3 X30; A3; Z3;2 For each = ( 1; : : : ; n) 2 f0; 1gn, we de ne the following ABox: A =
A0(a) [
Z0;j(a) j 1 j n and j = 1 : Lemma 2. (Tfn ; A ) j= qfn i 'fn is satis able, for 2 f0; 1gn.
To complete our reduction, we show that rewritings for qfn and Tfn can be turned into Boolean circuits computing f n.
Lemma 3. (i) Suppose q0fn is a pure FO- (PE-) rewriting for Tfn and qfn . Then there is a (monotone) Boolean formula fn computing f n with j fn j jq0fn j.
(ii) Suppose ( fn ; G) is a pure NDL-rewriting for Tfn and qfn . Then there is a monotone Boolean circuit Cfn computing f n with jCfn j j fn j.
The proof proceeds by eliminating quanti ers in the rewriting and replacing its predicates with propositional variables using the fact that, in ABoxes A , these predicates can only be true on the individual a. Lemmas 1 and 2 ensure that the resulting Boolean formula or circuit computes f n. The next lemma shows that circuits computing f n can be turned into pure rewritings for qfn and Tfn .
Lemma 4. (i) Suppose qn is an FO-sentence such that (Tfn ; A ) j= qfn i IA j= qn, for all 2 f0; 1gn. Then there exists a pure FO-rewriting q0n for qfn and Tfn with jq0nj jqnj + p(n), for a polynomial p.
(ii) Suppose ( n; G) is a pure NDL-query with a propositional goal G such that (Tfn ; A ) j= qfn i n; A j= G, for 2 f0; 1gn. Then there is a pure NDL-rewriting ( n0; G0) for qfn and Tfn with j n0j j nj+p(n), p a polynomial.
Now, results (1){(3) formulated in the introduction can be obtained by
applying Lemmas 1{4 to three concrete Boolean functions. For (1), we use the
function Cliquen;k of n(n 1)=2 variables eij , 1 i < j n, which returns
1 i the graph with vertices f1; : : : ; ng and edges ffi; jg j eij = 1g contains
a k-clique. A series of papers, started by Razborov's [
To show (2), we use the function Genn3 of n3 variables xijk, 1 i; j; k n,
de ned as follows. We say that 1 generates k n if either k = 1 or, for some
i and j such that xijk = 1, 1 generates both i and j. Genn3 (x111; : : : ; xnnn)
returns 1 i 1 generates n. It is clearly a monotone function computable by
polynomial-size monotone circuits. On the other hand, any monotone formula
computing Genn3 is of size at least 2n" , for some " > 0 [
For (3), we use the function Matching2n of n2 variables eij , 1 i; j
n, which returns 1 i there is a perfect matching in a bipartite graph G with
vertices fv11; : : : ; vn1; v12; : : : ; vn2g and edges ffvi1; vj g j eij = 1g, i.e., a subset E of
2
edges in G such that every node in G occurs exactly once in E. An exponential
lower bound 2 (n) for the size of monotone formulas computing this function
was obtained in [
The exponential bounds for the size of rewritings can be reduced to
polynomial by using two extra constants, say 0 and 1, which are included in the domain
of every IA (see [
Why are Pure Rewritings so Long? Let q(x) = 9y '(x; y) be a connected CQ and T a TBox. Let term q be the set of terms in q. Denote by CT the disjoint union of the canonical models for consistent (T ; fR(aRB; bRB); B(bRB)g), in which the generating relation is extended with aRB ; bRB. The RB-subtree of CT has root aRB and consists of the full subtree of CT with root bRB extended with the edge (aRB; bRB). We also need the formulas extC (x) =
_ A(x) _ AvT C
_ 9RvT C 9y R(x; y); extP (x; y) =
_ RvT P
R(x; y); for concepts C and role names P . Suppose CK j=a ', K = (T ; A), where a is an assignment of elements of CK to the variables in ' under which a(x) 2 ind(A) for all x 2 x. Consider an atom P (t; t0) 2 q with bound variables t, t0 and assume that a(t0) 2 ind(A), for some t0 2 term q. The assignment a can send t and t0 to four di erent locations in CK: (A) a(t); a(t0) 2 ind(A); (B) a(t) 2 ind(A), a(t0) 2= ind(A); (B ) a(t) 2= ind(A), a(t0) 2 ind(A); (O) a(t); a(t0) 2= ind(A). Let us see how these alternatives can be re ected in a rewriting. In case (A) we have CK j=a P (t; t0) i A j=a extP (t; t0). Case (B) is possible only if, for some concept 9R:B, we have a(t) ; w[RB], R vT P and the atoms of q `linked to' t0 can be mapped into the RB-subtree of CT . To illustrate, consider an example. Example 1. Let T and q be as in the picture below. The answer variable x must be mapped by a to an ABox element. However, y can be mapped either to an ABox element or to the point a(x) w[S B] provided that a(x) is an instance of 9S :B. In the latter case, we have two ways of mapping z: either to a(x) w[S B]w[SA0], in which case we must set a(v) = a(x) w[S B]w[SA0]w[T >], or to a(x), provided that a(x) is an instance of 9T . Thus we have two (partial) maps f and g from q into the S B-subtree of CT shown below.
T = f A v 9S :B; B v 9S:A0; q(x) = fS(y; x); S(y; z); T (z; v)g
A0 v 9T g q v T z S y S x f f f f
T
A0
S B S aS B g g g v T z S y S x q These observations motivate our key de nition. Given a pair (t; t0) of adjacent terms in q, a tree witness 6 for (t; t0) is a homomorphism f from the query qf = E(s) 2 q j s dom f; s 6 [t]f to the RB-subtree of CT , for some 9R:B, such that f (t) = aRB, dom f is the smallest set containing t, t0 for which s0 2 dom f whenever S(s; s0) 2 q with s 2 dom f n [t]f , and all s 2 dom f n [t]f are bound variables in q. Here f denotes the equivalence relation on dom f de ned by taking s f s0 i f (s) = f (s0) and [t]f the equivalence class of t. In Example 1, f and g are two tree witnesses for (x; y). Returning back to case (B), we can say now that there must exist a tree witness f for (t; t0) such that a(t) satis es the following tree-witness formula twf for f with f (t) = aRB: twf = ext9R:B(t) ^
^ (t = s) s2[t]f ^ ^
extE (s): Case (B ) is symmetric, and in case (O) there must exist S(s; s0) 2 q for which (B) holds, with P (t; t0) being `covered' by the tree witness for (s; s0).
This analysis suggests the following idea for a rewriting. We guess pairs of
adjacent terms (t; t0) in q that will be mapped to edges of the tree part of CK
6 A di erent notion of tree witness was used for DL-LitehNorn [
f x1
R y2
R
R y3 x4 g
C(T ;fA(a)g) aw[R>]
R
A a aw[R >]
R Clearly, there is a tree witness f for (x1; y2) with dom f = fx1; y2; y3g and [x1]f = fx1; y3g, and a tree witness g for (x4; y3) with dom g = fx4; y3; y2g and [x4]g = fx4; y2g. Although these tree witnesses cover the whole query q, they are only `realised,' say, in the canonical model C(T ;fA(a)g) (shown above on the right) under con icting maps: f sends x1, y3 to a and y2 to aw[R>], while g sends x4, y2 to a and y3 to aw[R >]; in fact, (T ; fA(a)g) 6j= q(a; a).
Tree witnesses f and g, for (t; t0) and (s; s0), respectively, are compatible if dom f \dom g [t]f \[s]g. If f and g are incompatible and neither dom f dom g nor dom g dom f , then we call f and g con icting (e.g., f and g in Example 2). A set of tree witnesses is called consistent if all pairs of tree witnesses in are compatible. Let qe(x) = detachedq _
_ 9y ^ twf ^ consistent f2 ^
extE(s) ;
E(s)2q s6 dom f; for all f2 where detachedq = ? if x 6= ;; otherwise it is a disjunction of the sentences 9x ext9R:B(x) such that there is a homomorphism from q to the RB-subtree of CT . The next theorem shows that qe is a pure PE-rewriting for q and T : Theorem 2. For all A and a
ind(A), we have (T ; A) j= q(a) i IA j= qe(a).
Example 3. Let q(x) = fRi(x; yi) j i ng and T = fAi v 9Ri j i ng. Each pair (x; yi) gives rise to one tree witness fi with twfi = Ai(x) _ 9y Ri(x; y), and qe = WN [0;n] 9y (Vi2N twfi ^ Vj2=N Rj(x; yj)).
The size of qe is O((nT ;q + 1)jqj jT j jqj2), where nT ;q is the number of distinct tree witnesses. Now, we observe that if (conf ) there are no con icting tree witnesses for q and T then qe can be transformed to the query
h qc(x) = detachedq _ 9y ^ (if q has no binary predicates then qc = qe).
^ extE(s) _ E(s)2q; s ft;t0g
_ twf i f is a tree witness t;t02dom f Theorem 3. If T and q satisfy (conf ) then, for any ABox A and a we have (T ; A) j= q(a) i IA j= qc(a). ind(A),
The size of qc is O(nT ;q jT j jqj2). So, if (conf ) holds and nT ;q is polynomial then qc is a polynomial pure PE-rewriting of q and T . For instance, the exponential qe of Example 3 reduces to polynomial qc = 9y Vi n(Ri(x; yi) _ twfi ). Note, however, that the CQs and TBoxes used in Section 3 generate exponentially many distinct tree witnesses.
We show now that, for a large class of CQs q and TBoxes T , all tree witnesses f for each (t; t0) in q (even if there are exponentially many of them) can be represented by a polynomial formula. Observe that each twf is determined by a concept 9R:B (such that the RB-subtree of CT contains the range of f ) and the equivalence relation f on dom f . As the number of concepts 9R:B is linear in jT j, the rewriting qc may be regarded polynomial if we show that all tree witnesses for each (t; t0) have the same equivalence relation. For example, let q(x) = fS(x; y); R(y; zi) j 1 i ng and T = fA v 9S; 9S v 9R:B1; 9S v 9R:B2g. There are 2n tree witnesses for (x; y), as each zi can be mapped either to a B1- or a B2-point in CT , and yet they all de ne the same equivalence relation and the same tree-witness formula ext9S (x).
We formalise this intuition in the following de nition. For a pair (t; t0) of adjacent terms in q, we call f = (dom f ; f ) a universal tree witness for (t; t0) if dom f is a subset of term q with t; t0 2 dom f and f is an equivalence relation on dom f such that qf = E(s) 2 q j s dom f ; s 6 [t]f = f is a tree-shaped query with root [t]f and, for every tree witness g for (t; t0), { dom g = dom f and there exists a homomorphism h : qf ! CT that preserves the distance from the root and g(s) = h([s]f ), for every s 2 dom f . A universal tree witness f for (t; t0) is not a tree witness in the sense of our original de nition, but rather a convenient structure representing all tree witnesses for (t; t0): we can merge the tree-witness formulas for (t; t0) into one formula twf = h _ ext9R:B(t)
i 9R:B2 f ^ ^ (t = s) ^
^ extE (s); where f is the set of concepts 9R:B such there is a homomorphism h from qf to the RB-subtree of CT with h([t]f ) = aRB.
We now identify a class of CQs and TBoxes for which a universal tree witness is unique (if exists) and can be constructed in time polynomial in jqj and jT j. Intuitively, for each tree witness f , we disallow situations in which CT and the quotient qf = f of qf simultaneously contain fragments of the form qf = f
T
S
CT
T T S
S We say that a role S is forward if u ; v for all (u; v) 2 SCT . If neither S nor its inverse S is forward then S is said to be a twisty role. A tree witness f for (t; t0) is called perfect if, for all T (s1; s2); S(s2; s3) 2 qf = f such that s2 6= [t]f and S is twisty, we have CT 6j= inv (T; S) ^ suc(T; S), where suc(T; S) = 9x; y; z (T (x; y) ^ S(y; z) ^ (x 6= z)); inv (T; S) = 9x; y (T (x; y) ^ S(y; x)): Lemma 5. There is a polynomial-time algorithm which, given q, T and a pair (t; t0), checks whether all tree witnesses for (t; t0) are perfect, and if this is the case, returns a unique universal tree witness f t;t0 for (t; t0).
Note that even though there may be exponentially many tree witnesses for (t; t0), the algorithm checks whether they all are perfect in polynomial time. We are now in a position to de ne our polynomial PE-rewriting qp for q and T : qp(x) = detachedq _ 9y ^
h Theorem 4. If all tree witnesses for q and T are perfect and condition (conf ) is satis ed then, for any ABox A and any a ind(A), we have (T ; A) j= q(a) i IA j= qp(a). Moreover, qp is constructed in time polynomial in jqj and jT j.
If T does not contain any twisty roles, then all tree witnesses in any CQ q over T are perfect. On the other hand, all examples of con icting tree witnesses above involve twisty roles. The following theorem shows that this is no accident: Theorem 5. Let T be an OWL 2 QL ontology without twisty roles. Then, for any CQ q, there are no con icting tree witnesses for q and T . Thus, qp is a pure PE-rewriting for q and T and it can be constructed in polynomial time.
Note that OWL 2 EL ontologies satisfy this condition, and so a polynomial
rewriting similar to qp can also be used for CQ answering over such ontologies
provided that the ABoxes are complete with respect to the ontologies [
As we saw in Section 3, pure PE- and NDL-rewritings of CQs over OWL 2 QL
ontologies are of exponential size in the worst case. The analysis in Section 4
showed that the length of a rewriting is related to the number of tree witnesses in
the query, which re ect how various parts of the query can be homomorphically
mapped to the intensional tree part of the canonical model. Thus, a rewriting
can be lengthy if the original query is su ciently long and the intensional part of
the canonical model for the ontology is su ciently complex. We proved that by
restricting the interaction between inverse roles and role inclusions in ontologies
and queries, we can guarantee transparent polynomial rewritings. Moreover, as
shown by a series of experiments [