Example ■R=(A,B,C) F=A→B,B→C) R1=A,B),R2=(B,C) Lossless decomposition: R1∩R2={B}and B->BC ■R1=(A,B),R2=(A,C) Lossless decomposition: R1∩R2={A}andA→AB ■Wote. ·B→BC is a shorthand notation for ·B→{B,C} Database System Concepts-7th Edition 7.19 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.19 ©Silberschatz, Korth and Sudarshan th Edition Example ▪ R = (A, B, C) F = {A → B, B → C) ▪ R1 = (A, B), R2 = (B, C) • Lossless decomposition: R1 R2 = {B} and B → BC ▪ R1 = (A, B), R2 = (A, C) • Lossless decomposition: R1 R2 = {A} and A → AB ▪ Note: • B → BC is a shorthand notation for • B → {B, C}
Dependency Preservation Testing functional dependency constraints each time the database is updated can be costly It is useful to design the database in a way that constraints can be tested efficiently. If testing a functional dependency can be done by considering just one relation,then the cost of testing this constraint is low When decomposing a relation it is possible that it is no longer possible to do the testing without having to perform a Cartesian Produced. A decomposition that makes it computationally hard to enforce functional dependency is said to be NOT dependency preserving. Database System Concepts-7th Edition 7.20 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.20 ©Silberschatz, Korth and Sudarshan th Edition Dependency Preservation ▪ Testing functional dependency constraints each time the database is updated can be costly ▪ It is useful to design the database in a way that constraints can be tested efficiently. ▪ If testing a functional dependency can be done by considering just one relation, then the cost of testing this constraint is low ▪ When decomposing a relation it is possible that it is no longer possible to do the testing without having to perform a Cartesian Produced. ▪ A decomposition that makes it computationally hard to enforce functional dependency is said to be NOT dependency preserving
Dependency Preservation Example Consider a schema: dept advisor(s ID,i ID,department name) With function dependencies: ilD→dept_name s_lD,dept_name→iD In the above design we are forced to repeat the department name once for each time an instructor participates in a dept_advisorrelationship. To fix this,we need to decompose dept_advisor Any decomposition will not include all the attributes in s_ID,dept_name→ilD Thus,the composition NOT be dependency preserving Database System Concepts-7th Edition 7.21 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.21 ©Silberschatz, Korth and Sudarshan th Edition Dependency Preservation Example ▪ Consider a schema: dept_advisor(s_ID, i_ID, department_name) ▪ With function dependencies: i_ID → dept_name s_ID, dept_name → i_ID ▪ In the above design we are forced to repeat the department name once for each time an instructor participates in a dept_advisor relationship. ▪ To fix this, we need to decompose dept_advisor ▪ Any decomposition will not include all the attributes in s_ID, dept_name → i_ID ▪ Thus, the composition NOT be dependency preserving
Boyce-Codd Normal Form A relation schema R is in BCNF with respect to a set F of functional dependencies if for all functional dependencies in F+of the form 0→B where a cR and Bc R,at least one of the following holds: ·o-→B is trivial(i.e.,Bso) ·a is a superkey for R Database System Concepts-7th Edition 7.23 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 7.23 ©Silberschatz, Korth and Sudarshan th Edition Boyce-Codd Normal Form ▪ A relation schema R is in BCNF with respect to a set F of functional dependencies if for all functional dependencies in F+ of the form → where R and R, at least one of the following holds: • → is trivial (i.e., ) • is a superkey for R
Boyce-Codd Normal Form(Cont.) Example schema that is not in BCNF: in dep (ID,name,salary,dept name,building,budget) because ·dept name→building,budget holds on in dep but dept name is not a superkey When decompose in dept into instructorand department ·instructor is in BCNF ·departmentis in BCNF Database System Concepts-7th Edition 7.24 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 7.24 ©Silberschatz, Korth and Sudarshan th Edition Boyce-Codd Normal Form (Cont.) ▪ Example schema that is not in BCNF: in_dep (ID, name, salary, dept_name, building, budget ) because : • dept_name→building, budget ▪ holds on in_dep ▪ but • dept_name is not a superkey ▪ When decompose in_dept into instructor and department • instructor is in BCNF • department is in BCNF