To begin with, then, every relation has a heading and a body, where the heading is a set of attributes and the body is a set of tuples that conform to the heading. For example, referring once again to the suppliers-and-parts database (see Figure 2-1, a repeat of Figure 1-1 from Chapter 1), the heading of the suppliers relation is the set {SNO CHAR, SNAME CHAR, STATUS INTEGER, CITY CHAR}—I’m assuming here for definiteness that attributes SNO, SNAME, STATUS, and CITY are defined to be of types CHAR, CHAR, INTEGER, and CHAR, respectively—and the body of that relation is the set of tuples for suppliers S1, S2, S3, S4, and S5. What’s more, each of those tuples does conform to the pertinent heading, inasmuch as it contains exactly one value, of the applicable type, for each of the attributes SNO, SNAME, STATUS, and CITY (and, of course, nothing else). Note: It would be more precise—and actually more correct—to say that each of those tuples has the pertinent heading, because in fact tuples have headings, just as relations do.

Figure 2-1. The suppliers-and-parts database—sample values

Every relation also has (or is of) a certain type—a certain relation type, to be specific, where the type in question is fully determined by the pertinent heading. Thus, we denote the type of a given relation in Tutorial D by means of the keyword RELATION followed by the applicable heading. For example, here’s the type for the suppliers relation:

RELATION { SNO CHAR , SNAME CHAR , STATUS INTEGER , CITY CHAR }

Next, there’s a logical difference between relations as such and relation variables.^[15] Take another look at Figure 2-1. That figure shows three relations: namely, the relations that happen to exist in the database at some particular time. But if we were to look at the database at some different time, we would probably see three different relations appearing in their place. In other words, S, P, and SP are really variables—relation variables, to be precise—and like all variables they have different values at different times. And since they’re relation variables specifically, their values at any given time are, of course, relation values. Note, however, that the legal values for a given relation variable must all be of the same relation type—i.e., they must all have the same heading—and the type and heading in question are thereby also considered to be the type and heading of the relation variable as such.

By way of elaboration on the foregoing ideas, suppose the relation variable S currently has the value shown in Figure 2-1, and suppose we delete the tuples for suppliers in London:

DELETE ( S WHERE CITY = 'London' ) FROM S ;

Relation variable S now looks like this:

+-------------------------------+
| SNO | SNAME | STATUS | CITY   |
+-----+-------+--------+--------|
| S2  | Jones |     10 | Paris  |
| S3  | Blake |     30 | Paris  |
| S5  | Adams |     30 | Athens |
+-------------------------------+

Conceptually, what’s happened here is that the old value of S (a relation value, of course) has been replaced in its entirety by a new value (another relation value). Now, the old value (with five tuples) and the new one (with three) are rather similar, in a sense, but they certainly are different values. In fact, the DELETE just shown is logically equivalent to, and is indeed defined to be “shorthand” for,^[16] the following relational assignment:

S := S WHERE NOT ( CITY = 'London' ) ;

Or equivalently:

S := S MINUS ( S WHERE CITY = 'London' ) ;

As with all assignments, what happens here is that (a) the source expression on the right side is evaluated and then (b) the value resulting from that evaluation is assigned to the target variable on the left side, with the overall effect already explained.

So DELETE is shorthand for a certain relational assignment—and, of course, an analogous remark applies to INSERT and UPDATE also: They too are basically just shorthand for certain relational assignments. Logically speaking, in fact, relational assignment is the only update operator we really need (a point I’ll elaborate on in the next section).

To sum up: There’s a logical difference between relation values and relation variables. For that reason, I’ll distinguish very carefully between the two from this point forward—I’ll talk in terms of relation values when I mean relation values and relation variables when I mean relation variables. However, I’ll also abbreviate relation value, most of the time, to just relation (exactly as we abbreviate integer value most of the time to just integer). And I’ll abbreviate relation variable most of the time to relvar; for example, I’ll say the suppliers-and-parts database contains three relvars (more specifically, three “real” or base relvars, so called to distinguish them from “virtual” relvars or views).

