Keywords

redundancy problem; circumlocution problem; contradiction problem; PACKED ON constraint; WHEN / THEN constraint; “temporal” key; current relvar; historical relvar

Simplifying the Running Example

We assume for the purposes of this chapter that the database has been designed in accordance with the recommendations of the section “Both Since and During Relvars” in Chapter 12, and our database therefore consists of the following seven relvars:

S_SINCE  SP_SINCE

S_DURING  SP_DURING

S_NAME_DURING

S_STATUS_DURING

S_CITY_DURING

(We leave discussion of designs involving since relvars only or during relvars only to the next chapter.) With respect to the foregoing “combination” design, however, it should be clear that:

Without loss of generality, therefore, (a) we can ignore the attribute pairs {SNAME,SNAME_SINCE} and {CITY,CITY_SINCE} in relvar S_SINCE, and (b) we can ignore relvars S_NAME_DURING and S_CITY_DURING in their entirety. For the purposes of this chapter, therefore, and indeed—please note—for the remainder of this book (barring explicit statements to the contrary, of course), we can simplify the database still further. In other words, we can take the database to be as defined, in outline, in Fig. 13.1 below (“in outline” meaning here among other things that all constraints other than conventional KEY and FOREIGN KEY constraints have been omitted, because of course we’re not yet in a position to say what those additional constraints should look like).

Here for purposes of subsequent reference are informal statements of the predicates for this simplified design. First the since relvars:

Now the during relvars:

Figs. 13.2 and 13.3—which repay very careful study—show some sample values for these relvars.

Note: The specific values shown in these figures deliberately don’t correspond exactly to our usual sample values as shown in Fig. 6.1 or Fig. 9.1, though they’re close. Note too that little in the present chapter depends on those specific values. As already suggested, however, a careful study of the figures should help you understand the semantics of the database in general.

Keys and Foreign Keys

The keys that apply to the database of Fig. 13.1 are as indicated in that figure, and in the case of the since relvars, at least, there’s not much more to say about them. By contrast, there certainly is more to say in the case of the during relvars, and those discussions form the bulk of the rest of this chapter. As for foreign keys, in fact there’s only one such in our simplified database, and that’s {SNO} in the current relvar SP_SINCE, which is a foreign key referencing the sole key {SNO} in the current relvar S_SINCE:

FOREIGN KEY { SNO } REFERENCES S_SINCE

This specification, which appears as part of the definition of relvar SP_SINCE, reflects the fact that if a supplier is currently able to supply some part, then that supplier must be currently under contract. (Of course, we’re appealing here to the informal notion that since relvars contain “current data” only.) As pointed out in Chapter 5, however, in connection with what was there called Constraint XST1, this foreign key constraint is insufficient by itself; what we really need is something more general, in order to enforce the constraint that whenever a supplier is, was, or will be able to supply some part, then that supplier is, was, or will be under contract at that same time. This more general constraint isn’ t a foreign key constraint as such, however, and we therefore defer further discussion of it for now. We’ll come back to it in the next chapter.

We now proceed to examine, in the next several sections, three general problems that might arise in connection with temporal databases like that of Fig. 13.1, in the absence of suitable constraints: namely, the redundancy problem, the circumlocution problem, and the contradiction problem. (We mentioned these terms in passing in Chapter 5, as you might recall.)

Note: Relvars S_SINCE and SP_SINCE aren’t discussed any further in this chapter (they’re shown again in Fig. 13.4, but that’s all). We’ll come back to them in Chapter 14.

The Redundancy Problem

Consider relvar S_STATUS_DURING. Because {SNO,DURING} is a key, a Tutorial D definition for that relvar might look as follows:

VAR S_STATUS_DURING BASE RELATION

 { SNO SNO , STATUS INTEGER , DURING INTERVAL_DATE }

  KEY { SNO , DURING } ; /* Warning: Inadequate! */

