Database Normalization

Contents
1. Introduction to Normalization
2. Anomalies of Un-Normalized Relations
3. Need for Normalization
4. Pros and Cons of Normalization
5. Functional Dependencies
6. Dependency Diagrams
7. Inference Rules (Armstrong's Axioms)
8. Closure of Functional Dependencies
9. Algorithms
10. Normal Forms
11. Lossless Join Decomposition and Dependency Preservation

Introduction to Normalization
➢ Normalization is a systematic approach of decomposing tables to eliminate data
redundancy and undesirable characteristics like insertion, update, and deletion anomalies.
➢ It is a multi-step process that organizes data in a database to reduce redundancy and
improve data integrity.

Key Objectives:
• Eliminate redundant data
• Ensure data dependencies make sense
• Reduce anomalies during data operations
• Optimize database structure

Anomalies of Un-Normalized Relations

Un-normalized relations suffer from three major types of anomalies:

[Link] Anomaly
Definition: Inability to insert data into the database without the presence of other data.

Example:

Consider an un-normalized Student_Course table:

Student_ID Student_Name Course_ID Course_Name

S001 John C101 DBMS
S001 John C102 OS
S002 Mary C101 DBMS
Problem: If a new student enrolls but hasn't registered for any course yet, we cannot insert their
record without leaving course fields NULL or empty.

[Link] Anomaly
Definition: Inconsistency in data when updates are not applied uniformly across all instances.

Example:

Emp_ID Emp_Name Dept_ID Dept_Location

E001 Alice D10 Building A
E002 Bob D10 Building A
E003 Carol D20 Building B

Problem: If Department D10 moves to Building C, we must update multiple rows. If we miss
updating one row, data becomes inconsistent.

[Link] Anomaly
Definition: Loss of useful data when other data is deleted.

Example:

Using the same Employee_Department table above:

Problem: If employee Carol (E003) leaves the company and we delete her record, we also lose the
information that Department D20 is located in Building B.

Need for Normalization

Normalization is essential for:

• Data Integrity: Ensures accuracy and consistency of data

• Eliminating Redundancy: Reduces duplicate data storage
• Preventing Anomalies: Avoids insertion, update, and deletion anomalies
• Efficient Storage: Optimizes disk space usage
• Easier Maintenance: Simplifies database updates and modifications
• Query Optimization: Improves query performance in many cases
• Data Consistency: Maintains uniform data across the database
Pros and Cons of Normalization

Advantages (Pros)
1. Reduced Data Redundancy: Minimizes duplicate data storage
2. Improved Data Integrity: Ensures data accuracy and consistency
3. Elimination of Anomalies: Prevents insertion, update, and deletion problems
4. Flexible Database Structure: Easier to extend and modify
5. Better Security: Sensitive data can be isolated in separate tables
6. Easier Maintenance: Changes need to be made in fewer places
7. Standardized Design: Follows established database design principles

Disadvantages (Cons)
1. Increased Complexity: More tables and relationships to manage
2. Slower Query Performance: May require multiple JOINs for data retrieval
3. More Storage for Keys: Additional foreign keys consume space
4. Complex Queries: More complex SQL statements required
5. Over-normalization Risk: Can lead to excessive fragmentation
6. Development Time: Takes longer to design and implement

Functional Dependencies:
➢ Functional Dependency (FD) is a constraint between two sets of attributes in a relation. If
attribute A functionally determines attribute B, we write: A → B. This means: For each
value of A, there is exactly one corresponding value of B.

Types of Functional Dependencies in DBMS

There are four main types of functional dependencies in a DBMS. Following are the types
of functional dependencies in DBMS:

• Multivalued dependency
• Trivial functional dependency
• Non-trivial functional dependency
• Transitive dependency
Trivial Functional Dependency
Definition: Trivial dependency refers to a set of attributes that are considered trivial if the attributes
within that set encompass the entirety of another attribute.

A functional dependency A → B is trivial if B is a subset of A.

Examples:

• {𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝑁𝑎𝑚𝑒} → 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷 (trivial)

• {𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝑁𝑎𝑚𝑒} → 𝑁𝑎𝑚𝑒 (trivial)
• 𝐴 → 𝐴 (always trivial)
Simple Example:
{ID,Name,Age}→{ID, Name} (Trivial)
{ID, Name, Age} → Age (Non-trivial)
Example-2:

Emp_id Emp_name

AS555 Divyansh

AS811 Krish

AS999 Aakash

Consider this table with two columns Emp_id and Emp_name.

{Emp_id, Emp_name} -> Emp_id is a trivial functional dependency as Emp_id is a subset of
{Emp_id,Emp_name}.

Non-Trivial Functional Dependency

Definition: A non-trivial dependency arises when A->B is valid and B is not a subset of A. In a
relational context, if attribute B does not constitute a subset of attribute A, it signifies a non-trivial
dependency.

A functional dependency A → B is non-trivial if B is not a subset of A.

Example:
Student_ID → Student_Name (Non-trivial)
Employee_ID → Salary (Non-trivial)
Example:

Company CEO Age

Microsoft Satya Nadella 51

Google Sundar Pichai 46

Apple Tim Cook 57

(Company} -> {CEO} (if we know the Company, we know the CEO name)

However, the CEO is not a subset of the Company, and hence it’s a non-trivial functional dependency.
Full Functional Dependency
Definition: An attribute B is fully functionally dependent on attribute set A if B is functionally
dependent on A, but not on any proper subset of A.

Example:

Consider relation: Student_Course(Student_ID, Course_ID, Grade, Student_Name)

• {𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝐶𝑜𝑢𝑟𝑠𝑒_𝐼𝐷} → 𝐺𝑟𝑎𝑑𝑒 (Full Dependency)

• Grade depends on both Student_ID and Course_ID together
• Grade does NOT depend on Student_ID alone or Course_ID alone

Partial Functional Dependency

Definition: An attribute is partially dependent on a composite key if it depends on only part of the
key.

Example:

In the same relation: Student_Course(Student_ID, Course_ID, Grade, Student_Name)

• Primary Key: {𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝐶𝑜𝑢𝑟𝑠𝑒_𝐼𝐷}

• 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷 → 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝑁𝑎𝑚𝑒 (Partial Dependency)
• Student_Name depends only on Student_ID, not the full key

Transitive Functional Dependency

Definition: If A → B and B → C, then A → C is a transitive dependency (where B is not a
candidate key).

Example:

Consider: Employee(Emp_ID, Emp_Name, Dept_ID, Dept_Location)

• 𝐸𝑚𝑝_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐼𝐷
• 𝐷𝑒𝑝𝑡_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐿𝑜𝑐𝑎𝑡𝑖𝑜𝑛
• Therefore: 𝐸𝑚𝑝_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐿𝑜𝑐𝑎𝑡𝑖𝑜𝑛 (Transitive)
Problem: Dept_Location depends on Emp_ID indirectly through Dept_ID. This violates 3NF.

Multivalued Dependency (MVD)

Definition: A multivalued dependency A →B exists if for a single value of A, there can be
multiple independent values of B.

Notation: A → B (read as "A multi-determines B")

Example:

Consider: Faculty_Course_Textbook(Faculty_ID, Course, Textbook)

 Faculty_ID Course Textbook
F001 DBMS Database Systems
F001 DBMS Introduction to Databases
F001 OS Operating Systems
F001 OS Database Systems
F001 OS Introduction to Databases

• 𝐹𝑎𝑐𝑢𝑙𝑡𝑦_𝐼𝐷 ↠ 𝐶𝑜𝑢𝑟𝑠𝑒 (F001 teaches DBMS and OS)

• 𝐹𝑎𝑐𝑢𝑙𝑡𝑦_𝐼𝐷 ↠ 𝑇𝑒𝑥𝑡𝑏𝑜𝑜𝑘 (F001 uses two textbooks)
• Courses and Textbooks are independent of each other

Join Dependency
Definition: A relation R has a join dependency if R can be decomposed into smaller relations that
can be joined back to produce the original relation without loss of information.

Example:

Relation R(A, B, C, D) has a join dependency if:

• R can be decomposed into R1(A, B), R2(B, C), R3(C, D)

• Natural join of R1, R2, and R3 produces R exactly
Example:
Consider Employee_Assignments with attributes (EmpID, Project, Skill):

EmpID Project Skill

E1 P1 Java

E1 P2 Python

E2 P1 Java

E2 P3 SQL

This holds a join dependency (EmpID-Project, Project-Skill, EmpID-Skill).

Decomposed Relations
• R1(EmpID, Project): E1-P1, E1-P2, E2-P1, E2-P3
• R2(Project, Skill): P1-Java, P2-Python,P3-SQL
• R3(EmpID, Skill): E1-Java, E1-Python, E2-Java, E2-SQL
Natural join R1 ⋈ R2 ⋈ R3 yields the original table without spurious tuples, confirming the
dependency.
Inclusion Dependency
Definition: An inclusion dependency exists when values in one relation must be present in another
relation (referential integrity).

Example:

• Relation: Student(Student_ID, Name, Dept_ID)

• Relation: Department(Dept_ID, Dept_Name)
• Inclusion Dependency: Student[Dept_ID] ⊆ Department[Dept_ID]
• Every Dept_ID in Student must exist in Department table
This is enforced through Foreign Key constraints.

Dependency Diagram
A dependency diagram visually represents functional dependencies among attributes in a relation, helping
identify normalization issues like partial or transitive dependencies.

Example:
For relation: Employee(Emp_ID, Emp_Name, Dept_ID, Dept_Name, Dept_Location)

Functional Dependencies:

• 𝐸𝑚𝑝_𝐼𝐷 → 𝐸𝑚𝑝_𝑁𝑎𝑚𝑒
• 𝐸𝑚𝑝_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐼𝐷
• 𝐷𝑒𝑝𝑡_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝑁𝑎𝑚𝑒
• 𝐷𝑒𝑝𝑡_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐿𝑜𝑐𝑎𝑡𝑖𝑜𝑛

Inference Rules for Functional Dependencies (Armstrong's Axioms)

Armstrong's Axioms are a set of inference rules used to derive all functional dependencies in a
relation.

1. Basic Rules (Sound and Complete)

1. Reflexivity: If 𝑌 ⊆ 𝑋, then 𝑋 → 𝑌
• Example: {𝐴, 𝐵} → 𝐴
2. Augmentation: If 𝑋 → 𝑌, then 𝑋𝑍 → 𝑌𝑍
• Example: If 𝐴 → 𝐵, then 𝐴𝐶 → 𝐵𝐶
3. Transitivity: If 𝑋 → 𝑌 and 𝑌 → 𝑍, then 𝑋 → 𝑍
• Example: If 𝐴 → 𝐵 and 𝐵 → 𝐶, then 𝐴 → 𝐶

2. Derived Rules
1. Union: If 𝑋 → 𝑌 and 𝑋 → 𝑍, then 𝑋 → 𝑌𝑍
• Example: If 𝐴 → 𝐵 and 𝐴 → 𝐶, then 𝐴 → 𝐵𝐶
 2. Decomposition: If 𝑋 → 𝑌𝑍, then 𝑋 → 𝑌 and 𝑋 → 𝑍
• Example: If 𝐴 → 𝐵𝐶, then 𝐴 → 𝐵 and 𝐴 → 𝐶
3. Pseudotransitivity: If 𝑋 → 𝑌 and 𝑊𝑌 → 𝑍, then 𝑊𝑋 → 𝑍

Closure of Functional Dependencies

1. Closure of a Set of FDs (F+)

Definition: The closure of a set of functional dependencies F, denoted as F+, is the complete set of
all functional dependencies that can be derived from F using Armstrong's Axioms.

Example:

Given: F = {A → B, B → C}

Find F+:

Using inference rules:

• 𝐴 → 𝐵 (given)
• 𝐵 → 𝐶 (given)
• 𝐴 → 𝐶 (by transitivity)
• 𝐴 → 𝐴 (by reflexivity)
• 𝐵 → 𝐵 (by reflexivity)
• 𝐶 → 𝐶 (by reflexivity)
• 𝐴 → 𝐴𝐵 (by augmentation)
• 𝐴 → 𝐴𝐶 (by union)
• 𝐴 → 𝐵𝐶 (by combining)
• 𝐴 → 𝐴𝐵𝐶 (by union)
F+ = {A → B, B → C, A → C, A → A, B → B, C → C, A → AB, A → AC, A → BC, A → ABC,
...}
2. Closure of an Attribute Set (X+)
Definition: The closure of an attribute set X, denoted as X+, is the set of all attributes that can be
functionally determined by X.

Example:

Given: R(A, B, C, D, E) and F = {A → BC, CD → E, B → D, E → A}

Find A+:

Step Result Set FD Applied Explanation

1 {A} - Initial set

2 {A, B, C} A → BC A determines B, C

3 {A, B, C, D} B→D B (now in set) determines D

4 {A, B, C, D, E} CD → E C, D determine E

5 No change E→A A already present; complete

Therefore, A+ = {A, B, C, D, E}

Since A+ contains all attributes, A is a candidate key.

Algorithms

1 .Algorithm to Find Candidate Key

Candidate Key: A minimal set of attributes that uniquely identifies a tuple and from which no
attribute can be removed without losing the uniqueness property.

Algorithm Steps:

1. Identify attributes that appear only on the left side of FDs (must be in candidate key)
2. Identify attributes that appear only on the right side (cannot be in candidate key)
3. Identify attributes that appear on both sides (may or may not be in candidate key)
4. Compute the closure of attributes from step 1
5. If closure contains all attributes, those attributes form a candidate key
6. If not, add one attribute at a time from step 3 and check closure
7. Find all minimal combinations
Example:

Given: R(A, B, C, D) and F = {A → B, B → C, C → D}

Step 1: Attributes only on left: {A}

Step 2: Attributes only on right: {D}
Step 3: Attributes on both: {B, C}

Step 4: Compute A+:

• Start: {A}
• A → B: {A, B}
• B → C: {A, B, C}
• C → D: {A, B, C, D}
A+ = {A, B, C, D} (all attributes)

Therefore, Candidate Key = {A}

9.2 Algorithm to Find Closure of Attribute Set

Algorithm:

Input: Set of attributes X, Set of FDs F

Output: X+ (closure of X)

Algorithm:

1. Initialize: result = X
2. Repeat until no change in result:
For each FD (A → B) in F:
If A ⊆ result:
result = result ∪ B
3. Return result as X+
Example:

Given: R(A, B, C, D, E) and F = {AB → C, C → D, D → E, E → A}

Find {A, B}+:

1. Initialize: result = {𝐴, 𝐵}

2. Check 𝐴𝐵 → 𝐶: A, B ⊆ result, so add C: result = {𝐴, 𝐵, 𝐶}
3. Check 𝐶 → 𝐷: C ⊆ result, so add D: result = {𝐴, 𝐵, 𝐶, 𝐷}
4. Check 𝐷 → 𝐸: D ⊆ result, so add E: result = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}
5. Check 𝐸 → 𝐴: E ⊆ result, A already in result
6. No more changes possible
{A, B}+ = {A, B, C, D, E}
9.3 Algorithm to Find Minimal Cover (Canonical Cover)
Minimal Cover: A simplified set of FDs equivalent to the original set, with:

• No extraneous attributes in FDs

• No redundant FDs
• All FDs in standard form (single attribute on right side)
Algorithm Steps:

1. Convert to Standard Form: Decompose FDs so each has a single attribute on the right
• 𝐴 → 𝐵𝐶 becomes 𝐴 → 𝐵 and 𝐴 → 𝐶
2. Remove Extraneous Attributes:
• For each FD 𝑋 → 𝑌:
• For each attribute A in X:
• If $(X - {A})^+ $ contains Y, remove A from X
3. Remove Redundant FDs:
• For each FD 𝑋 → 𝑌 in F:
• If Y is in 𝑋 + computed using 𝐹 − {𝑋 → 𝑌}, remove the FD
Example:

Given: F = {A → BC, B → C, A → B, AB → C}

Step 1: Standard Form

• F = {A → B, A → C, B → C, AB → C}
Step 2: Remove Extraneous Attributes

• For AB → C: Check if A+ or B+ contains C using F - {AB → C}

• A+ = {A, B, C} (using A → B, A → C, B → C)
• A alone can determine C, so AB → C is redundant
Step 3: Remove Redundant FDs

• F = {A → B, A → C, B → C}
• Check A → C: Using {A → B, B → C}, find A+
• A+ = {A, B, C}, so A → C is redundant
Minimal Cover: Fc = {A → B, B → C}
10. Normal Forms
Normal forms are standards for database design that progressively reduce redundancy and
anomalies[4].

10.1 First Normal Form (1NF)

Definition: A relation is in 1NF if:

• All attributes contain only atomic (indivisible) values

• Each attribute contains values of a single type
• Each column has a unique name
• The order of rows/columns doesn't matter
Example: NOT in 1NF

Student_ID Name Courses

S001 John DBMS, OS, Networks
S002 Mary DBMS, Python

Table 4: Violation of 1NF - Multi-valued attribute

Problem: Courses column contains multiple values (not atomic).

Conversion to 1NF:

Student_ID Name Course

S001 John DBMS
S001 John OS
S001 John Networks
S002 Mary DBMS
S002 Mary Python

Table 5: Table in 1NF

10.2 Second Normal Form (2NF)

Definition: A relation is in 2NF if[4]:

• It is in 1NF
• No partial dependency exists (all non-prime attributes are fully functionally dependent on
the primary key)
Applies to: Relations with composite primary keys.

Example: NOT in 2NF

Student_ID Course_ID Student_Name Grade

 S001 C101 John A
S001 C102 John B
S002 C101 Mary A

Table 6: Violation of 2NF

Primary Key: {Student_ID, Course_ID}

Functional Dependencies:

• {𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝐶𝑜𝑢𝑟𝑠𝑒_𝐼𝐷} → 𝐺𝑟𝑎𝑑𝑒 (Full dependency - OK)

• 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷 → 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝑁𝑎𝑚𝑒 (Partial dependency - Violation!)
Conversion to 2NF:

Decompose into two relations:

Relation 1: Student

Student_ID Student_Name
S001 John
S002 Mary

Table 7: Student Table (2NF)

Relation 2: Enrollment

Student_ID Course_ID Grade

S001 C101 A
S001 C102 B
S002 C101 A

Table 8: Enrollment Table (2NF)

10.3 Third Normal Form (3NF)

Definition: A relation is in 3NF if[4]:

• It is in 2NF
• No transitive dependency exists (no non-prime attribute depends on another non-prime
attribute)
Example: NOT in 3NF

Emp_ID Emp_Name Dept_ID Dept_Location

E001 Alice D10 Building A
 E002 Bob D10 Building A
E003 Carol D20 Building B

Table 9: Violation of 3NF

Primary Key: Emp_ID

Functional Dependencies:

• 𝐸𝑚𝑝_𝐼𝐷 → 𝐸𝑚𝑝_𝑁𝑎𝑚𝑒 (OK)

• 𝐸𝑚𝑝_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐼𝐷 (OK)
• 𝐷𝑒𝑝𝑡_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐿𝑜𝑐𝑎𝑡𝑖𝑜𝑛 (OK)
• 𝐸𝑚𝑝_𝐼𝐷 → 𝐷𝑒𝑝𝑡_𝐿𝑜𝑐𝑎𝑡𝑖𝑜𝑛 (Transitive - Violation!)
Conversion to 3NF:

Relation 1: Employee

Emp_ID Emp_Name Dept_ID

E001 Alice D10
E002 Bob D10
E003 Carol D20

Table 10: Employee Table (3NF)

Relation 2: Department

Dept_ID Dept_Location
D10 Building A
D20 Building B

Table 11: Department Table (3NF)

10.4 Boyce-Codd Normal Form (BCNF)

Definition: A relation is in BCNF if[4]:

• It is in 3NF
• For every non-trivial functional dependency 𝑋 → 𝑌, X must be a superkey
BCNF is stricter than 3NF.

Example: NOT in BCNF

Student_ID Subject Professor

S001 DBMS Prof. Smith
 S001 OS Prof. Jones
S002 DBMS Prof. Smith
S003 Networks Prof. Brown
S003 DBMS Prof. Smith

Table 12: Violation of BCNF

Functional Dependencies:

• {𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝑆𝑢𝑏𝑗𝑒𝑐𝑡} → 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟

• 𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑜𝑟 → 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 (Each professor teaches only one subject)
Primary Key: {Student_ID, Subject}

Problem: Professor → Subject violates BCNF because Professor is not a superkey.

Conversion to BCNF:

Relation 1: Student_Subject

Student_ID Professor
S001 Prof. Smith
S001 Prof. Jones
S002 Prof. Smith
S003 Prof. Brown
S003 Prof. Smith

Table 13: Student_Subject Table (BCNF)

Relation 2: Professor_Subject

Professor Subject
Prof. Smith DBMS
Prof. Jones OS
Prof. Brown Networks

Table 14: Professor_Subject Table (BCNF)

10.5 Fourth Normal Form (4NF)

Definition: A relation is in 4NF if:

• It is in BCNF
• It has no multivalued dependencies (MVD)
Example: NOT in 4NF

Faculty_ID Course Hobby

F001 DBMS Cricket
F001 DBMS Reading
F001 OS Cricket
F001 OS Reading
F002 Networks Football

Table 15: Violation of 4NF

Multivalued Dependencies:

• 𝐹𝑎𝑐𝑢𝑙𝑡𝑦_𝐼𝐷 ↠ 𝐶𝑜𝑢𝑟𝑠𝑒
• 𝐹𝑎𝑐𝑢𝑙𝑡𝑦_𝐼𝐷 ↠ 𝐻𝑜𝑏𝑏𝑦
• Courses and Hobbies are independent of each other
Problem: For each combination of Course and Hobby for a faculty, we need a separate row,
causing redundancy.

Conversion to 4NF:

Relation 1: Faculty_Course

Faculty_ID Course
F001 DBMS
F001 OS
F002 Networks

Table 16: Faculty_Course Table (4NF)

Relation 2: Faculty_Hobby

Faculty_ID Hobby
F001 Cricket
F001 Reading
F002 Football

Table 17: Faculty_Hobby Table (4NF)

11. Lossless Join Decomposition and Dependency Preservation

11.1 Lossless Join Decomposition

Definition: A decomposition of relation R into R1 and R2 is lossless if the natural join of R1 and
R2 produces exactly the original relation R (no spurious tuples).

Condition for Lossless Join:

A decomposition of R into R1 and R2 is lossless if and only if:

• 𝑅1 ∩ 𝑅2 → 𝑅1, OR
• 𝑅1 ∩ 𝑅2 → 𝑅2
(The common attributes must be a key for at least one of the relations)

Example:

Original Relation: R(A, B, C, D)

FDs: {A → B, C → D}

Decomposition: R1(A, B), R2(A, C, D)

Check:

• 𝑅1 ∩ 𝑅2 = {𝐴}
• Does 𝐴 → 𝑅1? Yes, 𝐴 → 𝐴𝐵 (A is key of R1)
Result: Lossless join decomposition ✓

11.2 Dependency Preservation

Definition: A decomposition preserves dependencies if all functional dependencies in the original
relation can be checked by examining only the individual decomposed relations.

Condition:

Let F be the set of FDs on R, and F1, F2, ..., Fn be the projections of F onto R1, R2, ..., Rn.

The decomposition preserves dependencies if:

(𝐹1 ∪ 𝐹2 ∪. . .∪ 𝐹𝑛)+ = 𝐹 +

Example:

Original Relation: R(A, B, C)

FDs: F = {A → B, B → C, C → A}

Decomposition 1: R1(A, B), R2(B, C)

Check:

• F1 (on R1): {𝐴 → 𝐵}
• F2 (on R2): {𝐵 → 𝐶}
• Can we check 𝐶 → 𝐴? NO (C and A are not together in any relation)
Result: Does NOT preserve dependencies ✗

Decomposition 2: R1(A, B), R2(A, C)

Check:

• F1 (on R1): {𝐴 → 𝐵}
• F2 (on R2): {𝐶 → 𝐴, 𝐴 → 𝐶}
• Can we check 𝐵 → 𝐶? Requires joining R1 and R2
Result: Does NOT preserve all dependencies ✗

Note: Sometimes we must choose between lossless join and dependency preservation. BCNF
guarantees lossless join but may not preserve all dependencies. 3NF can preserve dependencies but
may have some redundancy.

11.3 Testing Lossless Join (Chase Algorithm)

Algorithm Steps:

1. Create a table with rows for each decomposed relation

2. Columns represent all attributes of original relation
3. Fill with:
• Subscripted symbols (𝑎𝑖 , 𝑏𝑖 , 𝑐𝑖 ) for non-common attributes
• Unsubscripted symbols (a, b, c) for common attributes
4. Apply FDs to make rows equal
5. If any row becomes all unsubscripted, decomposition is lossless
Example:

Relation: R(A, B, C, D)
FDs: {A → B, C → D}
Decomposition: R1(A, B), R2(A, C, D)

Chase Table:

A B C D
R1 a b 𝑐1 𝑑1
R2 a 𝑏2 c d

Table 18: Initial Chase Table

Apply A → B: Since both rows have A = a, and A → B, make B equal:

A B C D
R1 a b 𝑐1 𝑑1
R2 a b c d

Table 19: After applying A → B

Apply C → D: No change (C values are different)
Result: No row with all unsubscripted symbols... Wait, R2 already was (a, b, c, d).

Actually, R1 should be checked: After FD application, does any row have all original
unsubscripted? The method needs refinement, but the concept is: if we can derive a row identical to
the original through FD applications, it's lossless.

Summary Table: Normal Forms

Normal Form Condition Eliminates

1NF Atomic values only Multi-valued attributes
2NF 1NF + No partial dependency Partial dependencies
3NF 2NF + No transitive dependency Transitive dependencies
BCNF 3NF + Every determinant is a key All FD anomalies
4NF BCNF + No MVD Multivalued dependencies

Table 20: Normal Forms Summary

Practice Problems

Problem 1: Identify Anomalies

Given the following un-normalized relation, identify insertion, update, and deletion anomalies:

Order_Details(Order_ID, Product_ID, Product_Name, Quantity, Customer_ID,

Customer_Name)

Problem 2: Find Candidate Keys

Given R(A, B, C, D, E) and F = {A → B, BC → D, D → E}

Find all candidate keys.

Problem 3: Normalize to 3NF

Normalize the following relation to 3NF:

Student(Student_ID, Student_Name, Course_ID, Course_Name, Instructor_ID,

Instructor_Name)

Given FDs:

• 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝐼𝐷, 𝐶𝑜𝑢𝑟𝑠𝑒_𝐼𝐷 → 𝑆𝑡𝑢𝑑𝑒𝑛𝑡_𝑁𝑎𝑚𝑒, 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑜𝑟_𝐼𝐷

• 𝐶𝑜𝑢𝑟𝑠𝑒_𝐼𝐷 → 𝐶𝑜𝑢𝑟𝑠𝑒_𝑁𝑎𝑚𝑒, 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑜𝑟_𝐼𝐷
• 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑜𝑟_𝐼𝐷 → 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑜𝑟_𝑁𝑎𝑚𝑒