VAR S BASE RELATION
  { SNO CHAR , SNAME CHAR , STATUS INTEGER , CITY CHAR }
    KEY { SNO } ;

VAR P BASE RELATION
  { PNO CHAR , PNAME CHAR , COLOR CHAR , WEIGHT RATIONAL , CITY CHAR }
    KEY { PNO } ;

VAR SP BASE RELATION
  { SNO CHAR , PNO CHAR , QTY INTEGER }
    KEY { SNO , PNO }
    FOREIGN KEY { SNO } REFERENCES S
    FOREIGN KEY { PNO } REFERENCES P ;

The Tutorial D syntax for relational assignment as such—i.e., as opposed to one of the shorthands such as INSERT or DELETE—takes the following generic form:

R := rx

Here R is a relvar reference (i.e., a relvar name, syntactically speaking), and rx is a relational expression, denoting a relation r, say, of the same type as relvar R. Now, it’s easy to see (thanks to David McGoveran for this observation) that any such assignment is logically equivalent to one of the following form—

R := ( r MINUS d ) UNION i

—where:

These points can conveniently be illustrated by means of a Venn diagram (see Figure 2-2 overleaf). Explanation: In that diagram, r, d, and i are as above, and u is the universal relation of the pertinent type (in other words, u is the relation whose body consists of all tuples with the same heading as R, including, of course, those tuples that currently appear in R). Note that the difference u – r is the absolute complement of r (in other words, u – r is the relation whose body consists of all tuples with the same heading as R that don’t currently appear in R).

Figure 2-2. The delete set d and the insert set i

Of course, the delete set d might be empty, in which case the original assignment is effectively a pure INSERT operation. Or the insert set i might be empty, in which case it’s effectively a pure DELETE operation. Or they might both be empty, in which case the assignment overall effectively degenerates to the “no op” R := R.

It follows from all of the above that the original assignment R := rx is in fact logically equivalent to the following multiple assignment (see Multiple Assignment on page 18 for further discussion of this latter construct):^[19]

DELETE d FROM R , INSERT i INTO R

As a consequence, although I said earlier that assignment as such is really the only update operator we need, we can always (and for intuitive reasons, at least, it turns out to be convenient to do this) think in terms of DELETE and INSERT operations instead. That is, faced with an arbitrary and possibly multiple assignment to relvar R—including in particular the case where the assignment in question is formulated as an explicit UPDATE on R—I propose that we map that assignment to a DELETE on R and an INSERT on R, where the delete set d and the insert set i are well defined, disjoint, and unique. Note: Because of this state of affairs, in what follows I’ll discuss explicit UPDATE operations only when there’s something interesting to say about them. Also, I’ll ignore for the most part the practical problem of actually computing d and i. My primary concern, in this book as in most of my other writings, is always to get the theory right first before worrying about issues of implementation. Of course, I don’t mean to suggest by these remarks that I think implementation issues are unimportant. Au contraire, in fact—checking feasibility of implementation is crucial to ensuring the correctness of the theory.

DELETE d FROM R , INSERT i INTO R

WITH ( R := R MINUS d ) : INSERT i INTO R

WITH ( R := R UNION i ) : DELETE d FROM R

WITH ( DELETE d FROM R ) : INSERT i INTO R

WITH ( INSERT i INTO R ) : DELETE d FROM R

I_DELETE d FROM R , D_INSERT i INTO R

D_INSERT i INTO R , I_DELETE d FROM R

DELETE ( S  WHERE SNO = 'S1' ) FROM S ,
DELETE ( SP WHERE SNO = 'S1' ) FROM SP ;

S := ... , SP := ... ;

UPDATE R : { K := K + A } ;

UPDATE R : { A := -A } ;

R := RELATION { TUPLE { K 1 , A -2 } , TUPLE { K 3 , A 2 } } ;

Every relvar is subject to a set of integrity constraints, or just constraints for short. First of all, as we know from the section Relations and Relvars, any given relvar is constrained to be of a certain type (more specifically, a certain relation type)—namely, the type specified when the relvar in question is defined. For example, here again is the definition of the suppliers relvar S:^[23]

