Database Design: Dependencies and Normal forms

NORMALIZATION:
Def: Normalization is a body of rules addressing analysis and conversion of data
structures in to relations that exhibit more desirable properties of internal
consistency, minimal redundancy and maximum stability.
Def: Normalization is the process of reducing /decomposing a relation into a set
of small relations free from data redundancy and ensuring data integrity.
Def: Normalization is a procedure of successive reduction of a given collection of
relational schemas based on their FDS and primary keys to achieve desirable
form of minimized redundancy, minimized insertion, deletion and minimized
update anomalies.
OBJECTIVES
• The basic objective of normalization is to reduce the data redundancy and
prevent loss of information or avoid inconsistencies when the data base is
altered.
• The types of alterations needed for relations are:
1. Insertion of new data values to a relation.
2. Deletion of tuple or a row in a relation.
3. Updating or changing the value of an attribute in a tuple.
• The normalized relation does not include spurious information when the
original schema is reconstructed.
• Preserves dependencies present in the original database
About Normalization:
• The process of normalization was proposed by EF Codd.
• Normalization is a bottom-up design technique for relational database.
• This technique is useful in the circumstances such as :
- A different method of checking the properties of design arrived at through EER
modeling.
- A technique of reverse engineering a design from an existing undocumented
implementation.
Key terms:
Data redundancy: If data in the database exist in two or more places / locations
i.e. direct redundancy or if data can be calculated from other data items i.e.
indirect data redundancy , then the data base is said to be redundant.
• Data should only be stored once and avoid storing data that can be calculated
from other data.
• During normalization redundancy is removed of course not at the cost of
integrity (rules) of the database.
Data Integrity:
All the data in the database are consistent and satisfies all integrity constraints.
INTEGRITY CONSTRAINTS:
An integrity constraint is a rule that restricts the values that may be present in
the database.
• The relational data model includes constraints that are used to verity the
validity or the data as well as adding meaningful structure to it.
Entity Integrity: The primary key must have unique and not null Value in each
row.
Referential Integrity: Every foreign key must either be null or its values must be
the actual value of a key in another relation.
Successive normal forms of a relation:
• Converting the relation to INF is the essential step.
• There are successive higher normal forms such as 2NF, 3NF, BCNF, 4NF, 5NF.
• Each normal form is an improvement over the earlier form.
• A higher normal form relation is a subset of lower normal form.

• The higher normalization steps are based on three important steps.

(i) Dependency among attributes in a relation.
(ii) Identification of an attribute or a set of attributes as the key of a
relation.
(iii) Multivalued dependency between attributes.
Normalization of data or relations is the process of analyzing the given relation
schema based on their FDS and primary keys to achieve the desirable properties
or
(i) Minimizing redundancy.
(ii) Minimizing insertion, deletion and updation anomalies.
Normalization procedure provides the database designers:
• A formal frame work for analyzing the relation based on their keys and
functional dependencies among their attributes.
• A series of normal form tests that can be carried out on individual relations so
that the relational database can be normalized to any desired degree.
The normal form of a relation refers to highest normal form condition that it
meets and hence indicated the degree to which it has been normalized.
• To reach the highest normal form the designers decompose the relation in top
down fashion.
• The process of normalization through decomposition must confirm to the
following properties while satisfying the criteria of normal forms.
(i) Loss less join /decomposition
(ii) Functional dependency preservation
(iii) Attribute preservation
Dependency theory - Functional dependencies,Armstrong's axioms for
FD's
FUNCTIONAL DEPENDENCY
• Normalization beyond 1NF relies on functional dependency.
• The value of an attribute in a row will uniquely determine the value of another
attribute.
• Let X and Y be two attributes of a relation. If there is only one attribute value of
Y corresponding to it for a given value of X, then Y is said to be functionally
dependent on X.
• This is indicated by a relation X → Y.
• The arrow notation should be read as “Functionally determines”.

• If X → Y, for any two tuples t1 and t2, if t1X = t2 X ⇒ t1Y = t2 Y.

