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.
Also see, Database Management System
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 }
|
85+ registered