Find the primary key of a database table

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples

Question:

The following relation schema is used to store information about the customers of a car service center.

Customer (Customer_ID, CName, CAddr, Phone, Customer_Visit_Date, Service_Advisor_ID, SAName, SAPhone, No_of_Cars_Serviced, Service_Date)

A customer is identified with a unique Customer_ID, he can have only one phone number, and he may have visited the service center many times. There are more service advisors and each advisor services many cars on a given service date. Any service advisors can be reached at only one phone number.

Find the primary key for Customer.

Solution:

From the given information, we can derive the following set of functional dependencies;

• Customer_ID → CName CAddr Phone 
• [as customer id is unique, every id is related to exactly one name, one address, and one phone]

The FDs that do not hold Customer_ID → Customer_Visit_Date – This FD does not hold because a customer can visit many times. Hence, customer id cannot uniquely determine customer visit date. Customer_ID → Service_Advisor_ID – This FD does not hold because a might have been attended by different advisors during each of his visit. Service_Advisor_ID → Service_Date No_of_Cars_Serviced – This FD does not hold because a service advisor services every day with number of cars. Hence, we cannot uniquely determine the number of cars serviced or the service dates. Service_Date → No_of_Cars_Serviced – This FD does not hold because on a given service date other service advisors may have serviced many cars as well.

• Service_Advisor_ID → SAName SAPhone 
• [Service advisors name and phone can be uniquely determined by service advisor id]

• Service_Advisor_ID Service_Date → No_of_Cars_Servicesd 
• [if we know the service date and the advisor id, we can uniquely determine the number of cars serviced on a data by an advisor]

Finding closure of attributes/attributes sets

Normally, it is enough to find the closure for the LHS (Left Hand Side) attributes of the FDs. [Refer here to know how to find closure ofan attribute/attribute set]

(Customer_ID)⁺ = Customer_ID, CName, CAddr, Phone

• [(Customer_ID) does not derive all the attributes of customer]

(Service_Advisor_ID)⁺ = Service_Advisor_ID, SAName, SAPhone

• [(Service_Advisor_ID) does not derive all the attributes of customer]

(Service_Advisor_ID, Service_Date)⁺ = Service_Advisor_ID, SAName, SAPhone, Service_Date, No_of_Cars_Serviced

• [(Service_Advisor_ID, Service_Date) does not derive all the attributes of customer]

(Customer_ID, Service_Advisor_ID, Service_Date)⁺ = Customer_ID, CName, CAddr, Phone, Service_Advisor_ID, SAName, SAPhone, Service_Date, No_of_Cars_Serviced

• [(Customer_ID, Service_Advisor_ID, Service_Date) does not derive all the attributes of customer.]

Here customer visit date is missing. And this attribute is not part of any FDs. Hence, we can include customer_visit_date attribute to the left hand side by assuming the trivial FD, Customer_Visit_Date → Customer_Visit_Date.

Then we have,

(Customer_ID, Customer_Service_Date, Service_Advisor_ID, Service_Date)⁺ = Customer_ID, CName, CAddr, Phone, Customer_Service_Date, Service_Advisor_ID, SAName, SAPhone, Service_Date, No_of_Cars_Serviced

(Customer_ID, Customer_Service_Date, Service_Advisor_ID, Service_Date) derives all the attributes of Customer. Hence, this combination forms the key for Customer.

Customer_ID Customer_Visit_Date Service_Advisor_ID Service_Date → CName CAddr Phone SAName SAPhone No_of_Cars_Serviced - This FD holds on Customer

(Customer_ID Customer_Visit_Date Service_Advisor_ID Service_Date) is the key and it is a composite primary key.

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?

Database normalization - solved exercise to find keys

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples

Question:

Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F⁺ is exactly the set of FDs that hold for R. Find the candidate keys of relation R. (GATE 2013 question)

Solution:

