solution for A First Course in database systems Chapter 3

1、Exercise 3.1.1Answers for this exercise may vary because of different interpretations.Some possible FDs:Social Security number à nameArea code à stateStreet address, city, state à zipcodePossible keys:Social Security number, street address, city, state, area code, phone numberNeed str

2、eet address, city, state to uniquely determine location. A person could have multiple addresses. The same is true for phones. These days, a person could have a landline and a cellular phoneExercise 3.1.2Answers for this exercise may vary because of different interpretationsSome possible FDs:ID à

3、; x-position, y-position, z-positionID à x-velocity, y-velocity, z-velocityx-position, y-position, z-position à IDPossible keys:IDx-position, y-position, z-positionThe reason why the positions would be a key is no two molecules can occupy the same point.Exercise 3.1.3aThe superkeys are any

4、 subset that contains A1. Thus, there are 2(n-1) such subsets, since each of the n-1 attributes A2 through An may independently be chosen in or out.Exercise 3.1.3bThe superkeys are any subset that contains A1 or A2. There are 2(n-1) such subsets when considering A1 and the n-1 attributes A2 through

5、An. There are 2(n-2) such subsets when considering A2 and the n-2 attributes A3 through An. We do not count A1 in these subsets because they are already counted in the first group of subsets. The total number of subsets is 2(n-1) + 2(n-2).Exercise 3.1.3cThe superkeys are any subset that contains A1,

6、A2 or A3,A4. There are 2(n-2) such subsets when considering A1,A2 and the n-2 attributes A3 through An. There are 2(n-2) 2(n-4) such subsets when considering A3,A4 and attributes A5 through An along with the individual attributes A1 and A2. We get the 2(n-4) term because we have to discard the subse

7、ts that contain the key A1,A2 to avoid double counting. The total number of subsets is 2(n-2) + 2(n-2) 2(n-4).Exercise 3.1.3dThe superkeys are any subset that contains A1,A2 or A1,A3. There are 2(n-2) such subsets when considering A1,A2 and the n-2 attributes A3 through An. There are 2(n-3) such sub

8、sets when considering A1,A3 and the n-3 attributes A4 through An We do not count A2 in these subsets because they are already counted in the first group of subsets. The total number of subsets is 2(n-2) + 2(n-3).Exercise 3.2.1aWe could try inference rules to deduce new dependencies until we are sati

9、sfied we have them all. A more systematic way is to consider the closures of all 15 nonempty sets of attributes. For the single attributes we have A+ = A, B+ = B, C+ = ACD, and D+ = AD. Thus, the only new dependency we get with a single attribute on the left is CàA.Now consider pairs of attribu

10、tes: AB+ = ABCD, so we get new dependency ABàD. AC+ = ACD, and ACàD is nontrivial. AD+ = AD, so nothing new. BC+ = ABCD, so we get BCàA, and BCàD. BD+ = ABCD, giving us BDàA and BDàC. CD+ = ACD, giving CDàA.For the triples of attributes, ACD+ = ACD, but the closure

11、s of the other sets are each ABCD. Thus, we get new dependencies ABCàD, ABDàC, and BCDàA.Since ABCD+ = ABCD, we get no new dependencies.The collection of 11 new dependencies mentioned above are: CàA, ABàD, ACàD, BCàA, BCàD, BDàA, BDàC, CDàA, ABC

12、àD, ABDàC, and BCDàA. Exercise 3.2.1bFrom the analysis of closures above, we find that AB, BC, and BD are keys. All other sets either do not have ABCD as the closure or contain one of these three sets.Exercise 3.2.1cThe superkeys are all those that contain one of those three keys. Tha

13、t is, a superkey that is not a key must contain B and more than one of A, C, and D. Thus, the (proper) superkeys are ABC, ABD, BCD, and ABCD.Exercise 3.2.2ai) For the single attributes we have A+ = ABCD, B+ = BCD, C+ = C, and D+ = D. Thus, the new dependencies are AàC and AàD.Now consider

14、pairs of attributes: AB+ = ABCD, AC+ = ABCD, AD+ = ABCD, BC+ = BCD, BD+ = BCD, CD+ = CD. Thus the new dependencies are ABàC, ABàD, ACàB, ACàD, ADàB, ADàC, BCàD and BDàC.For the triples of attributes, BCD+ = BCD, but the closures of the other sets are each ABCD

15、. Thus, we get new dependencies ABCàD, ABDàC, and ACDàB.Since ABCD+ = ABCD, we get no new dependencies.The collection of 13 new dependencies mentioned above are: AàC, AàD, ABàC, ABàD, ACàB, ACàD, ADàB, ADàC, BCàD, BDàC, ABCàD, ABD

16、àC and ACDàB.ii) For the single attributes we have A+ = A, B+ = B, C+ = C, and D+ = D. Thus, there are no new dependencies.Now consider pairs of attributes: AB+ = ABCD, AC+ = AC, AD+ = ABCD, BC+ = ABCD, BD+ = BD, CD+ = ABCD. Thus the new dependencies are ABàD, ADàC, BCàA and

17、 CDàB.For the triples of attributes, all the closures of the sets are each ABCD. Thus, we get new dependencies ABCàD, ABDàC, ACDàB and BCDàA.Since ABCD+ = ABCD, we get no new dependencies.The collection of 8 new dependencies mentioned above are: ABàD, ADàC, BCà

18、;A, CDàB, ABCàD, ABDàC, ACDàB and BCDàA.iii) For the single attributes we have A+ = ABCD, B+ = ABCD, C+ = ABCD, and D+ = ABCD. Thus, the new dependencies are AàC, AàD, BàD, BàA, CàA, CàB, DàB and DàC.Since all the single attributes clo

19、sures are ABCD, any superset of the single attributes will also lead to a closure of ABCD. Knowing this, we can enumerate the rest of the new dependencies.The collection of 24 new dependencies mentioned above are: AàC, AàD, BàD, BàA, CàA, CàB, DàB, DàC, AB

20、4;C, ABàD, ACàB, ACàD, ADàB, ADàC, BCàA, BCàD, BDàA, BDàC, CDàA, CDàB, ABCàD, ABDàC, ACDàB and BCDàA.Exercise 3.2.2bi) From the analysis of closures in 3.2.2a(i), we find that the only key is A. All other sets either do not h

21、ave ABCD as the closure or contain A.ii) From the analysis of closures 3.2.2a(ii), we find that AB, AD, BC, and CD are keys. All other sets either do not have ABCD as the closure or contain one of these four sets.iii) From the analysis of closures 3.2.2a(iii), we find that A, B, C and D are keys. Al

22、l other sets either do not have ABCD as the closure or contain one of these four sets.Exercise 3.2.2ci) The superkeys are all those sets that contain one of the keys in 3.2.2b(i). The superkeys are AB, AC, AD, ABC, ABD, ACD, BCD and ABCD.ii) The superkeys are all those sets that contain one of the k

23、eys in 3.2.2b(ii). The superkeys are ABC, ABD, ACD, BCD and ABCD.iii) The superkeys are all those sets that contain one of the keys in 3.2.2b(iii). The superkeys are AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD and ABCD.Exercise 3.2.3aSince A1A2AnC contains A1A2An, then the closure of A1A2AnC contains

24、 B. Thus it follows that A1A2AnCàB.Exercise 3.2.3bFrom 3.2.3a, we know that A1A2AnCàB. Using the concept of trivial dependencies, we can show that A1A2AnCàC. Thus A1A2AnCàBC. Exercise 3.2.3cFrom A1A2AnE1E2Ej, we know that the closure contains B1B2Bm because of the FD A1A2Anà

25、 B1B2Bm. The B1B2Bm and the E1E2Ej combine to form the C1C2Ck. Thus the closure of A1A2AnE1E2Ej contains D as well. Thus, A1A2AnE1E2EjàD.Exercise 3.2.3dFrom A1A2AnC1C2Ck, we know that the closure contains B1B2Bm because of the FD A1A2Anà B1B2Bm. The C1C2Ck also tell us that the closure of

26、A1A2AnC1C2Ck contains D1D2Dj. Thus, A1A2AnC1C2CkàB1B2BkD1D2Dj. Exercise 3.2.4aIf attribute A represented Social Security Number and B represented a persons name, then we would assume AàB but BàA would not be valid because there may be many people with the same name and different Socia

27、l Security Numbers.Exercise 3.2.4bLet attribute A represent Social Security Number, B represent gender and C represent name. Surely Social Security Number and gender can uniquely identify a persons name (i.e. ABàC). A Social Security Number can also uniquely identify a persons name (i.e. Aà

28、;C). However, gender does not uniquely determine a name (i.e. BàC is not valid).Exercise 3.2.4cLet attribute A represent latitude and B represent longitude. Together, both attributes can uniquely determine C, a point on the world map (i.e. ABàC). However, neither A nor B can uniquely ident

29、ify a point (i.e. AàC and BàC are not valid).Exercise 3.2.5Given a relation with attributes A1A2An, we are told that there are no functional dependencies of the form B1B2Bn-1àC where B1B2Bn-1 is n-1 of the attributes from A1A2An and C is the remaining attribute from A1A2An. In this ca

30、se, the set B1B2Bn-1 and any subset do not functionally determine C. Thus the only functional dependencies that we can make are ones where C is on both the left and right hand sides. All of these functional dependencies would be trivial and thus the relation has no nontrivial FDs.Exercise 3.2.6Lets

