Post your solutions to the Sep 26 In-Class Exercise to this thread. Best, Chris

-- Sep. 26 In-Class Exercise Thread

R(A,B,C,D,E) with FDs A->BC, B->D, D->E New relations: @BT@R_1@BT@(A,B,C) with FDs @BT@{A->BC}@BT@ @BT@R_2@BT@(B,D,E) with FDs @BT@{B->D,D->E}@BT@

-- Sep. 26 In-Class Exercise Thread

Conover Wang cycle through the FDs to check if we violate BCNF consider A -> BC check if A is a super key. to see if A is a super key compute {A}^+ = {A,B,C,D,E} A is a super key. Next we consider B->D which is also non trivial to check if B is a super key. we compute {B}^+ = {B,D,E} so this not a super key. So now we decompose the tables into R1 {B,D,E} R2{B,A,C} now recurse try to get r1 and r2 in BCNF the FD's on R1 are B->D D -> E the FD's on R2 are A -> BC now we check cycle R1 to see if it's FD's do not violate BCNF We check if B is a super key for R1 B is a super key We check if A is a super key for R2 A is a super key

-- Sep. 26 In-Class Exercise Thread

 Attributes to analyze: {A,B,D}
 FDs from {A}+ = A->B, A->C, B->D, D->E
 {A}+ yields {A,B,C,D,E}, A is superkey
 FDs from {B}+ = B->D, D->E
 {B}+ yields {B,D,E}
 new relation R1(B,D,E), FD(B->D, D->E)
 new relation R2(A,B,C), FD(A->BC)
 relation 2 contains other attributes B cannot reach as it is not a superkey
 For R1, B is a superkey
 For R2, A is a superkey
 We can not split R1 or R2, since the data will not faithfully represent the original data.
 

relation R(A,B,C,D,E) with FD A→BC, B→D, D→E Attributes to analyze: {A,B,D} FDs from {A}+ = A->B, A->C, B->D, D->E {A}+ yields {A,B,C,D,E}, A is superkey FDs from {B}+ = B->D, D->E {B}+ yields {B,D,E} new relation R1(B,D,E), FD(B->D, D->E) new relation R2(A,B,C), FD(A->BC) relation 2 contains other attributes B cannot reach as it is not a superkey For R1, B is a superkey For R2, A is a superkey We can not split R1 or R2, since the data will not faithfully represent the original data.

-- Sep. 26 In-Class Exercise Thread

 R2(B,A,C)
 R3(D,E)
 R4(D,B)

 S2 = A->BC
 S3 = D->E
 S4 = B->D

((resource:180926InClassExercise.png|Resource Description for 180926InClassExercise.png)) To reiterate the solution, the relation R was decomposed into three relations: R2(B,A,C) R3(D,E) R4(D,B) which all satisfy BCNF. The set of FD's that originally followed R, which we will call S, was similarly decomposed into three sets using our FD projection algorithm: S2 = A->BC S3 = D->E S4 = B->D We can see that all non-trivial sets of FD's contain only superkeys for their corresponding relations, so the decomposition into BCNF is complete.

