1

INSY 8222: Database Management System

Sep - Dec 2025

Week 5: Normalization and Relational Algebra

Temitope Oguntade
 Logistics

● Instructor: Temitope Oguntade

● Email: toguntad@[Link]
● TAs:
● Class Time: 11:30 - 14:20 Tue (G), Thur (F)
● Course Credit: 3
● Prerequisite: As may be determined
● Code Source:
 Agenda

● Fixing Bad Designs: Understanding Anomalies and Redundancy

● The Tool for the Job: Functional Dependencies
● The Cleanup Process: Step-by-step Normalization (1NF, 2NF, 3NF,
BCNF)
● The Language of Queries: Introduction to Relational Algebra
● Lab Session: Normalizing a broken table and querying it with
Relational Algebra
 Why Good Design Isn't Enough

● In Week 3 & 4, we went from an idea (ERD) to a set of tables. But

what if our initial design creates subtle problems?
● Problem: A poorly designed schema can lead to a database that is
difficult to use and maintain
● Solution: Normalization, a formal process for analyzing and
improving a relational schema to minimize data redundancy and
avoid update anomalies
 Question

For 15 points to each group member, two groups should select

two random questions from the last assignment and present to
the class
 The "Anomalies": Symptoms of a Bad Design

● Let's look at one "bad" table that stores everything about student
course enrollment:

● StudentProject(StudentID, StudentName, CourseID, CourseName,

Grade, ProfessorID, ProfessorName)

● Primary Key: To uniquely identify a row (specifically, a student's

grade in a course), the composite primary key must be (StudentID,
CourseID)
Bad Table Design
Poor Design - 1
Poor Design - 2

-1
Poor Design - 3
 The "Anomalies": Symptoms of a Bad Design

● The Problems (Anomalies):

1. Insertion Anomaly: We cannot add a new student to the database
who hasn't enrolled in any courses yet, because CourseID is part of the
primary key and cannot be NULL. Similarly, we can't add a new course
that has no students enrolled.
2. Deletion Anomaly: If student S101 is the only student in 'History
101', and we delete S101's record (e.g., they drop out), we lose all
information that the course 'History 101' ever existed.
3. Update Anomaly: If Professor P20 changes their name, we have to
find and update every single row for every student they teach. If we
miss one, the data becomes inconsistent.
 The Root Cause: Functional Dependencies
● The anomalies are caused by improper functional dependencies
(FDs)
● Definition: An FD, written A -> B, means that if you know the value
of attribute A, you uniquely know the value of attribute B. A
determines B.
● In our bad table:
○ StudentID -> StudentName (A Student ID determines their name)
○ CourseID -> CourseName (A Course ID determines the course name)
○ ProfessorID -> ProfessorName
○ (StudentID, CourseID) -> Grade (To know a grade, you need to know which
student and in which course)
● The problem is that we have non-key attributes determined by
other non-key attributes all mixed together in one table.
 Normal Forms: The Steps to a Good Design

● Normalization is a process of decomposing (breaking up) tables to

eliminate these problematic dependencies. We move through a
series of "Normal Forms"
 First Normal Form (1NF)

● Rule: All attribute values must be atomic. No repeating groups or

multivalued attributes
● Our StudentProject table is already in 1NF
● Non-1NF Example: A PhoneNumber column containing '555-1234,
555-5678'. To fix this, we'd create a separate Student_Phones table
(as we learned in ER-to-Relational mapping)
 Second Normal Form (2NF)
● Rule: Must be in 1NF, AND every non-key attribute must be fully
functionally dependent on the entire primary key
● This rule only applies to tables with composite primary keys.
● Our Problem Table: The primary key is (StudentID, CourseID)
○ StudentName depends only on StudentID, not the full key. This is a partial
dependency.
○ CourseName, ProfessorID, ProfessorName depend only on CourseID, not the
full key. Another partial dependency.
● Solution: We break the table up to remove these partial
dependencies
○ STUDENT (StudentID, StudentName)

○ COURSE (CourseID, CourseName, ProfessorID, ProfessorName)

○ ENROLLMENT (StudentID, CourseID, Grade)

 Third Normal Form (3NF) - 1
● Rule: Must be in 2NF, AND there must be no transitive
dependencies
● Transitive Dependency: When a non-key attribute determines
another non-key attribute (e.g., A -> B -> C where A is the PK).
● Our New COURSE table has a problem:
○ COURSE(CourseID, CourseName, ProfessorID, ProfessorName)
○ The PK is CourseID.
○ CourseID -> ProfessorID
○ ProfessorID -> ProfessorName
○ This is a transitive dependency! The professor's name doesn't
belong in the course table.
 Third Normal Form (3NF) - 2
● Solution: Break it up further
○ COURSE (CourseID, CourseName, ProfessorID)
○ PROFESSOR (ProfessorID, ProfessorName)
 The Final, Normalized Design (3NF)
● By following the process, we turned one bad table into four good
ones:
○ STUDENT (StudentID, StudentName)
○ PROFESSOR (ProfessorID, ProfessorName)
○ COURSE (CourseID, CourseName, ProfessorID) (ProfessorID -
Foreign Key to Professor)
○ ENROLLMENT (StudentID, CourseID, Grade) (StudentID, CourseID
- Foreign Keys to Student and Course)
● Result: No redundancy, no anomalies. Each table describes a single
entity
Shifting Gears: How Do We Query Our Clean Data?

