数据库管理系统概述英文版课件：tutorial6 Functional DependenciesNormalization

1、COMP231 Tutorial 6Functional Dependencies and Normalization 2Review: We want to decompose SchemasDecompositionR=A,B,C,D,ER1=A,B,C, R2=D,ELossless-join decomposition (complete reproduction)Satisfy normal forms (BCNF or 3NF)Dependency preservingR = A,B,C,D,E. F = ABC, CD E, B D, EA .Is the following d

2、ecomposition a lossless join?1) R1 = A,B,C,R2 =A,D,E.2) R1 = A,B,C,R2 =C,D,E.1) Since R1 R2 = A, and A is a key for R1, the decomposition is lossless join.2)Since R1 R2 = C, and C is not a key for R1 or R2, the decomposition is not lossless join.Exercise 1: Lossless-join DecompositionR = A,B,C,D,E.F

3、 = ABC, CD E, B D, EA .R1 = A,B,C, R2 = A,D,E.Is the above decomposition dependency-preserving?No.CD E and B D are lost. Exercise 2 : FD-Preserving DecompositionBCNF: R is in BCNF if and only iffor each FD: X A in F+ThenA X (trivial FD), orX is a superkey for R In other words, the left part of any n

4、on-trivial dependency must be a superkey.* If we do not have redundancy in F, then for each X A , X must be a candidate key.* The decomposition is lossless-join but may not be dependency-preserving.Review: Boyce-Codd Normal Form3NF: R is in 3NF if and only iffor each FD: X A in F+A X (trivial FD), o

5、rX is a superkey for R, orA is prime attribute for R If a relation is in BCNF, it is in 3NF (since BCNF permits only the first two conditions).If every FD that does not contain extraneous (useless) attributes, then for each X A , X must be a candidate key, or A must belong to a candidate key.The dec

6、omposition is both lossless-join and dependency-preserving.Review: Third Normal FormR =(A, B, C, D).F = CD, CA, BC.Question 1: Identify all candidate keys for R.Question 2: Does R satisfy 3NF or BCNF?Question 3: Decompose R into a set of BCNF relations.Question 4: Decompose R into a set of 3NF relat

7、ions.Exercise 3R =(A, B, C, D).F = CD, CA, BC.Question 1: Identify all candidate keys for R. B+ = B (BB) = BC (BC) = BCD (CD) = ABCD (CA) so the candidate key is B. B is the ONLY candidate key, because nothing determines B: There is no rule that can produce B, except B B.Exercise 3 (cont)R =(A, B, C

8、, D).F = CD, CA, BC. Question 2: Does R satisfy 3NF or BCNF? R is not 3NF, because: CD causes a violation,CD is non-trivial (D C).C is not a superkey.D is not part of any candidate key.CA causes a violationSimilar to aboveBC causes no violation Since R is not 3NF, it is not BCNF either.Exercise 3 (c

9、ont)R =(A, B, C, D).F = CD, CA, BC.Question 3: Decompose R into a set of BCNF relations.CD, CA violas BCNF. Take CD: decompose R to R1= A, B, C , R2=C, D.R1 violates BCNF (because of CA)Decompose R1 to R11 = B, C R12 = C, A.Final decomposition: R2 = C, D, R11 = B, C, R12 = C, A.No more violations: F

10、inished!Exercise 3 (cont)Let R be the initial table with FDs FS=RUntil all relation schemes in S are in BCNFfor each R in S for each FD X Y that violates BCNF for RS = (S R) (R-Y) (X,Y)enduntilR =(A, B, C, D).F = CD, CA, BC.Question 4: Decompose R into a set of 3NF relations.Compute canonical cover

11、Fc = CDA, BC. Create a table for each functional dependency in Fc R1 = C, D, A, R2 = B, C.The table R2 contains the candidate key Finished. Exercise 3 (cont)Compute the canonical cover Fc of FS=for each FD XY in the canonical cover FcS=S(X,Y) if no scheme contains a candidate key for R Choose any ca

12、ndidate key CNS=S table with attributes of CNExercise 4R = (A, B, C, D) F = ABC, ABD, CA, DBIs R in 3NF, why? If it is not, decompose it into 3NFIs R in BCNF, why? If it is not, decompose it into BCNFExercise 4R = (A, B, C, D) F = ABC, ABD, CA, DBIs R in 3NF, why? If it is not, decompose it into 3NF

13、Yes. Find all the Candidate Keys: AB, BC, CD, AD Check all FDs in F for 3NF condition2. Is R in BCNF, why? If it is not, decompose it into BCNFNo. CA, C is not a superkey. Similar for DBBegin with CA or begin with DB get the same result: R1 = C, D, R2 = A, C, R3 = B, DMore Exercise 5R = (A, B, C, D)F = ABCD, DA 1. Identify all the candidate keys for RCandidate keys: ABC, BCD 2. Identify the highest normal form that R satisfiesR is in 3NF but not BCNF. 3. If R is not in BCNF, decompose it into a set of BCNF relations that