Checking if \(R\) satisfies 3NF

First Normal Form (1NF)

A relation \(R\) is in 1NF if all attributes contain only atomic (indivisible) values. No repeating groups or nested relations are allowed.

Example: A table with a column PhoneNumbers = "123-456, 789-012" is not in 1NF. Split it into separate rows or a separate table.

Second Normal Form (2NF)

A relation \(R\) is in 2NF if it is in 1NF and:

\[ \forall (X \to A) \in F^+,\, A \notin X,\, A \text{ non-prime}: X \text{ is a superkey of } R \]

To check 2NF: for each non-trivial FD \(X \to A\) where \(A\) is non-prime, verify that \(X\) is a superkey. If you find one where \(X\) is not a superkey, then \(R\) violates 2NF.

Partial dependency: a non-prime attribute depends on only a proper subset of a candidate key.

Example: Student enrollment tracking

• \(R(\underline{\text{StudentID}}, \underline{\text{CourseID}}, \text{StudentName}, \text{Grade})\)
• Candidate key: \(\{\text{StudentID}, \text{CourseID}\}\) (a student enrolls in multiple courses)
• FDs:
  • \(\text{StudentID} \to \text{StudentName}\) (a student has one name)
  • \(\{\text{StudentID}, \text{CourseID}\} \to \text{Grade}\) (a student gets one grade per course)

Problem: \(\text{StudentName}\) depends on only \(\text{StudentID}\), which is a proper subset of the key \(\{\text{StudentID}, \text{CourseID}\}\). This is a partial dependency, so \(R\) is not in 2NF.

Solution: decompose into:

• \(R_1(\underline{\text{StudentID}}, \text{StudentName})\)
• \(R_2(\underline{\text{StudentID}}, \underline{\text{CourseID}}, \text{Grade})\)

Now both relations are in 2NF because \(\text{Grade}\) depends on the full key of \(R_2\).

Third Normal Form (3NF)

Given a relation schema \(R\) and a set of functional dependencies \(F\) on \(R\), \(R\) is in 3NF (w.r.t. \(F\)) iff:

\[ \forall (X \to A) \in F^+,\, A \notin X: \begin{cases} X \text{ is a superkey of } R \\ A \text{ is a prime attribute of } R \end{cases} \]

Where:

• Superkey: \(X\) is a superkey of \(R\) iff \(X^+ = R\).
• Prime attribute: an attribute that belongs to some candidate key of \(R\).

Why \(A \notin X\) matters:

By reflexivity, for any \(X\) and any \(A \in X\), we have \(X \to A \in F^+\). If we checked these trivial dependencies, consider \(R(A, B, C)\) with key \(\{A\}\) and \(F = \{A \to B, A \to C\}\). The reflexive dependency \(\{B, C\} \to B\) is in \(F^+\), but:

• \(\{B, C\}\) is not a superkey
• \(B\) is not prime (only \(A\) is in the key)

Without excluding trivial FDs, this would fail 3NF even though \(R\) is in 3NF (all non-trivial FDs have \(A\) on the LHS, which is a superkey). The condition \(A \notin X\) excludes such reflexive dependencies.

In practice: decompose FDs into single-attribute RHS (\(X \to A_1 A_2 \dots A_n\) becomes \(X \to A_1, \dots, X \to A_n\)), then verify the condition for each non-trivial \(X \to A\).

If you find a single counterexample (a non-trivial \(X \to A\) that violates the rule), then \(R\) is not in 3NF.

Example

Given:

• Relation scheme: \(R = \{A, B, C, D\}\)
• Functional dependencies: \(F = \{A \to B, B \to C, C \to D\}\)

Check each FD:

1. For \(A \to B\):
   • \(B \notin A\) (not trivial)
   • \(A\) is a superkey (\(A^+ = \{A, B, C, D\}\)) ✓
2. For \(B \to C\):
   • \(C \notin B\) (not trivial)
   • \(B\) is not a superkey (\(B^+ = \{B, C, D\} \neq R\))
   • \(C\) is not prime (only \(A\) is a key)
3. For \(C \to D\):
   • \(D \notin C\) (not trivial)
   • \(C\) is not a superkey
   • \(D\) is not prime

\(B \to C\) and \(C \to D\) violate 3NF, so \(R\) is not in 3NF.

Boyce-Codd Normal Form (BCNF)

Given a relation schema \(R\) and a set of functional dependencies \(F\) on \(R\), \(R\) is in BCNF (w.r.t. \(F\)) iff:

\[ \forall (X \to A) \in F^+,\, A \notin X: X \text{ is a superkey of } R \]

In other words: for every non-trivial functional dependency \(X \to A\), the left-hand side \(X\) must be a superkey.

BCNF vs 3NF: BCNF is stricter than 3NF. In 3NF, a dependency \(X \to A\) can violate the superkey requirement if \(A\) is a prime attribute. BCNF eliminates this exception—all non-trivial dependencies must have a superkey on the left side.

Example: Employee department assignment

• \(R(\underline{\text{EmpID}}, \text{DeptID}, \text{DeptName})\)
• Candidate keys: \(\{\text{EmpID}\}\) and \(\{\text{EmpID}, \text{DeptName}\}\) (assuming an employee can only be in one department)
• FDs:
  • \(\text{EmpID} \to \text{DeptID}\)
  • \(\text{EmpID} \to \text{DeptName}\)
  • \(\text{DeptID} \to \text{DeptName}\) (each department ID has one name)

Checking BCNF:

1. For \(\text{EmpID} \to \text{DeptID}\): \(\text{EmpID}\) is a superkey ✓
2. For \(\text{EmpID} \to \text{DeptName}\): \(\text{EmpID}\) is a superkey ✓
3. For \(\text{DeptID} \to \text{DeptName}\):
   • \(\text{DeptName} \notin \text{DeptID}\) (not trivial)
   • \(\text{DeptID}\) is not a superkey (\(\text{DeptID}^+ = \{\text{DeptID}, \text{DeptName}\} \neq R\))

The dependency \(\text{DeptID} \to \text{DeptName}\) violates BCNF because \(\text{DeptID}\) is not a superkey. (Note: \(R\) is in 3NF because \(\text{DeptName}\) is prime.)

Solution: decompose into:

• \(R_1(\underline{\text{DeptID}}, \text{DeptName})\)
• \(R_2(\underline{\text{EmpID}}, \text{DeptID})\)

Both relations are now in BCNF.