As the comment indicates, however, the KEY constraint here, though it is logically correct, is also inadequate, in a sense. To be specific, it fails to prevent the relvar from containing (for example) both of the following tuples at the same time:

As you can see, these two tuples display a certain redundancy, inasmuch as the status for supplier S4 on day 6 is effectively stated twice. Clearly, it would be better if we were to replace the two tuples shown by the following single tuple:

Observe now that if the two original tuples were the only tuples in some relation and we were to pack that relation on DURING, we would wind up with a relation containing only the tuple just shown. Loosely speaking, therefore, we might say the tuple just shown is a “packed” tuple, obtained by packing the two original tuples on DURING (“loosely speaking” because, of course, the operation of packing really applies to relations, not tuples). So what we want to do is replace those two original tuples by that “packed” tuple. Indeed, as pointed out in Chapter 5, not performing that replacement—i.e., permitting both original tuples to appear—would be as bad as permitting duplicate tuples to appear, in a sense. What’s more, if both original tuples did appear, the relvar would be in violation of its own predicate! Consider the tuple containing the interval [d06:d07]. That tuple says among other things that supplier S4 did not have status 25 on the day immediately before day 6. But then the other tuple says among other things that supplier S4 did have status 25 on day 5, and of course day 5 is the day immediately before day 6.¹

The Circumlocution Problem

The KEY constraint shown in the previous section for S_STATUS_DURING is inadequate in another way also. To be specific, it fails to prevent the relvar from containing (for example) both of the following tuples at the same time:

Here there’s no redundancy as such, but there’s a certain circumlocution, inasmuch as we’re taking two tuples to say what could be better said with just a single “packed” tuple (the same one as before, in fact):

In fact, not replacing the two original tuples by that single “packed” tuple would mean, again, that the relvar would be in violation of its own predicate, as you can easily confirm.

PACKED ON

Now, it should be clear that in order to avoid redundancies and circumlocutions like the ones we’ve been discussing, what we need to do is enforce a constraint—let’s call it Constraint A—along the following lines:

Recall that MERGES is basically the logical OR of OVERLAPS and MEETS. Replacing MERGES by OVERLAPS in Constraint A gives the constraint we need to enforce in order to avoid the redundancy problem; replacing it by MEETS gives the constraint we need to enforce in order to avoid the circumlocution problem.

It should be clear too that there’s a very simple way to enforce Constraint A: namely, by keeping the relvar packed at all times on DURING. We therefore propose a new PACKED ON specification, with syntax PACKED ON (ACL)—ACL standing as usual for a commalist of attribute names²—that can appear in a relvar definition, as here:

VAR S_STATUS_DURING BASE RELATION

 { SNO SNO , STATUS INTEGER , DURING INTERVAL_DATE }

  PACKED ON ( DURING ) /* Warning: Still */

  KEY { SNO , DURING } ; /* inadequate! */

The PACKED ON (DURING) specification here implies that any attempt to update the relvar in such a way that the result is not packed on DURING must be rejected. That is, the relvar must at all times be kept packed on DURING, and hence must at all times be identical to the result of the expression PACK S_STATUS_DURING ON (DURING)—implying among other things that this latter expression can always be replaced by the much simpler one S_STATUS_DURING, an observation that could be of interest to the optimizer. This special syntax thus suffices to solve the redundancy and circumlocution problems; in other words, it solves the problems exemplified by the constraint we referred to in Chapter 5 as Constraint XFT1.³

Note: An argument might possibly be made for providing two separate syntactic extensions, one for solving the redundancy problem and another for solving the circumlocution problem.⁴ Indeed, we’ll give an example later in this chapter of a relvar, TERM, that might be cited in support of such a position. However, we’ve yet to see a truly convincing argument for such a position; for now, therefore, our preference is to kill two birds with one stone and solve both problems at once.

The Contradiction Problem

