Saturday, February 17, 2018

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










No comments:

Post a Comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery