DecompositionRecall Functional DependenciesClosure of a Set of FDClosure Computing ExampleLossless DecompositionLossless Decomposition Testing (1)Lossless Decomposition Testing (2)Lossless Decomposition Testing (3)Lossless Decomposition Testing (3) Cont.Slide 10Slide 11Dependency PreservationDependency Preservation Cont.Slide 14Slide 15Slide 16ReferenceDecompositionDecompositionLiangsheng DengLiangsheng DengSection 2Section 211/15/200511/15/2005Recall Functional DependenciesRecall Functional Dependencies A->B holds iff for any pairs of tuples t1 and t2 A->B holds iff for any pairs of tuples t1 and t2 such that if t1[A] = t2[A], then t1[B] = t2[B].such that if t1[A] = t2[A], then t1[B] = t2[B].Armstong’s axioms:Armstong’s axioms:Reflexivity rule. If a is a set of attributes and b is a Reflexivity rule. If a is a set of attributes and b is a subset of a, then a->b holds.subset of a, then a->b holds.Augmentation rule. If a->b holds and c is a set of Augmentation rule. If a->b holds and c is a set of attributes, then ac->bc holds.attributes, then ac->bc holds.Transitivity rule. If a->b holds and b->c holds, then Transitivity rule. If a->b holds and b->c holds, then a->c holds.a->c holds.Closure of a Set of FDClosure of a Set of FD Given f, a set of FD of a relational Given f, a set of FD of a relational schema, we can use Armstrong axioms to schema, we can use Armstrong axioms to derive other possible FD implied by f.derive other possible FD implied by f.The closure of f is the set of all FD implied The closure of f is the set of all FD implied by f.by f. Determine whether S, a set of attributes, Determine whether S, a set of attributes, is a superkey by computing the closure of is a superkey by computing the closure of S.S.Closure Computing ExampleClosure Computing Example Given R(A, B, C, D, E, H) withGiven R(A, B, C, D, E, H) withFD1. BD->A, FD2. AC->H, FD3. D->C, FD1. BD->A, FD2. AC->H, FD3. D->C, FD4. E->D.FD4. E->D.Is BE a superkey of R?Is BE a superkey of R?{BE}+ = {BDE} because E->D{BE}+ = {BDE} because E->D{BE}+ = {BCDE} because D->C{BE}+ = {BCDE} because D->C{BE}+ = {ABCDE} because BD->A{BE}+ = {ABCDE} because BD->A{BE}+ = {ABCDEH} because AC->H{BE}+ = {ABCDEH} because AC->HBE is a superkey of R.BE is a superkey of R.Lossless DecompositionLossless Decomposition The purpose of using lossless decomposition: Reduce unnecessary redundancy. Retrieve information efficientlyHow do we decide a decomposition is a lossless decomposition?Let R be a relation schema. Let F be a set of functional dependencies on R. Let R1 and R2 form a decomposition of R. The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies holds.R1 ∩ R2 -> R1 or R2 ∩ R1 -> R2Lossless Decomposition Testing (1) Lossless Decomposition Testing (1) Given R1(A, B), R2(A, C, D) andGiven R1(A, B), R2(A, C, D) andF = {A->C; D->B; AC->B}.F = {A->C; D->B; AC->B}.Is the join of R1 and R2 lossless?Is the join of R1 and R2 lossless? R1 ∩ R2 = {A} If we can prove A->B, then the answer is yes.If we can prove A->B, then the answer is yes.Proof:Proof:A->AC because A->CA->AC because A->CA->B because A->AC and AC->BA->B because A->AC and AC->BSo, it is a lossless cecomposition.So, it is a lossless cecomposition.Lossless Decomposition Testing (2)Lossless Decomposition Testing (2) To test whether To test whether R1 ∩ R2 -> R1 or R2, we can test whether R1 ∩ R2 is a superkey of R1 or R2 by computing the closure of R1 ∩ R2. Same question in the previous slide.{R1 ∩ R2}+ = {A}+,{A}+ = {AC} because A->C{A}+ = {ABC} because AC->BConclusion: A is a superkey of R1.Therefore, it is a lossless decomposition.Lossless Decomposition Testing (3)Lossless Decomposition Testing (3) For the case of decomposition of a schema into For the case of decomposition of a schema into more than 2 schemas, we can use the chase more than 2 schemas, we can use the chase matrix algorithm.matrix algorithm. For example, F = {A->C, B->C, C->D, For example, F = {A->C, B->C, C->D, DE->C, CE->A}, R1(AD), R2(AB), R3(BE),DE->C, CE->A}, R1(AD), R2(AB), R3(BE),R4(CDE) and R5(AE).R4(CDE) and R5(AE).AABBCCDDEER1(AD)R1(AD)a1a1b12b12b13b13a4a4b15b15R2(AB)R2(AB)a1a1a2a2b23b23b24b24b25b25R3(BE)R3(BE)b31b31a2a2b33b33b34b34a5a5R4(CDE)R4(CDE)b41b41b42b42a3a3a4a4a5a5R5(AE)R5(AE)a1a1b52b52b53b53b54b54a5a5Lossless Decomposition Testing (3) Lossless Decomposition Testing (3) Cont.Cont.A->C, we getA->C, we getAABBCCDDEER1(AD)R1(AD)a1a1b12b12b13b13a4a4b15b15R2(AB)R2(AB)a1a1a2a2b13b13b24b24b25b25R3(BE)R3(BE)b31b31a2a2b33b33b34b34a5a5R4(CDE)R4(CDE)b41b41b42b42a3a3a4a4a5a5R5(AE)R5(AE)a1a1b52b52b13b13b54b54a5a5B->C, we getB->C, we getAABBCCDDEER1(AD)R1(AD)a1a1b12b12b13b13a4a4b15b15R2(AB)R2(AB)a1a1a2a2b13b13b24b24b25b25R3(BE)R3(BE)b31b31a2a2b13b13b34b34a5a5R4(CDE)R4(CDE)b41b41b42b42a3a3a4a4a5a5R5(AE)R5(AE)a1a1b52b52b13b13b54b54a5a5Lossless Decomposition Testing (3) Lossless Decomposition Testing (3) Cont.Cont.C->D, we getC->D, we getAABBCCDDEER1(AD)R1(AD)a1a1b12b12b13b13a4a4b15b15R2(AB)R2(AB)a1a1a2a2b13b13a4a4b25b25R3(BE)R3(BE)b31b31a2a2b13b13a4a4a5a5R4(CDE)R4(CDE)b41b41b42b42a3a3a4a4a5a5R5(AE)R5(AE)a1a1b52b52b13b13a4a4a5a5DE->CDE->CAABBCCDDEER1(AD)R1(AD)a1a1b12b12b13b13a4a4b15b15R2(AB)R2(AB)a1a1a2a2b13b13a4a4b25b25R3(BE)R3(BE)b31b31a2a2a3a3a4a4a5a5R4(CDE)R4(CDE)b41b41b42b42a3a3a4a4a5a5R5(AE)R5(AE)a1a1b52b52a3a3a4a4a5a5Lossless Decomposition Testing (3) Lossless Decomposition Testing (3) Cont.Cont.CE->ACE->AAABBCCDDEER1(AD)R1(AD)a1a1b12b12b13b13a4a4b15b15R2(AB)R2(AB)a1a1a2a2b23b23a4a4b25b25R3(BE)R3(BE)a1a1a2a2a3a3a4a4a5a5R4(CDE)R4(CDE)a1a1b42b42a3a3a4a4a5a5R5(AE)R5(AE)a1a1b52b52a3a3a4a4a5a5The third tuple has a1, a2, a3 ,a4 and a5, soThe third tuple has a1, a2, a3 ,a4 and a5, so it is a lossless decomposition.it is a lossless decomposition.Dependency PreservationDependency PreservationLet Let FF be a set of functional dependencies on be a set of functional dependencies on schema schema RR. . Let {R1,R2,…Rn} be a decomposition of Let {R1,R2,…Rn} be a decomposition of RR. . The The restrictionrestriction of of FF to Ri is the set of all to Ri is the set of all functional dependencies in F+ that include functional dependencies in F+ that include only attributes of Ri. only attributes of Ri. Functional dependencies in a restriction can Functional dependencies in a restriction can be tested in one relation, as they involve
View Full Document
Unlocking...