Keywords

redundancy problem; circumlocution problem; since attribute; from and to attributes; semitemporal database; fully temporal database

Revising the Running Example

Actually, the first change we want to make isn’t a temporal one at all (nor is it an addition); rather, it’s a matter of simplification. To be specific, we simplify relvar S, the suppliers relvar, by dropping all of the attributes except attribute SNO. The predicate for this revised—and dramatically simplified!—relvar is thus just: Supplier SNO is under contract. (The predicate for SP remains unchanged, of course.) Fig. 5.1, a simplified version of Fig. 1.1, shows a set of sample values for the database after this revision has been applied.

As already indicated, this simplified database is still a purely conventional one—it involves no temporal aspects at all. Note: In case you’re thinking it’s surely much too simple, we’d like to assure you that in fact it’s perfectly adequate as a basis for illustrating almost all of the points we want to make in this part of the book, and we’ll stay with it until further notice. In fact, not simplifying the database in the manner indicated would lead to certain problems that we don’t wish to get into at this juncture. We’ll consider those problems in Part III of this book.

Sample Constraints and Queries

We now proceed to consider some sample constraints and queries against the database of Fig. 5.1. In the two sections following this one (also in the next chapter, to some extent), we’ll see what happens to those constraints and queries when that database is extended to incorporate various temporal features.

Constraints (nontemporal database, Fig. 5.1): The only constraints we want to consider here are the pertinent key and foreign key constraints. Just to remind you, {SNO} is the sole key for relvar S; {SNO,PNO} is the sole key for relvar SP (in fact, S and SP are now both “all key”); and {SNO} is a foreign key in relvar SP, referencing the sole key of relvar S.

Queries (nontemporal database, Fig. 5.1): We consider just two queries, both of them very simple:

Observe that Query A involves a simple projection and Query B involves the difference between two such projections. When we consider temporal analogs of these two queries in Chapter 9, we’ll find they involve “temporal” analogs of these operators (and you probably won’t be surprised to learn in Chapter 11 that similar “temporal” analogs of other relational operators can be defined as well).

Semitemporalizing the Example

As previously noted, we plan to proceed gently and make our temporal revisions to the database in a piecemeal fashion. The first such revision involves “semitemporalizing” (so to speak) relvars S and SP by adding a timestamp attribute, SINCE, to each and renaming the relvars accordingly. See Fig. 5.2.

For simplicity, we don’t show real timestamps in Fig. 5.2; instead, we use symbols of the form d01, d02, etc. (where the “d” can conveniently be pronounced “day”), a convention to which we adhere throughout this book. (Note that most of our examples in the next few chapters do make use of time points that are days specifically; the applicable granularity in all of those examples is thus one day.) We assume that day 1 immediately precedes day 2, day 2 immediately precedes day 3, and so on; also, as you can see, we drop insignificant leading zeros from expressions such as “day 1.”

The predicate for relvar S_SINCE is:

And the predicate for relvar SP_SINCE is:

Supplier SNO has been able to supply part PNO ever since day SINCE, and not on the day immediately before day SINCE.

(We deliberately spell these predicates out fairly precisely here, just to remind you of the need to be careful when stating intended interpretations. We won’t always bother to be quite so precise, however, appealing instead for the most part to our tightened interpretations of the terms since and during as explained at the very end of Chapter 4.)

Constraints (semitemporal database, Fig. 5.2): The key and foreign key constraints for the semitemporal database of Fig. 5.2 are the same as they were for the original nontemporal database of Fig. 5.1. Thus, the relvar definitions might look as follows:

VAR S_SINCE BASE RELATION { SNO SNO , SINCE DATE }

  KEY { SNO } ;

VAR SP_SINCE BASE RELATION { SNO SNO , PNO PNO , SINCE DATE }

  KEY { SNO , PNO }

  FOREIGN KEY { SNO } REFERENCES S_SINCE ;

We’ve defined the two SINCE attributes to be of type DATE, which we take to be a system defined type representing calendar dates (by which we mean dates—points on the timeline—that are accurate to the day and are constrained by the usual calendar rules, implying among other things that, e.g., “April 31st, 2015” and “February 29th, 2100” aren’t valid dates).

But the foregoing definitions are inadequate as they stand. To be specific, we need an additional constraint, over and above the foreign key constraint from SP_SINCE to S_SINCE, to reflect the fact that no supplier can supply any part before that supplier is under contract:

