Outline ■Reasoning with MVDs Higher normal forms Join dependencies and PJNF ·DKNF Database System Concepts-7th Edition 28.2 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 28.2 ©Silberschatz, Korth and Sudarshan th Edition Outline ▪ 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: ·Reflexivity rule.If a is a set of attributes and B,then a→阝 holds. Augmentation rule.If a->B holds and y is a set of attributes, then y a-→yβholds.. ·Transitivity rule.lfa→B holds and B→holds,then a→y holds. Database System Concepts-7th Edition 28.3 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 28.3 ©Silberschatz, Korth and Sudarshan th Edition 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: • Reflexivity rule. If is a set of attributes and , then → holds. • Augmentation rule. If → holds and is a set of attributes, then → holds. • Transitivity rule. If → holds and → holds, then → holds
Theory of Multivalued Dependencies (Cont.) 。 Complementation rule.If a>>B holds,then a>>R-B-a holds. 。 Multivalued augmentation rule.If aB holds and y R and y,then y aB holds. 。 Multivalued transitivity rule.If a>B holds and B>>y holds, then→>y-βholds. Replication rule.If a>B holds,then a>B. Coalescence rule.lfo->>βholds and yβand there is aδ such thatδRandδ∩B=☑andδ>Y,then>y holds. Database System Concepts-7th Edition 28.4 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 28.4 ©Silberschatz, Korth and Sudarshan th Edition Theory of Multivalued Dependencies (Cont.) • Complementation rule. If holds, then R – – holds. • Multivalued augmentation rule. If holds and R and , then holds. • Multivalued transitivity rule. If holds and holds, then – holds. • Replication rule. If holds, then . • 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 a>B holds and a>>y holds,then -→>βy holds. · Intersection rule.If a>B holds and a>>y holds,then a>>By holds. ·Difference rule..lfa→>B holds and a->>y holds,then a>>β-y holds and>>y-阝holds. Database System Concepts-7th Edition 28.5 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 28.5 ©Silberschatz, Korth and Sudarshan th Edition 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 holds and holds, then – holds and – holds
Example R=(A,B,C,G,H,1) D={A-→>B BHI CG→H Some members of D+: ·A>>CGHl. Since A->>B,the complementation rule (4)implies that A->>R-B-A. Since R-B-A=CGHI.so A->CGHI ·A>>Hl. Since A-→>B and B→→Hl,the multivalued transitivity rule(6) implies that B>>H/-B. Since HI-B=HI.A>HI. Database System Concepts-7th Edition 28.6 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 28.6 ©Silberschatz, Korth and Sudarshan th Edition 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