■ First of all, we’ve dropped the parts relvar P entirely (hence the revised name “suppliers and shipments”). Note: The term relvar is short for relation variable. Relation variables are discussed in detail in Chapter 3.

■ Second, we’ve removed attribute QTY (“quantity”) from the shipments relvar SP, leaving just attributes SNO and PNO.

■ Third, we (re)interpret that revised SP relvar thus: “Supplier SNO is currently able to supply part PNO. ” In other words, instead of standing for actual shipments of parts by suppliers, as it did in, e.g., reference [45], relvar SP now stands for what might be called potential shipments—i.e., the ability of certain suppliers to supply certain parts.

■ Relvar S represents suppliers under contract. Each such supplier has a supplier number (SNO), unique to that supplier; a supplier name (SNAME), not necessarily unique (though the sample SNAME values shown in Fig. 1.1 do happen to be unique); a status or rating value (STATUS); and a location (CITY). Note: In the rest of this book we’ll refer to “suppliers under contract,” most of the time, as just suppliers for short.

■ Relvar SP represents potential shipments—it shows which suppliers are capable of supplying, or shipping, which parts. Obviously, the combination of SNO and PNO values for a given “potential shipment” is unique to that shipment. Note: In the rest of this book we’ll take the liberty of referring to “potential shipments”—somewhat inaccurately, but very conveniently—as just shipments for short. Also, we’ll assume it’s possible for a given supplier to be under contract at some time and yet not actually be able to supply any parts at that time (supplier S5 is a case in point, given the sample values of Fig. 1.1).

■ The first three lines are type definitions (shown here in outline only; further details are given in the section “Types,” immediately following the present section). The specified types—SNO, PNO, and NAME—are user defined types, and they’re used in the definitions of attributes SNO and SNAME in relvar S and attributes SNO and PNO in relvar SP. By contrast, attributes STATUS and CITY in relvar S are of system defined types—namely, INTEGER (integers) and CHAR (character strings of arbitrary length), respectively—and, of course, no explicit type definitions are needed for such types. Note: In what follows, we’ll assume the availability of another system defined type also: namely, type BOOLEAN (truth values), consisting of just the two values TRUE and FALSE.

■ The next seven lines constitute the definition of relvar S. The keyword VAR indicates that the statement overall defines a variable. The variable in question is called S. The keyword BASE indicates the kind of variable being defined; it stands for “base relvar,” which is the kind of relvar S is. Note: Relvars come in several different varieties, of which the most important are (a) base, or real, relvars and (b) virtual relvars, also called views. In this book, however, we’ll have little to say regarding virtual relvars until we get to Chapter 15; prior to that point, therefore, we’ll adopt the simplifying assumption that the unqualified term relvar always means a base relvar specifically, unless the context demands otherwise.

■ Within the definition for relvar S, lines 2–6 specify the type of the variable being defined. The keyword RELATION shows it’s a relation type, and the next four lines specify the corresponding attributes, where each attribute consists of the applicable attribute name together with the name of the corresponding type. The complete set of attribute specifications is enclosed in braces. No significance attaches to the order in which the attributes are specified within those braces. Note: For a general explanation of how braces are used in Tutorial D, please see Appendix D.

■ Line 7 of the definition for relvar S defines {SNO} to be a key for that relvar.

■ The last six lines constitute the definition of relvar SP. The definition follows the same general pattern as that for relvar S; the only new construct is the foreign key specification in the last line, which defines {SNO} to be a foreign key in relvar SP referencing the “target” key {SNO} in relvar S. Note, incidentally, that relvar SP is “all key.”

■ The set of all integers (type INTEGER)

■ The set of all character strings (type CHAR)

■ The set of all supplier numbers (type SNO)

Aside: Instead of saying that (e.g.) type INTEGER is the set of all integers, it would be more correct to say it’s the set of all integers that are capable of representation in the computer system under consideration. Obviously there’ll be some integers that are beyond the representational capability of any given system. In what follows, however, we won’t usually bother to be quite so precise. End of aside.

■ Every variable is defined, or “declared,” to be of some type, meaning that every possible value of the variable in question is a value of the type in question.

