Keywords

The Information Principle; temporal database; timestamped proposition; interval; granularity; valid time; transaction time

Temporal Databases

A temporal database can be thought of, loosely, as a database that contains historical data instead of or in addition to current data. Such databases have been under active investigation since at least the beginning of the 1980s—perhaps earlier. Some of those investigations have taken the extreme position that data in such a database, once inserted, should never be deleted or changed in any way, in which case the database can be thought of, again loosely, as containing historical data only. (Some data warehouses adopt this approach, at least to a first approximation.) Conventional databases, by contrast, are typically at the other extreme; a conventional database typically contains current data only, and data in such a database is changed or deleted as soon as the propositions represented by that data cease to be true. (Refer to Chapter 1, subsection titled “Relations and Their Meaning,” if you need to refresh your memory regarding the important idea that the data in a database can be thought of as a collection of true propositions.) In what follows, we’ll occasionally refer to such a database explicitly as nontemporal, in order to emphasize the fact that it contains current data only.¹

The suppliers-and-shipments database of Chapters 1-3 is a nontemporal database in the foregoing sense. Consider Fig. 1.1 once again, which shows some sample values for that database. That figure shows among other things that the status of supplier S1 is currently 20. By contrast, a temporal version of that database might show not only that the status of that supplier is currently 20, but also that it has been 20 ever since July 1st last year, and perhaps that it was 15 from April 5th to June 30th last year, and so on. Thus, the propositions in a nontemporal database are generally thought of as referring to the current state of affairs (i.e., the state of affairs“now,” when the database is actually inspected). In fact, even if they’re thought of as referring to some time other than “now,” it makes no real difference to the way the data is managed and used. As we’ll see over the next few chapters, however, the way the data is managed and used in a temporal database differs in a variety of ways from the way it’s managed and used in a nontemporal one (a fact that accounts for the existence of this book, of course).

The distinguishing feature of a temporal database is, naturally, time itself. Temporal database research has therefore involved a certain amount of investigation into the nature of time as such. Here are some of the questions that have been explored:

But these questions, interesting though they might be in themselves, aren’t intrinsically database questions as such, and we therefore won’t delve very deeply into them in this book. Instead, we’ll simply make what we hope are reasonable assumptions as we proceed. This approach allows us to concentrate on matters that are more directly relevant to our overall aim. However, we note that parts of that temporal research do possess certain interesting generalizations; that is, ideas developed originally or primarily to support temporal data in particular have been found to have application in other important areas as well. We’ll touch on this point again from time to time in subsequent chapters.

Out of all that research, the ideas we focus on in this book represent what we regard—naturally enough, since the ideas in question are due primarily to one of the present authors (Lorentzos)²—as the most satisfactory and most promising part. What do we mean by “most promising”? Well, it’s unfortunately the case that for a long time the research community was divided over how best to address the temporal database problem. (Indeed, in some respects it still is.) In a nutshell:

The departure in question—i.e., from relational principles—consists primarily in representing timestamps by means of “hidden attributes” instead of by conventional relational attributes in the usual way. (The attributes are hidden in the sense that they’re not directly visible to the user in the usual way and can’t be referenced by simple attribute names in the usual way.) We believe such a scheme is unwise. Indeed, it’s clear that “hidden attributes” aren’t true relational attributes, “relations” that contain such “attributes” aren’t true relations, and the overall approach constitutes a clear violation of Codd’s Information Principle. Some of the consequences of such violation are explained in detail in reference [29].

Now, if (as we saw in Chapter 1) data in general can be regarded as an encoded representation of propositions, then temporal data in particular can be regarded as an encoded representation of timestamped propositions—by which we mean propositions that involve one or more values of some timestamp type. It follows that in a temporal database (under the extreme interpretation of that term, according to which all of the data is temporal), every proposition is timestamped in the foregoing sense. We might therefore define a temporal relation to be one in which each tuple contains at least one timestamp (i.e., the relation heading contains at least one attribute of some timestamp type); we might further define a temporal relvar to be one whose heading is that of some temporal relation; and we might finally define a temporal database to be one in which all of the relvars are temporal ones. Note: We’re being deliberately vague here as to what the timestamps we’re talking about might look like in actual practice. We’ll take up this issue in Chapters 5 and (especially) 6.

