5.1 The join of a single relation, JOIN{r}, is just r; the join of no relations at all, JOIN{}, is TABLE_DEE (the only relation of degree zero and cardinality one). For further explanation, see SQL and Relational Theory.
5.2 See the body of the chapter.
5.3 FDs c. and d. (only) are trivial. All eight FDs a.- h. are satisfied by the current value of relvar S. All but h. hold in relvar S. FDs a., c., e., and g. are irreducible with respect to relvar S; FDs b., d., and f. are reducible. (As for h., the question of irreducibility doesn’t arise, since that FD doesn’t hold in the relvar. Check the definition of FD irreducibility if you don’t immediately grasp this point.)
5.4 Heath’s Theorem (original version) says that if (a) relation r has heading H, (b) X, Y, and Z are subsets of H whose union is equal to H, and (c) r satisfies the FD X → Y, then (d) r is equal to the join of its projections on XY and XZ (where XY denotes the union of X and Y, and similarly for XZ). In what follows, I show the proof of this theorem in exhaustive detail. Note: The expression “t ∈ r” can be read as “tuple t appears in relation r.”
First of all, consider the simplest possible case, in which X, Y, and Z are singleton sets (i.e., contain just one attribute each). Let the attributes in question be A, B, and C, respectively. Now, we know from the answer to Exercise 3.2 that no tuple of r is lost by taking the projections r1 over XY (= {A,B}) and r2 over XZ (= {A,C}), respectively, and then joining r1 and r2 back together again. I now show that, conversely, every tuple of the join is indeed a tuple of r (in other words, the join doesn’t generate any “spurious” tuples). Let (a,b,c) ∈ JOIN {r1,r2}. In order to generate such a tuple in the join, we must have (a,b) ∈ r1 and (a,c) ∈ r2. Hence there must exist tuples (a,b,c′) ∈ r and (a,b′,c) ∈ r for some b′ and some c′. But r satisfies {A} → {B}; hence b = b′, and so (a,b,c) ∈ r.
The next simplest case is the one in which X, Y, and Z aren’t necessarily singleton sets but are pairwise disjoint. In this case, we can regard the attributes constituting X as a single composite attribute (and similarly for Y and Z), and the argument of the previous paragraph then applies directly.
We now need to consider what happens if X, Y, and Z aren’t pairwise disjoint. There are three cases to consider: X and Y not disjoint, X and Z not disjoint, and Y and Z not disjoint.
First, then, let X and Y not be disjoint, but let X and Z be disjoint and let Y and Z be disjoint (hence Z = H - XY). Recall now that if X → Y is satisfied, then so is X+ → Y- for all subsets Y- of Y. It follows that the FD X → Y - X is satisfied. But X and Y - X are disjoint; by the previous result, therefore, r is equal to the join of its projections on (a) the union of X and Y - X and (b) XZ. But (again) X and Y - X are disjoint, so their union is equal to XY. So the theorem applies in this case also, and we can (and I will) assume without loss of generality in the remainder of the proof that X and Y are disjoint.
Now let X and Z not be disjoint, but let Y and Z be disjoint. By the previous result, then, r is equal to the join of its projections on (a) XY and (b) the union of X and Z - X. But the union of X and Z - X is equal to XZ. So the theorem applies in this case also, and we can (and I will) assume without loss of generality in the remainder of the proof that X and Z are disjoint.
Now let Y and Z not be disjoint. Let W = Z - Y. Since r satisfies the FD X → Y, then, it also satisfies the FD X → Y - W, and Y - W and Z are disjoint. By the previous result, therefore, r is equal to the join of its projections on (a) the union of X and Y - W and (b) XZ. I now appeal to a lemma, easily proved (see below), to the effect that if (a) r1 and r2 are projections of r such that JOIN{r1,r2} = r, (b) H′ is a subset of H but a superset of the heading of r1, and (c) r′ is the projection of r on H′, then (d) JOIN{r′,r2} = r; in other words, loosely, r1 can be extended with arbitrary attributes of r2 without altering the result of the join. From this lemma, it follows immediately that r is equal to the join of its projections on XY and XZ; so the theorem applies in this case also. Conclusion: Heath’s Theorem is valid in all possible cases.
Lemma: Let r have heading H and let H be partitioned into A, B, C, and D, and assume for simplicity that none of these four subsets is empty. (Extending the proof to cover the case where that assumption fails to hold is left as a subsidiary exercise.) Without loss of generality, we can treat A, B, C, and D as if they were individual attributes. So let r1 = R{A,B} and r2 = r{B,C,D}, and let (a,b) ∈ r1 and (b,c,d) ∈ r2. Since r = JOIN{r1,r2}, it follows that (a,b,c,d) ∈ r; hence (a,b,c) ∈ r{A,B,C} and (b,c,d) ∈ r{B,C,D}; hence (a,b,c,d) ∈ JOIN{r{A,B,C},r{B,C,D}}. The desired result follows—r{B,C,D} is r2, and r{A,B,C} can be taken as r′, with H′ = {A,B,C}. End of lemma.
The converse of Heath’s Theorem would say that if relation r is equal to the join of its projections on XY and XZ, then r satisfies the FD X → Y. This converse is false. To show this is so, it’s sufficient to exhibit a counterexample. So consider a relvar CTX, with attributes CNO (course), TNO (teacher), and XNO (textbook), and predicate Course CNO can be taught by teacher TNO and uses textbook XNO. Here’s a sample value for this relvar:
This sample value is equal to the join of its projections on {CNO,TNO} and {CNO,XNO}, but it clearly fails to satisfy the FD {CNO} → {TNO} (or the FD {CNO} → {XNO}, come to that). Note: I’ll have more to say about this particular example in Chapter 12.
5.5 See the body of the chapter.
5.6 Suppose we start with a relvar with attributes D, P, S, L, T, and C corresponding to parameters of the predicate in the obvious way. Then the following nontrivial FDs hold in that relvar:
{ L } → { D , P , C , T }
{ D , P , C } → { L , T }
{ D , P , T } → { L , C }
{ D , P , S } → { L , C , T }A possible set of BCNF relvars is:[192]
SCHEDULE { L , D , P , C , T }
KEY { L }
KEY { D , P , C }
KEY { D , P , T }
STUDYING { S , L }
KEY { S , L }Note that the FD {D,P,S} → {L,C,T} is “lost” in this decomposition (see Chapter 6).
5.7 The simplest design is:
EMP { ENO , ENAME , SALARY }
KEY { ENO }
PGMR { ENO , LANG }
KEY { ENO }
FOREIGN KEY { ENO } REFERENCES EMPEvery employee has a tuple in EMP (and EMP has no other tuples). Employees who happen to be programmers additionally have a tuple in PGMR (and PGMR has no other tuples). Note that the join of EMP and PGMR gives full information—employee number, name, salary, and language skill—for programmers (only).
The only significant difference if programmers could have an arbitrary number of language skills is that relvar PGMR would be “all key” (i.e., its sole key would be {ENO,LANG}).
5.8 Yes, they are (of course!).