Database

Normalization
Muhammad Ali
 • Decompose table into multiple
tables
• Each table must have lossless
Normalizati decomposition
on • There are two types of
dependencies
• Functional Dependencies
• Multivalue Dependencies
 • A functional dependency is a relationship
between two set of attributes(columns)
• Value of one set of attributes uniquely
determine values in other set of attributes
• It is written as X → Y
Function • Means X functionally determines Y
Dependen • Determinant (X): This is the attribute or
set of attributes on the left side of the
cy arrow. If you know the value(s) of the
determinant, you can uniquely identify the
value(s) of the dependent.
• Dependent (Y): This is the attribute or set
of attributes on the right side of the arrow.
Its value is determined by the determinant.
 Let R be a relation schema
α ⊆ R and β⊆ R

Function The functional dependency

α→β
Dependen holds on R if and only if for any legal
cy relations r(R), whenever any two tuples
t1 and t2 of r agree on the attributes α,
they also agree on the attributes β. That
is,

t1[α] = t2 [α] ⇒ t1[β] = t2 [β]

Consider
following
salar dept_nam buildin
id name budget
y e g
1 Alice Smith 60000 Engineering 1000000 Main
table 2
3
Bob Johnson
Carol White
75000 Sales 500000 Annex
62000 Engineering 1000000 Main
4 David Brown 50000 HR 200000 Admin
5 Eva Green 80000 Marketing 300000 Annex
6 Frank Black 70000 Engineering 1000000 Main
7 Grace Hall 55000 Sales 500000 Annex
8 Henry King 90000 Engineering 1000000 Main
9 Ivy Scott 48000 HR 200000 Admin
10 Jack Adams 68000 Marketing 300000 Annex
11 Karen Lee 72000 Engineering 1000000 Main
12 Leo Wilson 63000 Sales 500000 Annex
 • In this table, we can identify several
functional dependencies:
id → name, salary, dept_name,
budget, building

Functional • Given an id, you can uniquely

Dependen determine the employee's name,
salary, department name, budget, and
cy building

• For example, id = 1 always refers to

Alice Smith with a salary of 60000 in
the Engineering department, budget
1000000 in the Main building
 dept_name → budget, building

• Given a dept_name, you can uniquely

determine the budget and building for
that department.
Functional
Dependen • For instance, "Engineering" always has a
budget of "1000000" and is in the "Main"
cy building.

• This means that if you know the

department name, you don't need to look
up the budget or building in another
place, they're consistently linked to that
department name.
 • The closure of a set of
functional dependencies (FDs),
Closure of denoted as F+, is the complete
set of all functional
a set of dependencies that are logically
Functional implied by a given set of FDs
(F).
dependenc • Think of it as deriving every single
ies dependency that must hold true in
a database if the initial set of FDs
holds true.
 • If you know an employee's ID, you know
their department.
ID → Dept
• If you know a department, you know its
Logical building
implication Dept → Building
• From these two rules, you can logically
of Functional imply a third rule:
Dependenci • If you know an employee's ID, you know
es their building.
ID → Building
• This third rule ID → Building would be part
of the closure of the initial set of FDs {ID
→ Dept, Dept → Building}.
 • K is a superkey for relation schema R if and only if
K→R
• K is a candidate key for R if and only if
K → R, and for no α ⊂ K, α → R
• Functional dependencies allow us to express
Keys and constraints that cannot be expressed using
superkeys. Consider the schema:
Functional in_dep (ID, name, salary, dept_name, building,
budget ).
Dependenci
es • We expect these functional dependencies to hold:
dept_name→ building
ID → building
but would not expect the following to hold:
dept_name → salary
 • A functional dependency is trivial if
it is satisfied by all instances of a
relation
Trivial • Example:
Functional ID, name → ID
Dependenci name → name
es
In general, α → β is trivial if β⊆ α
 • A multivalued dependency (MVD)
occurs when, in a table with at least
three attributes (X, Y, and Z), X
determines multiple values of Y, and X
also determines multiple values of Z,
Multivalue but Y and Z are independent of each
d other.
• It's often written as X → → Y, meaning
Dependen "X multidetermines Y.”
cy • Think of it this way: if you know the
value of X, you can find a set of Y
values and a set of Z values. The
crucial part is that the set of Y values
isn't related to the set of Z values;
they're independent.
 • The key difference lies in the "multi"
aspect:
• Functional Dependency (X → Y): For
MVD vs. a single value of X, there is exactly
one corresponding value of Y.
Functional • Multivalued Dependency (X → → Y):
For a single value of X, there can be
Dependen multiple corresponding values of Y,
and these multiple values are
cy (FD) independent of other attributes in the
table (that are also multidetermined by
X).
 • Let's imagine a table CourseInfo with the following attributes:
Course, Textbook, and Instructor.

Course Textbook Instructor

Database SQL Basics Prof. Smith
Database Data Models Prof. Smith

Multivalue
Database SQL Basics Prof. Jones
Database Data Models Prof. Jones
• Here's how MVDs come into play:
Algorithms Intro Algo Prof. Brown

d
• For the Course "Database," there are multiple Textbooks ("SQL
Basics", "Data Models") and multiple Instructors ("Prof. Smith",
"Prof. Jones").

Dependen • The set of Textbooks for "Database" is independent of the set of

Instructors for "Database." In other words, assigning a new
textbook to "Database" doesn’t necessarily mean you have to
cy change or add instructors, and vice versa.
• This table exhibits two multivalued dependencies:
Course → → Textbook
Course → → Instructor
• The redundancy arises because if "Database" gets a new
textbook, say "Advanced SQL," you'd have to add two new rows
(one for "Prof. Smith" and one for "Prof. Jones") to maintain
consistency for all existing instructors for that course. This type
of redundancy is what
 • A table is considered to be in 1NF if it meets the
following three main conditions:
• Atomic Values: Each cell in the table must contain a
single, indivisible value. This means you shouldn't have
multiple values (like a comma-separated list, an array,
or a nested table) within a single cell. For example, a
"Phone Numbers" column shouldn't store "555-1234,

First 555-5678" in one cell. Instead, each phone number

should be in its own row, perhaps with the associated ID
repeating.
Normal • Unique Column Names: Every column in the table
must have a distinct name. This prevents ambiguity
Form(1NF) when referring to data.
• No Repeating Groups (or Repeating Columns):
There should be no sets of columns that essentially
store the same type of information. For instance, if you
have Skill1, Skill2, Skill3 columns to list an employee's
skills, this violates 1NF because it's a repeating group of
attributes. To fix this, you'd create separate rows for
each skill, duplicating the employee's other information
as needed, or create a separate table for skills.
 • Reduces Redundancy: By ensuring
atomic values and eliminating
repeating groups, 1NF helps reduce
unnecessary duplication of data.
• Improves Data Integrity:
First Consistent data entry and easier
enforcement of data constraints
Normal become possible when data is
Form(1NF) structured according to 1NF.
• Simplifies Queries: With data
organized into single, atomic values,
it's much easier to query, sort, and
filter information using standard SQL
operations.
 • Second Normal Form (2NF) is
the next step in database
normalization after a table has
Second achieved First Normal Form (1NF).
Normal • The primary goal of 2NF is to
eliminate partial dependencies.
Form This means that all non-key
attributes must be fully dependent
(2NF) on the entire primary key, not just a
part of it.
 • A table must first be in 1NF to be
considered for 2NF. Recall that 1NF
Prerequisit ensures:
• All values are atomic.
es for 2NF • There are no repeating groups.
• Each column has a unique name.
 • The Core Rule of 2NF: No Partial
Dependencies
• A partial dependency occurs when a
non-key attribute (an attribute that is
not part of any candidate key) is
The Core functionally dependent on only part of
a composite primary key.
Rule of • Composite Primary Key: A primary
2NF key made up of two or more attributes.
• If a table has a single-attribute primary
key, it is automatically in 2NF
(assuming it's already in 1NF) because
there's no "part" of the key for a non-
key attribute to be partially dependent
on.
 • Let's consider a hypothetical OrderDetails table
that includes information about an order and the
product ordered:
Example OrderI ProductI Quantit
D
101
D
P1
y
2
ProductName ProductPrice
Laptop 1200

with
101 P2 1 Mouse 25
102 P1 3 Laptop 1200

• The composite primary key is {OrderID,

Partial ProductID} because both are needed to uniquely
identify each row (e.g., Order 101 with Product P1).
Dependen • Quantity is fully dependent on {OrderID,
ProductID} (the quantity of a specific product in a
cy specific order).
• However, ProductName and ProductPrice are only
(Violating dependent on ProductID (a part of the composite
primary key), not on the OrderID. This is a partial
2NF) dependency.
• This design has redundancy: "Laptop" and "1200"
are repeated for every order that includes
ProductID "P1."
 • To resolve partial dependencies and bring
the table into 2NF, you decompose the
Example table into multiple tables, ensuring that
non-key attributes are fully dependent on
with the primary key of their respective tables.
• Continuing the example, we would
Partial decompose OrderDetails into two tables:
Dependen • OrderLineItems handles order specific
details
cy
OrderI ProductI Quantit
D D y
101 P1 2

(Violating
101 P2 1
102 P1 3

2NF) • Primary Key: {OrderID, ProductID}

• Quantity is fully dependent on the entire
composite key.
 • Product handles product specific details
Example
with
ProductI
D ProductName ProductPrice
P1 Laptop 1200
P2 Mouse 25

Partial • Primary Key: {ProductID}

• ProductName and ProductPrice are
Dependen fully dependent on ProductID.
cy
(Violating • Now, each table is in 2NF. This
decomposition reduces redundancy and
2NF) makes the database more efficient and
easier to manage.
 • Third Normal Form (3NF) builds upon 2NF.
A table is in 3NF if:
• It is already in 2NF.
• It contains no transitive dependencies.
Third • A transitive dependency occurs when a
non-key attribute is indirectly dependent
Normal on the primary key through another non-
key attribute. In simpler terms, if A → B
Form and B → C, then C is transitively
(3NF) dependent on A through B. 💡
• The goal of 3NF is to eliminate
redundancy that arises when an attribute
does not directly depend on the primary
key, but rather on another non-key
attribute.
 dept_na
id name salary budget building
me
Engineeri
1 Alice Smith 60000 1000000 Main
ng
Bob
Example of 2
Johnson
75000 Sales 500000 Annex
Carol Engineeri
3NF, 3
White
62000
ng
1000000 Main

eliminating 4
David
Brown
50000 HR 200000 Admin

transitive 5 Eva Green

Frank
80000 Marketing
Engineeri
300000 Annex

dependency 6
Black
70000
ng
1000000 Main
7 Grace Hall 55000 Sales 500000 Annex
Engineeri
8 Henry King 90000 1000000 Main
ng
9 Ivy Scott 48000 HR 200000 Admin
Jack
10 68000 Marketing 300000 Annex
Adams
Engineeri
11 Karen Lee 72000 1000000 Main
 • Here's the breakdown of
dependencies:
Example • id → name, salary, dept_name:
of 3NF, An employee's ID uniquely
eliminatin determines their name, salary, and
the department they belong to.
g • dept_name → budget, building:
transitive The department name uniquely
determines its budget and the
dependen building it's located in.
cy • The transitive dependency is:
id → dept_name → budget, building.
Example • This means budget and building are
determined by dept_name, which in
of 3NF, turn is determined by id.
eliminatin • This creates redundancy because
the budget and building information
g for a department (e.g.,
transitive "Engineering" has a budget of
"1000000" and is in "Main") is
dependen repeated for every employee in that
cy department.
 • This means budget and building are
determined by dept_name, which in
Example turn is determined by id.
of 3NF, • This creates redundancy because the
eliminatin budget and building information for a
department (e.g., "Engineering" has a
g budget of "1000000" and is in "Main")
is repeated for every employee in
transitive that department.
dependen • To move to 3NF, we need to remove
the transitive dependency by creating
cy new tables for the attributes that are
transitively dependent.
 • We'll split the original table into two: one for
employee-specific data and one for
department-specific data.
Example • By performing this decomposition, we achieve
of 3NF, the following benefits:
• Reduced Redundancy: Department budget
eliminatin and building information is now stored only
once in the Departments table, rather than
g being repeated for every employee in that
department.
transitive • Improved Data Integrity: If a department's
budget or building changes, you only need to
dependen update it in one place (Departments table),
minimizing the risk of inconsistencies.
cy • Easier Maintenance: Adding a new
department or changing department details is
simpler and less error-prone.
 • Here are the tables normalized to
Example Third Normal Form:
of 3NF, • 1. Employees Table (Contains
employee-specific information
eliminatin directly dependent on id
dept_nam

g
ID name salary
e
Alice
1 60000 Engineering
Smith

transitive
Bob
2 75000 Sales
Johnson
Carol
3 62000 Engineering

dependen
White
David
4 50000 HR
Brown
5 Eva Green 80000 Marketing

cy 6
7
Frank
Black
Grace Hall
70000
55000
Engineering
Sales
Henry
8 90000 Engineering
King
9 Ivy Scott 48000 HR
Jack
10 68000 Marketing
Adams
11 Karen Lee 72000 Engineering
 • 2. Departments Table (Contains
department-specific information
Example directly dependent on dept_name)
of 3NF, dept_nam
e
budget building

eliminatin
Engineering 1000000 Main
Sales 500000 Annex
HR 200000 Admin

g
Marketing 300000 Annex

• Relationships: The Employees

transitive table now contains dept_name as a
foreign key, which references the
dependen dept_name (primary key) in the
Departments table. This link allows
cy you to retrieve all department details
for an employee by joining the two
tables.
 • A table is in Boyce-Codd Normal Form
(BCNF) if:

• It is already in 3NF.
(Boyce- • For every non-trivial functional dependency
(FD) X → Y, X must be a superkey.
Codd
Normal • Let's break down that second condition:
• Non-trivial FD: This means Y is not a subset
Form)BCN of X (i.e., the dependency tells you something
new).
F • Superkey: A superkey is any attribute or set
of attributes that uniquely identifies a row in a
table. This includes the primary key and any
other candidate keys, as well as any superset
of a candidate key.
 • Essentially, BCNF tightens the rule
from 3NF.
• In 3NF, a non-key attribute could be
(Boyce- dependent on a non-key attribute as
long as the determinant was part of
Codd a candidate key or the dependent
was a prime attribute.
Normal
• BCNF simplifies this by saying: if
Form)BCN any attribute (or set of attributes)
F determines another attribute, then
that determinant must be a
superkey.
• There are no exceptions for prime
attributes on the right-hand side.
 • Imagine a university database
where we want to keep track of
Example which students are enrolled in
which courses, and who their
of BCNF, advisors are, along with the
eliminatin specialty of each advisor.
• Initially, we might design a single
g non- table called EnrollmentAdvisor
trivial
StudentID CourseID AdvisorName AdvisorSpecialt
y
S101 CS101 Dr. Smith Databases

dependen
S101 CS201 Dr. Jones AI
S102 CS101 Dr. Smith Databases

cies
S103 CS201 Dr. Jones AI
S104 CS301 Dr. White Networking
S104 CS401 Dr. Smith Databases
 • Primary Key (Candidate Key):
{StudentID, CourseID}. This is
because a student can take multiple
courses, and a course can have
(Boyce- multiple students. To uniquely identify
a row (e.g., student S101 in course
Codd CS101), you need both StudentID and
Normal CourseID.
• Functional Dependencies (FDs):
Form)BCN • {StudentID, CourseID} → AdvisorName (A
F student taking a specific course is
assigned a particular advisor for that
course context).
• AdvisorName → AdvisorSpecialty (Each
advisor has one specific specialty, e.g.,
Dr. Smith is always "Databases").
 • Now, let's check for BCNF:
• Is it in 3NF? Yes. There are no partial dependencies (non-key
attributes depend on the full composite key). There are no
transitive dependencies where a non-key attribute depends on
another non-key attribute, and that intermediate non-key
attribute isn't part of a candidate key.
(Boyce- • AdvisorName (non-key) determines AdvisorSpecialty (non-key).
However, AdvisorName is not a candidate key.

Codd
• This specific scenario is allowed in 3NF because AdvisorSpecialty is
not transitively dependent on the primary key via another non-key
attribute that is not a determinant. (It gets tricky here, which is why
BCNF was introduced!)

Normal • Does it satisfy the BCNF rule? No. The BCNF rule states: For
every non-trivial functional dependency X → Y, X must be a

Form)BCN superkey.
• Consider the FD: AdvisorName → AdvisorSpecialty.
• Here, X is AdvisorName.

F • However, AdvisorName is NOT a superkey of the

Enrollment_Advisor table (e.g., "Dr. Smith" appears multiple times,
not uniquely identifying a row without StudentID and CourseID).
• Since AdvisorName is a determinant but not a superkey, the table
violates BCNF.
• The Anomaly: The specialty of an advisor is repeated for
every course they advise. If Dr. Smith's specialty changes, we'd
have to update multiple rows, leading to potential
inconsistencies.
 • To convert this table to BCNF, we need to
decompose it based on the violating
functional dependency (AdvisorName →
AdvisorSpecialty). We'll create two new tables:

(Boyce- • StudentCourseAdvisors Table (Contains

student-course enrolment and their assigned
Codd advisor)
StudentID CourseID AdvisorName

Normal
S101 CS101 Dr. Smith
S101 CS201 Dr. Jones
S102 CS101 Dr. Smith

Form)BCN S103
S104
CS201
CS301
Dr. Jones
Dr. White

F
S104 CS401 Dr. Smith

Primary Key: {StudentID, CourseID}

Foreign Key: AdvisorName references
AdvisorName in Advisors table
 • Advisors Table (Contains unique advisor details
and their specialties)
AdvisorName AdvisorSpecialty
Dr. Smith Databases

(Boyce- Dr. Jones

Dr. White
AI
Networking

Codd Primary Key: AdvisorName

Normal • Now, both StudentCourseAdvisors and Advisors

Form)BCN tables are in BCNF:

• In StudentCourseAdvisors, the only determinant is
F the primary key {StudentID, CourseID}.
• In Advisors, the only determinant is the primary
key AdvisorName.
• This decomposition eliminates the redundancy and
potential for update anomalies, making the
database design more robust