■ Every attribute of every relation is declared to be of some type, meaning that every possible value of the attribute in question is a value of the type in question.

■ Every operator that returns a result is declared to be of some type, meaning that every possible result that can be returned by an invocation of the operator in question is a value of the type in question. Note: An operator that returns a result is called a read-only operator; an operator that returns no result but updates one or more of its arguments instead is called an update operator. Examples of both kinds are given in the subsection “User Defined Operators” later in this section. Further, let Op be an update operator. Since an invocation of Op doesn’t denote a value, Op doesn’t have a declared type (though its parameters do—see the bullet item immediately following).

■ Every parameter of every operator is declared to be of some type, meaning that every possible argument that can be substituted for the parameter in question is a value or variable of the type in question. Note that it must be a variable if the operator in question is an update operator and the argument corresponding to the parameter in question will be updated by an invocation of the operator in question.

■ More generally, every expression is declared to be of some type—namely, the type declared for the outermost operator (necessarily a read-only operator) involved in the expression in question, or equivalently the type of the value denoted by that expression.

Aside: The remarks concerning operators and parameters in the two bullet items immediately preceding require some slight refinement if the operator in question is polymorphic. An operator is said to be polymorphic if it’s defined in terms of some parameter P and the argument corresponding to P can be of different types on different invocations. The equality operator “=” is an obvious example: We can compare values of any type for equality (just so long as the values in question are both of the same type), and so “=” is polymorphic—it applies to integers, and character strings, and supplier numbers, and in fact to values of every type. Analogous remarks apply to the assignment operator “:=”; indeed, we follow reference [49] in requiring both “=” and “:=” to be defined for every type. Further examples of polymorphic operators include aggregate operators such as SUM and MAX (see Chapter 2); operators of the relational algebra such as UNION and JOIN (again, see Chapter 2); and the operators defined for intervals in Part II of this book. End of aside.

■ First, the relational model expressly prohibits relations in the database from having attributes of any pointer type—meaning in particular, albeit a little loosely, that no relation in the database is allowed to have an attribute whose values are pointers to tuples in the database. Note: Relations and tuples are discussed in the next section.

■ The second limitation is a little harder to state, but what it boils down to is this: If relation r has heading H, then no attribute of r can be defined in terms of a relation or tuple type that has that same heading H, at any level of nesting. Note: Headings too are discussed in the next section.

■ Type INTEGER is a scalar type (it has no user visible components); hence, values, variables, and so on of type INTEGER are also all scalar.

■ Relation and tuple types are nonscalar (the pertinent user visible components being the corresponding attributes); hence, relation and tuple values, variables, and so on are also all nonscalar.

Aside: Another term you’ll sometimes hear used to mean “scalar” is encapsulated. Be aware, however, that this term is also used—especially in object oriented contexts—to refer to the physical bundling, or packaging, of code and data (or operator definitions and data representation definitions, to be more precise about the matter). But to use the term in this latter sense is to mix model and implementation considerations; clearly the user shouldn’t care, and shouldn’t need to care, whether code and data are physically bundled together or are kept separate. See reference [36] for further discussion. End of aside.

■ One selector operator, which allows the user to select, or specify, a value of the type in question by supplying a value for each component of the possible representation in question

■ A set of THE_ operators (one such for each component of the possible representation in question), which allow the user to access components of the corresponding possible representation of values of the type in question

Aside: When we say a POSSREP specification causes “automatic definition” of such operators, what we mean is this: Whatever agency—possibly the system, possibly some human user—is responsible for implementing the type in question is also responsible for implementing those operators; moreover, until those operators have been implemented, the process of implementing the type can’t be regarded as complete. End of aside.

Definition: Let T1, T2, …, Tn (n ≥ 0) be type names, not necessarily all distinct. Associate with each Ti a distinct attribute name, Ai; each of the n attribute-name : type-name pairs that results is an attribute. Associate with each attribute Ai an attribute value, vi, of type Ti; each of the n attribute : value pairs that results is a component. Then the set—call it t—of all n components thus defined is a tuple value (or just a tuple for short) over the attributes A1, A2, …, An. The value n is the degree of t; a tuple of degree one is unary, a tuple of degree two is binary, a tuple of degree three is ternary, …, and more generally a tuple of degree n is n-ary. The set H of all n attributes is the heading of t (and the degree and attributes of t are, respectively, the degree and attributes of H).