We continue to focus on relvar S_STATUS_DURING specifically. Unfortunately, the PACKED ON and KEY constraints together are still not quite adequate, because they fail to prevent the relvar from containing (for example) both of the following tuples at the same time:

Here supplier S4 is shown as having a status of both 10 and 25 on days 5 and 6—clearly an impossible state of affairs. In other words, we have a contradiction on our hands; in fact, the relvar is in violation of its own predicate once again, because of course (as you’ll recall) any given supplier is supposed to have exactly one status on any given day.

Note: To say any given supplier is supposed to have exactly one status on any given day is to say, more formally, that if we were to unpack S_STATUS_DURING on DURING, thereby producing a result in which every DURING value consists of a unit interval, then the functional dependency {SNO,DURING} → {STATUS} would hold in that result. (Or, rather, it’s to say the specified functional dependency would still hold in that result—it already holds in S_STATUS_DURING as such, of course, thanks to the specification KEY {SNO,DURING} for that relvar.) We’ll have more to say regarding such matters in the next section, also in the section “Neither PACKED ON nor WHEN / THEN” later in the chapter.

WHEN / THEN

It should be clear that, in order to avoid contradictions like the ones discussed in the previous section, what we need to do is enforce a constraint—let’s call it Constraint B—along the following lines:

Note carefully that, as we’ve already seen, the fact that the relvar is kept packed on DURING isn’t sufficient to enforce Constraint B. Nor, of course, is the fact that {SNO,DURING} is a key. But suppose the relvar were kept unpacked on DURING (ignore for the moment the fact that this supposition is an impossibility, given that, as just mentioned, the relvar is actually kept packed on DURING). Then:

■ All DURING values in that unpacked form would be unit intervals and would thus effectively correspond to individual time points.

■ The sole key for that unpacked form would still be {SNO,DURING}, because any given supplier under contract at any given time has exactly one status at that time. In other words, as noted in the previous section, the functional dependency {SNO,DURING} → {STATUS} would still hold in that unpacked form.

■ Thus, if the original relvar did contain the contradictory tuples shown earlier—

—then the unpacked form would contain (among other things) these two tuples:

And these two tuples would together violate the functional dependency {SNO,DURING} → {STATUS} that’s supposed to hold in the unpacked form. Equivalently, they would violate the constraint that {SNO,DURING} is supposed to be a key for that unpacked form.

It follows that if we were to enforce the constraint that {SNO,DURING} is a key for the unpacked form UNPACK S_STATUS_DURING ON (DURING), then we’d be enforcing Constraint B a fortiori. We therefore propose another new specification, WHEN / THEN, that can appear in a relvar definition and has syntax as illustrated in this example:

VAR S_STATUS_DURING BASE RELATION

 { SNO SNO , STATUS INTEGER , DURING INTERVAL_DATE }

  PACKED ON ( DURING )

  WHEN UNPACKED ON ( DURING ) THEN KEY { SNO , DURING }

  KEY { SNO , DURING } ;

The specification WHEN UNPACKED ON (DURING) THEN KEY {SNO,DURING} implies that any attempt to update the relvar in such a way that the unpacked form of the result violates the functional dependency {SNO,DURING} → {STATUS} must be rejected. This special syntax thus suffices to solve the contradiction problem. Note: For reasons that should become clear later, given the WHEN / THEN specification WHEN UNPACKED ON (ACL) THEN KEY {BCL}, where ACL and BCL are both commalists of attribute names, every attribute mentioned in ACL must also be mentioned in BCL.

It follows from the foregoing discussion that the WHEN / THEN, PACKED ON, and KEY specifications are together sufficient—at last—to fix all of the problems we’ve been discussing in this chapter so far. However, it can’t be denied that those specifications do seem to be a little clumsy, or cumbersome, in combination. In particular, the specifications WHEN UNPACKED ON (DURING) THEN KEY {SNO,DURING} and KEY {SNO,DURING}, taken together, certainly look as if they might somehow be saying the same thing twice. It therefore seems worth considering the possibility of simplifying the syntax somewhat, and we will. But there are several other topics we need to get out of the way first before we can consider such a possibility in any detail. Those topics are addressed in the next four sections. So we’ll come back to the syntax issue later, in the section “Keys Revisited.”

