Database

Management
Systems
(24B11CS213)
Database Systems and Web

Lecture 25: Normalization: Data Dependencies,

Contents to be covered
Relation Scheme and Relational Design
Functional Dependencies (FD)
Closure
Armstrong’s Axioms
Closure of Attributes
Minimal Sets of Functional Dependencies
Normalization
1NF
 Relation Scheme and Relational Design

Referenced By:
1) Ramez Elmasri & Shamkant B. Navathe Fundamentals of Database Systems, 7th Edition and
2) Bipin C. Desai, An Introduction to Database Systems
 Example of Relation

Referenced By:
1) Ramez Elmasri & Shamkant B. Navathe Fundamentals of Database Systems, 7th Edition and
2) Bipin C. Desai, An Introduction to Database Systems
 FUNCTIONAL DEPENDENCY

● There is no exact method to specify dependency (at requirement gathering stage) .

● Use your common sense and judgement to specify dependencies
● Let X1 and X2 be the two columns of a R.
● Given the value of X1, if there is only one value of X2 corresponding to it, then X2 is
said to be functionally dependent on X1. This can be denoted as:
X1->X2
● Consider the following relation schema:
STD(Roll_no, Name, Phone_No)
● {Name, Phone_No} is functionally dependent on roll_no.
Referenced By:
1) Ramez Elmasri & Shamkant B. Navathe Fundamentals of Database Systems, 7th Edition and
2) 2) Bipin C. Desai, An Introduction to Database Systems
 Anomalies in a Database
Consider the following relation schema:
STDINF (Name, Course, Phone No, Major, Prof, Grade)
Following functional dependencies
FD1: Name->Phone No
FD2: Name-> Major
FD3: {Name,Course}-> Grade
FD4: Course-> Prof.
Referenced By:
1) Ramez Elmasri & Shamkant B. Navathe Fundamentals of Database Systems, 7th Edition and
2) 2) Bipin C. Desai, An Introduction to Database Systems
Anomalies in a Database
Anomaly 1-- Redundancy:
e.g. the major and phone_no of student are stored several times in the
database.

Anomaly 2-- Update anomalies:

e.g. Phone_no of “xyz” person is updated, inconsistency is there, if update
is made and only some of the multiple copies (of “xyz”) are updated.
Anomalies in a Database
Anomaly 3-- Insertion anomalies:
Let us consider SCHEDULE relation of Figure A.
If this is the only relation then professor is teaching a given course details
cannot be entered in the database unless a student is registered in the
course.

Anomaly 4-- Deletion anomalies:

same as above if the only student in the course discontinues the course
then information about the course offering by the prof will be lost.
FUNCTIONAL DEPENDENCY
▪ Let a relation R have some functional dependencies F specified.
▪ The closure of F (usually written as F+) is the set of all functional dependencies that
may be logically derived from F.
▪ Often F is the set of most obvious and important functional dependencies.
▪ F+, the closure, is the set of all the functional dependencies including F and those that
can be deduced from F.
Trivial Functional Dependency
Trivial − If a X → Y holds, where Y ⊆X, then it is called a trivial FD.
Non-trivial − If an FD X → Y holds, where Y ⊈X, then it is called a non-trivial FD.
Axioms
▪ To determine closure of the relation we need to learn some rules.
▪ Developed by Armstrong in 1974.
▪ There are six rules (axioms), using these RULES all possible functional
dependencies may be derived.
 Armstrong’s Axioms
1. Reflexivity Rule :
If Y ⊆ X,
then X → Y
each subset of X is functionally dependent on X.

2. Augmentation Rule :
If X → Y holds and
W is a set of attributes,
then WX → WY holds.

3. Transitivity Rule :
If X → Y and Y → Z holds,
then X → Z holds.
Derived Theorems from Armstrong’s Axioms
4. Union Rule :
If X → Y and X → Z holds,
then X → YZ holds.

5. Decomposition Rule :
If X → YZ holds,
then so do X → Y and X → Z.

6. Pseudotransitivity Rule :
If X → Y and WY → Z hold then so does WX → Z.
 Examples of Armstrong’s Axioms
We can find all of F+ by applying :
◦ if Y ⊆ X, then X → Y (reflexivity)
loan-no → loan-no
loan-no, amount → loan-no
loan-no, amount → amount

◦ if X → Y, then WX → WY (augmentation)
loan-no → amount (given)
loan-no, branch-name → amount, branch-name
Example: Closure of set F of functional dependencies

R = (A, B, C, G, H, I)
F= { A→B
A→C
CG → H
CG → I
B→H }
Find Closure of F: some members of F +
◦ A→H
◦ by transitivity from A → B and B → H
◦ AG → I
◦ by augmenting A → C with G, to get AG → CG
and then transitivity with CG → I
◦ CG → HI
◦ from CG → H and CG → I : “union rule”
Example
Example
 Example
QUES. Given this FD for this R(A,B,C,D,E,F)
AB C
AD E
B D
AF B
Check if AB+ is a key for this relation?
AB+ is key if AB+ can find all the attribute of R

Solution: X=AB, X->AB

AB AB
B D so B ⊆AB AB+ ABD
AD E so AD ⊆ABD AB+ ABDE
AB C so AB ⊆ABDE AB+ ABCDE
AF B so AF Not ⊆ABDE AB+ ABCDE
AB not a key because it does not contain all attributes such as F
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 ?

