Recap of Feb 13: SQL, Relational Calculi, Functional Dependencies• SQL: multiple group bys, having, lots of examples• Tuple Calculus• Domain Calculus• Functional Dependencies– F+ = the closure of the set of FDs on a given relationRelational Database Design• A major goal in designing a database is to have a schema that– makes queries simpler (easy to phrase)– avoids redundancies and update anomalies (about which more later)Schema and Query Simplicity (1)Example Schema 1: EMP(eno, ename, sal, dno)DEPT(dno, dname, floor, mgr)Query 1: find all employees that make more than their managerselect e.ename from EMP e, EMP m, DEPT dwhere e.dno = m.dno and d.mgr=m.eno and e.sal>m.salQuery 2: for each department, find the maximum salaryselect d.dname, max(e.sal) from EMP e, DEPT dwhere e.dno = d.dno group by d.dnoQ1 requires two joins; Q2 requires a join and a group-by.Schema and Query Simplicity (2)Example Schema 2: (a single relation)ED(eno, ename, sal, dno, dname, floor, mgr)Query 1: find all employees that make more than their managerselect e.ename from ED e, ED mwhere e.mgr=m.eno and e.sal>m.salQuery 2: for each department, find the maximum salaryselect d.dname, max(sal) from ED egroup by dnoQ1 requires one join; Q2 requires just a group-by.Schema and Query Simplicity (3)• How did we get simpler queries?• Schema 2 was a more complicated relation with more information; in essence ED was EMP and DEPT from Schema 1 with the join pre-computed• Should we just precompute the joins and store bigger relations?• Taken to the extreme, we could compute the universal relation with all attributes inside it and null values for those values that make no sense• Why wouldn’t we want to do that?• Problems with too-complex relations: repetition of information (data redundancy) and inability to represent certain information (update anomalies)DB Design: Redundancy and Anomalies• Redundancy (repetition of information)– each department is repeated for each employee in it– great risk of inconsistencies -- suppose the department is moved to a new floor?– A simple update (change in mgr name, department floor, etc) in Schema 1 becomes multiple updates in Schema 2• Anomalies (inability to represent some types of information)– departments can’t exist without employees. A department cannot exist until the first employee is inserted, and it can no longer exist when the last employee is deleted from the ED relationDB Design: Dealing with Anomalies• So complex relations make for simpler queries, but have the disadvantages of data redundancy and creation of anomalies. How do we balance the two objectives? We want:– simple queries– no anomalies; minimize data redundancy• If we start with Schema 2 and discover anomalies we can decompose the relation(s) until the problems go away. This process is called normalization.Objectives of DB Design (Normalization)• no redundancy– for space efficiency and to reduce the potential for inconsistencies• update integrity– avoid update anomalies• linguistic efficiency– simpler queries are much better for the application programmer and for the query optimizer• good performance– smaller relations imply more joins (bad)Lossy Decompositions• Not all decompositions are reversible (lossless)Example:Shipment(S#, P#, J#) decomposed into SP(S#, P#) and SJ(S#, J#)s1 p1 j1 s1 p1 s1 j1s2 p2 j1 s2 p2 s2 j1s2 p3 j2 s2 p3 s2 j2s3 p3 j3 s3 p3 s3 j3s4 p4 j3 s4 p4 s4 j3Lossy DecompositionsShipment(S#, P#, J#) decomposed into SP(S#, P#) and SJ(P#, J#)s1 p1 j1 s1 p1 p1 j1s2 p2 j1 s2 p2 p2 j1s2 p3 j2 s2 p3 p3 j2s3 p3 j3 s3 p3 p3 j3s4 p4 j3 s4 p4 p4 j3If we join SP and SJ again into SP-PJ(S#, P#, P#, J#) we get:s1 p1 p1 j1s2 p2 p2 j1s2 p3 p3 j2 from the joined tuples we cannots2 p3 p3 j3 deduce the original form of the data.s3 p3 p3 j2 this is called the connection traps3 p3 p3 j3 and the decomposition is lossys4 p4 p4 j3Example of Lossy Join Decomposition• Lossy-join decompositions result in information loss• Example: decomposition of R=(A,B) into R1=(A) and R2=(B) R=(A, B) R1= (A) R2= (B) ? 1 ? 1? 2 ? 2? 1R1 X R2 = (A, B)? 1? 2? 1? 2Decomposition Continued• Decompose the relation schema• All attributes of an original schema (R) must appear in the decomposition (R1, R2) • Lossless (reversible) join decomposition: for all possible relations r on schema R, the decomposition into (R1, R2) is lossless ifr = ?R1(r) ?R2(r)• The decomposition of R into R1and R2 is lossless if and only if at least one of the following dependencies is in F+:R1? R2 ? R1 R1? R2 ? R2Lossless Join Decomposition and Functional Dependencies• So FDs can help determine whether a decomposition is lossless• R is a relation schema and F its FDs. Then a decompositionR = R1? R2is lossless if at least one of the following dependencies holdsR1? R2 ? R1 R1? R2 ? R2 • either of the above FDs guarantees uniqueness in the mapping (and therefore that the decomposition is lossless)Dependency Preservation• Dependencies are preserved in a decomposition if we do not need to join in order to enforce FDs -- all FDs remain intra-relational and do not become inter-relational• To check if a decomposition is dependency preserving, we need to examine all FDs in F+• There is an algorithm for testing dependency preservation (requires the computation of F+)Goals of Normalization• Decide whether a particular relation R is in “good” form• if it is not in “good” form, decompose it into a set of relations (R1, R2, R3, …, Rn) such that:– each relation is in “good” form– the decomposition is a lossless-join decomposition, based upon functional dependenciesNormalization• Types of FDs in R(A, B, C, D) with (A, B) a candidate key:– trivial: AB ==> A– partial: A ==> C (C depends upon a part of the key)TEACH(student, teacher, subject)student, subject ==> teacher (students not allowed in the same subjectof two different teachers)teacher ==> subject (each teacher teaches only one subject)– transitive: A ==> C ==> DED(eno, ename, sal, dno, dname, floor, mgr)eno ==> dno ==> mgrNormalization using FDs• When we decompose a relation schema R with a set of functional dependencies F into R1, R2, R3, …, Rnwe want:– lossless-join decomposition: otherwise the decomposition results in loss of information relative to the original schema R– no redundancy: the relations Rishould be in either BCNF (Boys-Codd Normal Form) or 3NF (Third Normal Form)
View Full Document
Unlocking...