4.1 The complete set of FDs—what’s known, formally, as the closure, though it has nothing to do with the closure property of the relational algebra—for relvar SP contains a total of 31 FDs. Here they are:
{ SNO , PNO , QTY } → { SNO , PNO , QTY }
{ SNO , PNO , QTY } → { SNO , PNO }
{ SNO , PNO , QTY } → { SNO , QTY }
{ SNO , PNO , QTY } → { PNO , QTY }
{ SNO , PNO , QTY } → { SNO }
{ SNO , PNO , QTY } → { PNO }
{ SNO , PNO , QTY } → { QTY }
{ SNO , PNO , QTY } → { }
{ SNO , PNO } → { SNO , PNO , QTY }
{ SNO , PNO } → { SNO , PNO }
{ SNO , PNO } → { SNO , QTY }
{ SNO , PNO } → { PNO , QTY }
{ SNO , PNO } → { SNO }
{ SNO , PNO } → { PNO }
{ SNO , PNO } → { QTY }
{ SNO , PNO } → { }
{ SNO , QTY } → { SNO , QTY }
{ SNO , QTY } → { SNO }
{ SNO , QTY } → { QTY }
{ SNO , QTY } → { }
{ PNO , QTY } → { PNO , QTY }
{ PNO , QTY } → { PNO }
{ PNO , QTY } → { QTY }
{ PNO , QTY } → { }
{ SNO } → { SNO }
{ SNO } → { }
{ PNO } → { PNO }
{ PNO } → { }
{ QTY } → { QTY }
{ QTY } → { }
{ } → { }The only ones that aren’t trivial are the following four:
{ SNO , PNO } → { SNO , PNO , QTY }
{ SNO , PNO } → { SNO , QTY }
{ SNO , PNO } → { PNO , QTY }
{ SNO , PNO } → { QTY }The only irreducible ones are the following eleven:
{ SNO , PNO } → { SNO , PNO , QTY }
{ SNO , PNO } → { SNO , PNO }
{ SNO , PNO } → { SNO , QTY }
{ SNO , PNO } → { PNO , QTY }
{ SNO , PNO } → { QTY }
{ SNO , QTY } → { SNO , QTY }
{ PNO , QTY } → { PNO , QTY }
{ SNO } → { SNO }
{ PNO } → { PNO }
{ QTY } → { QTY }
{ } → { }4.2 Yes, it is (“whenever two tuples agree on X, they also agree on Y” implies a comparison between the projections of the tuples in question on the attributes of X and Y).
4.3 No answer provided.
4.4 First of all, here are the two definitions, numbered for purposes of subsequent reference:
Relvar R is in 2NF if and only if, for every key K of R and every nonkey attribute A of R, the FD K → {A} is irreducible.
Relvar R is in 2NF if and only if, for every nontrivial FD X → Y that holds in R, at least one of the following is true: (a) X is a superkey; (b) Y is a subkey; (c) X is not a subkey.
Now, Definition 2 says R isn’t in 2NF if and only if there exists a nontrivial FD X → Y that holds in R such that X isn’t a superkey and Y isn’t a subkey and X is a subkey. But if X is a subkey and not a superkey, it must be a proper subkey; thus, Definition 2 effectively says R isn’t in 2NF if and only if there exists a nontrivial FD X → Y that holds in R such that X is a proper subkey and Y isn’t a subkey. So let K be a key that includes X as a proper subkey. Then the FD K → Y holds in R and is reducible, whence it follows that the FD K → {A} holds in R and is reducible for every attribute A contained in Y. So Definition 2 implies Definition 1. Following this argument in the reverse direction will likewise show that Definition 1 implies Definition 2.
4.5 Consider the following argument.
Let relvar R not be in 2NF. Then there must be some key K of R and some nonkey attribute A of R such that the FD K → {A} (which holds in R, necessarily) is reducible—meaning some attribute can be dropped from K, yielding K′ say, such that the FD K′ → {A} still holds. Hence K must be composite.
This argument appears to show that the answer to the exercise must be yes—i.e., if a relvar isn’t in 2NF, it must have a composite key. But the argument is incorrect! Here’s a counterexample. Let USA be a binary relvar with attributes COUNTRY and STATE; the predicate is STATE is part of COUNTRY, but COUNTRY is the United States in every tuple. Now, {STATE} is the sole key for this relvar, and the FD {STATE} → {COUNTRY} thus certainly holds. However, the FD {} → {COUNTRY} clearly holds as well (see the answer to Exercise 4.10 below); the FD {STATE} → {COUNTRY} is thus reducible, and so the relvar isn’t in 2NF, and yet the key {STATE} isn’t composite.
4.6 No! By way of a counterexample, consider relvar USA from the answer to the previous exercise. That relvar is subject to the FD {} → {COUNTRY}, which is neither trivial nor an arrow out of a superkey, and so the relvar isn’t in BCNF. (In fact, of course, it isn’t even in 2NF, as we saw in the answer to the previous exercise.) It follows that the relvar can be nonloss decomposed into its two unary projections on {COUNTRY} and {STATE}, respectively. (Note that the corresponding join, needed to reconstruct the original relvar, is in fact a cartesian product.)
4.7 Yes. If no nontrivial FDs hold at all—which is certainly the case for an “all key” relvar—then there’s no nontrivial FD that holds for which the determinant isn’t a superkey, and so the relvar is in BCNF.
4.8
CONSTRAINT ...
COUNT ( SNP { SNO , SNAME } ) = COUNT ( SNP { SNO } ) ;
CONSTRAINT ...
COUNT ( SNP { SNO , SNAME } ) = COUNT ( SNP { SNAME } ) ;By the way, this trick for specifying that an FD holds—i.e., by stating that two projections have the same cardinality—certainly does the job; as noted in Chapter 2, however, it’s hardly very elegant, and for that reason I showed a different approach, using AND, RENAME, and JOIN, in that chapter. Alternatively, Hugh Darwen and I have proposed[190] that Tutorial D should support another form of CONSTRAINT statement in which the usual boolean expression is replaced by the combination of a relational expression and one or more key specifications. Using this syntax, the foregoing constraints could be stated thus:
CONSTRAINT ... SNP { SNO , SNAME } KEY { SNO } KEY { SNAME };Explanation: Think of the relational expression—SNP{SNO,SNAME}, in the example—as defining some temporary relvar (perhaps a view); then the key specifications—KEY {SNO} and KEY{SNAME}, in the example above—indicates that the specified attributes constitute keys for that relvar.
As an aside, I note that Darwen and I have also proposed allowing foreign key constraints to be specified for expressions in the same kind of way.
4.9 Let the FD X → Y hold in R. By definition, X and Y are subsets of the heading of R. Given that a set of n elements has 2n possible subsets, it follows that each of X and Y has 2n possible values, and hence an upper limit on the number of possible FDs that might hold in R is 22n. For example, if R is of degree five, the maximum number of FDs that might hold is 1,024 (of which 243 are trivial). Subsidiary exercises: (a) Where did that figure of 243 come from? (b) Suppose those 1,024 FDs do all in fact hold. What can we conclude about R in that case? (Answer: It must have cardinality less than two. The reason is that one FD that holds in such a case is {} → H, where H is the heading; it follows that {} is a key, and so R is constrained to contain at most one tuple, as explained in the answer to the next exercise.)
As for how many keys R can have: Let m be the smallest integer greater than or equal to n/2. R will have the maximum possible number of keys if either (a) every distinct set of m attributes is a key or (b) m is odd and every distinct set of (m-1) attributes is a key. Either way, it follows that the maximum number of keys is n! / (m! * (n-m)!).[191] For example, a relvar of degree five can have at most ten distinct keys.
4.10 Let the specified FD X → Y hold in relvar R. Now, every tuple (regardless of whether it’s a tuple of R) has the same value—namely, the 0-tuple—for the projection of that tuple over the empty set of attributes. If Y is empty, therefore, the FD X → Y holds for all possible sets X of attributes of R; in fact, it’s a trivial FD (and so it isn’t very interesting), because the empty set is a subset of every set and so Y is definitely a subset of X in this case. On the other hand, if X is empty, the FD X → Y means that, at any given time, all tuples of R have the same value for Y (since they certainly all have the same value for X). What’s more, if Y in turn is the heading of R—in other words, if X is a superkey—then R is constrained to contain at most one tuple. Note: In this latter case, X isn’t just a superkey but a key, since it’s certainly irreducible. What’s more, it’s the only key, because every other subset of the heading includes it as a proper subset.
4.11 Consider a relvar in the database catalog whose purpose is to record the FDs that hold in various relvars in the database. Given that an FD is an expression of the form X → Y where X and Y are sets of attribute names (see Chapter 5), a reasonable design for that catalog relvar is one with attributes R (relvar name), X (determinant), and Y (dependant), and predicate X → Y holds in R. For any given value of R, then, the values of X and Y are relations of degree one, whose tuples contain names of attributes of the relvar named R.
For another example, involving a “user relvar” instead of a relvar in the catalog, you might like to think about the following problem:
I decided to throw a party, so I drew up a list of people I wanted to invite and made some preliminary soundings. The response was good, but several people made their acceptance conditional on the acceptance of certain other invitees. For example, Bob and Cal both said they would come if Amy came; Fay said she would come if Don and Eve both came; Guy said he would come anyway; Hal said he would come if Bob and Amy both came; and so on. Design a database to show whose acceptance is based on whose. (With acknowledgments to Hugh Darwen.)
It seems to me that a reasonable design here would involve a relvar with two attributes X and Y, both relation valued, and predicate The set of people X will attend if and only if the set of people Y will attend. Subsidiary exercise: Can you think of any refinements you might want to make to this design? (Hint: Is it true that Bob will attend if and only if Bob will attend?)
4.12 Well, I don’t know what you conclude, but I know what I do. One thing I conclude is that we should always be on our guard against getting seduced by the latest fad. I could say quite a lot more on this subject, but I don’t think this appendix is the appropriate place to do so.
4.13 There are two cases to consider: (a) The relation depicted is a sample value for some relvar R; (b) the relation depicted is a sample value for some relational expression rx, where rx is something other than a simple relvar reference (where a relvar reference is basically just the pertinent relvar name). In Case (a), double underlining simply indicates that a primary key PK has been declared for R and the pertinent attribute is part of PK. In Case (b), you can think of rx as the defining expression for some temporary relvar R (think of it as a view defining expression and R as the corresponding view, if you like); then double underlining indicates that a primary key PK could in principle be declared for R and the pertinent attribute is part of PK.
4.14 I assume for the sake of this exercise and the next that the relation shown in Figure 4-1 is a sample value for a relvar SPQ. Here then are Tutorial D formulations (not the only ones possible) of the two queries:
Observe that the first of these expressions involves a restriction followed by an ungrouping, while the second involves an ungrouping followed by a restriction (there’s the asymmetry). Note: The UNGROUP operator hasn’t been discussed prior to this point, but its semantics should be obvious from the foregoing examples. Basically, it’s used to map a relation with an RVA to one without such an attribute. (There’s a GROUP operator too, for “going the other way”—that is, mapping a relation without an RVA to one with one.) For further discussion, see SQL and Relational Theory.
4.15 Here I think it might be helpful to give part of the Tutorial D grammar for <relation assign>, which is the fundamental relational update operator in Tutorial D. (The names of the syntactic categories are meant to be intuitively self-explanatory.)
<relation assign>::=<relvar name>:=<relation exp>|<insert>|<delete>|<update><insert>::= INSERT<relvar name> <relation exp><delete>::= DELETE<relvar name><relation exp>| DELETE<relvar name>[ WHERE<boolean exp>]<update>::= UPDATE<relvar name>[ WHERE<boolean exp>] : {<attribute assign commalist>}
And an <attribute assign>, if the attribute in question is relation valued, is basically just a <relation assign> (except that the pertinent <attribute name> appears in place of the target <relvar name> in that <relation assign>), and that’s where we came in. Here then are Tutorial D statements for the required updates:
4.16 No answer provided—except to note that I was just as confused as everybody else, back in 1995! (But at least I corrected my error in subsequent editions of the subject book.)