Database design: E/R diagrams and BCNF CSE 444 section October 14, 2010 1 Michael Ratanapintha - CSE 444, Fall 2010Today • Database design with E/R diagrams • Functional dependencies • Boyce-Codd normal form (BCNF) 2 Michael Ratanapintha - CSE 444, Fall 2010From English to an E/R diagram • Professors have SSN, age, rank, and specialty • Projects have IDs, sponsors, budgets, start and end dates Professor rank Specialty age ssn Project pid end-date sponsor start-date budget 3 Example from: R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd ed. Michael Ratanapintha - CSE 444, Fall 2010From English to an E/R diagram • Each project is managed by one professor (principal investigator) • A professor can manage multiple projects Professor rank Specialty age ssn Project pid end-date sponsor start-date budget 4 Example from: R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd ed. Michael Ratanapintha - CSE 444, Fall 2010 ManagesFrom English to an E/R diagram • Each project is worked on by one or more professors • Professors can work on multiple projects Professor rank Specialty age ssn Project pid end-date sponsor start-date budget 5 Example from: R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd ed. Michael Ratanapintha - CSE 444, Fall 2010 Manages Work-onFrom E/R diagram to relations Professor Project rank Specialty age ssn pid end_date sponsor start-date budget Manages Work-on • Professor (ssn, age, rank, specialty) • Project (pid, sponsor, start_date, end_date, budget) • Work_on (ssn, pid) • Manages (ssn, pid) 6 Example from: R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd ed. Michael Ratanapintha - CSE 444, Fall 2010Integrating the many-one relation Professor Project rank Specialty age ssn pid end_date sponsor start-date budget Manages Work-on • Professor (ssn, age, rank, specialty) • Project (pid, sponsor, start_date, end_date, budget, ssn) • Work_on (ssn, pid) 7 Example from: R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd ed. Michael Ratanapintha - CSE 444, Fall 2010SQL code for this database Professor Project rank Specialty age ssn pid end_date sponsor start-date budget Manages Work-on CREATE TABLE Professor ( ssn INT PRIMARY KEY, age INT, urank VARCHAR(30), specialty VARCHAR(30) ); CREATE TABLE Project ( pid INT PRIMARY KEY, sponser INT, start_date DATE, end_date DATE, budget FLOAT, ssn INT REFERENCES Professor(ssn) ); CREATE TABLE Work_on ( ssn INT REFERENCES Professor(ssn), pid INT REFERENCES Project(pid), PRIMARY KEY (ssn, pid) ); • Professor(ssn, age, rank, specialty) • Project(pid, sponsor, start_date, end_date, budget, ssn) • Work_in(ssn, pid) 8 Example from: R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd ed. Michael Ratanapintha - CSE 444, Fall 2010Today • Database design with E/R diagrams • Functional dependencies • Boyce-Codd normal form (BCNF) 9 Michael Ratanapintha - CSE 444, Fall 2010Garcia-Molina, problem 3.3.2 (i) Consider a relation S(A,B,C,D) with FDs A → B, B → C, and B → D. a. Give the nontrivial FDs that follow from the given FDs. Restrict to 1 attr on right side. b. What are all the keys of S? c. What are the superkeys that aren’t keys? 10 Michael Ratanapintha - CSE 444, Fall 2010Garcia-Molina, problem 3.3.2 (ii) Consider a relation T(A,B,C,D) with FDs AB → C, BC → D, CD → A, and AD → B. a. Give the nontrivial FDs that follow from the given FDs. Restrict to 1 attr on right side. b. What are all the keys of S? c. What are the superkeys that aren’t keys? 11 Michael Ratanapintha - CSE 444, Fall 2010Today • Database design with E/R diagrams • Functional dependencies • Boyce-Codd normal form (BCNF) 12 Michael Ratanapintha - CSE 444, Fall 2010What is BCNF? A relation R is in BCNF iff: If A1,… An → B is a non-trivial dependency in R, then {A1, …, An} is a superkey for R 13 Michael Ratanapintha - CSE 444, Fall 2010Why do BCNF decompositions? 14 Michael Ratanapintha - CSE 444, Fall 201015 BCNF decomposition algorithm BCNF_Decompose(R) find X s.t.: X ≠X+ ≠ [all attributes] if (not found) then “R is in BCNF” let Y = X+ - X let Z = [all attributes] - X+ decompose R into R1(X Y) and R2(X Z) continue to decompose recursively R1 and R2 Michael Ratanapintha - CSE 444, Fall 2010Consider the following FDs: • CD → E • D → B • A → CD BCNF example: table R(A, B, C, D, E) Which ones are the bad dependencies? CD is not a superkey D is not a superkey A is a superkey CD+ = BCDE D+ = BD A+ = ABCDE BAD BAD 16 Michael Ratanapintha - CSE 444, Fall 2010Consider the following FDs: • CD → E • D → B • A → CD BCNF example: table R(A, B, C, D, E) R3(A,C,D) [BCNF] R5(C,D,E) [BCNF] R2(B,C,D,E) [D+ = BD ≠ BCDE] BAD BAD R(A,B,C,D,E) [CD+ = BCDE ≠ ABCDE] R4(B,D) [BCNF] 17 Michael Ratanapintha - CSE 444, Fall 20102 more BCNF decompositions S(A, B, C, D) C → D, C → A, B → C T(A, B, C, D, E) AB → C, DE → C, B → D Michael Ratanapintha - CSE 444, Fall 2010 18Consider the following FDs: • C → D, C+ = ACD • C → A, C+ = ACD • B → C, B+ = ABCD S(A,B,C,D) solution S3(B,C) [BCNF] S2(A,C,D) [BCNF] BAD BAD S(A,B,C,D) [C+ = ACD ≠ ABCD] 19 Michael Ratanapintha - CSE 444, Fall 2010Consider the following FDs: • AB → C, AB+ = ABCD • DE → C , DE+ = CDE • B → D, B+ = BD T(A,B,C,D,E) 1st solution T3(A,B,E) [BCNF] T5(A,B,C) [BCNF] T2(A,B,C,D) [B+ = BD ≠ ABCD] BAD BAD T(A,B,C,D,E) [AB+ = ABCD ≠ ABCDE] T4(B,D) [BCNF] BAD 20 Michael Ratanapintha - CSE 444, Fall 2010Consider the following FDs: • AB → C, AB+ = ABCD • DE → C , DE+ = CDE • B → D, B+ = BD T(A,B,C,D,E) 2nd solution T3(C,D,E) [BCNF] T5(A,B,E) [BCNF] T2(A,B,D,E) [B+ = BD ≠ ABDE] BAD BAD T(A,B,C,D,E) [DE+ = CDE ≠ ABCDE] T4(B,D) [BCNF] BAD 21 Michael Ratanapintha - CSE 444, Fall 2010Consider the following FDs: • AB → C, AB+ = ABCD • DE → C , DE+ = CDE • B → D, B+ = BD T(A,B,C,D,E) 3rd solution T3(B,D) [BCNF] T5(A,B,E) [BCNF] T2(A,B,C,E) [AB+ = ABC ≠ ABCE] BAD BAD T(A,B,C,D,E) [B+ = BD ≠ ABCDE] T4(A,B,C) [BCNF] BAD 22 Michael Ratanapintha - CSE 444, Fall
View Full Document