Definition: Let H be a tuple heading, and let t1, t2, …, tm (m ≥ 0) be distinct tuples all with heading H. Then the combination—call it r—of H and the set of tuples {t1, t2, …, tm} is a relation value (or just a relation for short) over the attributes A1, A2, …, An, where A1, A2, …, An are all of the attributes in H. The heading of r is H; r has the same attributes (and hence the same attribute names and types) and the same degree as that heading does. The set of tuples {t1, t2, …, tm} is the body of r. The value m is the cardinality of r.

■ In terms of the usual tabular picture of a relation—see, e.g., the two examples in Fig. 1.1—the row of column names denotes the heading and the data rows denote the body. Note: Strictly speaking, the rows of column names in such pictures should therefore include the relevant type names; similarly, the data rows should include the relevant attribute names. In practice, however, it’s usual to omit those type and attribute names as we did in Fig. 1.1 (and as we’ll continue to do throughout the rest of the book).

■ Following on from the previous point, observe that of course there’s a logical difference⁷ between an attribute name and an attribute per se. Informally, however, we often use expressions such as “attribute A”—indeed, we’ve done so several times in this chapter already, as you might have noticed—but such expressions must of course be understood as meaning the attribute whose name is A (and whose type has been left unspecified).

■ Observe now that a relation does not directly contain its tuples—it contains a body, and that body in turn contains those tuples. Informally, however, it’s convenient to talk as if relations did contain their tuples directly, and we’ll follow this simplifying convention throughout this book. In particular, we’ll often use the term “empty relation,” a little loosely, to mean a relation whose body is empty.

■ A relation of degree one is said to be unary, a relation of degree two binary, a relation of degree three ternary, …, and a relation of degree n n-ary. A relation of degree zero is said to be nullary.⁸ Note: Perhaps we should say a little more about the nullary case, since the concept might be unfamiliar to you. In fact there are exactly two nullary relations, one that contains just one tuple (necessarily with no components, and hence a nullary tuple or 0-tuple—see the bullet item immediately following), and one that’s empty and thus contains no tuples at all. Following reference [25], we refer to these two relations colloquially as TABLE_DEE and TABLE_DUM, respectively. We’ll meet them again, many times, in later chapters.

Aside: For the benefit of readers who might not be native English speakers, we should explain that the names TABLE_DEE and TABLE_DUM are basically just wordplay on Tweedledee and Tweedledum, who were originally characters in a children’s nursery rhyme and were subsequently incorporated into Through the Looking-Glass and What Alice Found There, by Lewis Carroll. TABLE_DEE is the one with just one tuple, TABLE_DUM is the empty one. End of aside.

■ The term n-tuple is sometimes used in place of tuple (and so we sometimes speak of, e.g., 2-tuples, 4-tuples, 0-tuples, etc.). However, it’s usual to drop the “n-” prefix and speak of just tuples, unqualified. The terms pair, triple, etc., are also used on occasion.

■ No relation ever contains any duplicate tuples.⁹ Note: We should explain precisely what we mean by the term “duplicate tuples.” Here’s a definition:

Definition: Tuples t and t' are duplicates of one another if and only if they have exactly the same attributes A1, A2, …, An and, for all i (i = 1, 2, …, n), the value for Ai in t is equal to the value for Ai in t'. Furthermore—this might seem obvious but it needs to be said—tuples t and t' are equal to each other (i.e., t = t' is true) if and only if they’re duplicates of each other, meaning they’re in fact the very same tuple.

■ There’s no top to bottom ordering to the tuples of a relation (pictures like Fig. 1.1 notwithstanding).

■ There’s no left to right ordering to the attributes of a tuple or relation (pictures like Fig. 1.1 notwithstanding).

