Chapter 7: Relational Database DesignSlide 2The Banking SchemaCombine Schemas?A Combined Schema Without RepetitionWhat About Smaller Schemas?A Lossy DecompositionFirst Normal FormFirst Normal Form (Cont’d)Goal — Devise a Theory for the FollowingFunctional DependenciesFunctional Dependencies (Cont.)Slide 13Use of Functional DependenciesSlide 15Closure of a Set of Functional DependenciesBoyce-Codd Normal FormDecomposing a Schema into BCNFBCNF and Dependency PreservationFigure 7.6Figure 7.7Third Normal FormGoals of NormalizationHow good is BCNF?How good is BCNF? (Cont.)Slide 26Functional-Dependency TheorySlide 28ExampleProcedure for Computing F+Closure of Functional Dependencies (Cont.)Closure of Attribute SetsExample of Attribute Set ClosureUses of Attribute ClosureCanonical CoverExtraneous AttributesTesting if an Attribute is ExtraneousSlide 38Computing a Canonical CoverLossless-join DecompositionSlide 41Dependency PreservationTesting for Dependency PreservationSlide 44Testing for BCNFTesting Decomposition for BCNFBCNF Decomposition AlgorithmExample of BCNF DecompositionSlide 49Slide 50Third Normal Form: Motivation3NF ExampleRedundancy in 3NFTesting for 3NF3NF Decomposition Algorithm3NF Decomposition Algorithm (Cont.)3NF Decomposition: An Example3NF Decompsition Example (Cont.)Comparison of BCNF and 3NFDesign GoalsMultivalued Dependencies (MVDs)MVD (Cont.)Slide 63Example (Cont.)Use of Multivalued DependenciesTheory of MVDsFourth Normal FormRestriction of Multivalued Dependencies4NF Decomposition AlgorithmSlide 70Further Normal FormsOverall Database Design ProcessER Model and NormalizationDenormalization for PerformanceOther Design IssuesModeling Temporal DataModeling Temporal Data (Cont.)End of ChapterProof of Correctness of 3NF Decomposition AlgorithmCorrectness of 3NF Decomposition AlgorithmCorrectness of 3NF Decomposition Algorithm (Cont’d.)Correctness of 3NF Decomposition (Cont’d.)Slide 83Figure 7.5: Sample Relation rFigure 7.15: An Example of Redundancy in a BCNF RelationFigure 7.16: An Illegal R2 RelationFigure 7.18: Relation of Practice Exercise 7.2Database System Concepts, 5th Ed.©Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use Chapter 7: Relational Database DesignChapter 7: Relational Database Design©Silberschatz, Korth and Sudarshan7.2Database System Concepts - 5th Edition, Oct 5, 2006Chapter 7: Relational Database DesignChapter 7: 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©Silberschatz, Korth and Sudarshan7.3Database System Concepts - 5th Edition, Oct 5, 2006The Banking SchemaThe Banking Schemabranch = (branch_name, branch_city, assets)customer = (customer_id, customer_name, customer_street, customer_city)loan = (loan_number, amount)account = (account_number, balance)employee = (employee_id. employee_name, telephone_number, start_date)dependent_name = (employee_id, dname)account_branch = (account_number, branch_name)loan_branch = (loan_number, branch_name)borrower = (customer_id, loan_number)depositor = (customer_id, account_number)cust_banker = (customer_id, employee_id, type)works_for = (worker_employee_id, manager_employee_id)payment = (loan_number, payment_number, payment_date, payment_amount)savings_account = (account_number, interest_rate)checking_account = (account_number, overdraft_amount)©Silberschatz, Korth and Sudarshan7.4Database System Concepts - 5th Edition, Oct 5, 2006Combine Schemas?Combine Schemas?Suppose we combine borrower and loan to get bor_loan = (customer_id, loan_number, amount )Result is possible repetition of information (L-100 in example below)©Silberschatz, Korth and Sudarshan7.5Database System Concepts - 5th Edition, Oct 5, 2006A Combined Schema Without RepetitionA Combined Schema Without RepetitionConsider combining loan_branch and loanloan_amt_br = (loan_number, amount, branch_name)No repetition (as suggested by example below)©Silberschatz, Korth and Sudarshan7.6Database System Concepts - 5th Edition, Oct 5, 2006What About Smaller Schemas?What About Smaller Schemas?Suppose we had started with bor_loan. How would we know to split up (decompose) it into borrower and loan?Write a rule “if there were a schema (loan_number, amount), then loan_number would be a candidate key”Denote as a functional dependency: loan_number  amountIn bor_loan, because loan_number is not a candidate key, the amount of a loan may have to be repeated. This indicates the need to decompose bor_loan.Not all decompositions are good. Suppose we decompose employee intoemployee1 = (employee_id, employee_name)employee2 = (employee_name, telephone_number, start_date)The next slide shows how we lose information -- we cannot reconstruct the original employee relation -- and so, this is a lossy decomposition.©Silberschatz, Korth and Sudarshan7.7Database System Concepts - 5th Edition, Oct 5, 2006A Lossy DecompositionA Lossy Decomposition©Silberschatz, Korth and Sudarshan7.8Database System Concepts - 5th Edition, Oct 5, 2006First Normal FormFirst 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 9)©Silberschatz, Korth and Sudarshan7.9Database System Concepts - 5th Edition, Oct 5, 2006First Normal Form (Cont’d)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