Which attribute (or set of attributes) is the key? – We know that, if the closure of an attribute (or set of attributes) includes all the attributes of the relation, then that attribute (or set of attributes) is one of the candidate keys of the relation (table).

To simplify, we would find the closure for left hand side attributes of all the functional dependencies (we can skip redundant attributes).

Closure of A (A⁺):

Result = A

Result = ABC from A → BC

Result = ABCFH from B → CFH

Result = ABCEFGH from F → EG

Final result = ABCEFGH which is not ABCDEFGH i.e., result ≠ R. hence, A is not a candidate key.

Closure of E (E⁺):

Result = E

Result = EA from E → A

If we know A, from the above derivation, final result would be ABCEFGH. And this is not equal to R, hence E is not a candidate key.

At this stage, we need to observe one thing from the set of functional dependencies given. The thing is, attribute D is not part of any functional dependencies. Hence, we need to include D with other attributes. That means, whatever key we find, D should be a part of it.

Hence, we would try with D as a component attribute; if we follow the steps applied above; we would get the following;

Closure of AD (AD⁺) = R. Hence, AD is one of the candidate keys.

Closure of BD (BD⁺) = R. So BD is one of the candidate keys.

Closure of ED (ED⁺) = R. So, ED is one of the candidate keys.

Closure of FD (FD⁺) = R. Hence, FD is one of the candidate keys.

AD, BD, ED, and FD are the candidate keys of R.

What about other set of attributes?

The other attributes other than AD, BD, ED, and FD cannot be the keys (refer definition for candidate keys). Why?

We know that the closure of ABD, ADE, ADF, BED, etc. would form the keys. According to the definition (candidate key is a minimal key for which the proper subset must not contain a key), for example, the subset of ABD contains the keys AD, and BD which are keys. This holds for all the other combinations. Hence, they cannot form the candidate keys. (they are all super keys).

Another try: Let us try to find the closure of CH.

Closure of CH (CH⁺):

Result = CH

Result = CHG from CH → G.

We cannot move further because C, H and G are not (individually or collectively) uniquely determine any other attributes. Hence, CH⁺ = CHG.

As a result, we would conclude that AD, BD, ED, and FD are the qualified candidate keys for R.

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?

Database Normalization Solved Exercise 7

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples

Question:

Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies {{E, F} → {G}, {F} → {I, J}, {E, H} → {K, L} → {M}, {K} → {M}, {L} → {N}} on R. What is the key for R?

Solution:

To find the key of a relation, we need to find the closure of attributes. If any attribute’s or set of attributes’ closure gives all the attributes of the relation, then we would say that attribute/set of attributes as the key for that relation.

To simplify this task or to avoid finding closure of all attributes, let us do find the closure for left hand side (LHS) attributes of the functional dependencies.

For the given question, attributes F, (E, F), (E, H), K, and L are the LHS attributes.

• The closure of F, i.e., (F)⁺ = FIJ ≠ EFGHIJKLMN. Hence F is not a candidate key. [Refer, How to find closure]

• (EF)⁺ = EFGIJ ≠ EFGHIJKLMN. Hence EF is not a candidate key.

• (EH)⁺ = EHKLMN ≠ EFGHIJKLMN. Hence EH is not a candidate key.

• (K)⁺ = KM ≠ EFGHIJKLMN. Hence, K is not a candidate key.

We observed that the left side attributes of any FDs alone cannot form a key. Let us try with the combination of two FDs LHS.

• (EFH)⁺ = EFGHIJKLMN  = R.

Hence, EFH is the key for this relation.

[

Derivation of EFH+:

Step 1: result = EFH

Step 2: result = EFGH from {E, F} → {G}

Step 3: result = EFGHIJ from {F} → {I, J}

Step 4: result = EFGHIJKLM from {E, H} → {K, L} → {M}

Step 5: result = EFGHIJKLMN from {L} → {N}

We have reached that the result = R. hence, EFH is the key.

]

 

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?

How to find candidate keys using closure finding algorithms