We design a temporal description logic, TQL, that extends the standard ontology language OWL 2 QL, provides basic means for temporal conceptual modelling and ensures rst-order rewritability of conjunctive queries for suitably de ned data instances with validity time. In this paper, we investigate the possibility of extending the current W3C standard language OWL 2 QL for ontology-based data access (OBDA) with temporal operators in a way preserving rst-order rewritability of conjunctive queries. Our ultimate aim is to understand the feasibility of OBDA for temporal data. In applications, instance data is often time-dependent: employment contracts come to an end, parliaments are elected, children are born. Temporal data can be modelled by pairs consisting of facts and their validity time; for example, givesBirth(diana; william; 1982). To query data with validity time, it would be useful to employ an ontology that provides a conceptual model for both static and temporal aspects of the domain of interest. Thus, when querying the fact above, one could use the knowledge that, if x gives birth to y, then x becomes a mother of y from that moment on: 3P givesBirth v motherOf;
(1) where 3P reads `sometime in the past.' OWL 2 QL does not support temporal conceptual modelling and, rather surprisingly, no attempt has yet been made to lift OBDA based on query rewriting to temporal ontologies and data.
Temporal extensions of DLs have been investigated since 1993; see [
The aim of this paper is to design a temporal DL that contains OWL 2 QL,
provides basic means for temporal conceptual modelling and, at the same time,
? This paper is an abridged version of the paper accepted for IJCAI 2013; omitted
proofs can be found in [
In conjunctive queries (CQs) over TQL knowledge bases, we allow timestamped predicates together with atoms of the form ( < 0) or ( = 0), where ; 0 are temporal constants denoting integers or variables ranging over integers.
Our main result is that, given a TQL TBox T and a CQ q, one can construct a union q0 of CQs such that the answers to q over T and any temporal ABox A can be computed by evaluating q0 over A extended with the temporal precedence relation < between the moments of time in A. For example, the query motherOf(x; y; t) over (1) can be rewritten as
motherOf(x; y; t) _ 9t0 (t0 < t) ^ givesBirth(x; y; t0) :
Note that the addition of the transitive relation < to the ABox is unavoidable:
without it, there is no rst-order rewriting even for the simple example above [
From a technical viewpoint, one of the challenges we are facing is that, in
contrast to known OBDA languages with CQ rewritability (including fragments
of datalog [
Roles S and concepts C of TQL are de ned by the grammar:
R ::= B ::= ? j ? j
Pi j
Pi ; Ai j 9R;
S ::= R C ::= B j j
S1 u S2 j
C1 u C2 j
3P S
3P C
j
j
3F S;
3F C;
where Pi is a role name, Ai a concept name (i 0), and 3P and 3F are temporal
operators `sometime in the past' and `sometime in the future,' respectively. We
call roles and concepts of the form R and B basic. A TQL TBox, T , is a nite
set of concept and role inclusions of the form C v B, S v R which are assumed
to hold globally (over the whole timeline). Note that the 3F=P -free fragment of
TQL is an extension of the description logic DL-LitehHorn [
and standard (atemporal) interpretations I(n) = ( I ; I(n)), for each n 2 Z. Thus, I 6= ; is the common domain of all I(n), aiI(n) 2 I , AiI(n) I and PiI(n) I I . We assume that aiI(n) = aiI(0), for all n 2 Z. To simplify presentation, we adopt the unique name assumption, that is, aiI(n) 6= ajI(n) for i 6= j (although the obtained results hold without it as the language has no number restrictions). The temporal constructs are interpreted in I as follows, where n 2 Z: (3P C)I(n) = fx j x 2 CI(m); for some m < ng; (3F C)I(n) = fx j x 2 CI(m); for some m > ng; (3P S)I(n) = f(x; y) j (x; y) 2 SI(m); for some m < ng; (3F S)I(n) = f(x; y) j (x; y) 2 SI(m); for some m > ng: The satisfaction relation j= is de ned as usual. If all inclusions in T and atoms in A are satis ed in I, we call I a model of K = (T ; A) and write I j= K.
A conjunctive query (CQ ) is a (two-sorted) rst-order formula q(x; s) = 9y; t '(x; y; s; t), where '(x; y; s; t) is a conjunction of atoms of the form Ai( ; ), Pi( ; ; ), ( = ) and ( < ), with , being individual terms |individual constants or variables in x, y|and , temporal terms |temporal constants or variables in t, s. In a positive existential query (PEQ) q, the formula ' can also contain _. A union of CQs (UCQ) is a disjunction of CQs (so every PEQ is equivalent to an exponentially larger UCQ).
Given a KB K = (T ; A) and a CQ q(x; s), we call tuples a ind(A) and n tem(A) a certain answer to q(x; s) over K and write K j= q(a; n), if I j= q(a; n) for any model I of K (understood as a two-sorted rst-order model). Example 1. Suppose Bob was a lecturer at UCL between times n1 and n2, after which he was appointed professor on a permanent contract. To model this situation, we use individual names, e1 and e2, to represent the two events of Bob's employment. The ABox will contain n1 < n2 and the atoms lect(bob; e1; n1), lect(bob; e1; n2), prof(bob; e2; n2 + 1). In the TBox, we make sure that everybody is holding the corresponding post over the duration of the contract, and include other knowledge about the university life:
We can now obtain sta who supervised PhDs between times k1 and k2 by posing the following CQ: 9y; t (k1 < t < k2) ^ Sta (x; t) ^ supervisesPhD(x; y; t) :
The key idea of OBDA is to reduce answering CQs over KBs to evaluating FO-queries over relational databases. To obtain such a reduction for TQL KBs, we employ a very basic type of temporal databases. With every TQL ABox A, we associate a data instance [A] that contains all atoms from A as well as the atoms (n1 < n2) such that n1; n2 2 Z with min tem(A) n1; n2 max tem(A) and n1 < n2. Thus, in addition to A, we explicitly include in [A] the temporal precedence relation over the convex closure of the time points that occur in A. (Note that, in standard temporal databases, the order over timestamps is built-in.) The main result of this paper is the following:
struct a UCQ q0(x; s) such that, for any consistent KB (T ; A) such that A contains all temporal constants from q, any a ind(A) and any n tem(A), we have (T ; A) j= q(a; n) i [A] j= q0(a; n).
Such a UCQ q0(x; s) is called a rewriting for q and T . Note that consistency checking can easily be reduced to CQ-answering. Indeed, let F be a fresh role name. Denote by T ? the result of replacing ? with F in all role inclusions of T and with 9F in all concept inclusions. Clearly, (T ?; A) is consistent for any ABox A, and (T ; A) is inconsistent i (T ?; A) j= q?, where q? = 9x; y; t F (x; y; t).
For an ABox A, we denote by AZ the in nite data instance which contains the atoms in A as well as all (n1 < n2) such that n1; n2 2 Z and n1 < n2. It will be convenient to regard CQs q(x; s) as sets of atoms, so that we can write, e.g., A( ; ) 2 q. We say that q is totally ordered if, for any temporal terms ; 0 in q, at least one of the constraints < 0, = 0 or 0 < is in q and the set of such constraints is consistent (in the sense that it can be satis ed in Z). Every CQ is equivalent to a union of totally ordered CQs (the empty union is ?).
for any ABox A containing all temporal constants from q, any a ind(A) and n tem(A), we have AZ j= q(a; n) i [A] j= q0(a; n).
Example 2. Let T = f3F C v A; 3P A v Bg and q(x; s) = B(x; s). Then, for any A, a 2 ind(A), n 2 tem(A), we have (T ; A) j= q(a; n) i AZ j= q0(a; n), where q0(x; s) = B(x; s) _ 9t (t < s)^A(x; t) _ 9t; r (t < s)^(t < r)^C(x; r) : Note, however, that q0 is not a rewriting for q and T . Take, for example, A = fC(a; 0)g. Then (T ; A) j= B(a; 0) but [A] 6j= q0(a; 0). A correct rewriting is obtained by replacing the last disjunct in q0 with 9r C(x; r); it can be computed by applying Lemma 1 to q0 and slightly simplifying the result.
In view of Lemma 1, from now on we will only focus on rewritings over AZ.
The problem of nding rewritings for CQs and TQL TBoxes can be reduced to the case where the TBoxes only contain inclusions of the following form: B1 u B2 v B; 3F B1 v B2; 3P B1 v B2; R1 u R2 v R; 3F R1 v R2; 3P R1 v R2: We say that such TBoxes are in normal form.
names) such that T 0 j= T and, for every model I of T , there exists a model of
Suppose now that we have a UCQ rewriting q0 for a CQ q and the TBox T 0 in Theorem 2. We obtain a rewriting for q and T simply by removing from q0 those CQs that contain symbols occurring in T 0 but not in T . From now on, we assume that all TQL TBoxes are in normal form. The set of role names in T and with their inverses is denoted by RT , while jT j is the number of concept and role names in T .
We begin the construction of rewritings by considering the case when all concept inclusions are of the form C v Ai, so existential quanti cation 9R does not occur in the right-hand side. TQL TBoxes of this form will be called at. Note that RDFS statements can be expressed by means of at TBoxes.
Let K = (T ; A) be a KB with a at TBox T (in normal form). Our rst aim is to construct a model CK of K, called the canonical model, for which the following theorem holds: Theorem 3. For any consistent K = (T ; A) with at T and any CQ q(x; s), we have K j= q(a; n) i CK j= q(a; n), for all tuples a ind(A) and n Z.
The construction uses a closure operator, cl, which applies the rules (ex), (c1){(c3), (r1){(r3) below to a set, S, of atoms of the form R(u; v; n), A(u; n), 9R(u; n) or (n < n0): (ex) If R(u; v; n) 2 S then add 9R(u; n), 9R (v; n) to S; (c1) if (B1 u B2 v B) 2 T and B1(u; n), B2(u; n) 2 S, then add B(u; n) to S; (c2) if (3P B v B0) 2 T , B(u; m) 2 S for some m < n and n occurs in S, then add B0(u; n) to S; (c3) if (3F B v B0) 2 T , B(u; m) 2 S for some m > n and n occurs in S, then add B0(u; n) to S; (r1) if (R1 u R2 v R) 2 T and R1(u; v; n); R2(u; v; n) 2 S, then add R(u; v; n) to S; (r2) if (3P R v R0) 2 T , R(u; v; m) 2 S for some m < n and n occurs in S, then add R0(u; v; n) to S; (r3) if (3F R v R0) 2 T , R(u; v; m) 2 S for some m > n and n occurs in S, then add R0(u; v; n) to S.
We set cl0(S) = S; cli+1(S) = cl(cli(S)); cl1(S) = [ i 0 cli(S): Note rst that K = (T ; A) is inconsistent i ? 2 cl1(AZ). If K is consistent, we de ne the canonical model CK of K by taking CK = ind(A), a 2 ACK(n) i A(a; n) 2 cl1(AZ), and (a; b) 2 P CK(n) i P (a; b; n) 2 cl1(AZ), for n 2 Z. (As T is at, atoms of the form 9R(u; n) can only be added by (ex).) This gives us Theorem 3. The following lemma shows that to construct CK we actually need only a bounded number of applications of cl that does not depend on A: Lemma 2. Let T be a at TBox and nT = (4 jT j)4. Then cl1(AZ) = clnT (AZ), for any ABox A.
We now use Lemma 2 to construct a rewriting for any at TBox T and CQ q(x; s). For a concept C and a role S, denote by C] and S] their standard FOtranslations: for example, (3F A)]( ; ) = 9t (( < t) ^ A( ; t)) and (9R)]( ; ) = 9y R( ; y; ). Now, given a PEQ ', we set '0# = ' and de ne, inductively, '(n+1)# as the result of replacing every { A( ; ) with A( ; ) _ W(CvA)2T (C]( ; ))n#, { P ( ; ; ) with P ( ; ; ) _ W(SvP )2T (S]( ; ; ))n#.
Finally, we set: extqT (x; s) = (q(x; s))nT #: Clearly, extqT (x; s) is a PEQ, and so can be equivalently transformed into a UCQ. By Theorem 3, Lemma 2 and Lemma 1, we obtain a rewriting for q and T :
KB (T ; A), any a ind(A) and n Z, (T ; A) j= q(a; n) i AZ j= extqT (a; n). 4
Canonical models for consistent KBs K = (T ; A) with not necessarily at TBoxes T (in normal form) can be constructed starting from AZ and using the rules given in the previous section together with the following one: (;) if 9R(u; n) 2 S and R(u; v; n) 2= S for any v, then add R(u; v; n) to S, for some fresh individual name v; in this case we write u ;nR v.
Denote by cl1 the closure operator under the resulting 8 rules. Again, K is inconsistent i ? 2 cl11(AZ). If K is consistent, we de ne the canonical model CK for K by the set cl11(AZ) in the same way as in Section 3 but taking the domain CK to contain all the individual names in cl11(AZ).
Theorem 5. For every consistent K = (T ; A) and every CQ q(x; s), we have K j= q(a; n) i CK j= q(a; n), for any tuples a ind(A) and n Z. Example 3. Let K = (T ; A) with A = fA(a; 0)g and
T = f A v 9R; 3P R v Q; 9Q v 9S; 3P Q v P; 3P S v S0 g: A fragment of the model CK is shown in the picture below: u2 u1
We say that the individuals a 2 ind(A) are of depth 0 in CK; now, if u is of depth d in CK and u ;nR v, for some n 2 Z and R, then v is of depth d + 1 in CK. Thus, both u1 and u2 in Example 3 are of depth 2 and v is of depth 1. The restriction of CK, treated as a set of atoms, to the individual names of depth d is denoted by CKd. Note that this set is not necessarily closed under the rule (;).
In the remainder of this section, we describe the structure of CK, which is required for the rewriting in the next section. We split CK into two parts: one consists of the elements in ind(A), while the other contains the fresh individuals introduced by (;). As this rule always uses fresh individuals, to understand the structure of the latter part it is enough to consider KBs of the form KT ;R = (T [ fA v 9Rg; fA(a; 0)g) with fresh A. We begin by analysing the behaviour of the atoms R0(a; u; n) entailed by R(a; u; 0), where a ;0R u.
v a
R A 0
S Q 1
S
S0 Q P 2 Lemma 3. Let a ;0R u in CKT ;R . If either m < n < 0 or 0 < n < m, then R0(a; u; n) 2 CKT ;R implies R0(a; u; m) 2 CKT ;R ; moreover, if n < m = jRT j or jRT j = m < n, then R0(a; u; m) 2 CKT ;R i R0(a; u; n) 2 CKT ;R .
The atoms R0(a; u; n) entailed by R(a; u; 0) in CKT ;R via (r1){(r3), also have an impact, via (ex), on the atoms of the form B(a; n) and B(u; n) in CKT ;R . Thus, in Example 3, R(a; v; 0) entails 9Q(a; n), for n > 0. To analyse the behaviour of such atoms, it is helpful to assume that T is in concept normal form (CoNF) in the following sense: for every role R 2 RT , the TBox T contains 9R v A0R; 3F 9R v AR1; 3F ARm v ARm 1; 3P 9R v A1R; 3P ARm v ARm+1; for 0 m
jRT j and some concepts AiR, and ARm v 9R0;
for all jmj jRT j and R0(a; v; m) 2 CKT ;R : AR3
AR2
AR1
0 AR
1 AR
2 AR
3
AR 9R (In Example 3, CK will contain the atoms A1R(a; n) and A2R(a; n + 1), for n 1.) By Lemma 3, if T is in CoNF, then we can compute the atoms B(a; n) and B(u; n) in CKT ;R without using the rules (r1){(r3). Lemma 3 also implies that we can add the inclusions above (with fresh AiR) to T if required, thereby obtaining a conservative extension of T ; so from now on we always assume T to be in CoNF. These observations enable the proof of the following two lemmas. The rst one characterises the atoms B(u; n) in CKT ;R : Lemma 4. Let a ;0R u in CKT ;R . If either m < n < 0 or 0 < n < m, then B(u; n) 2 CKT ;R implies B(u; m) 2 CKT ;R ; moreover, if either n < m = jT j or jT j = m < n, then B(u; m) 2 CKT ;R i B(u; n) 2 CKT ;R .
The second lemma characterises the ABox part of CK and is a straightforward generalisation of Lemma 2: Lemma 5. For any KB K = (T ; A) and any atom of the form A(a; n), 9R(a; n) or R(a; b; n), where a; b 2 ind(A) and n 2 Z, we have 2 CK i 2 clnT (AZ).
An obvious extension of the rewriting of Theorem 4 provides, for every CQ q(x; s), a UCQ extqT (x; s) of the appropriate length such that
CK0 j= q(a; n) i
AZ j= extqT (a; n); for all a ind(A); n
Z: (2) In particular, for every basic concept of the form 9R, we have 9R(a; n) 2 CK i AZ j= ext9TR(a; n), for all a 2 ind(A) and n 2 Z.
We now use the obtained results to show that one can nd all answers to
a CQ q over a TQL KB K by only considering a fragment of CK whose size
is polynomial in jT j and jqj. This property is called the polynomial witness
property [
Let q(x; s) be a CQ. Tuples a ind(A) and n tem(A) give a certain answer to q(x; s) over K = (T ; A) i there exists a homomorphism h from q to CK, which maps individual (temporal) terms of q to individual (respectively, temporal) terms of CK in such a way that the following conditions hold: h(x) = a and h(s) = n; h(b) = b and h(m) = m, for any individual and temporal constants b and m; and h(q) CK, where h(q) is the set of atoms obtained by replacing every term in q with its h-image, e.g., P ( ; ; ) with P (h( ); h( ); h( )) and ( 1 < 2) with h( 1) < h( 2). Now, using the monotonicity lemmas for the temporal dimension and the fact that the atoms of depth > jRT j in the canonical models duplicate atoms of smaller depth, we obtain
KB K = (T ; A), any CQ q(x; s) and any a ind(A) and n tem(A), we have K j= q(a; n) i there is a homomorphism h : q ! CK such that h(q) CKd;`, where d = f1(jT j; jqj) and ` = f2(jT j; jqj). 5
We now de ne a rewriting for any given CQ and TQL TBox. Suppose q(x; s) is a CQ and T a TQL TBox (in CoNF). Without loss of generality we assume q to be totally ordered. By a sub-query of q we understand any subset q0 q containing all temporal constraints ( < 0) and ( = 0) that occur in q. In the rewriting for q and T given below, we consider all possible splittings of q into two sub-queries (sharing the same temporal terms). One is to be mapped to the ABox part of the canonical model C(T ;A), and so we can rewrite it using (2). The other sub-query is to be mapped to the non-ABox part of C(T ;A) and requires a di erent rewriting. by TFohreoerveemry 6R. L2etRTh, bweeacomnastprufrcotmthae sseutb-CqKdu;T`e;rRy, qwhhere qd taondCKd`;T` a;Rrespurcohvitdheadt h(qh) CKd;T` ;R . Denote by Xh the set of individual terms in qh with h( ) = a, and let Yh be the remaining set of individual terms in qh. We call h a witness for R if { Xh contains at most one individual constant; { every term in Yh is an existentially quanti ed variable in q; { qh contains all atoms in q with a variable from Yh.
Let h be a witness for R. Denote by ; the union of all ;nR0 in CKd;T` ;R . Clearly, ; is a tree order on the individuals in CKd;T` ;R , with root a. Let Th be its minimal sub-tree containing a and the h-images of all the individual terms in qh. For each v 2 Th n fag, we take the (unique) moment g(v) with u ;gR(v) v, for some u and R, and set g(a) = 0. For A(y; ) 2 qh, we say that h(y) realises A(y; ). For any P ( ; 0; ) 2 qh, there are u; u0 2 Th with u ; u0 and fu; u0g = fh( ); h( 0)g; we say that u0 realises P ( ; 0; ). Let r be a list of fresh temporal variables ru, for u 2 Th n fag. Consider the following formula, whose free variables are ra and the temporal variables of qh: g(v) g(u)(ru; rv) ^ ^
h( ) g(u)(ru; ) ; u realises ( ; ) where the formulas n(t; s) say that t is at least n moments before s: that is, 0(t; s) is (t = s) and n(t; s) is 9s1; : : : ; sn 1(t < s1 < 9s1; : : : ; sjnj 1(t > s1 > < sn 1 < s); > sjnj 1 > s); if n > 0; if n < 0: Take a fresh variable xh and associate with h the formula wh = 9ra9xh ext9TR(xh; ra) ^
^ ( = xh) ^ th : h( )=a To give the intuition behind wh, suppose that C(T ;A) j=g wh, for some assignment g. Then g maps all terms in Xh to g(xh) 2 ind(A) such that 9R(g(xh); g(ra)) 2 C(T ;A), so (g(xh); g(ra)) is the root of a substructure of C(T ;A) isomorphic to CKT ;R in which the variables from Yh can be mapped according to h. For temporal terms, the formula th cannot specify the values prescribed by h: without : in UCQs, we can only say that is at least (not exactly) n moments before 0. However, by Lemmas 3 and 4, this is still enough to ensure that g and h give a homomorphism from qh to C(T ;A).
Example 4. Let T be the same as in Example 3 and let
q(x; t) = 9y; z; t0 (t < t0) ^ Q(x; y; t) ^ S0(y; z; t0) : The map h = fx 7! a; y 7! v; z 7! u1; t 7! 1; t0 7! 2g is a witness for R, with qh = q and wh is the following formula 9ra9xh ext9TR(xh; ra) ^ (xh = x) ^
We now de ne a rewriting for q(x; s) and T . Let T be the set of all witnesses for q and T . We call S T consistent if (Xh1 [ Yh1 ) \ (Xh1 [ Yh2 ) Xh1 \ Xh2 , for any distinct h1; h2 2 S. Assuming that y and t contain all the existentially quanti ed individual and temporal variables in q and q n S is the sub-query of q obtained by removing the atoms in qh, h 2 S, other than ( < 0) and ( = 0), we set: q (x; s) = 9y; t _
S T S consistent ^ wh ^ extqTnS : h2S
(T ; A) j= q(a; n) i AZ j= q (a; n).
Theorem 1 now follows by Lemma 1.
In this section, we show that the language TQL is nearly optimal as far as rewritability of CQs and ontologies is concerned.
We note rst, that the syntax of TQL allows concept inclusions and role inclusions; `mixed' axioms such as the datalog rule A(x; t) ^ R(x; y; t) ! B(x; t) are not expressible. The reason is that mixed rules often lead to non-rewritability, as is well known from E L. For example, for T = fA(y; t) ^ R(x; y; t) ! A(x; t)g, there is no FO-query q(x; t) such that (T ; A) j= A(a; n) i AZ j= q(a; n) since such a query has to express that at time-point t there is an R-path from x to some y with A(y; t).
Second, it would seem to be natural to extend TQL with the temporal
next/previous-time operators as concept or role constructs. However, again this
would lead to non-rewritability: any FO-rewriting for A(x; t) and the TBox
f P A v B; P B v Ag has to express that there exists n 0 such that
A(x; t 2n) or B(x; t (2n + 1)), which is impossible [
Another natural extension would be inclusions of the form A v 3F B. (Note
that inclusions of the form A v 9R:B are expressible in OWL 2 QL.) But again
such an extension would ruin rewritability. The reason is that temporal
precedence < is a total order, and so one can construct an ABox A and a UCQ
q(x) = q1 _ q2 such that (T ; A) j= q(a) but (T ; A) 6j= qi(a), i = 1; 2, for
T = fA v 3F Bg. Indeed, we can take A = fA(a; 0); C(a; 1)g and
q1(x) = 9t (C(x; t) ^ B(x; t));
q2(x) = 9t; t0 ((t < t0) ^ C(x; t) ^ B(x; t0)):
In fact, by reduction of 2+2-SAT [
data complexity. 7
In this paper, we have proved UCQ rewritability for conjunctive queries and TQL ontologies over data instances with validity time. Our focus was solely on the existence of rewritings, and we did not consider e ciency issues such as nding shortest rewritings, using temporal intervals in the data representation or mappings between temporal databases and ontologies. We only note here that these issues are of practical importance and will be addressed in future work. It would also be of interest to investigate the possibilities to increase the expressive power of both ontology and query language. For example, we believe that the extension of TQL with the next/previous time operators, which can only occur in TBox axioms not involved in cycles, will still enjoy rewritability. We can also increase the expressivity of conjunctive queries by allowing the arithmetic operations + and over temporal terms, which would make the CQ A(x; t) and the TBox f P A v B; P B v Ag rewritable in the extended language.