First of all, here are answers to a couple of exercises that were stated inline in the body of the chapter. The first asked what the difference was, given our usual sample data, between the expressions P JOIN (S{CITY}) and (P JOIN S){CITY}. Answer: The first yields full part details (PNO, PNAME, COLOR, WEIGHT, and CITY) for parts in the same city as at least one supplier, the second yields just CITY values for those same parts (speaking a trifle loosely in both cases).

The second exercise asked what the difference was between an equijoin and a natural join. Answer: Let the relations to be joined be r1 and r2, and assume for simplicity that r1 and r2 have just one common attribute, A. Before we can perform the equijoin, then, we need to do some renaming. For definiteness, suppose we apply the renaming to r2, to yield r3 = r2 RENAME {A AS B}. Then the equijoin is defined to be equal to (r1 TIMES r3) WHERE A = B. Note in particular that A and B are both attributes of the result, and every tuple in that result will have the same value for those two attributes. Projecting attribute B away from that result yields the natural join r1 JOIN r2.

6.1 a. The result has duplicate column names (as well as left to right column ordering). b. The result has left to right column ordering. c. The result has an unnamed column (as well as left to right column ordering). d. The result has duplicate rows (even though the SELECT clause explicitly specifies S.SNO, not SP.SNO, and SNO values are unique in table S). e. Compile time error: S NATURAL JOIN P has no column called S.CITY.^[203] f. Nothing wrong (though it would be nice if CORRESPONDING were specified). g. The result has duplicate rows and left to right column ordering; it also has no SNO column, a fact that might come as a surprise.^[204] h. The result has duplicate column names (as well as left to right column ordering). i. Compile time error: AS specification not allowed (because the expression “(S NATURAL JOIN P)” is neither a table name nor a table subquery—see Chapter 12). j. The result has duplicate column names (as well as left to right column ordering).

6.2 No! In particular, certain relational divides that you might expect to fail don’t. Here are some examples (which won’t make much sense until you’ve read the relevant section of Chapter 7):

6.3 The joining attributes are SNO, PNO, and CITY (each of which is a common attribute for exactly two of the relations to be joined, as it happens). The result predicate is: Supplier SNO is under contract, is named SNAME, has status STATUS, and is located in city CITY; part PNO is used in the enterprise, is named PNAME, has color COLOR and weight WEIGHT, and is stored in city CITY; and supplier SNO supplies part PNO in quantity QTY. Note that both appearances of SNO in this predicate refer to the same parameter, as do both appearances of PNO and both appearances of CITY. Given our usual sample values, the result looks like this:

The simplest SQL formulation is just

     S NATURAL JOIN SP NATURAL JOIN P

(though it might be necessary to prefix this expression with “SELECT * FROM,” depending on context—see Chapter 12).

6.4 In 2-dimensional cartesian geometry, the points (x,0) and (0,y) are the projections of the point (x,y) on the X axis and the Y axis, respectively; equivalently, (x) and (y) are the projections into certain 1-dimensional spaces of the point (x,y) in 2-dimensional space. These notions are readily generalizable to n dimensions (recall from Chapter 3 that relations are indeed n-dimensional).

6.5 Throughout these answers, I show SQL expressions that aren’t necessarily direct transliterations of their algebraic counterparts but are, rather, “more natural” formulations of the query in SQL terms.

6.6 Intersection and product are both special cases of join, so we can ignore them here. The fact that union and join are commutative is immediate from the fact that the definitions are symmetric in the two relations concerned. I now show that union is associative. Let t be a tuple. Using “≡” to stand for “if and only if” (or “is equivalent to”) and “∈” to stand for “appears in,” we have:

     t ∈ r UNION ( s UNION u )  ≡  t ∈ r OR t ∈ ( s UNION u )
                                ≡  t ∈ r OR ( t ∈ s OR t ∈ u )
                                ≡  ( t ∈ r OR t ∈ s ) OR t ∈ u
                                ≡  t ∈ ( r UNION s ) OR t ∈ u
                                ≡  t ∈ ( r UNION s ) UNION u

Note the appeal in the third line to the associativity of OR. The proof that join is associative is analogous. As for SQL, well, let’s first of all ignore nulls and duplicate rows (what happens if we don’t?). Then:

The operators are, however, all associative.

6.7 RENAME is the only one—and even that one’s debatable! See the answer to Exercise 7.3 later in this appendix.

6.8 The product of a single table t is defined to be just t. But the question of what the product of t1 and t2 is if t1 and t2 both contain duplicate rows is a tricky one! See the answer to Exercise 4.4 earlier in this appendix for further discussion.

6.9 Tutorial D on the left, SQL on the right, as usual (the solutions aren’t unique, in general; note too that the Tutorial D solutions in particular could often be improved by using operators to be described in Chapter 7):

6.10 It’s intuitively obvious that all three statements are true. No further answer provided.

6.11 Union isn’t idempotent in SQL, because the expression SELECT * FROM T UNION CORRESPONDING SELECT * FROM T isn’t identically equal to SELECT * FROM T. That’s because if T contains any duplicates, they’ll be eliminated from the result of the union. (And what happens if T contains any nulls? Good question!)

Join is idempotent, and therefore so are intersection and cartesian product—in all cases, in the relational model but not in SQL, “thanks” again to duplicates and nulls.

