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

Time Complexity: Third Normal Form (3NF)

O(n * m)

Understanding Time Complexity

When organizing data in a database using Third Normal Form (3NF), we want to understand how the work needed to check and enforce 3NF grows as the database size increases.

We ask: How does the effort to ensure 3NF change when the number of records or attributes grows?

Scenario Under Consideration

Analyze the time complexity of checking if a database table is in 3NF.

-- Assume a table with attributes and functional dependencies
-- Steps to check 3NF:
-- 1. Identify all candidate keys
-- 2. For each functional dependency (FD):
--    a. Check if FD is trivial or if determinant is a superkey
--    b. Check if dependent attributes are prime (part of any key)
-- 3. Confirm all FDs meet 3NF rules
    

This process involves examining keys and dependencies to ensure no unwanted data duplication or anomalies.

Identify Repeating Operations

Look at what repeats during the 3NF check:

• Primary operation: Checking each functional dependency against candidate keys and prime attributes.
• How many times: Once for every functional dependency in the table.

How Execution Grows With Input

As the number of functional dependencies (FDs) and attributes grows, the checking work grows roughly in proportion.

Input Size (number of FDs)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows linearly as the number of functional dependencies increases.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to check 3NF grows in proportion to the number of functional dependencies (n) and the number of attributes (m), since checking candidate keys and prime attributes involves attribute-level operations.

Common Mistake

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

[OK] Correct: Each functional dependency must be checked, so more dependencies mean more work.

Interview Connect

Understanding how the effort to enforce 3NF grows helps you explain database design choices clearly and shows you can think about efficiency in organizing data.

Self-Check

"What if the number of attributes grows but the number of functional dependencies stays the same? How would the time complexity change?"

Practice

1. What is the main goal of the Third Normal Form (3NF) in database design?

easy

A. To ensure no non-key column depends on another non-key column

B. To remove all duplicate rows from a table

C. To combine multiple tables into one

D. To allow NULL values in all columns

Solution

1. Step 1: Understand 3NF definition

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

2. Step 2: Compare options with 3NF goal

   Only To ensure no non-key column depends on another non-key column correctly states this goal. Other options describe different concepts.

3. Final Answer:

   To ensure no non-key column depends on another non-key column -> Option A

4. Quick Check:

   3NF = No transitive dependency [OK]

Hint: 3NF removes transitive dependencies between non-key columns [OK]

Common Mistakes:

• Confusing 3NF with removing duplicates
• Thinking 3NF merges tables
• Believing 3NF allows NULLs everywhere

2. Which of the following functional dependencies violates the Third Normal Form (3NF)?

easy

A. PrimaryKey -> NonKeyColumn

B. NonKeyColumn1 -> NonKeyColumn2

C. PrimaryKey -> CompositeKey

D. PrimaryKey -> ForeignKey

Solution

1. Step 1: Identify 3NF violation

   3NF disallows non-key columns determining other non-key columns (transitive dependency).

2. Step 2: Analyze each dependency

   NonKeyColumn1 -> NonKeyColumn2 shows a non-key column determining another non-key column, violating 3NF.

3. Final Answer:

   NonKeyColumn1 -> NonKeyColumn2 -> Option B

4. Quick Check:

   Transitive dependency = 3NF violation [OK]

Hint: Watch for non-key to non-key dependencies breaking 3NF [OK]

Common Mistakes:

• Assuming all dependencies from primary key violate 3NF
• Confusing foreign keys with functional dependencies
• Ignoring transitive dependencies

3. Consider a table with columns StudentID (primary key), AdvisorName, and AdvisorOffice. If AdvisorName determines AdvisorOffice, which of the following is true about this table regarding 3NF?

medium

A. The table is in 3NF because StudentID is the primary key

B. The table violates 3NF because AdvisorOffice depends on StudentID

C. The table is in 3NF because AdvisorOffice depends on AdvisorName

D. The table violates 3NF due to transitive dependency

Solution

1. Step 1: Identify dependencies

   StudentID -> AdvisorName and AdvisorName -> AdvisorOffice shows a transitive dependency.

2. Step 2: Check 3NF rules

   3NF disallows non-key columns (AdvisorName) determining other non-key columns (AdvisorOffice).

3. Final Answer:

   The table violates 3NF due to transitive dependency -> Option D

4. Quick Check:

   Transitive dependency breaks 3NF [OK]

Hint: Check if non-key columns determine others to spot 3NF violation [OK]

Common Mistakes:

• Thinking primary key alone ensures 3NF
• Ignoring transitive dependencies
• Confusing direct and transitive dependencies

4. A table has columns OrderID (primary key), CustomerName, and CustomerCity. The dependency CustomerName -> CustomerCity exists. What is the problem with this table in terms of 3NF, and how can it be fixed?

medium

A. Violates 3NF; fix by splitting into two tables separating customer info

B. No problem; table is already in 3NF

C. Violates 3NF; fix by adding CustomerCity to primary key

D. No problem; just rename columns

Solution

1. Step 1: Identify 3NF violation

   CustomerName -> CustomerCity is a transitive dependency violating 3NF.

2. Step 2: Fix violation by normalization

   Split table into Orders and Customers tables to separate customer details.

3. Final Answer:

   Violates 3NF; fix by splitting into two tables separating customer info -> Option A

4. Quick Check:

   Split tables to remove transitive dependencies [OK]

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

Common Mistakes:

• Adding columns to primary key incorrectly
• Ignoring transitive dependencies
• Thinking renaming fixes normalization

5. You have a table with columns EmployeeID (primary key), DepartmentID, DepartmentName, and ManagerID. DepartmentID determines DepartmentName and ManagerID. How should you redesign the table to achieve Third Normal Form (3NF)?

hard

A. Keep all columns in one table because EmployeeID is primary key

B. Add DepartmentName and ManagerID to EmployeeID primary key

C. Create two tables: one for Employees and one for Departments with DepartmentID as key

D. Remove ManagerID column to fix 3NF

Solution

1. Step 1: Identify transitive dependencies

   DepartmentID -> DepartmentName and ManagerID means non-key columns depend on another non-key column.

2. Step 2: Normalize by splitting tables

   Create separate Department table with DepartmentID as key to remove transitive dependencies.

3. Final Answer:

   Create two tables: one for Employees and one for Departments with DepartmentID as key -> Option C

4. Quick Check:

   Split tables to remove transitive dependencies [OK]

Hint: Separate dependent columns into new table keyed by determinant [OK]

Common Mistakes:

• Keeping all columns in one table ignoring transitive dependency
• Adding columns to primary key unnecessarily
• Removing important columns instead of normalizing