# Lec 8: Finding number of candidate keys in relation - part 2 | DBMS **Channel:** Jenny's Lectures CS IT **Source:** https://www.youtube.com/watch?v=jFlxFODMLYw **Transcript page:** https://www.withtranscript.ai/video/jFlxFODMLYw ## Chapters - 0:00 — Reviewing Candidate Key Shortcut Method - 2:42 — Deriving the First Candidate Key - 7:08 — Finding Additional Candidate Keys - 13:43 — Alternative Reduction Paths and Summary - 20:21 — Transition to Normalization ## Transcript **[0:00]:** So in the previous video, we have discussed how to find out all the candidate keys from a given relation with the help of a short tree, right? There we have taken a simple example and we have discussed that method, right? Now, I have given you one question in the last video, right? You have to tell me that the number of candidate keys present in the given relation, right? And what are those keys? **[0:22]:** So the answer of that question is in that relation, four candidate keys are present and these are those four candidate keys, right? Now we will take a complex problem, right? And we will see with the help of that shortcut that how to find out the number of candidate keys present in a given relation relation is given having these attributes, right? And these are the functional dependencies given on this relation. Now the question is you have to find out the number of candidate keys in this relation, right? How many candidate keys are there and what are those candidate keys, right? Now the simple trick I have told you in that trick, the first step is what? Obviously candidate key is what, a super key. Or you can say a minimal super key. A super key whose proper subset is not a super key, right? **[1:14]:** And super key is what? A set of attributes whose attribute closer contains all all the attributes of a given relation. I have already discussed, right? What is attribute closure, how to find it? What is functional dependency in the previous videos? You can check out those videos right? Now the very first step is what? Definitely this would be a super key here. **[1:39]:** If I take the complete set of these relation A, B, C, D, E, F, right? And if you take the closer, right? Then the closure will contain all the attribute of this relation. **[1:53]:** So definitely it would be a super key, right? Because I'm taking all the attribute, definitely that would be a super key. That is very simple. Or you can say that that is common sense. Now, now you have to find out which attribute you can discard from the super key. **[2:10]:** See, this is having 1, 2, 3, 4, 5, 6, 6 attributes. So almost 2 raised to power 6 subset would be there or 2 raised to power 6 minus 2 proper subset would be there to check all the proper subset that that proper subset is a super key or not, right? Obviously to find out candidate keys we have to check the proper subset of super keys, right? So that would be lengthy process. So the simple trick is just discard the attributes from here. **[2:37]:** Now check which attribute you can discard from this key. Now check the dependency is given. **[2:42]:** See ab. Both can determine C. It means if you have AB with U, then you can determine C. With the help of ab, you can determine AB because of reflexivity property as well as from ab you can determine C. So from here I can discard C because I have AB. Right now super key is A, B, D, E, F. This is super key. **[3:07]:** You can take this attribute closer and check see ab. Definitely that would determine itself because of reflexivity property and A B determines C. Do you have a B? Yes. So it can determine C and these can determine itself. So this is also a super key. **[3:27]:** Now check which attribute you can discard. Now see, AB can determine C and C determines de. So now because of reflex. Sorry, that transitivity property AB can determine de. I have already discussed all the Armstrong axioms. You can check out that video in the side button. Right. AB determines C. C determine de. It means indirectly you can say AB determine de. Do you have ab? Yes. So I can discard A DE because AB can determine de. Right. So now the super key is ab F. If you want to check out that still it is a super key or not. So you can check. You can find out the attribute closure of this key. See ABF because of reflexivity. That would definitely be here. Now C, check the functional dependency A B determines C. Do you have a B? Yes, I have A, B both. **[4:22]:** So I can write down here C. Right. Now C can determine D. Do you have C? Yes, I have C. So I can write down here de. You can check out attribute closure of this is having complete set of attributes of a relation. So this is still a super key. **[4:36]:** Right now check. Now you can discard anything. Check A, B can determine C. Fine. So C can determine. Can I write here? **[4:48]:** C can determine D and C can determine E. Obviously I can split it because of that splitting property or decomposition property. Right. You can apply split to the right right hand side, not to the left hand side. Here I cannot write A will determine C. B will determine C. No, you can split on only the right hand side. You can split the dependent only you cannot split the determinant. **[5:12]:** Now C C can determine E and E can determine F. Right. It means using that transitivity property, can we say A? B will determine E. Yes, AB determines C. Right. C determine E. It means AB will determine E. E determine F means AB will determine F. Sorry, F, not E. Right. So here I can discard F because I have ab. **[5:46]:** Using AB I can determine F. So no need to write down F. Now we are left with AB only. Right? You can check out the closure. Closure of this will contain all the attributes ab, AB determines C. So I can write down C. C will determine de. I can Write down DE E will determine F. I have E, So this will determine F. Right? **[6:06]:** So AB is still a super key. Fine. Now now you cannot discard anything, right? You can check out the functional dependency. Now you cannot discard anything. Now this is super key. Now check is this candidate key or not? For this you need to check out what all the proper subset of a B. Proper subset of A B is one is A, another is B. Right? **[6:30]:** Now check A is super Q or not B super Q. Note how to check. Take the attribute closer of A and B. Right? Now attribute closure of A will definitely contain A. **[6:40]:** Now see, A is determining nothing because both AB are determining C. But I have only A. So attribute closure of A is a. Attribute closure of is B is only B. Right? So this is not super key. This is not super key. So no proper subset of A of AB is super key. So that is why I can say that A B is candidate key. Definitely. Right. **[7:05]:** Now we got one candidate key. **[7:08]:** Fine. Now after that it is very simple. Now you need to check still there are another candidate he is present in the relation or not. How to check that thing? **[7:18]:** See, now prime attributes are. Check out the prime attributes. First of all, all the attributes which are making candidate key. Those are prime attributes. At this point of time we have only one candidate key ab. **[7:32]:** So prime attributes are A, B, two prime attributes we have. Fine. Now check. If prime attribute are present to the right hand side of any functional dependency, then you can say definitely there would be more candidate keys present in the relation and you have to find it out. Fine. **[7:54]:** Check attribute are A and B. A check out is a present on the right hand side of any functional dependency. Yes. Here D will determine A. Here A is present to the right hand side of D this functional dependency. **[8:11]:** Right? So now it means you have more candidate keys in this relation, right? You need to find out those. How to find out those? Now you replace this A with D in this the candidate key you have. **[8:27]:** Now we have A replace this A with D. So I have now D B. But here. Now you cannot say that DB will be a candidate key. No. Yes, I can say that DB is super key definitely. But I cannot say that it is definitely a candidate key. How to check out this thing? Make the proper subset of DB1 is D, another is B2 proper subset would be there, right? B I have already checked. This is not a super key. Now check out for D. How to check out? Find out the closure of D in the closer I have. First of all D. Now D is determining A. So I can write down here A because I have D. Now A is determining anything. No, because both AB is determining C. But I have only A. I don't have B. **[9:15]:** So now attribute closure of D is da. So this is also not a super key. Now you can say that this is also a candidate key. Because no proper subset of DB is super key. So this is candidate key. Now we got second candidate key. Now the prime attributes are. One more attribute is there that is D. So we will add one more attribute that is D here. Fine. Now C. Another is what A is present here. We have already taken this. See, B is also present to the right hand side of this functional dependency. So now see, at starting when I I was having A B. Then I have replaced A. Then I got this thing second option was you can replace this B. You will replace this B with C. So now I got a C. Right, two options we have at the starting one with this one, One is this one. **[10:08]:** So this is definitely a super key. But I cannot say that this is definitely a candidate key. You need to check out the proper subset. Proper subset of this is what one is A. One is C. C A is not a proper subset. I have already checked it out. One remaining is C. So how to check out the C is a super key or not? Find out the attribute closure of C. Now definitely I can write here C in the functional dependencies. Now C can determine D. Do you have C? Yes, I have C. So I can write down here D E. Right. Now E. See, E can determine F. Do you have E? Yes, so I can determine F. Now D can determine A. Do you have D? Yes, I have D. So I can determine A. **[10:50]:** See, C can determine B. Do you have C? Yes, I have C. So I can determine B. See now ab, C, D, E, F. All the attributes are there in the closure of C. So now C is what? A super P. So now we cannot say that this is a candidate key because proper subset of AC is C and C is a super key. **[11:15]:** So now AC is not a candidate key. Right? This is the case. That is why I was saying that after replacing directly, we cannot say that that would be a candidate key. You need to check it out, you need to verify it. **[11:28]:** So AC is not a candidate key. Now see, C is a super key. Okay, fine. Now proper subset of C would be what? Definitely phi. And phi cannot be a super key because phi set of attribute cannot determine any attribute in a relation. So now you can say that C is definitely a candidate key. Right? Because no proper subset of C would be a super key. So now C is also a candidate key. We have got three candidate key. One is ab, one is db, one is C. Right. Now one more prime attribute you have to add that is C. Now fine. Now check. We have taken this A and B. Now check. Is D present any right hand side of any functional dependency? Yes, Here we got. Fine. See this means C determine D. C determine E. Right. **[12:26]:** So now see, D is present to the right hand side of this functional dependency. Means at the place of D you can replace C. So here I have D. So here. So sorry, C is also a candidate key. One is this one. One is this one. **[12:41]:** So now at the place of D I can replace C means here C, B after replacing. Now this is definitely a super key. But we cannot say that this is a candidate key. You need to check it out. Find out proper subset. Proper subset 1 is B. B is not a super key. One is C. C is a super key. I have already checked it out. So this is not a candidate key. **[13:03]:** Right? Definitely. Now C is candidate key that I have already taken. Fine. Now check. What about C? Is C present on the right hand side of any functional dependency? Yes. Now at the place of C you can replace it with ab. So when you replace the C with AB, then you got this one and this thing. I have already discussed that this is a candidate key. I have already got this one as a candidate key. So now no need to replace this thing. Fine. So now at this point of time we have checked for all the prime attributes are present on the right hand side or not. We have replaced and we have got three candidate keys in this relation. **[13:43]:** One is ab, one is this, one BD and one is C. And prime attributes are A, B, C, A, B, C and D. The attributes which are making candidate keys, those are prime attributes. And non prime attributes are E and F in this relation. Fine. So this is how you can find out with that trick all the number of candidate keys present in a relation. **[14:11]:** Now see, when you solve this one, when you are discarding these attributes, it is not necessary that you will get ab. First of all, maybe, maybe someone is getting like this. See. Now when you are discarding attribute means AB will determine C. So you will discard C. Fine. Now you will not apply the transitivity rule and you will check another functional dependency. C is determining D. Do you have C? No. So I cannot discard De. E can determine F, so I have E. So I can discard F. Because if E is there with you, then you can determine F. So no need to write down F. Now check again. Next is D can determine A, so I have D, so I can discard A. C can determine B, but I don't have C. So the remaining is B, T, E. Maybe someone can get this thing after discarding the attributes. **[15:05]:** Not ab. It's okay. Now see is BD is a super key. Find out the proper subset. Obviously we have B, D and E. Right? So now check out the functional dependencies. A, B can determine C. We don't have A. B, C can determine de. I don't have C. E can determine F. I have E, so I can determine F. D can determine A. I have D. I, I can determine A. **[15:30]:** C can determine B, but I don't have C. Again, check repetition. AB can determine C. Do you have ab? Now I have ab, so now I can determine C. Right now all the attributes are there. So BD is a. BDE is a super key. Now I cannot discard anything. **[15:48]:** Right now at this point of time you need to check out the proper subset of this thing bd, de, be, and bde. Now six proper subset are there, so you need to check out these proper subsets. So try to reduce. Try to discard as many attribute as you can by applying maybe that Armstrong axioms transitivity property or something like this. Right here I haven't applied any transitivity property. **[16:19]:** So I am left with BDE3 attributes. So that is why now I have to check for six proper subset. And here I got only two attributes. So two proper subsets are there, A and B. So that is simple. So try to discard as many attributes as you can by applying some rules that Armstrong axioms. So here check BD closer I can write bd yes, reflexivity rule. Check out the functional dependencies. AB can determine C. I don't have AB. C can determine I don't have C. E can determine F. D can determine A. Yes, I have D, so I can determine A. Now C. This I have used C can determine B, but C I don't have. Now again check again. Repetition. AB can determine C. Now do you have ab? Yes, I have AB both. So now I can write down here C C can determine de. **[17:14]:** So I can write down here D I have already written so E. So now E can determine F. C. So now all the attributes are there. So BD is a super key. So definitely this would not be a candidate key because proper subset of this one bd. **[17:32]:** Right. And this is a super key. So I cannot say that this would be a candidate key. Right? So now take this bd. **[17:41]:** Now check for this one. Is there any chance of BD to be a candidate key? How to check proper subset R, B and D. B is not a super key. D is also not a super key. So definitely BD is a candidate key. **[17:54]:** Now this if you follow this approach, if you, you know after discarding, if you go to bde. So at this approach the first candidate key you got is B D. And here we got ab. No problem, just stick to the rules. Right, now the prime attributes are B and D. Now check prime attributes are available on the right hand side or not? Yes, B is available at the right hand side, right? **[18:21]:** D is also available. So here also after replacing you will get two thing. BD is candidate key. So at the place of B I can write down C. So CD is there. Now D is also right hand side of this functional dependency. So at the place of D I can write down C. So here I have bc. So check out for this. This is a candidate key or not? This is a candidate key or not, right? But C is a proper subset and C is super key. So this is not a candidate key. This is also not candidate key. Candidate key you got is what C Now so next candidate key you got is C. So prime attribute is C. Again you can check C is available on the right hand side or something is not, right? And after that you will get ab. So answer would be same, right? **[19:07]:** Maybe your approach of discarding the attributes may be different, but answer you would get will be same. So this is how with this trick you can find out all the candidate keys in a given relation, right? Whether simple dependencies are given or complex like this, dependencies are given. Fine, just stick to the rules. First take all the attributes, discard as many attributes as you can after discarding. If you are not able to discard any more attributes, find out the proper subset of that super key. If proper subset is not super key, then that would be candidate key. Once you got first candidate key you means you will get prime attributes. Once you got prime attributes then check prime attributes are available on the right hand side of functional dependencies or not. If available then definitely there would be more candidate keys present. If not, then only one candidate key would be there, right? **[20:01]:** If prime attributes are present on the right hand side, then replace use that functional dependencies and replace that attribute in the candidate key with that left hand side attribute of the functional dependency. Fine. Like this you will get all the possible candidate keys in that relation. **[20:21]:** Fine. **[20:22]:** So now in the next video, from the next video I'll start normalization. I hope you got the concept of functional dependency attribute closure. How to find out the candidate is in a relation. These are very important topics. If you got these topics, then only you can get normalization concept very easily, right? **[20:39]:** So from the next video I'm going to start normalization. So now I'll see you in the next video. Till then, bye bye. Take care.