數(shù)據(jù)庫(kù)管理系統(tǒng)概述英文版課件：8 Functional Dependency and Normal Forms

1、COMP231Functional Dependency,Schema Refinement & Normal FormsPrepared by Raymond WongPresented by Raymond WongCOMP2311OutlineProblems caused by redundancyFunctional dependenciesBoyce Codd normal form (BCNF)Third normal form (3NF)DecompositionDependency preservationBCNF decomposition algorithm3NF dec

2、omposition algorithmDesign GoalCOMP23121. Problems caused by redundancyWaste of resources of storagePotential inconsistencyCOMP23131. Problems caused by redundancyStudent-IDStudent-NameCourse-IDCourse-Name123RaymondCOMP231Database123RaymondCOMP170D. Math567MaryCOMP104C+567MaryCOMP271Algorithm999Pete

3、rCOMP231DatabaseRedundancy!Waste of resourcesCOMP23141. Problems caused by redundancyStudent-IDStudent-NameCourse-IDCourse-Name123RaymondCOMP231Database123Raymond WongCOMP170D. Math567MaryCOMP104C+567MaryCOMP271Algorithm999PeterCOMP231DatabaseInconsistency!COMP23151. Problems caused by redundancyDec

4、ompositionThe essential idea is that many problems arising from redundancy can be addressed by replacing a relation with a collection of “smaller” relationsCOMP23161. Problems caused by redundancyStudent-IDStudent-NameCourse-IDCourse-Name123RaymondCOMP231Database123RaymondCOMP170D. Math567MaryCOMP10

5、4C+567MaryCOMP271Algorithm999PeterCOMP231DatabaseStudent-IDStudent-Name123Raymond567Mary999PeterStudent-IDCourse-ID123COMP231123COMP170567COMP104567COMP271999COMP231Course-IDCourse-NameCOMP231DatabaseCOMP170D. MathCOMP104C+COMP271AlgorithmNo potential inconsistencyCOMP2317OutlineProblems caused by r

6、edundancyFunctional dependenciesBoyce Codd normal form (BCNF)Third normal form (3NF)DecompositionDependency preservationBCNF decomposition algorithm3NF decomposition algorithmDesign GoalCOMP23182. Functional dependenciesFunctional dependency is a type of constraint that is a generalization of the no

7、tation of keyDefinitionR a relation schema, R, R if and only if,for any relation r on R,for any two tuples t1, t2 of r (t1) = (t2) (t1) = (t2)COMP2319ExampleABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4Can you find a functional dependency that satisfy the following relation?COMP23110A C is satis

8、fiedABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4COMP23111ABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4A C is satisfiedCOMP23112ABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4A C is satisfiedCOMP23113Is C A satisfied?ABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4COMP23114No. There is no

9、 such C A.ABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4COMP23115ExampleABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4Can you find another functional dependency that satisfies the following relation?COMP23116ExampleABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4DB is also satisfied.COMP23117

10、ExampleABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4DB is also satisfied.COMP231182.1 Trivial and Non-Trivial Functional DependencyTrivial Functional Dependency where E.g. AB ANon-Trivial Functional DependencyE.g. AB CCOMP23119Although A C is satisfied in this relation, can we deduce that A C is

11、 a functional dependency from this result?ABCD1a1b1c1d12a1b2c1d23a2b2c2d24a2b2c2d35a3b3c2d4COMP23120Although A C is satisfied in this relation, can we deduce that A C is a functional dependency from this result?No.AC is satisfied only in this relation for this schema.Functional dependency is defined

12、 for all relations for a particular schema.AC is a functional dependency only if AC is satisfied for all relations for a particular schema.COMP231212.2 Information deduced from Functional dependencies is a key for R R is a candidate key for R R, there is no s.t. , RCOMP23122ExampleAC R, AD R, ACD RA

13、BCDa1b2c1d2a2b2c1d2a1b4c3d3a4b4c3d4COMP23123ExampleAC R, AD R, ACD RAC is a candidate keyABCDa1b2c1d2a2b2c1d2a1b4c3d3a4b4c3d4COMP23124ExampleAC R, AD R, ACD RAC is a candidate keyAD is also a candidate keyABCDa1b2c1d2a2b2c1d2a1b4c3d3a4b4c3d4COMP23125ExampleAC R, AD R, ACD RAC is a candidate keyAD is

