Tham khảo tài liệu 'database systems - part 12', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | COP 4710: Database Systems Spring 2004 Introduction to Normalization – Part 3 BÀI 12, 1/2 ngày School of Electrical Engineering and Computer Science University of Central Florida Instructor : Mark Llewellyn markl@ CC1 211, 823-2790 Phd, MS, Under Algorithm #1 for Producing a 3NF Decomposition Algorithm // input: a relation schema R= (A1, A2, , An), a set of fds F, a set of candidate keys K. // output: a 3NF decomposition of R, called D, which has the lossless join property and the // functional dependencies are preserved. (R, F, K) a = 0; for each fd X Y in F do a = a +1; Ra = XY; endfor if [none of the schemes Rb (1 b a) contains a candidate key of R] then a = a + 1; Ra = any candidate key of R endif if [ ] then //there are missing attributes Ra+1 = return D = {R1, R2, ., Ra+1} end. Let R = (A, B, C, D, E) K = {AB, AC} F = {AB CDE, AC BDE, B C, C B, C D, B E} Step 1: D = {(ABCDE), (ACBDE), (BC), (CB), (CD), | COP 4710: Database Systems Spring 2004 Introduction to Normalization – Part 3 BÀI 12, 1/2 ngày School of Electrical Engineering and Computer Science University of Central Florida Instructor : Mark Llewellyn markl@ CC1 211, 823-2790 Phd, MS, Under Algorithm #1 for Producing a 3NF Decomposition Algorithm // input: a relation schema R= (A1, A2, , An), a set of fds F, a set of candidate keys K. // output: a 3NF decomposition of R, called D, which has the lossless join property and the // functional dependencies are preserved. (R, F, K) a = 0; for each fd X Y in F do a = a +1; Ra = XY; endfor if [none of the schemes Rb (1 b a) contains a candidate key of R] then a = a + 1; Ra = any candidate key of R endif if [ ] then //there are missing attributes Ra+1 = return D = {R1, R2, ., Ra+1} end. Let R = (A, B, C, D, E) K = {AB, AC} F = {AB CDE, AC BDE, B C, C B, C D, B E} Step 1: D = {(ABCDE), (ACBDE), (BC), (CB), (CD), (BE)} Reduce to: D = {(ABCDE), (BC), (CD), (BE)} Step 2: Does D contain a candidate key for R? Yes, in (ABCDE) Step 3: Are all the attributes of R contained in D? Yes. Return D as: {(ABCDE), (BC), (CD), (BE)} Example – Using Algorithm Algorithm #2 for Producing a 3NF Decomposition Algorithm // input: a relation schema R= (A1, A2, , An), a set of fds F, a set of candidate keys K. // output: a 3NF decomposition of R, called D, which is not guaranteed to have either the // lossless join property or to preserve the functional dependencies in F. // This algorithm is based on the removal of transitive dependencies. (R, F, K) do if [K Y A where A is non-prime and not an element of either K or Y] then decompose R into: R1 = {R – A} with K1 = {K} and R2 = {YA} with K2 = {Y}. repeat until no transitive dependencies exist in any schema D = union of all 3NF schemas produced above. test for lossless join test for preservation of the functional dependencies end. Let R = (A, B,
