Boyce-Codd Normal Form

1. A relation scheme is in Boyce-Codd Normal Form (BCNF) with respect to a set of functional dependencies if for all functional dependencies in of the form , where and , at least one of the following holds:
   • is a trivial functional dependency (i.e. ).
   • is a superkey for scheme .
2. A database design is in BCNF if each member of the set of relation schemes is in BCNF.

3. Let's assess our example banking design:

   

   

   

   

   Customer-scheme and Branch-scheme are in BCNF.

4. Let's look at Borrow-scheme:
   • We have the non-trivial functional dependency loan# amount, and
   • loan# is not a superkey.
   • Thus Borrow-scheme is not in BCNF.
   • We also have the repetition of information problem.
   • For each customer associated with a loan, we must repeat the branch name and amount of the loan.
   • We can eliminate this redundancy by decomposing into schemes that are all in BCNF.
5. If we decompose into

   

   we have a lossless-join decomposition. (Remember why?)

   To see whether these schemes are in BCNF, we need to know what functional dependencies apply to them.

   • For Loan-info-scheme, we have loan# amount bname applying.
   • Only trivial functional dependencies apply to Cust-loan-scheme.
   • Thus both schemes are in BCNF.
   We also no longer have the repetition of information problem. Branch name and loan amount information are not repeated for each customer in this design.

   For the entire design to be in BCNF, we must also decompose Deposit-scheme into

   

6. Now we can give a general method to generate a collection of BCNF schemes.

   

7. This algorithm generates a lossless-join BCNF decomposition. Why?
   • We replace a scheme with and .
   • The dependency holds on .

   • .
   • So we have , and thus a lossless join.
8. Let's apply this algorithm to our earlier example of poor database design:

   

   The set of functional dependencies we require to hold on this scheme are

   

   A candidate key for this scheme is {loan#, cname}.

   We will now proceed to decompose:

   • The functional dependency

     

     holds on Lending-scheme, but bname is not a superkey.

     We replace Lending-scheme with

     

   • Branch-scheme is now in BCNF.
   • The functional dependency

     

     holds on Borrow-scheme, but loan# is not a superkey.

     We replace Borrow-scheme with

     

   • These are both now in BCNF.
   • We saw earlier that this decomposition is both lossless-join and dependency-preserving.
9. Not every decomposition is dependency-preserving.
   • Consider the relation scheme

     

   • The set of functional dependencies is

     

   • The scheme is not in BCNF as banker is not a superkey.

   • If we apply our algorithm, we may obtain the decomposition

     

   • The decomposed schemes preserve only the first (and trivial) functional dependencies.
   • The closure of this dependency does not include the second one.
   • Thus a violation of cname bname banker cannot be detected unless a join is computed.
   This shows us that not every BCNF decomposition is dependency-preserving.

10. It is not always possible to satisfy all three design goals:
    • BCNF.
    • Lossless join.
    • Dependency preservation.
11. We can see that any BCNF decomposition of Banker-scheme must fail to preserve

    

12. Some Things To Note About BCNF
    • There is sometimes more than one BCNF decomposition of a given scheme.
    • The algorithm given produces only one of these possible decompositions.

    • Some of the BCNF decompositions may also yield dependency preservation, while others may not.
    • Changing the order in which the functional dependencies are considered by the algorithm may change the decomposition.

    • For example, try running the BCNF algorithm on

      

      Then change the order of the last two functional dependencies and run the algorithm again. Check the two decompositions for dependency preservation.