Querying ATSQL databases with temporal logic.
We establish a correspondence between temporal logic and a subset of ATSQL, a temporal extension of SQL-92. In addition, we provide an effective translation from temporal logic to ATSQL that enables a user to write high-level queries which are then evaluated against a space-efficient representation of the database. A reverse translation, also provided in this paper, characterizes the expressive power of a syntactically defined subset of ATSQL queries.
Introduction
This paper brings together two research directions in temporal databases. The first direction is concerned
with temporal extensions to practical query languages such as SQL [Gad93, NA93, Sar93].
The issues addressed include space-efficient storage, effective implementation techniques and handling
of large amounts of data. This direction includes ATSQL [SJB95], the integration of ideas
from TSQL2 [Sno95] and ChronoLog [B-oh94]. The second direction of research focuses on high-level
query languages for temporal databases based on temporal logic [TC90, GM91, CCT94]. The
advantages of using a logic-based query language come from their well-understood mathematical
properties [GHR94]. The declarative character of these languages also allows the use of advanced
optimization techniques. In addition, temporal logic has been proposed as the language of choice
for formulating temporal integrity constraints and triggers [Cho95, CT95, GL96, LS87, SW95], admitting
space-efficient methods for enforcing these constraints.
While temporal logic may seem to be a natural choice for a temporal query language, its semantics
is defined with respect to abstract temporal databases: time-instant-indexed sequences of database
states [GHR94]. This point of view has often disqualified temporal logic as a practical temporal query
language: For efficiency reasons we can not construct and store all the individual states explicitly
(this is indeed impossible if the sequence is not finite). Therefore most of the practical proposals
associate a concise encoding of a set of time instants at which a particular fact holds with the tuple
representing this fact. The encoding is commonly realized by a period 1 [NA93, Sar90, Sno87, Tan86]
or a temporal element-a finite union of periods [CC87, Gad88, Sno95].
The contributions of this paper are twofold. First, we develop a translation of temporal logic to
ATSQL. This translation allows the users to take advantage of a high-level declarative language while
queries are still efficiently evaluated over compactly represented ATSQL temporal databases that
use period encodings. The translation also dispels the myth of logic-based temporal query languages
being inherently inefficient: The approach presented in this paper shows that queries expressed in
temporal logic can be evaluated as efficiently as queries in any of the practical approaches mentioned
above. We also develop a syntactic criterion that guarantees safety of queries in temporal logic and
is broad enough to contain the equivalents of all domain-independent queries. Second, we present a
reverse translation of a syntactically defined subset of ATSQL, to clarify the expressiveness picture.
Although we use ATSQL as the domain of the reverse translation, our results apply, with minor
adjustments, to any other temporal query language that uses a distinguished period-valued attribute
to represent valid time for facts stored in the database and enforces coalescing on the encoding .
The paper is organized as follows: We start with a discussion of the basic framework in Section 2,
including the syntax and semantics of temporal logic and ATSQL (in the case of ATSQL we introduce
only constructs relevant to the development in this paper; for a full description see [SJB95]). In
Section 3 we give the mapping from temporal logic to ATSQL. We conclude the section with an
example and the discussion of some implementation issues. In Section 4 we discuss the reverse
mapping and relate the expressive power of (a subset of) ATSQL and temporal logic. Section 5
discusses the relations to other temporal query languages including the impact of the presented
results.
2 Basic framework
Before we start comparing temporal logic and ATSQL we need to set up a common formal framework
suitable to both languages. In this paper we fix the structure of time to be integer-like: linear (totally
discrete, unbounded in both the past and the future. However, our approach can be easily
adopted to other structures of time, e.g., bounded in the past (natural numbers like time), or dense
(rational-like time). The proposed mapping changes in only minor ways to accommodate such
extensions. We also assume a single, fixed time granularity (one year).
All the references to time in this paper represent the valid-time references capturing the relationship
between individual time points and validity of facts in reality [JCE + 94]. In particular, the
transaction time, which relates when facts are stored in the database, is not considered. (This is
because the standard temporal logic can only deal with a single temporal dimension.)
Finally, we restrict the discussion to the point-based view of a temporal database-the view
adopted by temporal logic. As ATSQL is period-based we use coalescing to enforce strictly point-based
semantics. Coalescing is a unary operation on ATSQL temporal relations that merges value-equivalent
tuples with adjacent or overlapping periods into a single tuple [BSS96]. Throughout, we
make sure that base relations as well as intermediate relations are coalesced.
2.1 Temporal logic
Temporal logic is an abstract query language, a language defined with respect to the class of abstract
temporal databases [Cho94, CT98]. An abstract temporal database, in turn, is a database which cap-
1 In this paper we use the term 'period' rather than the term `interval' commonly used in temporal logic because
the latter term conflicts with the SQL INTERVALs, which are unanchored durations, such as 3 months.
tures the formal semantics of a temporal database without considering any particular representation
issues.
It is possible to view an abstract temporal database in several different but equivalent ways. We
choose here the snapshot view [Cho94] in which every time instant is associated with a (finite) set
of facts that hold at it. For integer-like time, abstract temporal databases can be viewed as infinite
sequences of finite database states of the form
Example 2.1 Figure 1 presents an example of an abstract temporal database, viewed as a sequence
of states. The database represents information about Eastern European history, modeling the independence
of various countries [Cho94]. Each fact indicates an independent nation and its capital.
This relation is used as a running example throughout the paper.
Year Timeslice

Figure

1: Eastern European history: the abstract temporal database
Syntax. First-order temporal logic (FOTL) extends first order logic with binary temporal connectives
since and until, and unary connectives 5 ("previous" or "yesterday") and 4 ("next" or
"tomorrow"). Informally, A since B is true in a state if A is true for states between when B was
true and now (this state). A until B is true in a state if A will be true into the future until B will
be true. The rest of the usual temporal connectives can be defined in terms of these, e.g.,
true since A A was true sometime in the past
A will be true sometime in the future
was true always in the past
will be true always in the future
In the rest of this paper we also consider the universal quantifier (8X)A to be a shorthand for
:(9X):A, the implication A ! B a shorthand for :A - B, etc.
Example 2.2 Our first example is a query which does not relate different database states. The
query
determines all years when Poland but not Slovakia was an independent country, i.e., the times when
the query evaluates to true.
Example 2.3 The second example relates different database states. The query
returns the name of the city that superseded Cracow as Poland's capital and the years when this
city was the capital.
Example 2.4 Consider the query [Cho94, p.515] "list all countries that lost and regained indepen-
dence" over the abstract temporal database shown in Figure 1. This is formulated in temporal logic
as:
For a country and a year to result, the country will have been independent in the past, will be
independent in the future, but is currently not independent.
Formally, the semantics of the temporal logic queries is defined as follows:
Definition 2.5 An abstract temporal database is an integer indexed sequence of database states
Every database state D i contains a relation (relation instance)
r for each relation schema R. We define the semantics of temporal logic formulas in terms of a
satisfaction relation j= and a valuation - (a valuation is a mapping from variables to constants):
is the result of applying - to variables of R,
is a valuation identical to
- except that it maps X to c,
An answer to a temporal logic query ' in D is the set 'g. Thus, temporal
logic may be viewed as a natural extension of relational calculus.
As indicated by the example queries, temporal logic provides a convenient means for expressing
rather involved English queries in a natural way. However, the state-based semantics of temporal
logic does not suggest an efficient implementation of such queries. Any implementation taking
advantage of a compact period-based representation of temporal databases promises much better
performance.
2.2 ATSQL
ATSQL [SJB95] is a further development of TSQL2, a temporal extension of SQL-92. An early
version of ATSQL has been proposed to the ISO international committee for standardization for
incorporation into the SQL/Temporal standard, and implemented. Therefore, we use it as the
target query language of our translation.
ATSQL Databases. A period is a pair [a; b] where a is the left endpoint and b the right endpoint .
The period [a; b] is used to encode the set of instants ft ja - t - bg. A valid-time relation is a
finite relation where tuples are implicitly timestamped with periods. A ATSQL database is a finite
collection of valid-time relations. Figure 2 shows an ATSQL database that encodes the abstract
temporal database shown in Figure 1. Remember that throughout the paper we assume that all
indep
Country Capital VALID
Czech Kingdom Prague [1198; 1620]
Czechoslovakia Prague [1918; 1938]
Czechoslovakia Prague [1945; 1992]
Czech Republic Prague [1993; 1]
Slovakia Bratislava [1940; 1944]
Slovakia Bratislava [1993; 1]
Poland Gniezno [1025; 1039]
Poland Cracow [1040; 1595]
Poland Warsaw [1596; 1794]
Poland Warsaw [1918; 1938]
Poland Warsaw [1945; 1]

Figure

2: Eastern European history: the concrete ATSQL relation
the ATSQL temporal relations are coalesced: The timestamps are represented by maximal non-overlapping
periods. This assumption is fundamental for our translation of temporal logic queries
to ATSQL to work correctly.
ATSQL Queries. ATSQL extends the query language of SQL-92 [MS93]. The crucial concepts in
ATSQL are statement modifiers (or flags) that can be prepended to queries to modify their temporal
behavior . As a consequence ATSQL queries come in three flavors:
1. SQL-92 queries (without any additional flags) are executed on the temporal database with
respect to the current time instant (now).
2. SQL-92 queries preceded by the SEQUENCED VALID flag are evaluated relative to every snapshot
of the temporal database; the results are then collected in a temporal relation with timestamps
corresponding to the evaluation point (cf. snapshot reducibility [SJB95]).
3. SQL-92 queries preceded by the NONSEQUENCED VALID flag: in this case the processing of the
timestamps is completely controlled by the query, rather than by some implicit mechanism
of the underlying DBMS. In other words, the enclosed statement is executed with standard
semantics. Timestamps are treated like all other attributes and no built-in temporal
processing is performed. The manipulation of timestamps is made explicit using the following
constructs:
ffl given a period p, BEGIN(p) denotes the start point of p and END(p) the endpoint of p.
We often use shorthands respectively, to denote the endpoints.
ffl given two time points b and e, b - e, PERIOD(b,e) denotes the period constructed out of
two time points (instants). Again, we often use a shorthand [b; e].
ffl we use integer constants to denote time instants (e.g., 1998 stands for the year 1998). We
also include constants denoting the start of time, TIMESTAMP 'beginning' or \Gamma1, and
the end of time, TIMESTAMP 'forever' or 1.
ffl to dislocate a given time point, t by one year 2 we In similar fashion we can
dislocate periods: to dislocate period by one year we resulting
period is [b
ffl finally, we use FIRST(t,s) and LAST(t,s) to find the earlier and later, respectively, point
of t and s.
The above syntax is used to manipulate timestamps in ATSQL select-blocks. First, we need
to gain access to the implicit valid-time attributes of ATSQL relations: VTIME(R) denotes
the timestamp associated with the range variable (tuple in the relation) R and substitutes for
the lack of explicit temporal attributes. The WHERE clause uses temporal built-in predicates
to specify temporal relationships between periods. While all the relationships between two
periods can be expressed using order relationships on their endpoints, ATSQL also supports
Allen algebra-like comparisons of pairs of periods (which we won't use further in this paper).
To be consistent with SQL2, these relationships have a somewhat different meaning than the
identically-named relationships in [All83]:
It is easy to see that the above relationships (and their Boolean combinations) can express
all period relationships of [All83] and thus all possible topological relationships between two
periods. Metric relationships can be captured using the above timestamp constructs. Finally,
the SET VALID p clause, which is part of the NONSEQUENCED VALID statement modifier and
precedes the actual query, defines p to be the resulting timestamp period for all tuples in the
answer to the query (p is usually a function of the VTIME(R) attributes).
In addition every query or table reference can be followed by a (VALID) flag to enforce coalescing
of the corresponding temporal table, that is, tuples with identical explicit attribute values whose
valid-times overlap or are adjacent are merged into a single tuple, with a period equal to the union
of the periods of the original tuples. As a side-effect, duplicates are eliminated.
Example 2.6 In order to determine the name of the city that superseded Cracow as Poland's
capital (cf. Example 2.3), the query has to relate different database states. In ATSQL this means
that we have to specify the VALID clause and the required temporal relationship. This results in the
following ATSQL query:
NONSEQUENCED VALID
SELECT i1.Capital
FROM indep(VALID) AS i1, indep(VALID) AS i2
2 In this paper we assume that the valid-time uses granularity of a year. Thus +1 is shorthand for +INTERVAL '1'
YEAR and -1 for -INTERVAL '1' YEAR.
Example 2.7 The formulation of a query becomes even simpler if it can be answered by looking at
single snapshots. In this case the user simply specifies sequenced semantics when formulating a query,
as illustrated in the following query, which determines all periods when Poland was independent but
not Slovakia (cf. Example 2.2):
SELECT i1.Country
FROM indep(VALID) AS i1
AND NOT EXISTS ( SELECT *
FROM indep(VALID) AS i2
The proposed translation uses both the SEQUENCED VALID variant of the ATSQL queries (to translate
the first-order fragments of the temporal logic queries) and the NONSEQUENCED VALID queries (to
translate the temporal connectives).
Mapping Temporal Logic to ATSQL
In this section we introduce the main result of this paper: the translation of queries formulated
in temporal logic to ATSQL. Similarly to mapping relational calculus queries to SQL, our translation
has to identify a syntactic subset of domain-independent temporal queries that can be safely
translated to ATSQL. The syntactic criterion is based on an extension of the criterion presented in
[AHV95]. However, our approach can be analogously used in more complicated translations, e.g.,
[VGT91]. We discuss several possible refinements in Section 3.5.
3.1 Correspondence of Temporal Databases
Before we can describe the actual mapping of temporal formulas to ATSQL we need to establish
a relationship between temporal databases (over which the semantics of temporal logic queries is
defined) and ATSQL databases, the target of our translation.
Definition 3.1 Let be an abstract temporal database. The support of a
temporal logic formula ' under a valuation - is the set of time instants
The support for ground formulas (facts in particular) does not depend on the valuation. In this way
the definition of the support yields the definition of the class of abstract temporal databases we are
interested in:
Definition 3.2 An abstract temporal database is finitary if it contains a finite number of facts and
the support of every fact can be represented as a finite union of periods.
Not every abstract temporal database is finitary. For example, the database that contains a single
fact p(a) in every even-numbered state and whose every odd-numbered state is empty cannot be
finitely represented by a union of periods. On the other hand, the class of finitary temporal databases
captures exactly all ATSQL databases.
Proposition 3.3 Every ATSQL database represents a unique finitary abstract temporal database
and every finitary abstract temporal database can be represented as an ATSQL database.
In the rest of the paper we use k:k to denote the mapping of ATSQL databases to the corresponding
finitary abstract temporal databases.
3.2 Domain Independence and Range Restriction
The actual translation of temporal logic queries to ATSQL is based on the semantic rules in Definition
2.5. However, there is a problem with a direct use of these rules: the interpretation of
variables is relative to a potentially infinite universe of data values . Thus it is easy to formulate
"unsafe" queries in temporal logic that produce non-finitary answers or use quantification over the
infinite universe of data values (similarly to relational calculus [AHV95]). To avoid these problems
we introduce the notion of domain-independent temporal logic queries:
Definition 3.4 Let ' be a FOTL query and D an abstract temporal database. We define the active
domain, adom(D;'), to be the set of all data constants that appear in D and '.
The interpretation j= U is the ?from Definition 2.5 relativized to the universe of data
values U . We assume that U always contains all the data constants appearing in the query and the
temporal database.
A temporal logic query ' is domain-independent if for all sets U 1 ; U 2 such that adom(D;') ' U 1 "U 2
we have D; a valuation of free variables of ' over
Note that the above definition relativizes the interpretation of the queries only with respect to the
data domain. The universe of time instants is fixed to an integer-like linear order (Z; !). It is
easy to see that to obtain an answer to a domain-independent query it is sufficient to evaluate
the query using the active domain interpretation, i.e., for adom(D;'). Moreover, the formula
characterizing the active domain for a fixed query can be expressed uniformly for all D as a temporal
logic query.
Lemma 3.5 Let D be an abstract temporal database and ' a temporal query. Then there is a
formula adomD;' (x) such that 8i 2 Z:D;
C be the set of all constants in ' and R the set of all formulas of the form
where r is a predicate symbol corresponding to a relation in the database D,
9   x is the string of existential quantifiers for all free variables of r but x. We define
can be used to restrict variables in domain-independent temporal logic
queries without changing their meaning.
We present a syntactic criterion that guarantees domain-independence of temporal logic que-
ries. While domain independence itself is not decidable (the class of temporal logic queries contains
all relational calculus queries), we show that the safe range queries-those queries that pass our
syntactic criterion-can express all the domain-independent queries in temporal logic.
The criterion is based on a modification of the criterion for the relational calculus queries
[AHV95]: we treat the binary temporal connectives since and until as -, and ignore the unary
ones, 3; 1; 2; 0; 5, and 4:
Definition 3.6 [Range restriction (rr).] Let ' be an arbitrary temporal query and FV (') the set
of free variables in '. We define
or OE since /
We say that a formula ' is safe range if and for all subformulas of ' of the form
9x:/ we have x 2 FV (/) oe x 2 rr(/).
Note that this extension of the original criterion for relational calculus queries is the strongest
possible: we map since and until to - and ignore the unary temporal connectives. To achieve
better results we would have to start with a stronger criterion for the first order case, e.g., [VGT91].
Theorem 3.7 Let ' be a domain-independent query. Then there is an equivalent safe range query.
domain-independent query ' can be correctly evaluated using the active-domain
semantics. The active domain adom(D;') can be defined uniformly for all D by a temporal logic
query adomD;' (x) (cf. Lemma 3.5). We add conjuncts that restrict the domain of every variable
in all subformulas of '. The resulting formula is equivalent to ' and safe range (follows from easy
induction on the structure of the formula). 2
Therefore every domain-independent query can be equivalently asked using a safe-range query. Moreover

Lemma 3.8 Let D be a finitary abstract temporal database and ' a safe-range query. Then '(D)
is also finitary.
By induction on the structure of ': it is sufficient to observe that (i) temporal connectives
preserve the finitary properties and (ii) all variables in ' are range-restricted. 2
However, while domain independence is preserved under equivalence of queries, the rr criterion
is not. We define a normal form of temporal logic queries to improve our chances of discovering
equivalent safe-range reformulation of a given query:
Definition 3.9 SRNF be an arbitrary temporal logic query. We define:
Variable substitution: We rename all quantified variables using unique names to avoid variable name
clashes in the subsequent transformations.
Removal of 8: We replace subformulas of the form 8x:A by :9x::A.
Removal of ! and $: We replace implications A ! B by :A-B, and similarly for the equivalences.
Pushing of negations : We use the following rules to push negations towards leaves of the formulas
and to remove double negations:
1. ::A 7! A
2. 9x:A 7! A if x 62 FV (A).
3.
4. :3A 7! 1:A, :1A 7! 3:A, :2A 7! 0:A, and :0A 7! 2:A.
5. :4A 7! 4:A, and :5A 7! 5:A.
6. since :B), and
A SRNF resulting from applying these rules to a temporal formula ' as long as possible
is denoted SRNF
Note that the last rule for since and until is valid only for discrete time; for dense time we have to
omit this rule 3 . For time bounded in the past we would also have to remove the part handling 5
from rule (5), as the equivalence does not hold for time bounded in the past (natural numbers-like).
Clearly, all the above transformations are equivalence-preserving. Thus
Lemma 3.10 DB; -; i
Thus at the end of this step we are left with an equivalent and cleaned-up temporal formula. In
addition it is easy to see that:
Lemma 3.11 Let ' be safe-range. Then SRNF
This lemma guarantees that applying the SRNF TL transformation on the given query can only
improve the chances that the query passes the rr criterion. Thus the rr criterion is always applied
on the result of the SRNF
The safe-range criterion rr assumes that the since and until connectives behave like -. Unfor-
tunately, the temporal connectives do not have the same commutative and distributive properties -
has, e.g., (OE - /) until ' 6j (OE until ') - (/ until '): However, it is easy to see that the variable
x in the formula :p(x) until q(x) is safe-range by the atomic formula q(x): clearly if there is a
valuation - such that DB; -; i there must be another time instant i 0 such
that DB; -; i 0 q(x). Thus the formula q(x) gives us a range restriction for x. We exploit this fact
to propagate the range restricting subformulas towards the leaves of the original formula using the
following equivalences:
Lemma 3.12 OE until / j OE until (3OE - /), OE until / j (OE - 2/) until /.
We show only the first equivalence; proof of the second one is analogous.
by the definition of until we know that there is an j ? i such
that DB; -; j
using the definition of until we get DB; -; i
(: Let DB; -; i similarly to the previous case there is an j ? i such that
thus DB; -; i
A similar lemma holds for the since connective. Using these equivalences we can move the range
restricting subformulas between the left- and right-hand sides of the since and until connectives. In
addition, we may need to move a range restricting formula into the scope of a temporal connective:
Lemma 3.13 '-(OE until /) j '-(OE until (3'-(OE until /) j '-((OE-43') until /).
Again, we prove only the first statement.
and by the definition of until we know that
there is an j ? i such that DB; -; j
using the definition of until we get DB; -; i
3 The rule may also significantly increase the size of the resulting formula and we may not want to use it even in
the case of discrete time.
(distribute in since left-to-right)
(distribute in until left-to-right)
since (distribute in since right-to-left)
(distribute in until right-to-left)
A - (B since C) 7! A - ((52A - B) since C) (push into since, left side)
A - (B until C) 7! A - ((43A - B) until C) (push into until, left side)
A - (C since B) 7! A - (C since (2A - B)) (push into since, right side)
A - (C until B) 7! A - (C until (3A - B)) (push into until, right side)
The rules are used when x is a variable range restricted in the subformula denoted by A, x 2 rr(A),
and free but not range restricted in the subformula denoted by B, x

Figure

3: RANF rules.
(: Let DB; -; i Similarly to the previous case DB; -; i and there is
an
implied by DB; -; i
Similar laws hold for the remaining connectives, including the unary ones (cf. the rewriting rules
in Definition 3.14). We use these laws in the final step of the conversion to propagate the range
restricting subformulas towards the leaves of the query. This way the final ATSQL query can always
be evaluated bottom-up. This goal is achieved by a modified RANF transformation [AHV95].
Definition 3.14 [RANF ' be a safe range temporal formula. A RANF is the result
of applying the rules in Figure 3 together with commutativity and associativity of conjunction to ',
starting from the top-level connective.
Clearly, all the rewriting rules preserve the meaning of the formula:
Lemma 3.15 DB; -; i
Follows from Lemmas 3.12 and 3.13, and standard equivalences for first order logic. 2
It is also easy to see that every rule in Figure 3 propagates x's restriction in A towards B.
Lemma 3.16 Let ' be a safe range temporal formula. Then every subformula of RANF
rooted by - or : is safe range.
Assume that RANF contains a subformula not rooted by - or : that
is not safe range. By case analysis we can show that ' is not safe range (as none of the rules in
Definition 3.14 is applicable by the assumption); a contradiction. 2
Similarly to [AHV95] the RANF rewriting terminates, as there are only finitely many subformulas
in the original query. Moreover, every safe range temporal query is domain independent:
Lemma 3.17 Let ' be a safe-range temporal query. Then ' is domain independent.
is equivalent to RANF Because query equivalence preserves
domain independence, it is sufficient to show that RANF TL (') is domain-independent. This follows
from an easy induction on the structure of RANF applied on every subformula
of RANF
This result, together with Theorem 3.7, shows that the classes of domain-independent queries and
safe-range queries coincide.
The translation itself is defined in three steps:
1. The first step corresponds to transforming the formula to SRNF; essentially we clean up the
formula and remove superfluous connectives, especially double negations.
2. In the second step we test all the variables in the cleaned up formula for the safe-range property.
3. For the formulas that pass the check-the safe range formulas-we propagate the range restrictions
so that all (significant) subformulas also became safe range.
3.3 Translation to ATSQL
The next step in traditional translations is the translation to relational algebra. However, we have
chosen ATSQL as our target language. The translation of temporal logic formulas in RANF TL to
ATSQL is defined by induction on the structure of the formula.
The input to this transformation is a safe-range temporal logic formula in RANF TL . It is
translated to ATSQL by repeating the following two steps:
1. First the maximal non-temporal subformulas are translated to sequenced SQL queries; this
can be done using a simple RANF TL to SQL translation (patterned, e.g., after the RANF to
Relational Algebra translation in [AHV95]).
2. The translations of the subformulas are combined using the translations of the temporal connectives
defined in the next section.
This process is repeated until the whole formula is translated.
3.3.1 Temporal Logic Connectives
We define translations of the individual temporal connectives to ATSQL as ATSQL query templates.
The subformulas rooted by the temporal connectives are then translated to subqueries embedded
into these templates.
The connectives since and until. Figure 4 graphically illustrates the semantics of since and
until over periods. We have listed all possible temporal relationships [All83] between the truth
periods of two formulas A and B. For each relationship we have determined the truth period of
A since B and A until B respectively. More formally the truth periods of A since B and A until B
are defined as follows.
A since B 7!
Temporal relationship
between formulas A and B
A
A
A
A
A
A
A
A
A
A
A
A
A
Temporal logic
A since B
A since B
A since B
A since B
A since B
A since B
A since B
A since B
A since B
A since B
A since B
A since B
A since B
Truth period
of formula F

Figure

4: Period semantics of since and until
The reader may verify that these general expressions evaluated on any particular relationship given
in

Figure

4 result in the correct truth period.
These expressions are translated to ATSQL straightforwardly using the NONSEQUENCED VALID
modifier and specifying the final timestamp using the SET VALID clause. The additional conditions
are translated into appropriate WHERE clause conditions. More precisely, A since B is translated to
NONSEQUENCED VALID
SELECT .
AND .
and A until B is translated to
NONSEQUENCED VALID
SELECT .
AND .
where A 0 and B 0 are the results of applying the translation recursively on A and B, respectively.
The SELECT lists of the ATSQL statements are derived from the sets of free variables occurring in A
and B. Variables used in both A and B give rise to additional WHERE clause conditions that equate
the corresponding attributes in A 0 and B 0 .
It is important to remember that the translations for non-atomic formulas A and B are required
to produce coalesced temporal relations:
Example 3.18 Consider a temporal database D containing two temporal relations A(x;
and B(x; 9. It is easy to see
that if coalescing has not been enforced at every step of the translation, e.g., if the relation A was
not re-coalesced after projecting out the x attribute, the translation would not be correct any more.
Indeed, applying the translation for until on the non-coalesced results of 9x:A and 9x:B would give
us the result t 2 [4; 9] instead of the correct result t 2 [0; 9].
3.3.2 Specialized Mappings
Based on the translation of since and until, the mapping of other temporal connectives can be
defined. While theoretically feasible, such an approach may be cumbersome in practice as it leads
to unnecessarily complicated ATSQL statements. Moreover, introducing these specialized mappings
allows us to translate a wider class of temporal formulas to ATSQL (cf. Section 3.2).
The connectives 3 and 2. We illustrate how the definition of since can be used to derive an
efficient special purpose mapping for 3.
The formula 3B is equivalent to true since B. Therefore we take the definition of A since B
(Section 3.3.1) and substitute A by true. We notice that the truth period of true is the whole time
line which means that BEGIN(VTIME(a0)) evaluates to \Gamma1 (beginning of time) and END(VTIME(a0))
evaluates to +1 (end of time). After the obvious simplifications we obtain:
NONSEQUENCED VALID
SELECT .
which is considerably less complex than the original statement. Similarly, we can use the definition
of until to derive a mapping for 2B, namely
NONSEQUENCED VALID
SELECT .
The connectives 1 and 0. For 1A, one can rewrite it as :3:A and use the approach presented
above. Unfortunately, this approach is not very practical as it may lead to formulas that cannot be
translated (e.g., :3:p(X) versus 1p(X)). Therefore we derive a ATSQL translation for 1A from
the definition
This can be easily expressed in ATSQL, where the 'beginning' keyword stands for \Gamma1:
NONSEQUENCED VALID
SELECT .
Again, coalescing of A 0 is crucial for the translation to work correctly. By analogy, a special purpose
mapping for 0A can be derived:
NONSEQUENCED VALID
SELECT .
The connectives 5 and 4. We use discrete time to model the temporal domain in the ATSQL
databases. Thus, in addition to the since and until connectives, we add temporal connectives that
allow us to refer to the immediately previous (5) and the immediately following
The mapping of these connectives is defined as follows: First we define the truth periods for 5A
and 4A with respect to the truth period of A:
The result is translated to ATSQL using a definition of the corresponding valid-time clause that
shifts the valid-time period by one in the appropriate direction. The translation for 5A is
NONSEQUENCED VALID
SELECT .
and the translation for 4A is
NONSEQUENCED VALID
SELECT .
Similarly to the previous cases, the SELECT list is obtained from the set of free variables of A and
A 0 is the ATSQL translation of A.
3.3.3 Putting it Together
Using the transformation defined in Section 3.2 we can convert every safe range temporal query to an
equivalent RANF We have already shown that the RANF preserves
equivalence. We have also shown that the translations of the individual temporal connectives are
correct. By composing these two steps we have:
Theorem 3.19 Let ' ba a safe range temporal logic formula and D an ATSQL database. Then
ATSQL is the ATSQL translation of the temporal logic query '.
4 With respect to the chosen granularity of time which in this paper is a year.
3.4 Example
Consider the query "list all countries that lost and regained independence" (Example 2.4) formulated
in temporal logic as:
To simplify the illustration of the translation we break up the formula into a set of auxiliary rules
We translate the first rule to
NONSEQUENCED VALID
SELECT a0.Country, a0.Capital
FROM indep(VALID) AS a0
and the second rule to
NONSEQUENCED VALID
SELECT a1.Country, a1.Capital
The main query is then translated to
SEQUENCED VALID
a2.Country AS Country
FROM aux view1(VALID) AS a2, aux view2(VALID) AS a3
AND NOT EXISTS (
FROM indep(VALID) AS a4
Note that, apart from the sequenced flag, this last step is identical to the translation from first
order logic to SQL. Because ATSQL handles the temporal dimension of snapshot-reducible queries
automatically, the translation of formulas that do not contain temporal connectives reduces to the
translation of first order logic to SQL.
3.5 Refinement and Optimization
In Section 3.2 we described only the simplest version of the translation; we used a direct temporal
extension of the translation presented in [AHV95]. However, such a direct extension has several
drawbacks. We address some of them in this section:
Negation is pushed too deep during the SRNF phase. This is necessary to find all double
negations in the original formula and to eliminate them:
However, if there are no hidden double negations (and this happens in many common cases) then
the resulting formula in SRNF does not improve range restrictedness of the variables and may be
unnecessarily complicated. In such cases we might be better off using the original query:
In such cases we can use a weaker SRNF we push the negations only if there is a chance
they may cancel out in the subformulas. However, there is no unique SRNF any more: we need
to decide how deep we want to push the negations (this decision can be based on heuristics or we
can pick the query with the cheapest execution plan).
The restricting formulas are unnecessarily duplicated. The second problem is intimately
connected with the first one: by transforming the original query we may end up with a formula,
where we need to propagate the bindings for variables across numerous connectives in order to obtain
a formula in RANF . However, this propagation often unnecessarily duplicates subformulas in the
resulting query:
The underlined p(x) - part of the resulting formula is redundant. Note, that this is a general
problem with the conversion proposed in [AHV95] (and most of the other proposals) rather than
with its temporal extension-our example indeed uses only pure first order logic. This problem can
be addressed in two ways:
1. by restricting the depth : gets pushed during the SRNF translation (this is often the main
source of this problem).
2. by eliminating the superfluous restricting formulas; this can be achieved by an additional
bottom-up pass through the generated query after the RANF
Note that in the additional pass we are not trying to eliminate redundant parts of the original query;
this is too difficult. We only eliminate unnecessary subformulas introduced during the RANF
transformation.
Nested temporal connectives (and conjunctions) create unnecessary ATSQL query
blocks. The translation generates a separate ATSQL query block for every temporal connective
(and conjunction). However, this approach may produce unnecessarily nested query blocks, that
may be merged into a single block: Consider the query 31R(x). The translation produces the
following code:
)(VALID) AS R
However, it is obvious we could merge the nested select blocks into a single equivalent block as the
inner temporal operation (1) preserves coalescing and thus the re-coalescing is not necessary:
However, at this point we need to emphasize that the translations of the individual temporal connectives
do require the input relations to be coalesced (cf. Example 3.18). Therefore we can only
merge those select blocks that preserve coalescing (as in the above example). This optimization
corresponds to flattening conjunctions in the relational calculus queries. While in theory this step
could be performed by a smart query optimizer, we are not aware of any implementation that would
be able to perform such an optimization: most query optimizers are not able to perform arithmetic
simplifications needed during the process (e.g., evaluating used in our example). This
observation can be summarized by the following lemma:
Lemma 3.20 The translations of A since B, A until B, 1A, 0A, 3B, 2B, 5B, and 4B remain
correct even if the ATSQL translation of B is not coalesced (however, A has to be coalesced in all
cases). Moreover, if B is coalesced, the result of applying a temporal connective is coalesced too.
This lemma, together with the observation that coalescing is preserved under temporal joins and
differences (and not preserved by unions and projections) allows us to safely remove redundant
coalescing operators in the translated formula.
Mapping ATSQL to Temporal Logic
Establishing a mapping between a subset of ATSQL and temporal logic is less important from a
practical point of view than establishing the mapping in the other direction, as described in the
previous section. A possible application is the decompilation of ATSQL queries. However, the main
purpose of establishing a mapping from ATSQL to temporal logic is to identify a subset of the former
that has the same expressive power as the latter. This clarifies the issue of expressive power of some
proposed restrictions of ATSQL, e.g., [WY98].
Indeed, only a subset of ATSQL can be mapped back to temporal logic. There are several reasons
for that. First, ATSQL inherits SQL-2's duplicate (bag-theoretic) semantics, while the semantics of
temporal logic is set-theoretic. Second, ATSQL (like SQL-2) has aggregate operations that are not
first-order expressible. Finally, ATSQL (like two-sorted first-order logic with a time sort) can express
queries referring to multiple temporal contexts. Recently, it has been shown [AHVdB96, TN96] that
such queries are not expressible in temporal logic.
Therefore, to define the subset of ATSQL corresponding to temporal logic we introduce a few
syntactic restrictions. The first limits ATSQL to the SQL-2 constructs that can be mapped to
relational algebra or calculus:
Definition 4.1 A ATSQL query is pure if:
1. It does not use aggregate functions.
2. Coalescing of periods is forced using (VALID). As a side-effect, this ensures that no duplicates
are generated.
The second restriction prohibits referring to multiple temporal contexts:
Definition 4.2 A ATSQL query Q is local if in every subclause of Q, all the references of the form
VTIME(v) refer to a range variable v of the FROM clause of this particular SELECT. (There is no similar
requirement for non-temporal attributes.) This implies that nested SELECT clauses cannot refer to
the valid-times of range variables specified in the FROM clause of an enclosing SELECT.
Example 4.3 The following ATSQL query is not local.
SELECT * FROM a AS a
Our mapping translates a pure local ATSQL query Q to a temporal logic formula OE Q . We define it
step by step.
Temporal built-in predicates. We start by considering a simplified form of nonsequenced AT-
SQL2 queries:
Additionally, we assume at first that:
1. the only references to valid time in the query are of the form VTIME(v) where v is one of the
range variables R
2. ff does not contain subqueries.
We will subsequently relax these assumptions. For ATSQL queries obeying the above restrictions
the mapping is defined in following steps:
1. We define a set of special points to contain all the time instants explicitly referenced by the
query (essentially the endpoints of valid periods for all relations in the FROM clause). These
points are ordered linearly along the time line consistently with the WHERE clause ff- we try
all such linear orders one by one.
2. Each of the above linear orderings divides the time line into isolated points and (open) periods,
each of which corresponding to a set of time instants that make a local characteristic formula
written in FOTL true over a given database.
3. Similarly, the timestamp for the result of the ATSQL query is represented by a disjunction
of global characteristic formulas (again one for each of the partitions of the time line defined
above).
In the rest of this section we develop this idea formally and show how it can be extended to a more
general class of queries. For a query Q define the set SQ of special points of Q to be
Also, for every range variable v of Q, define l(v) as the literal r( -
X) where r is the relation symbol
of v and -
X is a vector of unique (logical) variables of length equal to the arity of r. In this way, a
unique logical variable is also assigned to every attribute.
Now every temporal predicate in ff (or its negation) can also be written as a disjunction of
atomic order predicates relating some of the special points in SQ . Therefore, there is one or more
(but finitely many) strict linear orderings of SQ that are consistent with ff. (In such orderings some
of the special points may coincide.) For every such ordering W we will construct a
that encodes it.
For every special point p 62 f\Gamma1; +1g in W we determine the set of atomic formulas T (p) that
are true in W :
For this has to be modified in an obvious way.
For every open period are special points we also determine the set
of atomic formulas T (i) that are true in W :
We define now the local characteristic formula \Phi p of a special point p in W as
A
and the local characteristic formula \Phi i of an open period i in W as
A:
Consider a pair of consecutive special points in W . They may correspond to consecutive time
instants, e.g., v \Gamma and We will call the first the point-point case. In
the second case we also have to consider the open period between those two points and have two
cases: point-period and period-point.
The SET VALID clause of the query Q specifies a closed period
are special points in W . This period consists of a number of special points and open periods between
those points. We construct global characteristic formulas: \Psi p for each special point in i 0 and \Psi i
for each (open) period in i 0 . Such formulas encode the ordering W and the position of the point
(resp. period) in this ordering. A formula \Psi
encodes the past of p in W
and \Psi R
encodes the future of p in W (for periods this is defined similarly). Now assuming p 0 is the
predecessor of p in W , \Psi L
p and \Psi L
are defined as follows:
point-point case), or
the predecessor of p is an period (the period-point case), and
p1 for an open period
The formulas \Psi R
are symmetric to \Psi L
used instead of 5 and until
instead of since. To get the formula fl W we take the disjunction of all the global characteristic
formulas corresponding to the points and periods in i 0 .
Finally, the query corresponding to the ATSQL query Q is obtained as the disjunction of all
the formulas fl W over all linear orders W of SQ that are consistent with ff.
4.1 Lifting the restrictions.
The reverse translation can be extended from the restricted ATSQL queries to all pure local ones as
follows:
Nontemporal conditions. Every condition A 1 'A 2 is translated as
is the variable corresponding to the attribute A 1 (resp. A 2 ). A condition A 1 'c is translated similarly.
Nested subqueries. The WHERE clause of a query Q can contain a nested subquery Q 1 . The
subquery Q 1 is recursively translated using the same mechanism yielding a formula OE Q1 . The
only difference is that the subquery can refer to, in addition to its own range variables, the range
variables of Q. However, Q 1 cannot force any relationship between the special points of Q because
the temporal predicates in Q 1 cannot refer to the range variables of Q (Q is local).
Now there are several ways in which Q 1 may be embedded in the WHERE clause of Q. If the
condition is EXISTS Q 1 , then the translation is
X is the vector of the free variables of OE Q1 . Similarly for NOT EXISTS. If the condition is IN
the query is rewritten to a form that uses only EXISTS and NOT EXISTS.
Temporal constants and expressions. To handle a temporal constant c we need to introduce
a constant 0-ary relation r c and treat this relation as if it were part of every FROM clause. Clearly,
c . (It is enough to have just one constant relation, e.g., ZERO, and define the remaining ones
using 5 or 4.) For every occurrence of a temporal expression VALID(v) we need to add the
points
to the set of special points of the query. Similarly for VALID(v) \Gamma k. It is easy to see that every
pure local ATSQL query can be rewritten to a query in which all the temporal expressions are
either constants or of the form VALID(v) \Sigma k. In particular, the occurrences of FIRST/LAST can be
eliminated by splitting the query.
Assume now that the WHERE clause of a pure local ATSQL query Q is a conjunction of temporal
predicates, nontemporal conditions and conditions with subqueries. The formula OE Q is a conjunction
of the formulas obtained by translating each of those separately and conjoining the result with l(v)
for every range variable v in the query (using a consistent naming of variables that correspond
to relation attributes). A SELECT list with attributes A An is translated into an existential
quantifier prefix consisting of all the variables that are not in this list. Finally, UNION is translated
as disjunction and EXCEPT as "and not".
Sequenced queries. Sequenced queries do not contain temporal predicates, except in subqueries.
Therefore the main query is translated as in the standard translation of SQL into relational calculus.
Temporal subqueries are translated as nested subqueries of nonsequenced queries (see above).
Theorem 4.4 For every pure local ATSQL query Q, there is a temporal logic formula fi Q such that
for every ATSQL database D, a tuple - a timestamped by an period i belongs to the answer of Q
over D iff jjDjj; -; t (where jjDjj is the abstract temporal database
corresponding to D and - is the valuation that maps the free variables of fi Q to - a).
Example 4.5 Assume that a relation a has two attributes: X and Y, and a relation b one attribute
Z.
Consider the following (pure local) ATSQL query.
FROM a AS a, b AS b
WHERE VTIME(a) CONTAINS VTIME(b)
AND a.X=b.Z
We extend the previous notation to apply to tuple variables as follows: x
END(VTIME(x)). The WHERE clause of the query generates the following partial order
of endpoints:
a
The following points are special:
a
Consider now all linear orders of special points that are consistent with the above partial order, for
example, the linear order O
a
The local characteristic formulas corresponding to this order are as follows:
a
true
The global characteristic formulas corresponding to this order are as follows (going from left to right
in the order):
a
In a similar way, \Psi R
obtained. The disjunction of \Psi L
linear orders of special
points that are consistent with the partial order of endpoints generated by the query is then formed,
and subsequently conjoined with the nontemporal condition
The translation from temporal logic to ATSQL presented in the previous section produces pure
local ATSQL queries. Thus:
Corollary 4.6 Temporal logic and pure local ATSQL have the same expressive power as query
languages.
The following is a natural next question to ask: Is there a logical query language equivalent to full
ATSQL? The lack of aggregate functions in temporal logic can be remedied by a syntactic extension
of the language, along the lines of one proposed for relational calculus [Klu82]. The requirement of
maximal periods is more fundamental. In fact, allowing non-coalesced periods calls for a temporal
logic that is not point- but period-based. In that case, there can be no translation from full ATSQL
to the temporal logic discussed in this paper, even for local queries.
The restriction to local queries is also critical. Pure ATSQL has the same expressive power as
two-sorted first-order logic in which there is a separate sort for time. It has been recently shown
[AHVdB96, TN96] that temporal logic is strictly less expressive than the above two-sorted logic.
Thus, there can be no translation from ATSQL to temporal logic that works for all pure queries.
5 Related Work
Despite extensive studies of theoretical properties of temporal logic and other logic-based temporal
query languages [GM91, CCT94, AHVdB96, TN96], there has been surprisingly little work on implementations
of these languages. The main reason for disregarding logic-based approaches to practical
query language for temporal databases is their perceived inefficiency, mainly due to the point-based
semantics commonly accompanying these languages. Indeed, some of the early approaches have
utilized explicit construction of all temporal snapshots of the database [TC90]. However,
ffl for infinite temporal databases this approach fails (even when the databases are finitary);
ffl for finite databases the space requirements are exponentially worse (in the number of bits).
Our approach avoids the above problems while preserving the declarative nature of temporal logic
(similar statement can also be made about most other translation-based approaches, e.g., [Tom97,
Tom98]).
Our translation converts safe-range temporal logic formulas to ATSQL. However, the translation
could have used any other temporal query language as the target, provided it operated over temporal
databases based on a single distinguished temporal attribute over periods and the corresponding
query language enforced coalescing. Fortunately, majority of the proposed temporal data models
and languages satisfy these conditions. Therefore temporal logic can serve as a convenient tool for
interoperability of temporal database represented using one of these models (until a single standard
emerges).
A more general translation from two-sorted first-order logic to ATSQL, which is of clear practical
interest, is considerably more complicated than the translation from temporal logic to ATSQL given
in the present paper. In [Tom96] a translation from a point based two-sorted first-order logic to an
period based temporal query language was proposed. This approach was subsequently extended to
a SQL-based temporal query language SQL/TP [Tom97, Tom98]. This translation could serve as
a translation from two-sorted first-order logic to ATSQL. There are two subtle points about this
ffl It generates non-local ATSQL queries. Indeed, the results [AHVdB96, TN96] show that there
can not be a translation of the two-sorted first-order logic to local ATSQL queries (and views).
ffl In general the generated query may be exponential in the size of the input query 5 . In [Tom97]
we defined a syntactic criterion, that guarantees only polynomial (linear) increase in size for
a subclass of the two-sorted first-order logic queries. Moreover, this subclass contains the
first-order temporal logic.
The reverse translation, while of little practical use, provides the desperately needed insight into how
the various practical query languages for temporal database compare in expressive power: It allows
us to classify temporal extensions of SQL (and related languages) that are essentially equivalent to
temporal logic (with since and until connectives) 6 . The notion of locality plays a major role in this
classification:
Languages equivalent to temporal logic: TQuel [Sno87], HSQL [Sar93], temporal algebra [WY98]
used for temporal data warehousing.
Languages strictly stronger than temporal logic: ATSQL [SJB95] and SQL/Temporal [SBJS96]
(using explicit coercion of temporal attributes to data attributes and vice versa), IXRM [Lor93]
(description incomplete), SQL/TP [Tom97, Tom98].
An important consequence of this classification is, that only the first group of languages can be
implemented by a temporal relational algebra over the universe of temporal relations (with a single
distinguished valid-time attribute) [TN96]. All the languages in the second group require relations
with multiple temporal attributes to store intermediate results during bottom-up query evaluation.
Moreover, there is no upper bound on the number of temporal attributes needed even if the top-level
query is boolean. For a more comprehensive discussion of the above issues see [CT98].
6

Summary

We have established an exact correspondence between temporal logic and a syntactically defined
subset of ATSQL. The translation from temporal logic to ATSQL allows the efficient implementation
of temporal logic queries within a temporal database management system supporting ATSQL.
Future work includes extending temporal logic and the translation to support aggregate functions.
Also interesting would be an adaptation of our approach to a dense domain. This would require first
extending ATSQL to such a domain, including support for half-open and open periods, and then
extending the mapping introduced here.
5 However, this may happen even in the translation from relational calculus to algebra [AHV95].
6 More precisely, their first-order fragments are equivalent to FOTL.

Acknowledgment

We are grateful to Rick Snodgrass for participating in the preparation of the first version of this paper
and continued guidance. Jan Chomicki's work was partially supported by NSF grant IRI-9632870.



--R

Foundations of Databases.

Maintaining Knowledge about Temporal Intervals.
Managing Temporal Knowledge in Deductive Databases.
Coalescing in Temporal Databases.
The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans.
On Completeness of Historical Relational Query Languages.
Temporal Query Languages: A Survey.
Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding.
Implementing Temporal Integrity Constraints Using an Active DBMS.
Temporal Logic in Information Systems.
A Homogenous Relational Model and Query Languages for Temporal Databases.
Temporal Databases: A Prelude to Parametric Data.
Temporal Logic: Mathematical Foundations and Computational Aspects.
Deriving Optimized Integrity Monitoring Triggers from Dynamic Integrity Constraints.
Temporal Logic and Historical Databases.
A Glossary of Temporal Database Concepts.
Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions.
The Interval-Extended Relational Model and Its Application to Valid-time Databases
Monitoring Dynamic Integrity Constraints Based on Temporal Logic.
Understanding the new SQL: A Complete Guide.
Temporal Extensions to the Relational Model and SQL.
Extensions to SQL for Historical Databases.
HSQL: A Historical Query Language.
Adding Valid Time to SQL/Temporal.
Evaluating and Enhancing the Completeness of TSQL2.
The Temporal Query Language TQuel.
The TSQL2 Temporal Query Language.
Temporal Triggers in Active Databases.
Adding Time Dimension to Relational Model and Extending Relational Algebra.
A Temporal Relational Algebra as a Basis for Temporal Relational Completeness.
Temporal Databases: Theory

Point vs. Interval-based Query Languages for Temporal Databases


Safety and Translation of Relational Calculus Queries.
Maintaining temporal views over non-temporal information sources for data warehousing
--TR
The temporal query language TQuel
Adding time dimension to relational model and extending relational algebra
Monitoring dynamic integrity constraints based on temporal logic
A homogeneous relational model and query languages for temporal databases
A temporal relational algebra as a basis for temporal relational completeness
Safety and translation of relational calculus
Evaluation of relational algebras incorporating the time dimension in databases
Understanding the new SQL
Temporal databases
On completeness of historical relational query languages
A consensus glossary of temporal database concepts
Temporal logic (vol. 1)
Efficient checking of temporal integrity constraints using bounded history encoding
Point vs. interval-based query languages for temporal databases (extended abstract)
Deriving optimized integrity monitoring triggers from dynamic integrity constraints
Temporal logic in information systems
Temportal connectives versus explicit timestamps to query temporal databases
Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions
Maintaining knowledge about temporal intervals
Temporal statement modifiers
The TSQL2 Temporal Query Language
Foundations of Databases
Extensions to SQL for Historical Databases
Temporal Triggers in Active Databases
Implementing Temporal Integrity Constraints Using an Active DBMS
First-Order Queries over Temporal Databases Inexpressible in Temporal Logic
Maintaining Temporal Views over Non-Temporal Information Sources for Data Warehousing
Point-Based Temporal Extension of Temporal SQL
The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans
Temporal Query Languages
Temporal Logic MYAMPERSANDamp; Historical Databases
Coalescing in Temporal Databases

--CTR
Fusheng Wang , Carlo Zaniolo, An XML-Based Approach to Publishing and Querying the History of Databases, World Wide Web, v.8 n.3, p.233-259, September 2005
Paolo Reconciling Point-Based and Interval-Based Semantics in Temporal Relational Databases: A Treatment of the Telic/Atelic Distinction, IEEE Transactions on Knowledge and Data Engineering, v.16 n.5, p.540-551, May 2004
Fusheng Wang , Xin Zhou , Carlo Zaniolo, Bridging relational database history and the web: the XML approach, Proceedings of the eighth ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA
Michael Bhlen , Johann Gamper , Christian S. Jensen, An algebraic framework for temporal attribute characteristics, Annals of Mathematics and Artificial Intelligence, v.46 n.3, p.349-374, March     2006
first-order temporal logic;ATSQL;query translation;temporal databases