Unformatted text preview:

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) 2NormalizationIf 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 RelationLet 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 LossBefore 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+; orR1  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 a6Need 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, …, nRi(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

UTSA CS 3743 - Logical Database Design

Download Logical Database Design
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logical Database Design and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logical Database Design 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?