CHAPTER 10

10.1 a. No (see the discussion of relvar SPJ in the body of the chapter for a counterexample). b. No (in fact, as was shown in the answer to Exercise 4.6, a binary relvar isn’t necessarily even in BCNF, or even in 2NF). c. No (see Chapter 13). d. No (again, see Chapter 13). e. See the body of the chapter. f. No (see relvar CTXD in Chapter 9 for a counterexample; see also Chapter 15).

10.2 See the body of the chapter.

10.3 First, I assume no JD has any repeated components, for otherwise the number of JDs would literally be infinite. Second, relvar SP is in 5NF, and in fact in 6NF; we haven’t discussed 6NF yet (see Chapter 13), but I can at least say that if a relvar is in 6NF, then all of the JDs that hold in that relvar will be trivial ones. So the question becomes: How many trivial JDs hold in relvar SP? Well, all such JDs take the form {H,X1,...,Xn}, where H denotes the entire heading and {X1,...,Xn} is a set—possibly empty—of proper subsets of H. Since H is of degree three, it has eight subsets, of which all but one are proper. How many distinct sets are there whose elements are some subset of a prescribed set of seven elements? Well, there’s one such set with no elements at all; there are seven such sets with just one element; and, more generally, there are “7 pick i” such sets with i elements (i = 0, 1, ..., 7).[195] So the total number of sets of proper subsets of H = (7 pick 0) + (7 pick 1) + (7 pick 2) + ... + (7 pick 7) = 1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = 128. So there are 128 trivial JDs that hold in relvar SP. Note: Of those 128, 64 involve an empty component, which might reasonably be ignored—for example, the JDs {H,{}} and {H} are clearly equivalent[196]—thereby reducing the total count to 64.

10.4 See the body of the chapter.

10.5 For the definition, see the body of the chapter. Since an FD isn’t a JD but merely implies one, a trivial FD isn’t a special case. However, the JD implied by a trivial FD is indeed itself trivial in turn. For example, the trivial FD {CITY,STATUS} → {STATUS} holds in the suppliers relvar S. Applying Heath’s Theorem, therefore, we see the trivial JD {AB,AC} holds in S, where A is {CITY,STATUS}, B is {STATUS}, and C is {SNO,SNAME} (and hence AC is the entire heading).

10.6 For an example of a tuple forcing JD, see the SPJ example in the body of the chapter. As for one that’s not tuple forcing, consider, e.g., the JD {{SNO,SNAME,CITY},{CITY,STATUS}} that holds in relvar S (which fails to be tuple forcing, observe, precisely because it has a component that’s a superkey for the pertinent relvar).

10.7 Examples can be obtained from the examples given in the body of the chapter in connection with relvar SPJ by systematically replacing supplier numbers by RNO values, part numbers by ANO values, and project numbers by PNO values. No further answer provided.

10.8 Well, obviously I don’t know whether you have any comments, but I certainly do. However, I don’t think it would be polite to air them here, so I won’t.



[195] In general, the expression “n pick r” denotes the number of ways of picking r elements from a set of n elements.

[196] Proof: For all relations r, JOIN{r{H},r{}} = JOIN{r} = r.