slides01-1.pdf

Background: Functional Dependencies #0F We are always talking about a relation R, with a #0Cxed schema #28set of attributes#29 and a varying instance #28set of tuples#29. #0F Conventions: A;B;:::are attributes; :::;Y;Z are sets of attributes. Concatenation means union. #0F FD is X ! Y, where X and Y are sets of attributes. Two tuples that agree in all attributes of X must agree in all attributes of Y . #0F Implication: FD X ! Y follows from F i#0B all relation instances that satisfy F also satisfy X ! Y . Three Ways to Reason About FD's 1. Semantic:FDX ! Y is the set of relation instances that satisfy it. a33 Say Fj= X ! Y if every instance that satis#0Ces all FD's in F also satisfy X ! Y . a33 All approaches assume there is a #0Cxed relation scheme R to which the FD's pertain. 2. Algorithmic: Give an algorithm that tells us, given F and X ! Y, whether Fj= X ! Y . 3. Logical: Give a reasoning system that lets us deduce an FD like X ! Y exactly when Fj= X ! Y . a33 Deduction indicated by F`X ! Y . Closure Test for Implication#28Algorithmic Approach#29 Start with X + = X. Adjoin V to X + if U ! V is in F, and U #12 X + .At end, test if Y #12 X + . #0F Proof that if Y #12 X + , then Fj= X ! Y : Easy induction on the number of additions to X + that X ! A for all A in X + . #0F Proof that if F implies X ! Y , then Y #12 X + : Prove the contrapositive; assume Y is not a subset of X + and prove F does not imply X ! Y. Construct relation R with two tuples that agree on X + and disagree elsewhere. 1 Armstrong's Axioms #28Logical Approach#29 A sound #28what may be deduced is correct in the j= sense#29 and complete #28what is true in the j= sense can be deduced#29 axiomatization of FD's. A1: Trivial FD's or Re#0Dexivity. X ! Y always holds if Y #12 X. A2: Augmentation.IfX ! Y , then XZ ! YZfor any set of attributes Z. A3: Transitivity.IfX ! Y and Y ! Z, then X ! Z. Deductive Proofs A series of #5Clines." Each line is either: 1. A given statement #28FD in the given set F for deductions about FD's#29, or 2. A statement that follows from previous lines by applying an axiom. Example Given fAB ! C; CD ! Eg, deduce ABD ! E. AB ! C #28Given#29 ABD ! CD #28A2#29 CD! E #28Given#29 ABD ! E #28A3#29 Proof of Soundness Easy observations about relations. Proof of Completeness 1. Given F, show that if A is in X + , then X ! A follows from F by AA's. 2. Show that if X ! A 1 ;:::;X ! A n follow from AA's, then so does X ! A 1 #01#01#01A n . 3. Complete the proof by observing that X ! A 1 #01#01#01A n follows from F i#0B all of A 1 ;:::;A n are in X + , and therefore i#0B X ! A 1 #01#01#01A n follows by AA's. Proof #282#29 Induction on i that X ! A 1 #01#01#01A i follows. #0F Basis: i = 1, given. 2 #0F Induction: Assume X ! A 1 #01#01#01A i,1 . a33 X ! XA 1 #01#01#01A i,1 #28A2 by X applied to X ! A 1 #01#01#01A i,1 #29. a33 XA 1 #01#01#01A i,1 ! A i #28A2 by A 1 #01#01#01A i,1 applied to X ! A i #29. a33 X ! A 1 #01#01#01A i #28A3 applied to previous two FD's#29. Proof #281#29 Induction on the number of steps used to add A to X + . #0F Basis: 0 steps. Then A is in X, and X ! A by A1. #0F Induction: Assume B 1 #01#01#01B k ! A in F used to add A to X + . a33 By the inductivehypothesis, X ! B j follows from F for all 1 #14 j #14 k. a33 By part #282#29 of the theorem, X ! B 1 #01#01#01B k follows from F. a33 By A3, X ! A follows. Background: Normal Forms #0F A key for R is a minimal set of attributes such that X ! R #28note: I use R as both the instance and schema of a relation | shame on me#29. A superkey is any superset of a key. #0F BCNF: If X ! Y holds for R and is nontrivial, then X is a superkey. #0F 3NF: If X ! Y holds for R and is nontrivial, then either X is a superkey or Y contains a prime attribute #28member of some key#29. #0F Decomposition:We can decompose R into schemas S 1 ;:::;S n if S 1 #5B#01#01#01#5BS n = R. The instance for S i is #19 S i #28R#29. The FD's that hold for S i are those X ! Y such that XY #12 S i and X ! Y follows from the given FD's for R. Covers of Sets of FD's #0F Sets F 1 and F 2 of FD's are equivalent if each implies the other. a33 I.e., exactly the same relation instances satisfy each. 3 #0F Any set of FD's equivalenttoF is a cover for F. #0F Acover is minimal if: 1. No right side has more than one attribute. 2. We cannot delete any FD from the cover and have an equivalent set of FD's. 3. We cannot delete any attribute from any left side and have an equivalent set of FD's. Example Relation CTHRSG represents courses, teachers, hours, rooms, students, and grades. The FD's: C ! T; HR ! C; HT ! R; HS ! R; CS ! G; CH ! R. #0F We can eliminate CH ! R. a33 Proof: Using the other 5 FD's, CH + = CHTR. #0F Having done so, we cannot eliminate any attribute from any left side. a33 Sample proof: Suppose we tried to eliminate T from HT ! R.Wewould need that C ! T, HT ! R, HR ! C, HS ! R, and CS ! G imply H ! R. But H + = H with respect to these 5 FD's. #0F Thus the remaining #0Cve are a minimal cover of the original six. #0F Note: minimal cover need not be unique, or even have the same number of FD's. Lossless Join The decomposition of R into S 1 ;:::;S n has a lossless join #28with respect to some constraints on R#29 if for any instance r of R that satis#0Ces the constraints: #19 S 1 #28r#29 .#2F #01#01#01.#2F#19 S n #28r#29=r #0F Motivation: We can replace R by S and T, knowing that the instance of R can be recovered from the instances of S and T. Theorem A decomposition of R into S and T has a lossless join wrt FD's F if and only if S #5C T ! S or S #5C T ! T. 4 Proof #0F First note that r #12 #19 S #28r#29 .#2F#19 T #28r#29 always. #0F Assume S #5C T ! S and show that #19 S #28r#29 .#2F#19 T #28r#29 #12 r a33 Suppose s is in #19 S #28r#29 and t is in #19 T #28r#29, and s and t join #28i.e., they agree in S #5C T#29. a33 Then t is the projection of a tuple t 0 of r that agrees with s on S. a33 So t 0 agrees with t on T and with s on S, so t 0 is s.#2Ft; i.e., s.#2Ftis in r. #0F Similarly if S #5C T ! T. #0F Now assume neither FD follows from F. a33 Then there is an instance r consisting of two tuples that agree on #28S #5C T#29 + and disagree elsewhere. This instance satis#0Ces F. a33 Neither S nor T is contained in #28S #5C T#29 + #28or else one of the FD's in question would follow#29. a33 Thus, r projected and rejoined yields four distinct tuples, and cannot be r. Theorem We can always decompose a relation R with FD's F into BCNF relations with a lossless join. Proof #0F We decompose when we #0Cnd a BCNF violation X ! Y ,into X #5B Y and #28R,Y #29 #5B X. #0F But , #28R , Y#29 #5B X #01 #5C #28X #5B Y#29=X.Thus the intersection of the schemas functionally determines one of them, X #5B Y. #0F To complete the proof, we need to show that when we decompose further, the resulting n relations have a lossless join, but that is an easy induction on n. 5 Dependency Preservation When we decompose R with FD's F, will F be equivalent to the union of its projections onto the decomposed relations? #0F One way to guarantee dependency preservation is to use a minimalcover, and convert each FD in the cover X ! A into the schema XA. a33 But if there are some attributes not mentioned in any FD, make them a schema by themselves. Theorem A minimal cover F yields 3NF relations. Proof Suppose XA #28the relation from X ! A#29 is not in 3NF, because Y ! B is a 3NF violation. #0F We know Y is not a superkey, and B is not prime. #0F Case 1: A = B. Then Y #1A X. Since Y ! B follows from F, and X ! A surely follows from Y ! B,we know F is equivalentto F,fX ! Ag#5BfY ! Bg. a33 Then F was not a minimalcover. #0F Case 2: A 6= B. Then B is in X. a33 X is surely a superkey for XA, and since B is not prime, B must not be in anykey Z #12 X. a33 Then #28X ,B#29 ! A can replace X ! A in F, showing F is again not minimal. DecompositionWith 3NF, Dependency Preservation and Lossless Join To the schema from a minimal cover, add a key for the original relation if there is not already some relation schema that is a superkey. Example R = ABCD; F = fA ! B;C ! Dg. #0F Start with AB and CD from the FD's. #0F Only key for R is AC. #0F Thus, DP, LJ, 3NF decomposition is fAB;AC;CDg. 6 #0F Proof that the decomposition is always LJ will havetowait for the theory of #5Cgeneralized dependencies." a33 This decomposition is obviously LJ, since AB .#2FACis lossless because A ! B, and then ABC .#2FCDis lossless because of C ! D. 7 small1.dvi