Appendix C:Advanced Relational Database Design Reasoning with MVDs Higher normal forms Join dependencies and PJNF DKNF Database System Concepts,5th Ed. c.1 @Silberschatz,Korth and Sudarshan
Database System Concepts, 5 C.1 ©Silberschatz, Korth and Sudarshan th Ed. Appendix C: Advanced Relational Database Design Reasoning with MVDs Higher normal forms Join dependencies and PJNF DKNF
Theory of Multivalued Dependencies Let D denote a set of functional and multivalued dependencies.The closure D+of D is the set of all functional and multivalued dependencies logically implied by D. Sound and complete inference rules for functional and multivalued dependencies: 1.Reflexivity rule.If a is a set of attributes and Bc a,then a>B holds. 2.Augmentation rule.If a>B holds and y is a set of attributes,then y o-→y B holds. 3.Transitivity rule.lfo-→βholds and y a-→y B holds,then a-→y holds. Database System Concepts,5th Ed. C.2 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.2 ©Silberschatz, Korth and Sudarshan th Ed. Theory of Multivalued Dependencies Let D denote a set of functional and multivalued dependencies. The closure D+ of D is the set of all functional and multivalued dependencies logically implied by D. Sound and complete inference rules for functional and multivalued dependencies: 1. Reflexivity rule. If is a set of attributes and , then → holds. 2. Augmentation rule. If → holds and is a set of attributes, then → holds. 3. Transitivity rule. If → holds and → holds, then → holds
Theory of Multivalued Dependencies (Cont.) 4.Complementation rule.If>B holds,then R-B-a holds. 5.Multivalued augmentation rule.Ife>B holds and y R and 8 cy,thena δB holds. 6.Multivalued transitivity rule.If e>B holds and>y holds, then->y-βholds. 7.Replication rule.If B holds,then>B. 8.Coalescence rule.Ife>B holds andy B and there is a 8 such thatδR andδB=g-andδY,t拽eno y holds. Database System Concepts,5th Ed. C.3 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.3 ©Silberschatz, Korth and Sudarshan th Ed. Theory of Multivalued Dependencies (Cont.) 4. Complementation rule. If holds, then R – – holds. 5. Multivalued augmentation rule. If holds and R and , then holds. 6. Multivalued transitivity rule. If holds and holds, then – holds. 7. Replication rule. If holds, then . 8. Coalescence rule. If holds and and there is a such that R and = and , then holds
Simplification of the Computation of D+ We can simplify the computation of the closure of D by using the following rules(proved using rules 1-8). Multivalued union rule.If aB holds and ay holds,then o>>βy holds. Intersection rule.If a B holds and ay holds,then aBr holds. Difference rule.IfIf aB holds and ay holds,then aB-Y holds and ay-B holds. Database System Concepts,5th Ed. C.4 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.4 ©Silberschatz, Korth and Sudarshan th Ed. Simplification of the Computation of D+ We can simplify the computation of the closure of D by using the following rules (proved using rules 1-8). Multivalued union rule. If holds and holds, then holds. Intersection rule. If holds and holds, then holds. Difference rule. If If holds and holds, then – holds and – holds
Example R=(A,B,C,G,H,I) D=(A B .> HI CG 份 Some members of D+: A CGHI. Since A B,the complementation rule(4)implies that A、R2B-A. Since R-B-A=CGHI,so A CGHI. A Hl. Since A、B and B H,the multivalued transitivity rule(6)implies that B HI-B. Since HI-B=HI,A HI. Database System Concepts,5th Ed. c.5 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.5 ©Silberschatz, Korth and Sudarshan th Ed. Example R = (A, B, C, G, H, I) D = {A B B HI CG H} Some members of D+: A CGHI. Since A B, the complementation rule (4) implies that A R – B – A. Since R – B – A = CGHI, so A CGHI. A HI. Since A B and B HI, the multivalued transitivity rule (6) implies that B HI – B. Since HI – B = HI, A HI