Finding Attribute Closure and Candidate Keys

Amisha Purswani
Last Updated: May 13, 2022

Introduction

Closure of an attribute set refers to the set of all attributes that can be functionally determined from an attribute set.

A key is a set of attributes that can be used to differentiate each tuple in a relation. A candidate key is a set of attributes that can uniquely identify each tuple in a relation. A candidate key is a name given to a minimal super key.

In this blog, we will learn the various methods of finding attribute closure and candidate keys.

Finding Attribute Closure

Closure of an attribute set is the set of all those attributes that can be functionally determined from that attribute set. For finding the attribute closure, we first need all the functional dependencies in the table. In relation, a functional dependency A->B exists if two tuples with the same value of attribute A also have the same value of attribute B.

For example, In the given EMPLOYEE table.

EMP_NO

NAME

PHONE

ADDRESS

AGE

1

AA

111

Surat

28

2

BB

222

Ahmedabad

29

3

CC

333

Pune

29

4

DD

444

Ahmedabad

30

 

Functional Dependencies

EMP_NO -> NAME, EMP_NO->PHONE is valid

but

NAME -> ADDRESS does not hold

The domain of the relationship determines a relation's functional dependencies. In the same example, we know that EMP_NO is unique for each employee. So, EMP_NO -> NAME, EMP_NO->PHONE,EMP_NO->ADDRESS,and EMP_NO->AGE all will be valid functional dependencies. Similarly, we know that PHONE is also unique for each employee.

A relation's functional dependency set, or FD set, collects all FDs in the relation. For Example, FD set for the EMPLOYEE table shown is: 

EMP_NO->NAME

EMP_NO->PHONE

EMP_NO->ADDRESS

EMP_NO->AGE

PHONE->NAME

PHONE->ADDRESS

PHONE->EMP_NO

PHONE->AGE

To find attribute closure of an attribute set:

  • Add attribute set elements to the result set.
  • Add recursively to the result set elements that can be functionally determined from the result set items.


Given a set of attributes α, the Closure of α under F is the set of attributes that are 

functionally determined by α under F. 

Which is denoted by α+.

Pseudo Code:

 result =  α; 

 while (changes to result) do 

       for each a->b   in F do 

            begin 

                if a   result then  result = result ∪ b   

            end 

Example

Consider the relation schema below.

Depositer_Account(id,acc_num,access_date,balance, and branch_name).

A set of functional dependencies F can be specified for this relation as 

F = { {id, acc_num} → access_date and acc_num → {balance, branch_name} } 

Find out the closure of {id, acc_num} and acc_num. 

Solution: 

Finding out { id, acc_num }+ 

 

Step-1 : { id, acc_num }+ = { id, acc_num }  

   

Step-2 : { id, acc_num }+ = { id, acc_num, acess_date }                    

               Since {id, acc_num} → access_date

 

  { id, acc_num }+ = { id, acc_num, acess_date, balance, branch_name }             

          Since acc_num → {balance, branch_name}

 

Step-3 :  { id, acc_num } + = { id, acc_num, acess_date, balance, branch_name } 

 

So { id, acc_num }+ = { id, acc_num, acess_date, balance, branch_name } 

 

Finding out acc_num+  

 

Step-1 :acc_num+ = acc_num     

 

Step-2 :acc_num+ = { ac_num, balance, branch_name }          

                       Since acc_num → {balance, branch_name} }    

 

Step-3 :acc_num+ = { acc_num, balance,branch_name } 

 

So acc_num+ = { acc_num, balance, branch_name } 

 

Finding Candidate key

A candidate key is a single or group of multiple keys that uniquely identify rows in a table. A candidate key is also called a super key without redundancy. A candidate key is not reducible further. The minimum set of attributes is used to uniquely differentiate the record of the table that you called a candidate key.

  • A candidate key can never be NULL or EMPTY and its value should be unique.
  • There can be more than one candidate key to a table
  • A candidate key can be a combination of more than one attribute.

Example

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

AB → C

C → D

B → E

Find the candidate keys.

Solution

Essential attributes of the relation Q are - A and B.

So, attributes A and B will be a part of every candidate key.

Now,

We will check if AB can determine all remaining attributes.

To check, we find the closure of AB.

So, we have

{ AB }+

= { A , B }

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

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

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

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

As a result, AB is the candidate key for the relation. 

FAQs

  1. What is the use for attribute closure?
    It is used to check whether an attribute (or set of attributes) forms a key or not. 
     
  2. What is a prime attribute?
    Prime attributes of the candidate key define the uniqueness (Eg: SSN number in an employee database). A primary key is a table column whose values uniquely identify the rows.
     
  3. What is the difference between primary key and candidate key??
    A primary key is a non-null key that uniquely identifies a record in a table.
    There can only be one primary key in a table. A candidate key is a unique key used to identify a record in a table. However, a table can have multiple candidate keys.
     
  4. What is the candidate key?
    A candidate key is also called a super key without redundancy. We can even say that a candidate key is the minimal set of attributes that uniquely identify a tuple.

Key Takeaways

In this blog, we have meticulously learned that the Closure of an attribute set is the set of all those attributes that may be functionally determined from that attribute set. A candidate key is a set of attributes that can uniquely identify each tuple in a table. We have learned how to find attribute closure and candidate key using examples. 

Ninja, don't stop here; check out the Top 100 SQL Problems to get hands-on experience with frequently asked interview questions and land your dream job. Also, try CodeStudio to practice programming problems for your complete interview preparation.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think