Candidate Key | Finding Candidate Keys | Examples

Keys in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Keys in DBMS.

 

We have discussed-

  • A key is a set of attributes that can identify each tuple uniquely in the given relation.
  • There are various types of keys in DBMS-

 

 

In this article, we will discuss how to find candidate keys of a given relation.

 

Candidate Key-

 

A candidate key may be defined as-

 

A set of minimal attribute(s) that can identify each tuple uniquely in the given relation is called as a candidate key.

OR

A minimal super key is called as a candidate key.

 

For any given relation,

  • It is possible to have multiple candidate keys.
  • There exists no general formula to find the total number of candidate keys of a given relation.

 

Example-

 

Consider the following Student schema-

Student ( roll , name , sex , age , address , class , section )

 

Given below are the examples of candidate keys-

  • ( class , section , roll )
  • ( name , address )

 

These are candidate keys because each set consists of minimal attributes required to identify each student uniquely in the Student table.

 

Finding Candidate Keys-

 

We can determine the candidate keys of a given relation using the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes are those attributes which are not present on RHS of any functional dependency.
  • Essential attributes are always a part of every candidate key.
  • This is because they can not be determined by other attributes.

 

Example

 

Let R(A, B, C, D, E, F) be a relation scheme with the following functional dependencies-

A → B

C → D

D → E

 

Here, the attributes which are not present on RHS of any functional dependency are A, C and F.

So, essential attributes are- A, C and F.

 

Step-02:

 

  • The remaining attributes of the relation are non-essential attributes.
  • This is because they can be determined by using essential attributes.

 

Now, following two cases are possible-

 

Case-01:

 

If all essential attributes together can determine all remaining non-essential attributes, then-

  • The combination of essential attributes is the candidate key.
  • It is the only possible candidate key.

 

Case-02:

 

If all essential attributes together can not determine all remaining non-essential attributes, then-

  • The set of essential attributes and some non-essential attributes will be the candidate key(s).
  • In this case, multiple candidate keys are possible.
  • To find the candidate keys, we check different combinations of essential and non-essential attributes.

 

We will further understand how to find candidate keys with the help of following problems.

The following practice problems are based on Case-01.

 

PRACTICE PROBLEMS BASED ON FINDING CANDIDATE KEYS-

 

Problem-01:

 

Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies-

C → F

E → A

EC → D

A → B

Which of the following is a key for R?

  1. CD
  2. EC
  3. AE
  4. AC

 

Also, determine the total number of candidate keys and super keys.

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- C and E.
  • So, attributes C and E will definitely be a part of every candidate key.

 

Step-02:

 

Now,

  • We will check if the essential attributes together can determine all remaining non-essential attributes.
  • To check, we find the closure of CE.

 

So, we have-

{ CE }+

= { C , E }

= { C , E , F }                       ( Using C → F )

= { A , C , E , F }                  ( Using E → A )

= { A , C , D , E , F }            ( Using EC → D )

= { A , B , C , D , E , F }       ( Using A → B )

 

We conclude that CE can determine all the attributes of the given relation.

So, CE is the only possible candidate key of the relation.

 

Thus, Option (B) is correct.

 

Total Number of Candidate Keys-

 

Only one candidate key CE is possible.

 

Total Number of Super Keys-

 

There are total 6 attributes in the given relation of which-

  • There are 2 essential attributes- C and E.
  • Remaining 4 attributes are non-essential attributes.
  • Essential attributes will be definitely present in every key.
  • Non-essential attributes may or may not be taken in every super key.

 

 

So, number of super keys possible = 2 x 2 x 2 x 2 = 16.

Thus, total number of super keys possible = 16.

 

Problem-02:

 

Let R = (A, B, C, D, E) be a relation scheme with the following dependencies-

AB → C

C → D

B → E

Determine the total number of candidate keys and super keys.

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- A and B.
  • So, attributes A and B will definitely be a part of every candidate key.

 

Step-02:

 

Now,

  • We will check if the essential attributes together can determine all remaining non-essential attributes.
  • To check, we find the closure of AB.

 

So, we have-

{ AB }+

= { A , B }

= { A , B , C }                     ( Using AB → C )

= { A , B , C , D }               ( Using C → D )

= { A , B , C , D , E }          ( Using B → E )

 

We conclude that AB can determine all the attributes of the given relation.

Thus, AB is the only possible candidate key of the relation.

 

Total Number of Candidate Keys-

 

Only one candidate key AB is possible.

 

Total Number of Super Keys-

 

There are total 5 attributes in the given relation of which-

  • There are 2 essential attributes- A and B.
  • Remaining 3 attributes are non-essential attributes.
  • Essential attributes will be definitely present in every key.
  • Non-essential attributes may or may not be taken in every super key.

 

 

So, number of super keys possible = 2 x 2 x 2 = 8.

Thus, total number of super keys possible = 8.

 

Problem-03:

 

Consider the relation scheme R(E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies-

{ E, F } → { G }

{ F } → { I , J }

{ E, H } → { K, L }

{ K } → { M }

{ L } → { N }

 

What is the key for R?

  1. { E, F }
  2. { E, F, H }
  3. { E, F, H, K, L }
  4. { E }

 

Also, determine the total number of candidate keys and super keys.

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- E, F and H.
  • So, attributes E, F and H will definitely be a part of every candidate key.

 

Step-02:

 

Now,

  • We will check if the essential attributes together can determine all remaining non-essential attributes.
  • To check, we find the closure of EFH.

 

So, we have-

{ EFH }+

= { E , F , H }

= { E , F , G , H }                                ( Using EF → G )

= { E , F , G , H , I , J }                       ( Using F → IJ )

= { E , F , G , H , I , J , K , L }             ( Using EH → KL )

= { E , F , G , H , I , J , K , L , M }       ( Using K → M )

= { E , F , G , H , I , J , K , L , M , N } ( Using L → N )

 

We conclude that EFH can determine all the attributes of the given relation.

So, EFH is the only possible candidate key of the relation.

 

Thus, Option (B) is correct.

 

Total Number of Candidate Keys-

 

Only one candidate key EFH is possible.

 

Total Number of Super Keys-

 

There are total 10 attributes in the given relation of which-

  • There are 3 essential attributes- E, F and H.
  • Remaining 7 attributes are non-essential attributes.
  • Essential attributes will be definitely present in every key.
  • Non-essential attributes may or may not be taken in every super key.

 

 

So, number of super keys possible = 2 x 2 x 2 x 2 x 2 x 2 x 2 = 128.

Thus, total number of super keys possible = 128.

 

Problem-04:

 

Consider the relation scheme R(A, B, C, D, E, H) and the set of functional dependencies-

A → B

BC → D

E → C

D → A

 

What are the candidate keys of R?

  1. AE, BE
  2. AE, BE, DE
  3. AEH, BEH, BCH
  4. AEH, BEH, DEH

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- E and H.
  • So, attributes E and H will definitely be a part of every candidate key.

 

The only possible option is (D).

Thus, Option (D) is correct.

 

Next Article- Functional Dependency in DBMS

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Candidate Key | Finding Candidate Keys | Examples
Article Name
Candidate Key | Finding Candidate Keys | Examples
Description
A candidate key is defined as a set of minimal attributes that can identify each tuple uniquely in the given relation. Examples. How to find Candidate Keys- To find candidate keys of any given relation, we follow the discussed steps.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-