6.12 As explained in the body of the chapter, the expression r{} denotes the projection of r on no attributes; it returns TABLE_DUM if r is empty and TABLE_DEE otherwise. The answer to the question “What’s the corresponding predicate?” depends on what the predicate for r is. For example, the predicate for SP{} is (a trifle loosely): There exists a supplier SNO, there exists a part PNO, and there exists a quantity QTY such that supplier number SNO supplies part PNO in quantity QTY. Note that this predicate is in fact a proposition; if SP is empty (in which case SP{} is TABLE_DUM) it evaluates to FALSE, otherwise (in which case SP{} is TABLE_DEE) it evaluates to TRUE.

The expression r{ALL BUT} denotes the projection of r on all of its attributes (in other words, it denotes the identity projection of r); it returns r. The corresponding predicate is identical to that for r.

6.13 So far as I know, DB2 and Ingres both perform this kind of optimization (DB2 refers to it as “predicate transitive closure”). Other products might do so too.

6.14 The expression means “Get suppliers who supply all purple parts.” Of course, the point is that (given our usual sample data values) there aren’t any purple parts. The expression correctly returns a relation identical to the current value of relvar S (i.e., all five suppliers, loosely speaking). For further explanation—in particular, for justification of the fact that this is indeed the correct answer—see Chapter 11.

6.15 For S{CITY} D_UNION P{CITY}, a rough equivalent in SQL might look like this:

     SELECT CITY
     FROM ( SELECT CITY FROM S
            UNION  CORRESPONDING
            SELECT CITY FROM P ) AS TEMP
     WHERE  NOT EXISTS
          ( SELECT    CITY FROM S
            INTERSECT CORRESPONDING
            SELECT    CITY FROM P )

This SQL expression isn’t precisely equivalent to the original, however. To be specific, if supplier cities and part cities aren’t disjoint, then the SQL expression won’t fail at run time but will simply return an empty result. Note: The CORRESPONDING specifications could safely be omitted in this example—why, exactly?—but it’s easier, and shouldn’t hurt, always to specify CORRESPONDING, even when it’s logically unnecessary. As for the AS TEMP specification, it’s required—on the subquery in the FROM clause but not on the subquery in the WHERE clause (where in fact it would be illegal!)—for reasons explained in Chapter 7.

Turning now to S{CITY} I_MINUS P{CITY}, a rough equivalent in SQL might look like this:

     SELECT CITY
     FROM ( SELECT CITY FROM S
            EXCEPT CORRESPONDING
            SELECT CITY FROM P ) AS TEMP
     WHERE  NOT EXISTS
          ( SELECT CITY FROM P
            EXCEPT CORRESPONDING
            SELECT CITY FROM S )

Again, however, this SQL expression isn’t precisely equivalent to the original, however. To be specific, if part cities aren’t a subset of supplier cities, then the SQL expression won’t fail at run time but will simply return an empty result.

6.16 Relations r1 and r2 are joinable if and only if attributes with the same name are of the same type (equivalently, if and only if the set theory union of their headings is a legal heading). That’s the dyadic case. Extending the definition to the n-adic case is easy: Relations r1, r2, ..., rn (n > 0) are joinable if and only if, for all i, j (1 ≤ i ≤ n, 1

6.17 It’s possible to define n-adic versions of JOIN, UNION, and D_UNION because the operators (a) are all both commutative and associative and (b) all have a corresponding identity value.

SQL does effectively support (analogs of) n-adic join and union, though not for n < 2. For join, the syntax is:

     [ SELECT * FROM ] t1 NATURAL JOIN t2
                          NATURAL JOIN t3
                            ...........
                          NATURAL JOIN tn

For union, the syntax is:

     SELECT * FROM t1 UNION CORRESPONDING SELECT * FROM t2
                      UNION CORRESPONDING SELECT * FROM t3
                        ................................
                      UNION CORRESPONDING SELECT * FROM tn

An n-adic version of MINUS or I_MINUS makes no sense because MINUS and I_MINUS are neither commutative nor associative, nor do they have a corresponding identity value.

6.18 For a brief justification, see the answer to Exercise 6.12 above. A longer one follows. Consider the projection S{SNO} of (the relation that’s current value of) the suppliers relvar S on {SNO}. Let’s refer to the result of this projection as r; given our usual sample data values, r contains five tuples. Now consider the projection of that relation r on the empty set of attributes, r{}. As we saw in the answer to Exercise 3.16 earlier in this appendix, projecting any tuple on no attributes at all yields an empty tuple; thus, every tuple in r produces an empty tuple when r is projected on no attributes. But all empty tuples are duplicates of one another; thus, projecting the 5-tuple relation r on no attributes yields a relation with no attributes and one (empty) tuple, or in other words TABLE_DEE.

Now recall that every relvar has an associated predicate. For relvar S, that predicate looks like this:

For the projection r = S{SNO}, it looks like this:

And for the projection r{}, it looks like this:

Observe now that this last predicate is in fact a proposition: It evaluates to TRUE or FALSE, unequivocally. In the case at hand, r{} is TABLE_DEE and the predicate (proposition) evaluates to TRUE. But suppose no suppliers at all were represented in the database at this time. Then S{SNO} would yield an empty relation r, r{} would be TABLE_DUM, and the predicate (proposition) in question would evaluate to FALSE.

6.19 The expression returns the current value of table S—unless table P is currently empty, in which case it returns an empty result.