Functional Dependencies & Normalization

Normalization is not a ritual of splitting wide tables, and “no duplicate values” is not its objective. It starts from semantic rules—dependencies saying which facts determine which other facts—and derives schemas in which each independently changing fact has one stable home. A good decomposition must also preserve information: joining the pieces must reconstruct exactly the legal original relation, without missing or spurious tuples.

The hard part is not memorizing 1NF, 2NF, 3NF, and BCNF. It is learning to move from domain statements to dependencies, use inference to find keys, and judge the two properties that a decomposition can trade off: lossless join and dependency preservation.

From domain rules to functional dependencies #

Let $R(U)$ be a relation schema over attribute set $U$, and let $X,Y \subseteq U$. A functional dependency (FD)

$$X \to Y$$

holds on relation value $r$ when any two tuples that agree on every attribute of $X$ also agree on every attribute of $Y$:

$$\forall t_1,t_2 \in r:\quad t_1[X]=t_2[X] \Rightarrow t_1[Y]=t_2[Y].$$

The dependency is a constraint on all legal states, not a correlation in today's rows and not necessarily a causal claim.

The reverse dependencies do not automatically hold. Many courses may share an instructor, and many instructors may share an office. Direction is the entire point.

Trivial and nontrivial dependencies #

$X \to Y$ is trivial when $Y \subseteq X$; agreement on $X$ already includes agreement on $Y$. Otherwise it is nontrivial. Trivial FDs are always true and impose no additional restriction on legal instances.

A data sample can refute but not establish an FD #

If two observed tuples have the same course_id and different instructor_id, the sample refutes course_id → instructor_id. If no such pair exists, the sample is merely consistent with the FD. Only the domain rule says whether every future legal state must satisfy it.

Armstrong's axioms: the inference kernel #

For a set of FDs $F$, $F^+$ denotes every FD logically implied by $F$. Armstrong's three inference rules are sound—every derived dependency is truly implied—and complete—every implied FD can be derived.

Useful derived rules include:

• union: $X\to Y$ and $X\to Z$ imply $X\to YZ$;
• decomposition: $X\to YZ$ implies $X\to Y$ and $X\to Z$;
• pseudotransitivity: $X\to Y$ and $WY\to Z$ imply $WX\to Z$.

These are proof rules, not commands that inspect stored rows.

Attribute closure turns inference into an algorithm #

The closure $X_F^+$ is the set of every attribute functionally determined by $X$ under $F$. Compute it by a fixed point:

closure := X
repeat
  for each dependency L → R in F
    if L ⊆ closure then closure := closure ∪ R
until closure no longer changes

Because the universe has finitely many attributes and closure only grows, the procedure terminates.

Worked closure and key derivation #

Consider

$$Enrollment(student, course, instructor, office, grade)$$

with

$$F=\{ student\ course \to grade,\quad course \to instructor,\quad instructor \to office \}.$$

Start from {student, course}:

Thus {student, course} is a superkey. It is minimal because neither {student} nor {course} closes to all attributes, so it is a candidate key.

Closure answers several questions with the same mechanism:

• Is $X$ a superkey? Exactly when $X_F^+=U$.
• Does $F$ imply $X\to Y$? Exactly when $Y\subseteq X_F^+$.
• Is an attribute extraneous in a determinant? Remove it and test the closure.
• Which attributes must occur in every key? Any attribute appearing on no dependency's right side cannot be derived from others and must be seeded.

Minimal covers remove redundant syntax #

A minimal (or canonical) cover is an equivalent FD set arranged for synthesis. A common form requires:

1. one attribute on each right-hand side;
2. no extraneous attribute on any left-hand side;
3. no dependency removable without changing the closure.

The safe workflow is:

1. decompose $X\to YZ$ into $X\to Y$ and $X\to Z$;
2. for each $A\in X$, test whether $(X-\{A\})^+$ already contains the right side; if yes, remove $A$;
3. temporarily remove each FD and test whether the remaining set still implies it; if yes, discard the redundant FD;
4. optionally regroup dependencies with equal left sides for presentation.

Order can lead to different-looking minimal covers, but they are equivalent if their closures are the same. Minimal cover does not mean a globally unique string representation.

Why the unnormalized relation is fragile #

In Enrollment, three distinct facts are mixed in one tuple:

• a student receives a grade in a course;
• a course has a responsible instructor;
• an instructor occupies an office.

That creates anomalies:

The repeated strings are a symptom. The mechanism is that facts with different determinants and lifecycles occupy the same relation.

