Find the candidate keys of a relation in RDBMS

Find all the candidate keys of relation R - solved exercise

Question:

Find all the candidate keys of R given R and the set F of functional dependencies (FDs) as follows;

R = (a, b, c, d, e) and F = {a → c, c → bd, d → a}

Solution:

Let us follow the steps given in the box below to find all the candidate keys of R.

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

Given,

R = (a, b, c, d, e) and F = {a → c, c → bd, d → a}

Step 1: Out of all attributes of R, only {e} is not present in the RHS of any FD. So, A = {e}. And, every candidate key of R must have the attribute e in it.

Step 2: Set of attributes appear on RHS of any FD are a, b, c, and d. Out of them the attributes not appear on the LHS of FDs is b. So, B = {b}. And, the attribute b cannot be part of any candidate key. 

Step 3: A⁺ = {e}⁺ ≠ R. So, let us move on to step 4.

Step 4: Since A⁺ ≠ R is not a candidate key, then for each attribute x in (R – B) check whether A U {x} is a candidate key or not.

R – B = {a, b, c, d, e} – {b} = {a, c, d, e}

Now, let us combine attributes of A with each attribute of (R-B) and check whether they form a candidate key or not. That is, check whether {a, e}, {c, e} and {d, e} forms candidate key or not using closure of these attribute sets. [Refer how to find closure here, one more solved exercise]

{a, e}⁺         = {a, e}

                   = {a, e, c} from FD a → c

                   = {a, e, c, b, d} from FD c → b d

                   = R

Hence, {a, e} is a super key and also a candidate key.

{c, e}⁺ = {c, e, b, d, a} = R, hence a candidate key.

{d, e}⁺ = {d, e, a, c, b} = R, hence a candidate key.

Result:

The candidate key of R are {a, e}, {c, e} and {d, e}.

**********

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 database relation

steps to find candidate keys

Easy way to find candidate keys

Candidate keys solved exercise

Candidate keys for normalization

Find candidate key and normalize the relation into 2nf and 3nf

Find candidate key and normalize the relation into 2nf and 3nf

Question:

A relation R is defined as follows.

R = (name, street, city, state, postal_code)

Here, name is unique, and for any given postal code, there is just one city and state.

• Give a set of FDs for this relation.
• What are the candidate keys?
• Is R in 3NF? 2NF? Explain why?
• If R is not in 3NF, normalize it into 3NF relations.

Solution:

a) Set of functional dependencies;

It is given that Name is unique. Hence, it determines all the other attributes.

name → street, name → city, name → state, name → postal_code

also given that postal_code is unique for a city and state. Hence, postal_code can determine city and state uniquely.

postal_code → city, postal_code → state.

So, set F of functional dependencies for the given relation R is;

F = {name → street, name → city, name → state, name → postal_code, postal_code → city, postal_code → state}

b) What are the candidate keys?

Candidate key is the minimal super key that can uniquely identify all the other attributes of a given relation.

In our case, the attribute name is said to be unique and determines all the other attributes of R. Hence, name is the candidate key.

c) Is R in 3NF? 2NF? Explain why?

2NF

A relation is said to be in 2NF if no partial key dependencies exist.

In our problem, name is the candidate key and there is no possibility for partial key dependencies (it may occur only if the key is composite). Hence, R is in 2NF.

3NF

A relation is said to be in 3NF if it does not have any non-key dependencies.

In our problem, postal_code determines city and state [postal_code → city, postal_code → state] and postal_code is a non-key attribute. So, R is not in 3NF.

d. If R is not in 3NF, normalize it into 3NF relations.

R is not in 3NF. So we need to decompose R into two or more relations. We can do this using the functional dependencies that violate the 3NF property.

In our problem, the attribute postal_code violates 3NF property by uniquely determining the city and state attributes. Hence, we can decompose R by taking these attributes into a separate table as follows;

R1 = (postal_code, city, state) with FDs { postal_code → city, postal_code → state} and postal_code as the candidate key.

R2 = (name, street, postal_code) with FDs { name → street, name → postal_code} and name as the candidate key.

Now the relations R1 and R2 are in 3NF.

***********

Go to Normalization solved exercises page

Go to Solved exercises in DBMS page

Normalize the tables into second and third normal forms solved examples

normalization exercises solved

2nf

3nf

find candidate keys

convert 2nf relation to 3nf relation

convert unnormalized into normalized relation

Lossless join decomposition one more example

Lossless Join Decomposition

Question:

Let R = {ssn, ename, pnumber, pname, plocation, hours} and R is decomposed into three relations R1, R2, and R3 as follows;

R1 = EMP = {ssn, ename}

R2 = PROJ = {pnumber, pname, plocation}

R3 = WORKS_ON = {ssn, pnumber, hours}

Assume that the following functional dependencies are holding on relation R.

F = {ssn → ename; pnumber → {pname, plocation}; {ssn, pnumber} → hours}.

Find whether the decomposition into R1, R2, and R3 is lossless join decomposition or not.

Answer:

In theory, if a relation R is decomposed into relations R1 and R2 then the decomposition is lossless if either of the following holds;

• (R₁ ∩ R₂) → R₁

• (R₁ ∩ R₂) → R₂

In our problem, if we apply intersection between R1 and R2, we shall get nothing, that is, no attribute is common between R1 and R2.

Hence, let us apply intersection between R1 and R3. Now we shall get ssn as result.

(R₁ ∩ R₃) ⇒ ({ssn, ename} ∩ {ssn, pnumber, hours}) ⇒ {ssn}.

From the given set of functional dependencies F, we understand that, ssn → ssn, ename. That is,

({ssn, ename} ∩ {ssn, pnumber, hours}) → {ssn, ename} ⇒ {ssn} → {ssn, ename} ⇒ (R₁ ∩ R₃) → R₁.

Hence, the decomposition into R1 and R3 is lossless.

Similarly, the decomposition into R2 and R3 is also lossless.

  ({pnumber, pname, plocation} ∩ {ssn, pnumber, hours}) → {pnumber, pname, plocation} ⇒ (R₂ ∩ R₃) → R₂.

So, we can conclude that decomposition of R into R1, R2, and R3 is lossless join decomposition.

********

Go to Normalization solved exercises page

Go to Solved exercises in DBMS page

Normalization solved examples

normalization exercises solved

what is lossless decomposition

rules for lossless join decomposition

lossless decomposition example

how to find whether a decomposition is lossless or not

lossless join decomposition one more example