Find whether the given decomposition is Lossless or lossy decomposition

Find whether the given decomposition is Lossless or lossy decomposition

Question:

Suppose you are given a relation R(A,B,C,D). let us assume that set of functional dependencies F = { B → C, D → A} and R is decomposed into R1(B,C), and R2(A,D).

(a) Find the candidate key(s) for R. (b) State whether or not the proposed decomposition of R into smaller relations is a good decomposition and briefly explain why or why not.

Solution:

a) To find the candidate keys, we have to find the closure of attributes of LHS (left hand side) of all functional dependencies. If the closure includes all the attributes of the given relation, then that attribute (or set of attributes) is the candidate key.

B⁺ = BC. It does not include all attributes of R.

D⁺ = DA. It does not include all attributes of R.

(BD)⁺ = BCDA. It includes all attributes of R, hence BD is the candidate key.

b) The decomposition of R into R1 and R2 is lossy because there is no common attribute between R1 and R2 (R1∩R2 = ∅). Hence, the join of R1 and R2 will result in Cartesian product of these two relations which is not the base relation R.

***********

Go to Normalization solved exercises page

Go to Solved exercises in DBMS page

Normalization exercises

Decompose given relation

Find whether the decomposition is lossless or lossy

lossless join decomposition exercises

lossy join decomposition exercises

Find minimal cover/canonical cover in a set of FDs

Find minimal cover/canonical cover in a set of given functional dependencies

Question:

For a relation schema R = (A, B, C, D, E), consider the following set of functional dependencies;

F = {A → BC, CD → E, B → D, E → A}

Using the functional dependencies compute the canonical cover F_c.

Solution:

Minimal cover: Definition 1: A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. There can be many such minimal covers for a set of functional dependencies F. Definition 2: A set of FDs F is minimum if F has as few FDs as any equivalent set of FDs. [How to find minimal cover? – Refer here].

Follow these steps to find the canonical (minimal) cover;

1. Decompose each functional dependency in F to have singleton (single) attribute on the Right Hand Side (RHS).

2. Remove extraneous (redundant) attributes from Left Hand Side of each functional dependency.
[What is extraneous attribute? Refer here].

3. Find and eliminate redundant functional dependencies.

Let us apply the above said properties to F;

F = {A → BC, CD → E, B → D, E → A}

1. RHS of all functional dependencies should be singleton. To achieve this we decompose each functional dependency that has two or more attributes in their RHS. We get the following set of functional dependencies F1;

F1 = {A → B, A → C, CD → E, B → D, E → A}

2. Remove extraneous (redundant) attributes. This is applicable only for those functional dependencies that have two or more attributes on its LHS.

We need to check whether or not an attribute/set of attributes of LHS of a functional dependency is redundant or not. For checking this, we have to find the closure of each individual LHS attribute of each FD that has two or more LHS attributes.

With this property we have only one FD, CD → E. We need to check whether C alone or E alone can find E uniquely.

C+ = C by reflexivity rule

D+ = D by reflexivity rule

From this we found that either C or D alone cannot determine the value of E. Hence, the FD CD → E does not have any extraneous attributes.

Hence, our F1 is as follows;

F1 = {A → B, A → C, CD → E, B → D, E → A}

3. Eliminate redundant functional dependencies.

To find redundant FDs, we have to find whether the RHS of a FD can be determined using other FDs.

(i) Let us check first for FD, A → B. To proceed, we forget , A → B from F, and use only the remaining FDs A → C, CD → E, B → D, E → A of F. That is our F becomes F1 = {A → C, CD → E, B → D, E → A}

Now find A+ using F1. A+ = {A,C} which does not include B. Hence, A → B is not redundant.

(ii) Now check for A → C. can we find C using following FDs?

F1 = {A → B, CD → E, B → D, E → A}

A+ = ABD

B+ = BD

We are not able to determine C using F1. Hence, A → C is not redundant.

If we repeat this for each FD in F, we found that none of them are redundant.

Hence our Fc is as follows;

Fc = {A → BC, CD → E, B → D, E → A} which is same as F in the question.

***********

Similar topics

How to find closure of set of functional dependencies?

How to find closure of attributes?

How to find canonical cover for a set of functional dependencies?

How to find extraneous attribute?

Go back to Question/QUIZ page

Go back to Online Quizzes home page

find canonical cover of F

what is minimal cover? how to find minimal cover

minimal cover solved exercise

find extraneous attributes

 

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