Tuesday, August 26, 2014

How to find closure of attributes in DBMS?




Closure of Attribute Set / Closure of Attribute Set Algorithm / How do we find a key given a set of attributes? / How to find super key? / Attribute Closure in DBMS / Closure of Attributes Set Example / How to find key for a relation?


Closure of Attribute Set

After finding a set of functional dependencies that are hold on a relation, the next step is to find the Super key for that relation (table). The set of identified functional dependencies play a vital role in finding the key for the relation. We can decide whether an attribute (or set of attributes) of any table is a key for that table or not by identifying the attribute or set of attributes’ closure. If A is an attribute, (or set of attributes) then its attribute closure is denoted as A+.

Algorithm:

The following algorithm will help us in finding the closure of an attribute;
result := A;
while (changes to result) do
for each functional dependency B C in F do
begin
if B result then result := result C;
end
Let us discuss this algorithm with an example;
Assume a relation schema R = (A, B, C) with the set of functional dependencies F = {A B, B C}. Now, we can find the attribute closure of attribute A as follows;
Step 1: We start with the attribute in question as the initial result. Hence, result = A.
Step 2: Take the first FD A B. Its left hand side (i.e, A) is in the result, hence the right hand side can be included with the result. This lead to result = AB.
Step 3: Take the second FD B C. Its left hand side (i.e, B) is in the result (or subset of result), hence the right hand side can be included with the result. Now, result = ABC.
We have no more attributes. Hence the algorithm exits. As the result, A+ includes all the attributes of relation R. now we would say A+ is ABC. And, A is one of the keys of the relation R.

Example:

Question:
Consider a relation R with the schema R(A, B, C, D, E, F) with a set of functional dependencies F as follows;
{AB C, BC AD, D E, CF B}
Find the super key for this relation.

Solution:
Finding (AB)+
First, let us find (AB)+ , the closure of attribute set AB (We do not need to test all the attributes individually. Instead we can try with those attributes that are on the left hand side of any FD.)
·         result = AB
·         As AB determines C, C can be included with the result. Hence, result = AB U C = ABC.
·         According to second FD BC AD, the attributes B and C together can identify both A and D. Hence, result = ABC U AD = ABCD
·         If you know D, you will know E according to third FD D E. so, result = ABCD U E = ABCDE.
·         F cannot be identified by any of these FDs. And our result can include ABCDE attributes only.
Hence, the solution is AB is not the key for R. The reason is, the closure of AB, i.e., (AB)+ does not include all the attributes of R in the result.
Finding (ABF)+
Then what would be the key for R?. As I told you initially, we can try all the left hand side attributes (because they are the determiners), or some of their combination. From the above example, we would get an idea to include F as one of the key attribute. So, let us try to find (ABF)+ , the closure of attribute set ABF.
·         result = ABF
·         from the above example, we could say (AB)+ = ABCDE
·         we know C and F, then according to CF B, we would deduce the result as ABCDEF, which includes all the attributes from R.
Hence, the solution is ABF is one of the key for R. because, (ABF)+ includes all the attributes of R.

Go to Normalization Exercises - Solved page

Go to How to find closure of set of functional dependencies page



Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery