Functional DependenciesExamplesFinding the Attributes of a RelationRules for Binary RelationshipsRules for Multiway RelationshipsSome Properties of FD’sComparing Functional DependenciesClosure of a set of AttributesClosure AlgorithmExampleProblems in Designing SchemaRelation DecompositionDecompositions in GeneralBoyce-Codd Normal FormSlide 15And Now?What About This?More DecompositionsMore Careful StrategyExample DecompositionDecomposition Based on BCNF is Necessarily CorrectMultivalued DependenciesFunctional DependenciesDefinition: If two tuples agree on the attributes A , A , … A 1 2 n then they must also agree on the attributesB , B , … B 1 2 mFormally: A , A , … A 1 2 nB , B , … B 1 2 mMotivating example for the study of functional dependencies:Name Social Security Number Phone NumberExamplesProduct: name price, manufacturerPerson: ssn name, ageCompany: name stock price, presidentKey of a relation is a set of attributes that: - functionally determines all the attributes of the relation - none of its subsets determines all the attributes.Superkey: a set of attributes that contains a key.Finding the Attributes 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 ssnPersonRules for Binary RelationshipsSeveral cases are possible for a binary relationship E1 - E2: 1. Many-many: the key includes the key of E1 together with the key of E2.What happens for: 2. Many-one: 3. One-one:PersonbuysProductnameprice name ssnRules for Multiway RelationshipsNone, really.Except: 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.PurchaseProductPersonStorePayment MethodSome Properties of 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…A , A , … A 1 2 niAAlways holds.Splitting rule and Combing ruleComparing Functional DependenciesFunctional dependencies: a statement about the set of allowable databases.Entailment and equivalence: comparing sets of functional dependenciesEntailment: a set of functional dependencies S1 entails a set S2 if: any database that satisfies S1 much also satisfy S2.Example: {A B, B C} entails A CEquivalence: two sets of FD’s are equivalent if each entails the other.{A B, B C } is equivalent to {A B, A C, B C}Closure of a set of AttributesGiven a set of attributes A and a set of dependencies C, we want to find all the other attributes that are functionally determined by A. In other words, we want to find the maximal set of attributes B, such that for every B in B, C entails A B.Closure AlgorithmStart with Closure=A.Until closure doesn’t change do: if is in C, and B is not in Closure then add B to closure.A , A , … A 1 2 nBA , A , … A 1 2 nare all in the closure, andExampleA B CA D E B DA F BClosure of {A,B}:Closure of {A, F}:Problems in Designing SchemaName SSN Phone NumberFred 123-321-99 (201) 555-1234Fred 123-321-99 (206) 572-4312Joe 909-438-44 (908) 464-0028Joe 909-438-44 (212) 555-4000Problems: - redundancy - update anomalies - deletion anomaliesRelation Decomposition Name SSNFred 123-321-99Joe 909-438-44Name Phone NumberFred (201) 555-1234Fred (206) 572-4312Joe (908) 464-0028Joe (212) 555-4000Break the relation into two relations:Decompositions in GeneralA , A , … A 1 2 nLet R be a relation with attributes Create two relations R1 and R2 with attributes B , B , … B 1 2 mC , C , … C 1 2 lSuch that:B , B , … B 1 2 mC , C , … C 1 2 l A , A , … A 1 2 nAnd -- R1 is the projection of R on -- R2 is the projection of R on B , B , … B 1 2 mC , C , … C 1 2 lBoyce-Codd Normal FormA simple condition for removing anomalies from relations: A relation R is in BCNF if and only if: Whenever there is a nontrivial dependency for R , it is the case that { } a super-key for R. A , A , … A 1 2 nBA , A , … A 1 2 nIn English (though a bit vague): Whenever a set of attributes of R is determining another attribute, should determine all the attributes of R.ExampleName SSN Phone NumberFred 123-321-99 (201) 555-1234Fred 123-321-99 (206) 572-4312Joe 909-438-44 (908) 464-0028Joe 909-438-44 (212) 555-4000What are the dependencies?What are the keys?Is it in BCNF?And Now?SSN Name123-321-99 Fred909-438-44 JoeSSN Phone Number123-321-99 (201) 555-1234123-321-99 (206) 572-4312909-438-44 (908) 464-0028909-438-44 (212) 555-4000What About This?Name Price CategoryGizmo $19.99 gadgetsQuestion: Find an example of a 2-attribute relation that is not in BCNF.More DecompositionsName Address Move-DateName AddressName Move-DateWhat’s wrong?More Careful StrategyFind a dependency that violates the BCNF condition:A , A , … A 1 2 nB , B , … B 1 2 mA’sOthersB’sR1 R2Example Decomposition Name Social-security-number Age Eye Color Phone NumberFunctional dependencies: Name + Social-security-number Age, Eye ColorWhat if we also had an attribute Draft-worthy, and the FD: Age Draft-worthyDecomposition Based on BCNF is Necessarily CorrectAttributes A, B, C. FD: A CRelations R1[A,B]
View Full Document
Unlocking...