14、 also a candidate keybut, ACD is not a candidate keyABCDa1b2c1d2a2b2c1d2a1b4c3d3a4b4c3d4COMP23126Reasoning about FDsF : a set of functional dependenciesf: an individual functional dependencyf is implied by F if whenever all functional dependencies in F are truethen f is trueE.g., F = A B, BC implies

15、 ACCOMP231272.3 Closure of FF f1, f2, , fi, , fn Where f1, f2, , fi, , fn are functional dependenciesf an individual functional dependencyF implies f, if whenever all f1, , fn are true, f is trueE.g. F = A B, BC F implies AC (by transitivity)F+ closure of F: the set of all functional dependencies th

16、at F impliesE.g. F = A B F+ = AA, BB, ABAB, AB, AAB, ABA, ABBCOMP231282.3 Closure of F:Armstrongs axioms If then (reflexivity) A, C A, B, C ABC AC If then (augmentation)A B CA CBIf , then (transitivity)A BD, BD C A CCOMP231292.3 Three Additional RulesIf and then (union)A B and A C A BCIf then and (d

17、ecomposition)A BC AB and A CIf and then (pseudotransitivity)AB and BCD ACDThe above rules can be inferred from Armstrongs axioms.E.g., pseudotransitivity and (given) (by augmentation) (by transitivity)COMP231302.4 Closure of attribute sets a set of attributes+ closure of under FAlgorithm to compute

18、+:result := while(changes in result) dofor each doif result then result := result end forend whileCOMP23131ExampleR = (A, B, C, D)F = A B, B C To compute A+ : (A B)(B C)result = Aresult = ABresult = ABCCOMP23132OutlineProblems caused by redundancyFunctional dependenciesBoyce Codd normal form (BCNF)T

19、hird normal form (3NF)DecompositionDependency preservationBCNF decomposition algorithm3NF decomposition algorithmDesign GoalCOMP231333. Boyce Codd normal form (BCNF)R a relation schemaF a set of functional dependencies on RR is in BCNF if for any A in F A is trivial (A ), or is a key for RCOMP23134E

20、xampleR = (A, B, C)F = A B, B C Key = A R is not in BCNF, why?F = A B, B CB is not a key, C B (non-trivial)Decompose R into R1 = (A, B), R2 = (B, C), then R1, R2 are in BCNFR is in BCNF if for any A in F A is trivial (A ), or is a key for RCOMP23135OutlineProblems caused by redundancyFunctional depe

21、ndenciesBoyce Codd normal form (BCNF)Third normal form (3NF)DecompositionDependency preservationBCNF decomposition algorithm3NF decomposition algorithmDesign GoalCOMP231364. Third normal form (3NF)R a relation schemaF a set of functional dependencies on RA a single attribute in RR is in 3NF if for a

22、ny A in F A is trivial (A ), or is a key for R, orA is part of some key(s) for RE.g. AB is a key for R then A is a part of the key. B is also a part of the key.R is in BCNF R is in 3NFCOMP23137ExampleR = (A, B, C, D, E)F = AE BCD, D A Key = AE, DE R is in 3NFIs R in BCNF? No. D is not a key for R.BC

23、NF implies 3NF but 3NF cannot imply BCNFR is in 3NF if for any A in F A is trivial (A ), or is a key for R, orA is part of some key(s) for RCOMP23138OutlineProblems caused by redundancyFunctional dependenciesBoyce Codd normal form (BCNF)Third normal form (3NF)DecompositionDependency preservationBCNF

24、 decomposition algorithm3NF decomposition algorithmDesign GoalCOMP231395. Lossless join decomposition R1, , Rn a set of relation schemas R1, , Rn is a decomposition of R if R1 R2 Rn = R R1, , Rn is a lossless-join decomposition of R if, for all relations r on schema R, R1(r) x x Rn(r) = rCOMP231405.

25、 Lossless join decompositionR a relation schemaF a set of functional dependencies on R R1, R2 is a lossless-join decomposition of R(R1R2) R1 F+ or (R1R2) R2 F+(R1R2) is a key for R1 or R2COMP23141Example (non-lossless)ABCa1b1c1a1b2c2ABa1b1a1b2ACa1c1a1c2ABCa1b1c1a1b1c2a1b2c1a1b2c2decomposejoinF = B C