CONSTRAINT XST1 /* “extra semitemporal constraint no. 1” */

  IS_EMPTY ( ( ( SP_SINCE RENAME { SINCE AS SPS } ) JOIN ( S_SINCE RENAME { SINCE AS SS } ) ) WHERE SPS < SS ) ;

The intuition behind this formulation is that if tuple sp in SP_SINCE references tuple s in S_SINCE, then the SINCE value in sp mustn’t be less than that in s. We observe that, given a semitemporal database like that of Fig. 5.2, we’ll probably need to state many constraints of the same general and rather cumbersome nature as Constraint XST1, and we’ll soon begin to wish we had some convenient shorthand for the purpose.

Queries (semitemporal database, Fig. 5.2): We now consider, not Queries A and B as such (i.e., as those queries were stated in the previous section), but rather certain semitemporal analogs of those queries.

If supplier Sx is currently able to supply any parts at all, then clearly Sx has been able to supply at least one part since the earliest SINCE date shown for that supplier in relvar SP_SINCE (e.g., if Sx is S1, that earliest SINCE date is d04). Here then is a Tutorial D formulation of the query:

EXTEND SP_SINCE { SNO } : { SINCE := MIN ( !!SP_SINCE , SINCE ) }

Here’s the result:

In our sample data there’s just one supplier, supplier S5, who’s currently unable to supply any parts at all. However, we can’t discover the date since when that supplier has been unable to supply any parts, because there isn’t enough information in the database; to say it again, the database is still only semitemporal. For example, suppose the current day is day 10. Then it might be the case that supplier S5 was able to supply at least one part from as early as day 2, when that supplier was first placed under contract, right up to as late as day 9; or, going to the other extreme, it might be the case that supplier S5 has never been able to supply any parts at all.

In order to have any hope of answering Query B, therefore, we must complete the “temporalizing” of our database (or the SP portion of it, at any rate). To be more precise, we must keep historical records in the database to show which suppliers were able to supply which parts when, as described in the section immediately following.

Fully Temporalizing the Example

Fig. 5.3 shows a “fully temporalized” version of suppliers and shipments.¹ Observe that the SINCE attributes have become FROM attributes, and each relvar has acquired an additional timestamp attribute called TO (and for that reason we’ve replaced “_SINCE” by “_FROM_TO” in the relvar names). The FROM and TO attributes together express the notion of an interval of time during which, according to our current beliefs, some proposition was true. Note: We’ve assumed for definiteness that today is day 10, and so we’ve shown d10 as the TO value for each tuple that pertains to the current state of affairs. However, that assumption might, and indeed should, immediately lead you to wonder what mechanism could cause all of those d10’s to be replaced by d11’s on the stroke of midnight (as it were) on day 10. Well, we’ll have to set this issue aside for the time being. We’ll return to it in Chapter 12.

Because we’re now keeping historical records, there are more tuples in this database than there were in either of its predecessors, as you can see. In fact, the fully temporal database of Fig. 5.3 includes all of the information from the semitemporal one of Fig. 5.2—except that, purely for the sake of the example, we’ve shown the TO value for two of supplier S4’s shipments as a date prior to the current date (i.e., we’ve converted those two shipments from “current” to past or “historical” information). That fully temporal database also includes historical information concerning an earlier interval of time, from d02 to d04, during which supplier S2 was also under contract and able to supply certain parts. The predicate for S_FROM_TO is:

And the predicate for SP_FROM_TO is:

Constraints (fully temporal database, Fig. 5.3): First of all, we need to guard against the absurdity of a FROM-TO pair appearing in which the TO value is less than the FROM value:

CONSTRAINT S_FROM_TO_OK IS_EMPTY ( S_FROM_TO WHERE TO < FROM ) ;

CONSTRAINT SP_FROM_TO_OK IS_EMPTY ( SP_FROM_TO WHERE TO < FROM ) ;

Next, observe from the double underlining in Fig. 5.3 that we’ve included the FROM attribute in the primary keys for both relvars. (Note that {SNO} alone is not a key for S_FROM_TO, nor is {SNO,PNO} a key for SP_FROM_TO.) But observe also that we could equally well have included the TO attributes in those keys instead of the FROM attributes; in fact, relvars S_FROM_TO and SP_FROM_TO both have two keys and are good examples of relvars for which there’s no obvious reason to choose one of those keys as primary. We make the choices we do in Fig. 5.3 purely for the sake of definiteness, not for any good logical reason.

