1、M.P. Johnson, DBMS, Stern/NYU, Spring 2008,1,C20.0046: Database Management Systems Lecture #5,M.P. Johnson Stern School of Business, NYU Spring, 2008,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,2,Agenda,Last time: FDs This time: Anomalies Normalization: BCNF & 3NF Next time: SQL,M.P. Johnson, DBMS, S
2、tern/NYU, Spring 2008,3,Review: FDs,Definition:Notation: Read as: Ai functionally determines Bj,If two tuples agree on the attributes,A1, A2, , An,A1, A2, , An B1, B2, , Bm,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,4,Review: Combining FDs,If some FDs are satisfied, then others are satisfied too,If
3、all these FDs are true:,name color category department color, category price,Then this FD also holds:,name, category price,Why?,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,5,Problem: find all FDs,Given a relation instance and set of given FDs Find all FDs satisfied by that instanceUseful if we dont g
4、et enough information from our users: need to reverse engineer a data instanceQ: How long does this take? A: Some time for each subset of atts Q: How many subsets? powerset exponential time in worst-case But can often be smarter,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,6,Closure Algorithm,Start wi
5、th X=A1, , An.Repeat:if B1, , Bn C is a FD andB1, , Bn are all in Xthen add C to X.until X didnt change,name, category+ = name, category, color, department, price,name color category department color, category price,Example:,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,7,Closure alg e.g.,A, B C A, D B
6、 B D,Example:,Compute X+, for every set X (AB is shorthand for A,B):,A+ = A, B+ = BD, C+ = C, D+ = D AB+ = ABCD, AC+ = AC, AD+ = ABCD, BC+ = BC, BD+ = BD, CD+ = CD ABC+ = ABD+ = ACD+ = ABCD (no need to computewhy?) BCD+ = BCD, ABCD+ = ABCD,What are the keys?,M.P. Johnson, DBMS, Stern/NYU, Spring 200
7、8,8,Closure alg e.g.,Compute A,B+ X = A, B, Compute A, F+ X = A, F, ,R(A,B,C,D,E,F),A, B C A, D E B D A, F B,In class:,What are the keys?,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,9,Closure alg e.g.,Product(name, price, category, color) name, category price category colorFDs are: Keys are: name, ca
8、tegoryEnrollment(student, address, course, room, time) student address room, time course student, course room, timeFDs are: Keys are:,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,10,Next topic: Anomalies,Identify anomalies in existing schemataDecomposition by projectionBCNFLossy v. losslessThird Norma
9、l Form,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,11,Types of anomalies,Redundancy Repeat info unnecessarily in several tuplesUpdate anomalies: Change info in one tuple but not in anotherDeletion anomalies: Delete some values & lose other values tooInsert anomalies: Inserting row means having to ins
10、ert other, separate info / null-ing it out,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,12,Examples of anomalies,Redundancy: name, maddress Update anomaly: Bill moves Delete anom.: Bill doesnt pay bills, lose phones lose Bill! Insert anom: cant insert someone without a (non-null) phone Underlying caus
11、e: SSN-phone is many-many Effect: partial dependency ssn name, maddress, Whereas key = ssn,phone,SSN Name, Mailing-address,SSN Phone,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,13,Decomposition by projection,Soln: replace anomalous R with projections of R onto two subsets of attributes Projection: an
12、 operation in Relational Algebra Corresponds to SELECT command in SQLProjecting R onto attributes (A1,An) means removing all other attributes Result of projection is another relation Yields tuples whose fields are A1,An Resulting duplicates ignored,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,14,Proje
13、ction for decomposition,R1 = projection of R on A1, ., An, B1, ., Bm R2 = projection of R on A1, ., An, C1, ., Cp A1, ., An B1, ., Bm C1, ., Cp = all attributes R1 and R2 may (/not) be reassembled to produce original R,R(A1, ., An, B1, ., Bm, C1, ., Cp),M.P. Johnson, DBMS, Stern/NYU, Spring 2008,15,
14、Decomposition example,The anomalies are gone No more redundant data Easy to for Bill to move Okay for Bill to lose all phones,Break the relation into two:,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,16,Thus: high-level strategy,E/R Model:,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,17,Using FDs to pro
15、duce good schemas,Start with set of relations Define FDs (and keys) for them based on real world Transform your relations to “normal form” (normalize them) Do this using “decomposition”Intuitively, good design means No anomalies Can reconstruct all (and only the) original information,M.P. Johnson, D
16、BMS, Stern/NYU, Spring 2008,18,Decomposition terminology,Projection: eliminating certain atts from relation Decomposition: separating a relation into two by projection Join: (re)assembling two relations Whenever a row from R1 and a row from R2 have the same value for some atts A, join together to fo
17、rm a row of R3If exactly the original rows are reproduced by joining the relations, then the decomposition was lossless We join on the attributes R1 and R2 have in common (As) If it cant, the decomposition was lossy,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,19,A decomposition is lossless if we can
18、recover:R(A,B,C)R1(A,B) R2(A,C)R(A,B,C) should be the same as R(A,B,C),R is in general larger than R. Must ensure R = R,Decompose,Recover,Lossless Decompositions,Lossless Decompositions,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,20,Lossless decomposition,Sometimes the same set of data is reproduced:
19、(Word, 100) + (Word, WP) (Word, 100, WP) (Oracle, 1000) + (Oracle, DB) (Oracle, 1000, DB) (Access, 100) + (Access, DB) (Access, 100, DB),M.P. Johnson, DBMS, Stern/NYU, Spring 2008,21,Lossy decomposition,Sometimes its not:(Word, WP) + (100, WP) (Word, 100, WP) (Oracle, DB) + (1000, DB) (Oracle, 1000,
20、 DB) (Oracle, DB) + (100, DB) (Oracle, 100, DB) (Access, DB) + (1000, DB) (Access, 1000, DB) (Access, DB) + (100, DB) (Access, 100, DB),Whats wrong?,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,22,Ensuring lossless decomposition,Examples: name price, so first decomposition was lossless category name a
21、nd category price, and so second decomposition was lossy,R(A1, ., An, B1, ., Bm, C1, ., Cp),If A1, ., An B1, ., Bm or A1, ., An C1, ., Cp Then the decomposition is lossless,R1(A1, ., An, B1, ., Bm),R2(A1, ., An, C1, ., Cp),Note: dont need both,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,23,Quick loss
22、less/lossy example,At a glance: can we decompose into R1(Y,X), R2(Y,Z)? At a glance: can we decompose into R1(X,Y), R2(X,Z)?,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,24,Next topic: Normal Forms,First Normal Form = all attributes are atomic As opposed to set-valued Assumed all alongSecond Normal Fo
23、rm (2NF)Third Normal Form (3NF)Boyce Codd Normal Form (BCNF)Fourth Normal Form (4NF)Fifth Normal Form (5NF),M.P. Johnson, DBMS, Stern/NYU, Spring 2008,25,BCNF definition,A simple condition for removing anomalies from relations:I.e.: The left side must always contain a key I.e: If a set of attributes
24、 determines other attributes, it must determine all the attributesSlogan: “In every FD, the left side is a superkey.”,A relation R is in BCNF if:If As Bs is a non-trivial dependencyin R , then As is a superkey for R,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,26,BCNF decomposition algorithm,Repeat ch
25、oose A1, , Am B1, , Bn that violates the BNCF condition split R into R1(A1, , Am, B1, , Bn) and R2(A1, , Am, others) continue with both R1 and R2 Until no more violations,/Heuristic: choose Bs as large as possible,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,27,Boyce-Codd Normal Form,Name/phone exampl
26、e is not BCNF:ssn,phone is key FD: ssn name,mailing-address holds Violates BCNF: ssn is not a superkey Its decomposition is BCNF Only superkeys anything else,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,28,Design/BCNF example,Consider situation: Entities: Emp(ssn,name,lot), Dept(id,name,budg) Relship:
27、 Works(E,D,since) Draw E/RNew rule: in each dept, everyone parks in same lot Translate to FD Normalize,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,29,BCNF Decomposition,Larger example: multiple decompositions Title, Year, Studio, President, Pres-Address FDs: Title Year Studio Studio President Preside
28、nt Pres-Address Studio President, Pres-Address No many-many this time Problem cause: transitive FDs: Title,year studio president,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,30,BCNF Decomposition,Illegal: As Bs, where As not a superkey Decompose: Studio President, Pres-Address As = studio Bs = preside
29、nt, pres-address Cs = title, year Result: Studios(studio, president, pres-address) Movies(studio, title, year) Is (2) in BCNF? Is in (1) BCNF? Key: Studio FD: President Pres-Address Q: Does president studio? If so, president is a key But if not, it violates BCNF,M.P. Johnson, DBMS, Stern/NYU, Spring
30、 2008,31,BCNF Decomposition,Studios(studio, president, pres-address) Illegal: As Bs, where As not a superkey Decompose: President Pres-Address As = president Bs = pres-address Cs = studio Studio, President, Pres-Address becomes President, Pres-Address Studio, President,M.P. Johnson, DBMS, Stern/NYU,
31、 Spring 2008,32,Decomposition algorithm example,R(N,O,R,P) F = N O, O R, R NKey: N,P Violations of BCNF: N O, OR, N ORPick N OR (on board) Can we rejoin? (on board) What happens if we pick N O instead? Can we rejoin? (on board),M.P. Johnson, DBMS, Stern/NYU, Spring 2008,33,An issue with BCNF,We coul
32、d lose FDsRelation: R(Title, Theater, Neighboorhood) FDs: Title,Nhood Theater Assume a movie shouldnt play twice in same nhood Theater Nhood Keys: Title, Nhood Theater, Title,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,34,Losing FDs,BCNF violation: Theater Nhood Decompose: Theater, NHood Theater, Tit
33、leResulting relations:,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,35,Losing FDs,Suppose we add new rows to R1 and R2:Neither R1 nor R2 enforces FD Title,Nhood Theater,R1,R2,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,36,Third normal form: motivation,Sometimes BCNF is not dependency-preserving, and Ef
34、ficient checking for FD violation on updates is importantIn these cases BCNF is too severe a req. “over-normalization”Solution: define a weaker normal form, 3NF FDs can be checked on individual relations without performing a join (no inter-relational FDs) relations can be converted, preserving both
35、data and FDs,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,37,BCNF lossiness,NB: BCNF decomp. is not data-lossy Results can be rejoined to obtain the exact originalBut: it can lose dependencies After decomp, now legal to add rows whose corresponding rows would be illegal in (rejoined) originalData-loss
36、y v. FD-lossy,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,38,Third Normal Form,Now define the (weaker) Third Normal Form Turns out: this example was already in 3NF,A relation R is in 3rd normal form if :For every nontrivial dependency A1, A2, ., An B for R, A1, A2, ., An is a super-key for R, or B is part of a key, i.e., B is prime,Tradeoff: BCNF = no FD anomalies, but may lose some FDs 3NF = keeps all FDs, but may have some anomalies,M.P. Johnson, DBMS, Stern/NYU, Spring 2008,39,Next week,For Monday: read ch.5.1-2 (SQL)Proj1 due next Monday,