• So, X functionally determines Y and Y is functionally dependent on X.

Trivial functional dependency

• The functional dependency X → Y is said to be trivial if Y≤ X.
• If X → Y in R, this does not mean whether or not Y → X in R.
Ex.: {Roll No} → {Name} ≠ {Name} → {Roll No}

Armstrong Rules: The well known rules called inference rules are defined in
functional dependencies.

IRI : Reflexive rule: If X ⊇ Y then X →Y If Y ⊆ X then X →Y Any set of attributes

functionally determines itself X →Y
IR2 : Augmentation Rule: If X →Y then XZ →YZ The augmentation rule may also
be stated as If X →Y then XZ →Y that is Augmenting the left hand side attribute
of a functional dependency produces another functional dependency.
IR3: Transitive rule: If X →Y and Y →Z then X →Z
IR4: Decomposition / projective rule: If X →YZ and X →Y then X →Z
IR5: Union or Additive rule: If { X →Y and X →Z} then X →YZ
IR6: Pseudo Transitive rule: If { X →Y, WY →Z} then WX →Z
Among these the first three are known as Armstrong’s inference rules. These are
sound because it is enough if a set of FDS satisfy these three. They are complete
because using these three rules we can generate the rest of the inference rules.

Full Functional dependency (FFD)

• The term full functional dependency (FFD) is used to indicate the minimum set
of attributes in a determinant of a FD.
• In other words, the set of attributes X will be fully functionally dependent on
the set of attributes Y if. • X is functionally dependent on Y and
• X is not functionally dependent on any subset of Y
Eg.
Note: Like FD, FFD is a property of the information presented by the relation.
• It is not an indication of the way that attributes are formed in to relations or
current contents of the relations.

IR7: Composition: If X →Y, and Z →W then XZ →YW

IR8: Self Accumulation: If X →YZ, and Z →W then X →YZW

Keys of relational schema:

Super key: A super key is a set of attributes S of a relation schema R i.e. S subset
of R, with the property that no two tuples t1 and t2 will have t1 [S]= t2 [S] The
difference between any key and a super key is that a key is minimal.
Ex. {EMPNPO} is a key for the relation EMP whereas {EMPNPO, ENAME},
{EMPNPO, ENAME, JOB} and any set of attributes is said to be a super key if it
includes the key {EMPNO}
Candidate key: The minimal super key is called the candidate key. If a relation
schema has more than one primary key, then each is called a candidate key.
• One of the candidate key is chosen as primary key and others are secondary
keys.
Prime attribute: An attribute of a relation schema R is called a prime attribute of
R if it is a member of some candidate key of R.
Non-prime attribute: An attribute is called a nonprime attribute if it is not a prime
attribute i.e. an attribute is said to be a non-prime attribute if it is not a part of
the candidate keys.
Q. State Armstrong’s axioms. Show that Armstrong’s axioms are complete.
Ans. Armstrong’s axioms: Let R (X, Y,Z) is a relation schema with attributes X,
Y,Z for which Armstrong’s axioms are stated as follows.

Inf. Rule-1 : Reflexivity, If X⊇ Y, the X→Y

Inf. Rule-2 : Augmentation, If X→Y then XZ→YZ
Inf. Rule-3 : Transitivity, If X→Y, Y→Z then X→Z.
Completeness of Armstrong’s axioms: Armstrong’s axioms are said to be
complete because for a given set F of functional dependencies we can determine
the closure F+ from the FD’s of F by using the Armstrong axioms i.e. inference
rules 1 through inference rule 3.
Proof: Let us consider a relation scheme R (A,B,C,D,E,F) With set of FD’S, F=
{A→ B, A→C, CD→E, CD→DF, B→E}.
A+ = {A,B,C,E}
{CD} + = {C,D,E,F}
F + = (ACD)+ = {A,B,C,D,E,F}
Here, several FDS which are inferred in F+ are:
(i) A→E
(ii) CD→EF
(iii) AD→F IF we are able to prove the above using Armstrong’s axioms then we
can say that the Armstrong’s axioms are complete.
 (i) A→E
