Decomposition Decompose the relation schema Lending schema into Branch-schema=(branch-name, branch-city, assets) Loan-info-schema =(customer-name, loan-number branch-name, amount) All attributes of an original schema(R)must appear in the decomposition(R1, R2) R=R∪R Lossless-join decomposition(无损连接分解) For all possible relations r on schema R r=R1()IR2( 标 Database System Concepts 7.6 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.6 ©Silberschatz, Korth and Sudarshan Decomposition Decompose the relation schema Lending-schema into: Branch-schema = (branch-name, branch-city,assets) Loan-info-schema = (customer-name, loan-number, branch-name, amount) All attributes of an original schema (R) must appear in the decomposition (R1 , R2 ): R = R1 R2 Lossless-join decomposition（无损连接分解）. For all possible relations r on schema R r = R1 (r) R2 (r)
Example of Non Lossless Join Decomposition Decomposition of R=(A, B) R2=(A)R2=(B) A B A B a2 2 B ∏(r) ∏A(r)∏B(r) aaββ 2 2 Database System Concepts 7.7 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.7 ©Silberschatz, Korth and Sudarshan Example of Non Lossless-Join Decomposition Decomposition of R = (A, B) R2 = (A) R2 = (B) A B 1 2 1 A B 1 2 r A(r) B(r) A (r) B (r) A B 1 2 1 2
Goal- Devise a Theory for the Following Decide whether a particular relation R is in good form In the case that a relation R is not in good form, decompose it into a set of relations (R, R2, ...,Rny such that each relation is in good form the decomposition is a lossless-join decomposition Our theory is based on functional dependencies multivalued dependencies Database System Concepts 7.8 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.8 ©Silberschatz, Korth and Sudarshan Goal — Devise a Theory for the Following Decide whether a particular relation R is in “good” form. In the case that a relation R is not in “good” form, decompose it into a set of relations {R1 , R2 , ..., Rn } such that each relation is in good form the decomposition is a lossless-join decomposition Our theory is based on: functional dependencies multivalued dependencies
Functional Dependencies 函救依赖 Constraints on the set of legal relations Require that the value for a certain set of attributes determines uniquely the value for another set of attributes A functional dependency is a generalization of the notion of a key. 标 Database System Concepts 7.9 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.9 ©Silberschatz, Korth and Sudarshan Functional Dependencies （函数依赖） Constraints on the set of legal relations. Require that the value for a certain set of attributes determines uniquely the value for another set of attributes. A functional dependency is a generalization of the notion of a key
Functional Dependencies(Cont.) Let r be a relation schema α CR and Bc r The functional dependency 0→>B holds on R if and only if for any legal relations r(R) whenever any two tuples t, and t2 of r agree on the attributes a, they also agree on the attributes B. That is t1[o]=t2[]→t1[/]=t2[6] K is a superkey for relation schema R if and only if K>R K is a candidate key for R if and only if K→)R.and for no ac K.a→R Database System Concepts 7.10 OSilberschatz. Korth and Sudarshan
Database System Concepts 7.10 ©Silberschatz, Korth and Sudarshan Functional Dependencies (Cont.) Let R be a relation schema R and R The functional dependency → holds on R if and only if for any legal relations r(R), whenever any two tuples t1 and t2 of r agree on the attributes , they also agree on the attributes . That is, t1 [] = t2 [] t1 [ ] = t2 [ ] K is a superkey for relation schema R if and only if K → R K is a candidate key for R if and only if K → R, and for no K, → R