1. It is a super key.
2. (A+) = ABCH, (G+) = G.
YES.
 EQUIVALENCE OF SETS OF FUNCTIONAL
DEPENDENCIES
• Steps to check equivalence of two sets F and E of functional dependencies
1. Calculate X+ with respect to F for each FD X Y in E
2. Check whether this X+ includes the attributes in Y
• If this is the case for every FD in E, then F covers E

3. Similarly check whether E covers F

4. If E covers F and F covers E. then E+ = F+

 EQUIVALENCE OF SETS OF FUNCTIONAL
DEPENDENCIES
1. Consider the following two sets of functional dependencies:
F = {A C, AC D, E AD, E H}
G = {A CD, E AH}.
Check whether they are equivalent.
A+=ACD
(AC)+=ACD
E+=EAHCD
• Consider a set F of functional dependencies and the functional dependency α → β in F.
– Attribute A is extraneous in α if A ∈ α
and F logically implies (F – {α → β}) ∪ {(α – A) → β}.
– Attribute A is extraneous in β if A ∈ β
and the set of functional dependencies
(F – {α → β}) ∪ {α →(β – A)} logically implies F.

• Example: Given F = {A → C, AB → C }
– B is extraneous in AB → C because {A → C, AB → C} logically implies A → C (I.e. the result of dropping B from
AB → C).
• Sets of functional dependencies may have redundant dependencies that can be inferred from the others

– For example: A → C is redundant in: {A → B, B → C}

– Parts of a functional dependency may be redundant

• E.g.: on RHS: {A → B, B → C, A → CD} can be simplified to
• A → B, B → C, A C, A D
{A → B, B → C, A → D}

• E.g.: on LHS: {A → B, B → C, B → D, AC → D} can be simplified to

• {A → B, B → C, B → D, A → D} further simplified to {A → B, B → C, B → D}

• Intuitively, a canonical cover of F is a “minimal” set of functional dependencies equivalent to F, having no

redundant dependencies or redundant parts of dependencies
• A canonical cover of F is a set of dependencies Fc such that
– F logically implies all dependencies in Fc, and
– Fc logically implies all dependencies in F, and
– No functional dependency in Fc contains an extraneous attribute, and
– Each left side of functional dependency in Fc is unique.

• To compute a canonical cover for F:

repeat
Use the union rule to replace any dependencies in F
α1 → β1 and α1 → β2 with α1 → β1 β2
Find a functional dependency α → β with an
extraneous attribute either in α or in β
If an extraneous attribute is found, delete it from α → β
until F does not change

• Note: Union rule may become applicable after some extraneous attributes have been deleted, so
it has to be re-applied
Given: R = (A, B, C) F = {A → BC B→C A→B AB → C}
• Combine A → BC and A → B into A → BC
– Set is now {A → BC, B → C, AB → C}
• A is extraneous in AB → C
– Check if the result of deleting B from AB → C is implied by the other dependencies
• Yes: in fact, A → C is already present!
– Set is now {A → BC, B → C}
• C is extraneous in A → BC
– Check if A → C is logically implied by A → B and the other dependencies
• Yes: using transitivity on A → B and B → C.
– Can use attribute closure of A in more complex cases
• The canonical cover is: A→B
B→C
Normalization
• Normalization: The process of analyzing the given relation based on FDs
and primary keys to achieve the desirable properties of:
-Minimizing redundancy
-Minimizing anomalies (insertion, deletion, updation)
• Process of decomposing unsatisfactory "bad" relations by breaking up their
attributes into smaller relations to achieve above desirable properties.

• Two additional properties with normalization should be achieved for good

database design.
• Lossless join or nonadditive join
• Dependency preservation.
Normal forms
• Normal form: refers to the highest normal form condition that it meets, and hence indicates
the degree to which it is normalized.

• Condition using keys and FDs of a relation to certify whether a relation schema is in a
particular normal form

– First Normal Form (1NF)

– Second Normal Form (2NF)
– Third Normal Form (3NF)
– Boyce-Codd Normal Form (BCNF)
– Fourth Normal Form (4NF)
– Fifth Normal Form (5NF)

• 2NF, 3NF, BCNF based on keys and FDs of a relation schema

• 4NF based on keys, multi-valued dependencies : MVDs; 5NF based on keys, join dependencies :
JDs
Unnormalized Relation
First Normal Form
• To move to First Normal Form a relation must contain only atomic values at
each row and column.
– No repeating groups
– Disallows composite attributes, multivalued attributes, and nested
relations;
First Normal Form
 1NF Storage Anomalies
• Insertion: A new patient has not yet undergone surgery -- hence no surgeon
# -- Since surgeon # is part of the key we can’t insert.
• Insertion: If a surgeon is newly hired and hasn’t operated yet -- there will be
no way to include that person in the database.
• Update: If a patient comes in for a new procedure, and has moved, we need
to change multiple address entries.
• Deletion (type 1): Deleting a patient record may also delete all info about a
surgeon.
• Deletion (type 2): When there are functional dependencies (like side effects
and drug) changing one item eliminates other information.
Practice questions

Q1 List all functional dependencies satisfied by the relation of Figure

Q2. Compute the closure of the following set F of functional dependencies for relation
schema R = (A, B, C, D, E).
F= {A→BC, CD→E, B→D, E→A}
1. List the candidate keys for R.
2. compute the minimal cover