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
Example (Cont.) Some members of D+(cont.): ·B>H. Apply the coalescence rule (8);B->>H/holds. Since HC HI 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>>CGH∥andA>>Hl. By the difference rule,A->>CGHI -HI. Since CGHI-HI=CG.A->CG Database System Concepts-7th Edition 28.7 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 28.7 ©Silberschatz, Korth and Sudarshan th Edition 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,...,R be a decomposition of R.If R=RUR2....R,we say that a relation r(R)satisfies the join dependency*(R1,R2,...,R)if: r=ΠR1()凶ΠR2()凶.凶ΠRn() A join dependency is trivial if one of the R,is R itself. A join dependency *(R1,R2)is equivalent to the multivalued dependency R1∩R2>R2.Conversely,o-→>B is equivalent to*(aU(R-B),oUβ) However,there are join dependencies that are not equivalent to any multivalued dependency. Database System Concepts-7th Edition 28.8 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 28.8 ©Silberschatz, Korth and Sudarshan th Edition 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,...,Rn where each Ric R and R=RjUR2...UR 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-7th Edition 28.9 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 28.9 ©Silberschatz, Korth and Sudarshan th Edition 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-7th Edition 28.10 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 28.10 ©Silberschatz, Korth and Sudarshan th Edition Example ▪ Consider Loan-info-schema = (branch-name, customer-name, loannumber, 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 DUK logically imply G. Database System Concepts-7th Edition 28.11 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 28.11 ©Silberschatz, Korth and Sudarshan th Edition 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