1、COMP231 Tutorial 5Functional Dependencies, 3NFSuperkeyK RCandidate KeyK Rno K K, s.t. K R (minimal)Primary KeyThe candidate key chosen to uniquely identify tuples in a relationsuperkeycandidate keyprimary keyReview: KeyFor a set of functional dependencies F, we can get the closure, F+, by applying A

2、rmstrongs Axioms.Armstrongs Axioms:ReflexivityIf X Y, then X YAugmentationIf X Y, then XZ YZTransitivityIf X Y, Y Z, then X ZDerived rules:DecompositionIf X YZ, then X Y and X ZUnionIf X Y and X Z, then X YZPseudo-transitivityIf X Y and WY Z, then WX ZReview: The Closure of FDIf XYZ then XZ and YZDe

3、finition: X, Y are attributes of a relation R:X Y is in F+ Y X+ Example:Given R = (loan_no, amount, branch_name, customer_name)If loan_no amountthen loan_no+ = loan_no, amountIf we also have loan_no branch_namethen loan_no+ = loan_no, amount, branch_nameIf we also have loan_no customer_namethen loan

4、_no+ = loan_no, amount, branch_name, customer_nameAlgorithm:X(0) := XRepeatX(i+1) := X(i) Z,where Z is the set of attributes such that there exists YZ in F, and Y X(i) Until X(i+1) := X(i) Return X(i+1)Review: The Closure of AttributesReview: Canonical Cover of FDDefinition:A canonical cover for F i

5、s a set of dependencies Fc such that F and Fc are equivalent Fc contains no redundancyEach left hand side of functional dependency in Fc is uniqueReview: NormalizationDecomposition of a relation R with the following goalsLossless (necessary)Information lost?Dependency preservation (desirable)(i Fi)+

6、 = F+ ?Good form1NF, 2NF, 3NF, BCNF2NF:R is in 2NF if and only iffor each FD: X A in F+ThenA X (the FD is trivial), ORX is not a proper subset of a candidate key for R, ORA is a prime attribute3NF:R is in 3NF if and only iffor each FD: X A in F+ThenA X (trivial FD), ORX is a superkey for R, ORA is p

7、rime attribute for RA prime attribute is an attribute that is part of a candidate keyR = (A, B, C, D, E)F = ABC, CDE, BD, EACompute A+ and B+:A+:= A:= A, B, CABC and A A+:= A, B, C, DBD and B A+:= A, B, C, D, ECDE and C, D A+ends because A+ stops changingB+:= B:= B, DBD and B B+ ends because B+ stop

8、s changingExercise 1: The Closure of AttributesR = (A, B, C, D, E)F = ABC, CDE, BD, EAList all candidate keys of R.We have A+ = A, B, C, D, E in Exercise 1,then AABCDE, it is a candidate key of R.Since EA, then EABCDE. (transitivity)Since CDE, then CDABCDE. (transitivity)Since BD, then BCCD, then BC

9、ABCDE. (augmentation, transitivity)So A, E, CD, BC are candidate keys of R.Exercise 2: Candidate KeysR = (A, B, C, D, E)F = ACE, ACDB, CED, BEFind the canonical cover of F.Algorithm:RepeatUnionX1Y1 and X1Y2 replaced with X1Y1Y2Find an extraneous attributeIf an extraneous attribute is found in XY, de

10、lete it from XYUntil F does not changeExercise 3: Compute Canonical CoverR = (A, B, C, D, E)F = ACE, ACDB, CED, BEFind the canonical cover of F.First loop:Union Fc(1) = ACE, ACDB, CED, BEFind an extraneous attributeConsider ACDB:D is extraneous because ACE and CEDRemove D in ACDBFc(1) = ACE, ACB, CE

11、D, BEExercise 3: Compute Canonical Cover (cont)R = (A, B, C, D, E)Fc(1) = ACE, ACB, CED, BESecond loop:UnionFc(2) = ACBE, CED, BEFind an extraneous attributeConsider ACBE:E is extraneous because BERemove E in ACBEFc(2) = ACB, CED, BEExercise 3: Compute Canonical Cover (cont)R = (A, B, C, D, E)Fc(2)