Combining Specifications

We’ve now met three kinds of constraints that can be specified in a relvar definition: KEY constraints, PACKED ON constraints, and WHEN / THEN constraints. At first sight, therefore, there appear to be eight possible combinations that might be specified for any given relvar. But do all of those combinations make sense?

Well, we can simplify our investigation by first stipulating—until further notice, at any rate—that at least one explicit KEY constraint is always required, since we know from Chapter 3 that every relvar certainly does have at least one key. This stipulation reduces the possibilities from eight to four. Now let R be a relvar with an interval attribute. Then we already know from previous discussions that R might need both a PACKED ON and a WHEN / THEN constraint. So the possibilities we still need to examine are:

These three possibilities are the subject of the next three sections.

PACKED ON without WHEN / THEN

It should be readily apparent without the need for detailed analysis that relvar S_DURING, with its attributes SNO and DURING, is susceptible to redundancy and circumlocution problems analogous to those discussed earlier for relvar S_STATUS_DURING. However, it’s not susceptible to a corresponding contradiction problem. Why not? Answer: Because it’s all key—i.e., its sole key is the attribute combination {SNO,DURING}—and so it can’t possibly contain two tuples that contradict each other.⁵ Thus, PACKED ON (DURING) does apply, but WHEN UNPACKED ON (DURING) THEN KEY {SNO,DURING} is unnecessary. The following thus serves as an adequate definition for this relvar:

VAR S_DURING BASE RELATION

 { SNO SNO , DURING INTERVAL_DATE }

  PACKED ON ( DURING )

  KEY { SNO , DURING } ;

So a WHEN / THEN constraint isn’t needed for this relvar. However, it wouldn’t be wrong to specify one, as here:

VAR S_DURING BASE RELATION

 { SNO SNO , DURING INTERVAL_DATE }

  PACKED ON ( DURING )

  WHEN UNPACKED ON ( DURING ) THEN KEY { SNO , DURING }

  KEY { SNO , DURING } ;

To repeat, the WHEN / THEN constraint here isn’t wrong, but it might lead to some inefficiency in implementation if the system tried to enforce it too blindly. (As we’ll see in the next section, however—and as in fact should be fairly obvious—if some relvar definition does specify both WHEN … THEN KEY {K} and KEY {K}, then enforcing the specified WHEN / THEN constraint will enforce the specified KEY constraint automatically.)

Remarks analogous to the foregoing apply to relvar SP_DURING as well and effectively dispose of that case also. Thus, the following is a possible definition for that relvar:

VAR SP_DURING BASE RELATION

 { SNO SNO , PNO PNO , DURING INTERVAL_DATE }

  PACKED ON ( DURING )

  KEY { SNO , PNO , DURING } ;

From these examples, we see that if the relvar is all key, then no WHEN / THEN is required. But it doesn’t follow that if no WHEN / THEN is required, then the relvar is all key! A counterexample (relvar INFLATION) is given in the section after next, and another, perhaps slightly more convincing, is given in the answer to Exercise 13.8 at the end of the chapter.

WHEN / THEN without PACKED ON

Suppose we’re given a relvar TERM representing U.S. presidential terms, with attributes DURING and PRESIDENT and sole key {DURING}. Here’s a sample value (perhaps we should say rather, here’s part of the value that’s current at the time of writing):

Back to the main thread of our discussion. It should be clear that PACKED ON (DURING) must not be specified for relvar TERM, because (with reference to the sample value shown above) such a constraint would cause the two Reagan tuples to be packed into one and the two Clinton tuples likewise. At the same time, it should be clear that a WHEN / THEN specification is needed, in order to avoid the possibility that the relvar might contain, e.g., both of the following tuples at the same time:

