Why normalization matters in SQL - Performance Analysis

Time Complexity: Why normalization matters

O(n)

Understanding Time Complexity

When we organize data in a database, the way we arrange it affects how fast queries run.

We want to see how the structure of data impacts the work needed to get answers.

Scenario Under Consideration

Analyze the time complexity of the following SQL query on a normalized vs denormalized table.

-- Denormalized table example
SELECT customer_name, order_id, product_name
FROM orders
WHERE customer_id = 123;

-- Normalized tables example
SELECT c.customer_name, o.order_id, p.product_name
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN products p ON o.product_id = p.product_id
WHERE c.customer_id = 123;
    

This code fetches customer orders and product details either from one big table or by joining smaller tables.

Identify Repeating Operations

Look at what repeats as data grows.

• Primary operation: Scanning rows and joining tables.
• How many times: Once per matching row in orders.

How Execution Grows With Input

As the number of orders grows, the work to find matching rows grows too.

Input Size (orders)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

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 get results grows linearly as the number of rows grows.

Common Mistake

[X] Wrong: "Joining tables always makes queries slower than using one big table."

[OK] Correct: Normalized tables can reduce repeated data and make searches faster by focusing on smaller sets of data.

Interview Connect

Understanding how data layout affects query speed shows you know how to build efficient databases that grow well.

Self-Check

"What if we added indexes on the join columns? How would the time complexity change?"

Practice

1. Why is normalization important in a database?

easy

A. It automatically creates backups of the database.

B. It makes the database run faster by using more memory.

C. It allows storing data in one big table without keys.

D. It reduces data duplication and improves data integrity.

Solution

1. Step 1: Understand what normalization does

   Normalization organizes data to reduce repetition and avoid errors.

2. Step 2: Identify the main benefit

   Reducing duplication helps keep data accurate and easier to update.

3. Final Answer:

   It reduces data duplication and improves data integrity. -> Option D

4. Quick Check:

   Normalization = less duplication [OK]

Hint: Normalization means less repeated data and fewer errors [OK]

Common Mistakes:

• Thinking normalization speeds up all queries
• Believing normalization stores everything in one table
• Confusing normalization with backup processes

2. Which of the following is the correct way to represent a normalized table relationship?

easy

A. Separate tables for customers and orders linked by a customer ID.

B. One table with repeated customer addresses for each order.

C. All data combined in a single table without keys.

D. Storing all orders in a text file outside the database.

Solution

1. Step 1: Recall normalization structure

   Normalization splits data into related tables connected by keys.

2. Step 2: Identify correct table design

   Separate tables for customers and orders linked by customer ID avoid duplication.

3. Final Answer:

   Separate tables for customers and orders linked by a customer ID. -> Option A

4. Quick Check:

   Normalized tables use keys to link data [OK]

Hint: Normalized tables use keys to connect related data [OK]

Common Mistakes:

• Repeating data in one big table
• Ignoring foreign keys between tables
• Storing data outside the database

3. Given two tables:
Customers(customer_id, name, address)
Orders(order_id, customer_id, product)
What happens if you update a customer's address in the Customers table?

medium

A. The address updates in all related orders automatically.

B. The address in Orders table also changes because it stores addresses.

C. Only the address in the Customers table changes; orders remain linked by customer_id.

D. The database throws an error because address is duplicated.

Solution

1. Step 1: Understand table roles

   Customers table stores addresses; Orders table links by customer_id only.

2. Step 2: Effect of updating address

   Updating address changes it only in Customers; Orders remain linked by customer_id without address duplication.

3. Final Answer:

   Only the address in the Customers table changes; orders remain linked by customer_id. -> Option C

4. Quick Check:

   Normalized data updates in one place [OK]

Hint: Update data in one table; linked tables stay consistent [OK]

Common Mistakes:

• Assuming address is stored in Orders table
• Thinking all related tables update automatically
• Believing address duplication causes errors

4. You have a table storing customer orders with repeated customer names and addresses. What is the main problem with this design?

medium

A. It improves query speed by avoiding joins.

B. It wastes space and risks inconsistent data.

C. It ensures data is always backed up.

D. It automatically normalizes data.

Solution

1. Step 1: Identify issue with repeated data

   Repeating customer info wastes space and can cause inconsistent updates.

2. Step 2: Understand normalization benefit

   Normalization avoids repetition, saving space and keeping data consistent.

3. Final Answer:

   It wastes space and risks inconsistent data. -> Option B

4. Quick Check:

   Repeated data = waste and errors [OK]

Hint: Repeated data wastes space and causes errors [OK]

Common Mistakes:

• Thinking repeated data speeds up queries
• Confusing normalization with backup
• Believing database auto-fixes repetition

5. You have a table with columns: OrderID, CustomerName, CustomerAddress, Product. To normalize it, which step should you take?

hard

A. Split into two tables: Customers (CustomerID, CustomerName, CustomerAddress) and Orders (OrderID, Product, CustomerID).

B. Add more columns to store multiple addresses per customer.

C. Combine all data into one table without keys.

D. Store customer addresses as a comma-separated list in Orders.

Solution

1. Step 1: Identify repeated data

   CustomerName and CustomerAddress repeat for each order, causing duplication.

2. Step 2: Apply normalization

   Split data into Customers table (with unique customer info) and Orders table linked by CustomerID.

3. Final Answer:

   Split into two tables: Customers (CustomerID, CustomerName, CustomerAddress) and Orders (OrderID, Product, CustomerID). -> Option A

4. Quick Check:

   Normalization splits repeated data into related tables [OK]

Hint: Split repeated data into separate tables linked by keys [OK]

Common Mistakes:

• Adding columns instead of splitting tables
• Storing multiple addresses in one field
• Ignoring keys to link tables