■ Every tuple of every relation contains exactly one value, of the appropriate type, for each attribute of the relation in question (in other words, relations are always normalized or, equivalently, in first normal form, 1NF). Note: As you probably know, much of the literature talks about—and SQL products in particular support—the use of what are called “nulls” in attribute positions to indicate that some value is missing for some reason. However, since by definition nulls aren’t values, the notion of a “tuple” containing nulls is a contradiction in terms. A “tuple” that contains nulls isn’t a tuple!—and a “relation” that contains such a “tuple” isn’t a relation. In other words, relations never contain nulls. (In fact, we categorically reject the concept of nulls, at least as that concept is usually understood. A detailed justification for this position can be found in reference [37]. See also references [23], [24], [34], and [90], among many others.)

■ If relation r has heading H, then that relation r is of type RELATION H (and the name of that type is, precisely, “RELATION H”). In fact, RELATION here is a type generator (see the subsection “Relation Types Revisited,” later in this section), and RELATION H is a specific relation type—namely, the type produced by invoking that type generator with heading H as argument. And type RELATION H is said to have the same heading, degree, and attributes as every relation of that type does.

■ Note carefully that, by definition, a relation is a value (a nonscalar value, of course, with a set of user visible components). Fig. 1.1, for example, shows two such values. For emphasis, we sometimes speak of “relation values” explicitly, but we usually abbreviate that term to simply relations (just as we usually abbreviate, e.g., “integer values” to simply integers). See Chapter 3 for further discussion of this and related matters. Note: All of the remarks in this bullet item apply to tuples also, mutatis mutandis.¹⁰

■ Finally, if tuple t has heading H, then that tuple t is of type TUPLE H (and the name of that type is, precisely, “TUPLE H”). In fact, TUPLE here is a type generator (again, see the subsection “Relation Types Revisited”), and TUPLE H is a specific tuple type—namely, the type produced by invoking that type generator with heading H as argument. And type TUPLE H is said to have the same heading, degree, and attributes as every tuple of that type does. Note: If tuple t has heading H, we also say, a trifle informally, that tuple t “conforms to” heading H. Note that if relation r is of type RELATION H, then every tuple in r is of type TUPLE H and thus conforms to heading H.

1.1 Explain in your own words the terms type, possible representation, and selector.

1.2 Explain the difference between scalar and nonscalar types.

1.3 What’s a literal?

1.4 Write a Tutorial D definition for a read-only operator called DOUBLE that takes an integer and doubles it.

1.5 Repeat Exercise 1.4 but make the operator an update operator instead (i.e., the effect of invoking the operator should be to double the value assigned to a specified variable).

1.6 Define the terms heading, attribute, body, tuple, cardinality, and degree. By the way, the following facts are worth bearing in mind:

a. Every subset of a heading is a heading.

b. Every subset of a body is a body.

c. Every subset of a tuple is a tuple.

Aside: The term subset and various related terms are often used somewhat imprecisely in informal writing, and we therefore offer some brief (but accurate) definitions here. Let A and B be sets. Then “A is a subset of B” (or “A is included in B”), written A ⊆ B, means every element of A is also an element of B. By contrast, “A is a proper subset of B” (or “A is properly included in B”), written A ⊂ B, means A is a subset of B but there exists at least one element of B that isn’t also an element of A. So every set is a subset of itself, but no set is a proper subset of itself.
All of the foregoing applies to supersets also, mutatis mutandis. Thus, “B is a superset of A” (or “B includes A”), written B ⊇ A, means the same as “A is a subset of B.” Similarly, “B is a proper superset of A” (or “B properly includes A”), written B ⊃ A, means the same as “A is a proper subset of B.” So every set is a superset of itself, but no set is a proper superset of itself. End of aside.

1.7 State as precisely as you can what it means for two tuples t and t' to be duplicates of each other.

1.8 What’s a relation valued attribute?

1.9 Explain the term relation predicate.

1.10 Explain The Closed World Assumption.

1.11 What’s a type generator?

1.12 Give an example of (a) a tuple literal, (b) a relation literal.

1.4 OPERATOR DOUBLE ( N INTEGER ) RETURNS INTEGER ;
  RETURN ( 2 * N ) ;
END OPERATOR ;

1.5 OPERATOR DOUBLE ( N INTEGER ) UPDATES { N } ;
  N := 2 * N ;
END OPERATOR ;