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

Time Complexity: First Normal Form (1NF)

O(n * m)

Understanding Time Complexity

When working with databases, organizing data properly helps queries run efficiently.

We want to understand how checking if a table meets First Normal Form affects the work done as data grows.

Scenario Under Consideration

Analyze the time complexity of verifying First Normal Form on a table.

-- Check each row for atomic values in each column
FOR EACH row IN table LOOP
  FOR EACH column IN row LOOP
    IF column contains multiple values THEN
      RETURN false; -- violates 1NF
    END IF;
  END LOOP;
END LOOP;
RETURN true; -- table is in 1NF
    

This code checks every cell in the table to ensure each column holds only single, indivisible values.

Identify Repeating Operations

Identify the loops that repeat over the data.

• Primary operation: Checking each cell in the table for atomicity.
• How many times: Once for every row and every column in the table.

How Execution Grows With Input

As the number of rows or columns increases, the number of checks grows proportionally.

Input Size (rows x columns)	Approx. Operations
10 x 5	50
100 x 5	500
1000 x 5	5000

Pattern observation: Doubling rows doubles the work; more columns also increase work linearly.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to check 1NF grows proportionally with the number of rows (n) and columns (m) in the table.

Common Mistake

[X] Wrong: "Checking just a few rows is enough to confirm 1NF for the whole table."

[OK] Correct: Because any row could have multiple values in a column, all rows must be checked to be sure.

Interview Connect

Understanding how data size affects validation checks like 1NF helps you design efficient database systems and write better queries.

Self-Check

"What if the table had nested tables inside columns? How would that affect the time complexity of checking 1NF?"

Practice

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

easy

A. Tables have multiple primary keys

B. Tables have no foreign keys

C. Each cell contains only one atomic value

D. Data is encrypted for security

Solution

1. Step 1: Understand the definition of 1NF

   1NF requires that each column in a table holds atomic (indivisible) values, meaning no multiple values or lists in a single cell.

2. Step 2: Compare options with 1NF definition

   Only Each cell contains only one atomic value matches this requirement. Other options relate to different concepts like keys or security.

3. Final Answer:

   Each cell contains only one atomic value -> Option C

4. Quick Check:

   1NF = atomic values only [OK]

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

Common Mistakes:

• Confusing 1NF with encryption or keys
• Thinking 1NF allows multiple values in a cell
• Mixing 1NF with higher normal forms

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

easy

A. A table with a column storing multiple phone numbers separated by commas

B. A table where each column contains only single values

C. A table with unique primary keys for each row

D. A table with no repeating rows

Solution

1. Step 1: Identify the 1NF violation

   1NF forbids multiple values in a single cell. Storing multiple phone numbers separated by commas means one cell holds multiple values.

2. Step 2: Check other options

   Options B, C, and D follow 1NF rules because they have atomic values and unique rows.

3. Final Answer:

   A table with a column storing multiple phone numbers separated by commas -> Option A

4. Quick Check:

   Multiple values in one cell violate 1NF [OK]

Hint: Look for columns with multiple values in one cell [OK]

Common Mistakes:

• Assuming commas separate values correctly in 1NF
• Confusing unique rows with atomic values
• Ignoring multi-valued columns

3. Consider this table data:
StudentID | Courses
1 | Math, Science
2 | English
3 | Math, English
Which statement is true about this table regarding 1NF?

medium

A. The table violates 1NF because the Courses column has multiple values

B. The table is in 1NF because Courses are listed as text

C. The table is in 1NF because each row has a unique StudentID

D. The table violates 1NF because StudentID is not unique

Solution

1. Step 1: Analyze the Courses column

   The Courses column contains multiple values separated by commas in some rows, which means cells are not atomic.

2. Step 2: Check uniqueness and 1NF rules

   Although StudentID is unique, 1NF requires atomic values in each cell. Multiple courses in one cell violate 1NF.

3. Final Answer:

   The table violates 1NF because the Courses column has multiple values -> Option A

4. Quick Check:

   Multiple values in one cell break 1NF [OK]

Hint: Check if any cell holds multiple values separated by commas [OK]

Common Mistakes:

• Thinking unique keys alone satisfy 1NF
• Ignoring multi-valued columns
• Assuming text format means atomic values

4. You have a table with columns: OrderID, ProductIDs where ProductIDs stores multiple product IDs separated by semicolons. How would you fix this to comply with 1NF?

medium

A. Remove the ProductIDs column entirely

B. Keep the table as is because semicolons separate values

C. Combine all ProductIDs into one string without separators

D. Split the table so each row has one ProductID per OrderID

Solution

1. Step 1: Identify the 1NF violation

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

2. Step 2: Apply 1NF correction

   Splitting the table so each row has one ProductID per OrderID ensures atomic values and removes repeating groups.

3. Final Answer:

   Split the table so each row has one ProductID per OrderID -> Option D

4. Quick Check:

   One value per cell fixes 1NF violation [OK]

Hint: Make each cell hold only one value by splitting rows [OK]

Common Mistakes:

• Thinking separators alone satisfy 1NF
• Removing columns instead of fixing data structure
• Combining values into one string without atomicity

5. A table stores employee skills as follows:
EmpID | Skills
101 | Java, Python
102 | Python
103 | Java, SQL, Python
How can you transform this table into 1NF compliant form?

hard

A. Keep skills as comma-separated values in one cell

B. Create a new row for each skill per EmpID

C. Remove the Skills column and store skills elsewhere

D. Combine all skills into a single string without commas

Solution

1. Step 1: Identify multi-valued attribute

   The Skills column contains multiple skills separated by commas, violating 1NF.

2. Step 2: Normalize by creating multiple rows

   To comply with 1NF, create a separate row for each skill linked to the same EmpID, making each cell atomic.

3. Final Answer:

   Create a new row for each skill per EmpID -> Option B

4. Quick Check:

   One skill per row ensures 1NF compliance [OK]

Hint: Turn multi-valued cells into multiple rows [OK]

Common Mistakes:

• Leaving multi-valued cells unchanged
• Removing data instead of restructuring
• Combining values without atomicity