VAR S BASE RELATION
  { SNO CHAR , SNAME CHAR , STATUS INTEGER , CITY CHAR }
    KEY { SNO } ;

As you can see, this definition states explicitly that relvar S is of type RELATION {SNO CHAR, SNAME CHAR, STATUS INTEGER, CITY CHAR}. What’s more, it’s immediate from that specification that attributes SNO, SNAME, STATUS, and CITY are of types CHAR, CHAR, INTEGER, and CHAR, respectively. Note: These latter constraints—the ones on the individual attributes—are examples of what are sometimes called attribute constraints.

To repeat, every relvar (and every attribute, a fortiori) is constrained to be of some type. But relvars in general are also subject to numerous additional constraints, constraints that are typically formulated in Tutorial D by means of explicit CONSTRAINT statements.^[24] The following simple examples are, I hope, self-explanatory (further explanation can be found if you need it in SQL and Relational Theory):

CONSTRAINT CX1 IS_EMPTY ( S WHERE STATUS < 1 ) ;

CONSTRAINT CX2 IS_EMPTY ( S WHERE CITY = 'London' AND STATUS ≠ 20 ) ;

CONSTRAINT CX3 IS_EMPTY ( ( S JOIN SP )
                              WHERE STATUS < 20 AND PNO = 'P6' ) ;

Now, The Third Manifesto requires all constraints to be satisfied at statement boundaries (“immediate checking”). In other words, constraints are checked, logically, at the end of any statement that has the potential to violate them.^[25] Loosely, we can say they’re checked “at semicolons.” Thus, contrary to the SQL standard and certain SQL products, integrity checking is never deferred to end of transaction or COMMIT time.

Finally, note that it’s sometimes convenient to talk in terms of “the” (total) constraint—sometimes the total relvar constraint, for emphasis—for a given relvar R, meaning the logical AND of all of the individual constraints that mention relvar R. It’s also sometimes convenient to talk in terms of “the” (total) constraint—sometimes the total database constraint, for emphasis—for a given database, meaning the logical AND of all of the constraints that mention any relvar in that database.

In Chapter 1, when I introduced the running example (i.e., the suppliers-and-parts database), I said this among other things:

Of course, what in that chapter I called “table S” I’d much rather call “relvar S,” but that’s not the point I want to make here. Rather, the point is that, first, the foregoing text represents the meaning of relvar S as understood by the user; second, the term used in logic for such meanings is predicate (or sometimes interpretation or intended interpretation,but I’ll mostly stay with predicate in this book). In other words, we can say of every relvar that it has an associated predicate, called the relvar predicate for the relvar in question, and that relvar predicate is, in essence, how the relvar in question is understood by the user. Here by way of example is the way I would prefer to state the predicate for relvar S:

And here for the record are the predicates for relvars P and SP:

You can think of a predicate as a truth valued function. Like all functions, it has a set of parameters; it returns a result when it’s invoked; and (because it’s truth valued) that result is either TRUE or FALSE. In the case of the predicate for relvar S, for example, the parameters are SNO, SNAME, STATUS, and CITY (corresponding of course to the attributes of the relvar), and they stand for values of the applicable types (CHAR, CHAR, INTEGER, and CHAR, respectively). When we invoke the function—when we instantiate the predicate, as the logicians say—we substitute arguments for the parameters. Suppose we substitute the arguments S1, Smith, 20, and London, respectively. We obtain:

This latter sentence is in fact a proposition, which in logic is a sentence that has no parameters and evaluates unequivocally to either true or false. (In the case at hand, of course, the proposition is a true one, or so at least we assume for the sake of the example.) Which brings me to another important principle, The Closed World Assumption:

For example, with reference to Figure 2-1 once again, it’s currently a “true fact” that supplier S1 supplies part P1 in quantity 300, because the tuple (S1,P1,300) currently appears in relvar SP. But if we were to delete that tuple from that relvar, we would be saying (in effect) that it’s no longer the case that supplier S1 supplies part P1 in quantity 300.

