We study query answering in the description logic SQ supporting number restrictions on both transitive and non-transitive roles. Our main contributions are (i) a tree-like model property for SQ knowledge bases and, building upon this, (ii) an automata based decision procedure for answering two-way regular path queries, which gives a 3ExpTime upper bound.
In the last years, several e orts have been put into the study of the query
answering problem (QA) in description logics (DLs) featuring transitive roles (or
generalisations thereof, such as regular expressions on roles) and number
restrictions, see e.g., [
The lack of investigations of query answering in DLs of this kind is partly
because (i) the interaction of these features often leads to undecidability of the
standard reasoning tasks (e.g., satis ability) - even in lightweight sub-Boolean
DLs with unquali ed number restrictions [
The objective of this paper is to start the investigation of query answering
in DLs supporting number restrictions on transitive roles. In particular, we look
at the problem of answering regular path queries, which generalise standard
query languages like positive existential queries, over SQ knowledge bases [
There has been some work on the extension of decidable rst-order logic
fragments, such as the guarded fragment, with transitivity and counting, see
e.g., [
Syntax. We introduce the DL SQ, which extends the classical DL ALC with transitivity declarations on roles (S) and quali ed number restrictions (Q). We consider a vocabulary consisting of countably in nite disjoint sets of concept names NC, role names NR, and individual names NI, and assume that NR is partitioned into two countably in nite sets of non-transitive role names Nnt R and transitive role names Nt . The syntax of SQ-concepts C; D is given by the
R grammar rule C; D ::= A j :C j C u D j ( n r C) where A 2 NC, r 2 NR, and n is a number given in binary. We use ( n r C) as an abbreviation for :( (n 1) r C), and other standard abbreviations like ?, >, C t D, 9r:C, 8r:C. Concepts of the form ( n r C) and ( n r C) are called at most-restrictions and at least-restrictions, respectively.
An SQ-TBox T is a nite set of concept inclusions C v D where C; D are SQ-concepts. An ABox is a nite set of concept and role assertions of the form A(a), r(a; b) where A 2 NC, r 2 NR and fa; bg NI; ind(A) denotes the set of individual names occurring in A. A knowledge base (KB) K is a pair (T ; A). Semantics. As usual, the semantics is de ned in terms of interpretations. An interpretation I = ( I ; I ) consists of a non-empty domain I and an interpretation function I mapping concept names to subsets of the domain and role names to binary relations over the domain such that transitive role names are mapped to transitive relations. We de ne CI for complex concepts C by interpreting : and u as usual and ( n r D)I by taking ( n r D)I = fd 2
I j jfe 2 CI j (d; e) 2 rI gj ng: For ABoxes A we adopt the standard name assumption (SNA), that is, aI = a, for all a 2 ind(A), but we conjecture that our results hold without the unique name assumption. The satisfaction relation j= is de ned in the standard way: I j= C v D i CI
DI ;
I j= A(a) i a 2 AI ;
I j= r(a; b) i (a; b) 2 rI : An interpretation I is a model of a TBox T , denoted I j= T , if I j= for all 2 T ; it is a model of an ABox A, written I j= A, if I j= for all 2 A; it is a model of a KB K if I j= T and I j= A. A KB is satis able if it has a model. Query Language. As query language, we consider regular path queries, supporting regular expressions over roles. Recall that a regular expression E over an alphabet is given by the grammar E ::= " j j E E j E [ E j E ; where 2 and " denotes the empty word. We denote with L(E ) the language de ned by E .
We use NR to refer to NR [ fr j r 2 NRg with (r )I de ned as f(d; e) j
(e; d) 2 rI g, and identify r with s 2 NR if r = s . A positive 2-way regular path
query (P2RPQ) is a formula of the form q(x) = 9y:'(x; y) where x and y are
tuples of variables and ' is constructed using ^ and _ of atoms of the form A(t)
or E (t; t0) where A 2 NC, E is a regular expression over S ::= NR [fA? j A 2 NCg,
and t; t0 are terms, i.e., individual names or variables from x; y. We de ne as
usual when a possible answer tuple a 2 ind(A) is a certain answer of q over K
and write K j= q(a) in case it is [
Reasoning Problem. We study the certain answers problem: Given a KB K, a query q(x) and a tuple of individuals a, determine whether K j= q(a). Without loss of generality, we consider Boolean queries. 3
Decomposing SQ-Interpretations Existing algorithms for QA in expressive DLs, e.g., SHIQ (without number restrictions on transitive roles), exploit the fact that for answering queries it su ces to consider canonical models that are forest-like, roughly consisting of an interpretation of the ABox and a collection of tree-interpretations whose roots are elements of the ABox. However, for SQ this A tree-model property is lost: Example 1. Let T = fA v ( 1 r C) u 9r:B u 9r::B; > v 9r:Cg with r 2 Nt . The number restrictions in T force that ev
R ery model of T satisfying A contains the structure in Fig. 1(a).
Moreover, in SQ strongly connected components can be en- A forced. Let T 0 = fA v (= 3 r B); B v (= 3 r B); A v :Bg with r 2 Nt . Then, in every model of T 0, an element satis
R fying A roots the structure depicted in Fig. 1(b), where the elements satisfying B form a strongly connected component. (a) (b) :B
B B
B
B
Nevertheless, we will de ne tree-like canonical models for SQ that su ce for query answering. We start with introducing a basic form of tree decompositions of SQ-interpretations.
C A tree is a connected, acyclic graph (T; E) with a distinguished root, which we usually denote with ". We usually write only T instead of (T; E), thus leaving E implicit. Fix some interpretation I = ( I ; I ). A bag M is a set of assertions of the form A(d); r(d; e) with d; e 2 I . We denote with dom(M ) the set of domain elements appearing in M . Given a set I , we denote with bagI ( ) the set bagI ( ) = fA(d) j d 2 ; d 2 AI g [ fr(d; e) j d; e 2 ; (d; e) 2 rI g: De nition 2. A tree decomposition of an interpretation I is a tuple (T; bg) where T is a tree and bg assigns a bag to every node w in T such that: (i) bg(w) = bagI (dom(bg(w))); (ii) I = Sw2T dom(bg(w)); (iii) rI = r for non-transitive r and rI = r+ for transitive r, where r = f(d; e) j r(d; e) 2 bg(w); w 2 T g; (iv) for all d 2
I , the set fw 2 T j d 2 dom(bag(w))g is connected in T .
De nition 2 provides a variant of tree decompositions of interpretations with transitive relations. This formalisation does not yet enable tree automata to count over transitive roles (with a small number of states) since assertions r(d; e) can appear far away from each other in the decomposition. To address this, we introduce canonical tree decompositions which extend tree decompositions with a third component rl which assigns a role name to every non-root node of T and ? to the root ". Intuitively, a node w 2 T labeled with r = rl(w) will be responsible for capturing r-successors of some element(s) in the previous bag.
Fix a triple (T; bg; rl) such that (T; bg) is a tree decomposition of I. By Item (iv) of De nition 2, for each d 2 I , there is a unique node w 2 T such that all occurrences of d are in or below w in T . In this case, we say that d is fresh in w, and we denote with F (w) the set of all fresh elements in w. We will also need a relativised version of freshness which takes into account the role associated to the predecessor bag. In particular, for each transitive role r and each w 2 T with rl(w) 2 fr; ?g, we de ne a set Fr(w) by taking: { Fr(w) = F (w) if the predecessor w^ of w satis es rl(w^) 2 fr; ?g; { Fr(w) = dom(bg(w)) otherwise.
Intuitively, Fr(w) contains all elements that are eligible as origins for r-successors.
For a transitive role r and a bag M , we call ; ( a dom(M ) an r-cluster in M if (i) r(a; b) 2 M for all a 6= b 2 a, and (ii) for all a 2 a, b 2 dom(M ) with r(a; b); r(b; a) 2 M , we have b 2 a. An r-cluster a in M is an r-root cluster in M if r(d; e) 2 M for all d 2 a and e 2 dom(M ) n a.
De nition 3. A triple T = (T; bg; rl) is a canonical tree decomposition of I if (T; bg) is a tree decomposition of I and the following conditions are satis ed for every w 2 T with M = bg(w) and r = rl(w) and every successor w0 of w with M 0 = bg(w0) and r0 = rl(w0): (C1) if r0 2 NRnt, then dom(M 0) = fd; eg, for some d 2 F (w), e 2 F (w0), and r0(d; e) is the only role assertion in M 0; (C2) if r0 2 NtR and r 2= f?; r0g, then there are d 2 F (w) and an r-root cluster a in M 0 such that dom(M ) \ dom(M 0) = fdg and d 2 a; moreover, there is no successor v0 of w di erent from w0 satisfying this for d and rl(v0) = r0; (C3) if r0 2 NtR and r 2 f?; r0g, then there is an r0-cluster a in M with: (a) a Fr0 (w); (b) a is an r0-root cluster in M 0; (c) for all d 2 a and r0(d; e) 2 M , we have e 2 dom(M 0); and (d) for all r0(d; e) 2 M 0, d 2 a [ F (w0) or e 2= F (w0).
De nition 3 imposes restrictions on the structural relation between
neighbouring bags. Note that Condition (C1) is also satis ed by standard unravelings over
non-transitive roles [
As a consequence of De nition 3, we can address r-successors of elements in a canonical tree decomposition T = (T; bg; rl) of I. For a non-transitive role r, Condition (C1) ensures that r-successors e of d are contained only in successor nodes of the (unique) node where d is fresh. For a transitive role r, note rst that (d; e) 2 rI i there is a sequence d0; w0; d1; : : : ; wn 1; dn with di 2 I and wi 2 T such that d = d0, e = dn, and r(di; di+1) 2 bg(wi), for all 0 i < n; we call such a sequence an r-path from d to e in T. We call an r-path d0; w0; d1; : : : ; wn 1; dn downward if wi is a successor of wi 1 and di is contained in an r-root cluster of wi, for all 0 < i < n. An r-path in T is canonical if P1: it is downward; or P2: d0 2 Fr(w0), d1 2= Fr(w0), and, if n > 1, then d1; w1; : : : ; dn is a downward path in T and the predecessor w^ of w1 is an ancestor of w0 and satis es d1 2 Fr(w^). Two r-paths d0; w0; d1; : : : ; wn 1; dn and e0; w00; e1; : : : ; wm0 1; em from d to e are equivalent if n = m, wi = wi0, for 0 i < n, and di and ei are in the same r-cluster in bg(wi), for every 1 i < n.
Lemma 4 establishes the basis for uniquely identifying transitive r-successors in a canonical tree decomposition which is essential for the design of automata. Lemma 4. Let T be a canonical decomposition of I, r transitive, and (d; e) 2 rI . Then there is a unique canonical r-path up to equivalence from d to e in T. 3.1
Unraveling into Canonical Decompositions We give now the main technical contribution of our paper: an unraveling operation into canonical decompositions of small width, and consequently a tree-like model property for SQ-interpretations. A canonical tree decomposition (T; bg; rl) has width k 1 if k is the maximum size of dom(bg(w)), where w ranges over T ; its outdegree is the outdegree of the underlying tree T .
Theorem 5. Let K = (T ; A) be an SQ KB and I j= K. Then, there is an interpretation J and a canonical tree decomposition (T; bg; rl) of J such that: (1) A bg("); (2) J j= K; (3) there is a homomorphism from J to I; (4) width and outdegree of (T; bg; rl) are bounded by O(jAj 2poly(jT j)). We outline the proof of Theorem 5. As a rst step, we show that wlog. we can assume that I has a restricted outdegree and width, as de ned below. This will be used later on to ensure the satisfaction of Condition (4) above. Given d 2 I and a transitive role r, the r-cluster of d in I, denoted by QI;r(d), is the set of all elements e 2 I such that both (d; e) 2 rI and (e; d) 2 rI . The width of I is the minimum k such that jQI;r(d)j k for all d 2 I , r 2 NtR. Moreover, for a transitive role r, we say that e is a direct r-successor of d if (d; e) 2 rI but e 2= QI;r(d), and for each f with (d; f ); (f; e) 2 rI , we have f 2 QI;r(d) or f 2 QI;r(e); if r is non-transitive, then e is a direct r-successor of d if (d; e) 2 rI . The breadth of I is the maximum k such that there are d; d1; : : : ; dk and a role name r, all di are direct r-successors of d, and { if r is non-transitive, then di 6= dj for all i 6= j; { if r is transitive, then QI;r(di) 6= QI;r(dj ), for all i 6= j.
We can assume that width and breath of I are within the following boundaries.
Lemma 6 (adapting [
WitI;r(d) = Sejd I;re QI;r(e): Intuitively, WitI;r(d) contains all witnesses of at-most restrictions of some element d, and due to using I;r, also the witnesses of at-most restrictions of those witnesses and so on. It is important to note that the size of WitI;r(T ) is bounded exponentially in T (and linearly in A), see appendix.
We describe now the construction of the interpretation J and its tree decomposition via a possibly in nite unraveling process. Elements of J will be either of the form a with a 2 ind(A) or of the form dx with d 2 I and some index x. We usually use to refer to domain elements in J (in either form), and de ne a function : J ! I by setting ( ) = , for all 2 ind(A), and ( ) = d, for all of the form dx in J .
To start the construction of J and (T; bg; rl), we set J = Ijind(A) and, for every transitive role r, de ne two sets r; 0r by taking r = fdr j d 2 Sa2ind(A) WitI;r(a) n ind(A)g and 0r = r [ ind(A):
Then extend J by adding, for each transitive r, r to the domain and extending the interpretation of concept and role names such that, for all ; 0 2 0r, we have 2 AJ ,
( ) 2 AI , for all A 2 NC, and ( ; 0) 2 rJ , ( ( ); ( 0)) 2 rI : (y) Now, initialise (T; bg; rl) with T = f"g, bg(") = bagJ ( J ), and rl(") = ?. Intuitively, this rst step ensures that all witnesses of ABox individuals appear in the rst bag. This nishes the initialisation phase.
Next, extend J and (T; bg; rl) by applying the following rules exhaustively and in a fair way: R1 Let r be non-transitive, w 2 T , 2 F (w), and d a direct r-successor of ( ) in I with f ; dg 6 ind(A). Then, add a fresh successor v of w to T , add a fresh element dv to J , extend J by adding ( ; dv) 2 rJ and dv 2 AJ i d 2 AI , for all A 2 NC, and set bg(v) = bagJ (f ; dvg) and rl(v) = r. R2 Let r be transitive, w 2 T , and 2 F (w) such that: (a) w = " and 2 s, s 6= r ( s de ned in the initialisation phase), or (b) w 6= " and rl(w) 6= r.
Then add a fresh successor v of w to T , and de ne
= fev j e 2 WitI;r( ( )) n f ( )gg and 0 = [ f g: Extend the domain of J with and the interpretation of concept and role names such that (y) is satis ed for all ; 0 2 0. Finally, set bg(v) = bagJ ( 0) and rl(v) = r.
R3 Let r be transitive, w 2 T , a Fr(w) an r-cluster in bg(w) such that: (a) w = " and a 0r, or (b) w 6= " and rl(w) = r.
If there is a direct r-successor e of ( ) in I for some 2 a such that ( ; 0) 2= rJ for any 0 with ( 0) = e, then add a fresh successor v of w to T , and de ne = ffv j f 2 WitI;r(e) n WitI;r( ( ))g
and 0 =
[ a [ f 00 j r( 0; 00) 2 bg(w) for some 0 2 ag: Then extend the domain of J with and the interpretation of concept names such that (y) is satis ed for all pairs ; 0 with 2 a [ and 0 2 0.
Finally, set bg(v) = bagJ ( 0) and rl(v) = r.
Rules R1{R3 are, respectively, in one-to-one correspondence with Conditions (C1)-(C3) in De nition 3. In particular, R1 implements the well-known unraveling procedure for non-transitive roles. R2 is used to change the `role component' for transitive roles by creating a bag which contains all witnesses of the chosen element . Finally, R3 describes how to unravel direct r-successors in case of transitive roles r. In the de nition of it is taken care that witnesses which are `inherited' from predecessors are not introduced again, in order to preserve at-most restrictions.
Example 7. Let K = (fA1 v ( 1 r B); A2 v ( 1 r C)g; fA1(a)g) with r 2 NtR. Fig. 2 shows a model I of T and a canonical decomposition T of its unraveling (transitivity connections are omitted). In the initialisation phase, the ?-bag is constructed starting from individual a. Since a I;r e and e I;r f , we have WitI;r(a) = fe; f g, thus er and fr are added in this phase.
It is veri ed in the appendix that (T; bg; rl) and J satisfy the conditions
from Theorem 5. Theorem 5 yields a tree-like model property for SQ-knowledge
bases, which is interesting on its own since existing decidability results (for
satis ability) [
In this section, we devise an automata-based decision procedure for query
answering in SQ. By Theorem 5, if K 6j= q, there is an interpretation of small width
and outdegree witnessing this. The idea is now to design two automata AK and
Aq working over tree decompositions which accept precisely the models (of a
xed width) of the KB K and the query q, respectively. Query answering is then
reduced to the question if some tree is accepted by AK, but not by Aq [
Trees are represented as pre x-closed subsets T (N n f0g) such that additionally, wc 2 T implies w(c 1) 2 T for all c > 1. A tree is k-ary if each node has exactly k successors. As a convention, we set w 0 = w and wc ( 1) = w, leave " ( 1) unde ned, and for any k 2 N, set [k] = f 1; 0; : : : ; kg. Let be a nite alphabet. A -labeled tree is a pair (T; ) with T a tree and : T ! assigns a letter from to each node. An alternating 2-way tree automaton (2ATA) over -labeled k-ary trees is a tuple A = (Q; ; q0; ; F ) where Q is a nite set of states, q0 2 Q is an initial state, is the transition function, and F is the (parity) acceptance condition [26]. The transition function maps a state q and an input letter a 2 to a positive Boolean formula over the constants true and false, and variables from [k] Q. The semantics is given in terms of runs, see the appendix. As usual, L(A) denotes the set of trees accepted by A. Emptiness of L(A) can be checked in exponential time in the number of states of A [26].
In principle, tree decompositions T can be represented as labeled trees, where
each node label consists of a bag and a role name (or ?). However, 2ATAs
cannot run over such labeled trees because the domain underlying the bags
is potentially in nite. Exploiting the bounded width, we encode the in nite
domain with nitely many elements in the following well-known way [
The mentioned automaton AK is obtained as the conjunction of A1, A2, and
A3. Note that AK can be used to decide KB satis ability in double exponential
time, thus not optimal [
^ d2dom(M) CvD2T 3(q0; ) = true (0; qnnf(:C);d) _ (0; qD;d) 3(qA;d; hM; xi) = if A(d) 2 M , then true else false 3(q:A;d; hM; xi) = if A(d) 2= M , then true else false 3(qC1tC2;d; hM; xi) = (0; qC1;d) _ (0; qC2;d) 3(q( n r D);d; hM; xi) = (0; Fx;d) ^ (0; q( n r D);d) _ _ (i; q( n r D);d) ^ (i; qd) i2[k] 3(qd; hM; xi) = if d 2 dom(M ), then true else false 3(F?;d; hM; xi) = true
(( 1; Fr0;d) if r 2 NRnt or (r 2 NtR and x = r) 3(Fr;d; hM; xi) =
false otherwise 3(Fr0;d; hM; xi) = (true d 2= dom(M ) or (r 2 NtR and x 2= f?; rg)
false otherwise Intuitively, q0 is used to verify that the TBox is globally satis ed. A state qC;d assigned to a node w is used as an obligation to verify that the element d satis es the concept C. This can be done locally for Boolean concept constructors u; t; :, as implemented in the transitions above. For concepts of the form ( n r D), we have to be more careful: the automaton has to move to the unique node w where d 2 Fr(w), identi ed using states Fr;d and qd (and the acceptance condition).
The transitions for number restrictions on non-transitive roles are defered to the appendix. For transitive roles, Lemma 4 provides the following observation: For counting the r-successors satisfying D of some d 2 dom(bg(w)), it su ces to look at three \locations" in the tree decomposition: in the bag at w itself, along canonical paths satisfying P1, and along canonical paths satisfying P2. We next implement this strategy for at-least restrictions. In the following transitions, we assume that a1; : : : ; a` are all r-clusters in M , and that a1; : : : ; a` are representatives of each cluster. A partition n1 + : : : + n` = n respects M relative to d if ni = 0 whenever r(d; ai) 2= M ; it d-respects M relative to d if ni = 0 whenever r(d; ai) 2= M or d 2 ai. Moreover, we de ne Mr(d) = fe j r(d; e); r(e; d) 2 M g, and de ne transitions for (the complement of Fx;d) F x;d similar to Fx;d. 3(q( n r D);d; hM; xi) = ^ (0; q(0 ni r D);ai ) _ (0; q(1 ni r D);ai ) n1+:::+n`=n respects M rel. to d ni6=0 3(q(0 n r D);d; hM; xi) = (0; Fr;d) ^ (0; q(# n r D);d) 3(q(1 n r D);d; hM; xi) = (0; F r;d) ^ ( 1; q(" n r D);d) _ _ 3(p( n r D);d; ) = if n = 0, then true else false 3(q(# n r D);d; hM; xi) =
3(pn;r;D;d; hM; xi) = 3(p( n r D);d; hM; xi) =
(0; pn0;r;D;d) ^ n0+n1+:::+nk=n
_ ^ qD;e ^ Y Mr(d);jY j=n e2Y 8false > <
_ > n1+:::+n`=n :d-respects M rel. to d ni6=0 ^ (i; p( ni r D);d) ni6=0 ^
q D;e y2Mr(d)nY if x 6= r or d not in root cluster ^ (0; q(0 ni r D);ai ) otherwise Intuitively, the automaton non-deterministically guesses a partition n1 + : : : + nk of n and veri es that, starting from ai at least ni elements are reachable via r and satisfy D. For each such r-cluster, it proceeds either downwards (in states of the form q0 and q#) or looks for the world where the cluster ai was a root (in states q1 and q") and proceeds downwards from there on. In states q(# n r D);d, the automaton again partitions n this time into n0; : : : ; nk; it then veri es that there are n0 elements in the r-cluster of d satisfying D and, recursively, that via the i-th successor of the current node, there are ni elements that are reachable via r and satisfy D. Using the parity condition, we make sure that states q(# n r D);d with n 1 are not suspended forever, that is, eventualities are nally satis ed.
For the at-most restrictions, recall that ( n r D) is equivalent to :( n + 1 r D); we can thus obtain the transitions for q( n r D);d by \complementing" the transitions for q( n+1 r D);d; details are given in the appendix.
In order to construct, for a given query q, an automaton Aq which accepts a
tree (T; ) 2 L(A1) i IT; j= q, we adapt and extend ideas from [
We have developed a tree-like decomposition for SQ which handles the
interaction of number restrictions over transitive roles and enables the use of
automatabased techniques for query answering. Our techniques yield a 3ExpTime upper
bound, leaving an exponential gap to the known 2ExpTime lower bound, for
answering positive existential queries over ALC KBs [
As immediate future work, we plan to close this gap, taking into account
also other techniques for query answering such as rewriting [
of STACS-05. pp. 83{96 (2005) 26. Vardi, M.Y.: Reasoning about the past with two-way automata. In: Proc. ICALP98. pp. 628{641 (1998) 27. Wolstencroft, K., Brass, A., Horrocks, I., Lord, P., Sattler, U., Turi, D., Stevens, R.: A little semantic web goes a long way in biology. In: Proc. of ISWC-05 (2005)