Temporal Description Logic for Ontology-Based Data Access

1 Introduction

One of the most promising and exciting applications of description logics (DLs) is to supply ontology languages and query answering technologies for ontology-based data access (OBDA), a way of querying incomplete data sources that uses ontologies to provide additional conceptual information about the domains of interest and enrich the query vocabulary. The current W3C standard language for OBDA is OWL2QL, which was built on the DL-Lite family of DLs [Calvanese et al., 2006; 2007]. To answer a conjunctive query q over an OWL2QL ontology T and instance data A, an OBDA system first 'rewrites' q and T into a new first-order query q′ and then evaluates q′ over A (without using the ontology). The evaluation task is performed by a conventional relational database management system. Finding efficient and practical rewritings has been the subject of extensive research [P´erez-Urbina et al., 2009; Rosati and Almatelli, 2010; Kontchakov et al., 2010; Chortaras et al., 2011; Gottlob et al., 2011; K¨onig et al., 2012]. Another fundamental feature of OWL2QL, supplementing its first-order rewritability, is the ability to capture basic conceptual data modelling constructs [Berardi et al., 2005; Artale et al., 2007].

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,

2Department of Computer Science and Information Systems Birkbeck, University of London, U.K.

one could use the knowledge that, if x gives birth to y, then x becomes a mother of y from that moment on:

where ♦P reads 'sometime in the past.' OWL2QL does not support temporal conceptual modelling and, rather surprisingly, no attempt has yet been made to lift the OBDA framework to temporal ontologies and data.

Temporal extensions of DLs have been investigated since 1993; see [Gabbay et al., 2003; Lutz et al., 2008; Artale and Franconi, 2005] for surveys and [Franconi and Toman, 2011; Guti´errez-Basulto and Klarman, 2012; Baader et al., 2012] for more recent developments. Temporalised DL-Lite logics have been constructed for temporal conceptual data modelling [Artale et al., 2010]. But unfortunately, none of the existing temporal DLs supports first-order rewritability.

The aim of this paper is to design a temporal DL that contains OWL2QL, provides basic means for temporal conceptual modelling and, at the same time, ensures first-order rewritability of conjunctive queries (for suitably defined data instances with validity time).

The temporal extension TQL of OWL2QL we present here is interpreted over sequences I(n), n ∈ Z, of standard DL structures reflecting possible evolutions of data. TBox axioms are interpreted globally, that is, are assumed to hold in all of the I(n), but the concepts and roles they contain can vary in time. ABox assertions (temporal data) are timestamped unary (for concepts) and binary (for roles) predicates that hold at the specified moments of time. Concept (role) inclusions of TQL generalise OWL2QL inclusions by allowing intersections of basic concepts (roles) in the left-hand side, possibly prefixed with temporal operators ♦P (sometime in the past) or ♦F (sometime in the future). Among other things, one can express in TQL that a concept/role name is rigid (or time-independent), persistent in the past/future or instantaneous. For example, ♦F♦PPerson ⊑ Person states that the concept Person is rigid, ♦PhasName ⊑ hasName says that the role hasName is persistent in the future, while givesBirth ⊓ ♦PgivesBirth ⊑ ⊥ implies that givesBirth is instantaneous. Inclusions such as ♦P Start⊓♦F End ⊑ Employed represent convexity (or existential rigidity) of concepts or roles. However, in contrast to most existing temporal DLs, we cannot use temporal operators in the right-hand side of inclusions (e.g., to say that every student will eventually graduate: Student ⊑ ♦F Graduate).

In conjunctive queries (CQs) over TQL knowledge bases, we allow time-stamped predicates together with atoms of the form (τ < τ ′ ) or (τ = τ ′ ), where τ, τ ′ 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 q′ of CQs such that the answers to q over T and any temporal ABox A can be computed by evaluating q′ 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