26、, C B A AB F+?A AC F+?nonoCOMP23142Example (lossless)ABCa1b1c1a1b2c2BCb1c1b2c2ACa1c1a1c2ABCa1b1c1a1b2c2decomposejoinF = B C, C B C BC F+?C AC F+?yesnoCOMP23143OutlineProblems caused by redundancyFunctional dependenciesBoyce Codd normal form (BCNF)Third normal form (3NF)DecompositionDependency preser

27、vationBCNF decomposition algorithm3NF decomposition algorithmDesign GoalCOMP231446. Dependency PreservationR a relation schemaF a set of functional dependencies on R R1, R2 is a decomposition of RFi a subset of F with only attributes in Ri (i.e. the projection of F on Ri)Dependency is preserved if (

28、F1 F2)+ = F+E.g F = AB, BC R1 = (A, B) and R2 = (B, C) F1 = AB and F2 = BCCOMP231456. Dependency preserving decompositionE.g F = AB, CB R1 = (A, B) and R2 = (A, C) F1 = AB and F2 = CB is not in both F1 and F2. If dependency is NOT preserved, joins must be computed in order to check if an update is i

29、llegalVery inefficient !COMP23146OutlineProblems caused by redundancyFunctional dependenciesBoyce Codd normal form (BCNF)Third normal form (3NF)DecompositionDependency preservationBCNF decomposition algorithm3NF decomposition algorithmDesign GoalCOMP231477. BCNF decomposition algorithmSuppose R is n

30、ot in BCNF, A is an attribute, and X A is a FD that violates the BCNF condition.Remove A from RDecompose R into XA and R-ARepeat this process until all the relations become BCNFCOMP23148ExampleR = (A,B,C,D,E)Key = ACA BA DC E ABCDEABACDEADACECEACA BA DC ELossless decompositionDependency preservingCO

31、MP23149ExampleR = (A,B,C,D,E)Key = ACE, BCEAC BE DBE AABCDEABCACDEEDACEAC BE DLossless decompositionNot Dependency preservingCOMP23150ExampleR = (A,B,C,D,E)Key = ACE, BCEAC BE DBE AABCDEEDABCEABEBCEE DBE ALossless decompositionNot Dependency preservingSame exampleDifferent orders of chosen FDslead t

32、o different decompositions!COMP23151BCNF decomposition guarantees that the decomposition is a lossless-joinIt does not guarantees that the decomposition is dependency preservingCOMP23152OutlineProblems caused by redundancyFunctional dependenciesBoyce Codd normal form (BCNF)Third normal form (3NF)Dec

33、ompositionDependency preservationBCNF decomposition algorithm3NF decomposition algorithmDesign GoalCOMP231538. 3NF decomposition algorithmCanonical CoverrepeatReplace any 1 1 and 1 2by 1 1 2Delete any extraneous attributefrom any until F does not changeCOMP231548. 3NF decomposition algorithmCanonica

34、l CoverE.g F = EA, EB, ABC, BCF = EA, EB, ABC, BCF = EAB, ABC, BCF = EAB, ABC, BCF = EAB, AB, BCABC is extraneousFrom AB and BCwe deduce AC (transitivity)From AB and ACwe deduce ABC (union)Fc = EA, AB, BCCOMP231558. 3NF decomposition algorithmfind a canonical cover Fc for Fresult = for each in Fc do

35、if no schema in result contains thenadd schema to resultend forif no schema in result contains a candidate key for Rchoose any candidate key for Radd schema to resultend ifCOMP23156ExampleR = (A,B,C,D,E,F,G)F = A B, A C, D E, B A, F BG Fc =Candidate key = A BC, D E, B A, F BG DFCOMP23157ExampleR = (A,B,C,D,E,F,G)Fc = A BC, D E, B A, F BG Candidate key = DFFcresultA BCD EB AF BGCOMP23158ExampleR = (A,B,C,D,E,F,G)Fc = A BC, D E, B A, F BG Candidate key = DFFcresultA BCD EB AF BGABCCOMP23159ExampleR = (A,B,C,D,E,F,G)Fc = A BC,