Chapter 15 1 CS 6360 Database Design Chris Irwin Davis Ph D Email chrisirwindavis utdallas edu Phone 972 883 3574 O ce ECSS 4 705 Notation In the following discussion we use an abbreviated notation when discussing functional dependencies We concatenate attribute variables and drop the commas for convenience Hence the FD X Y Z is abbreviated to XY Z and the FD X Y Z U V is abbreviated to XYZ UV 2 Inference Rules IR1 reflexive rule If X Y then X Y IR2 augmentation rule X Y XZ YZ IR3 transitive rule X Y Y Z X Z 3 Inference Rules IR4 decomposition or projective rule X YZ X Y and X Z IR5 union or additive rule X Y X Z X YZ IR6 pseudo transitive rule X Y WY Z WX Z 4 Closure Definition For each such set of attributes X we determine the set X of attributes that are functionally determined by X based on F X is called the closure of X under F Algorithm 16 1 can be used to calculate X 5 Algorithm 15 1 6 Coverage Definition A set of functional dependencies F is said to cover another set of functional dependencies E if every FD in E is also in F That is if every dependency in E can be inferred from F Alternatively we can say that E is covered by F Definition Two sets of functional dependencies E and F are equivalent if E F Therefore equivalence means that every FD in E can be inferred from F and every FD in F can be inferred from E that is E is equivalent to F if both the conditions E covers F and F covers E hold 7 Minimal Set of Functional Dependencies Informally a minimal cover of a set of functional dependencies E is a set of functional dependencies F that satisfies the property that every dependency in E is in the closure F of F In addition this property is lost if any dependency from the set F is removed F must have no redundancies in it and the dependencies in F are in a standard form 8 Minimal Cover To satisfy these properties we can formally define a set of functional dependencies F to be minimal if it satisfies the following conditions Every dependency in F has a single attribute for its right hand side We cannot replace any dependency X A in F with a dependency Y A where Y is a proper subset of X and still have a set of dependencies that is equivalent to F We cannot remove any dependency from F and still have a set of dependencies that is equivalent to F 9 Minimal Cover cont d We can think of a minimal set of dependencies as being a set of dependencies in a standard or canonical form and with no redundancies Condition 1 just represents every dependency in a canonical form with a single attribute on the right hand side Conditions 2 and 3 ensure that there are no redundancies in the dependencies either by having redundant attributes on the left hand side of a dependency Condition 2 or having a dependency that can be inferred from the remaining FDs in F Condition 3 10 Minimal Cover Definition A minimal cover of a set of functional dependencies E is a minimal set of dependencies in the standard canonical form and without redundancy that is equivalent to E We can always find at least one minimal cover F for any set of dependencies E using Algorithm 15 2 11 Algorithm 15 2 Let the given set of FDs be E B A D A AB D We have to find the minimal cover of E All above dependencies are in canonical form that is they have only one attribute on the right hand side so we have completed step 1 of Algorithm 16 2 and can proceed to step 2 In step 2 we need to determine if AB D has any redundant attribute on the left hand side that is can it be replaced by B D or A D 12 Since B A by augmenting with B on both sides IR2 we have BB AB or B AB i However AB D as given ii Hence by the transitive rule IR3 we get from i and ii B D Thus AB D may be replaced by B D We now have a set equivalent to original E say E B A D A B D No further reduction is possible in step 2 since all FDs have a single attribute on the left hand side In step 3 we look for a redundant FD in E By using the transitive rule on B D and D A we derive B A Hence B A is redundant in E and can be eliminated Therefore the minimal cover of E is B D D A 13