CLOSURE OF ATTRIBUTES, FINDING CANDIDATE KEY, SUPER KEY , PRIME ATTRIBUTES AND NON PRIME ATTRIBUTES
CLOSURE OF ATTRIBUTE SETS
The set of all those attributes which can be functionally determined from an attribute set is called a closure of that attribute set.
Closure of the attribute set {X} is denoted as {X}+ .
Steps to Find Closure of an Attribute Set
Step 1: Add the attributes contained in the attribute set for which closure is being calculated to the result set.
Step 2: Recursively add the attributes to the result set which can be functionally determined from the attributes already contained in the result set.
Example
R ( A , B , C , D , E , F , G ) with the functional dependencies
A → BC
BC → DE
D → F
CF → G
Solution:
Now, let us find the closure of some attributes and attribute sets.
Closure of attribute A
A + = { A }
= { A , B , C } ( Using A → BC )
= { A , B , C , D , E } ( Using BC → DE )
= { A , B , C , D , E , F } ( Using D → F )
= { A , B , C , D , E , F , G } ( Using CF → G )
Thus, A + = { A , B , C , D , E , F , G }
Closure of attribute D
D + = { D }
= { D , F } ( Using D → F )
We can not determine any other attribute using attributes D and F contained in the result set. Thus, D + = { D , F }
Closure of attribute set {B, C}
{ B , C }+ = { B , C }
= { B , C , D , E } ( Using BC → DE )
= { B , C , D , E , F } ( Using D → F )
= { B , C , D , E , F , G } ( Using CF → G )
Thus, { B , C }+ = { B , C , D , E , F , G }
FINDING CANDIDATE KEY, SUPER KEY , PRIME ATTRIBUTES AND NON-PRIME ATTRIBUTES
FInd Candidate Key, Super Key , Prime Attributes and Non-Prime Attributes
R ( A , B , C , D ) with the functional dependencies
A → B
B → C
C → D
Solution:
Now, let us find the closure of attributes.
A + = { B,C,D,A }
Here A is a Candidate Key as it determines all attributes.
B + = { B,C,D } - Not a Candidate Key
C + = { C,D } - Not a Candidate Key
D + = { D } - Not a Candidate Key
Candidate Key-C.K={A}
Super Key-S.K={AB,AC,AD…etc}
Prime Attributes={A} // Attributes which helps in formation of Candidate Key
Non-Prime Attributes={B,C.D} //Attributes which does not help in formation of Candidate Key
Here A is the only Candidate Key , if we put together any other attribute with Candidate Key , it becomes Super Key .
R ( A , B , C , D ) with the functional dependencies
A → B
B → C
C → D
D → A
Solution:
Now, let us find the closure of attributes.
A + = { B,C,D,A }
Here A is a Candidate Key as it determines all attributes.
B + = { B,C,D,A } - Candidate Key
C + = { C,D,A,B } - Candidate Key
D + = { D,A,B,C } - Candidate Key
Candidate Key-C.K={A,B,C,D}
Prime Attributes={A,B,C,D} // Attributes which helps in formation of Candidate Key
Non-Prime Attributes={0} //Attributes which does not help in formation of Candidate Key
Here A is the only Candidate Key , if we put together any other attribute with Candidate Key , it becomes Super Key .
2. SECOND METHOD: Check for the attribute(s) which are NOT present on the Right Side of any Functional Dependency.
R ( A , B , C , D,E) with the functional dependencies
A → B
BC → D
E → C
D → A
Solution:
Step 1: Check which attributes are there in RHS of F.D
RHS attributes={ B,D,C,A} // all these attributes are getting determined except E
The attribute E is not present on the Right Side of any Functional Dependency. This means that the attribute E cannot be determined by any other attribute(s). Thus E must be present on the candidate key and also the super key.
E alone cannot be Candidate Key but will help in making of Candidate Key . Lets find closure of E.
E+={E,C}
To find Candidate Key , let us find closure of E with all other attributes .
AE+={A,B,E,C,D} - Candidate Key —---------------- 1
From above lets see if A is present in right hand side of any FD
D->A
Replace A with D in 1
DE+={D,E,A,B,C} - Candidate Key —---------------- 2
From above lets see if D is present in right hand side of any FD
BC->A
BE+={BCDAE}-Candidate Key
CE+={CE}- No Candidate Key
Candidate Key(CK)={AE, DE,BE}
Prime Attribute={A,B.D,E}
Non-Prime Attribute={C}
b) Consider a Relation
R (A, B, C, D, E, F)
Given Functional Dependencies (F):
AB→C
BC→AD
D→E
CF→B
Solution:
The attribute F is not present on the Right Side of any Functional Dependency. This means that the attribute F cannot be determined by any other attribute(s). Thus F must be present on the candidate key and also the super key.
So let's start with finding the closure of F.
F+ = {F}
From the given set of functional dependencies, the attribute F cannot determine any other attribute. Thus F canNOT be the Super Key.
Let's find the closure of the attribute CF.
{CF}+: = {CF} (because of the axiom of reflexivity)
= {CFB} (from the given dependency CF → B)
= {CFBAD} (from the given dependency BC → AD)
= {CFBADE} (from the given dependency D → E)
Finally {CF}+ = {CFBADE} or {ABCDEF}
Since CF can determine all other attributes, CF is a Candidate Key.
And all the combinations of CF with or without other attribute(s) are Super Keys.
For example,
CF, CFA, CFB, CFA, CFD, CFE, ABCDF, ABCFE, etc are Super Keys.
Question :
Consider a relation
R ( A , B , C , D,E) with the functional dependencies
AB→ C
BC → D
C → E
Find the Candidate Keys and the number of Super Key.
Solution:
Lets use the second method , and find the attributes whuch are not present in RHS of functional depenndency.
R={A,B,C,D,E}, here AB are not present in RHS so they should be present in formation of Candidate Keys
Lets find the closure of AB
AB+={A,B,C,D,E} - AB is a Candidate Key
From AB we get C and from C get E , so find closure of C+ and E+ . Both of them are not Candidate Keys.
Hence only AB is the Candiadte Key .
Finding Super Key :
Lets see the attributes of AB+={A,B,C,D,E}
find the probablity of occurance of each attrubutes of Candidate Key .
A B C D E
1* 1 * 2 * 2 * 2
Here, 1 means it must occur and 2 means it can occur or cannot occur in formation of Super Key . If we find the product we get the answer 8. Hence , We will have Super Key in the relation,