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
Example (Cont.) Some members of D+(cont.): B>H. Apply the coalescence rule(8);B>H/holds. Since HCHI and CG Hand CGHI=,the coalescence rule is satisfied with a being B,B being H,8 being CG,and y being H.We conclude that B H. A>CG. A>CGHI and A>HI. By the difference rule,A> CGHI -HI. Since CGHI -HI=CG.A>CG. Database System Concepts,5th Ed. c.6 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.6 ©Silberschatz, Korth and Sudarshan th Ed. Example (Cont.) Some members of D+ (cont.): B H. Apply the coalescence rule (8); B HI holds. Since H HI and CG H and CG HI = Ø, the coalescence rule is satisfied with being B, being HI, being CG, and being H. We conclude that B H. A CG. A CGHI and A HI. By the difference rule, A CGHI – HI. Since CGHI – HI = CG, A CG
Normalization Using Join Dependencies Join dependencies constrain the set of legal relations over a schema R to those relations for which a given decomposition is a lossless-join decomposition. Let R be a relation schema and R1,R2,...,Rn be a decomposition of R.If R= RR2....R,we say that a relation r(R)satisfies the join dependency *(R1,R2...Rn)if: r=R1()凶ΠR2(0凶..凶ΠRn() Ajoin dependency is trivial if one of the R,is R itself. Ajoin dependency *(R1,R2)is equivalent to the multivalued dependency R1 R2 R2.Conversely,a B is equivalent to *(a(R-B),aB) However,there are join dependencies that are not equivalent to any multivalued dependency. Database System Concepts,5th Ed. C.7 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.7 ©Silberschatz, Korth and Sudarshan th Ed. Normalization Using Join Dependencies Join dependencies constrain the set of legal relations over a schema R to those relations for which a given decomposition is a lossless-join decomposition. Let R be a relation schema and R1 , R2 ,..., Rn be a decomposition of R. If R = R1 R2 …. Rn , we say that a relation r(R) satisfies the join dependency *(R1 , R2 ,..., Rn ) if: r =R1 (r) ⋈ R2 (r) ⋈ …… ⋈ Rn(r) A join dependency is trivial if one of the Ri is R itself. A join dependency *(R1 , R2 ) is equivalent to the multivalued dependency R1 R2 R2 . Conversely, is equivalent to *( (R - ), ) However, there are join dependencies that are not equivalent to any multivalued dependency
Project-Join Normal Form (PJNF) A relation schema R is in PJNF with respect to a set D of functional, multivalued,and join dependencies if for all join dependencies in D+of the form *(R1,R2,...,R where each RiR and R=RjUR2...URp at least one of the following holds: *(R1,R2,...,R)is a trivial join dependency. Every R,is a superkey for R. Since every multivalued dependency is also a join dependency. every PJNF schema is also in 4NF. Database System Concepts,5th Ed. C.8 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.8 ©Silberschatz, Korth and Sudarshan th Ed. Project-Join Normal Form (PJNF) A relation schema R is in PJNF with respect to a set D of functional, multivalued, and join dependencies if for all join dependencies in D+ of the form *(R1 , R2 ,..., Rn ) where each Ri R and R =R1 R2 ... Rn at least one of the following holds: *(R1 , R2 ,..., Rn ) is a trivial join dependency. Every Ri is a superkey for R. Since every multivalued dependency is also a join dependency, every PJNF schema is also in 4NF
Example Consider Loan-info-schema =(branch-name,customer-name,loan-number. amount). Each loan has one or more customers,is in one or more branches and has a loan amount;these relationships are independent,hence we have the join dependency *(=(loan-number,branch-name),(loan-number,customer-name),(loan- number,amount)) Loan-info-schema is not in PJNF with respect to the set of dependencies containing the above join dependency.To put Loan-info-schema into PJNF, we must decompose it into the three schemas specified by the join dependency: (loan-number,branch-name) (loan-number,customer-name) (loan-number,amount) Database System Concepts,5th Ed. c.9 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.9 ©Silberschatz, Korth and Sudarshan th Ed. Example Consider Loan-info-schema = (branch-name, customer-name, loan-number, amount). Each loan has one or more customers, is in one or more branches and has a loan amount; these relationships are independent, hence we have the join dependency *(=(loan-number, branch-name), (loan-number, customer-name), (loannumber, amount)) Loan-info-schema is not in PJNF with respect to the set of dependencies containing the above join dependency. To put Loan-info-schema into PJNF, we must decompose it into the three schemas specified by the join dependency: (loan-number, branch-name) (loan-number, customer-name) (loan-number, amount)
Domain-Key Normal Form(DKNY) Domain declaration.Let A be an attribute,and let dom be a set of values.The domain declaration A c dom requires that the A value of all tuples be values in dom. Key declaration.Let R be a relation schema with Kc R.The key declaration key(K)requires that K be a superkey for schema R(K-> R).All key declarations are functional dependencies but not all functional dependencies are key declarations. General constraint.A general constraint is a predicate on the set of all relations on a given schema. Let D be a set of domain constraints and let K be a set of key constraints for a relation schema R.Let G denote the general constraints for R.Schema R is in DKNF if DK logically imply G. Database System Concepts,5th Ed. C.10 ©Silberschat乜，Korth and Sudarshan
Database System Concepts, 5 C.10 ©Silberschatz, Korth and Sudarshan th Ed. Domain-Key Normal Form (DKNY) Domain declaration. Let A be an attribute, and let dom be a set of values. The domain declaration A dom requires that the A value of all tuples be values in dom. Key declaration. Let R be a relation schema with K R. The key declaration key (K) requires that K be a superkey for schema R (K → R). All key declarations are functional dependencies but not all functional dependencies are key declarations. General constraint. A general constraint is a predicate on the set of all relations on a given schema. Let D be a set of domain constraints and let K be a set of key constraints for a relation schema R. Let G denote the general constraints for R. Schema R is in DKNF if D K logically imply G