Here then are the relvar definitions:

VAR S_FROM_TO BASE RELATION { SNO SNO , FROM DATE , TO DATE }

  KEY { SNO , FROM }

  KEY { SNO , TO } ;

VAR SP_FROM_TO BASE RELATION { SNO SNO , PNO PNO , FROM DATE , TO DATE }

  KEY { SNO , PNO , FROM }

  KEY { SNO , PNO , TO } ;

However, the constraints we’ve discussed so far—the two “_FROM_TO_OK” constraints and the four KEY constraints—are still inadequate in themselves to capture everything we’d like them to.² Consider relvar S_FROM_TO, for example. Obviously, if there’s a tuple for supplier Sx in that relvar with FROM value f and TO value t, we want there not to be a tuple for supplier Sx in that same relvar indicating that Sx was under contract on the day immediately before f or the day immediately after t. By way of example, consider supplier S1, for whom we have just one S_FROM_TO tuple, with FROM = d04 and TO = d10:

The mere fact that {SNO,FROM} is a key for relvar S_FROM_TO is clearly insufficient to prevent the appearance of an additional “overlapping” S1 tuple with (say) FROM = d02 and TO = d06:

Observe that if this additional tuple did appear, the relvar would be in violation of its own predicate (because the previous tuple implies among other things that supplier S1 wasn’t under contract on day 3, while the “overlapping” tuple implies that supplier S1 was under contract on day 3, and we would thus have a contradiction on our hands). Clearly, what we’d like is for these two S1 tuples to be merged into one, with FROM = d02 and TO = d10:

Now, you might already have guessed that this idea of merging tuples is going to turn out to be very important. Indeed, not merging tuples in the foregoing example would be almost as bad as permitting duplicates! Duplicates amount to “saying the same thing twice.” And those two tuples for supplier S1 with overlapping FROM-TO intervals do indeed “say the same thing twice”; to be specific, they both say among other things that supplier S1 was under contract on days 4, 5, and 6. We’ll revisit this issue and discuss it in detail in Chapter 13.

Next, the fact that {SNO,FROM} is a key for S_FROM_TO is also insufficient to prevent the appearance of an additional “abutting” S1 tuple with (say) FROM = d02 and TO = d03:

If this tuple did appear, the relvar would again be in violation of its own predicate (the original tuple implies among other things that supplier S1 wasn’t under contract on day 3, while the “abutting” tuple implies that supplier S1 was under contract on day 3, and so again we would have a contradiction on our hands). As before, then, what we’d like is for the two tuples in question to be merged into one—the same one as before, in fact:

Again, we’ll revisit this issue and discuss it in detail in Chapter 13.

Here then is a constraint that does prohibit such overlapping and abutting:

CONSTRAINT XFT1

 IS_EMPTY ( ( ( S_FROM_TO RENAME { FROM AS F1 , TO AS T1 } ) JOIN ( S_FROM_TO RENAME { FROM AS F2 , TO AS T2 } ) ) WHERE ( T1 ≥ F2 AND T2 ≥ F1 ) ) OR ( F2 = T1+1 OR F1 = T2+1 ) ) ;

With this example, we begin to see the problem. This constraint is quite complicated!—not to mention the fact that we’ve taken the gross liberty of writing (e.g.) T1+1 to designate the immediate successor of the day denoted by T1, a point we’ll come back to in the next chapter. Furthermore, we observe that, given a fully temporal database like that of Fig. 5.3, we’ll probably need to state many constraints of the same general nature as constraint XFT1, and again we’ll surely wish we had some good shorthand for the purpose.³

Next, observe that {SNO,FROM} in relvar SP_FROM_TO is not a foreign key from that relvar to relvar S_FROM_TO, even though it does involve the same attributes as one of the keys—in fact, the one we arbitrarily chose to be the primary key—of this latter relvar. (It’s not a foreign key because it’s possible for an {SNO,FROM} value to appear in SP_FROM_TO and not in S_FROM_TO, as a glance at Fig. 5.3 will quickly confirm.)⁴ On the other hand, we certainly do need to ensure that if a given supplier is represented in relvar SP_FROM_TO, then that same supplier is also represented in relvar S_FROM_TO:

