Solved Exercises Normalization 1

Normalization - Solved exercise

Question:

Consider a relation Movies_Screened with attributes Theatre, Movie, Day, Time, and Certificate. Sample tuples are as follows:

Sathyam, 'Slumdog Millionaire', Wed, 18:00, 15

Sathyam, 'Slumdog Millionaire', Wed, 20:00, 15

PVR, 'Slumdog Millionaire', Wed, 20:30, 15

PVR, 'Vicky Christina Barcelona', Wed, 20:30, 12A

Each movie is assigned a certificate by the Indian Board of Film Certification; the certificate value 15 means that nobody younger than 15 years of age can see this movie in a cinema. The same theatre can show a movie on multiple times during a day, and may show different movies at the same time (on different screens).

(a) Does this relation violate the second normal form requirements? Explain.

(b) Decompose this relation into BCNF, and explain why the resulting relations are in BCNF.

Answer (a):

To check for 2NF, first we need to find the candidate keys for MOVIES_SCREENED.

Let us find the functional dependencies (FDs) of MOVIES_SCREENED.

• THEATRE cannot determine any attributes as a theatre screens more than one movie, it screens on different days, different timings, and different certification movies.

• MOVIE can determine the CERTIFICATE value as a movie will be given only one certificate. Hence, we can include MOVIE → CERTIFICATE.

• Likewise, DAY, TIME and CERTIFICATE cannot determine the other attributes uniquely.

We get the set of FDs for this relation as follows;

F = { MOVIE → CERTIFICATE, (THEATRE, MOVIE, DAY, TIME) → CERTIFICATE }

To find the candidate key, we need to find the closure of left hand side attributes of the FDs.

(THEATRE, MOVIE, DAY, TIME)⁺ = THEATRE, MOVIE, DAY, TIME, CERTIFICATE.

Hence, the composite key (THEATRE, MOVIE, DAY, TIME) is the candidate key for the relation MOVIES_SCREENED.

To be in 2NF, a relation should not have partial functional dependency.

In our relation, a non-key attribute CERTIFICATE is determined by MOVIE, which is part of a candidate key (THEATRE, MOVIE, DAY, TIME). So the given relation is not in 2NF.

The relation MOVIES_SCREENED violates second normal form. 

Answer (b):

As discussed, the relation violates 2NF. To normalize to 2NF, we decompose the the relation using the violating functional dependency MOVIE → CERTIFICATE.

It results in the following relations;

Movie_Screens (THEATRE, MOVIE, DAY, TIME)

Movies (MOVIE, CERTIFICATE).

Both relations are in 2NF because no partial dependency exists [see the keys underlined].

Both relations are in 3NF too because no transitive dependencies found.

Also, both are in BCNF because in the Movie_Screens relation, no subset of the attributes determines any other attribute, and the only non-trivial dependency in MOVIES is from MOVIES to CERTIFICATE.

************** 

Go back to Normalization – solved exercises page.

Go to How to find closure page

Go to 2NF, 3NF and BCNF

normalize the table, normalize a relation to second normal form, third normal form, boyce-codd normal form

Find the redundant extraneous attributes

Find the redundant (extraneous) attributes from the set of functional dependencies

Question:

Consider the relation STUDENT with the schema STUDENT(RegNo, Name, DOB, Age, Dept, Course, Semester, Grade) and set of functional dependencies F = {RegNo → Name, RegNo → DOB, RegNo DOB → Age, RegNo → Dept, RegNo Dept Course Semester → Grade}. Find the attributes that are redundant in the given set F of functional dependencies.

Solution:

What is redundant attribute?

An attribute in the left hand side (LHS) of a functional dependency, especially if more than one attribute present in the LHS, is said to be a redundant (extraneous) attribute if the RHS attribute(s) can be determined with the help of other LHS attributes.

How to identify a redundant attribute?

If the RHS of the said functional dependency can be derived without one of the attributes on the LHS, using the other FDs of that relation, then that particular attribute is said to be redundant. For example, in AB → C the attribute B is redundant if closure of A can determine C.

Let us solve the given question;

We don’t need to check for redundant attributes in a FD (functional dependency) where the LHS attribute is only one. Hence, we can omit the following FDs.

RegNo → Name,

RegNo → DOB,

RegNo → Dept,

(i) Now let us take the FD RegNo DOB → Age. To check either of the LHS attributes are redundant, we have to use the other attribute to derive the RHS.

Is DOB redundant?

To check, we have to find the closure of the other attributes. In this FD, RegNo is the only other attribute. Hence let us find the closure of RegNo.

(RegNo)⁺ = RegNo, Name, DOB, Dept, Age.

Observe from the closure that the attribute Age is part of the closure. Hence, DOB is redundant attribute. So we can remove DOB from RegNo DOB → Age results in the FD RegNo → Age.

Now our F becomes { RegNo → Name, RegNo → DOB, RegNo → Age, RegNo → Dept, RegNo Dept Course Semester → Grade}

(ii) Now let us take the last FD RegNo Dept Course Semester → Grade.

Is Dept redundant?

Find the closure of RegNo, Course, Semester.

(RegNo Course Semester)⁺ = RegNo, Name, DOB, Dept, Age, Course, Semester, Grade.

Result includes Grade. So attribute Dept is redundant and can be removed.

Now our F becomes { RegNo → Name, RegNo → DOB, RegNo → Age, RegNo → Dept, RegNo Course Semester → Grade}

(iii) Let us take the last FD given above, RegNo Course Semester → Grade.

Is Course redundant?

Find the closure of RegNo, Semester.

(RegNo Semester)⁺ = RegNo, Name, DOB, Age, Dept, Semester

The result does not include Grade. Hence, the attribute Course is not redundant. And our F does not change.

Is Semester redundant?

Find the closure of RegNo, Course.

(RegNo, Course)⁺ = RegNo, Name, DOB, Age, Dept, Course.

The result does not include Grade. Hence, the attribute Semester is not redundant. And our F does not change.

The final set of functional dependencies F is as follows;

F = { RegNo → Name, RegNo → DOB, RegNo → Age, RegNo → Dept, RegNo Course Semester → Grade}

***************

Go to Normalization - Solved Exercises page

Go to - 1NF,    2NF,    3NF,    BCNF

Go to How to find closure? page

Find the redundant attributes in a given functional dependency

How to remove redundant attributes

How to remove extraneous attributes

Find and remove redundant (extraneous) attributes

Normalize relational table by removing redundant attributes

How to eliminate extraneous attributes to find minimal cover