Since A →B , and B→E then A→E by IR3: Transitive rule

(ii) CD →EF
We have CD →E ……. (i)
And CD→F ……. (ii)
CD→CDE ……. (iii) using IR2, Augmenting
CDE→ EF……… (iv) using IR2, Augmenting with E on (ii) (iii), (iv)
= CD→EF, using IR3 on (iii) and (iv)
(iii) AD→ F We have the FD’S A→C …… (i) and CD →F ……. (ii)
AD →CD…..(iii) using IR2, augmenting with D on (1)
AD→F, Using IR3, transitive rule on (2) and (3) Similarly all the
FD’S in F+ can be derived by using Armstrong’s axioms, i.e. IR1
through IRS.
Hence, Armstrong’s axioms are complete.

Closure set:
CLOSURE: The set of all functional dependencies that include F as well as all
dependencies that can be inferred from F is called the closure of F and denoted
by F+.
The closure F+ of F is the set of all functional dependencies that can be inferred
from F.
Eg.: F= { {A} → {B} {A} → {c} } A + = {A,B,C} i.e. F+ =A+ = {A,B,C}

Algorithm: Determining X+, the closure of X under F

X + = X repeat
Old X+ = X+
For each functional dependency, Y→ Z in F

If X+ ⊇ Y then If X+ = X+ U Z
do

Until (X+ = old X+),

Problem: The relation R (A, B, C) with FD = {B→C} exists. Does the relation have
potential candidate key If it does what is it? if it does not why not.
Solution: R (A, B, C)
So, super key = {A, B, C}
F = {B→C} A + = {A} B + = {B, C} AB+ = {A, B, C}
The potential candidate key = {A, B}
Problem: Let us consider a relation R (A,B,C,D,E).
With following dependencies {A,B} → {C}, {C,D} → {E}, {D,E} → {B}
Find the candidate key of the given relation.
Solution:
FDs are:
{A,B} → {C}
{C,D} → {E}
{D,E} → {B}
{A,B}+ = {A,B,C}
{A,B,D}+ = {A,B,C,D,E}
So, {A, B, D} is the candidate key
Problem: Let the relation R (A,B,C,D,E,F,G,H,I,J) has functional dependencies:
F = {A,B} → {C} {B,D} → {E,F} {A,D} → {G,H} {A} → {I} {H} → {J}
Solution:
{AB}+ = {A, B, C, I}
{BD}+ = {B, D, E, F}
{AD}+ = {A,D,G,H,I,J}
{A}+ = {A,I}
{H}+ = {H,J}
{A,B,D}+ = {A,B,C,D,E,F,G,H,I,J}
Example:
R = (A, B, C, G, H, I) F = {A → B A → C CG → H CG → I B → H}
(AG)+
1. result = AG
2.result = ABCG (A → C and A → B)

3. result = ABCGH (CG → H and CG ⊆ AGBC)

4. result = ABCGHI (CG → I and CG ⊆ AGBCH) Is AG a candidate key? Is AG a

super key? Does AG → R? == Is (AG)+ ⊇ R Is any subset of AG a superkey? Does
A → R? == Is (A)+ ⊇ R Does G → R? == Is (G)+ ⊇ R

Definitions of 1NF, 2NF, decompositions and desirable properties of them

FIRST NORMAL FORM:
• First Normal Form (INF) deals with the shape of the record type.
• The relation is said to be in INF if and only if, it. It contains no repeating
attributes or groups attributes. • The relation/table is said to be in INF when each
cell of the tuple/relation contains precisely one value (atomic)
• The relation is said to be INF if each cell value is atomic.
Let us consider a relation student (Roll no, name, dob, subject grade)

Table: An un normalized relation with multiple values in a cell.

• Here the table students is not normalized because the cells in subjects and
grade are not atomic.
• By the definition of INF, each cell value must be atomic so, to normalize the
relation we need to fill all the columns of rollno, name, dob by repeating values
for each rows corresponding to subject and grade or each student. So, the
normalized table would be:

