Chapter 8:Relational Database Design Features of Good Relational Design Atomic Domains and First Normal Form Decomposition Using Functional Dependencies Functional Dependency Theory Algorithms for Functional Dependencies Decomposition Using Multivalued Dependencies More Normal Form Database-Design Process Modeling Temporal Data Database System Concepts-6th Edition 8.2 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.2 ©Silberschatz, Korth and Sudarshan th Edition Chapter 8: Relational Database Design Features of Good Relational Design Atomic Domains and First Normal Form Decomposition Using Functional Dependencies Functional Dependency Theory Algorithms for Functional Dependencies Decomposition Using Multivalued Dependencies More Normal Form Database-Design Process Modeling Temporal Data
Combine Schemas? Suppose we combine instructor and department into inst_dept (No connection to relationship set inst_dept) Result is possible repetition of information 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 Database System Concepts-6th Edition 8.3 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.3 ©Silberschatz, Korth and Sudarshan th Edition Combine Schemas? Suppose we combine instructor and department into inst_dept (No connection to relationship set inst_dept) Result is possible repetition of information
A Combined Schema Without Repetition Consider combining relations sec_class(sec id,building,room number)and section(course_id,sec_id,semester,year) into one relation section(course_id,sec_id,semester,year, building,room_number) No repetition in this case Database System Concepts-6th Edition 8.4 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.4 ©Silberschatz, Korth and Sudarshan th Edition A Combined Schema Without Repetition Consider combining relations sec_class(sec_id, building, room_number) and section(course_id, sec_id, semester, year) into one relation section(course_id, sec_id, semester, year, building, room_number) No repetition in this case
What About Smaller Schemas? Suppose we had started with inst_dept.How would we know to split up (decompose)it into instructor and department? Write a rule"if there were a schema(dept_name,building,budget),then dept_name would be a candidate key" Denote as a functional dependency: dept_name->building,budget In inst_dept,because dept_name is not a candidate key,the building and budget of a department may have to be repeated. This indicates the need to decompose inst_dept Not all decompositions are good.Suppose we decompose employee(ID,name,street,city,salary)into employee1 (ID,name) employee2(name,street,city,salary) 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-6th Edition 8.5 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.5 ©Silberschatz, Korth and Sudarshan th Edition What About Smaller Schemas? Suppose we had started with inst_dept. How would we know to split up (decompose) it into instructor and department? Write a rule “if there were a schema (dept_name, building, budget), then dept_name would be a candidate key” Denote as a functional dependency: dept_name → building, budget In inst_dept, because dept_name is not a candidate key, the building and budget of a department may have to be repeated. This indicates the need to decompose inst_dept Not all decompositions are good. Suppose we decompose employee(ID, name, street, city, salary) into employee1 (ID, name) employee2 (name, street, city, salary) 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 name street city salary 57766 Kim Main Perryridge 75000 98776 Kim North Hampton 67000 employee ID name name street city salary 57766 Kim Kim Main Perryridge 75000 98776 Kim Kim North Hampton 67000 natural join ID mame 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-6th Edition 8.6 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.6 ©Silberschatz, Korth and Sudarshan th Edition A Lossy Decomposition
Example of Lossless-Join Decomposition Lossless join decomposition Decomposition of R=(A,B,C) R1=(A,B) R2=(B,C) A B C AB B C A a 1 A B B B 2 12 B r ΠAB() ΠB.c0 C ΠA()凶ΠB(r) A B 1 A B B Database System Concepts-6th Edition 8.7 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.7 ©Silberschatz, Korth and Sudarshan th Edition Example of Lossless-Join Decomposition Lossless join decomposition Decomposition of R = (A, B, C) R1 = (A, B) R2 = (B, C) A B 1 2 A B 1 2 r B,C(r) A (r) B (r) A B 1 2 C A B B 1 2 C A B C A B A,B(r)
First Normal Form Domain is atomic if its elements are considered to be indivisible units Examples of non-atomic domains: Set of names,composite attributes Identification numbers like CS101 that can be broken up into parts A relational schema R is in first normal form if the domains of all attributes of R are atomic Non-atomic values complicate storage and encourage redundant (repeated)storage of data Example:Set of accounts stored with each customer,and set of owners stored with each account We assume all relations are in first normal form (and revisit this in Chapter 22:Object Based Databases) Database System Concepts-6th Edition 8.8 ©Silberschat乜,Korth and Sudarshan
Database System Concepts - 6 8.8 ©Silberschatz, Korth and Sudarshan th Edition First Normal Form Domain is atomic if its elements are considered to be indivisible units Examples of non-atomic domains: Set of names, composite attributes Identification numbers like CS101 that can be broken up into parts A relational schema R is in first normal form if the domains of all attributes of R are atomic Non-atomic values complicate storage and encourage redundant (repeated) storage of data Example: Set of accounts stored with each customer, and set of owners stored with each account We assume all relations are in first normal form (and revisit this in Chapter 22: Object Based Databases)
First Normal Form(Cont'd) Atomicity is actually a property of how the elements of the domain are used. Example:Strings would normally be considered indivisible Suppose that students are given roll numbers which are strings of the form CS0012 or EE1127 If the first two characters are extracted to find the department,the domain of roll numbers is not atomic. Doing so is a bad idea:leads to encoding of information in application program rather than in the database. Database System Concepts-6th Edition 8.9 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.9 ©Silberschatz, Korth and Sudarshan th Edition First Normal Form (Cont’d) Atomicity is actually a property of how the elements of the domain are used. Example: Strings would normally be considered indivisible Suppose that students are given roll numbers which are strings of the form CS0012 or EE1127 If the first two characters are extracted to find the department, the domain of roll numbers is not atomic. Doing so is a bad idea: leads to encoding of information in application program rather than in the database
Goal-Devise a Theory for the Following 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 a set of relations {R1,R2,...R}such that each relation is in good form the decomposition is a lossless-join decomposition Our theory is based on: functional dependencies multivalued dependencies Database System Concepts-6th Edition 8.10 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.10 ©Silberschatz, Korth and Sudarshan th Edition Goal — Devise a Theory for the Following 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 a set of relations {R1 , R2 , ..., Rn } such that each relation is in good form the decomposition is a lossless-join decomposition Our theory is based on: functional dependencies multivalued dependencies
Functional Dependencies 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-6th Edition 8.11 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.11 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies 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