CONSTRAINT XFT2 SP_FROM_TO { SNO } ⊆ S_FROM_TO { SNO } ;

This constraint is an example of an inclusion dependency [10]. Inclusion dependencies can be regarded as a generalization of foreign key constraints. And it should be clear that any fully temporal database like that of Fig. 5.3 is likely to involve a large number of such dependencies.

Constraint XFT2 is still not enough, however; we also need to ensure that if relvar SP_FROM_TO shows some supplier as being able to supply some part during some interval of time, then relvar S_FROM_TO shows that same supplier as being under contract throughout that same interval of time (this is an example of what in Chapter 14 we’ll be calling a denseness constraint). Two attempts at formulating this constraint—the first of which is incorrect, please note—are shown below. We recommend strongly that you try producing a formulation of your own before reading any further.

Here then is a first attempt (Warning: Incorrect!):

CONSTRAINT XFT3

 IS_EMPTY ( ( S_FROM_TO RENAME { FROM AS SF , TO AS ST } ) JOIN ( SP_FROM_TO RENAME { FROM AS SPF , TO AS SPT } ) ) WHERE SPF < SF OR SPT > ST ) ;

The intuition behind this formulation is that if tuples s and sp, in relvars S_FROM_TO and SP_FROM_TO, respectively, correspond to the same supplier, then the FROM-TO interval in s must encompass that in sp. As the comment indicates, however, both the intuition and the formulation are incorrect, or at least incomplete. To see why, let relvars S_FROM_TO and SP_FROM_TO be as shown in Fig. 5.3, except that SP_FROM_TO contains an additional tuple for supplier S2 with (say) FROM = d03 and TO = d04:

Such an arrangement is clearly consistent (since supplier S2 was under contract from day 2 to day 4), and yet constraint XFT3 as stated above would actually prohibit it—because (a) the result of the join would contain a tuple for supplier S2 with SF = d07, ST = d10, SPF = d03, and SPT = d04; (b) the comparison SPF < SF would give TRUE for this tuple; (c) the IS_EMPTY test overall would therefore give FALSE; and (d) the constraint would thereby be violated.

Here by contrast is a correct formulation:

CONSTRAINT XFT3

 COUNT ( SP_FROM_TO { SNO , FROM , TO } ) =

 COUNT ( ( ( SP_FROM_TO RENAME { FROM AS SPF , TO AS SPT } ) { SNO , SPF , SPT } JOIN ( S_FROM_TO RENAME { FROM AS SF , TO AS ST } ) ) WHERE SF ≤ SPF AND ST ≥ SPT ) ;

The (correct) intuition here is that if relvar SP_FROM_TO contains a tuple showing supplier Sx as able to supply some specific part from day spf to day spt, then relvar S_FROM_TO must contain exactly one tuple showing supplier Sx as being under contract throughout that interval. (Note that we’re assuming here that all of the constraints discussed previously are in effect!) A detailed explanation follows:

Now, you might have had some difficulty in following the foregoing explanation. Even if you didn’t, you’ll surely recognize that once again the constraint is quite complex, and yet once again we’ll surely need to state many constraints of that same general nature, given a fully temporal database like that of Fig. 5.3. Once again, therefore, we’ll surely wish we had some good shorthand available.

So much for constraints. We turn now to queries.

Queries (fully temporal database, Fig. 5.3): Here then are fully temporal analogs of Queries A and B:

Well, you might like to take a little time to convince yourself that, like us, you’d really rather not even attempt these queries! If you do make the effort, however, the fact that they can be expressed, albeit exceedingly laboriously, will (or should) eventually emerge, but it’ll surely be obvious that some kind of shorthand is highly desirable.

In a nutshell, then, the problem of temporal data is that it quickly leads to constraints and queries⁵ that are unreasonably complex to express: unreasonably complex, that is, unless the system provides some well designed shorthands, which commercially available DBMSs typically don’t.⁶ In the next chapter, therefore, we’ll begin our search for such a set of “well designed shorthands.”

Exercises

What about analogs of these two queries on the database of Fig. 5.3? At least try to state such analogs in natural language, even if you decide you’d rather not attempt to come up with any corresponding Tutorial D formulations.

Answers

Analogous queries for the database of Fig. 5.3, expressed in natural language, are: