08 Normalization II -Key

CSE 3241 In-Class Assignment – 08 Functional Dependencies and Normalization Names Date 1. Consider the relation R1(A, B, C, D, E, F) with functional dependencies: A  {B,C,D,E}; D  F; {B,C}  {A,D}; B  E a. What are the possible candidate keys for relation R1? {A}, {B,C} (If we have A we can get E and F via transitive dependencies. If we have B and C we get A, so we can get everything else via transitive dependencies as well) b. Is R1 in BCNF? If so why, and if not why not? Show a decomposition of R1 into BCNF No. We have B  E. B is only part of a key and E is a non-prime attribute, so this violates 2NF. We also have D  F which violates the definition of 3NF – D is not a superkey of R1 and F is not a prime attribute. One possible decomposition: R1a(A,B,C,D); R1b( B ,E); R1c(D ,F). Other solutions may be possible 2. Consider the relation R2(A, B, C, D, E, F) with functional dependencies: {B,D}  {A,E}; C  F; {E,F}  {A}; E  C a. What are the possible candidate keys for relation R1? Only {B,D}. Since nothing determines B and nothing determines D, both of these must be in any key we propose. And both of these determine everything, so it will be our only key. b. Is R2 in BCNF? If so why, and if not why not? Show a decomposition of R2 into BCNF No. R2 is only in 2NF. Nothing is dependent on a piece of a key (either B or D by themselves), but C  F and E  C and {E,F}  {A}; are all dependencies where a non superkey determines a non prime attribute, and so violates 3NF. One possible breakdown that is in BCNF would be R2a(B , D , E); R2b(E , C, A); R2c(C , F). This retains the dependencies {B,D}  A and {E,F}  A through transitivity – since E  C, C  F, which means that E  F. If E  F we can substitute E in for F on the left side of {E,F}  A and get {E,E}  A, which simplifies to E  A. So preserving E  A also preserves {E,F}  A and this breakdown preserves dependencies. 3. Consider the relation R3(A, B, C, D, E, F) with functional dependencies: {A}  {F}; {E}  {B,C}; {E,F}  {D}; {F}  {A,C} a. What are the possible candidate keys for relation R3? {A, E} and {E,F} are the possible candidate keys b. Is R3 in BCNF? If so why, and if not why not? Show a decomposition of R3 into BCNF No. R3 is not in 2NF because the dependencies {E}  {B,C} and {F}  {C} are partial dependencies. One possible breakdown that is in BCNF would be: R3a(E , F , D); R3b(E , B, C); R3c(F, A); This one loses the dependency F  C.