31、prove this by using the contrapositive. We wish to show that if X+ is not a subset of Y+, then it must be that X is not a subset of Y. If X+ is not a subset of Y+, there must be attributes A1A2An in X+ that are not in Y+. If any of these attributes were originally in X, then we are done because Y do

32、es not contain any of the A1A2An. However, if the A1A2An were added by the closure, then we must examine the case further. Assume that there was some FD C1C2CmàA1A2Aj where A1A2Aj is some subset of A1A2An. It must be then that C1C2Cm or some subset of C1C2Cm is in X. However, the attributes C1C

33、2Cm cannot be in Y because we assumed that attributes A1A2An are only in X+ and are not in Y+. Thus, X is not a subset of Y.By proving the contrapositive, we have also proved if X Y, then X+ Y+.Exercise 3.2.7The algorithm to find X+ is outlined on pg. 76. Using that algorithm, we can prove that (X+)

34、+ = X+. We will do this by using a proof by contradiction.Suppose that (X+)+ X+. Then for (X+)+, it must be that some FD allowed additional attributes to be added to the original set X+. For example, X+ à A where A is some attribute not in X+. However, if this were the case, then X+ would not b

35、e the closure of X. The closure of X would have to include A as well. This contradicts the fact that we were given the closure of X, X+. Therefore, it must be that (X+)+ = X+ or else X+ is not the closure of X.Exercise 3.2.8aIf all sets of attributes are closed, then there cannot be any nontrivial f

36、unctional dependencies. Suppose A1A2.AnàB is a nontrivial dependency. Then A1A2.An+ contains B and thus A1A2.An is not closed.Exercise 3.2.8bIf the only closed sets are ø and A,B,C,D, then the following FDs hold:AàBAàCAàDBàABàCBàDCàACàBCàDDà

37、;ADàBDàCABàCABàDACàBACàDADàBADàCBCàABCàDBDàABDàCCDàACDàBABCàDABDàCACDàBBCDàAExercise 3.2.8cIf the only closed sets are ø, A,B and A,B,C,D, then the following FDs hold:AàBBàACàACàBCà

38、;DDàADàBDàCACàBACàDADàBADàCBCàABCàDBDàABDàCCDàACDàBABCàDABDàCACDàBBCDàAExercise 3.2.9We can think of this problem as a situation where the attributes A,B,C represent cities and the functional dependencies represent

39、one way paths between the cities. The minimal bases are the minimal number of pathways that are needed to connect the cities. We do not want to create another roadway if the two cities are already connected.The systematic way to do this would be to check all possible sets of the pathways. However, w

40、e can simplify the situation by noting that it takes more than two pathways to visit the two other cities and come back. Also, if we find a set of pathways that is minimal, adding additional pathways will not create another minimal set.The two sets of minimal bases that were given in example 3.11 ar

41、e:AàB, BàC, CàAAàB, BàA, BàC, CàBThe additional sets of minimal bases are:CàB, BàA, AàCAàB, AàC, BàA, CàAAàC, BàC, CàA, CàBExercise 3.2.10aWe need to compute the closures of all subsets of ABC, although there i

42、s no need to think about the empty set or the set of all three attributes. Here are the calculations for the remaining six sets:A+=AB+=BC+=ACEAB+=ABCDEAC+=ACEBC+=ABCDEWe ignore D and E, so a basis for the resulting functional dependencies for ABC is: CàA and ABàC. Note that BC->A is tru

43、e, but follows logically from C->A, and therefore may be omitted from our list.Exercise 3.2.10bWe need to compute the closures of all subsets of ABC, although there is no need to think about the empty set or the set of all three attributes. Here are the calculations for the remaining six sets:A+=

44、ADB+=BC+=CAB+=ABDEAC+=ABCDEBC+=BCWe ignore D and E, so a basis for the resulting functional dependencies for ABC is: ACàB.Exercise 3.2.10cWe need to compute the closures of all subsets of ABC, although there is no need to think about the empty set or the set of all three attributes. Here are th

45、e calculations for the remaining six sets:A+=AB+=BC+=CAB+=ABDAC+=ABCDEBC+=ABCDEWe ignore D and E, so a basis for the resulting functional dependencies for ABC is: ACàB and BCàA.Exercise 3.2.10dWe need to compute the closures of all subsets of ABC, although there is no need to think about t

46、he empty set or the set of all three attributes. Here are the calculations for the remaining six sets:A+=ABCDEB+=ABCDEC+=ABCDEAB+=ABCDEAC+=ABCDEBC+=ABCDEWe ignore D and E, so a basis for the resulting functional dependencies for ABC is: AàB, BàC and CàA.Exercise 3.2.11For step one of

47、Algorithm 3.7, suppose we have the FD ABCàDE. We want to use Armstrongs Axioms to show that ABCàD and ABCàE follow. Surely the functional dependencies DEàD and DEàE hold because they are trivial and follow the reflexivity property. Using the transitivity rule, we can derive

