Functional DependenciesExamplesFinding the Attributes of a RelationRules for Binary RelationshipsRules for Multiway RelationshipsSome Properties of FD’sComparing Functional DependenciesClosure of a set of AttributesClosure AlgorithmExampleFunctional 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 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 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,
View Full Document