In other words, without such a specification—or something equivalent to such a specification, of course—relvar TERM would be susceptible to the contradiction problem. Here then is a possible relvar definition:⁶

VAR TERM BASE RELATION

 { DURING INTERVAL_… , PRESIDENT NAME }

  WHEN UNPACKED ON ( DURING ) THEN KEY { DURING }

  KEY { DURING } ;

Several further points arise in connection with this example, however. First, note that we certainly do want to avoid the possibility that the relvar might contain, e.g., both of the following tuples at the same time:

(an example of the redundancy problem). At the same time, we don’t want to avoid the possibility that the relvar might contain, e.g., both of the following tuples at the same time:

On the face of it, therefore, it looks as if TERM is an example of a relvar for which we might want to avoid the redundancy problem but not the circumlocution problem (a possibility touched on, briefly, earlier in the chapter).

That said, we have to say too that in our opinion the example intuitively fails, because the circumlocution it displays—if it truly is circumlocution—is intentional. To be specific, if the two Clinton tuples were to be replaced by a single packed tuple, then information would actually be lost (namely, the information that one of the DURING intervals corresponds to Clinton’s first term and the other to his second). In other words, the real problem is that relvar TERM has no explicit “term number” attribute. If we introduce such an attribute, the problem goes away:

(Well, the problem doesn’t entirely go away; the relvar might still contain a pair of tuples that would better be replaced by a single tuple. For example, it might contain two tuples for Carter’s single term, one with a DURING value of [1977:1978] and the other with a DURING value of [1979:1980], thus:

This state of affairs genuinely is an example of the circumlocution problem. But an exactly analogous situation could occur without the TERMNO attribute! The trouble is, before we introduced that attribute, the system couldn’t tell the difference between a genuine circumlocution like this Carter example and a “false circumlocution” like the Clinton example shown earlier.)

Of course, the key constraint KEY {DURING} still holds in this revised version of relvar TERM (with its TERMNO attribute). On the face of it, however, the relvar is now susceptible to all three of our usual problems (redundancy, circumlocution, and contradiction). Redundancy would occur if the relvar were to contain, e.g., both of the following tuples at the same time:

As already noted, circumlocution would occur if the relvar were to contain, e.g., both of the following tuples at the same time:

And contradiction would occur if the relvar were to contain, e.g., both of the following tuples at the same time:

It therefore might appear as if this revised version of TERM does need both PACKED ON and WHEN / THEN, as follows:

VAR TERM BASE RELATION

 { DURING INTERVAL_… , PRESIDENT NAME, TERMNO INTEGER }

  PACKED ON ( DURING )

  WHEN UNPACKED ON ( DURING ) THEN KEY { DURING }

  KEY { DURING } ;

But observe now that there’s no good reason for this relvar ever to have two distinct tuples with the same values for PRESIDENT and TERMNO. The following constraint thus applies:

KEY { PRESIDENT , TERMNO }

And this specification makes the PACKED ON specification superfluous!—not actually wrong, as it was with the original version of the relvar, but certainly unnecessary. The reason is that, since {PRESIDENT,TERMNO} is a key, packing the relvar on DURING can’t possibly have any effect.⁷ (More generally, the operation PACK R ON (ACL) can’t possibly have any effect if R has a key that doesn’t include the set of attributes mentioned in ACL. Thus, there’s no point in specifying the constraint PACKED ON (ACL) for such a relvar.) So our final definition for relvar TERM (revised version) looks like this:

VAR TERM BASE RELATION

 { DURING INTERVAL_… , PRESIDENT NAME, TERMNO INTEGER }

  WHEN UNPACKED ON ( DURING ) THEN KEY { DURING }

  KEY { DURING }

  KEY { PRESIDENT , TERMNO } ;

