Database Management System Lecture Notes PDF

# Database Management System ## LECTURE - 7: Finding Candidate Key **By - Puneet Kaur** ## Recap - SQL: Part 2 ## TOPICS - Finding Candidate Key ## Topic: Finding Candidate Key ### Content: 1. Functional Dependency 2. Candidate Key 3. Super Key 4. Prime Attribute ### Functional Dependency...

# Database Management System ## LECTURE - 7: Finding Candidate Key **By - Puneet Kaur** ## Recap - SQL: Part 2 ## TOPICS - Finding Candidate Key ## Topic: Finding Candidate Key ### Content: 1. Functional Dependency 2. Candidate Key 3. Super Key 4. Prime Attribute ### Functional Dependency A functional dependency (FD) is a relationship between two attributes typically between the PK and other non-key attributes within a table. For any relation R, attribute N is functionally dependent on attribute M (usually the PK) if for every valid instance of X that value of M uniquely determines the value of N. The relationship is indicated by the representation below: M------> N **Determinant** **Dependent** The left side of the above FD diagram is called **determinant** and the right side is the **dependent**. ### Candidate Key - A super key, whose no proper subset forms a Super Key is called a candidate key. - Thus, candidate key is a minimal super key (i.e. a Super Key having no extraneous attributes). - An entity set may have more than one candidate Keys. **E.g.: AB is a super key If proper subset of B is not SK, then AB is a candidate key.** ### Shortcut to Determine Candidate Key **NOTE:** This shortcut is applicable in most cases but not all. **Rule:** The attributes not existing on **RHS** of any **FD** will definitely be the part of a **Candidate Key**. **E.g.: R(ABCDEF) FD: | A → C | C → P | D → B | E → F **Find closure of AE. **AE**+ = {ACDBEF} Since all attributes are determined from **AE**+, AE is a Candidate Key. ### Prime Attributes - Attributes, which are part of a Candidate Key. **E.g. A, E** ### Non-Prime Attributes - Attributes which are not the part of a Candidate Key. **E.g. B, C, D, F** **E.g.: R(ABCDE) Candidate Key is: - AB - AD - BC - DE FD: | A → B | AB → C | BC → E | BD → E **Find closure of AD **AD**+ = {ABCDE} ∴ AD is a Candidate key.** **E.g.: R(ABCDEFGH) FD: | C → G | A → BC | B → CFH | E → A | F → EG **Find closure of D **D**+ = {DBCFHEGJ} Attribute D is not on RHS. ..D will surely be the part of the Candidate Key. **{D}+ = D** ∴ D alone is not CK **Possible Candidate Keys = {DA, DB, DE, D, AS}** **E.g.: R(ABCD) FD: | BC → A | AD → B | CD → B | AC → D **Find closure of CA **CA**+ = {CEBADV} checkmark **Find closure of CB **CB**+ = {CEBADAS} checkmark Candidate Keys? - {CA, CB, CO} -{CA, CB, CD} - {CA, CO} -{CA, CS} ### LONG METHOD **R(ABCDEF) FD: | AB → C | CD → DE | EF → F | D → A | C → B **Find closure of {A, B, C, D, E, F} **{ABCDEFS}+ = {ABCDEFS} checkmark **Find closure of {ABDEFS} **{ABDEFS}+ = {ABCDEFS} checkmark **Find closure of {ABCDEFS} **{ABCDEFS}+ = {ABCDEFS} checkmark **Find closure of {ABCDEFS} **{ABCDEFS}+ = {ABCDEFS} checkmark **Find closure of {ABDEFS} **{ABDEFS}+ = {ABCDEFS} checkmark Super Key = {ABCDEFS} Check if AB is a Candidate Key {AB} {A} Proper Subsest {B} **Find closure of A **{A}+ = A **Find closure of B **{B}+ = B Proper subset of AB is not SK. ∴ AB is a Candidate Key. **Find closure of {A1B} all attributes = {A1B} **Rule:** If Prime attributes are existing on RHS of any FD, then we have more Candidate Keys. **E.g .:D → A** Prime attribute A is on RHS of FD. .. we have more Candidate Key **Find closure of DB {DB} <--- Proper subset {D} <br> {B } **Find closure of D **{D}+ = {D, A} **Find closure of B **{B}+ = {B} No Proper subset is OK ∴ DB is a Candidate Key. **Find closure of AC **{AC} <--- Proper subset {A} {C} <br> **Find closure of A **{A}+ = {A, B} **Find closure of C **{C}+ = {C, D, E, B, A} Proper subset is form a SK. ∴ AC is not a Candidate Key. **Find closure of C {C}<--- Proper subset Φ Φ cannot be a SK. ∴ C is a Candidate Key. **Prime = {A, B, D, F, C} Candidate Key = {AB, DB, C} ## Topic: Finding Candidate Key **Q. R(A, B, C, D, E ,F) Functional Dependency: - AB → C - C → DE - E → F - D → A - C → B Super Key:- - {ABCDEF}+ = {ABCDEF} - {ABDEF}+ = {ABCDEF} - {ABF}+ = {ABCDEF} - {AB}+ = {ABCDEF} Eliminate F here: C → DE Means c D, c → E, & E → F **Find closure of AB {AB}+ - {ABCDEF} Proper subset of SK should be a Super Key. But here no proper set of Super Key AB is a Super Key, i.e. AB is a CK. **Prime Attribute:** Attributes that are making a candidate key. Till now we just have 2 attributes AB which are prime. If Prime attributes are present on RHS of any FD, then definitely you have more Candidate Keys present. FD is **D** → **A** ### Now replace A with D in Candidate key DB We can not say definitely that DB is a CK, but we can say definitely that DB is a SK. No proper subset of DB is SK i.e. DB is a CK Now prime attributes are {A, B, D}. B is present on RHS of FD C B So replace B with C in AB. So, we will get AC (this is definitely a SK, but not sure if it is a CK). {A} - X **AC** < --- Proper Subset {C} - {CDEFAB} AC is not a CK i.e. proper subset of AC i.e. C can determine all the attributes: AC is a SK not CK. C is a SK. Proper subset of C is O cannot be SK, therefore C is a CK therefore no proper subset of C is SK. Till now Candidate Keys are AB, DB, C. Prime attribute = { A, B, D ,C) Now replacing D in AB DB is a SK proper subset of DB is {D} = D X {B} = B X So DB is a CK. Now C is also present on RHS of FD ABC so replace C with AB AB we have already discussed is a CK 3 Candidate keys = AB, DB, C Prime attribute = A, B, D, C Non-prime = E, F ## Topic: Finding Candidate Key **Q. {A, B, C, D, E} FD: {A→B, D→E} ABCDE will be a SK {ABCDE}+ = ABCDE CK is a SK, whose proper subset is not a SK. ABCDE = {ABCDE} SK ACD = ABCDE Can this SK be CK proper subset of this is AC CD AD A .. C D = All of them are not SK therefore ACD is CK **If closure of any of those contain all the attributes then it ACD SK is not a CK Prime attributes are those attributes, where are part of CK so till now ACD are prime. Prime attributes present in RHS of FD A ------ not present C ------ not present D ------not present Therefore in the relation there is only one CK = ACD If no prime attribute is present on RHS of any FD’s then there is no CK. ## 2 mins Summary Finding Candidate Key (Shortcut + Long Method)