The table is normalized to INF but it can lead to several undesirable problems
• Redundancy exists which leads to wastage of memory also.
• The multiple copies of same fact leads to update anomalies.
Ex: Change in date of birth leads to change in all tuples.
• If the teacher teaching a subject, it can be entered only if a student enrolls to
the subject. So it leads to insertion anomalies.
• If the only student in a given course discontinues the information as to which
course a professor is teaching will be lost if the student information is deleted.

SECOND NORMAL FORM: 2NF is more stringent normal form than 1 NF.
Def1: A relation is in 2NF if and only if, it is in INF and every non-key attribute is
fully functionally dependent on the whole key.
Def2: A relation schema R is in 2NF if every non prime attribute A in R is fully
functionally dependent on the primary key of R.
Def3: A relation R is in 2NF provided it is in INF and every non prime attribute to
be fully functionally dependent on candidate key of R.
Def4: A relation schema R is in 2NF if every non prime attribute A in R is not
partially dependent on any key of R. or A relation schema R is in 2NF if every non
prime attribute A in R is fully functionally, dependent on every key of R.
• 2 NF is really a test of primary key.
• 2 NF is concerned with the concept of full functional dependency.
• If a relation is in 1 NF and has a single attribute key it must automatically be in
2Nf.
 Decomposing the relation:
student relation involved redundancy and inconsistencies due to insertion,
deletion & updation. It can be decomposed in the three simple relations to
eliminate the redundancy and inconsistency.
Stdinf (Roll no, name., dob)
Courseinf (subject, grade, rollno)
Teacher inf (subject, teacher)

Since, the dependencies in the student table are: Roll No ->Name, DOB
Teacher-> Subject, Grade

Second Normal Form (2NF)

Let us consider a relation schema R (A,B,C,D,E,F) with a set of functional
dependencies.
F= {A} → {B} {A} → {C} {A,D} → {F} {D} → {E}
(i) Find the super key
(ii) Closure
(iii) Identify the candidate key
(iv) Is it in 2NF?
(v) If not decompose it in to 2 NF form.

Solution:
The given functional Dependencies are:
{A} → {B}, {A} → {C}, {D} →{E}, {AD} →{F} Super key of R is {AD}
Closure A+ = {A,B,C} D + = {D,E} {A,D} + = {A,B,C,D,E,F}
• There is no such single key that can derive /determine the other attribute.
• Here we take two keys together i.e. {AD} as the minimum super key.
Hence the candidate key is {AD}. The relation is not is 2 NF since partial
dependency exists.
So we decompose our original relations R1 (A,D,F) Since {A,D} → {F}, R2 (A,B,C)
Since {A} → {B}, {A} → {C} and R3 (D,E) Since {D} → {E} .

Properties of normalized relation:

An ideal relation after normalization should have the following properties so that
the problems of redundancy and inconsistency is avoided.
1. No data value should be duplicated in different rows unnecessarily.
2. A value must be specified (and required) for every attribute in a row.
3. Each relation should be self contained. In other words if a row from a relation
is deleted, important information should not be (Deleted) accidentally lost.
4. When a row is added to a relation, other relations in the database should not
be affected.
5. A value of an attribute in a tuple may be changed independent of other tuples
in the relation and other relations.
The idea of normalizing relations to higher and higher normal forms is to attain
the goals of having a set of ideal relations meeting the above criteria.

3RD NORMAL FORM (3NF):

• 3NF is more stricter normal form than the 2NF
• 3NF is concerned with transitive functional dependency.
• Transitive functional dependency may exist, only if there are more than one
non key field.
• We may say that if a relation is in 2NF and has zero or one non key field it must
automatically be in 3NF
Definition: A relation is in 3NF if and only if it is in 2NF and there are no
transitive functional dependency.
• Transitive functional dependency arises when one non key attribute is
functionally dependent on another non key attribute.
• In other words, the value of one non key attribute is determined by the value of
another non key attribute.
• This means there is redundancy in the database.
• Let us consider a relation employee (proj.no, manager, address)
  Here transitive dependency exists, as proj. no determines manager and
