Functional Dependencies, NormalizationOr…Fixing Broken Database DesignsOutlineFunctional Dependencies (FD)ExampleFDs from DataSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14FDs from ER DiagramsDrawing FDsNotation ShorthandKeys RevisitedSlide 19Two Ways to Find KeysWhy Talk About FDs?Redundancy Leads to AnomaliesSlide 23NormalizationThird Normal FormNormalization AlgorithmExample: Grades RelationStep 1: Find the FDsStep 2: Check for 3NF ViolationsStep 3: Pick a Violating FD, Find ClosureStep 4: Split R into Two RelationsRepeat for the New RelationsFunctional Dependencies,NormalizationRose-Hulman Institute of TechnologyCurt CliftonOr…Fixing Broken Database DesignsThis material will almost certainly appear on Exam II next week.OutlineFunctional DependenciesKeys RevisitedRedundancy and AnomaliesNormalizationFunctional Dependencies (FD)Let X be a set of attributes of a relation RLet A be a single attribute of RX  A holds for R if:whenever two tuples of R agree on all the attributes of X, then they must also agree on the attribute A.We say X “uniquely determines” A in RExampleCustomer(Name, Addr, SodaLiked, Manf, FavSoda), with name identifying a unique personLots of redundancy here…Name Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes Name  Addr?Name Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes Name  Addr?Yes, since we assumed unique namesName Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes Name  FavSoda?Name Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes Name  FavSoda?Yes, we want just one favorite per personName Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes SodaLiked  Manf?Name Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes SodaLiked  Manf?Yes, since each soda has just one manf.Name Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes FavSoda  Name?Name Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from DataDoes FavSoda  Name?No, two people might have the same favoriteName Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeFDs from ER DiagramsFrom entity sets(Key of entity set)  other attributes of entity setFrom many-one relationship(Key of “many” set)  attributes of “one” setDrawing FDsUse arrows to indicate FDs on schemas:Customer(Name, Addr, SodaLiked, Manf, FavSoda)Notation ShorthandTechnically FDs go from sets to single attributes{ Name }  Addr{ Name }  FavSodaOften just combine to write:Name  Addr, FavSodaUsually omit set braces on left side also:Restaurant, Soda  PriceKeys RevisitedLet K be a set of attributes of a relation RK is a super key for R if:For all attributes A in R, K  AK is a key for R if:No proper subset of K is a super key for RAn attribute B is a prime attribute of R if:B is an element of some key of RExampleWhat is the key here?What are the prime attributes?Customer(Name, Addr, SodaLiked, Manf, FavSoda)Two Ways to Find KeysGuess a superkey K:Show that K  A for all attributes AShow that no subset of K is a superkeyFind all functional dependenciesCheck all possible keysWhy Talk About FDs?Let us formally identify redundancyTell us how to fix it!Redundancy Leads to AnomaliesUpdate anomaly: one occurrence of a fact is changed, but not all occurrencesDeletion anomaly: valid fact is lost when a tuple is deletedExampleName Addr SodaLiked Manf FavSodaJaneway Voyager Pepsi PepsiCo CokeJaneway Voyager Sprite CocaCola CokeSpock Enterprise Pepsi PepsiCo CokeRedundant with first row since Name  Addr, FavSodaRedundant with first row since SodaLiked  ManfNormalizationUsing functional dependencies to eliminate redundancyAn extremely powerful techniqueThird Normal FormA relation R is in Third Normal Form (3NF) if whenever X  A is a nontrivial functional dependency that holds in R, then either:X is a superkey for R, orA is a prime attribute of RNormalization AlgorithmTo normalize a relation R:Find the functional dependencies for RCheck that whether each FD satisfies 3NFIf so, we’re done and R is normalizedOtherwise let X  A be an FD that violates 3NFFind the closure of X in R, denoted X+Split R into new relations (R - X+ + X) and X+ Repeat algorithm for each new relationExample: Grades RelationGrade(Term, Yr, C#, Sec#, IName, SName, SAddr, S#, SSSN, Gr)Step 1: Find the FDsStep 2: Check for 3NF ViolationsA relation R is in Third Normal Form (3NF) if whenever X  A is a nontrivial functional dependency that holds in R, then either:X is a superkey for R, orA is a prime attribute of RStep 3: Pick a Violating FD, Find ClosureFor X  A the closure of X, denoted X+, is:The set of all attributes that can be reached from any subset of X by following any FDsOr, just follow the arrowsStep 4: Split R into Two RelationsR-X +X X +-XR2R1RRepeat for the New RelationsFind FDsCheck for 3NF