Candidate Key

Candidate Key is a minimal set of attributes of a relationship that can be used to identify a tuple uniquely. For Example, each tuple of EMPLOYEE relation given in Table 1 can be uniquely identified by E-ID and it is minimal as well. So it will be the Candidate key of the relationship.

A candidate key may or may not be a primary key. Super Key is a set of attributes of a relationship that can be used to identify a tuple uniquely. For Example, each tuple of EMPLOYEE relation given in Table 1 can be uniquely identified by E-ID or (E-ID, E-NAME) or (E-ID, E-CITY) or (E-ID, E-STATE) or (E_ID, E-NAME, E-STATE), etc. So all of these are super keys of EMPLOYEE relation.

Note: A candidate key is always a super key but vice versa is not true.

Q.3 Finding Candidate Keys and Super Keys of a Relation using FD set.

The set of attributes whose attribute closure is a set of all attributes of the relation is called the super key of the relation. For Example, the EMPLOYEE relation shown in Table 1 has the following FD set. {E-ID->E-NAME, E-ID->E-CITY, E-ID->E-STATE, E-CITY->E-STATE}. Let us calculate the attribute closure of different sets of attributes:

(E-ID)+ = {E-ID, E-NAME,E-CITY,E-STATE}
(E-ID,E-NAME)+ = {E-ID, E-NAME,E-CITY,E-STATE}
(E-ID,E-CITY)+ = {E-ID, E-NAME,E-CITY,E-STATE}
(E-ID,E-STATE)+ = {E-ID, E-NAME,E-CITY,E-STATE}
(E-ID,E-CITY,E-STATE)+ = {E-ID, E-NAME,E-CITY,E-STATE}
(E-NAME)+ = {E-NAME}
(E-CITY)+ = {E-CITY,E-STATE}

As (E-ID)⁺, (E-ID, E-NAME)⁺, (E-ID, E-CITY)⁺, (E-ID, E-STATE)⁺, (E-ID, E-CITY, E-STATE)⁺ give set of all attributes of relation EMPLOYEE. So all of these are super keys of relation.

The minimal set of attributes whose attribute closure is a set of all attributes of relation is called the candidate key of the relation. As shown above, (E-ID)⁺ is a set of all attributes of relation and it is minimal. So E-ID will be the candidate key. On the other hand (E-ID, E-NAME)⁺ also is a set of all attributes but it is not minimal because its subset (E-ID)⁺ is equal to the set of all attributes. So (E-ID, E-NAME) is not a candidate key.

In this article, we will find the attribute closure and also we will find the candidate keys using the functional dependency. We will look into this topic in detail. But before proceeding to this topic, we will first learn about what is functional dependency.

A functional dependency X->Y in a relation holds if two tuples having the same value for X also have the same value for Y i.e. X uniquely determines Y. Consider the table given below.

In the EMPLOYEE relation given in Table,

• Functional Dependency E-ID->E-NAME holds because, for each E-ID, there is a unique value of E-NAME.
• Functional Dependency E-ID->E-CITY and E-CITY->E-STATE also holds.
• Functional Dependency E-NAME->E-ID does not hold because E-NAME ‘John’ is not uniquely determining E-ID. There are 2 E-IDs corresponding to John (E001 and E003).

Table EMPLOYEE

Table 1: The FD set for EMPLOYEE relation given in Table 1 are:

{E-ID->E-NAME, E-ID->E-CITY, E-ID->E-STATE, E-CITY->E-STATE}