manager determines address.
 If a manager is associated with more than one project then his address is
repeated leading to data redundancy.
 If we need to change address of a manager we need to change at many
places leading to updation anomalies.
 So, we split the table in to two relations.
 The determinant attributes become the primary key in the new relation
 The attribute manager becomes the link between two tables/new
relations.

 Here in project relation, proj.no serves as the primary key and manager
can be determined by project no.
• In manager relation, address can be determined by knowing the manager
name, so, manager becomes the primary key.
• So, in the above relation the non prime attributes depend upon the primary
key.
• Hence we can define the third normal form as below
Alternative Definition: A relation is said to be in 3NF when it is in 2NF and every
non key attributes is functionally dependent only on the primary key.
Guidelines for converting a table to 3NF:
• Find the non. key attributes and remove them that are functionally dependent
on attributes that are not the primary key.
• Place them in a different relation.
Third Normal Form (3NF) (Summary) A relation R is said to be in third normal
form (3NF) if the relation R is in 2NF and nonprime attributes are:
• Mutually independent
• Functionally dependent on the primary key
• In other words, no attributes of the relation should be transitively dependent on
the primary key.
• Thus in 3NF, no non prime attribute is functionally dependent on another
nonprime attribute.
• This means that a relation in 3NF consists of the primary key and a set of
independent non prime attributes

Lossless join and Dependency preserving Decomposition

A relation schema R can be decomposed in to collection of relation schemes to
eliminate some of the anomalies contained in the original relation scheme R.
However the decomposition should be maintained with
(i) No loss of information
(ii) Dependency preserved
(iii) Attribute preserved.

To maintain the above properties we check the following.

(i) Lossless join decomposition
(ii) Dependency preserving
(iii) Attribute preserving
Lossless join decomposition: A decomposition of a relation scheme R in to the
relation schemes, Ri (1≤ i≤ n) is said to be lossless join decomposition or simply
lossless if for every relation R (R) that satisfies the FDS in F, the natural join of
the projections of R gives the original relation R. is R = π R1 (R) X π R2 (R) X
………… X π Rn (R) If RC = π R1 (R) X π R2 (R) X ………… X π Rn (R) then the
decomposition is called lossy.
Dependency Preserving: The given relation scheme R (S,F) where F is the set of
functional dependencies on the attribute in S, R is decomposed in to the relation
schemes R1, R2, ….. Rn with the functional dependencies F1, F2… Fn. Then this
decomposition of R is dependency preserving if the closure of F Where, F1 = (F1
U F2 …… U fn) is the identical to F+ (i.e. F+ = F) ie. F1 (R1) U F2 (R2) UF3 (R3)
…….Fn (Rn) = F+
Thm:
A decomposition of relation scheme R into R1 and R2 < (X,Z), F2> R2 < (X,Z,F2)
is
(a) Dependency preserving if every functional dependency in R can be logically
derived from the functional dependencies of R1 and R2 i.e. (F1, UF2) + = F+ and
(b) Is lossless if the common attributes X of R1 and R2 from a super key of at
least one of these i.e. X → Y or X → Z.
Example: Check for lossless decomposition
Let the given relation R (A,B,C,D) with the functional dependencies FD = {A→B,
A→C, C→D} .
let the relation has been decomposed preserving the dependencies as R1 (A,B,C)
and R2 (C,D).
let us verify whether it is loss less or not

Here, we considered the FD: C→ D, Since the symbols in column C are same and
hence we made the symbol in column C are same and hence we made the
symbols in column D same as one of the valve in D column is a . For other
dependencies A→ B, A →C we do not find two rows with identical entries for
columns of the determinant. Here we get one row with all a values lossless.

BCNF: A relation schema R is in BCNF with respect to a set for functional

dependencies, if for all FDS in . F+ X→ Y at least one of the following is true.
(i) X→ Y is trivial or
(ii) X is a super key

Example:
R (A,B,C) is the given relation schema and the given Functional Dependency is F
={A →B, B →C}

Solution: Key = {A} since A+ = {A,B,C}

