Normalization-I Module 3

Module 3
• Referential Integrity
• Concept of Foreign key
• Functional Dependency(FD)
• Closures of Attributes
• Closures of FD
• Inference rules
• Finding Candidate Key
• Types of FDs
• Normalization
• Types of Normalization.(1NF,2NF,3NF, BCNF, 4NF and
5NF)
• R(A,B,C,G,H,I)
• Given FD= {A→B,
• A→C,
• CG→ H,
• CG→I,
• B→H}
• Find (FD)+ ?
Question to perform:
• R(A,B,C,D,E)
• FD={ A→BC,
• CD→E,
• B→D,
• E→A}
• Find the closure of FD?
Finding Candidate keys in a table.
R(A,B,C,D,E,F)
FD= {A→C,
C→D,
D→B,
E→F}
Find CK=?
Questions on Candidate Key
Q1.R(A,B,C,G,H,I) Q2.R(A,B,C,D,E)
FD= {A→B, FD= {A→B,
A→C, AB→C,
CG→H, BC→E,
CG→I, BD→E}
B→H} Find CK=?
Find CK=?
Q3.Let R(A,B,C,D,E)
FD={A→BC,
CD→E,
B→D,
E→A}
Find Candidate keys=?
• R(A,B,C,D,E,F,G,H)
• FD={CH→G,
• A→BC,
• B→CFH,
• E→A,
• F→EG}
• Find Candidate Keys=?
Types of FDs
• Fully Functional Dependency FFD
• Partial Functional Dependency
• Transitive Functional Dependency
• Trivial Functional Dependency.
• Single valued .
Partial Dependency:
• Suppose we have more than one attribute in
Primary key. Let A be the non primary key
attribute. If A doesn’t depends upon all the
primary key attribute than partial dependency
exists.
• X→ Y , Y is said to be partial dependent on X,
because any proper subset of X can be able to
determine Y, such kind of dependency if exists
are known as partial dependency.
Fully FD & Partial FD
• X→ Y, if Y can be fully functionally determined
by a subset of X, then it is said to be partially
functional dependent.
• On the other hand,
• If Y cannot be determined by any subset of X
then it is said to be fully functionally
dependent on X.
Transitive Dependent:
• This dependency can be derived easily and is
based on the transitive rule only, which says,
• If X→ Y, holds and
• Y→Z exists than because of transitive rule
X→Z also exists. And X→Z is called TFD or we
say Z is transitively dependent on X or X
transitively determines Z.
Trivial Dependency
• X C Y, then Y → X exists.
Dependency of this type is called
• Similarly A→A Trivial Dependency. This can be
proved by Reflexive Rule.
Single valued and multiple valued
dependency
• Single Valued – In any relation R, if for a
particular value of X, Y has single value then it
is known as single valued Dependency.
• For Single valued we has,
• Teacher_ID → Teacher_name
• For multiple valued: Teacher_ID→→Dept
Teacher_ID Teacher_name Dept
1 ABC CSE
1 ABC MAE
2 XYZ CE
2 XYZ ECE
3 PQR ECE
Normalization
Decomposition of a Relation
The process of breaking up or dividing

a single relation into two or more
relation is called as decomposition of a
relation
Decomposition
• Lossless:- If R1 R2 gives original R again.(R1
and R2 were obtained after normalization.)
• If R1 R2 forms a super key in either R1 or R2,
then it is a lossless decomposition.
• Lossy:- If R1 natural Join R2 is not giving the
original R.
• Example: R(A, B, C) FD= {A → B}
• R was decomposed into R1(A, B) and R2(A, C)
• As R1 R2 = { A} so lossless decomposition.
Let R(A, B, C, D) FD= {A→B, A→C, C→D}
• After decomposition we get,
• R1(A, B, C) FD = { A→ B, A→C}
• R2(C, D) FD = { C→D}
• R1 R2 = {C}
• ANOTHER METHOD
• Will create a matrix 2 x 2( or a table)
• A B C D
R1
R2
A B C D
R1 X X X
R2 X X
Alpha(x) is a dependency variable.

And we will put alpha across.
We will fill this table up with (alpha) using following
rules:
➢If 2 or more rows have alpha at left hand side of

FD
➢If one or more rows have alpha at RHS of FD
➢At least one row has a non alpha at RHS of FD.
• Let solve a problem.
• Let R(A,B,C,D,E,G)
• FD={ AB→C, AD→E, BC→ A, AC→ B, B→ D,
E→G}
• This relation was decomposed into R1(A,B),
R2(B,C), R3(A, B, D, E), R4(E,G).
• Find out whether this decomposition is
dependency preserving or not?
• Also Find out where it is a lossy or lossless
decomposition?
• So the decomposition should be Lossless and
dependency preserving.
• We perform decomposition of tables, in order
to avoid redundancy and consequently related
anomalies (delete, update anomalies etc).
• But with decomposition comes complexity.
• And Complexity cannot be over looked.
• So, Normalization is required and is done
generally till 3rd NF.
Properties of decomposition
Question on Decomposition.
• Let R(A, B, C, D, E) and FD={ AB→C, C→ E, B→
D, E→ A}
• The relation R was decomposed into R1(BCD)
and R2(ACE).
• Find out this decomposition is Dependency
preserving?
• Whether the decomposition is lossy or
lossless?
Question on Decomposition.
• Let R(A, B, C, D, E) and FD={ A→BC, CD→ E,
B→ D, E→ A}
• The relation R was decomposed into R1(ABC)
and R2(ADE).
• Find out this decomposition is Dependency
preserving?
• Whether the decomposition is lossy or
lossless?
5TH NORMAL FORM
• R be in 4th NF.
• Based on JOIN Dependency(JD)
• Also known as PJNF(Project(pi) Join Normal Form
• If the main table can not be recreated (i.e. join
dependency does not exist) it is in 5NF and
should not be decomposed.
• And if the main table can be recreated (i.e. join
dependency exists) we should decompose it to be
in 5NF.
Q. Consider the relation R(V,W,X,Y,Z) with functional
dependencies as FD={ Z→Y,Y→Z,X→Y,X→V,VW→X}.
Suppose that the relation is decomposed into two
relations R1(V,W,X) and R2(X,Y,Z).
Find out is the decomposition lossy or lossless.

Normalization-I Module 3

Uploaded by

Copyright:

Available Formats

Normalization-I Module 3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Normalization-I Module 3

Uploaded by

Copyright:

Available Formats

Module 3

The process of breaking up or dividing

Alpha(x) is a dependency variable.

➢If 2 or more rows have alpha at left hand side of

You might also like