First Normal Form (1NF) in SQL - Time & Space Complexity

Time Complexity: First Normal Form (1NF)

O(n)

Understanding Time Complexity

When we check if a database table follows First Normal Form, we look at how data is organized in rows and columns.

We want to understand how the work needed to verify this grows as the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of this SQL query that checks for repeated groups in a table.

SELECT CustomerID, COUNT(OrderID) AS OrderCount
FROM Orders
GROUP BY CustomerID
HAVING COUNT(OrderID) > 1;
    

This query finds customers who have more than one order, helping to check if data is stored in separate rows as 1NF requires.

Identify Repeating Operations

Look at what repeats as the query runs:

• Primary operation: Scanning all rows in the Orders table.
• How many times: Once for each row, to count orders per customer.

How Execution Grows With Input

As the number of orders grows, the query must check each one to count them by customer.

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

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check 1NF grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "Checking 1NF takes the same time no matter how many rows there are."

[OK] Correct: The database must look at each row to find repeated groups, so more rows mean more work.

Interview Connect

Understanding how checking data rules like 1NF scales helps you explain database design clearly and shows you know how data size affects work.

Self-Check

"What if the table had an index on CustomerID? How would that change the time complexity of checking 1NF?"

Practice

1. What does First Normal Form (1NF) require in a database table?

easy

A. Each table must have a primary key.

B. Tables must have at least two columns.

C. Each column must contain atomic (single) values only.

D. Columns can contain lists or multiple values.

Solution

1. Step 1: Understand 1NF definition

   1NF requires that each column holds only one atomic value per row, no lists or sets.

2. Step 2: Evaluate options

   Each column must contain atomic (single) values only. matches the 1NF rule exactly. Options A, B, and D describe other concepts or violate 1NF.

3. Final Answer:

   Each column must contain atomic (single) values only. -> Option C

4. Quick Check:

   1NF = atomic columns only [OK]

Hint: 1NF means no multiple values in one cell [OK]

Common Mistakes:

• Thinking 1NF requires a primary key
• Allowing lists or sets in columns
• Confusing 1NF with other normal forms

2. Which of the following SQL table definitions violates First Normal Form (1NF)?

easy

A. CREATE TABLE Students (ID INT, Name VARCHAR(50), PhoneNumbers VARCHAR(100));

B. CREATE TABLE Students (ID INT PRIMARY KEY, Name VARCHAR(50), PhoneNumber VARCHAR(15));

C. CREATE TABLE Students (ID INT, Name VARCHAR(50), Email VARCHAR(50));

D. CREATE TABLE Students (ID INT, Name VARCHAR(50), Address VARCHAR(100));

Solution

1. Step 1: Identify 1NF violation in table definitions

   CREATE TABLE Students (ID INT, Name VARCHAR(50), PhoneNumbers VARCHAR(100)); uses PhoneNumbers as VARCHAR(100), likely storing multiple numbers in one field, violating 1NF.

2. Step 2: Check other options

   Options A, B, and C have single atomic values per column, so they follow 1NF.

3. Final Answer:

   CREATE TABLE Students (ID INT, Name VARCHAR(50), PhoneNumbers VARCHAR(100)); -> Option A

4. Quick Check:

   Multiple values in one column break 1NF [OK]

Hint: Multiple values in one column break 1NF [OK]

Common Mistakes:

• Assuming VARCHAR can hold multiple values without issue
• Confusing primary key with 1NF rules
• Ignoring column data types when checking 1NF

3. Given the table below, which row violates First Normal Form (1NF)?

Orders(OrderID, Customer, Items)
Where Items column contains comma-separated product IDs.

Rows:
1. (101, 'Alice', 'P1')
2. (102, 'Bob', 'P2,P3')
3. (103, 'Carol', 'P4')
4. (104, 'Dave', 'P5')

medium

A. Row 1

B. Row 2

C. Row 3

D. Row 4

Solution

1. Step 1: Understand 1NF violation in data rows

   Row 2 has 'P2,P3' in Items, which is multiple values in one cell, violating 1NF.

2. Step 2: Check other rows

   Rows 1, 3, and 4 have single product IDs, so they follow 1NF.

3. Final Answer:

   Row 2 -> Option B

4. Quick Check:

   Multiple values in one cell break 1NF [OK]

Hint: Comma-separated values in one cell break 1NF [OK]

Common Mistakes:

• Ignoring multiple values separated by commas
• Assuming string with commas is atomic
• Not checking all rows carefully

4. You have this table definition violating 1NF:

CREATE TABLE Employees (ID INT, Name VARCHAR(50), Skills VARCHAR(100));

Skills column stores multiple skills separated by commas.
Which SQL change fixes the 1NF violation?

medium

A. Store skills as a single string with semicolons instead of commas.

B. Change Skills to TEXT and store JSON arrays.

C. Keep Skills as VARCHAR but limit length to 50.

D. Create a separate Skills table with EmployeeID and Skill columns.

Solution

1. Step 1: Identify 1NF violation and fix approach

   Storing multiple skills in one column violates 1NF. The fix is to separate repeating data into another table.

2. Step 2: Evaluate options for 1NF compliance

   Create a separate Skills table with EmployeeID and Skill columns. creates a separate Skills table with one skill per row, fixing 1NF. Options B, C, and D still store multiple values in one column.

3. Final Answer:

   Create a separate Skills table with EmployeeID and Skill columns. -> Option D

4. Quick Check:

   Separate repeating data into new table for 1NF [OK]

Hint: Use separate table for repeating groups to fix 1NF [OK]

Common Mistakes:

• Trying to store multiple values in one column anyway
• Using JSON or delimiters inside one column
• Not normalizing repeating data into separate tables

5. You have a table storing orders with multiple products in one column:

Orders(OrderID INT, Customer VARCHAR(50), Products VARCHAR(255))
Products column stores product IDs separated by commas.

How do you redesign the schema to fully comply with First Normal Form (1NF)?

hard

A. Create a new table OrderProducts(OrderID, ProductID) with one product per row.

B. Split Products into multiple columns like Product1, Product2, Product3.

C. Store Products as JSON array in the same column.

D. Keep Products column but restrict to one product ID only.

Solution

1. Step 1: Identify 1NF violation in current design

   Storing multiple product IDs in one column violates 1NF because values are not atomic.

2. Step 2: Choose redesign that enforces atomicity

   Create a new table OrderProducts(OrderID, ProductID) with one product per row. creates a new table with one product per row, fully normalizing the data and satisfying 1NF. Split Products into multiple columns like Product1, Product2, Product3. uses multiple columns but is limited and not scalable. Options C and D still violate 1NF.

3. Final Answer:

   Create a new table OrderProducts(OrderID, ProductID) with one product per row. -> Option A

4. Quick Check:

   Separate repeating data into rows for 1NF compliance [OK]

Hint: Use separate table with one value per row for 1NF [OK]

Common Mistakes:

• Adding multiple columns instead of rows
• Using JSON or arrays inside one column
• Restricting to one product but losing data