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 R and B R,at least one of the following holds: aB is trivial (i.e.,Bc a) a is a superkey for R Example schema not in BCNF: bor loan =customer_id,loan_number,amount because loan_number->amount holds on bor_loan but loan number is not a superkey Database System Concepts-5th Edition,Oct 5,2006 7.17 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 7.17 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Boyce-Codd Normal Form → is trivial (i.e., ) is a superkey for R 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: Example schema not in BCNF: bor_loan = ( customer_id, loan_number, amount ) because loan_number → amount holds on bor_loan but loan_number is not a superkey
Decomposing a Schema into BCNF Suppose we have a schema R and a non-trivial dependency a> causes a violation of BCNF. We decompose R into: ·(aUB) °(R-(B-a) In our example, a=loan number B=amount and bor loan is replaced by (a UB)=(loan_number,amount) (R-（B-u)）=(customer_id,loan_number) Database System Concepts-5th Edition,Oct 5,2006 7.18 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 7.18 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Decomposing a Schema into BCNF Suppose we have a schema R and a non-trivial dependency → causes a violation of BCNF. We decompose R into: • ( U ) • ( R - ( - ) ) In our example, = loan_number = amount and bor_loan is replaced by ( U ) = ( loan_number, amount ) ( R - ( - ) ) = ( customer_id, loan_number )
BCNF and Dependency Preservation Constraints,including functional dependencies,are costly to check in practice unless they pertain to only one relation If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that al/functional dependencies hold,then that decomposition is dependency preserving. Because it is not always possible to achieve both BCNF and dependency preservation,we consider a weaker normal form,known as third normal form. Database System Concepts-5th Edition,Oct 5,2006 7.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 7.19 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 BCNF and Dependency Preservation Constraints, including functional dependencies, are costly to check in practice unless they pertain to only one relation If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that all functional dependencies hold, then that decomposition is dependency preserving. Because it is not always possible to achieve both BCNF and dependency preservation, we consider a weaker normal form, known as third normal form
Third Normal Form A relation schema R is in third normal form(3NF)if for all: oa-→BinF+ at least one of the following holds: o→B is trivial(i.e.,B∈o) a is a superkey for R Each attribute A in B-a is contained in a candidate key for R. (NOTE:each attribute may be in a different candidate key) If a relation is in BCNF it is in 3NF(since in BCNF one of the first two conditions above must hold). Third condition is a minimal relaxation of BCNF to ensure dependency preservation (will see why later). Database System Concepts-5th Edition,Oct 5,2006 7.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 7.20 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Third Normal Form A relation schema R is in third normal form (3NF) if for all: → in F+ at least one of the following holds: → is trivial (i.e., ) is a superkey for R Each attribute A in – is contained in a candidate key for R. (NOTE: each attribute may be in a different candidate key) If a relation is in BCNF it is in 3NF (since in BCNF one of the first two conditions above must hold). Third condition is a minimal relaxation of BCNF to ensure dependency preservation (will see why later)
Goals of Normalization Let R be a relation scheme with a set F of functional dependencies. Decide whether a relation scheme R is in"good"form. In the case that a relation scheme R is not ingood"form, decompose it into a set of relation scheme (R1,R2,...R}such that each relation scheme is in good form the decomposition is a lossless-join decomposition Preferably,the decomposition should be dependency preserving. Database System Concepts-5th Edition,Oct 5,2006 7.21 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 7.21 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Goals of Normalization Let R be a relation scheme with a set F of functional dependencies. Decide whether a relation scheme R is in “good” form. In the case that a relation scheme R is not in “good” form, decompose it into a set of relation scheme {R1 , R2 , ..., Rn } such that each relation scheme is in good form the decomposition is a lossless-join decomposition Preferably, the decomposition should be dependency preserving