In other words, relvar TERM, even with the addition of attribute TERMNO, still serves as an example of a relvar for which we would probably want to specify WHEN / THEN and not PACKED ON.

VAR TERM BASE RELATION

 { DURING INTERVAL_… , PRESIDENT NAME , TERMNO INTEGER }

  WHEN UNPACKED ON ( DURING ) THEN KEY { DURING }

  KEY { DURING }

VAR S_STATUS_DURING BASE RELATION

 { SNO SNO , STATUS INTEGER , DURING INTERVAL_DATE }

  PACKED ON ( DURING )

  WHEN UNPACKED ON ( DURING ) THEN KEY { SNO , DURING }

  KEY { SNO , DURING } ;

 { SPOUSE1 NAME , SPOUSE2 NAME , DURING INTERVAL_… }

  PACKED ON ( DURING )

  WHEN UNPACKED ON ( DURING ) THEN KEY { SPOUSE1 , DURING }

  WHEN UNPACKED ON ( DURING ) THEN KEY { SPOUSE2 , DURING }

  KEY { SPOUSE1 , DURING }

  KEY { SPOUSE2 , DURING } ;

Neither PACKED ON nor WHEN / THEN

Suppose we’re given a relvar INFLATION representing inflation rates for a certain country during certain intervals of time. The attributes are DURING and RATE, and the sole key is {DURING}. Here’s a sample value, showing that the inflation rate was 18 percent for the first three months of the year, went up to 20 percent for the next three months, stayed at 20 again for the next three months (but went up to 25 percent in month 7), …, and averaged out at 20 percent for the year as a whole:

Note: This relvar is perhaps not very well designed (or so it could be argued, at any rate), since it contains monthly, quarterly, and annual information all mixed together; that is, it might be better to replace it by three separate relvars. But bad or not, the design is certainly a possible one, and we’ll stay with it for the sake of the discussion.

It should be clear, then, that this relvar must not be kept packed on DURING—i.e., PACKED ON (DURING) must not be specified—because if it were, then (in terms of the sample data shown above) the three tuples with RATE = 20 would be packed into one, and we would lose the information that the inflation rate for months 4-6 and months 7-9 was 20 percent (as it was also for the year overall). What’s more, unpacking the relvar on DURING also causes information to be lost, in general (try it on the sample data above if you don’t immediately see why). We could if we like specify the following:

WHEN UNPACKED ON ( DURING ) THEN KEY { DURING , RATE }

But this specification merely says, in effect, that the result of UNPACK INFLATION ON (DURING) is all key and thus never contains any duplicate tuples, and this “constraint” is thus no constraint at all, because no relation ever contains any duplicate tuples.

So relvar INFLATION does seem to be an example of a relvar for which it doesn’t really seem to make sense to specify either PACKED ON or WHEN / THEN. The relvar definition thus becomes simply:

VAR INFLATION BASE RELATION

 { DURING INTERVAL_… , RATE INTEGER }

  KEY { DURING } ;

In fact, this relvar is subject to none of our usual redundancy, circumlocution, and contradiction problems—or rather, to state the matter more precisely, it’s impossible to tell the difference between (a) a value of the relvar that does suffer from such problems and (b) a value of the relvar that looks as if it suffers from such problems but in fact is correct and doesn’t.

Keys Revisited

Despite—or perhaps because of!—the discussions of the last few sections, it does seem likely in practice that relvars with interval attributes will often be subject to both a PACKED ON constraint and a WHEN / THEN constraint (not to mention the required KEY constraint). For that reason, it seems desirable to come up with some syntax that combines the functionality of all three. We therefore propose another shorthand; to be specific, we propose that the definition of any given relvar R should be allowed to contain a specification of the following form:

USING ( ACL ) : KEY { K }

Here:

PACKED ON ( ACL )

WHEN UNPACKED ON ( ACL ) THEN KEY { K }

KEY { K }

