DEV Community

loading...
Cover image for Closure set of Attributes and finding Candidate Keys

Closure set of Attributes and finding Candidate Keys

hebaShakeel
A Computer Science Student
・2 min read

Closure of an Attribute Set:
-> It is denoted by { }+

Example 1:
Let a relation, R(ABCDE)
FDs: {AB->C, C->E, BC->E, B->AD}

Closure of AB, {AB}+ : {A,B,C,E,D}
Closure of C, {C}+ : {C,E}
Closure of CE, {CE}+ : {C,E}

Example 2:
Let a relation, R(MNPXZ)
FDs: {MN->PZ, PX->Z, MX->Z, P->M, N->M}

Closure of P, {P}+ : {P,M}
Closure of XZ, {XZ}+ : {X,Z}
Closure of MNP, {MNP}+ : {M,N,P,Z}
Closure of XPZ, {XPZ}+ : {X,P,Z,M}

How to Find a Candidate Key in a Relation?
Example 1:
Let a relation, R(ABCDE)
FDs: {A->BC, B->C, D->C, AC->D}

Alt Text

Total no. of Possible Candidate Keys: 2^n - 1
where, n = no. of Attributes

Short-Cut Method

Example 1:
Let a relation, R(ABCDE)
FDs: {A->BC, B->C, D->C, AC->D}

Find the attributes that are not present in the LHS of the FD, here A and E. Therefore A, E are essential attributes.

(AE)+ = {A,E,B,C,D} => Candidate Key
(AEB)+ = {A,E,B,C,C} => Super Key

Example 2:
Let a relation, R(PQRST)
FDs: {PQR->T, RSTP->S, P->Q, Q->T, TS->R}

Here P is not on the LHS of any FD, i.e P cannot be derived from any of the FD. Therefore it is an essential Attribute and will be present in all the Candidate Keys.

(P)+ = {P,Q,T} => Not a Candidate Key

Now take 2-attributes combinations:
(PQ)+ = {P,Q,T} => Not a Candidate Key
(PR)+ = {P,R,Q,T} => Not a Candidate Key
(PS)+ = {P,S,Q,T,R} => Candidate Key
(PT)+ = {P,T,Q} => Not a Candidate Key

Now check for 3-attributes combinations:
(PQR)+ = {P,Q,R,T} => Not a Candidate Key
(PQS)+ => Super Key because PS is a Candidate Key already

Total no. of Candidate Keys possible: 2^n-1 = 2^5-1 = 32-1 = 31

This is how Candidate Keys can be found.

Do let me know if you enjoyed it!
Thank You.

Discussion (0)