12、= ACB, CED, BEThird loop:UnionFc(3) = ACB, CED, BEFind an extraneous attribute No extraneous attributes foundEnds because Fc stops changingFc = ACB, CED, BEExercise 3: Compute Canonical Cover (cont)Exercise 3: Compute Canonical Cover (cont)Different order of removing the extraneous attributes may re

13、sult in different FCExample:R=(A, B, C, D)FD = AC, BCA, ABCDIn ABCD, A is extraneous or C is extraneousIf we remove A first, we get Fc = AC, BCADIf we remove C first, we get Fc = AC, BCA, ABDExercise 4: Normal formsR=(A, B, C, D, E)FD = ABC, CDE, BD, EAIs R in 1NF?Yes. Relational tables are always i

14、n 1NF.Is R in 2NF?We found candidate keys: A, E, CD, BC.ABCBC are prime attributeCDEE is a prime attributeBDD is a prime attributeEAA is a prime attributeSo R is in 2NF2NF:R is in 2NF if and only iffor each FD: X A in F+ThenA X (the FD is trivial), ORX is not a proper subset of a candidate key for R

15、, ORA is a prime attributeExercise 4: Normal forms (cont)R=(A, B, C, D, E)FD = ABC, CDE, BD, EAIs R in 3NF?We found candidate keys: A, E, CD, BC.ABCA is a candidate keyCDECD is a candidate keyBDD is a prime attributeEAE is a candidate keySo R is in 3NF3NF:R is in 3NF if and only iffor each FD: X A i

16、n F+ThenA X (trivial FD), ORX is a superkey for R, ORA is prime attribute for RExercise 4: Normal forms (cont)R=(A, B, C, D, E, F)FD = AB, BCD, CE, BFIs R in 2NF?Candidate key: AC.ABA is a proper subset of candidate key AND B is not a prime attributeBCDBC is not a proper subset of candidate keyCEC i

17、s a proper subset of candidate key AND E is not a prime attributeBFB is not a proper subset of candidate keyAB or CE makes R not in 2NF2NF:R is in 2NF if and only iffor each FD: X A in F+ThenA X (the FD is trivial), ORX is not a proper subset of a candidate key for R, ORA is a prime attributeExercis

18、e 4: Normal forms (cont)R=(A, B, C, D, E, F)FD = AB, BCD, CE, BFIs R in 3NF?3NF 2NF 1NF, R is not in 2NF, so R is not in 3NF either.Candidate key: AC.ABA is not a super-key AND B is not a prime attributeBCDBC is not a super-key AND D is not a prime attributeCEC is not a super-key AND E is not a prim

19、e attributeBFB is not a super-key AND F is not a prime attributeEither one of the FD makes R not in 3NF3NF:R is in 3NF if and only iffor each FD: X A in F+ThenA X (trivial FD), ORX is a superkey for R, ORA is prime attribute for RExercise 5: DecompositionR = (A, B, C, D, E, F, G, H)F = ACG, DEG, BCD

20、, CGBD, ACDB, CEAGA decomposition of R:Table1: (A, B, C, D)Table2: (D, E, G)Table3: (A, C, D, F, H)Is it lossless?YesA decomposition of R into R1 and R2 is lossless if and only if the common attributes of R1 and R2 is a candidate key for R1 or R2 Candidate Keys: T1(ACD,ABC) T2(D) T3(ACDFH)(Table1 Ta

21、ble3) Table2 = D (candidate key of Table2)Table1 Table3 = ACD (candidate key of Table1)Exercise 5: Decomposition (cont)R = (A, B, C, D, E, F, G, H)F = ACG, DEG, BCD, CGBD, ACDB, CEAGA decomposition of R:Table1: (A, B, C, D)Table2: (D, E, G)Table3: (A, C, D, F, H)Is it dependency preserving?Table1: F1=ACD B, BCDTable2: F2=DEGTable3: F3=(F1 F2 F3 )+= ACG, DEG, BCD, ACDB,Answer: No (CGBD, CEAG is lost)Exercise 6: 3NFR = (A, B, C, D, E, F, G, H)F = ACG, DEG, BCD, CGBD, ACDB, CEAGDecompose R into 3NFAlgorithm:Compute Fc of FS := For each FD XY