!" #Chris Irwin Davis, Ph.D.Email: [email protected]: (972) 883-3574Office: ECSS 4.705Chapter 16.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. ■ 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!" #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.6!" #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.7!" #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. 8!" #■ 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).9!" #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 16.2.10!" #Algorithm 16.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?11!" #■ 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
Unlocking...