2.1 The Information Principle is a fundamental principle that underpins the entire relational model. It can be stated as follows:

Note that SQL tables (at least, SQL tables in the database) that involve left to right column ordering, or contain duplicate rows or nulls, all violate The Information Principle (see the answer to the next exercise). Interestingly, however, SQL tables with anonymous columns or columns with nonunique names apparently don’t violate the principle. The reason is that the principle as stated applies explicitly to relvars or relations in the database. And while SQL tables in general can have anonymous columns or columns with nonunique names, such tables can’t be part of the database as such. This state of affairs suggests rather strongly that The Information Principle could do with a little tightening up.

2.2 a. True. b. True. c. True. d. True. e. True. f. True. g. True. h. False. (However, it’s “almost” true; there are two small exceptions, both of which I’ll simplify just slightly for present purposes. The first is that if relation r is of type T, then no attribute of r can itself be of type T. The second is that no relation in the database can have an attribute of any pointer type.) i. True. Subsidiary exercise: Would any of these answers change if the original statements are were framed in terms of SQL tables instead of relations and relvars? (Answer: Yes, they would all change except for a. and h. In the case of h., moreover, the answer ought really to change too, from “False” to “False, but even more so.” One reason for this state of affairs—not the only one—is that SQL has no proper notion of table type, and SQL columns thus can’t possibly be of such a type a fortiori.)

2.3 a. True. b. True. c. True. Note: Perhaps I should state for the record here that throughout this book, in accordance with normal practice, I take expressions of the form “B is a subset of A” to include the possibility that B and A might be equal. Thus, e.g., every heading is a subset of itself, and so is every body, and so is every tuple. When I want to exclude such a possibility, I’ll talk explicitly in terms of proper subsets. For example, the body of our usual suppliers relation is certainly a subset of itself, but not a proper subset of itself (no set is a proper subset of itself). What’s more, the foregoing remarks apply equally to supersets, mutatis mutandis; for example, the body of our usual suppliers relation is a superset of itself, but not a proper superset of itself. More terminology: A set is said to include its subsets. Incidentally, don’t confuse inclusion with containment—a set includes its subsets but contains its elements.

2.4 The reason the term isn’t mentioned in the body of the chapter is that it’s just a synonym for type. (Early relational writings, my own included, tended to use it, but more recent ones use type instead, since it’s shorter and has a more extensive pedigree anyway, at least in the computing world.) Thus, a domain is a named, finite set of values—all possible values of some specific kind: for example, all possible integers, or all possible character strings, or all possible triangles, or all possible XML documents, or all possible relations with a specific heading (etc., etc.). By the way, don’t confuse domains as understood in the relational world with the construct of the same name in SQL, which (as explained in SQL and Relational Theory) can be regarded at best as a very weak kind of type.

2.5 See the body of the chapter.

2.6 Relvar S: Supplier SNO is named SNAME and is located in city CITY, which has status STATUS. Relvar P: Part PNO is named PNAME, has color COLOR and weight WEIGHT, and is stored in city CITY. Relvar SP: Supplier SNO supplies part PNO in quantity QTY.

2.7 No answer provided.

2.8 The Closed World Assumption says, loosely, that everything stated or implied by the database is true and everything else is false.^[188] And The Open World Assumption—yes, there is such a thing—says that everything stated or implied by the database is true and everything else is unknown. What are the implications? Well, first let’s agree to abbreviate Closed World Assumption and Open World Assumption to CWA and OWA, respectively. Now consider the query “Is supplier S6 in Rome?” (meaning, more precisely, “Is there a tuple for supplier S6 in relvar S with CITY value equal to Rome?”). Tutorial D formulation:

     ( S WHERE SNO = 'S6' AND CITY = 'Rome' ) { }

As explained in SQL and Relational Theory, this expression evaluates to either TABLE_DEE or TABLE_DUM (where TABLE_DEE and TABLE_DUM are the only relations of degree zero; TABLE_DEE contains just one tuple, and TABLE_DUM contains no tuples at all). Under the CWA, moreover, if the result is TABLE_DEE, it means the answer is yes, supplier S6 does exist and is in Rome; if the result is TABLE_DUM, it means the answer is no, it’s not the case that supplier S6 exists and is in Rome. Under the OWA, by contrast, TABLE_DEE still means yes, but TABLE_DUM means it’s unknown whether supplier S6 exists and is in Rome.

Now consider the query “If supplier S6 exists, is that supplier in Rome?” (note the logical difference between this query and the one discussed above). Observe that the answer to this query has to be no if relvar S shows supplier S6 as existing but in some city other than Rome, regardless of whether we’re talking about the CWA or the OWA.^[189] So here’s the Tutorial D formulation:

     TABLE_DEE MINUS ( ( S WHERE SNO = 'S6' AND CITY ≠ 'Rome' ) { } )

