Third Normal Form (3NF) in SQL - Time & Space Complexity

Time Complexity: Third Normal Form (3NF)

O(n)

Understanding Time Complexity

When we organize data using Third Normal Form, we split tables to reduce repeated information.

We want to know how this splitting affects the time it takes to get data back.

Scenario Under Consideration

Analyze the time complexity of this SQL query joining normalized tables.

SELECT Orders.OrderID, Customers.CustomerName, Orders.OrderDate
FROM Orders
JOIN Customers ON Orders.CustomerID = Customers.CustomerID
WHERE Orders.OrderDate > '2023-01-01';
    

This query fetches orders with customer names after a certain date, joining two tables split by 3NF.

Identify Repeating Operations

Look at what repeats when the query runs:

• Primary operation: Scanning Orders and matching Customers by CustomerID.
• How many times: Once for each order after the date filter.

How Execution Grows With Input

As the number of orders grows, the query checks more rows and matches customers.

Input Size (n)	Approx. Operations
10	About 10 order checks and 10 customer lookups
100	About 100 order checks and 100 customer lookups
1000	About 1000 order checks and 1000 customer lookups

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line with the number of orders.

Common Mistake

[X] Wrong: "Splitting tables into 3NF always makes queries slower because of joins."

[OK] Correct: While joins add steps, they avoid repeated data and can keep queries efficient, especially with indexes.

Interview Connect

Understanding how normalization affects query time helps you design databases that balance speed and data quality.

Self-Check

"What if we added an index on CustomerID in both tables? How would the time complexity change?"

Practice

1. Which of the following best describes Third Normal Form (3NF) in database design?

easy

A. Every non-key column depends only on the primary key.

B. Tables must have no more than three columns.

C. All columns must be unique across the table.

D. Data must be stored in a single table without duplicates.

Solution

1. Step 1: Understand 3NF definition

   3NF requires that non-key columns depend only on the primary key, not on other non-key columns.

2. Step 2: Evaluate options

   Every non-key column depends only on the primary key. correctly states this. The other options are incorrect descriptions of 3NF.

3. Final Answer:

   Every non-key column depends only on the primary key. -> Option A

4. Quick Check:

   3NF = Non-key columns depend only on primary key [OK]

Hint: 3NF means no column depends on non-key columns [OK]

Common Mistakes:

• Confusing 3NF with limiting number of columns
• Thinking all columns must be unique
• Believing 3NF means one big table

2. Which SQL statement correctly creates a table that follows Third Normal Form (3NF)?

easy

A. CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT, CustomerName VARCHAR(50));

B. CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerName VARCHAR(50), CustomerAddress VARCHAR(100));

C. CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT); CREATE TABLE Customers (CustomerID INT PRIMARY KEY, CustomerName VARCHAR(50));

D. CREATE TABLE Orders (OrderID INT, CustomerName VARCHAR(50));

Solution

1. Step 1: Identify 3NF compliance in table design

   3NF requires separating data so non-key columns do not depend on other non-key columns. CustomerName depends on CustomerID, so it should be in a separate table.

2. Step 2: Analyze options

   CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT); CREATE TABLE Customers (CustomerID INT PRIMARY KEY, CustomerName VARCHAR(50)); splits Orders and Customers, following 3NF. CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT, CustomerName VARCHAR(50)); stores CustomerName in Orders, violating 3NF. The other options miss primary keys or mix data improperly.

3. Final Answer:

   CREATE TABLE Orders (OrderID INT PRIMARY KEY, CustomerID INT); CREATE TABLE Customers (CustomerID INT PRIMARY KEY, CustomerName VARCHAR(50)); -> Option C

4. Quick Check:

   Separate related data into tables = 3NF [OK]

Hint: Split tables to avoid non-key dependencies [OK]

Common Mistakes:

• Putting dependent data in the same table
• Missing primary keys
• Ignoring data duplication issues

3. Given the table below, which is NOT in Third Normal Form (3NF)?

EmployeeID | EmployeeName | Department | DepartmentHead

What is the main reason this table violates 3NF?

medium

A. DepartmentHead depends on Department, not EmployeeID.

B. EmployeeName depends on EmployeeID.

C. EmployeeID is not unique.

D. Department is a primary key.

Solution

1. Step 1: Identify dependencies in the table

   DepartmentHead depends on Department, which is a non-key column, not on the primary key EmployeeID.

2. Step 2: Check 3NF rules

   3NF requires no non-key column depends on another non-key column. Here, DepartmentHead depends on Department, violating 3NF.

3. Final Answer:

   DepartmentHead depends on Department, not EmployeeID. -> Option A

4. Quick Check:

   Non-key depends on non-key = violates 3NF [OK]

Hint: Check if non-key columns depend on other non-key columns [OK]

Common Mistakes:

• Thinking EmployeeName dependency breaks 3NF
• Assuming EmployeeID is not unique
• Confusing primary key with foreign key

4. You have a table:

StudentID | StudentName | Advisor | AdvisorOffice

This table violates 3NF. What is the best way to fix it?

medium

A. Remove AdvisorOffice column.

B. Create a separate Advisor table with Advisor and AdvisorOffice.

C. Make StudentName the primary key.

D. Add AdvisorOffice to StudentID as a foreign key.

Solution

1. Step 1: Identify the 3NF violation

   AdvisorOffice depends on Advisor, a non-key column, causing a transitive dependency violating 3NF.

2. Step 2: Fix by separating dependent data

   Creating a separate Advisor table with Advisor and AdvisorOffice removes the transitive dependency.

3. Final Answer:

   Create a separate Advisor table with Advisor and AdvisorOffice. -> Option B

4. Quick Check:

   Separate dependent data into own table to fix 3NF [OK]

Hint: Fix 3NF by splitting tables for transitive dependencies [OK]

Common Mistakes:

• Just removing columns without restructuring
• Changing primary keys incorrectly
• Adding foreign keys without normalization

5. A company has a table:

InvoiceID | ProductID | ProductName | SupplierID | SupplierName

To convert this table into Third Normal Form (3NF), which of the following is the best approach?

hard

A. Remove SupplierName column from the table.

B. Add ProductName and SupplierName as primary keys.

C. Keep all columns in one table but add unique constraints.

D. Create separate tables for Products and Suppliers, linking them by IDs.

Solution

1. Step 1: Identify transitive dependencies

   ProductName depends on ProductID, and SupplierName depends on SupplierID, both non-key columns, causing 3NF violation.

2. Step 2: Normalize by splitting tables

   Creating separate Product and Supplier tables linked by IDs removes these dependencies and achieves 3NF.

3. Final Answer:

   Create separate tables for Products and Suppliers, linking them by IDs. -> Option D

4. Quick Check:

   Split related entities into tables to achieve 3NF [OK]

Hint: Split entities into tables linked by keys for 3NF [OK]

Common Mistakes:

• Trying to keep all data in one table
• Using names as primary keys
• Removing columns without restructuring