RELATIONAL DAATBASE
DESIGN 2
BROTOTI MONDAL
Assistant Professor
Department of Computer Science
Sammilani Mahavidyalaya
TYPES OF DECOMPOSITION
Lossless Join Decomposition:
No information is lost from the original relation
during decomposition.
When the sub relations are joined back, the same
Prof. Brototi Mondal
relation is obtained that was decomposed.
Lossy Join Decomposition:
The join of the sub relations does not result in the
same relation that was decomposed.
The natural join of the sub relations is always
found to have some extraneous tuples.
Every decomposition must always be 2
lossless.
LOSSLESS AND LOSSY
DECOMPOSITION
If a relation R is decomposed into two sub
relations R1 and R2 then, this decomposition is
said to be lossless if following three conditions
are satisfied.
Prof. Brototi Mondal
Union of R1 and R2 contains all the attributes of
all R.
R 1 ∪ R2 = R
Intersection
of R1 and R2 must not be Null, There
must be some common attribute between R1 and
R2.
R1 ∩ R2 ≠ ∅
3
Intersection of R1 and R2 must be the super key of
either R1 or R2 or both.
CONSIDER A RELATION SCHEMA R ( A , B , C , D ) WITH
THE FUNCTIONAL DEPENDENCIES A → B AND C → D.
DETERMINE WHETHER THE DECOMPOSITION OF R INTO
R1 ( A , B ) AND R2 ( C , D ) IS LOSSLESS OR LOSSY.
To determine whether the decomposition is
lossless or lossy,
We will check all the conditions one by one.
Prof. Brototi Mondal
If any of the conditions fail, then the decomposition is
lossy otherwise lossless.
Condition-01:
According to condition-01, union of both the sub
relations must contain all the attributes of relation
R.
So, we have-
R1 ( A , B ) ∪ R2 ( C , D ) = R ( A , B , C , D )
Clearly, union of the sub relations contain all the 4
attributes of relation R.
Condition-02:
According to condition-02, intersection of both
the sub relations must not be null.
Prof. Brototi Mondal
So, we have-
R1 ( A , B ) ∩ R 2 ( C , D ) = Φ
Clearly, intersection of the sub relations is
null.
So, condition-02 fails.
Thus, we conclude that the decomposition is
lossy.
5
Consider a relation schema R ( A , B , C , D, E )
with the functional dependencies- C → D, D → B,
B →E , A → E. Determine whether the
decomposition of R into R1 ( A , B, C ) , R2 ( C, D )
and R3 ( B , D ,E) is lossless or lossy.
Prof. Brototi Mondal
Condition-01:
According to condition-01, union of both the sub
relations must contain all the attributes of relation
R.
So, we have-
R1 ( A , B, C ) ∪ R2 ( C , D ) = R12 ( A , B , C , D )
Next,
R12 ( A , B , C , D ) ∪ R3 ( B , D ,E) = R(A,B,C,D,E )
Clearly, union of the sub relations contain all the
6
attributes of relation R.
Thus, condition-01 satisfies.
Condition-02:
According to condition-02, intersection of both the
sub relations must not be null.
R12 ( A , B , C , D ) ∩ R3 ( B , D ,E) = B, D
Clearly, intersection of the sub relations is not null.
Prof. Brototi Mondal
Thus, condition-02 satisfies.
Condition-03:
According to condition-03, intersection of both the
sub relations must be the super key of one of the two
sub relations or both.
So, we have- R12 ( A , B , C , D ) ∩ R3 ( B , D ,E) = B, D
(BD)+ ={BDE} (Using B →E)
(BD)+ is a super key of relation R3 ( B , D ,E) .
7
So, condition-03 satisfies.
Thus, we conclude that the decomposition is lossless.
Assignment
Q1. Consider a relation schema R ( A , B , C , D )
with the functional dependencies- A → B, B → C,
C → D, D → B. Determine whether the
decomposition of R into R1 ( A , B ) , R2 ( B , C )
Prof. Brototi Mondal
and R3 ( B , D ) is lossless or lossy.
Q2. Decomposition of R'(A,B,C) with A->B , B->C,
C->A into R1(A, B) and R2(B, C)- Determine
whether the decomposition is lossless or lossy.
8
DEPENDENCY PRESERVATION
If a relation R with set of FDs F is
decomposed into relation R1 and R2
with set of FDs F1 and F2, then the
Prof. Brototi Mondal
dependencies of R either must be a part
of R1 or R2 or must be derivable from
the combination of functional
dependencies of R1 and R2.
It is not a mandatory criteria of
decomposition, rather than an optional
criteria. But Lossless criteria is a
mandatory criteria . 9
A decomposition is said to be dependency
preserving if ,
(F1 ∪ F2)+ = F+ where F1+ ⊆ F+ F2+ ⊆ F+
Prof. Brototi Mondal
R(F)
R1(F1) R2(F2)
R(F1 ∪ F2)= F
10
CHECKING OF DEPENDENCY PRESERVATION
Step1: Find out the dependencies which can
come from parent table to F1 and F2.
Step2: Check whether F1 and F2 are valid or
Prof. Brototi Mondal
not.
a. Finding dependencies from parent table
directly.
b. Dependencies which are not present in
parent table, find the closure of the
dependencies using parent table’s F to
check whether they are valid dependency
or not.
Step3: Check parent dependencies are 11
preserved or not from F1 and F2 by finding
R(ABCD) , AB → CD, D →A, R1(AD)
AND R2(BCD)
For R1(AD) , F1 ={ A → D, D →A}
A →D ( Not valid dependency because A+={A}
Prof. Brototi Mondal
D → A ( Valid dependency)
For R2(BCD) ,
F2 ={ B → (Not valid) B+ ={ B}
C → (Not valid) C+= {C}
D → (Not valid) D+={DA}
BC → (Not valid) (BC)+={BC}
BD → C (Valid) (BD)+={BDAC}
CD → (Not valid) }(CD)+={CDA} 12
For R1(AD) , F1 = {D → A}
For R2(BCD) , F2 = {BD → C}
Now we have to check whether the parent
table dependencies are preserved or not
Prof. Brototi Mondal
after decomposition.
R(ABCD) , AB → CD, D →A
Find out the closure of AB and D from F1 and F2.
(AB)+ = {AB}
D+= {DA}
As the closures don't contain all the attributes of
R, so the decomposition is not dependency
preserving.
13
R(ABCD) , A →B, B →C, C →D, D →B
R1(AB) , R2(BC) , R3(BD)
Prof. Brototi Mondal
14
Prof. Brototi Mondal
15
Hence, decomposition is dependency preserving.
HOW TO FIND THE HIGHEST NORMAL
FORM OF A RELATION
Step1: Find all possible candidate keys of
the relation.
Prof. Brototi Mondal
Step2: Divide all attributes into two
categories:
a) prime attributes
b) non-prime attributes.
Step 3: Check for 1st normal form then
2nd and so on. If it fails to satisfy
nth normal form condition, highest normal
form will be n-1. 16
Step 3.1: For 1st normal form, a Relational
Database Management System does not allow
multi-valued or composite attribute.
Step 3.2: For 2nd normal form, there will not be
Prof. Brototi Mondal
any partial dependency.
Partial Dependency : Any subset of
candidate key determines any non-prime
attribute.
Step 3.3: For 3rd normal form, for X → Y either X is
a super key or Y is a prime attribute.
17
Step 3.4: For BCNF , for X → Y , X is super key.
FIND THE HIGHEST NORMAL FORM OF A
RELATION R(A,B,C,D,E) WITH FD SET {A → D, B → A,
BC → D, AC → BE }
Step 1: (AC)+ ={A,C,B,E,D} and (BC)+
={A,C,B,E,D}
Prof. Brototi Mondal
So there will be two candidate keys {AC, BC}.
Step 2: Prime attribute are those attribute
which are part of candidate key {A,B,C} and
others will be non-prime {D,E}.
Step 3: The relation R is in 1st normal form as
a relational DBMS does not allow multi-valued 18
or composite attribute.
For 2nd normal form, check if there is any
partial dependency.
The relation is not in 2nd Normal form because A →
Prof. Brototi Mondal
D is partial dependency (A which is subset of
candidate key AC is determining non-prime
attribute D) and 2nd normal form does not allow
partial dependency.
So, the highest normal form will be
1st Normal Form.
19
FIND THE HIGHEST NORMAL FORM OF A
RELATION R(A,B,C,D,E) WITH FD SET AS
{BC → D, AC → BE, B → E}
Step 1: (AC)+ ={A,C,B,E,D} , there will be
Prof. Brototi Mondal
only 1 candidate key {AC}.
Step 2: Prime attribute are those attribute
which are part of candidate key {A,C} and
others will be non-prime {B,D,E}.
Step 3: The relation R is in 1st normal
form as a relational DBMS does not allow
multi-valued or composite attribute. 20
For 2nd normal form, check if there is any
partial dependency.
The relation is in 2nd normal form because,
a) BC → D is in 2nd normal form as BC is not subset of
candidate key AC,
Prof. Brototi Mondal
b) AC → BE is in 2nd normal form as AC is candidate
key.
c) B → E is in 2nd normal form as B is not a proper
subset of candidate key AC.
The relation is not in 3rd normal form because
in BC → D (neither BC is a super key nor D is a
prime attribute) and in B → E (neither B is a
super key nor E is a prime attribute) but to
satisfy 3rd normal for, either LHS of an FD should
be super key or RHS should be prime attribute. 21
So the highest normal form of relation will
be 2nd Normal form.
FIND THE HIGHEST NORMAL FORM OF A
RELATION R(A,B,C,D,E) WITH FD SET {B → A, A → C,
BC → D, AC → BE}
Step 1: (A)+ ={A,C,B,E,D} and(B)
+
={B,A,C,D,E}, So there will be two candidate
Prof. Brototi Mondal
keys {A,B}.
Step 2: Prime attribute are those attribute
which are part of candidate key {A,B} and
others will be non-prime {C,D,E}.
Step 3: The relation R is in 1st normal form as
a relational DBMS does not allow multi-valued or
22
composite attribute.
For 2nd normal form, check if there is any
partial dependency.
The relation is in 2nd normal form because B → A
is in 2nd normal form (B is a super key) and A →
Prof. Brototi Mondal
C is in 2nd normal form (A is super key) and BC →
D is in 2nd normal form (BC is a super key) and
AC → BE is in 2nd normal form (AC is a super
key).
The relation is in 3rd normal form because LHS of
all FD’s are super keys. The relation is in BCNF
as all LHS of all FD’s are super keys.
23
So , the highest normal form is BCNF.
Assignment
1. Find the highest normal form of a relation R(P, Q,
R, S, T) with Functional dependency set as (QR →
Prof. Brototi Mondal
S, PR → QT, Q → T).
2. Find the highest normal form of a relation R (P,
Q, R, S, T) with Functional Dependency set (Q →
P, P → R, QR → S, PR → QT)
3. Find the highest normal form of a relation R (P, Q,
R, S, T) with Functional Dependency set (P → S,
Q → P, QR → S, PR → QT).
24
HOW TO NORMALIZE A RELATION TABLE OR
DECOMPOSE A TABLE TO A DESIRED NORMAL
FORM
Consider a Relation R(ABCDEFGHIJ) with
AB →C, A → DE, B → F, F → GH, D → IJ and
Prof. Brototi Mondal
decompose or normalize R to its highest
normal form.
Ans: Find out candidate key.
(AB)+ ={ABCDEFGHIJ} ,hence AB is the
candidate key.
25
Initially R is in 1NF because a relational DBMS
does not allow multi-valued or composite
attribute.
To decompose into 2NF,
first consider AB →C ,because AB is the
Prof. Brototi Mondal
candidate key and break the relation into
R1(ABC) with Functional dependency AB →C .
Next consider A → DE and then D → IJ, to form
R2(ADEIJ) .
Next consider B → F and then F → GH, to form
R3(BFGH).
R1(ABC), R2(ADEIJ) , R3(BFGH) all three
tables are in 2NF but not in 3NF because 26
R2 and R3 have transitive dependency.
R2(ADEIJ) with functional dependency set {A →
DE, D → IJ} has transitive dependency.
Hence decompose it into R21(ADE) with A → DE
and R22(DIJ) with D → IJ.
Prof. Brototi Mondal
R3(BFGH) with functional dependency set {B → F
, F → GH} has transitive dependency.
Hence decompose it into R31(BF) with B → F and
R32(FGH) with F → GH.
Hence all tables are in 3NF and also in
BCNF .
27
