Lecture 11: Functional DependenciesOutlineRelational Schema DesignFunctional DependenciesImportant Point!ExamplesFormal definition of a keyExamples of KeysFinding the Keys of a RelationFinding the KeysSlide 11Expressing DependenciesSlide 13Inference Rules for FD’sInference Rules for FD’s (continued)Slide 16PowerPoint PresentationSlide 18Closure of a set of AttributesClosure AlgorithmExampleWhy Is the Algorithm Correct ?Relational Schema Design (or Logical Design)Slide 24Relation DecompositionSlide 26Decompositions in GeneralIncorrect DecompositionSlide 29Normal FormsBoyce-Codd Normal FormSlide 32Decompose it into BCNFSummary of BCNF DecompositionExample DecompositionOther ExampleCorrect DecompositionsSlide 383NF: A Problem with BCNFSo What’s the Problem?Solution: 3rd Normal Form (3NF)Lecture 11:Functional DependenciesJanuary 31st, 2003Outline•Functional dependencies (3.4)•Rules about FDs (3.5)•Design of a Relational schema (3.6)Relational Schema DesignPersonbuysProductnameprice name ssnConceptual Model:Relational Model:plus FD’sNormalization:Eliminates anomaliesFunctional DependenciesDefinition: A1, ..., Am B1, ..., Bn holds in R if:t, t’ R, (t.A1=t’.A1 ... t.Am=t’.Am t.B1=t’.B1 ... t.Bm=t’.Bm )A1 ... Am B1 ... Bmif t, t’ agree here then t, t’ agree herett’RImportant Point!•Functional dependencies are part of the schema!•They constrain the possible legal data instances.•At any point in time, the actual database may satisfy additional FD’s.Examples•EmpID Name, Phone, Position•Position Phone•but Phone PositionEmpID Name Phone PositionE0045 Smith 1234 ClerkE1847 John 9876 SalesrepE1111 Smith 9876 SalesrepE9999 Mary 1234 LawyerFormal definition of a key•A key is a set of attributes A1, ..., An s.t. for any other attribute B, A1, ..., An B•A minimal key is a set of attributes which is a key and for which no subset is a key•Note: book calls them superkey and keyExamples of Keys•Product(name, price, category, color)name, category pricecategory colorKeys are: {name, category} and all supersets•Enrollment(student, address, course, room, time)student addressroom, time coursestudent, course room, timeKeys are: [in class]Finding the Keys of a RelationGiven a relation constructed from an E/R diagram, what is its key?Rules: 1. If the relation comes from an entity set, the key of the relation is the set of attributes which is the key of the entity set.addressname ssnPersonPerson(address, name, ssn)Finding the KeysPersonbuysProductnameprice name ssnbuys(name, ssn, date)dateRules: 2. If the relation comes from a many-many relationship, the key of the relation is the set of all attribute keys in the relations corresponding to the entity setsFinding the KeysExcept: if there is an arrow from the relationship to E, then we don’t need the key of E as part of the relation key.PurchaseProductPersonStoreCreditCardnamecard-nossnsnamePurchase(name , sname, ssn, card-no)Expressing DependenciesSay: “the CreditCard determines the Person”PurchaseProductPersonStoreCreditCardnamecard-nossnsnamePurchase(name , sname, ssn, card-no)Incomplete(what doesit say ?)card-no nameFinding the KeysMore rules in the book – please read !Inference Rules for FD’sA , A , … A 1 2 nB , B , … B 1 2 mA , A , … A 1 2 n1Is equivalent toBA , A , … A 1 2 n2BA , A , … A 1 2 nmB…Splitting rule and Combing ruleA1 ... Am B1 ... BmInference Rules for FD’s(continued)A , A , … A 1 2 niATrivial RuleWhy ?A1 ... Amwhere i = 1, 2, ..., nInference Rules for FD’s(continued)A , A , … A 1 2 nTransitive Closure RuleB , B , … B1 2 mA , A , … A 1 2 n1B , B …, B2 m1C , C …, C2 p1C , C …, C2 pIfandthenWhy ?A1 ... Am B1 ... BmC1...Cp•Enrollment(student, major, course, room, time)student majormajor, course roomcourse timeWhat else can we infer ? [in class]Closure of a set of AttributesGiven a set of attributes {A1, …, An} and a set of dependencies S.Problem: find all attributes B such that:any relation which satisfies S also satisfies:A1, …, An B The closure of {A1, …, An}, denoted {A1, …, An} ,is the set of all such attributes B+Closure AlgorithmStart with X={A1, …, An}.Repeat until X doesn’t change do: if is in S, and C is not in X then add C to X.B , B , … B 1 2 nCB , B , … B 1 2nare all in X, andExampleA B CA D E B DA F BClosure of {A,B}: X = {A, B, }Closure of {A, F}: X = {A, F, }R(A,B,C,D,E,F)Why Is the Algorithm Correct ?•Show the following by induction:–For every B in X:•A1, …, An B•Initially X = {A1, …, An} -- holds•Induction step: B1, …, Bm in X–Implies A1, …, An B1, …, Bm–We also have B1, …, Bm C–By transitivity we have A1, …, An C•This shows that the algorithm is sound; need to show it is completeRelational Schema Design(or Logical Design)Main idea:•Start with some relational schema•Find out its FD’s•Use them to design a better relational schemaRelational Schema DesignAnomalies:• Redundancy = repeat data• Update anomalies = Fred moves to “Bellvue”• Deletion anomalies = Fred drops all phone numbers:what is his city ?Recall set attributes (persons with several phones):SSN Name, City, but not SSN PhoneNumberName SSN PhoneNumber CityFred 123-45-6789 206-555-1234 SeattleFred 123-45-6789 206-555-6543 SeattleJoe 987-65-4321 908-555-2121 WestfieldJoe 987-65-4321 908-555-1234 WestfieldRelation DecompositionBreak the relation into two:Name SSN CityFred 123-45-6789 SeattleJoe 987-65-4321 WestfieldSSN PhoneNumber123-45-6789 206-555-1234123-45-6789 206-555-6543987-65-4321 908-555-2121987-65-4321 908-555-1234Relational Schema DesignPersonbuysProductnameprice name ssnConceptual Model:Relational Model:plus FD’sNormalization:Eliminates anomaliesDecompositions in GeneralR(A1, ..., An) Create two relations R1(B1, ..., Bm) and R2(C1, ..., Cp)such that: B1, ..., Bm C1, ..., Cp = A1, ..., Anand:R1 = projection of R on B1, ..., Bm R2 = projection of R on C1, ..., CpIncorrect Decomposition•Sometimes it is incorrect:Name Price CategoryGizmo 19.99 GadgetOneClick 24.99 CameraDoubleClick 29.99 CameraDecompose on :
View Full Document
Unlocking...