R is not in BCNF as B is not a super key.
Decomposition:

The decomposition is lossless and dependency preserving.

Boyce Code Normal Form (BCNF)

• To eliminate the problems and redundancy of 3NF. Boyce proposed a normal
form known as Boyee code Normal form (BCNF).
• When the relation has more than one candidate key anamolies may arise even
though the relation is in 3NF.
• 3NF does not deal with the case of a relation with overlapping candidate keys.
• BCNF is based on the concept of a determinant
• A determinant is any attribute(s) on which some other attributes is fully
functionally dependent.

Def: A relation is in BCNF if and only if every determinant so candidate key. Let
us consider a relation R (A,B,C,D) with the set of functional dependencies. {A,C}
→ {B,D} {A,D} → {B}
• Here the first determinant suggests that the primary key of R could be changed
from {A.B} to {A,C}.
• If {A,C} would be the key then it could also determine all of the non key
attributes present in R.
• However the second determinant indicates that {A,D} determines B. But {A,D}
can’t be the key of R since it does not determine all the non key attributes of R
(Eg.C).
• Here, first determinant is a candidate key → {A,C}.
• But, the second determinant {A,D} is not a candidate key.

Thus, the relation R (A,B,C,D) is not in BCNF, since there exist over lapping keys
candidate keys. So the decomposition of the relation for BCNF is