Now, so far I’ve discussed predicates in connection with relvars specifically. In fact, however, all of the foregoing notions extend in a natural way to arbitrary relational expressions. For example, consider the projection of suppliers on all attributes but CITY (note the Tutorial D syntax for projection):^[28].

S { SNO , SNAME , STATUS }

This expression denotes a relation containing all tuples of the form (s,n,t) such that a tuple of the form (s,n,t,c) currently appears in relvar S for some CITY value c. In other words, the result contains all and only those tuples that correspond to currently true instantiations of the following predicate:

This predicate thus represents the meaning of the expression—the relational expression, that is—S{SNO,SNAME,STATUS}. Observe that it has just three parameters and the corresponding relation has just three attributes; CITY isn’t a parameter to that predicate but what logicians call a “bound variable” instead, owing to the fact that it’s “quantified” by the phrase There exists some city CITY such that. Note: A possibly clearer way of making the same point (i.e., that the predicate has three parameters, not four) is to observe that the predicate in question is effectively equivalent to this one:

Remarks analogous to the foregoing apply to every possible relational expression. To be specific: Every relational expression rx always has an associated meaning, or predicate; moreover, the predicate for rx can always be determined from the predicates for the relvars involved in that expression, in accordance with the semantics of the relational operations involved in that expression.^[29]

Now, relvar predicates as I’ve described them so far are quite informal; in fact, they’re essentially nothing more than a representation in natural language of the fact that the relvar in question has certain attributes (equivalently, is of a certain type). But we could use a somewhat more formal style if we wanted to. For example, given that the suppliers relvar S has attributes SNO, SNAME, STATUS, and CITY, and given also that {SNO} is the sole key for that relvar, we might say the corresponding predicate looks something like this:

is_entity  ( SNO ) AND
has_SNAME  ( SNO , SNAME ) AND
has_STATUS ( SNO , STATUS ) AND
has_CITY   ( SNO , CITY )

Suppose tuple t currently appears in relvar S. Then the foregoing predicate asserts that:

Of course, the system still doesn’t know the entity in question (the entity identified by SNO) is in fact a supplier in the real world—a supplier “under contract,” in fact—nor does it know what it means for something to have an SNAME property or a STATUS property or a CITY property.

In a similar manner, we might say the predicate for the projection of suppliers on all attributes but CITY is:

is_entity  ( SNO ) AND
has_SNAME  ( SNO , SNAME ) AND
has_STATUS ( SNO , STATUS ) AND
EXISTS CITY ( has_CITY ( SNO , CITY ) )

Finally, I’d like to close this section by confessing that everything I’ve said so far regarding relvar predicates in general has deliberately been slightly simplified. Of course, I believe the treatment is adequate for present purposes; for further specifics, however—“the true story,” as it were, or at least a slightly truer one—I refer you to Chapter 4 (“The Closed World Assumption”) of my book Logic and Databases: The Roots of Relational Theory (Trafford, 2007).

Throughout the bulk of this book, I will of course be discussing the operators of the relational algebra in some detail, and for the most part I’ll take it you’re reasonably familiar already with the operators in question (though definitions can be found if you need them in Appendix B). But there are certain useful operators, supported by Tutorial D in particular, that I do need to appeal to fairly frequently but you might not be familiar with, since they’re not discussed in most of the usual textbooks (probably because they’re not supported by SQL—at least, not directly). The first is MATCHING. Here’s a definition:

Here’s an example (“Get suppliers who currently supply at least one part”):

S MATCHING SP

Given our usual sample values, the result looks like this:

+-------------------------------+
| SNO | SNAME | STATUS | CITY   |
+-----+-------+--------+--------|
| S1  | Smith |     20 | London |
| S2  | Jones |     10 | Paris  |
| S3  | Blake |     30 | Paris  |
| S4  | Clark |     20 | London |
+-------------------------------+

Tutorial D also supports a negated form called NOT MATCHING. Here’s the definition:

Here’s an example (“Get suppliers who currently supply no parts at all”):

S NOT MATCHING SP

Given our usual sample values, the result looks like this:

