DOC PREVIEW
UW CSE 444 - E/R diagrams and BCNF

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UW CSE 444 - E/R diagrams and BCNF

Documents in this Course
XML

XML

48 pages

SQL

SQL

25 pages

SQL

SQL

42 pages

Recovery

Recovery

30 pages

SQL

SQL

36 pages

Indexes

Indexes

35 pages

Security

Security

36 pages

Wrap-up

Wrap-up

6 pages

SQL

SQL

37 pages

More SQL

More SQL

48 pages

SQL

SQL

35 pages

XML

XML

46 pages

Triggers

Triggers

26 pages

Load more
Download E/R diagrams and BCNF
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 E/R diagrams and BCNF 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 E/R diagrams and BCNF 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?