## TOPICS (Click to Navigate)

Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts

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

***********

Normalization solved examples
normalization exercises solved
2nf
3nf
find candidate keys
convert 2nf relation to 3nf relation
convert unnormalized into normalized relation

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

## Thursday, 12 April 2018

### Lossless join decomposition solved example in normalization

Lossless join decomposition solved example in normalization

Question:

Consider a relation R(A, B, C, D) with the set of functional dependencies F = {AB C, BC D, CD A}. Assume that R is decomposed into R1(A, B, C) and R2(A, C, D). Find whether the given decomposition is lossless or not.

Solution:

Lossless join decomposition implies that the result of joining all the decomposed relations will create the base relation again without any loss/gain in data.
If one of the following is true, then the decomposition is said to be lossless;

• (R1 ∩ R2) R1
• (R1 ∩ R2) R2
If we apply intersection between R1 and R2, we shall get,
(R1 ∩ R2) = {A, B, C} ∩ {A, C, D} = AC.
There is no functional dependency in F such that the AC is alone on the left hand side. Hence, this decomposition is lossless.

Example:

Let us populate R with sample data and try the experiment;

 A B C D a1 a2 a3 a4 a1 a4 a3 a2

According to the decomposition, we shall get R1 and R2 as follows;

 R1 A B C a1 a2 a3 a1 a4 a3

 R2 A C D a1 a3 a4 a1 a3 a2

Join back R1 and R2 must result in R if the decomposition is lossless.

R1
R2
=
R’

 A B C a1 a2 a3 a1 a4 a3

 A C D a1 a3 a4 a1 a3 a2

=

 A B C D a1 a2 a3 a4 a1 a2 a3 a2 a1 a4 a3 a2 a1 a4 a3 a4

R’ is the result of natural join of R1 and R2, and R’ is not equal to R the base relation. Hence, the decomposition is not 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

### Simple introduction to Naive Bayes classifier

Simple introduction to Naive Bayes classifier What is Naive Bayes Classifier? A Naive Bayes classifier is a probabilistic classifier ...