-- Sep. 26 In-Class Exercise Thread

 Let R0 = R(A, B, C, D, E) and its FDs, S0 = {A → BC,  B → D,  D → E}

 A → BC is a nontrivial FD. {A}+ = {A, B, C, D, E}, so A is a superkey.
 B → D is a nontrivial FD. {B}+ = {B, D, E}, so B is not a superkey. This FD violates BCNF, so we split the table.

 R1(B, D, E)      (attributes = {B}+)
 R2(A, B, C)      (attributes = B and everything in R0 that isn't in {B}+)
 S1 = {B → D, D → E}
 S2 = {A → BC}

 We see that R2 is in BCNF, so we leave that relation alone. Looking at the FDs of R1,
 B → D is a nontrivial FD. {B}+ = {B, D, E}, so B is a superkey.
 D → E is a nontrivial FD. {D}+ = {D, E}, so D is not a superkey. This FD violates BCNF, so we split R1.

 R3(D, E)          (attributes = {D}+)
 R4(B, D)          (attributes = D and everything in R1 that isn't in {D}+)
 S3 = {D → E}
 S4 = {B → D}

 So R1 = R3(D, E) ∪ R4(B, D)

 Both of these new relations have FDs that are nontrivial, and all the LHS of the FDs are superkeys, so they're all in BCNF and we're done. We return the union of the derived relations.

 Answer: R0 = R2(A, B, C) ∪ R3(D, E) ∪ R4(B, D)

Let R0 = R(A, B, C, D, E) and its FDs, S0 = {A → BC, B → D, D → E} A → BC is a nontrivial FD. {A}+ = {A, B, C, D, E}, so A is a superkey. B → D is a nontrivial FD. {B}+ = {B, D, E}, so B is not a superkey. This FD violates BCNF, so we split the table. R1(B, D, E) (attributes = {B}+) R2(A, B, C) (attributes = B and everything in R0 that isn't in {B}+) S1 = {B → D, D → E} S2 = {A → BC} We see that R2 is in BCNF, so we leave that relation alone. Looking at the FDs of R1, B → D is a nontrivial FD. {B}+ = {B, D, E}, so B is a superkey. D → E is a nontrivial FD. {D}+ = {D, E}, so D is not a superkey. This FD violates BCNF, so we split R1. R3(D, E) (attributes = {D}+) R4(B, D) (attributes = D and everything in R1 that isn't in {D}+) S3 = {D → E} S4 = {B → D} So R1 = R3(D, E) ∪ R4(B, D) Both of these new relations have FDs that are nontrivial, and all the LHS of the FDs are superkeys, so they're all in BCNF and we're done. We return the union of the derived relations. Answer: R0 = R2(A, B, C) ∪ R3(D, E) ∪ R4(B, D)

-- Sep. 26 In-Class Exercise Thread

A+ = {ABCDE}, B+={BDE}, D+ = {DE}, A is the superkey and doesn't violate BCNF. 1st FD, A-> BC, not violate BCNF, we have R1{ABC}, 2nd FD B->D, B is not the key so it violate BCNF, we have R2{BD}, 3rd FD D->E, D is not key so we have R3{DE}. Answer: R1(ABC), R2(BD). R3(DE)

-- Sep. 26 In-Class Exercise Thread

 R1(B,D,E) and R2(B,A,C) we now compute the FD for the new sub relations
 S1 = B->D, D->E 
 S2 =  A-> BC

 R3=(D,E)
 R4(D,B)
 S3 = D->E and 
 S4 = B->D

Himanshu Mehta We first look at the FD and see which keys violate the BCNF A+ ={A,B,C,D,E} B+= {B,D,E} D+= {D,E} In this case A does not violate the BCNF B violates the BCNF as it does not have all the elements R1(B,D,E) and R2(B,A,C) we now compute the FD for the new sub relations S1 = B->D, D->E S2 = A-> BC we now decompose these relations B+={B,D,E} and D+ = {D,E} In this case B is a superkey and D has a violation Decomposing D we get R3=(D,E) R4(D,B) S3 = D->E and S4 = B->D We can now see that the new relations have FD's that are non-trivial and only contain the super key for corresponding relation thus the decomposition is now complete.

-- Sep. 26 In-Class Exercise Thread

((resource:IMG_4702.jpeg|Resource Description for IMG_4702.jpeg))

-- Sep. 26 In-Class Exercise Thread

Lists the FD and show where it violates the BCNF A+ = {A,B,C,D,E} B+ = {B,D,E} D+ = {D,E} A is a superkey and doesn't violate BCNF. B violates BCNF, decompose R with B->D, R{ABCDE} becomes R1{BDE}, R2{ABC} The FDs on R1 are B->D and D->E The FDs on R2 is A->BC Decompose R1 with B->D R1{BDE} becomes R3{BD}, R4{BE} The FD on R3 are B->D The FD on R4 are D->E R3 and R4 are in BCNF because of the FD: D->E and B->D therefore R(A,B,C,D,E) = R3(D,E) U R4(D,B) U R2(B,A,C)