!" #Chris Irwin Davis, Ph.D. Email: [email protected] Phone: (972) 883-3574 Office: ECSS 4.705Chapter 15.1CS-6360 Database Design!" #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.16!" #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 →
View Full Document