Next: Third Normal Form Up: Normalization Using Functional Dependencies Previous: Repetition of Information

## Boyce-Codd Normal Form

1. A relation schema R is in Boyce-Codd Normal Form (BCNF) with respect to a set F 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 schema R.
2. A database design is in BCNF if each member of the set of relation schemas is in BCNF.
3. Let's assess our example banking design:

``` Customer-schema = (cname, street, ccity)

cname    street ccity

```

``` Branch-schema = (bname, assets, bcity)

bname    assets bcity

```

``` Loan-info-schema = (bname, cname, loan#, amount)

loan#    amount bname

```

Customer-schema and Branch-schema are in BCNF.

4. Let's look at Loan-info-schema:
• We have the non-trivial functional dependency loan# amount, and
• loan# is not a superkey.
• Thus Loan-info-schema 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 schemas that are all in BCNF.
5. If we decompose into

``` Loan-schema = (bname, loan#, amount)

Borrow-schema = (cname, loan#)

```

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

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

• For Loan-schema, we have loan# amount bname applying.
• Only trivial functional dependencies apply to Borrow-schema.
• Thus both schemas 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.
6. Now we can give a general method to generate a collection of BCNF schemas.

``` result :=   ;

done := false;

compute   ;

while (not done) do

if (there is a schema    in result that is not in BCNF)

then begin

let    be a nontrivial
functional dependency that holds on

such that    is not in   ,
and   ;

result = (result   ;

end

else done = true;

```

7. This algorithm generates a lossless-join BCNF decomposition. Why?

• We replace a schema 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:

``` Lending-schema = (bname, assets, bcity, loan#, cname, amount)

```

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

``` bname    assets bcity

loan#    amount bname

```

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

We will now proceed to decompose:

• The functional dependency

``` bname    assets bcity

```

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

We replace Lending-schema with

``` Branch-schema = (bname, assets, bcity)

Loan-info-schema = (bname, loan#, cname, amount)

```

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

``` loan#    amount bname

```

holds on Loan-info-schema, but loan# is not a superkey.

We replace Loan-info-schema with

``` Loan-schema = (bname, loan#, amount)

Borrow-schema = (cname, loan#)

```

• 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 schema

``` Banker-schema = (bname, cname, banker-name)

```

• The set F of functional dependencies is

``` banker-name    bname

cname bname    banker-name

```

• The schema is not in BCNF as banker-name is not a superkey.

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

``` Banker-branch-schema = (bname, banker-name)

Cust-banker-schema = (cname, banker-name)

```

• The decomposed schemas 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-name 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-schema must fail to preserve

``` cname bname    banker-name

```

12. Some Things To Note About BCNF

• There is sometimes more than one BCNF decomposition of a given schema.
• 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.

Next: Third Normal Form Up: Normalization Using Functional Dependencies Previous: Repetition of Information

Osmar Zaiane
Thu Jun 18 12:56:34 PDT 1998