Having just offered a reasonably precise definition of a temporal database (in its extreme form), we now dismiss that definition as not very useful! We dismiss it because even if the relvars in the database are indeed all temporal ones, many relations that can be derived from that database won’t be temporal in the foregoing sense. For example, the answer to the query “Get the names of all employees we’ve ever hired” might be obtained from some temporal database, but the result would clearly not be a temporal relation as defined above. And it would be a strange DBMS indeed—certainly not a relational one—that would let us obtain query results that couldn’t themselves be kept in the database.

From this point forward, therefore, we take a temporal database to be one that does include some temporal data but isn’t necessarily limited to temporal data only. The chapters in this part of the book discuss such databases in detail. The plan for those chapters is as follows:

By the way, it’s important to understand that—with just one exception, the interval type generator introduced in Chapter 6, along with its associated generic operators and generic constraints—all of the new constructs to be discussed in this part of the book (and the next part, too) are essentially just shorthand. That is, they can all be expressed—albeit only very longwindedly, in most cases—in terms of features already available in a relationally complete language such as Tutorial D. Thus, the approach to temporal databases that we advocate involves no changes to the classical relational model—though it does involve certain generalizations, as we’ll see in Chapter 11 and later chapters, and as already indicated it does also involve the introduction of a new type generator. With regard to this latter point, however, we note that the question as to which types and type generators are supported is essentially orthogonal to the question of support for the relational model itself. That is, the relational model merely requires that some types be made available, somehow, in order that relations might be defined over them; nowhere does it prescribe exactly what types have to be supported.³

Timestamped Propositions

We’re now in a position to begin our investigation into some of the issues surrounding temporal databases. We start by appealing to the way people typically express timestamped propositions in natural language. Here are three simple examples (labeled p1-p3 for purposes of subsequent reference):

p1: Supplier S1 was appointed—i.e., placed under contract—on July 1st, 2012.

p2: Supplier S1 has been under contract since July 1st, 2012.

p3: Supplier S1 was under contract during the interval from July 1st, 2012, to the present day.

Each of these three propositions represents a possible interpretation for a tuple—call it t—that looks like this (as you can see, that tuple has two attributes, SNO and FROM, with values the supplier number S1 and the timestamp July 1st, 2012, respectively):

Any of the three interpretations might be appropriate if tuple t appeared in some relation in some database that represented the state of affairs in some enterprise. The boldface prepositions on, since, and during characterize the three interpretations.

Now, although we’ve said there are three possible interpretations, it could be argued that they all say the same thing, albeit in slightly different ways. Indeed, we do take propositions p2 and p3 to be equivalent, but not p1. For consider:

Thus, neither of p1 and p2 implies the other, and they’re certainly not equivalent.

That said, tuples in conventional databases often do contain things like “date of appointment,” and propositions like p2 (or p3) often are the intended interpretation. If such is the case here, however—i.e., if p1 is meant to be equivalent to p2 and p3 after all—then the given formulation isn’t quite adequate to the task. We can improve it by rephrasing it thus:

p1: Supplier S1 was most recently appointed on July 1st, 2012, and the contract hasn’t subsequently been terminated.

What’s more, if this version of p1 really is what tuple t is supposed to mean, then p2 in its present form isn’t really adequate either—it needs to be rephrased thus:

p2: Supplier S1 wasn’t under contract on June 30th, 2012, but has been so ever since July 1st, 2012.

Of course, p3 needs an analogous clarification:

p3: Supplier S1 wasn’t under contract on June 30th, 2012, but has been so throughout the interval from July 1st, 2012, to the present day.