flowchart TD
  D["Domain rules"] --> F["Functional dependencies"]
  F --> C["Closures and candidate keys"]
  C --> M["Minimal cover"]
  M --> S["3NF synthesis or BCNF decomposition"]
  S --> L["Lossless-join test"]
  S --> P["Dependency-preservation test"]
  L --> E["SQL constraints"]
  P --> E

Normal forms are predicates on dependencies #

Let an attribute be prime if it belongs to at least one candidate key; otherwise it is non-prime. Normal forms are properties of a schema together with its intended dependency set—not visual properties of a table.

First normal form: one value per attribute position #

In the classical relational model, every tuple component is a single value from the declared domain; there are no repeating column groups or relation-valued cells inside the same flat relation. “Atomic” is relative to the chosen domain: a timestamp can be one value even though it has components, while a comma- separated list of product IDs is usually hiding a separate relationship.

Modern SQL systems permit arrays, JSON, and composite values. Using them is not automatically wrong; it means the nested structure and its constraints are now inside one domain value rather than represented by ordinary relations. Ask whether the application must independently identify, constrain, join, or update the elements.

Second normal form: no partial dependency on a candidate key #

A schema is in 2NF when it is in 1NF and no non-prime attribute depends on a proper subset of a candidate key. This matters only when a candidate key is composite.

Enrollment violates 2NF because candidate key (student,course) has proper subset course, and

$$course \to instructor \to office.$$

Both instructor and office are non-prime attributes determined without the whole key.

Third normal form: allow only a controlled prime-attribute exception #

A schema is in 3NF when, for every nontrivial implied dependency $X\to A$, at least one condition holds:

1. $X$ is a superkey; or
2. $A$ is prime.

This definition—not the slogan “no transitive dependencies”—handles multiple candidate keys correctly. The prime-attribute exception is what lets 3NF synthesis preserve every FD while still removing the harmful non-prime dependencies.

Boyce–Codd normal form: every determinant is a superkey #

A schema is in BCNF when every nontrivial implied dependency $X\to Y$ has a superkey determinant $X$. BCNF removes the 3NF prime-attribute exception and is therefore strictly stronger.

Every BCNF schema is in 3NF; not every 3NF schema is in BCNF.

Fourth normal form: independent multivalued facts separate #

A multivalued dependency $X \twoheadrightarrow Y$ says that, for each fixed $X$, the set of possible $Y$ values is independent of the remaining attributes $Z=U-(X\cup Y)$. If a person can have several skills and several languages, and those facts are independent, then

$$Person \twoheadrightarrow Skill \quad\text{and}\quad Person \twoheadrightarrow Language.$$

Storing PersonSkillLanguage(person, skill, language) forces every skill to be paired with every language. Two skills and three languages require six tuples; adding one language requires two more tuples even though no skill fact changed.

4NF requires every nontrivial MVD determinant to be a superkey. Decompose into

$$PersonSkill(person,skill)$$

and

$$PersonLanguage(person,language).$$

The original cross-product is recovered by join, while each independent fact is stored once.

Lossless join: decomposition must not invent facts #

Suppose $R$ is decomposed into $R_1$ and $R_2$. Projection always satisfies

$$r \subseteq \pi_{R_1}(r) \bowtie \pi_{R_2}(r),$$

because every original tuple can be reconstructed from its own projections. The danger is the reverse inclusion: projections from different tuples may recombine into spurious tuples.

For a binary FD-based decomposition, the join is lossless with respect to $F$ when $F^+$ implies at least one of:

$$(R_1 \cap R_2) \to R_1 \qquad\text{or}\qquad (R_1 \cap R_2) \to R_2.$$

The shared attributes must determine all attributes of at least one component.

For decompositions into more than two relations, use the chase/tableau test or a synthesis theorem; pairwise intuition alone is not sufficient.

Dependency preservation: can constraints be checked locally? #

A decomposition $\{R_1,\ldots,R_n\}$ preserves dependencies when the union of the FDs projected onto each component implies all of $F$:

$$\left(\bigcup_i \pi_{R_i}(F)\right)^+ = F^+.$$

If not, an original invariant may require joining relations merely to validate an insert or update. That is logically possible but operationally awkward and often not expressible by ordinary SQL keys/checks.

Losslessness and dependency preservation answer different questions:

Never accept a lossy decomposition. Dependency preservation is a design tradeoff when stronger normal forms make it impossible.

3NF synthesis: preserve dependencies constructively #

Given a minimal cover $G$:

1. create a relation schema $XA$ for each dependency $X\to A$ in $G$ (or group equal determinants);
2. remove any schema contained wholly in another;
3. if no created schema contains a candidate key of the original relation, add one relation containing such a key.

