Database Technologies
Contents
• Data Redundancy
• Data Anomalies
• Database Constraints (Unique, Not Null, Foreign
Key, Default, Check*)
• Functional Dependency
• Normalization
• Need for Normalization
• Normal Forms (1st NF, 2nd NF, 3rd NF, BCNF) with
examples, Introduction to 4th and 5th NF
• DML (INSERT/UPDATE/DELETE)
Normalization
• Normalization is a data analysis technique to
design a database system.
– An analytical technique used during logical database
design
– Offers a strategy for constructing relations and
identifying keys
• Normalization is a technique for producing
relational schema with the following properties:
– No Information Redundancy
– No Update Anomalies
Why Normalize - 1
emp emp join dept dept dept dept
code name date code name mngr bdgt
7369 shah 17-Dec-80 prch purchase roy 5
7499 ray 20-Feb-81 prch purchase roy 5
7521 jain 02-Apr-82 prch purchase roy 5
7654 gupta 28-Sep-79 info infoserv rao 6.5
redundancy
Why Normalize - 2
• emp
attributes
emp arejoinlost because
dept ofdeptthe deletion
dept dept
code name date code name mngr bdgt
of other attributes
7369 shah 17-Dec-80 prch purchase roy 5
7499 ray 20-Feb-81 prch purchase roy 5
7521 jain 02-Apr-82 prch purchase roy 5
7654 gupta 28-Sep-79 info infoserv rao 6.5
attributes are lost because of the deletion deletion
of other attributes
anomaly
Why Normalize - 2
emp emp join dept dept dept dept
code name date code name mngr bdgt
7369 shah 17-Dec-80 prch purchase roy 5
7499 ray 20-Feb-81 prch purchase roy 5
7521 jain 02-Apr-82 prch purchase roy 5
7654 gupta 28-Sep-79 info infoserv rao 6.5
deletion
anomaly
Why Normalize - 3
emp emp join dept dept dept dept
code name date code name mngr bdgt
7369 shah 17-Dec-80 prch purchase roy 5
7499 ray 20-Feb-81 prch purchase roy 5
7521 jain 02-Apr-82 prch purchase roy 5
7654 gupta 28-Sep-79 info infoserv rao 6.5
Update Anomaly exists when one or update
more instances of duplicated data is
updated, but not all.
anomaly
Why Normalize - 3
emp emp join dept dept dept dept
code name date code name mngr bdgt
7369 shah 17-Dec-80 prch purchase apte 5
7499 ray 20-Feb-81 prch purchase apte
roy 5
7521 jain 02-Apr-82 prch purchase apte
roy 5
7654 gupta 28-Sep-79 info infoserv rao 6.5
update
anomaly
Why Normalize - 4
emp emp join dept dept dept dept
code name date code name mngr bdgt
7369 shah 17-Dec-80 prch purchase roy 5
7499 ray 20-Feb-81 prch purchase roy 5
7521 jain 02-Apr-82 prch purchase roy 5
info infoserv rao 6.5
Insert Anomaly occurs when certain
attributes cannot be inserted into the
insertion
database without the presence of other anomaly
attributes
Normalisation Stages
• Process involves applying a series of tests on
a relation to determine whether it satisfies or
violates the requirements of a given normal
form.
– When a test fails, the relation is decomposed into
simpler relations that individually meet the
normalization tests.
– The higher the normal form the less vulnerable to
update anomalies
Normal Form??
• “restriction” on a relation
• a relation that satisfies certain
rules/conditions
• a relation that exhibits certain
properties
• depending on the conditions it
satisfies/the properties it exhibits,
the relation is said to be in the “nth
Normal Form”
Normal Forms
• 1 NF
• 2 NF
• 3 NF Functional Dependency
• BCNF
• 4NF Multi-valued Dependency
Join Dependency
• 5NF
Hierarchy of Normal Forms
1 NF
2 NF
3 NF
BCNF
Normal Forms are INCREMENTAL
Hierarchy of Normal Forms
• It must be emphasised here, that the
definition of a Normal Form is INCREMENTAL.
• You cannot have some relation that is in X-
normal form, but not in (X-1) Normal Form.
• If a relation is in 3 NF, it also has to be in 2NF,
which means it is also in 1NF.
Integrity Constraints
• Databases are structured stores of data
• Data must be accurate
– Semantic accuracy v/s Syntactic accuracy
◼consider an attribute age of type int. Any integer
would be syntactically correct; but if the attribute
pertains to the age of say, drivers, then any value
less than 18 would be semantically incorrect.
• Integrity constraints are the business rules
of the problem-domain.
Domain Constraints
• Integrity constraints guard against accidental
damage to the database, by ensuring that
authorized changes to the database do not result
in a loss of data consistency.
• Domain constraints are the most elementary form
of integrity constraint.
Referential Integrity
• Ensures that a value that appears in one relation for a given set of attributes also
appears for a certain set of attributes in another relation.
• Formal Definition
– Let r 1 (R 1 ) and r 2 (R 2 ) be relations with primary keys K 1 and K 2
respectively.
– The subset α of R 2 is a foreign key referencing K 1 in relation r 1 , if for every t
2 in r 2 there must be a tuple t 1 in r 1
• such that t 1 [K 1 ] = t 2 [α].
• Referential integrity constraint: Π α (r 2 ) ⊆ Π K 1 (r 1 )
more on Integrity Constraints
• 3 types of Integrity Constraints are of interest:
– Functional Dependencies (FD)
– Multi-Valued Dependency (MVD)
– Join-Dependency (JD)
• FDs are the most commonly used integrity
constraints in normalization.
Functional Dependencies
• Defines a constraint between two (sets of)
attributes of a relation
• Require that the value for a certain set of
attributes determines uniquely the value
for another set of attributes.
• Written as “X→Y”* (read “X determines Y”)
* here, “X” is called the “determinant” and “Y”, the “consequent”
Unnormalized
emp emp grade grade desig change grade desig
emp_data
code name code stage code date descr descr
7369 shah 12 3 slasst 20-Feb-82 Asst_A Sls Asst
--- --- --- --- ---
---
--- --- --- --- ---
---
7499 ray 23 2 supr 17-Jan-95 Offcr A Superint.
--- --- --- --- ---
--- --- --- --- ---
---
---
not
in
multi-valued attributes
1NF!
Unnormalized 1NF
•Eliminate variable repeating
fields and groups so that all
attributes take atomic values
A relation is said to be in “first normal form” (1NF) if and only if all
its attributes assume only atomic(indivisible) values.
Unnormalized 1NF
emp emp grade grade desig change grade desig
emp_data
code name code stage code date descr descr
7369 shah 12 3 slasst 20-Feb-82 Asst_A Sls Asst
--- --- --- --- ---
---
--- --- --- --- ---
---
7499 ray 23 2 supr 17-Jan-95 Offcr A Superint.
--- --- --- --- ---
--- --- --- --- ---
---
---
Unnormalized 1NF
emp emp_hist
emp emp
emp grade grade desig change grade desig
code name
code code stage code date descr descr
7369 shah
7499 ray 7369 12 3 slas 20-Feb-82 Asst_A Sls_Asst
in 7369 --- --- --- --- --- ---
7369 --- --- --- --- --- ---
1NF! 7369 --- --- --- --- --- ---
7369 --- --- --- --- --- ---
7499 23 2 supr 17-Jan-95 Offcr A Superint.
7499 --- --- --- --- --- ---
in 7499 --- --- --- --- --- ---
1NF!7499 --- --- --- --- --- ---
1NF 2NF
Eliminate fields that are
facts about only a subset of
the key so that all non-key
domains are fully
functionally dependent on
the primary key.
A relation is said to be in 2NF if and only if it is in 1NF and every non-
key attribute is fully functionally dependent (No partial dependency)
on any key.
1NF emp_hist
emp ?
emp_hist emp grade grade desig change grade desig
code code stage code date descr descr
Grade_descr
7369 12 3 slas 20-Feb-82 Asst_A Sls_Asst
is not fully 7369 --- --- --- --- --- ---
functionally 7369 --- --- --- --- --- ---
7369 --- --- --- --- --- ---
dependent on the 7369 --- --- --- --- --- ---
primary key.
7499 23 2 supr 17-Jan-95 Offcr A Superint.
7499 --- --- --- --- --- ---
7499 --- --- --- --- --- ---
not in 7499 --- --- --- --- --- ---
2NF!
Normalization 25
Eliminating partial dependencies
emp_hist
1NF emp grade grade desig change grade desig
code code stage code date descr descr
emp
emp_hist 7369
7369
12
---
3
---
slas
---
20-Feb-82
---
Asst_A
---
Sls_Asst
---
7369 --- --- --- --- --- ---
7369 --- --- --- --- --- ---
7369 --- --- --- --- --- ---
7499 23 2 supr 17-Jan-95 Offcr A Superint.
7499 --- --- --- --- --- ---
7499 --- --- --- --- --- ---
7499 --- --- --- --- --- ---
Eliminating partial dependencies
emp_hist
1NF emp grade grade desig change desig
code code stage code date descr
emp
emp_hist 7369
7369
12
---
3
---
slas
---
20-Feb-82
---
Sls_Asst
---
7369 --- --- --- --- ---
7369 --- --- --- --- ---
7369 --- --- --- --- ---
7499 23 2 supr 17-Jan-95 Superint.
7499 --- --- --- --- ---
7499 --- --- --- --- ---
7499 --- --- --- --- ---
1NF
emp
emp_hist emp_hist
emp grade grade desig change desig
grade code code stage code date descr
grade grade
code descr
7369 12 3 slas 20-Feb-82 Sls_Asst
12 Asst_A 7369 --- --- --- --- ---
7369 --- --- --- --- ---
23 Offcr A 7369 --- --- --- --- ---
7369 --- --- --- --- ---
7499 23 2 supr 17-Jan-95 Superint.
in 7499 --- --- --- --- ---
7499 --- --- --- --- ---
2NF 7499 --- --- --- --- ---
Normalization 28
2NF 3NF
Eliminate non-key fields
that are facts about other
non-key fields, so that all
non-key domains are
mutually independent.
A relation is said to be in 3NF if and only if it is in 2NF and for every
nonkey attribute is non transitively dependent on primary key.
2NF emp_hist
emp
emp_hist
emp grade grade desig change desig
grade code code stage code date descr
7369 12 3 slas 20-Feb-82 Sls_Asst
desig_descr is 7369 --- --- --- --- ---
7369 --- --- --- --- ---
transitively 7369 --- --- --- --- ---
dependent on the 7369 --- --- --- --- ---
primary key. 7499 23 2 supr 17-Jan-95 Superint.
7499 --- --- --- --- ---
not in 7499 --- --- --- --- ---
7499 --- --- --- --- ---
3NF
Normalization © 2015, CDAC 30
Eliminating Transitive Dependencies
emp_hist
2NF
emp emp grade grade desig change desig
code code stage code date descr
emp_hist
grade 7369 12 3 slas 20-Feb-82 Sls_Asst
7369 --- --- --- --- ---
7369 --- --- --- --- ---
7369 --- --- --- --- ---
7369 --- --- --- --- ---
7499 23 2 supr 17-Jan-95 Superint.
7499 --- --- --- --- ---
7499 --- --- --- --- ---
7499 --- --- --- --- ---
Eliminating Transitive Dependencies
emp_hist
2NF
emp emp grade grade desig change
code code stage code date
emp_hist
grade 7369 12 3 slas 20-Feb-82
7369 --- --- --- ---
in 7369 --- --- --- ---
3NF 7369 --- --- --- ---
desig 7369 --- --- --- ---
desig desig
7499 23 2 supr 17-Jan-95
code descr
7499 --- --- --- ---
slas Sls_Asst 7499 --- --- --- ---
supr Superint. 7499 --- --- --- ---
3NF BCNF*
• A relation schema R is in BCNF with respect to a set F of functional dependencies if for all
functional dependencies in F+ of the form where and at least one of
the following holds:
*BCNF = Boyce Codd Normal Form
3NF BCNF*
Eliminate key fields that are
facts about other (key) fields
so that every determinant
becomes a superkey.
*BCNF = Boyce Codd Normal Form
A relation is said to be in BCNF if and only if, for every nontrivial FD
A→B, ‘A’ is a superkey.
Problem-Domain (BCNF)
Consider a sales-management scenario:
• There are several product categories.
• Products are sold in several cities.
• Each city has several agents.
• Each product category is sold in each city by several retail
outlets.
• A given product category is distributed in a given city by
one and only one agent.
• A given agent will operate in one and only one city.
• A given agent can stock & sell more than one product
category for the same city.
Problem-domain (BCNF)
An appropriate schema would be
Supply {Product, City, Outlets, Agent}
Supply FDs:
Product City Outlets Agent {P, C} → {O, A}
Noodles Margao 155 Daulat {A} → {C}
Chocolates Margao 110 Keshav
{A,P} → {C}
Baby Foods Margao 235 Daulat
Ketchup Panjim 163 Magsons
Noodles Panjim 195 Aletta not in
Chocolates Vasco 102 Pranav BCNF
3NF BCNF
Supply
A_City A_Product
Product City Outlets Agent City Agent Product
Noodles Margao Daulat Margao Daulat Noodles
155
Keshav Margao Daulat Baby Foods
Chocolates Margao 110
Magsons Panjim Keshav Chocolates
Baby Foods Margao 235 Aletta Panjim Magsons Ketchup
Ketchup Panjim 163 Pranav Vasco Aletta Noodles
Noodles Panjim 195 Pranav Chocolates
Chocolates Vasco 102
BCNF
A B C
FD1 •Schematic relation in 3NF but not
in BCNF
B being prime attribute (member
FD2
of some candidate key)
Beyond BCNF...
• CTX is in BCNF, it has Schema CTX
no functional
CTX
dependency since it is
an all key relation course teachers texts
• a course is taught by Phy Green T1
multiple teachers Phy Green T2
• the course uses Phy Brown T1
multiple textbooks Phy Brown T2
Math Green T1
• there is redundancy Math Green T2
More redundancies …
COURSE TEACHERS TEXTS
Physics Prof. Green Basic Mechanics
Prof. Brown Principles of Optics
Math Prof. White Basic Mechanics
Vector Analysis
Trigonometry
Note: There are no FDs in this relation.
More redundancies …
Redundandanc
CTX
y !!
COURSE TEACHERS TEXTS
Physics Prof. Green Basic Mechanics
Physics Prof. Green Principles of Optics
Physics Prof. Brown Basic Mechanics
Physics Prof. Brown Principles of Optics
Math Prof. White Basic Mechanics
Math Prof. White Vector Analysis
Math Prof. White Trigonometry
Constraint: IF tuples (c, t1, x1), (c, t2, x2) both appear
THEN tuples (c, t1, x2), (c, t2, x1) both appear also
• Redundancy :
– TO add information that a physics course can be
taught by a new teacher
• Insert two new tuples
Multi-valued Dependency
IF tuples (c, t1, x1), (c, t2, x2) both appear
THEN tuples (c, t1, x2), (c, t2, x1) both appear also
Course teachers
Course texts
They are independent MVDs
Multi-valued Dependency
• Defines a constraint between two (sets of) attributes of a
relation
• Constraint in turn, defined by the semantics of the problem-
domain
• Helps identify redundancy that cannot be identified by mere FD
analysis
• MVDs are generalization of FDs
– Every FD is MVD but converse is not true
◼ → Y” (read “X multidetermines Y”)
Written as “X→
• For a relation R (A,B,C) the MVD
– A B holds if and only if MVD A C also
holds
MVD: Defined
given a relation schema R, and two attribute sets X, Y such
that
X R, Y R,
→
then, the MVD “X→ Y” means
t1 ,t2, t3, t4 r ( ‘r’ is an instance of ‘R’)
the following is true
t1 [X] = t2 [X] = t3 [X] = t4 [X]
t1 [Y] = t3 [Y]
t3 [R-Y] = t2 [R-Y]
t4 [Y] = t2 [Y]
t4 [R-Y] = t1 [R-Y]
BCNF 4NF
BCNF 4NF
CT CX
CTX
course teacher course
text
course teacher
text
Phy Green Phy T1
Phy Green T1 Phy Brown Phy T2
Phy Green T2 Math White Math T3
Phy Brown T2 Math T4
Phy Brown T1
Math white T3
Math White T4
In 4NF!
Eliminating independent, multi-valued facts
• Not in 4NF because the following non trivial multivalued
dependency holds on them and Course is not a superkey
Course texts
Course teachers
• After decomposition the two relations are in 4NF because the
MVD are trivial MVD(i.e their union produces the original
relation)
Normalization : a recap
• leads to a design that caters to ad-hoc queries.
• prevents update anomalies and data
inconsistencies.
• facilitates data independence.
• penalises data retrieval.
• rule-based, but intricately influenced by
semantics of the attributes.
Normal Forms : a recap
Eliminate repeating groups; attributes must have only atomic
1NF values.
Eliminate partial dependencies; all non-key attributes must be
2NF functionally dependent on entire primary key, not on a subset thereof.
Eliminate transitive dependencies; all non-key domains must be
3NF mutually independent.
Normal Forms : a recap
Eliminate FDs with prime attributes in the consequent; all
BCNF determinants must be super keys.
Eliminate independent, multi-valued attributes.
4NF
References - I
An Introduction to DB Systems (7/e)
C. J. Date
Addison-Wesley (Pearson-Asia Education)
Database System Concepts (3/e)
Silberschatz, Korth, Sudarshan
McGraw-Hill International Edition
Database Management Systems
Raghu Ramakrishnan
McGraw-Hill International Edition
Fundamental of Database Systems
Elmasri
Navathe
Normalization