We refer to {K} here as a U_key for short (but see further discussion below). Using this shorthand, the definition of relvar S_STATUS_DURING, for example, might be simplified to just:

VAR S_STATUS_DURING BASE RELATION

 { SNO SNO , STATUS INTEGER , DURING INTERVAL_DATE }

  USING ( DURING ) : KEY { SNO , DURING } ;

Suppose now that the commalist of attribute names ACL within a given U_key specification is empty (i.e., contains no attribute names at all), thus:

USING ( ) : KEY { K }

By definition, this specification is shorthand for:

PACKED ON ( )

WHEN UNPACKED ON ( ) THEN KEY { K }

KEY { K }

So:

It follows that we can take a regular KEY specification of the form KEY {K} to be shorthand for a certain U_key specification—namely, one of the form USING ( ) : KEY {K}. In other words, regular KEY constraints are essentially just a special case of our proposed new syntax! Thus, if we redefine the syntax of a regular KEY specification as follows—

[ USING ( ACL ) : ] KEY { K }

—and if we allow the USING specification and colon separator to be omitted if and only if ACL is empty, then we no longer have any need to talk about U_keys as such at all; all keys effectively become U_keys, and we can generalize the meaning of “key” accordingly. And so we will.

Note: It’s occasionally useful to refer to PACKED ON and WHEN / THEN constraints that have, and can have, no logical effect as trivial constraints. In particular, PACKED ON ( ) and WHEN UNPACKED ON ( ) THEN … are both trivial in this sense. So too are:

VAR S_DURING BASE RELATION

 { SNO SNO , DURING INTERVAL_DATE }

  USING ( DURING ) : KEY { SNO , DURING } ;

 { SNO SNO , PNO PNO , DURING INTERVAL_DATE }

  USING ( DURING ) : KEY { SNO , PNO , DURING } ;

USING ( ACL ) : FOREIGN KEY { FK } REFERENCES R1

Putting it all Tgether

We close this chapter by showing the overall effect of the syntactic simplifications discussed in the previous section on our running example (see Fig. 13.4). Note: We revert now to our preferred “combination” design (recall that in the subsection “Foreign U_keys” at the end of the previous section, we were assuming a design that consisted of during relvars only). Observe in particular in that combination design that, contrary to what you might have expected, relvar SP_DURING doesn’t have a foreign U_key referencing S_DURING, nor do relvars S_DURING and S_STATUS_DURING have foreign U_keys referencing each other. We’ll have more to say about such matters in the next chapter.

Exercises

Answers

13.1 The redundancy, circumlocution, and contradiction problems are all problems that can arise in connection with relvars having interval attributes. We explain them in terms of relvars S_DURING and S_STATUS_DURING:

■ For relvar S_DURING, the redundancy problem occurs if two or more tuples can have the same SNO value and overlapping DURING values. For example, if supplier S4 is shown in one tuple to be under contract from d05 to d06 and in another to be under contract from d06 to d07, then the information that S4 is under contract on d06 is represented twice.

■ For relvar S_DURING again, the circumlocution problem occurs if two or more tuples can have the same SNO value and DURING values that meet or “abut.” For example, if supplier S4 is shown in one tuple to be under contract from d05 to d05 and in another to be under contract from d06 to d07, then the information that S4 is under contract from d05 to d07 is represented in a roundabout way, using two tuples when one would clearly be enough.

■ For relvar S_STATUS_DURING, the contradiction problem—which can occur only in a relvar that has at least one nonkey attribute¹⁰—arises if two or more tuples can have the same SNO value, overlapping DURING values, and different STATUS values. For example, suppose supplier S4 is shown in one tuple as having status 10 from d04 to d06 and in another as having status 25 from d05 to d07. Then supplier S1 is represented as having both status 10 and status 25 on d05 and d06, thereby violating the constraint that a supplier has just one status at one time.

13.2 

