Third Normal Form

Third Normal Form

Sometimes, one encounters a relation schema and its FD's that are not in BCNF but that one doesn't want to decompose further. The following example is typical.

Example : Suppose we have a relation Bookings with attributes:

1. title, the name of a movie.

2. theater, the name of a theater where the movie is being shown.

3. city, the city where the theater is located.

The intent behind a tuple (m, t, c) is that the movie with title m is currently being shown at theater t in city c.

We might sensibly affirm the following FD's:

    theater  city
    title city  theater

The first says that a theater is located in one city. The second is not clear but is based on the assumed practice of not booking a movie into two theaters in the same city. We shall affirm this FD if only for the sake of the example.

Let us first find the keys. No single attribute is a key. For instance, title is not a key because a movie can play in various theaters at once and in various cities at once. Also, theater is not a key, because though theater functionally determines city, there are multiscreen theaters that show various movies at once. Therefore, theater does not determine title. Finally, city is not a key because cities generally have more than one theater and more than one movie playing.

On the other hand, two of the three sets of two attributes are keys. Obviously {title, city} is a key because of the given FD that says these attributes functionally determine theater.

It is also true that {theater, title} is a key. To see why, start with the given FD theater → city. By the augmentation rule, theater title → city follows. Apparently, if theater alone functionally determines city, then surely theatre and title together will do so.

The remaining pair of attributes, city and theater, do not functionally determine title, and are therefore not a key. We resolve that the only two keys are

    {title, city}
    {theater, title}

Now we right away see a BCNF violation. We were given functional dependency theater → city, but its left side, theater, is not a superkey. We are therefore enticed to decompose, using this BCNF-violating FD, into the two relation schemas:

    {theater, city}
    {theater, title}

There is a problem with this decomposition, concerning the FD

    title city  theater

There could be current relations for the decomposed schemas that satisfy the FD theater → city (which can be checked in the relation {theater, city} ) but that, when joined, yield a relation not satisfying title city → theater. For example, the two relations



Other Normal Forms

and


are allowable according to the FDs that apply to each of the above relations, but when we join them we get two tuples


that violate the FD title city → theater.

The solution to the above problem is to relax our BCNF requirement slightly, in order to allow the infrequent relation schema, like that of above example, which cannot be decomposed into BCNF relations without our losing the ability to check each FD within one relation. This relaxed condition is called the third normal form condition:

●  A relation R is in third normal form (3NF) if : whenever A1A2 . . . An → B is a nontrivial FD, either {A1, A2, . . . ,An} is a superkey, or B is a member of some key.

An attribute that is a member of some key is sometimes said to be prime. Therefore, the 3NF condition can be stated as "for each nontrivial FD, either the left side is a superkey, or the right side is prime".

Note that the difference between this 3NF condition and the BCNF condition is the clause "or B is a member of some key (i.e., prime)". This clause "excuses" a FD like theater → city in above example, because the right side, city, is prime.

It is outside the scope of this blog to prove that 3NF is actually enough for its purposes. That is, we can always decompose a relation schema in a way that does not lose information, into schemas that are in 3NF and allow all FDs to be checked. When these relations are not in BCNF, there will be some redundancy left in the schema, however.



Tags