Observe now that p1 expresses a time at which a certain event took place, while p2 and p3 express an interval of time during which a certain state persisted. We’ve deliberately chosen an example in which a certain state might be inferred from information regarding a certain event: Since the event—i.e., the most recent appointment of supplier S1—occurred on July 1st, 2012 (and the contract hasn’t subsequently been terminated), that supplier has been in the state of being under contract from that date to the present day. Conventional database technology can handle time instants (times at which events occur) reasonably well; however, it can’t handle time intervals (intervals during which states persist) very well at all, as we’ll see in the next chapter.

Now, events from which states can’t be inferred aren’t very interesting from the point of view of temporal data in general. For example, the statement “Lightning struck at 2:30 pm last Tuesday” is certainly a timestamped proposition, but—from the point of view of temporal data in general, at any rate—it’s not a very interesting one. To be more specific, the timestamp in this example has almost none of the special properties, and displays almost none of the special kinds of behavior, that (as we’ll see over the next few chapters) apply to temporal data in general. For such reasons, we’ll have little to say from this point forward regarding propositions like the one in the lightning example.

To return to propositions p1-p3: Observe now that, although p2 and p3 are logically equivalent, they’re significantly different in form; in other words, the predicates of which they’re instantiations (see Chapter 1) are significantly different. To be specific, p3 explicitly refers to a specific time interval, with a specific begin point and specific end point, while p2 refers only to a specific time instant. As a consequence, the form of p2 can’t be used for historical records, while that of p3 can⁵—provided, of course, that we replace the phrase “the present day” in that proposition by some explicit date, say July 1st, 2013. The corresponding predicates (call them P2 and P3, respectively) look something like this:

P2: Supplier Sx has been under contract since date d.

P3: Supplier Sx was under contract during the interval from date b to date e.

Note: For simplicity, we ignore for the moment the various clarifications discussed earlier, although those clarifications would certainly be needed in practice. See the further remarks on this subject at the very end of this chapter.

We conclude from the foregoing that the concept of during is very important for historical records. Indeed, that concept pervades the next several chapters, as we’ll soon see.⁶

We close this section by noting that, despite our repeated use of terms such as “historical data” and “historical records,” temporal databases might quite reasonably contain information about the future as well as, or instead of, the past. For example, we might wish to document the fact that supplier S1 will be under contract during the interval from date b to date e, where e is a date in the future, and b might be as well. Thus, we’ll take the terms temporal and historical to include the future in this way throughout this book, unless the context demands otherwise. We’ll also offer a few comments on the question of recording information about the future specifically, at suitable points in the text.

Valid Time vs. Transaction Time

In a conventional (nontemporal) database, anything can be updated, barring explicit edicts to the contrary. But if historical data can be updated, we find ourselves faced with the possibility that, apparently, history can be changed! What of this possibility?

Well, it’s important to understand that, obviously, the database doesn’t contain “the real world” as such; instead, it contains our knowledge of, or beliefs about, the real world.⁷ And while it’s perfectly reasonable to assert that the past is immutable and history as such can never change, it’s equally reasonable to assert that our beliefs about it can change—indeed, they often do. In a database context, therefore, when we speak of “updating history,” what we really mean is updating our beliefs about history, not updating history as such—though the distinction is often blurred, and even confused, in informal contexts, as you might imagine.

In the temporal database literature, the terms valid time and transaction time are used in an attempt to get at the foregoing distinction [103]. We don’t particularly care for these terms ourselves (their meanings can hardly be said to “leap off the page,” as it were), and we won’t be using them much in the chapters to come; however, the distinction as such is important, and it does merit some discussion. So consider the following simple example. Let p be the proposition “Supplier S1 was under contract.” Suppose it’s our current understanding that this state of affairs obtained from July 1st, 2012, to June 30th, 2013, and we therefore insert the following tuple into some relvar in the database:

Note very carefully that this tuple does not correspond to proposition p. Rather, it corresponds to what might be called a timestamped extension of p that can be stated thus:

