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?
- CD
- EC
- AE
- 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?
- { E, F }
- { E, F, H }
- { E, F, H, K, L }
- { 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?
- AE, BE
- AE, BE, DE
- AEH, BEH, BCH
- 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.