Note that the addition of the transitive relation < to the ABox is unavoidable: without it, there exists no first-order rewriting even for the simple example above [Libkin, 2004, Cor. 4.13].

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± [Cal`ı et al., 2012]), witnesses for existential quantifiers outside the ABox are not independent from each other but interact via the temporal precedence relation. For this reason, a reduction to known languages appears to be impossible and a novel approach to rewriting has to be found. We also observe that straightforward temporal extensions of TQL lose first-order rewritability. For example, query answering over the ontology {Student ⊑ ♦FGraduate} is shown to be non-tractable.

All omitted proofs can be found in [Artale et al., 2013].

2 TQL: a Temporal Extension of OWL2QL

Concepts C and roles S of TQL are defined by the grammar:

where Ai is a concept name, Pi a role name (i ≥ 0), and ♦P and ♦F are temporal operators 'sometime in the past' and 'sometime in the future,' respectively. We call concepts and roles of the form B and R basic. A TQL TBox, T , is a finite set of concept and role inclusions of the form

which are assumed to hold globally (over the whole timeline). Note that the ♦F/P -free fragment of TQL is an extension of the description logic DL-LiteHhorn [Artale et al., 2009] with role inclusions of the form R1 ⊓ · · · ⊓ Rn ⊑ R; it properly contains OWL 2QL (the missing role constraints can be safely added to the language).

A TQL ABox, A, is a (finite) set of atoms Pi(a, b, n) and Ai(a, n), where a, b are individual constants and n ∈ Z a temporal constant. The set of individual constants in A is denoted by ind(A), and the set of temporal constants by tem(A). A TQL knowledge base (KB) is a pair K = (T , A), where T is a TBox and A an ABox.

A temporal interpretation, I, is given by the ordered set (Z, <) of time points and standard (atemporal) interpretations I(n) = (∆I , ·I(n) ), for each n ∈ Z. Thus, ∆I ̸= ∅ is the common domain of all I(n), aI(n) i ∈ ∆I , AI(n) i ⊆ ∆I and P I(n) i ⊆ ∆I × ∆I . We assume that aI(n) i = aI(0) i , for all n ∈ Z. To simplify presentation, we adopt the unique name assumption, that is, aI(n) i ̸= aI(n) j for i ̸= j (although the obtained results hold without it). The role and concept constructs are interpreted in I as follows, where n ∈ Z:

⊥I(n) = ∅ (for both concepts and roles),

The satisfaction relation |= is defined by taking

If all inclusions in T and atoms in A are satisfied in I, we call I a model of K = (T , A) and write I |= K.

A conjunctive query (CQ) is a (two-sorted) first-order formula q(⃗x, ⃗s) = ∃⃗y, ⃗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 termstemporal 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 |= q(⃗a, ⃗n), if I |= q(⃗a, ⃗n) for every model I of K (understood as a two-sorted first-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 staff who supervised PhDs between times k1 and k2 by posing the following CQ:

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] which contains all atoms from A as well as the atoms (n1 < n2) such that ni ∈ Z with min tem(A) ≤ ni ≤ 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:

Theorem 2 Let q(⃗x,⃗s) be a CQ and T a TQL TBox. Then one can construct a UCQ q′ (⃗x,⃗s) such that, for any consistent KB (T ,A) such that A contains all temporal constants from q, any ⃗a ⊆ ind(A) and ⃗n ⊆ tem(A), we have (T ,A) |= q(⃗a, ⃗n) iff [A] |= q′ (⃗a, ⃗n).

Such a UCQ q′ (⃗x, ⃗s) is called a rewriting for q and T . We begin by showing how to compute rewritings for CQs over KBs with empty TBoxes.

For an ABox A, we denote by AZ the infinite data instance which contains the atoms in A as well as all (n1 < n2) such that n1, n2 ∈ 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(ξ, τ) ∈ q. We say that q is totally ordered if, for any temporal terms τ, τ ′ in q, at least one of the constraints τ < τ ′ , τ = τ ′ or τ ′ < τ is in q and the set of such constraints is consistent (in the sense that it can be satisfied in Z). Clearly, every CQ is equivalent to a union of totally ordered CQs (note that the empty union is ⊥).

Lemma 3 For every UCQ q(⃗x, ⃗s), one can compute a UCQ q′ (⃗x,⃗s) such that, for any ABox A containing all temporal constants from q and any ⃗a ⊆ ind(A), ⃗n ⊆ tem(A), we have

Proof. We assume that every CQ q0 in q is totally ordered. In each such q0, we remove a bound temporal variable t together with the atoms containing t if at least one of the following two conditions holds:

• there is no temporal constant or free temporal variable τ with (τ < t) ∈ q0, and for no temporal term τ ′ and atom of the form A(ξ, τ ′ ) or P (ξ, ζ, τ ′ ) in q0 do we have (τ ′ < t) or (τ ′ = t) in q0;
• the same as above but with < replaced by >.

It is readily checked that the resulting UCQ is as required. q

Example 4 Suppose T = {♦FC ⊑ A, ♦PA ⊑ B} and q(x, s) = B(x, s). Then, for any A, a ∈ ind(A), n ∈ tem(A), we have (T , A) |= q(a, n) iff AZ |= q′ (a, n), where

Note, however, that q′ is not a rewriting for q and T . Take, for example, A = {C(a, 0)}. Then (T ,A) |= B(a, 0) but [A] ̸|= q′ (a, 0). A correct rewriting is obtained by replacing the last disjunct in q′ with ∃r C(x, r); it can be computed by applying Lemma 3 to q′ and slightly simplifying the result.

In view of Lemma 3, from now on we will only focus on rewritings over AZ .

The problem of finding rewritings for CQs and TQL TBoxes can be reduced to the case where the TBoxes only contain inclusions of the form

We say that such TBoxes are in normal form.

Theorem 5 For every TQL TBox T , one can construct in polynomial time a TQL TBox T ′ in normal form (possibly containing additional concept and role names) such that T ′ |= T and, for every model I of T , there exists a model of T ′ that coincides with I on all concept and role names in T .

Suppose now that we have a UCQ rewriting q′ for a CQ q and the TBox T ′ in Theorem 5. We obtain a rewriting for q and T simply by removing from q′ those CQs that contain symbols occurring in T ′ 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 |T | 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 ⊑ Ai, so existential quantification ∃R does not occur in the right-hand side. TQL TBoxes of this form will be called flat. Note that RDFS statements can be expressed by means of flat TBoxes.

3 UCQRewriting for Flat TBoxes

Let K = (T ,A) be a KB with a flat TBox T (in normal form). Our first aim is to construct a model CK of K, called the canonical model, for which the following theorem holds:

Theorem 6 For any consistent KB K = (T ,A) with flat T and any CQ q(⃗x, ⃗s), we have K |= q(⃗a, ⃗n) iff CK |= 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), ∃R(u, n) or (n < n′ ); cl(S) is the result of (non-recursively) applying those rules to S,

• (ex) If R(u, v, n) ∈ S then add ∃R(u, n), ∃R-(v, n) to S;
• (c1) if (B1 ⊓ B2 ⊑ B) ∈ T and B1(u, n), B2(u, n) ∈ S, then add B(u, n) to S;
• (c2) if (♦PB ⊑ B′ ) ∈ T , B(u,m) ∈ S for somem< n and n occurs in S, then add B′ (u, n) to S;
• (c3) if (♦FB ⊑ B′ ) ∈ T , B(u,m) ∈ S for somem> n and n occurs in S, then add B′ (u, n) to S;
• (r1) if (R1 ⊓R2 ⊑ R) ∈ T and R1(u, v, n), R2(u, v, n) are in S, then add R(u, v, n) to S;

• (r2) if (♦PR ⊑ R′ ) ∈ T , R(u, v,m) ∈ S for some m < n and n occurs in S, then add R′ (u, v, n) to S;
• (r3) if (♦FR ⊑ R′ ) ∈ T , R(u, v,m) ∈ S for some m > n and n occurs in S, then add R′ (u, v, n) to S.

Note first that K = (T ,A) is inconsistent iff ⊥ ∈ cl∞(AZ ). If K is consistent, we define the canonical model CK of K by taking ∆CK = ind(A), a ∈ ACK(n) iff A(a, n) ∈ cl∞(AZ ), and (a, b) ∈ P CK(n) iff P(a, b, n) ∈ cl∞(AZ ), for n ∈ Z. (As T is flat, atoms of the form ∃R(u, n) can only be added by (ex).) This gives us Theorem 6. The following lemma shows that to construct CK we actually need only a bounded number of applications of cl which does not depend on A:

Proof. It is not hard to see that cl∞(S) can be obtained by first exhaustively applying (r1)-(r3), then (ex), and after that (c1)-(c3). Since no recursion of (ex) is needed, it is sufficient to bound the recursion depth for applications of (r1)-(r3) and (c1)-(c3) separately. As both behave similarly, we focus on (r1)-(r3). One can show that it is enough to consider ABoxes with two individuals, say a and b, and it is not difficult to find a bound for the recursion depth of the separated rule sets (r1), (r2) and, respectively, (r1), (r3); the interesting part of the analysis is how often one has to alternate between applications of (r1), (r2) and applications of (r1), (r3). The key observation here is that each alternation introduces a fresh cross over (i.e., a pair (R1,R2) of roles such that there are m1,m2 ∈ Z with m1 + 1 ≥ m2, R1(a, b, n) ∈ S for all n ≤ m1, and R2(a, b, n) ∈ S for all n ≥ m2). The number of such cross overs is bounded by |T |2 , and so the number of required alternations between exhaustively applying (r1), (r2) and (r1), (r3) is bounded by |T |2 . q

We now use Lemma 7 to construct a rewriting for any flat TBox T and CQ q(⃗x, ⃗s). For a concept C and a role S, denote by C ♯ and S♯ their standard FO-translations; for example, (♦FA)♯ (ξ, τ) = ∃t ((τ < t) ∧ A(ξ, t)) and (∃R)♯ (ξ, τ) = ∃yR(ξ, y, τ). Now, given a PEQ ϕ, we set ϕ0↓ = ϕ and define, inductively, ϕ(n+1)↓ as the result of replacing every

Finally, we set

Clearly, extTq (⃗x, ⃗s) is a PEQ, and so can be equivalently transformed into a UCQ. Denote by T ⊥ the result of replacing ⊥ with a fresh concept name, say F, in all concept inclusions and with a fresh role name, say Q, in all role inclusions of T . Clearly (T ⊥,A) is consistent for any ABox A. Let q⊥ = (∃x, t F(x, t)) ∨ (∃x, y, tQ(x, y, t)). By Theorem 6 and Lemma 7, we obtain:

Theorem 8 Let T be a flat TBox and q(⃗x, ⃗s) a CQ. Then, for any consistent KB (T , A), any ⃗a ⊆ ind(A) and ⃗n ⊆ Z,

Thus, we obtain a rewriting for q and T using Lemma 3.

4 Canonical Models for Arbitrary TBoxes

Canonical models for consistent KBs K = (T ,A) with not necessarily flat 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 ∃R(u, n) ∈ S and R(u, v, n) /∈ 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 iff ⊥ ∈ cl∞1 (AZ ). If K is consistent, we define the canonical model CK for K by the set cl∞1 (AZ ) in the same way as in Section 3 but taking the domain ∆CK to contain all the individual names in cl∞1 (AZ ).

Theorem 9 For every consistent K = (T , A) and every CQ q(⃗x,⃗s), we have K |= q(⃗a, ⃗n) iff CK |= q(⃗a, ⃗n), for any tuples ⃗a ⊆ ind(A) and ⃗n ⊆ Z.

Example 10 Let K = (T , A) with A = {A(a, 0)} and T = {A ⊑ ∃R, ♦PR ⊑ Q, ∃Q- ⊑ ∃S, ♦PQ ⊑ P, ♦PS ⊑ S′}.

A fragment of the model CK is shown in the picture below:

We say that the individuals a ∈ ind(A) are of depth 0 in CK; now, if u is of depth d in CK and u ⇝nR v, for some n ∈ Z and R, then v is of depth d + 1 in CK. Thus, both u1 and u2 in Example 10 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 C dK. 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 ∪ {A ⊑ ∃R}, {A(a, 0)}) with fresh A. We begin by analysing the behaviour of the atoms R′ (a, u, n) entailed by R(a, u, 0), where a ⇝0R u.

Lemma 11 (monotonicity) Let a ⇝0R u in CKT ,R . If either m < n < 0 or 0 < n < m, then R′ (a, u, n) ∈ CKT ,R implies R′ (a, u,m) ∈ CKT ,R ; moreover, if n < m = -|RT | or |RT | = m < n, then R′ (a, u, n) ∈ CKT ,R iff R′ (a, u, m) ∈ CKT ,R .

The atoms R′ (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 10, R(a, v, 0) entails ∃Q(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 ∈ RT , the TBox T contains

for 0 ≤ m ≤ |RT | and some concepts AiR, and

(In Example 10, CK will contain the atoms A1R(a, n) and A2R(a, n + 1), for n ≥ 1.) By Lemma 11, 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 11 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 first one characterises the atoms B(u, n) in CKT ,R :

Lemma 12 (monotonicity) Let a ⇝0R u in CKT ,R . If either m < n < 0 or 0 < n < m, then B(u, n) ∈ CKT ,R implies B(u,m) ∈ CKT ,R ; moreover, if either n < m = -|T | or |T | = m < n, then B(u, n) ∈ CKT ,R iff B(u, m) ∈ CKT ,R .

The second lemma characterises the ABox part of CK and is a straightforward generalisation of Lemma 7:

Lemma 13 For any KB K = (T , A) and any atom α of the form A(a, n), ∃R(a, n) or R(a, b, n), where a, b ∈ ind(A) and n ∈ Z, we have α ∈ CK iff α ∈ clnT (AZ ).

An obvious extension of the rewriting of Theorem 8 provides, for every CQ q(⃗x,⃗s), a UCQ extTq (⃗x,⃗s) such that for all ⃗a ⊆ ind(A) and ⃗n ⊆ Z of the appropriate length,

Moreover, for a basic concept ∃R, we find a UCQ extT∃R(ξ, τ ) such that, for any a ∈ ind(A) and n ∈ Z, ∃R(a, n) ∈ CK iff AZ |= extT∃R(a, n).

We now use the obtained results to show that one can find all answers to a CQ q over a TQL KB K by only considering a fragment of CK whose size is polynomial in |T | and |q|. This property is called the polynomial witness property [Gottlob and Schwentick, 2011]. Denote by C d,ℓ K , for d, ℓ ≥ 0, the restriction of C dK to the moments of time in the interval [min tem(A) - ℓ, max tem(A) + ℓ].

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) iff there is 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:

where h(q) denotes the set of atoms obtained by replacing every term in q with its h-image, e.g., P(ξ, ζ, τ) with P(h(ξ), h(ζ), h(τ)), (τ1 < τ2) with h(τ1) < h(τ2), etc.

Now, using the monotonicity lemmas for the temporal dimension and the fact that atoms of depth > |RT | in the canonical models duplicate atoms of smaller depth, we obtain Theorem 14 There are polynomials f1 and f2 such that, for any consistent TQL KB K = (T , A), any CQ q(⃗x, ⃗s) and any ⃗a ⊆ ind(A) and ⃗n ⊆ tem(A), we have K |= q(⃗a, ⃗n) iff there is a homomorphism h : q → CK such that h(q) ⊆ C d,ℓ K , where d = f1(|T |, |q|) and ℓ = f2(|T |, |q|).

We are now in a position to define a rewriting for any given CQ and TQL TBox.

5 UCQRewriting

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 q′ ⊆ q containing all temporal constraints (τ < τ ′ ) and (τ = τ ′ ) 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 nonABox part of C(T ,A) and requires a different rewriting.

For every R ∈ RT , we construct the set C d,ℓ KT ,R , where d and ℓ are provided by Theorem 14. Let h be a map from a subquery qh ⊆ q to C d,ℓ KT ,R such that h(qh) ⊆ C d,ℓ KT ,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 a quantified 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 ⇝nR′ in C d,ℓ KT ,R . Clearly, ⇝ is a tree order on the individuals in C d,ℓ KT ,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 ∈ Th \ {a}, we take the (unique) moment g(v) with u ⇝g(v) R v, for some u and R, and set g(a) = 0. For A(y, τ) ∈ qh, we say that h(y) realises A(y, τ). For any P(ξ, ξ ′ , τ) ∈ qh, there are u, u′ ∈ Th with u ⇝ u′ and {u, u′ } = {h(ξ), h(ξ ′ )}; we say that u′ realises P(ξ, ξ ′ , τ). Let ⃗r be a list of fresh temporal variables ru, for u ∈ Th\{a}. Consider the following formula, whose free variables are ra and the temporal variables of qh:

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

Take a fresh variable xh and associate with h the formula

To give the intuition behind wh, suppose that C(T ,A) |=g wh, for some assignment g. Then g maps all terms in Xh to g(xh) ∈ ind(A) such that ∃R(g(xh), g(ra)) ∈ 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 τ ′ . However, by Lemmas 11 and 12, this is still enough to ensure that g and h give a homomorphism from qh to C(T ,A).

Example 15 Let T be the same as in Example 10 and let

The map h = {x ↦→ a, y ↦→ v, z ↦→ u1, t ↦→ 1, t′ ↦→ 2} is a witness for R, with qh = q and wh is the following formula

We can now define a rewriting for q(⃗x,⃗s) and T . Let T be the set of all witnesses for q and T . We call a subset S ⊆ T consistent if (Xh1 ∪Yh1 )∩(Xh1 ∪Yh2 ) ⊆ Xh1 ∩Xh2 , for any distinct h1, h2 ∈ S. Assuming that ⃗y contains all the quantified variables in q and q \ S is the sub-query of q obtained by removing the atoms in qh, h ∈ S, other than (τ < τ ′ ) and (τ = τ ′ ), we set:

Theorem 16 Let T be a TQL TBox in CoNF and q(⃗x,⃗s) a totally ordered CQ. Then, for any consistent KB (T ,A) and any tuples ⃗a ⊆ ind(A) and ⃗n ⊆ Z,

Theorem 2 now follows by Lemma 3.

6 Non-Rewritability

In this section, we show that the language TQL is nearly optimal as far as rewritability of CQs and ontologies is concerned.

We note first, 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 the DL EL. For example, there does not exist an FO-query q(x, t) such that (T ,A) |= A(a, n) iff AZ |= q(a, n) for T = {A(y, t) ∧ R(x, y, t) → A(x, t)} 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 {©PA ⊑ B, ©PB ⊑ A} has to express that there exists n ≥ 0 such that A(x, t - 2n) or B(x, t - (2n + 1)), which is impossible [Libkin, 2004].

Another natural extension would be inclusions of the form A ⊑ ♦FB. (Note that inclusions of the form A ⊑ ∃R.B are expressible in OWL2QL.) 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) |= q(a) but (T ,A) ̸|= qi(a), i = 1, 2, for T = {A ⊑ ♦FB}. Indeed, we take A = {A(a, 0), C(a, 1)} and

In fact, by reduction of 2+2-SAT [Schaerf, 1993], we prove the following:

Theorem 17 Answering CQs over the TBox {A ⊑ ♦FB} is CONP-hard for data complexity.

7 RelatedWork

The Semantic Web community has developed a variety of extensions of RDF/S and OWL with validity time [Motik, 2012; Pugliese et al., 2008; Gutierrez et al., 2007]. The focus of this line of research is on representing and querying time stamped RDF triples or OWL axioms. In contrast, in our language only instance data are time stamped , while the ontology formulates time independent constraints that describe how the extensions of concepts and roles can change over time. In the temporal DL literature, a similar distinction has been discussed as the difference between temporalised axioms and temporalised concepts/roles; the expressive power of the respective languages is incomparable [Gabbay et al., 2003; Baader et al., 2012].

In Theorem 8, we show rewritability using boundedness of recursion. This connection between first-order definability and boundedness is well known from the datalog and logic literature where boundedness has been investigated extensively [Gaifman et al., 1987; van der Meyden, 2000; Kreutzer et al., 2007]. Grohe and Schwandtner [2009] investigate boundedness for datalog programs on linear orders; the results are different from ours since the linear order is the only predicate symbol of the datalog programs considered and no further restrictions (comparable to ours) are imposed.

8 Conclusion

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 efficiency issues such as finding 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 {©PA ⊑ B, ©PB ⊑ A} rewritable in the extended language.