● Now that we have beautifully normalized tables, how do we ask

questions that combine data from them?
● We use SQL, but SQL is based on a formal mathematical language
called Relational Algebra.
● Understanding Relational Algebra helps you understand how the
database thinks and lets you write more efficient queries.
 Core Idea: Operators on Tables

● Relational Algebra defines a set of operators that take one or more

relations (tables) as input and produce a new relation as output

● We will look at the most fundamental operators

 Selection (σ)

● Purpose: Filters rows based on a condition. The "WHERE" clause of

SQL.

● Notation: σ_condition(Relation)

● Example: Find all courses taught by Professor P20

○ σ_{ProfessorID='P20'}(COURSE)
 Projection (π)

● Purpose: Selects columns. The "SELECT" list of SQL

● Notation: π_{column1, column2}(Relation)

● Example: List the names and IDs of all students

○ π_{StudentID, StudentName}(STUDENT)
 Combining Selection and Projection

● We can chain operators together. The output of one becomes the

input for the next.

● Example: Find the names of all courses taught by Professor P20

○ π_CourseName(σ_{ProfessorID='P20'}(COURSE))

● Read from the inside out: First select the rows, then project the
columns
 Union (∪), Intersection (∩), Difference (-)

● Standard set operations, but they require the tables to be

union-compatible (same number of columns, and corresponding
columns have the same domain)
● Union: Combines all rows from two tables
● Intersection: Returns only rows that appear in both tables
● Difference: Returns rows that are in the first table but not the second
 Cartesian Product (×)

● Purpose: Combines every row from one table with every row from
another table
● Notation: Relation1 × Relation2
● Result: If Table A has 5 rows and Table B has 3 rows, A × B will have 15
rows
● Warning: On its own, this is rarely useful as it produces all possible
combinations, many of which are meaningless. It is the basis for the
JOIN operation
 The Most Important Operator: Natural Join (⋈)
● Purpose: The workhorse of relational queries. Combines related rows
from two tables into a single table
● How it works:
1. It computes the Cartesian Product
2. It performs a Selection to keep only the rows where the values in
the common columns (columns with the same name) are equal
3. It performs a Projection to remove the duplicate common columns
● Notation: Relation1 ⋈ Relation2
● Example: To get a list of all students and the grades for the courses
they are enrolled in:
a. STUDENT ⋈ ENROLLMENT
Example
Example
 Putting It All Together: A Complex Query
● Question: Find the names of students taking the 'Database Systems'
course
● Tables Needed: STUDENT, ENROLLMENT, COURSE
● Steps (in Relational Algebra):
1. Find the CourseID for 'Database Systems': σ_CourseName='Database Systems'
(COURSE)
2. Join this with the ENROLLMENT table to find the StudentIDs: (...) ⋈ ENROLLMENT
3. Join the result with the STUDENT table to find the names: (...) ⋈ STUDENT
4. Project just the student names: π_StudentName(...)
● Final Expression:
π_StudentName((σ_{CourseName='Database
Systems'}(COURSE)) ⋈ ENROLLMENT ⋈ STUDENT)
● This demonstrates how we build complex queries from simple,
powerful operators
Assignment

Download here
 Boyce-Codd Normal Form (BCNF) - 1
● A slightly stricter version of 3NF
● Rule: For every non-trivial functional dependency A -> B, the
determinant A must be a superkey
● Key terminology Recap:
○ Superkey: A set of one or more attributes that can uniquely
identify a row in a table. (StudentID, StudentName) is a
superkey. (StudentID) is also a superkey.
○ Candidate Key: A minimal superkey. No attribute can be
removed from it without losing the unique identification
property. (StudentID) is a candidate key.
○ Determinant: The attribute or set of attributes on the left side
of a functional dependency. The 'A' in A -> B.
 Boyce-Codd Normal Form (BCNF) - 2
● A Classic BCNF Example:
● Scenario & Rules: A student can take multiple subjects. For any
subject, a student is taught by only one professor. A professor
teaches only one subject
● Table: ENROLLMENT (StudentID, Subject, ProfessorID)
● Functional Dependencies:
○ (StudentID, Subject) -> ProfessorID
○ ProfessorID -> Subject (This is the key one!)
● Analysis:
○ Candidate Keys are (StudentID, Subject) and (StudentID,
ProfessorID).
○ The table is in 3NF (no transitive dependencies because
Subject is part of a candidate key).
 Boyce-Codd Normal Form (BCNF) - 3
● Analysis:
○ But it violates BCNF! The dependency ProfessorID -> Subject
exists, and its determinant (ProfessorID) is not a superkey.
● Anomaly: If we delete the last student taught by a professor,
we lose the fact that the professor teaches a specific subject.
● BCNF Solution: Decompose the table
○ Student_Professor (StudentID, ProfessorID)
○ Professor_Subject (ProfessorID, Subject)
● Takeaway: You achieve BCNF by ensuring that the only
determinants in your table are candidate keys