4NF and 5NFScheduleNormalizationExample of ProblemsPowerPoint PresentationDecomposition to Reach BCNFSlide 7ExampleSlide 9Decompose Drinkers23NFSlide 12“Elegant” WorkaroundWhat 3NF Gives YouMultivalued DependenciesSlide 16MVD RulesSplitting Doesn’t Hold4NFSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 284NF and 5NFProf. Sin-Min LeeDepartment of Computer ScienceSchedule•Today: Jan. 15 (T)–Normal Forms, Multivalued Dependencies.–Read Sections 3.6-3.7. Assignment 1 due.•Jan. 17 (TH)–Relational Algebra.–Read Chapter 5. Project Part 1 due.•Jan. 22 (T)–SQL Queries.–Read Sections 6.1-6.2. Assignment 2 due.•Jan. 24 (TH)–Subqueries, Grouping and Aggregation. –Read Sections 6.3-6.4. Project Part 2 due.NormalizationGoal = BCNF = Boyce-Codd Normal Form =all FD’s follow from the fact “key everything.”•Formally, R is in BCNF if for every nontrivial FD for R, say X A, then X is a superkey.–“Nontrivial” = right-side attribute not in left side.Why?1. Guarantees no redundancy due to FD’s.2. Guarantees no update anomalies = one occurrence of a fact is updated, not all.3. Guarantees no deletion anomalies = valid fact is lost when tuple is deleted.Example of ProblemsDrinkers(name, addr, beersLiked, manf, favoriteBeer)FD’s:1. name addr2. name favoriteBeer3. beersLiked manf•???’s are redundant, since we can figure them out from the FD’s.•Update anomalies: If Janeway gets transferred to the Intrepid,will we change addr in each of her tuples?•Deletion anomalies: If nobody likes Bud, we lose track of Bud’s manufacturer.name addr beersLiked manf favoriteBeerJaneway Voyager Bud A.B. WickedAleJaneway ??? WickedAle Pete's ???S pock Enterprise Bud ??? BudEach of the given FD’s is a BCNF violation:•Key = {name, beersLiked}–Each of the given FD’s has a left side that is a proper subset of the key.Another ExampleBeers(name, manf, manfAddr).•FD’s = name manf, manf manfAddr.•Only key is name.–Manf manfAddr violates BCNF with a left side unrelated to any key.Decomposition to Reach BCNFSetting: relation R, given FD’s F.Suppose relation R has BCNF violation X B.•We need only look among FD’s of F for a BCNF violation, not those that follow from F.•Proof: If Y A is a BCNF violation and follows from F, then the computation of Y+ used at least one FD X B from F.–X must be a subset of Y.–Thus, if Y is not a superkey, X cannot be a superkey either, and X B is also a BCNF violation.1. Compute X+.–Cannot be all attributes – why?2. Decompose R into X+ and (R–X+) X.3. Find the FD’s for the decomposed relations.–Project the FD’s from F = calculate all consequents of F that involve only attributes from X+ or only from (RX+) X.R X+ XExampleR = Drinkers(name, addr, beersLiked, manf, favoriteBeer)F =1. name addr2. name favoriteBeer3. beersLiked manfPick BCNF violation name addr.•Close the left side: name + = name addr favoriteBeer.•Decomposed relations:Drinkers1(name, addr, favoriteBeer)Drinkers2(name, beersLiked, manf)•Projected FD’s (skipping a lot of work that leads nowhere interesting):–For Drinkers1: name addr and name favoriteBeer.–For Drinkers2: beersLiked manf.(Repeating)•Decomposed relations:Drinkers1(name, addr, favoriteBeer)Drinkers2(name, beersLiked, manf)•Projected FD’s:–For Drinkers1: name addr and name favoriteBeer.–For Drinkers2: beersLiked manf.•BCNF violations?–For Drinkers1, name is key and all left sides of FD’s are superkeys.–For Drinkers2, {name, beersLiked} is the key, and beersLiked manf violates BCNF.Decompose Drinkers2•First set of decomposed relations:Drinkers1(name, addr, favoriteBeer)Drinkers2(name, beersLiked, manf)•Close beersLiked+ = beersLiked, manf.•Decompose Drinkers2 into:Drinkers3(beersLiked, manf)Drinkers4(name, beersLiked)•Resulting relations are all in BCNF:Drinkers1(name, addr, favoriteBeer)Drinkers3(beersLiked, manf)Drinkers4(name, beersLiked)3NFOne FD structure causes problems:•If you decompose, you can’t check all the FD’s only in the decomposed relations.•If you don’t decompose, you violate BCNF.Abstractly: AB C and C B.•Example 1: title city theatre and theatre city.•Example 2: street city zip,zip city.Keys: {A, B} and {A, C}, but C B has a left side that is not a superkey.•Suggests decomposition into BC and AC.–But you can’t check the FD AB C in only these relations.ExampleA = street, B = city, C = zip.Join:street z ip545 Tech S q. 02138545 Tech S q. 02139city z ipCambridge 02138Cambridge 02139city street z ipCambridge 545 Tec h S q. 02138Cambridge 545 Tec h S q. 02139zip citystreet city zip“Elegant” WorkaroundDefine the problem away.•A relation R is in 3NF iff (if and only if)for every nontrivial FD X A, either:1. X is a superkey, or2. A is prime = member of at least one key.•Thus, the canonical problem goes away: you don’t have to decompose because all attributes are prime.What 3NF Gives YouThere are two important properties of a decomposition:1. We should be able to recover from the decomposed relations the data of the original.–Recovery involves projection and join, which we shall defer until we’ve discussed relational algebra.2. We should be able to check that the FD’s for the original relation are satisfied by checking the projections of those FD’s in the decomposed relations.•Without proof, we assert that it is always possible to decompose into BCNF and satisfy (1).•Also without proof, we can decompose into 3NF and satisfy both (1) and (2).•But it is not possible to decompose into BNCF and get both (1) and (2).–Street-city-zip is an example of this point.Multivalued DependenciesThe multivalued dependency X Y holds in a relation R if whenever we have two tuples of R that agree in all the attributes of X, then we can swap their Y components and get two new tuples that are also in R.X Y othersExampleDrinkers(name, addr, phones, beersLiked) with MVD Name phones. If Drinkers has the two tuples:name addr phones beersLiked sue a p1 b1sue a p2 b2it must also have the same tuples with phones components swapped: name addr phones beersLiked sue a p2 b1sue a p1 b2Note: we must check this condition for all pairs of tuples that agree on name, not just one pair.MVD Rules1.Every FD is an
View Full Document
Unlocking...