FD and Normal Form Calculation

Given R(A,B,C,D,E) with the set of FDs,
F{AB-> CD, ABC-> E, C-> A}
(i) Find any two candidate keys of R
(ii) What is the normal form of R? Justify.

(i) To find two candidate keys of R, we have to find the closure of the set of attributes
under consideration and if all the attributes of R are in the closure then that set is a
candidate key. Now from the set of FD’s we can make out that B is not occurring on the RHS of any FD, therefore, it must be a part of the candidate keys being considered otherwise it will not be in the closure of any attribute set. So let us consider the following sets AB and BC.

Now (AB)+= ABCDE, CD are included in closure because of the FD, AB-> CD, and E is
included in closure because of the FD ABC-> E.
Now (BC) += BCAED, A is included in closure because of the FD C-> A, and then E is
included in closure because of the FD ABC ->E and lastly D is included in closure
because of the FD AB ->CD.

Therefore two candidate keys are : AB and BC.

(ii) The prime attributes are A, B and C and non-prime attributes are D and E.

A relation scheme is in 2NF, if all the non-prime attributes are fully functionally
dependent on the relation key(s). From the set of FDs we can see that the non-prime
attributes (D,E) are fully functionally dependent on the prime attributes, therefore, the relation is in 2NF.
A relation scheme is in 3NF, if for all the non-trivial FDs in F+ of the form X A, either
X is a superkey or A is prime. From the set of FDs we see that for all the FDs, this is
satisfied, therefore, the relation is in 3NF.
A relation scheme is in BCNF, if for all the non-trivial FDs in F+ of the form X A, X is
a superkey. From the set of FDs we can see that for the FD C A, this is not satisfied as LHS is not a superkey, therefore, the relation is not in BCNF.

Hence, the given relation scheme is in 3NF.


Given R {ABCD} and a set F of functional dependencies on R given as
F = {AB->C,AB->D,C->A, D->B}. Find any two candidate keys of R. Show each
step. In what normal form is R? Justify.

With the given set of FDs, it is not possible to derive or access all the other attributes based on single attribute (e.g., {A}+ = {A}, {B}+ = {B}, {C}+ = {CA}, {D}+ = {DB}).
Therefore, we have to chose the composite keys:
1. If we assume X = {AB} then X+ = {ABCD} because we can determine the
attributes C and D from AB as per F.
2. If we assume X = {CD} then X+ = {CDAB} because we can determine the
attributes A and B from C and D respectively as per F.

The other possible candidate keys are: {CB} and {AD}.

If we choose, {CD} as the primary key of the relation R, then FDs C A and D B are
partial functional dependencies as CD is the key of the relation. Therefore, the given relation R is not in 2NF and therefore first normal form (1 NF).

Find 3NF decomposition of the relation scheme,
R = {Faculty, Dean, Dept, Chairperson, Professor, Rank, Student} with the set of
functional dependencies,
F = {Faculty->Dean 
Department->Chairperson
Professor->Rank, Chairperson
Department->Faculty
Student ->Department, Faculty,Dean 
Dean ->Faculty
Professor, Rank ->Department, Faculty}

To find out 3NF decomposition of a relation we use canonical cover (Fc).
Requirements for canonical cover (Fc):

1. Each FD in Fc must be simple.
F’ = {Faculty ->Dean, Department->Chairperson, Professor-> Rank,
Professor ->Chairperson, Department ->Faculty, Student->Department, Student->Faculty, Student->Dean, Dean->Faculty, ProfessorRank->Department,
ProfessorRank->Faculty}

2. Each FD in Fc must be left reduced.
As given in F, the attribute Rank is functionally dependent on the Professor. Therefore the FDs ProfessorRank->Department and ProfessorRank->Faculty can be left reduced to Professor->Department and Professor->Faculty respectively based on the Augmentation axiom.
F’’ = {Faculty->Dean, Department->Chairperson, Professor->Rank, Professor->Chairperson, Department->Faculty, Student->Department, Student->Faculty, Student->Dean, Dean->Faculty, Professor->Department, Professor->Faculty}

3. Each FD in Fc must be non-redundant.
The FDs Professor->Chairperson, Student->Faculty, Student->Dean and
Professor->Faculty are redundant and have to be removed based on the Transitivity
axiom.
Fc = {Faculty->Dean, Department->Chairperson, Professor->Rank, Department->Faculty, Student->Department, Dean->Faculty, Professor->Department}

To make lossless join decompositions, it is required to preserve the key of the original relation. The key of the relation R is {Professor, Student}. The 3NF decompositions of the given relation are:

R1 = {Faculty, Dean} F1= {Faculty Dean, Dean Faculty}
R2 = {Department, Chairperson, Faculty} F2 = {Department Chairperson,Faculty}
R3 = {Professor, Rank, Department} F3 = {Professor Rank,Department}
R4 = {Student, Department} F4 = {Student Department }
R5 = {Professor, Student} F5 = {ProfessorStudent f}