a. A KEY constraint specifies that a given subset of the heading of a given relvar constitutes a superkey for that relvar. The subset in question is generally assumed, but can’t be guaranteed, to be a key as such (i.e., it’s assumed to be irreducible). Note: A superkey that’s not a key as such is said to be a proper superkey.

b. A PACKED ON constraint specifies that the relation that’s the current value of the pertinent relvar at any given time must be in the specified packed form.

c. A WHEN / THEN constraint specifies that a given subset of the heading of a given relvar constitutes a superkey for the specified unpacked form of that relvar. The subset in question is generally assumed, but can’t be guaranteed, to be a key as such for that unpacked form (i.e., it’s assumed to be irreducible).

d. A U_key constraint specifies a commalist ACL of attribute names and a commalist K of attribute names. It’s shorthand for the combination of (a) the PACKED ON constraint PACKED ON (ACL), (b) the KEY constraint KEY {K}, and (c) the WHEN / THEN constraint WHEN UNPACKED ON (ACL) THEN KEY {K}.

13.3 

a. S_STATUS_DURING (redundancy, circumlocution, and contradiction must all be addressed)

b. SP_DURING (contradiction can’t arise)

c. TERM with no TERMNO attribute (“circumlocution”—sort of—must be permitted)

d. INFLATION

13.4 A U_key constraint specifying KEY {K} and an empty USING commalist is equivalent to a regular KEY constraint specifying KEY {K}.

13.5 The following constraints are over and above those shown explicitly in the body of the chapter.

a. No president has more than two terms:
CONSTRAINT C135a IS_EMPTY ( TERM WHERE TERMNO ≠ 1 AND TERMNO ≠ 2 ) ;

b. No presidential term lasts more than four years:
CONSTRAINT C135b IS_EMPTY ( TERM WHERE COUNT ( DURING ) > 4 ) ;

c. For a given president, a tuple with TERMNO = 2 exists only if a tuple also exists with TERMNO = 1, and BEGIN (DURING) in the tuple with TERMNO = 2, if it exists, must be greater than END (DURING) in the tuple with TERMNO = 1:
CONSTRAINT C135c IS_EMPTY
( ( ( TERM RENAME { DURING AS D1 , TERMNO AS T1 } ) JOIN
   ( TERM RENAME { DURING AS D2 , TERMNO AS T2 } ) )
     WHERE T1 < T2 AND BEGIN ( D2 ) ≤ END ( D1 ) ) ;
Note: This formulation assumes Constraint C135a is in effect.

13.6 Such a state of affairs is impossible, except in certain pathological cases (e.g., if the relvar is constrained never to contain more than one tuple). For if USING (ACL) … and USING (BCL) … are both specified, then—among other things—the relvar is apparently to be kept packed on both ACL and BCL at the same time.

13.7 For STUDENT_HISTORY:

USING ( REG_DURING ) : KEY { STUDENTNO , REG_DURING }

For COURSE_OFFERING:

USING ( OFFERED_DURING ) : KEY { COURSENO , OFFERED_DURING }

13.8 This is an example of a relvar for which PACKED ON applies but WHEN / THEN doesn’t (even though, unlike, e.g., relvars S_DURING and SP_DURING, it’s not all key). For example, the following is a possible sample value:

Unpacking this relation on A and DURING yields among things the following pair of tuples:

Thus, {A,DURING} is clearly not a key for the unpacked form. So here’s a possible relvar definition:

VAR ABC BASE RELATION

  { A NAME , B NAME , DURING INTERVAL_DATE }

    PACKED ON ( A , DURING )

    KEY { A , DURING } ;

Note: If we assume that A is dating B at a given time if and only if B is dating A at the same time, we might want to impose a constraint on this relvar to the effect that A < B. The sample value shown above assumes such a constraint is in effect.

As a subsidiary exercise, what changes would be required to the foregoing definition if we wanted to insist that the interval during which A was dating B didn’t properly include the interval during which A was dating some distinct person B’?