We discuss the parameterised complexity of answering tree-shaped ontology-mediated queries (OMQs) in OWL 2 QL under various restrictions on their ontologies and conjunctive queries (CQs). In particular, we construct an ontology T such that answering OMQs (T ; q) with tree-shaped CQs q is W[1]hard if the number of leaves in q is regarded as the parameter. The number of leaves has previously been identified as an important characteristic of CQs as bounding it leads to tractable OMQ answering. Our result shows that treating it as a parameter does not make the problem fixed-parameter tractable, even for a fixed ontology.
Problem: decide whether T ; A j= q.
What is the parameterised complexity of a similar problem leaves-TREEOMQ, which takes the number of leaves in q as the parameter? Or what if we fix an ontology T in TREEOMQ and consider the problem TREEOMQ[T ]? Note that this problem reflects a typical ontology-based data access scenario, where the users are provided with a fixed ontology designed by a domain expert. Furthermore, we can consider the leafparameterisation leaves-TREEOMQ[T ] of TREEOMQ[T ].
In this paper, we summarise and discuss our recent results answering some of the
questions above and presented in [
To make the ontology axioms in Section 3 more compact and readable, we use the syntax of first-order rather than description logic. Thus, an OWL 2 QL ontology, T , is a finite set of sentences of the form 8x ( (x) ! 0(x)); 8xy (%(x; y) ! %0(x; y)); 8x %(x; x); 8x ( (x) ^ 0(x) ! ?); 8xy (%(x; y) ^ %0(x; y) ! ?); 8x (%(x; x) ! ?); where (x) and %(x; y) are defined, using unary predicates A and binary predicates P , by the grammars
(x) ::= %(x; y) ::= > j A(x) j 9y %(x; y); > j P (x; y) j P (y; x): When writing ontology axioms, we omit the universal quantifiers. Denote by RT the set of binary predicates P occurring in T and their inverses P , assuming that P = P . An ABox, A, is a finite set of unary or binary ground atoms. We denote by ind(A) the set of individual constants in A.
A conjunctive query (CQ) q(x) is a formula of the form 9y '(x; y), where ' is a conjunction of (unary A(u) or binary P (u; v)) atoms S(z) all of whose variables are among x [ y. We assume, without loss of generality, that CQs contain no constants. We often regard a CQ as the set of its atoms.With every CQ q, we associate its Gaifman graph G whose vertices are the variables of q and whose edges are the pairs fu; vg such that P (u; v) 2 q, for some P (note that the atoms P (u; u) do not add any edges to G). We call q connected if G is connected; q is tree-shaped if G is a tree, and linear if G is a tree with two leaves.
An ontology-mediated query (OMQ) is a pair Q(x) = (T ; q(x)), where T is an ontology and q(x) a CQ. A tuple a in ind(A) is a certain answer to (T ; q) 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). For a Boolean q, in which case x = ;, a certain answer to Q over A is ‘yes’ if T ; A j= q and ‘no’ otherwise.
Every consistent knowledge base (KB) (T ; A) has a canonical model (or chase in
database theory) [
We denote by WT the set consisting of the empty word " and all non-empty words %1 : : : %n 2 R+ satisfying the last two conditions. Every a 2 ind(A) is interpreted in
T CT ;A by itself, and unary and binary predicates are interpreted as follows: – CT ;A j= A(u) iff either u 2 ind(A) and T ; A j= A(u), or u = w% and we have
T j= 9y %(y; x) ! A(x); – CT ;A j= P (u; v) iff one of the following three conditions holds: (i) u; v 2 ind(A) and T ; A j= P (u; v); (ii) u = v and T j= P (x; x); (iii) T j= %(x; y) ! P (x; y) and either v = u% or u = v% .
We say that T is of depth 0 d < 1 if d is the maximum length of the words in
WT , and of depth 1 if WT is infinite. (Note that the depth of T is computable in NL;
cf. [
We consider various parameterisations and restrictions of the decision problem TREEOMQ defined above. As parameters, we can take the following1: query: leaves: ontology: depth: a tree-shaped CQ q, the number of leaves in the Gaifman graph of a tree-shaped CQs q, an OWL 2 QL ontology T , the depth of T .
Restrictions can take the forms leaves `: depth d: query = q: ontology = T : we consider only CQs with ` leaves, for some ` we consider only ontologies of depth d, for some d we fix the tree-shaped CQ q, we fix the ontology T . 2, 0,
parameter-TREEOMQ[restriction1; : : : ; restrictionn]; where parameter is one of the parameters above or blank, and each restrictioni, if any, is one of the restrictions above. To simplify notation, instead of [ontology = T ] we write [T ] and similarly for [query = q]. For example, leaves-TREEOMQ[T ] is the problem Instance: q and A,
Problem: decide whether T ; A j= q.
We now construct an ontology T for which this problem is W [
Theorem 1. There is an ontology T2 such that leaves-TREEOMQ[T2] is W [
Instance: a set T of tile types painted in colours from a set C, a positive integer k, Parameter: k,
Suppose C = f0; : : : ; ng, for n 1, and T = fS1; : : : ; Smg. Denote by right (t), left (t), top(t) and bottom(t) the right, left, top and bottom colour of St, respectively. Given a binary predicate name R, we denote by Ri a sequence of i-many predicates R. We represent each colour c n by the following two sequences of binary predicates: encc = P 3n cF c cnec = N 2cM N 2(n c) of length 3n; of length 2n + 1: Examples of encc and cnec, for n = 4 and c = 3, are shown in Figs. 2a and 2d, respectively. Each tile St is represented by the following sequence of binary predicates: tilet = B cneright(t) encleft(t) cnetop(t) encbottom(t)E of length 10n + 4: Since the length of encc does not depend on c, we use jencj to denote the length of some (any) encc, and similarly for jcnej and jtilej. We shall also require the following sequences
segm = tile1 tile2 : : : tilem S spring = (XY I)n probelt = Ijcnej+jencj+2 spring Ijtilej+1I2nM probedn = I2 spring I(jtilej+1)kI2nM of length m jtilej + 1; of length jencj; of length 2 jtilej + 1; of length 5n + 3 + (jtilej + 1)k: The first sequence will be called a segment and the second a spring.
The Boolean CQ q (see Fig. 1) is now defined by taking the following set of atoms (assuming that all variables are existentially quantified): fA(x0)g [ segm(x0; x1;1) [ [ segm(xi 1;j ; xi;j ) [ [ segm(xk;j 1; x1;j ) [ probelt(xi;j ; yi;j ) [
probedn(xi;j ; zi;j ); 2 i k 1 j k [ 2 i k 1 j k 2 j k [ 1 i k 2 j k where R1 : : : Rl(x; y) stands for fR1(x; x1); R2(x1; x2); : : : ; Rl(xl 1; y)g with fresh variables x1; : : : ; xl 1. It can be seen that q is a tree-shaped CQ with 2(k 1)k leaves.
A(x) ! 9y BI(x; y) ^ Right (y) ; A(x) ! 9u Sink (x; u); x1;k probedn z1;k x1;3 probedn z1;3 x1;2 probedn z1;2 x1;1 y2;kprobelt segm
x2;k probedn
z2;k y2;3probelt segm
A path in the canonical model CT2;fA(a)g where q can be homomorphically mapped is shown in Fig. 2 sandwiched between segm(x0; x1;1) [ segm(x1;1; x2;1) on the left and bottom and probelt(x2;1; y2;1) on the right and top (most predicate names are omitted).
We show that T2; fA(a)g j= q iff T tiles a k k-grid. Here, we only prove ()) and leave the converse direction to the reader. For two sequences w = R1 : : : Rl and w0 = R10 : : : Rl0 of binary predicate names, we write w v w0 if T2 j= Ri(x; y) ! Ri0(x; y), for all i (1 i l).
Let h be a homomorphism from q to C = CT2;fA(a)g such that h(x0) = v0 (cf. the definition of labelled nulls in Section 2). Then v0 2 AC and h(x1;1) = v1;1 2 AC with v1;1 of the form v0w1;1S, for some w1;1 that begins with B but does not contain S. Since (v0; v0Sink ) 2= SC and jtilej is even, it follows that there is a unique tile t1;1 such that – jw1;1j = jtilej and w1;1 v tilet1;1 , – the subquery of segm(x0; x1;1) for the sequence tile1 : : : tilet1;1 1 is mapped to the Sink arrow at v0 (i.e., forwards and backwards between v0 and v0Sink ); – the subquery for the sequence tilet1;1+1 : : : tilem is mapped to a Sink arrow at v0w1;1 (see Fig. 2).
Consider now any subquery segm(xi 1;1; xi;1), for 2 i k. By the same argument, we obtain h(xi;1) = vi;1, for vi;1 = vi 1;1wi;1S, and wi;1 v tileti;1 , for a unique 1 ti;1 m. Next, h(x1;2) = v1;2 for v1;2 = vk;1w1;2 S with w1;2 v tilet1;2 and, eventually, every subquery segm(xi 1;j; xi;j), for 1 i k and 1 j k, is mapped in such a way that 8 ><vi 1;jwi;jS; >:v0w1;1S; if i
2; if i = 1; j = 1: h(xi;j) = vk;j 1wi;jS; if i = 1; j
We prove now that the tiles Sti;j placed at (i; j) of the k k-grid form a tiling.
First, we show that left (ti;j) = right (ti 1;j), for 2 i k and 1 j k. As we observed above, h(xi;j) is of the form v wi 1;j S wi;j S. Consider the subquery probelt(xi;j; yi;j) and recall that
wi;j v B cneright(ti;j) encleft(ti;j) cnetop(ti;j) encbottom(ti;j) E: By the structure of T2, the subqueries Ijencj+jcnej+2(xi;j; vi;j) and spring(vi;j; ui;j) of probelt(xi;j; yi;j) are mapped by h in such a way (see Fig. 2) that h(vi;j) v v wi 1;j S B cneright(ti;j) encleft(ti;j); h(ui;j) v v wi 1;j S B cneright(ti;j) P 2c; for c = left (ti;j): On the other hand, the last element in probelt is M , and so we must have h(yi;j) v v B N 2c0 ;
for c0 = right (ti 1;j); c e nM c c en F
F neM c c en F
F
E Sink
N N N P P N N N N P P
X X X X
S tile1 Sink A : : : 1 ; 1 t e l i t : : : tilem c) b) a)
P I X Y P T
B x1;1
P I X Y P
v0w1;1S A iS B n k tile1 : : :
P I X Y P 2c
P I X Y P c 2 c 2 n 2
N N N N N N M N
N encc cne
enc jcnej + jencj + 1 T B 3n 2c Y P I X Y P
X P I X Y
P d)
f) e) N I N I N I N I N I N I M I N I N I cne 1 + n 2 + j e l i t j P I X Y P
L P
P spring
X X X F F F tilet2;1 Fig. 2. Matching the first two segments, segm(x0; x1;1) and segm(x1;1; x2;1), of q and probelt(x2;1; y2;1) in the canonical model C, and the magnified fragments for encc and cnec with n = 4 and c = 3: a) subsequence encc of tilet in q; b) a path in C where encc is mapped; c) matching the spring subquery of probelt in C; d) subsequence cnec of tilet in q; e) a path in C where cnec is mapped; f) mapping variable y2;1 of the subquery probelt(x2;1; y2;1) in C. v0w1;1Sw2;1S
E inS
k : : : tilem
I F I F
Y which is only possible if right (ti 1;j ) = left (ti;j ); see Fig. 2.
That down(ti;j ) = up(ti;j 1), for 2 j k and 1 i considering the mapping of the subquery probedn(xi;j ; zi;j ). 4
Complexity Landscape In this concluding section, we summarise what is known about the complexity of the decision problems introduced in Section 2. In the table below, parameters are listed horizontally, while restrictions on ontologies and CQs vertically in the first two columns, where ‘—’ means no restriction or parameter, FPTy indicates that FTP follows from tractability, while in the grey areas, the problems are trivial. k, is proved similarly by restrictions on T — q — fixed — fixed leaves d e x fi d leaves
— h t p ed leaves fixed ` ` `
— (combined complexity)
for some T ( ) in AC0 in LOGCFL
for some T ; ` = 2
FPT
parameter leaves
for some T
ontology paraNP see ( )
depth
Recall first that the basic problem TREEOMQ of answering tree-shaped OMQs is
NPcomplete [
The intractability result for TREEOMQ has recently been refined in [4, Theorem 20], which constructed an ontology Ty (of infinite depth) such that TREEOMQ[Ty] is NPcomplete. It follows that—unless P = NP—no algorithm can solve TREEOMQ in time poly(jqj; jAj)f(jT j), for any computable function f . Such a complexity bound would usually be regarded as an indication that, in practice, TREEOMQ could be solved efficiently for small T . Thus, ontology-TREEOMQ (actually, with any parameter determined by the ontology) cannot be FPT.
Tractability can be restored by restricting the number of leaves in q and/or the depth
of T : as shown in [
In fact, answering OMQs (T ; q) with q having at most ` leaves can be done in
time poly(jT j; jqj`; jAj`) [
A challenging open problem is to classify OWL 2 QL ontologies T according to
the combined complexity of answering OMQs (T ; q) with tree-shaped or arbitrary
CQs q. In particular, are there interesting conditions on T that ensure tractability of
TREEOMQ[T ]? Is it the case that, for every T , the problem TREEOMQ[T ] is either
in P or NP-complete? In a more general setting, dichotomies of this kind have been
considered in [
Acknowledgements. This work was supported by the UK EPSRC grant EP/M012670/ ‘iTract: Islands of Tractability in Ontology-Based Data Access’.