Outline Features of Good Relational Design Functional Dependencies Decomposition Using Functional Dependencies ■Normal Forms Functional Dependency Theory Algorithms for Decomposition using Functional Dependencies Decomposition Using Multivalued Dependencies ■More Normal Form Atomic Domains and First Normal Form Database-Design Process Modeling Temporal Data Database System Concepts-7th Edition 7.2 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.2 ©Silberschatz, Korth and Sudarshan th Edition Outline ▪ Features of Good Relational Design ▪ Functional Dependencies ▪ Decomposition Using Functional Dependencies ▪ Normal Forms ▪ Functional Dependency Theory ▪ Algorithms for Decomposition using Functional Dependencies ▪ Decomposition Using Multivalued Dependencies ▪ More Normal Form ▪ Atomic Domains and First Normal Form ▪ Database-Design Process ▪ Modeling Temporal Data
Features of Good Relational Designs Suppose we combine instructorand department into in_dep,which represents the natural join on the relations instructor and department ID name salary dept name building budget 22222 Einstein 95000 Physics Watson 70000 12121 Wu 90000 Finance Painter 120000 32343 El Said 60000 History Painter 50000 45565 Katz 75000 Comp.Sci. Taylor 100000 98345 Kim 80000 Elec.Eng. Taylor 85000 76766 Crick 72000 Biology Watson 90000 10101 Srinivasan 65000 Comp.Sci. Taylor 100000 58583 Califieri 62000 History Painter 50000 83821 Brandt 92000 Comp.Sci. Taylor 100000 15151 Mozart 40000 Music Packard 80000 33456 Gold 87000 Physics Watson 70000 76543 Singh 80000 Finance Painter 120000 There is repetition of information Need to use null values(if we add a new department with no instructors) Database System Concepts-7th Edition 7.4 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 7.4 ©Silberschatz, Korth and Sudarshan th Edition Features of Good Relational Designs ▪ Suppose we combine instructor and department into in_dep, which represents the natural join on the relations instructor and department ▪ There is repetition of information ▪ Need to use null values (if we add a new department with no instructors)
Decomposition The only way to avoid the repetition-of-information problem in the in_dep schema is to decompose it into two schemas-instructor and department schemas. Not all decompositions are good.Suppose we decompose employee(ID,name,street,city,salary) into employee1 (ID,name) employee2(name,street,city,salary) The problem arises when we have two employees with the same name The next slide shows how we lose information--we cannot reconstruct the original employee relation--and so,this is a lossy decomposition. Database System Concepts-7th Edition 7.6 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.6 ©Silberschatz, Korth and Sudarshan th Edition Decomposition ▪ The only way to avoid the repetition-of-information problem in the in_dep schema is to decompose it into two schemas – instructor and department schemas. ▪ Not all decompositions are good. Suppose we decompose employee(ID, name, street, city, salary) into employee1 (ID, name) employee2 (name, street, city, salary) The problem arises when we have two employees with the same name ▪ The next slide shows how we lose information -- we cannot reconstruct the original employee relation -- and so, this is a lossy decomposition
A Lossy Decomposition ID 1a11e street city salary 57766 Kim Main Perryridge 75000 98776 Kim North Hampton 67000 employee ID 1a11e name street city salary 57766 Kim Kim Main Perryridge 75000 98776 Kim Kim North Hampton 67000 natural join ID name street city salary 57766 Kim Main Perryridge 75000 57766 Kim North Hampton 67000 98776 Kim Main Perryridge 75000 98776 Kim North Hampton 67000 Database System Concepts-7th Edition 7.7 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 7.7 ©Silberschatz, Korth and Sudarshan th Edition A Lossy Decomposition
Lossless Decomposition Let R be a relation schema and let R;and R2form a decomposition of R. That is R=R,UR2 ■ We say that the decomposition is a lossless decomposition if there is no loss of information by replacing R with the two relation schemas R, UR2 ■Formally, ΠR1(r)凶ΠR2(C)=r And,conversely a decomposition is lossy if rCΠR1(C)凶ΠR2()=r Database System Concepts-7th Edition 7.8 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.8 ©Silberschatz, Korth and Sudarshan th Edition Lossless Decomposition ▪ Let R be a relation schema and let R1 and R2 form a decomposition of R . That is R = R1 U R2 ▪ We say that the decomposition is a lossless decomposition if there is no loss of information by replacing R with the two relation schemas R1 U R2 ▪ Formally, R1 (r) R2 (r) = r ▪ And, conversely a decomposition is lossy if r R1 (r) R2 (r) = r
Example of Lossless Decomposition Decomposition of R=(A,B,C) R1=(A,B) R2=(B,C) AB AB B C a 1 A 1 1 A 2 B B 2 2 B r Πa.B(r) Π8.c) AB C ΠA()凶ΠB(r) 1 2 B Database System Concepts-7th Edition 7.9 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 7.9 ©Silberschatz, Korth and Sudarshan th Edition Example of Lossless Decomposition ▪ Decomposition of R = (A, B, C) R1 = (A, B) R2 = (B, C)
Normalization Theory Decide whether a particular relation R is in "good"form. In the case that a relation R is not in "good"form,decompose it into set of relations {R1,R2,...R}such that Each relation is in good form The decomposition is a lossless decomposition Our theory is based on: Functional dependencies Multivalued dependencies Database System Concepts-7th Edition 7.10 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.10 ©Silberschatz, Korth and Sudarshan th Edition Normalization Theory ▪ Decide whether a particular relation R is in “good” form. ▪ In the case that a relation R is not in “good” form, decompose it into set of relations {R1 , R2 , ..., Rn } such that • Each relation is in good form • The decomposition is a lossless decomposition ▪ Our theory is based on: • Functional dependencies • Multivalued dependencies
Functional Dependencies There are usually a variety of constraints(rules)on the data in the real world. For example,some of the constraints that are expected to hold in a university database are: Students and instructors are uniquely identified by their ID. Each student and instructor has only one name. Each instructor and student is(primarily)associated with only one department. Each department has only one value for its budget,and only one associated building. Database System Concepts-7th Edition 7.11 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.11 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies ▪ There are usually a variety of constraints (rules) on the data in the real world. ▪ For example, some of the constraints that are expected to hold in a university database are: • Students and instructors are uniquely identified by their ID. • Each student and instructor has only one name. • Each instructor and student is (primarily) associated with only one department. • Each department has only one value for its budget, and only one associated building
Functional Dependencies (Cont.) An instance of a relation that satisfies all such real-world constraints is called a legal instance of the relation; A legal instance of a database is one where all the relation instances are legal instances Constraints on the set of legal relations. Require that the value for a certain set of attributes determines uniquely the value for another set of attributes. A functional dependency is a generalization of the notion of a key. Database System Concepts-7th Edition 7.12 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.12 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies (Cont.) ▪ An instance of a relation that satisfies all such real-world constraints is called a legal instance of the relation; ▪ A legal instance of a database is one where all the relation instances are legal instances ▪ Constraints on the set of legal relations. ▪ Require that the value for a certain set of attributes determines uniquely the value for another set of attributes. ▪ A functional dependency is a generalization of the notion of a key
Functional Dependencies Definition Let R be a relation schema aR and BCR The functional dependency 0→B holds on R if and only if for any legal relations r(R),whenever any two tuples f and t,of ragree on the attributes a,they also agree on the attributes B.That is, tila]=t2 [a]tlB]=t2[B] Example:Consider r(A,B)with the following instance of r. 4 1 5 37 ■On this instance,B>A hold;A→B does NOT hold, Database System Concepts-7th Edition 7.13 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.13 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies Definition ▪ Let R be a relation schema R and R ▪ The functional dependency → holds on R if and only if for any legal relations r(R), whenever any two tuples t1 and t2 of r agree on the attributes , they also agree on the attributes . That is, t1 [] = t2 [] t1 [ ] = t2 [ ] ▪ Example: Consider r(A,B ) with the following instance of r. ▪ On this instance, B → A hold; A → B does NOT hold, 1 4 1 5 3 7