The result is in 3NF, preserves the dependencies, and is lossless when the key relation condition is satisfied by the standard synthesis construction.

For Enrollment, the minimal cover is already

$$student\ course\to grade,\quad course\to instructor,\quad instructor\to office.$$

Synthesis produces:

EnrollmentGrade(student, course, grade)
CourseInstructor(course, instructor)
InstructorOffice(instructor, office)

EnrollmentGrade contains the original candidate key (student,course). Each FD can be enforced in one relation, and the three fact types now have separate lifecycles. In this example the components also satisfy BCNF because every nontrivial determinant is a key of its component.

BCNF decomposition and its tradeoff #

If schema $R$ violates BCNF through nontrivial $X\to Y$ where $X$ is not a superkey, decompose into

$$R_1=X\cup Y$$

and

$$R_2=R-(Y-X).$$

The decomposition is lossless because the intersection contains $X$, which determines $R_1$. Repeat until no component violates BCNF.

BCNF decomposition does not guarantee dependency preservation. Consider

$$R(A,B,C),\qquad F=\{AB\to C,\ C\to B\}.$$

Candidate keys are AB and AC; therefore every attribute is prime. The schema is in 3NF, but C → B violates BCNF because C is not a superkey. Decomposing on that FD gives R1(C,B) and R2(A,C). The join is lossless, yet no component contains A, B, and C together, so AB → C cannot be checked from a single component's dependencies. Enforcing it requires a join or a stronger mechanism.

That is the real 3NF-versus-BCNF decision: retain a controlled 3NF dependency so all constraints remain local, or choose BCNF and accept cross-relation enforcement.

SQL constraints are the executable boundary #

For the synthesized enrollment schema:

CREATE TABLE instructor_office (
  instructor_id bigint PRIMARY KEY,
  office text NOT NULL
);

CREATE TABLE course_instructor (
  course_id bigint PRIMARY KEY,
  instructor_id bigint NOT NULL
    REFERENCES instructor_office (instructor_id)
);

CREATE TABLE enrollment_grade (
  student_id bigint NOT NULL,
  course_id bigint NOT NULL
    REFERENCES course_instructor (course_id),
  grade numeric NOT NULL CHECK (grade BETWEEN 0 AND 100),
  PRIMARY KEY (student_id, course_id)
);

The key on course_instructor.course_id enforces course → instructor. The key on instructor_office.instructor_id enforces instructor → office. The composite key on enrollment_grade enforces one grade per student/course pair.

SQL has no general FUNCTIONAL DEPENDENCY declaration. A dependency is locally enforceable when its determinant is represented by a PRIMARY KEY or suitable UNIQUE constraint in the relation that stores the determined attributes. That is why dependency preservation has operational value.

A disciplined normalization workflow #

1. Define one tuple's fact. Include time scope and units.
2. List domain dependencies. Phrase each as “for one $X$, there is exactly one $Y$.” Separate rules from observations.
3. Split right-hand sides and compute a minimal cover.
4. Compute closures to enumerate candidate keys and prime attributes.
5. Classify violations using the formal 3NF/BCNF/4NF definitions.
6. Synthesize 3NF when local enforcement is the priority, or decompose to BCNF/4NF when stronger redundancy removal is required.
7. Prove losslessness. Use the binary intersection condition or a chase.
8. Test dependency preservation. Identify any invariant that crosses components.
9. Map every retained invariant to enforcement. Key, foreign key, check, exclusion constraint, trigger, transaction, or explicit application rule.
10. Test representative updates, not just reads: insert an entity before a relationship exists, change one determining fact, and delete the last referencing tuple.

When denormalization is legitimate #

Denormalization is a physical or derived-data decision made after the normalized facts and their invariants are understood. A cached total, materialized view, search document, or event projection can be worthwhile, but it creates a second representation that needs an explicit maintenance protocol:

• which copy is authoritative;
• which transaction or asynchronous process updates the derived copy;
• what lag is allowed;
• how drift is detected and repaired;
• what readers observe during partial failure.

Calling an accidental mixed-fact table “denormalized for performance” does not answer any of those questions.

Common wrong turns #

Exercises #

1. For $R(A,B,C,D)$ and $F=\{A\to B, B\to C, AC\to D\}$, compute $A^+$ and decide whether A is a candidate key.
2. In $R(A,B,C)$ with $F=\{AB\to C, C\to B\}$, verify both candidate keys and explain why the schema is 3NF but not BCNF.
3. For a binary decomposition $R_1(A,B)$ and $R_2(B,C)$, state the FD condition that makes the join lossless.
4. A person can independently hold many certifications and speak many languages. Identify the MVDs and a 4NF decomposition.