48、the FD ABCàD from the FDs ABCàDE and DEàD. Likewise, we can do the same for ABCàDE and DEàE and derive the FD ABCàE.For steps two through four of Algorithm 3.7, suppose we have the initial set of attributes of the closure as ABC. Suppose also that we have FDs CàD a

49、nd DàE. According to Algorithm 3.7, the closure should become ABCDE. Taking the FD CàD and augmenting both sides with attributes AB we get the FD ABCàABD. We can use the splitting method in step one to get the FD ABCàD. Since D is not in the closure, we can add attribute D. Takin

50、g the FD DàE and augmenting both sides with attributes ABC we get the FD ABCDàABCDE. Using again the splitting method in step one we get the FD ABCDàE. Since E is not in the closure, we can add attribute E.Given a set of FDs, we can prove that a FD F follows by taking the closure of t

51、he left side of FD F. The steps to compute the closure in Algorithm 3.7 can be mimicked by Armstrongs axioms and thus we can prove F from the given set of FDs using Armstrongs axioms. Exercise 3.3.1aIn the solution to Exercise 3.2.1 we found that there are 14 nontrivial dependencies, including the t

52、hree given ones and eleven derived dependencies. They are: CàA, CàD, DàA, ABàD, ABà C, ACàD, BCàA, BCàD, BDàA, BDàC, CDàA, ABCàD, ABDàC, and BCDàA.We also learned that the three keys were AB, BC, and BD. Thus, any dependency above

53、 that does not have one of these pairs on the left is a BCNF violation. These are: CàA, CàD, DàA, ACàD, and CDàA.One choice is to decompose using the violation CàD. Using the above FDs, we get ACD and BC as decomposed relations. BC is surely in BCNF, since any two-attri

54、bute relation is. Using Algorithm 3.12 to discover the projection of FDs on relation ACD, we discover that ACD is not in BCNF since C is its only key. However, DàA is a dependency that holds in ABCD and therefore holds in ACD. We must further decompose ACD into AD and CD. Thus, the three relati

55、ons of the decomposition are BC, AD, and CD.Exercise 3.3.1bBy computing the closures of all 15 nonempty subsets of ABCD, we can find all the nontrivial FDs. They are BàC, BàD, ABàC, ABàD, BCàD, BDàC, ABCàD and ABDàC. From the closures we can also deduce that t

56、he only key is AB. Thus, any dependency above that does not contain AB on the left is a BCNF violation. These are: BàC, BàD, BCàD and BDàC.One choice is to decompose using the violation BàC. Using the above FDs, we get BCD and AB as decomposed relations. AB is surely in BCNF

57、, since any two-attribute relation is. Using Algorithm 3.12 to discover the projection of FDs on relation BCD, we discover that BCD is in BCNF since B is its only key and the projected FDs all have B on the left side. Thus the two relations of the decomposition are AB and BCD.Exercise 3.3.1cIn the s

58、olution to Exercise 3.2.2(ii), we found that there are 12 nontrivial dependencies, including the four given ones and the eight derived ones. They are ABàC, BCàD, CDàA, ADàB, ABàD, ADàC, BCàA, CDàB, ABCàD, ABDàC, ACDàB and BCDàA.We also foun

59、d out that the keys are AB, AD, BC, and CD. Thus, any dependency above that does not have one of these pairs on the left is a BCNF violation. However, all of the FDs contain a key on the left so there are no BCNF violations.No decomposition is necessary since all the FDs do not violate BCNF.Exercise

60、 3.3.1dIn the solution to Exercise 3.2.2(iii), we found that there are 28 nontrivial dependencies, including the four given ones and the 24 derived ones. They are AàB, BàC, CàD, DàA, AàC, AàD, BàD, BàA, CàA, CàB, DàB, DàC, ABàC, AB

61、4;D, ACàB, ACàD, ADàB, ADàC, BCàA, BCàD, BDàA, BDàC, CDàA, CDàB, ABCàD, ABDàC, ACDàB and BCDàA.We also found out that the keys are A,B,C,D. Thus, any dependency above that does not have one of these attributes on the left is a BCN

62、F violation. However, all of the FDs contain a key on the left so there are no BCNF violations.No decomposition is necessary since all the FDs do not violate BCNF.Exercise 3.3.1eBy computing the closures of all 31 nonempty subsets of ABCDE, we can find all the nontrivial FDs. They are ABàC, DEàC, BàD, ABàD, BCàD, BEàC, BEàD, ABCàD, ABDàC, ABEàC, ABEàD, ADEàC, BCEàD, BDEàC, ABCEàD, and ABDEàC. From the closures we can also deduce that the only key is ABE. Thus, any dependency above that does not contain