And the literature would refer to the timestamp here—i.e., the interval from July 1st, 2012, to June 30th, 2013—as the valid time for the original proposition p. Thus, the valid time for p in this example is the interval of time during which (according to our current beliefs) p was in fact true. Note: We’re assuming here for simplicity that the specified interval (from July 1st, 2012, to June 30th, 2013) is the only interval during which the specified supplier was under contract. In general, however, the valid time for a given proposition will consist of a set of intervals, not just a single interval as such. For example, if it’s our understanding that supplier S1 was also under contract previously from January 1st, 2010, to March 30th, 2011, then the relevant valid time would clearly involve two intervals, not just one. But we’ll continue to assume for the remainder of this section, for simplicity, that valid times are indeed just single intervals.

Suppose we now learn that supplier S1’s contract in fact began on June 1st, not July 1st, 2012, and we therefore replace the original tuple by one that looks like this:

Now, this change has no effect on proposition p as such, of course—it merely changes the associated timestamp (i.e., it reflects our revised understanding, to the effect that supplier S1 was in fact under contract from June 1st, 2012, to June 30th, 2013). Thus, the valid time for proposition p is now the interval from June 1st, 2012, to June 30th, 2013, and we’ve just “updated our beliefs about history.” What we’ve certainly not done, however, is update history as such; the update we’ve just performed does not and cannot change the historical fact that the database previously showed supplier S1 as under contract from July (not June) 1st, 2012.

Finally, suppose we discover a mistake was made and supplier S1 was in fact never under contract at all, and we therefore delete the foregoing tuple entirely. Proposition p is now known to be false; as a consequence, there’s now no valid time associated with it at all.⁸

Now suppose the original tuple was inserted at time t1 and replaced at time t2, and that replacement tuple was then deleted at time t3. Then the literature would say the interval from t1 to t2 was the transaction time—not for proposition p as such, but rather for the timestamped extension of p with valid time July 1st, 2012, to June 30th, 2013; that is, the interval from t1 to t2 is the time during which the database asserted that this particular timestamped extension of p was true. Likewise, the literature would say the interval from t2 to t3 was the transaction time for the timestamped extension of p with valid time June 1st, 2012, to June 30th, 2013; that is, the interval from t2 to t3 is the time during which the database asserted that that particular timestamped extension of p was true.⁹ Note: Again we’re simplifying matters somewhat; in general, transaction times, like valid times, are sets of intervals, not individual intervals as such. For example, if the database additionally showed the first of the foregoing timestamped extensions of p as being true during the interval from t4 to t5, then the relevant transaction time would clearly involve two intervals instead of one.

We’ll have a great deal more to say about these matters in Chapter 17. Prior to that point, it’s sufficient to stress the fact that—as our examples have suggested—valid times can be updated, but transaction times can’t. (Valid times reflect our beliefs about history, and those beliefs can change; transaction times, by contrast, reflect history as such, and history can’t change. Indeed, as we’ll see in Chapter 17, transaction times are managed by the system anyway, not by some human user.) Largely for such reasons, all of our discussions from this point forward will concern themselves with valid times only (what’s more, they’ll do so only implicitly, for the most part), until we get to Chapter 17.

Some Fundamental Questions

The references in the foregoing discussions to intervals of time tacitly introduce a simple but fundamental idea: namely, the idea that an interval with begin time b and end time e can be thought of as the set of all times t such that b ≤ t ≤ e (where “<” means “earlier than,” of course). Though “obvious,” this simple notion has numerous far reaching consequences, as we’ll see in the chapters to come. It also leads directly to a series of fairly fundamental questions!—indeed, some of those questions might already have occurred to you. For example:

We close this section, and this chapter, with some final remarks regarding the running example. To be specific, from this point forward we’ll assume, realistically enough, that:

Exercises

Answers

The exercises in this chapter are all just review questions, and suitable answers can be found in the body of the chapter.