Logical Database Design (3 of 3)NormalizationDecomposition of a RelationAn Example of Information LossLossless Join DecompositionLossless Join: An ExampleTest for Lossless Join *TestLJ (cont.) *TestLJ: An ExampleDependency-Preserving DecompositionDependency Preservation: An ExampleTest for Dependency PreservationTestDP (cont.)TestDP: An exampleTestDP: An example (cont.) *Slide 16NormalizationNormalization to BCNFNormalization to BCNF (cont.)Normalization to BCNF (cont.) *Normalization to BCNF: An ExampleNormalize to BCNF: An Example *Slide 24Normalize to BCNF: Another Ex. *Equivalence of FD SetsExtraneous AttributesSummaryLook AheadLogical Database Design (3 of 3)John OrtizLecture 7 Logical Database Design (2) 2NormalizationIf a relation is not in BCNF or 3NF, we refine it by decomposing it into two or more smaller relation schemas that are in the normal form.Decomposition has to be used carefully, since there are potential problems.What are desirable properties of a decomposition, and how to test them?How to obtain a decomposition with some desirable properties?Lecture 7 Logical Database Design (2) 3Decomposition of a RelationLet R be a relation schema. A decomposition of R, demoted by D = {R1, R2, ..., Rn}, is a set of relation schemas such that R = R1 ... Rn. If {R1, R2, ..., Rn} is a decomposition of R and r is an instance of R, then r R1(r) R2(r) . . . Rn(r)Information may be lost (i.e. wrong tuples may be added by the natural join) due to a decomposition.Lecture 7 Logical Database Design (2) 4An Example of Information LossBefore AfterSID Name Cno Grade Room 101 Bill 1000 B 326 202 Mary 2000 A 326 SCSR SGSID Name Cno Grade Room 101 Bill 1000 B 326 202 Mary 2000 A 326 101 Mary 1000 B 326 202 Bill 2000 A 326 SID Cno Grade Room 101 1000 B 326 202 2000 A 326 SGName Room Bill 326 Mary 326 SRLecture 7 Logical Database Design (2) 5Lossless Join Decomposition Let R be a relation schema, and D = {R1, R2, ..., Rn} be a decomposition of R. D is a lossless (non-additive) join decomposition of R if for every legal instance r of R, we have r = R1(r) R2(r) . . . Rn(r)Theorem: Let F be a set of FDs over R, and D = {R1, R2} be a decomposition of R. D is a lossless-join decomposition if and only if R1 R2 R1 - R2 is in F+; orR1 R2 R2 - R1 is in F+.Lecture 7 Logical Database Design (2) 6Lossless Join: An Example Consider F = {B AH, L CAt} over Bank-Loans(Bank, Assets, Headquarter, Loan#, Customer, Amount).Let D = {Banks(B,A,H), Loans(B,L,C,At)}. Since Banks Loans = B AH = Banks - Loans is in F+ (since it is already in F), D is a lossless-join decomposition.What if the decomposition contains more than two relations.Lecture 7 Logical Database Design (2) 7Test for Lossless Join *Algorithm TestLJ (Chase)Input: A relation schema R(A1, …, Am), a set of FDs F, and a decomposition D = {R1, …, Rn}.Output: Yes, if D is a Lossless join; no, otherwise. Method:1. Create an n m table T (labeled by Ai and Rj). 2. If Ri contains Aj, place aj at Ti,j. Otherwise, place bij at Ti,j.Lecture 7 Logical Database Design (2) 8TestLJ (cont.) *3. Repeat for each FD X Y in F do For all rows with identical symbols on X do make the symbols on Y identical. (choose aj over bij whenever possible) Until no more change can be made.4. Return yes if there is a row of aj’s. Otherwise, return no.Lecture 7 Logical Database Design (2) 9TestLJ: An ExampleContinue with the previous example.Set up the table T. Enforce B AH. B A H L C At BAH a1 a2 a3 b14 b15 b16BLCAt a1 b22 b23 a4 a5 a6 B A H L C At BAH a1 a2 a3 b14 b15 b16BLCAt a1 a2 a3 a4 a5 a6Need to repeat until no more changes.Lecture 7 Logical Database Design (2) 10Dependency-Preserving Decomposition Let F be a set of FDs over R, and D = {R1, R2, ..., Rn} be a decomposition of R. D is a dependency-preserving decomposition if F+ = (R1(F) R2(F) . . . Rn(F))+ where for i = 1, …, nRi(F) = { X Y | X Y F and XY Ri}.Restrict FDs to local relations. If all “global” FDs can be derived from “local” FDs, all dependencies are preserved.Lecture 7 Logical Database Design (2) 11Dependency Preservation: An Example Consider F = {CS Z, Z C} over R(City, Street, Zipcode), and D ={R1(S, Z), R2(C, Z)}. Then R1(F) = {} and R2(F) = {Z C} (consider non-trivial FDs only)Since CS Z F+ but CS Z (R1(F) R2(F))+,D is not dependency-preserving.Lecture 7 Logical Database Design (2) 12Test for Dependency Preservation Algorithm TestDPInput: A relation schema R, A set of FDs F over R, a decomposition D = {R1, R2, ..., Rn} of R. Output: Yes, if D is dependency-preserving; no, otherwise. Method: for every X Y F if Ri such that XY Ri then X Y is preserved;Lecture 7 Logical Database Design (2) 13TestDP (cont.) else W := X; repeat for i from 1 to n do W := W ((W Ri)+ Ri); until there is no change to W; if Y W then X Y is preserved; if every X Y is preserved then return yes; else return no.Derive global FDs using only local FDs.Lecture 7 Logical Database Design (2) 14TestDP: An example Consider F = {A B, B C, C D, D A } over R(A, B, C, D), & D = {R1(A,B), R2(B,C), R3(C,D)}. Is D a dependency-preserving decomposition? Since AB R1, A B is preserved. Since BC R2, B C is preserved. Since CD R3, C D is preserved.Since DA is not in any one of the three relations, we need to compute W.Lecture 7 Logical Database Design (2) 15TestDP: An example (cont.) *Initialization: W = D; first iteration: W = D ((D AB)+ AB) = D; W = D ((D BC)+ BC) = D; W = D ((D CD)+ CD) = D (D+ CD) = D (ABCD CD) = CD;W changed from D to CD.Lecture 7 Logical Database Design (2) 16TestDP: An example (cont.) *second iteration: W = CD ((CD AB)+ AB) = CD; W = CD ((CD BC)+ BC) = CD (C+ BC) = BCD; W = BCD ((BCD CD)+ CD) = BCD; W changed from CD to BCD.Lecture 7 Logical Database Design (2) 18Normalization It
View Full Document