+-------------------------------+
| SNO | SNAME | STATUS | CITY   |
+-----+-------+--------+--------|
| S5  | Adams |     30 | Athens |
+-------------------------------+

The other operator I want to describe briefly here is EXTEND. EXTEND comes in two forms. Here’s a definition of the first:

By way of example, suppose part weights in relvar P are given in pounds, and we want to see those weights in grams. There are 454 grams to a pound, and so we can write:

EXTEND P : { GMWT := WEIGHT * 454 }

Given our usual sample values, the result looks like this:

+------------------------------------------------+
| PNO | PNAME | COLOR | WEIGHT | CITY   | GMWT   |
+-----+-------+-------+--------+--------+--------|
| P1  | Nut   | Red   |   12.0 | London | 5448.0 |
| P2  | Bolt  | Green |   17.0 | Paris  | 7718.0 |
| P3  | Screw | Blue  |   17.0 | Oslo   | 7718.0 |
| P4  | Screw | Red   |   14.0 | London | 6356.0 |
| P5  | Cam   | Blue  |   12.0 | Paris  | 5448.0 |
| P6  | Cog   | Red   |   19.0 | London | 8626.0 |
+------------------------------------------------+

The second form of EXTEND is aimed primarily at what are sometimes called “what if” queries. In other words, it can be used to explore the effect of making certain changes without actually having to make (and subsequently unmake, possibly) the changes in question. Here’s an example (“What if part weights were given in grams instead of pounds?”):

EXTEND P : { WEIGHT := WEIGHT * 454 }

The point here is that the target attribute in the assignment in braces here isn’t a “new” attribute as it was in the previous example; instead, it’s an attribute that already exists in the specified relation (that relation being the current value of relvar P, in the case at hand). The expression overall is defined to be equivalent to the following:

( ( EXTEND P : { GMWT := WEIGHT * 454 } ) { ALL BUT WEIGHT } )
                                            RENAME { GMWT AS WEIGHT }

Note: As you can see, this expansion makes use of the Tutorial D RENAME operator. I think that operator is more or less self-explanatory, but you can find a definition if you need it in Appendix B. For further discussion, see SQL and Relational Theory.

For completeness, here’s a definition of this second form of EXTEND:

This is the final section of this chapter. In it, I want to draw your attention to the important fact that just as there’s a logical difference between relation values and relation variables (relvars), so there’s also a logical difference between database values and database variables, or what might be called dbvars. Here’s a quote from the Manifesto book:

It follows that when we “update some relvar” (within some database), what we’re really doing is updating the pertinent dbvar. (For clarity, I’ll adopt the term dbvar for the remainder of this section.) For example, the Tutorial D statement

DELETE ( SP WHERE QTY < 150 ) FROM SP ;

“updates the shipments relvar SP” and thus really updates the entire suppliers-and-parts dbvar—the “new” database value for that dbvar being the same as the “old” one except that certain shipment tuples have been removed. In other words, while we might say a database “contains variables” (namely, the applicable relvars), such a manner of speaking is really only approximate, and is in fact quite informal. A more formal and more accurate way of characterizing the situation is this:

TUPLE { S  RELATION { SNO CHAR , SNAME CHAR ,
                      STATUS INTEGER, CITY CHAR } ,
        P  RELATION { PNO CHAR , PNAME CHAR ,
                      COLOR CHAR , WEIGHT RATIONAL , CITY CHAR } ,
        SP RELATION { SNO CHAR , PNO CHAR , QTY INTEGER } }

SPDB := TUPLE { S  ( S FROM SPDB ) ,
                P  ( P FROM SPDB ) ,
                SP ( ( SP FROM SPDB ) WHERE NOT ( QTY < 150 ) ) } ;

DELETE ( S  WHERE SNO = 'S1' ) FROM S ,
DELETE ( SP WHERE SNO = 'S1' ) FROM SP ;

SPDB := TUPLE { S  ( ( S FROM SPDB ) WHERE NOT ( SNO = 'S1' ) ,
                P  ( P FROM SPDB ) ,
                SP ( ( SP FROM SPDB ) WHERE NOT ( SNO = 'S1' ) ) } ;

R := rx