Note carefully, therefore, that if this expression evaluates to TABLE_DUM, that TABLE_DUM has to mean no, even under the OWA. Thus, the OWA suffers from an inherent ambiguity: Sometimes TABLE_DUM has to mean unknown and sometimes it has to mean no—and of course we can’t say (in general) which interpretation applies when.

Just to beat the point to death: TABLE_DEE and TABLE_DUM simply do mean yes and no, respectively, in the relational world, and there’s no “third relation” of degree zero available to represent the “third truth value” that the OWA fundamentally requires. Thus, the OWA and the relational model are fundamentally incompatible with each other.

2.9 Precise definitions are given in Chapter 5.

2.10 Two values of any kind are equal if and only if they’re the very same value (meaning they must be of the same type, a fortiori). In particular, (a) two tuples t and t′ are equal if and only if they have the same attributes A1, ..., An and for all i (i = 1, ..., n), the value of Ai in t is equal to the value of Ai in t′; (b) two relations r and r′ are equal if and only if they have the same heading and the same body (i.e., their headings are equal and their bodies are equal). Note in particular, therefore, that two “empty relations” (i.e., relations without any tuples) are equal if and only if their headings are equal.

2.11 Yes! However, we would of course want such operators always to produce a valid tuple as a result (i.e., we would want closure for such operations, just as we have closure for relational operations—see the answer to Exercise 2.16 below). For tuple union, for example, we would want the input tuples to be such that attributes with the same name have the same value (and are therefore of the same type, a fortiori). By way of example, let t1 and t2 be a supplier tuple and a shipment tuple, respectively, and let t1 and t2 have the same SNO value. Then the union of t1 and t2, UNION{t1,t2}, is—to use Tutorial D syntax—a tuple of type TUPLE {SNO CHAR, SNAME CHAR, STATUS INTEGER, CITY CHAR, PNO CHAR, QTY INTEGER}, with attribute values as in t1 or t2 or both (as applicable). E.g., if t1 is (S1,Smith, 20,London) and t2 is (S1,P1,300)—to use the shorthand notation for tuples introduced in the body of the chapter—then their union is the tuple (S1,Smith,20,London,P1,300). Note: This operation might reasonably be called tuple join instead of tuple union.

By the way, it’s not just the usual set operators that might be adapted to apply to tuples—the same goes for certain of the well known relational operators, too (as in fact I’ve just suggested). One important example is the tuple projection operator, which is a straightforward adaptation of the relational projection operator. For example, let t be a supplier tuple; then the projection t{SNO,CITY} of t on attributes {SNO,CITY} is that subtuple of t that contains just the SNO and CITY components from t. (Of course, a subtuple is itself a tuple in its own right.) Likewise, t{CITY} is that subtuple of t that contains just the CITY component from t, and t{} is that subtuple of t that contains no components at all (in other words, it’s the 0-tuple—see the next exercise). In fact, it’s worth noting explicitly that every tuple has a projection on the empty set of attributes whose value is, precisely, the 0-tuple.

2.12 The empty tuple (note that there’s exactly one such; equivalently, all empty tuples are equal to one another) is the same thing as the 0-tuple, mentioned in the answer to the previous exercise. As for uses for such a tuple, I’ll just say that, conceptually at least, the fact that such a tuple does exist is crucially important in numerous ways. In particular, the empty tuple is the only tuple in the special relation TABLE_DEE, already mentioned in the answer to Exercise 2.8.

2.13 To say relvar R has an empty key is to say R can never contain more than one tuple. Why? Because every tuple has the same value for the empty set of attributes—namely, the empty tuple (see the answers to the previous two exercises); thus, if R had an empty key, and if R were to contain two or more tuples, we would have a key uniqueness violation on our hands. And, yes, constraining R never to contain more than one tuple could certainly be useful. I’ll leave finding an example of such a situation as a subsidiary exercise.

2.14 A predicate with an empty set of parameters is a proposition. (In other words, a proposition is a degenerate predicate; all propositions are predicates, but “most” predicates aren’t propositions.)

2.15 Definitions of projection and join are given in Chapter 5, but here’s a definition of RENAME:

2.16 The relational algebra consists of operators that (speaking very loosely) allow us to derive “new” relations from “old” ones. Each such operator takes one or more relations as input and produces another relation as output (for example, the difference operator takes two relations as input and “subtracts” one from the other to derive another relation as output)—and that’s the closure property. Note that it’s that property that (among other things) lets us write nested relational expressions; since the output from every operation is the same kind of thing as the input, the output from one operation can become the input to another. For example, we can take the difference between relations r1 and r2 (in that order), feed the result as input to a union with some relation r3, feed that result as input to a projection or restriction, and so on.