Report

Properties of Armstrong’s Axioms •Soundness •All dependencies generated by the Axioms are correct •Completeness •Repeatedly applying these rules can generate all correct dependency (i.e., any FDs in F+ be generated) Closure of Attribute Set X Let F be a set of functional dependencies on a set of attributes U and let X U. We define X+ to be the set of all attributes that are dependent on X (under F). X {A | X A} X+ enables us to tell at a glance whether a dependency XA follows from F. Algorithm to compute X+ under F // initialization 1. X+:= X; // reflexive rule // find new attribute 2. For each function dependency YZ in F, if Y X+ and Z has an attribute not in X+, add the new attribute to X+; //transitive rule 3. Repeat Step 2 until no new attribute can be found Example 1 R(A,B,C,D,E,F), F={A->D, B->E, DB, C->F}, What is {A}+? Closure of Attribute Set: Example 2 EMP_PROJ(SSN,PNUMBER,HOURS,ENAME,PNAME,PLOCATION) F={ {SSN}->{ENAME}, {PNUMBER}->{PNAME,PLOCATION}, {SSN,PNUMBER}{HOURS} } (1) Compute {SSN}+ Initialization:{SSN}+={SSN} 1st iteration: SSN->ENAME, ENAME to is a new attribute {SSN}+={SSN,ENAME} 2nd iteration: {SSN}+={SSN,ENAME}, cannot find any new attribute F={ {SSN}->{ENAME}, {PNUMBER}->{PNAME,PLOCATION}, {SSN,PNUMBER}{HOURS} } (2) Compute {PNUMBER}+ Initialization:{PNUMBER}+={PNUMBER} 1st iteration: {PNUMBER} -> {PNAME,PLOCATION} {PNUMBER}+={PNUMBER,PNAME,PLOCATION} 2nd iteration: cannot find any new attribute {PNUMBER}+={PNUMBER,PNAME,PLOCATION} (3) Compute {SSN, PNUMBER}+ Use of X+ 1: Checking if XY • Steps of checking if an FD X Y is in the closure of a set of FDs F : + 1. Compute X wrt F. 2. Check if Y is in X+. 3. Y X+ XY is in F+ • Does F = {AB, BC, CDE } imply AE? • i.e, is A E in F+? Equivalently, is E in A+? • A+ (w.r.t. F)={A,B,C} • E is not in A+, thus, AE is not in F+. Use of X+ 2: Finding a key K Let R be the set of attributes for a schema and F be its functional dependency set Set K:=R For each attribute A in K Compute (K-A)+ w.r.t. F If (K-A)+ contains all the attributes in R then set K:= K-A • This algorithm returns only one key out of the possible candidate keys for R. • The key returned depends on the order in which attributes are removed from R. Examples: (1) R={A,B,C,D} F={AB,BC,ABD}; find a key of R. (2) R={A,B,C,D,E,F} F= {A->C, A->D, B->C, E->F}; find a key of R Use of X+ 3: Compute F+ Given a set of functional dependencies F, we define F+ to be the set of all functional dependencies that can be inferred from F. 1. 2. 3. F+ ={}; For each attribute set A in R, computing A+ For each XY implied by A+, add XY to F+ Equivalence of Sets of Functional Dependencies Let E&F be two sets of functional dependencies. + •F covers E if E F . •E and F are equivalent if E+=F+. •E+=F+ iff E covers F and F covers E. Note: Equivalence means that every FD in E can be inferred from F, and every FD in F can be inferred from E. Determine whether F covers E: + For each FD XY in E, calculate X with respect to F, then check whether X+ Y. EXAMPLE: Check whether or not F is equivalent to G. F={AC, ACD, EAD,EH} G={ACD, EAH} •Prove that F is covered by G. + + {A} ={A,C,D} (wrt to G). Since {C} A , AC can be inferred from G. + {AC} ={A,C,D} (wrt to G). Since {D} {AC}+, ACD is covered by G. {E}+={E,A,H,C,D} (wrt G), Since {AD} {E}+, EAD is covered by G. Since {H} {E}+, EH is covered by G. F={AC, ACD, EAD,EH} G={ACD, EAH} Prove that G is covered by F: •{A}+={A,C,D} (wrt F), Since {CD} {A}+, ACD is covered by F. •{E}+={E,A,D,H,C} (with respect to F) {A,H} {E}+, EAH is covered by F. Since F covers G and G covers F, F and G are equivalent. Minimal Cover of Functional Dependencies A set of functional dependencies F is minimal if it satisfies the following three conditions: •Every FD in F has a single attribute for its right-hand side. (This is a standard form, not a requirement.) •We cannot replace any dependency XA in F with a dependency YA, 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. There can be several minimal covers for a set of functional dependencies! Minimal Cover Definition: A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. /* The following procedure finds one minimal cover of F. */ Procedure: Find a minimal cover Fmin for F. 1. Set Fmin=F /*put every FD in a standard form, i.e., it has a single attribute as its right-hand side*/ 2. Replace each FD XA1,A2,…,An in Fmin by the n FDs XA1,…,XAn. /* minimize the left side of each FD, i.e., every attribute is needed */ 3. For each FD XA in Fmin • For each B X, • Let T=(Fmin- {XA})U{(X-{B})A} • Check whether T is equivalent to Fmin (1) • If (1) is true, then set Fmin = T. /* delete redundant FDs, i.e., No redundant FDs remain in Fmin. */ 4. For each FD XA in Fmin Let T=Fmin-{XA} Check whether T is equivalent to Fmin. (2) If (2) is true, set Fmin = T. Minimal Cover F={X1Y1, X2Y2, … XnYn} is a minimum cover 1) Any Yi is a single attribute 2) For any XiYi, it is impossible that X’Y and X’ is a subset of X 3) No XiYi can be taken out • F’ = F - {XiYi} is not equivalent to F Example: Find the minimal cover of the set F={ABCDE,ED,AB,ACD}. Example: Find the minimal cover of the set F={ABCDE,ED,AB,ACD}. Step 2: Fmin={ABCDE,ED,AB,ACD} Step 3: Replace ACD with AD; T={ABCDE,ED,AB,AD} Compute {A}+ wrt to F, {A}+={A,B} Compute {A}+ wrt to T, {A}+={A,B,D} Cannot replace Fmin with T. Is T equivalent to Fmin? Can Fmin Cover T? No, keep ACD Replace ABCDE with ACDE, T={ACDE,ED,AB,ACD} Compute {ACD}+ wrt to F, {ACD}+={A,C,D,B,E} Compute {ACD}+ wrt to T,{ACD}+={A,C,D,E,B} Replace Fmin with T. Step 3: (cont’d) Replace ACDE with ACE, T={ACE,ED,AB,ACD} Compute {AC}+ wrt to F, {AC}+={ACDBE} Compute {AC}+ wrt to T,{AC}+={ACEDB} Replace Fmin with T. Step 4: Consider T={ACE,ED,ACD,AB} (take out ACD) {AC}+={A,C,E,D,B} with respect to T; {D} {AC}+; we don’t have to include ACD The minimal cover of F is: {ACE,ED,AB} Some Important Concepts • X+ : Closure of an attribute set X – • K: a key – • minimum set of attributes that determines all attributes F+ : Closure of a dependency set F – • The set of all attributes that are determined by X The set of all dependencies that are implied from F Fmin: a minimum cover of a dependency set F – a minimum set of FDs that is equivalent to F