Dr.T.
THIMMAIAH INSTITUTE OF TECHNOLOGY
(Estd. 1986) Oorgaum, Kolar Gold Fields, Karnataka – 563120
(Affiliated to VTU, Belgaum, Approved by AICTE - New Delhi)
NAAC Accredited 'A' Grade
Department of Computer Science & Engineering
Database Management Systems – 21CS53
Module 4
1. Define Normalization
2. Explain the informal guidelines used to determine the quality of relation schema design.
Four informal guidelines that may be used as measures to determine the quality of relation schema design:
i. Making sure that the semantics of the attributes is clear in the schema
ii. Reducing the redundant information in tuples
iii. Reducing the NULL values in tuples
iv. Disallowing the possibility of generating spurious tuples. these measures are not always independent
of one another
i. Imparting Clear Semantics to Attributes in Relations
Semantics of a relation refers to its meaning resulting from the interpretation of attribute values in a tuple
Guideline 1: Design a relation schema so that it is easy to explain its meaning . Do not combine attributes
from multiple entity types and relationship types into a single relation
ii. Redundant Information in Tuples and Update Anomalies
One goal of schema design is to minimize the storage space used by the base relations. Grouping attributes
into relation schemas has a significant effect on storage space
Storing natural joins of base relations leads to an additional problem referred to as update anomalies.
These can be classified into: insertion anomalies deletion anomalies, modification anomalies
Dept. of CSE, [Link], KGF 1
Guideline 2
Design the base relation schemas so that no insertion, deletion, or modification anomalies are present in
the relations
If any anomalies are present, note them clearly and make sure that the programs that update the database
will operate correctly
iii. NULL Values in Tuples
If many of the attributes do not apply to all tuples in the relation, we end up with many NULLs in those
tuples - this can waste space at the storage level - may lead to problems with understanding the meaning
of the attributes - may also lead to problems with specifying JOIN operations
Dept. of CSE, [Link], KGF 2
Guideline 3
As far as possible, avoid placing attributes in a base relation whose values may frequently be NULL. If
NULLs are unavoidable, make sure that they apply in exceptional cases only and do not apply to a
majority of tuples in the relation
iv. Generation of Spurious Tuples
Guideline 4 : Design relation schemas so that they can be joined with equality conditions on attributes
that are appropriately related (primary key, foreign key) pairs in a way that guarantees that no spurious
tuples are generated Avoid relations that contain matching attributes that are not (foreign key, primary
key) combinations because joining on such attributes may produce spurious tuples.
Dept. of CSE, [Link], KGF 3
3. Define primary key, candidate key, prime attribute, non-prime attribute with examples each
4. Explain Functional dependency with an example
A functional dependency is a constraint between two sets of attributes from the database. Given a relation
R, a set of attributes X in R is said to functionally determine another attribute Y, also in R, (written X Y)
if and only if each X value is associated with at most one Y value.
Dept. of CSE, [Link], KGF 4
5. Explain 1NF- first normal form with example
Department (R1) Dept_Locations(R2)
Dname Dnumber Dmgr_ssn Dnumber Dlocation
Dept. of CSE, [Link], KGF 5
6. Explain 2NF- second normal form with example
Dept. of CSE, [Link], KGF 6
7. Explain 3NF- third normal form with example
Dept. of CSE, [Link], KGF 7
Dept. of CSE, [Link], KGF 8
8. Define general definition of Second and Third Normal form
9. Explain Boyce-Codd normal form BCNF with example
Dept. of CSE, [Link], KGF 9
10. Explain 4NF with example. When it is violated? Why is it useful?
Dept. of CSE, [Link], KGF 10
Dept. of CSE, [Link], KGF 11
11. Explain 5NF with an example.
Dept. of CSE, [Link], KGF 12
12. What is closure? Write the algorithm to find the closure and explain with example.
Dept. of CSE, [Link], KGF 13
13. Write an algorithm to find the minimal cover set of functional dependencies. Construct minimal
cover m for set of functional dependencies which are E: {B→A, D→A, AB→D}
Dept. of CSE, [Link], KGF 14
14. Explain Armstrong Inference rules.
Armstrong Inference rules are,
Dept. of CSE, [Link], KGF 15
15. Consider Relation R={A,B,C,D,E,F,G,H,I,J} and the set of functional dependencies,
F= { {A,B} →{C}
{A} → {D,E}
{B} → {F}
{F} → {G,H}
{D} → {I,J} } What is key of R, decompose R into 2NF and then 3NF relation.
Normalizing relation R on the basis of primary key {A, B} into a 2NF
Here C, D, E, F, G, H, I, J are all non-prime attributes.
FD2, FD3, FD4 & FD5 have partial dependencies of nonprime attributes on primary key
Hence 2NF form is:
R1 = {A, B, C}
R2 = {A, D, E, I, J}
R3 = {B, F, G, H}
Since R2 and R3 have transitive functional dependencies hence they are not in 3NF.
Transitive FDs A→D→{I, J} & B→F→{G, H}
Hence 3NF form is:
R1 = {A, B, C},
R2A = {A, D, E}
R2B = {D, I, J}
R3A = {B, F}
R3B = {F, G, H}
16. Construct minimal cover m for set of functional dependencies which are
FD: { A→C, AC→D, E →AD, E→H }
Step 1: {A->C, AC->D, E->H, E->A, E->D}
Step 2: {A->C, AC->D, E->H, E->A}
Here Redundant FD : {E->D}
Step 3: {AC->D}
{A}+ = {A,C}
Therefore C is extraneous and is removed.
{A->D}
Minimal Cover = {A->C, A->D, E->H, E->A}
Dept. of CSE, [Link], KGF 16
17. Construct minimal cover m for set of functional dependencies FD:{AB->C, D->E, AB->E, E-
>C}
Step 1: {AB->C, D->E, AB->E, E->C}
Step 2: {D->E, AB->E, E->C}
Here Redundant FD = {AB->C}
Step 3: {AB->E}
{A}+ = {A}
{B}+ = {B}
There is no extraneous attribute.
Therefore, Minimal cover = {D->E, AB->E, E->C}
18. Consider 2 sets of FD F={ A→C, AC→D, E →AD, E→H } and G ={A→CD, E→AH}, Are they
equivalent?
19. Given below are 2 sets of FDs for a relation R = {A,B,C,D,E}, are they equivalent?
F1={A→B, AB→C, D→AC, D→E}
F2={A→BC, D→AE}
Dept. of CSE, [Link], KGF 17
