We settle an open question on the complexity of the following problem: given two OWL 2 QL TBoxes and a signature, decide whether these TBoxes return the same answers to any conjunctive query over any data formulated in the given signature. It has been known that the complexity of this problem is between PSpace and ExpTime. Here we show that the problem is ExpTime-complete and, in fact, deciding whether two OWL 2 QL knowledge bases (each with its own data) give the same answers to any conjunctive query is ExpTime-hard.
In this paper, we show that the problem of deciding whether two given OWL 2 QL ontologies return the same answers to any conjunctive query in a given signature is ExpTime-hard. The notion of conjunctive query inseparability has recently been used in two settings: ontology engineering and maintenance, and knowledge base exchange.
It has been argued [
In the knowledge exchange framework [
The -query inseparability problem for ontologies (TBoxes) in the fragment
of OWL 2 QL without role inclusions proves to be quite simple: it is
NLogSpacecomplete and can be solved in practice using various existing reasoners [
In this paper, we prove, by encoding alternating Turing machines with polynomial tape, that the -query inseparability problem for both OWL 2 QL KBs and ontologies is ExpTime-hard. 2
-Query Entailment and Inseparability We use the following (somewhat 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 ) [
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. 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.
To de ne the main notions of this paper, consider two KBs K1 = (T1; A) and K2 = (T2; A). For example, the Ti are di erent versions of some ontology, or one of them is a re nement of the other by means of new axioms. The question we are interested in is whether they give the same answers to CQs formulated in a certain signature, say, in the common vocabulary of the Ti or in a vocabulary relevant to an application. More precisely, by a signature, , we understand any nite set of concept and role names. A concept (inclusion, TBox, etc.) all concept and role names of which are in is called a -concept (inclusion, etc.). We say that K1 -query entails K2 if, for all -queries q(x) and all a ind(A), K2 j= q(a) implies K1 j= q(a). In other words: any certain answer to a -query given by K2 is also given by K1. We call K1 and K2 -query inseparable if they -query entail each other, in which case we write K1 K2.
As the ABox is typically not xed or known at the ontology design stage, we may have to compare the TBoxes over arbitrary -ABoxes rather than a xed one, which gives the following de nition. Let T1 and T2 be TBoxes and a signature. T1 -query entails T2 if (T1; A) -query entails (T2; A) for any -ABox A. T1 and T2 are -query inseparable if they -query entail each other, in which case we write T1 T2.
In the remainder of this section, we recap the semantic criteria of -query
entailment established in [
Let [R] = fS j T j= R Sg. We write [R] T [S] if T j= R v S; thus, T is a partial order on the set f[R] j R a role in T g. For each [R], we introduce a witness w[R] and de ne a generating relation K on the set of these witnesses together with ind(A) by taking: a w[S]
K w[R] if a 2 ind(A) and [R] is K 6j= R(a; b) for any b 2 ind(A);
K w[R] if [R] is T -minimal with T j= 9S
T -minimal such that K j= 9R(a) and v 9R and [S ] 6= [R].
Clearly, K can be computed in polynomial time in jKj. A K-path is a nite sequence aw[R1] w[Rn], n 0, such that a 2 ind(A) and, if n > 0, then a K w[R1] and w[Ri] K w[Ri+1], for i < n. Denote by tail( ) the last element in the path . The canonical model CK of K is de ned by taking CK to be the set of all K-paths and setting: aCK = a; for all a 2 ind(A); ACK = fa 2 ind(A) j K j= A(a)g [
w[R] j T j= 9R f P CK = f(a; b) 2 ind(A) ind(A) j R(a; b) 2 A with [R] v Ag; for all concept names A;
T [P ]g [ f( ; f(
w[R]) j tail( ) w[R]; ) j tail( )
K w[R]; [R] K w[R]; [R]
T [P ]g [ T [P ]g; for all role names P: Theorem 1. For all consistent OWL 2 QL KBs K = (T ; A), CQs q(x) and tuples a ind(A), we have K j= q(a) i CK j= q(a).
Thus, to decide -query entailment between KBs K1 and K2, it su ces to check whether CK2 j= q(a) implies CK1 j= q(a) for all -queries q(x) and tuples a. This relationship between CK2 and CK1 can be characterised semantically in terms of nite -homomorphisms.
For an interpretation I and a signature , the -types tI (x) and rI (x; y), for x; y 2 I , are given by: tI (x) = f -concept B j x 2 BI g; rI (x; y) = f -role R j (x; y) 2 RI g: A -homomorphism from an interpretation I to I0 is a function h : such that h(aI ) = aI0 , for all individual names a interpreted in I, I !
I0 tI (x) tI0 (h(x)) and rI (x; y) rI0 (h(x); h(y)); for all x; y 2
I :
It is known that answers to -CQs are preserved under -homomorphisms.
Thus, if there is a -homomorphism from CK2 to CK1 , then K1 -query entails
K2. However, it was observed [
Theorem 2 ([
To obtain a similar criterion for TBoxes (rather than KBs), we use the fact that inclusions in OWL 2 QL, di erent from disjointness axioms, involve only one concept or role in the left-hand side and making sure that the TBoxes entail the same -inclusions, one can show that it is enough to consider singleton -ABoxes of the form fB(a)g.
Theorem 3 ([
-concepts B.
It was shown [
Our main result is the following theorem:
Theorem 4. The -query entailment and
ExpTime-hard for OWL 2 QL KBs.
-query inseparability problems are
Proof. The proof is by encoding alternating Turing machines with polynomial
tape and using the well-known fact that APSpace = ExpTime. For more details
on alternating Turing machines the reader is referred to [
Suppose we are given an alternating Turing machine M = ( ; Q; q0; q1; ), where is a tape alphabet, Q a set of states partitioned into existential Q9 and universal Q8 states, q0 2 Q9 an initial state, q1 2 Q an accepting state, and : (Q n fq1g) ! (Q f 1; 0; +1g)2 is a transition function that, for any q 2 Q and a 2 , gives two alternative transitions. We assume that existential and universal states strictly alternate, that is, any transition from an existential state results in a universal state, and vice versa. We also assume that M terminates on every input and there is a polynomial function f such that M uses at most f (m) tape cells on any input of length m. It will be convenient to extend the transition function by the instructions (q1; a) = ((q1; a; 0); (q1; a; 0)), for all a 2 , which have an e ect of going into an in nite loop if M reaches the accepting state. Thus, M accepts an input w i there is a run of the modi ed machine M 0 on w such that all branches of the run are in nite.
Our aim is to construct, given M and an input w, two TBoxes, T1 and T2, such that M accepts w i the canonical model C2 of K2 = (T2; fA(c)g) is nitely homomorphically embeddable into the canonical model C1 of K1 = (T1; fA(c)g), where comprises the concept and role names in T2 (in fact, can be any set of concept and role names including those from T2).
In the de nition of the TBox T1 (but not T2), we use inclusions of the form B v 9R:(C1 u u Ck) as an abbreviation for B v 9R0, R0 v R and 9R0 v Ci, for 1 i k, where R0 is a fresh role name. If Ci is a complex concept then 9R0 v Ci is also treated as an abbreviation for the respective concept and role inclusions.
We de ne T1 and T2 in three steps. Let n = f (jwj).
Step 1. First we encode con gurations and transitions of M 0 using T1. We represent a con guration (that is, the contents of every cell on the tape, the state and the position of the head) by a sequence of (n + 1) R-arrows, for some roles R, which will be called a block. More precisely, the rst arrow in each block is auxiliary; it is used to distinguish the type of the block. The range of the remaining n arrows belongs to one of the concepts Ca, for a 2 . For example, if the range of the (i + 1)th arrow in the block belongs to Ca then the ith cell of the tape contains a in the con guration de ned by the block.
C1
A
P
P
P Ca1
Ca2
Can 1
Can P
Qqn0;a1;1
Fig. 1. Encoding a con guration by a P -block.
The initial block of (n+1)-many P -arrows represents the initial con guration, that is, symbols a1; : : : ; an written in the n cells of the tape (comprising the input w in the rst m cells padded with the blanks) and the initial state q0 (see Fig. 1): A v 9P:9P:(Ca1 u 9P:(Ca2 u 9P:(: : : 9P:(Can u Qqn0;a1;1) : : : ))): (T1-1)
The concepts Qjq;a;k, for 0 j n, de ne the remaining components of a con guration: q 2 Q is the current state and k, 1 k n, is the current position of the head on the tape. In addition, a 2 speci es the contents of the cell scanned by the head (this duplicates the information given by Ca but simpli es the construction). Finally, the index j is required to propagate the current state and head position along the points encoding the con guration. At the end of the tape, the concept Qqn;a;k starts a separate branch for each of the two transitions: we take, for q 2 Q and a 2 with 0(q; a) = ((q1; a1; d1); (q2; a2; d2)), where d1; d2 2 f+1; 0; 1g, the inclusions
Qqn;a;k v 9P:(X1 u Bq01;a1;k;d1 ) u 9P:(X2 u Bq02;a2;k;d2 ); for 1 k n; (T1-2) where X1 and X2 are two fresh concept names (distinguishing the two branches) j and the Bq0;a0;k;d are fresh concepts encoding the next state q0 and the symbol a0 to be placed to the kth cell in the next con guration with k being the current position of the head and d indicating the direction in which the head moves.
For all cells before the head, that is, for all j with j + 1 < k + d and j + 1 < k, we use the following inclusions to pass the information along the sequences of arrows encoding the con guration:
Bq;a;k;d v 9P:(Cb u Bqj;+a1;k;d); j (these inclusions, in fact, generate, for each b 2 , a branch in C1 to represent the same cell but with a di erent symbol, b, tentatively assigned to the cell|we shall see later how the correct branch and the symbol are selected to match the cell contents in the preceding con guration). If j +1 = k or j +1 = k +d then the j cell contents is changed according to the subscript of Bq;a;k;d and the contents of the cell scanned by the head is then recorded in the subscript of Qjq;a;k: Bqk;a;2k; 1 v 9P:(Cb u 9P:(Ca u 9Sa;0 u Qqk;b;k 1));
Bqk;a;k;0 v 9P:(Ca u 9Sa;0 u Qqk;a;k);
1 Bqk;a;1k;+1 v 9P:(Ca u 9Sa;0 u 9P:(Cb u Qqk;+b;1k+1)); for b 2 ; The three situations are depicted in Fig. 2, where the Sa;0 arrows are not shown, and all arrows are labelled by P . The lled nodes represent the beginning of the pattern in each of the three inclusions (T1-4){(T1-6) and the subscript of the concept Ca in the label of the hatched nodes determines the respective subscript j of the sequence of roles Qq;a;k that follows the pattern.
Note that there is only one branch for the cell whose contents is modi ed: the branch corresponds to the new symbol, a, in that cell (see explanations below). (a) (b) (c)
Bqk;a;2k; 1
Bqk;a;2k;0 Bqk;a;2k;+1 cell (k
1) Cb Cb0
Cb00 Cb; Bqk;a;1k;0
Cb0 ; Bqk;a;1k;0
Cb00 ; Bqk;a;1k;0 Cb; Bqk;a;1k;+1
Cb0 ; Bqk;a;1k;+1 Cb00 ; Bqk;a;1k;+1 Ca; Qqk;b;k 1
Ca; Qqk;b0;k 1 Ca; Qqk;b00;k 1
Ca; Qqk;a;k
Ca; Qqk;a;k Ca; Qqk;a;k Ca Ca; Qqk;a;k Ca; Qqk;a;k cell (k + 1)
Cb; Qqk;+b;1k 1 Cb0 ; Qqk;+b;1k 1 Cb00 ; Qqk;+b;1k 1 Cb; Qqk;+a1;k Cb0 ; Qqk;+a1;k Cb00 ; Qqk;+a1;k Cb; Qqk;+b;1k+1 Cb0 ; Qqk;+b01;k+1 Cb00 ; Qqk;+b010;k+1 Finally, if k j < n then the current state and head position with the symbol scanned by the head are simply propagated along the tape:
Qq;a;k v 9P:(Cb u Qjq+;a1;k); j for b 2 (T1-7) (generating a separate branch for each symbol tentatively assigned to the cell; see cases (a) and (b) in Fig. 2).
Step 2. The axioms (T1-3){(T1-7) generate a separate P -successor for each symbol b in the alphabet . The correct one will be chosen by a -homomorphism from the canonical model C2 of K2 into the canonical model C1 of K1. To exclude wrong choices, we add the following concept and role inclusions to T1 and T2. Each element d1 of C1 that represents a possible cell contents, say a, also generates a block of arrows Sb;0; : : : ; Sb;n, for all symbols b di erent from a: Ca v D;
Ca v 9Sb;0; 9Sb;j 1 v 9Sb;j ; 9Sb;n v Cb; On the other hand, T2 makes sure that every element d2 of a concept D in C2 generates a block Za;0; : : : ; Za;n, for each a 2 :
D v 9Za;0; 9Za;j 1 v 9Za;j ; 9Za;n v Ca: for 0 < j n; (T2-1) (T2-2) (T2-3) Suppose a -homomorphism h : C2 ! C1 maps d2 to d1. The following role inclusions in T1 ensure then that all the Za;0; : : : ; Za;n blocks but one can be mapped by h to the respective blocks Sa;0; : : : ; Sa;n in C1 (see Fig. 3): Sa;j v Za;j ; for a 2 and 0 j n: (T1-12) So, the only remaining block is Za;0; : : : ; Za;n such that d1 belongs to Ca in C1 (that is, the symbol a tentatively contained in this cell). Then the following role inclusions allow the sequence of Za;j to be mapped along the inverses of P in C1, but only if the same cell contains a in the preceding con guration (that is, the element n + 1 steps closer to the root in C1 belongs to Ca; see Fig. 3): P v Za;j ; for a 2 and 0 j n: (T1-13) Thus, the blocks Sb;0; : : : ; Sb;n act as `sinks' for the respective blocks Zb;0; : : : ; Zb;n from C2.
C2 C1
Note that the cell whose contents is changed generates the additional blocks Sa;0; : : : ; Sa;n to allow the respective blocks of Za;0; : : : ; Za;n from C2 to be sunk there (because there can be no match along the P -edges).
Step 3. It remains to encode the acceptance condition for the Turing machine M 0. To this end, we extend T2 with four blocks of roles: for each i = 0; : : : ; 3, we take role names Pi;0; : : : ; Pi;n and add to T2 the inclusions 9Pi;j 1 v 9Pi;j ; for 0 i The four blocks are arranged into an in nite tree-like structure by the following concept inclusions:
A v 9P0;0; 9P0;n v 9P1;0; 9P1;n v 9P3;0; 9P3;n v 9P1;0; 9P0;n v 9P2;0; 9P2;n v 9P3;0; 9P3;n v 9P2;0: More precisely, the P0;j block can be thought of as the root, from which two branches start with P1;j and P2;j blocks, respectively. Each of these blocks is followed by a P3;j block. Then we again have the P1;j and P2;j blocks, and so on. Such a pattern is required to represent con gurations of M 0 with alternating universal and existential states. (T2-4) (T2-5) (T2-6) (T2-7) P0;0
P0;1 0
P0;n C2 A C1 A
P1;0 P2;0
X1P1;1 X2P2;1 1 2
P1;n
P3;0 P3;1 P2;n
P3;0 P3;1 3 3
P3;n P3;n
P1;0 P2;0 P1;0 P2;0 X1 X2
X1 X2 X1
X2
We extend T1 with the following role inclusions:
P v Pi;j ; for 0 i 3 and 0 j n: (T1-14) Thus, each the initial P0;i block in C2 can be -homomorphically mapped into the initial P -block in C1 (see Fig. 4). Its successor must be a universal state, which is re ected by the two blocks, P1;j and P2;j , in C2. Both of these blocks should be -homomorphically mapped into C1. The following concept inclusions in T2 ensure that the P1;j block is mapped to the P -block that begins with X1 and the P2;j to the P -block that begins with X2: 9P1;0 v X1; 9P2;0 v X2; (T2-8) Each of the P1;j and P2;j blocks in C2 is followed by a P3;j block, which corresponds to an existential state: the P3;j block can be mapped to either of the two P -blocks (beginning with X1 or X2); see Fig. 4, where possible homomorphisms are shown by thick grey dashed arrows.
It remains to add to T2 concept inclusions making sure that each of the domain elements representing cells of the tape in a non-initial con guration belongs to the concept D, thus enforcing synchronisation of the cell contents: 9Pi;j v D; for 1 i
One can show now that T1 and T2 are as required: M accepts w i the canonical model C2 of K2 = (T2; fA(c)g) is nitely -homomorphically embeddable into the canonical model C1 of K1 = (T1; fA(c)g), where contains the concept and role names in T2. It remains to use Theorem 2 and the fact that APSpace = ExpTime.
Next, we show that -query inseparability is also ExpTime-hard. To this end, let be the signature of T2. Then we take T11 and T22 be to the `localised' TBoxes T1 and T2, respectively: namely, Tkk is the result of attaching the superscript k to each symbol (concept or role name) in the TBox Tk (such symbols are local for the respective TBox, that is, the signatures of T11 and T22 do not intersect). Then we take Tk to link those local symbols to the signature : each TTkk0 =coTnkksi[stTskof. aCllo ninscidluesriothnes porfotbhlee mforomf S-kquverSy,infosrepsayrmabbiollistySofin(T10;. fNAo1w(a,)lget) and (T10 [ T20; fA1(a); A2(a)g). Evidently, the canonical model of (T10; fA1(a)g) is contained in the canonical model of (T10 [ T20; fA1(a); A2(a)g). The converse query entailment is only possible if there is a -homomorphism from the canonical model of (T20; fA2(a)g) into the canonical model of (T10; fA1(a)g), which amounts to checking whether T2 is -query entailed by T1. q
The ExpTime lower bound for -query entailment in the case of OWL 2 QL TBoxes can be proved, using Theorem 3, by a minor modi cation of T1 and T2 above: for each of the role names R involved in T2 (and so in T1), we take a fresh role R0 and add an extra role inclusion R v R0 to the each of the two TBoxes; and take to include the concepts A, X1, X2 and the Ca, for a 2 , together with the newly introduced role names R0. Thus we obtain: Theorem 5. The -query entailment and -query inseparability problems for OWL 2 QL TBoxes are ExpTime-complete.
In this paper, we have proved that the -query entailment and inseparability
problems for both OWL 2 QL KBs and TBoxes are ExpTime-hard. This lower
bound is tight for OWL 2 QL TBoxes matching the upper bound previously
established in [