Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts

# 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 2NF, 3NF and BCNF

## 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.

***********

# Normalize the tables into second and third normal forms solved examples

## 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.

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

• (R1 ∩ R2) → R1
• (R1 ∩ R2) → R2
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.
(R1 ∩ R3) ({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} (R1 ∩ R3) → R1.
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} (R2 ∩ R3) → R2.

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

********

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

## 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...

data recovery