Problem:
Here, there are two overlapping candidate keys {Manager, Machine} and
{Project code, Machine} In the functional dependencies
{Manager} → {Project Code}
{Project code} → {Manager}
Neither, manager, nor project code is a super key.
Decomposition for BCNF:
(1) PROJECT (Project code, Machine, Quantity used.
(2) MANAGER (Project code, Manager)
Comparison of 3NF and BCNF:
• BCNF is stronger than 3NF
• The relations there in 3NF are not necessarily in BCNF
• BCNF is needed in certain situations to obtain full understanding of the data
model.
• There are several routes to take to arrive at the same set of relations in BCNF.
Difference between 3NF and BCNF:
The difference between 3NF and BCNF is that for a functional dependency A→B,
3NF allows this dependency in a relation if B is a primary key attribute and A is
not a candidate key.
Whereas, BCNF insists that for this dependency to remain in this relation, A must
be candidate key.
Therefore, BCNF is a stronger form of 3NF, such that every relation in BCNF is
also in 3NF.
Problem:
The relation R (A,B,C) with FD = {B→C} exists. Does the relation have potential
candidate key If it does what is it ? if it does not why not.
Solution: R (A,B,C)
So, super key = {A,B,C}
F = {B→C}
A + = {A}
B + = {B,C}
AB+ = {A,B,C} The potential candidate key = {A,B}
Problem:
Let us consider a relation R (A,B,C,D,E). With following dependencies
{A,B} → {C}
{C,D} → {E},
{D,E} → {B} Find the candidate key of the given relation.
Solution: FDs are:
{A,B} → {C}
{C,D} → {E}
{D,E} → {B}
{A,B}+ = {A,B,C}
{A,B,D}+ = {A,B,C,D,E}
So, {A,B,D} is the candidate key

Multivalued Dependencies:
A multivalued dependency corresponds to a many many relationship or a many
one or one many relationship.
Def: The (Functional) Dependency represented by X →→ Y is said to be
multivalued dependency form X to Y if and only if each X value exactly
determined a set of Y values, independently of other attributes.
Def: The dependency X →→Y, Z is said to be a multivalue dependency if.
(i) For a single value of X there exist a set of values of Y
(ii) For a single value of X there exist a set of values of Z
Where Y and Z are independent of each other.

Explanation:
Let R be a relation and X and Y are any arbitrary set of attributes of R, if for any
two tuples, t1 and t2 with t1 [X] = t2 [X], there exists two tuples t3 and t4 such
that (Z=R=(XUY)).
  t1 [X] = t2 [X] = t3 [X] =t4 [X]
 t1 [Y] = t3 [Y] & t2 [Y] = t4 [Y]
 t1 [Z] = t4 [Z] & t2 [Z] = t3 [Z]
then X →→ Y
Example:
For, R (A,B,C)
(i) A →→B exist
(ii) A →→C exist

Trivial Multivalued Dependencies :

Trivial MVDS Let R is a relation with set of attributes X and Y then X→→Y is said
to be trivial iff.

(a) Y⊆ X or
(b) X U Y =R
(c) A trivial MVD does not represent a constraint.
(d) MVDs are generalization of FDS
(e) The existence of non-trivial MVDs that are not FDS causes problems.
Non Trivial MVD :
An MVD that satisfies neither (a) nor (b) conditions above is called non trivial
MVD.
Properties of MVDS:
Berry described the relevant rules to derive MVD
Rule 1: Reflexive (inclusive ): If YC X then X →→Y
Rule 2: Augmentation rule: If X→→Y and WCV and VCW then WX →→VY.
Rule 3 Transitive rule: If X→→Y and Y→→Z then X→→Z.
Rule 4 Complementation: if X →→Y then X →→U-X-Y holds. Additional rules to
derive closure of set of FDs and MVDs.
Rule 5 Intersection: If X→→Y and X →→Z, then X →→YnZ
Rule 6 Prado transitivity: If X →→Y and WY →→Z the XW→→Z-W
Rule 7 Union: If X →→Y and X →→Z then X→→YZ
Rule 8 Difference: If X →→Y and X→→Z then X→→Y-Z and X→→Z-Y.
Rule 9 Replicaiton: if X→Y , then X→→Y.
Rule 10 coalescence: If X→→Y and Z C Y and there is a W such that W C U and W
n Y = NULL and W→Z, then X→Z,
Note: U is the set of all attributes of R.
Fourth Normal Form:
Def: A relation R is said to be in fourth normal form (4NF) it is in BCNF and for
every non trivial MVD X→→Yin F+, X is a super key of R.
• The 4NF is concerned with dependencies between the elements of compound
keys composed of three or more attributes.
• The 4NF eliminates the problems of 3NF.
• The 4NF is violated if the relation has undesirable MVDS and hence can be
used to identify and decompose such relations.
Example:
In R (A,B,C) with MVDS
(i) A →→B
(ii) A →→C

Here, R = R1 X R2 So, it is a lossless decomposition.

Join Dependency:
 So for every relation was non loss decomposable in to two projections. In
case of n-decomposable relations we think about join dependency.
A join dependency is a further generalization of MVDS
Def: A join dependency (JD) X {R1 ,R2 ….Rn} is said to be hold over a relation
R if
R1, …… Rn is a lossless join decomposition of R.
An MVD X →→Y over a relation R can be expressed as the join dependency
{XY, X (R-Y) }
Example:
Let us consider the relation, CTB (Course, teacher, book)

Here in the CTB relation the MVD, C→→T can be expressed as the join
dependency {CT,CB} Join Dependency and multivalued dependency : (JDS Vs
MVDS)
• Join Dependency R (A,B,C) satisfies multivalued dependency (AB, AC) if and
only if it satisfies the MVDs A →→BIC.
• JD is the most general form of dependency (read ad determination) possible
between the attributes of a relation (in the relational model).
Fifth Normal Form: (5 NF)
Def: A relation schema R is said to be in fifth normal form (5NF) if, for every
JD X [R1. R2…Rn} that holds over R, one of the following statements is true.
• R1 = R for some I or
• The JD is implied by the set of those FDS over R in which the left side is a
key for R.
• The decomposition of R in to [R1. R2……….Rn} is lossless join whenever the
key dependencies (Functional dependency in which the left side is a key for
R) hold.
• JD X [R1. ……..…Rn} is a trivial FD if R1 = R for some I such a JD always
holds.
• If a relation schema is in 3NF and each of its keys consists of single
attribute it is also in 5NF.
(i) This is sufficient for a relation to be in 5NF but not necessary.
(ii) We conclude that a relation is in 5NF without ever identifying the
MVDS and JDS that may hold over the relation.