Advanced Database Management System - Tutorials and Notes: Find all the candidate keys of a relation

Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Wednesday, 15 April 2020

Find all the candidate keys of a relation

Finding all candidate keys of a relation, Steps to find the candidate keys of a relational table


Finding candidate keys in a relational table - Solved exercise


Question:
Given the following relation R and the set of functional dependencies F that hold on R, find all candidate keys for R.
R (A, B, C, D, E, F)
F = {AB → C, AC → B, AD → E, BC → A, E → F}

Solution:
Let us follow the steps given in the box below to find all the candidate keys of R.
Step 1: Let γ = set of attributes not present in the RHS of any FD. The set of attributes in γ must be a part of any candidate key of R.
Step 2: Let β = set of attributes appear on RHS but not on LHS of any FD. The set of attributes in β cannot be a part of any candidate key of R.
Step 3: Find closure γ+. if γ+ = R, then γ  is the only candidate key
Step 4: If γ+ ≠ R, then for each attribute x in R- β,
·        Test whether γ U {x} is a candidate key.
·        If not, add another attribute from R- β to γ and test whether it is a candidate key
·        Repeat this step until all candidate keys found

Given,
R (A, B, C, D, E, F) and F = {AB → C, AC → B, AD → E, BC → A, E → F}
Step 1: Find the set γ of attributes that are not present in the RHS of any functional dependency.
D is the only attribute that is not present in RHS of any of the functional dependencies. Hence, the candidate key(s) must have the attribute D.
γ = {D}
Step 2: Find the attributes that appear on RHS but not on LHS of any FD.
F is the only attribute that appear on RHS but not on LHS. Hence, F cannot be part of any candidate keys of R.
β = {F}
Step 3: Find closure of γ, ie., γ+
γ+ = D+ =
γ+ ≠ R, hence we move on to step 4.
Step 4: Find R- β and combine each attribute from this set with D and find the closures.
R- β = {A, B, C, D, E, F} – {F} = { A, B, C, D, E}
Let’s combine D with each of the element from the above set to test for candidate keys. Keep in mind that our candidate keys must consist of D in it but not F. Let us do one by one as follows;
(AD)+         = AD
                   = ADE from FD AD → E
                   = ADEF from FD E → F
                   ≠ R.
Hence, AD is not a candidate key. We try the others the same way.
(BD)+ = BD ≠ R.
(CD)+ = CD ≠ R.
(DE)+ = DEF ≠ R.
Now let us add one more attribute to check for candidate keys;
(ABD)+ = ABDCEF = R. Hence, (ABD) is a candidate key.
(ACD)+ = ACDBEF = R. Hence, (ACD) is a candidate key.
(AED)+ = AEDF ≠ R.
(BCD)+ = BCDAEF = R. Hence, (BCD) is a candidate key.
(BED)+ = BEDF ≠ R.
(CED)+ = CEDF ≠ R.
(ABCD)+ = ABCDEF = R. But (ABCD) is not a candidate key. It is a super key, because its subset consists of keys.
Result:
ABD, ACD, and BCD are the candidate keys of R.

**********

Go back to Normalization – solved exercises page.

Go to How to find closure page 

Go to Database Closures - Home page

Go to 2NF, 3NF and BCNF






Find all candidate keys of a relation in RDBMS

How to find candidate keys in a relational database for normalization

steps to find candidate keys

Easy way to find candidate keys

Candidate keys solved exercise

Candidate keys for normalization





No comments:

Post a comment

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