The idea: what a set of columns fixes
A functional dependency (FD) X → Y says: two rows that agree on X also agree on Y. From a few FDs you can work out, with no data at all, which columns a set of columns fixes, which sets are keys, and whether a table repeats facts. This page does that on the schema alone: a list of attributes and a list of FDs. Database Normalization: 1NF, 2NF and 3NF shows the same ideas on real rows.
Attribute closure
The closure of a set X, written X⁺, is every attribute that X fixes. The algorithm is short:
- Start with the set itself.
- Find an FD whose whole left side is inside the set. It fires: add its right side.
- Repeat until a pass over the FDs adds nothing.
In R(A, B, C, D, E) with A → B, B → C, AD → E, the set {A} grows to {A, B} and then to {A, B, C}. AD → E never fires, because D is not in the set. So {A}⁺ = {A, B, C} (Demo 1).
One pass is not always enough. In R(A, B, C, D) with AB → C, C → D, D → A, start from {B, D}. In the first pass AB → C can't fire, because A is missing. Then D → A adds A. In the second pass AB → C fires. {B, D}⁺ is all four attributes (Demo 2).
Superkeys and candidate keys
A set X is a superkey when X⁺ is every attribute of the relation. A candidate key is a superkey with no smaller superkey inside it. An attribute that belongs to some candidate key is prime.
To find the keys, test sets with the closure, smallest first. Two shortcuts keep the list short. An attribute that is on no right side can never be produced, so it is in every key. And a set that contains a key already found is a superkey but not minimal, so it is skipped.
| Relation | FDs | In every key | Tests | Candidate keys |
|---|---|---|---|---|
| R(A, B, C, D, E) | A → B, B → C, AD → E | A, D | 1 | AD |
| R(S, C, T) | SC → T, T → C | S | 3 | SC, ST |
| R(A, B, C, D) | AB → C, C → D, D → A | B | 4 | AB, BC, BD |
In the last relation {B} alone fixes nothing new, then {A, B}, {B, C} and {B, D} each reach all of R (Demo 3). A relation can have several candidate keys; the primary key is the one you pick.
BCNF and the split
A table is in Boyce–Codd normal form (BCNF) when, in every FD X → Y that holds in it (except the trivial ones, where Y is inside X), X is a superkey. If X is not a superkey, many rows can share the same X, and each of them repeats the same Y.
The fix is to split the table on the bad FD:
- one table gets
X⁺, everything X fixes; - the other keeps X and the rest of the attributes.
X stays in both tables and links them. Then each new table is checked again. In R(A, B, C, D, E) the key is AD, so A → B breaks BCNF. The split gives (A, B, C) and (A, D, E). In (A, B, C) the key is A, so B → C breaks BCNF, and a second split gives (B, C) and (A, B). Three tables, all in BCNF (Demo 4).
Lossless join test
A split is lossless when joining the two tables gives back exactly the original rows. The test needs only a closure: take the attributes the two tables share. If their closure covers one of the tables, they are a key of that table, each row on the other side meets exactly one row, and the join is exact.
A BCNF split always passes. The tables share X, and one of them is X⁺. A cut made with no FD behind it usually fails. Cut R(S, C, T) into (S, C) and (C, T): they share C, and {C}⁺ = {C} covers neither. One course has many students and many teachers, so the join pairs every student of a course with every teacher of it (Demo 6).
Dependency preservation: BCNF against 3NF
A decomposition preserves an FD when the tables can still check it without a join. That is so when the FD lies inside one table, or follows from the FDs that do. In Demo 4 all three FDs lie inside one table each.
The classic counter-example is R(S, C, T): student, course, teacher. A student has one teacher per course (SC → T), and a teacher gives one course (T → C). The keys are SC and ST. T is not a superkey, so T → C breaks BCNF. The split gives (C, T) and (S, T). It is lossless, but no table holds S, C and T together: SC → T is lost (Demo 5).
R(S, C, T) is already in 3NF. 3NF allows X → A when X is a superkey or A is prime, and C is part of the key SC. So 3NF keeps the one table and both FDs, and pays with repeated "teacher gives course" facts. That is the trade:
| 3NF: R(S, C, T) | BCNF: (C, T) and (S, T) | |
|---|---|---|
| Lossless | ✓ one table | ✓ shared T is a key of (C, T) |
| SC → T | ✓ a key of the table | ✗ lost, needs a join |
| T → C | ✗ no key can state it; the fact repeats | ✓ T is the key of (C, T) |
In MariaDB a key is the only cheap way to state an FD. The 3NF table states SC → T with a key:
CREATE TABLE enrol ( s INT, c INT, t INT, PRIMARY KEY (s, c) -- one teacher per student and course );
After the BCNF split, PRIMARY KEY (t) on the teacher table states T → C, but nothing states SC → T. MariaDB has no CREATE ASSERTION, and a CHECK constraint can't contain a subquery, so a rule that spans two tables needs a trigger or a check in the application.
A lost FD is not rare. R(A, B, C, D) with AB → C, C → D, D → A has three keys and is in 3NF, yet BCNF splits it twice and loses AB → C (Demo 7).
See also Database Normalization: 1NF, 2NF and 3NF for anomalies and a lossy join on real rows, ER Model to Tables: Keys and Foreign Keys for where the tables come from, and Relational Algebra: Tables In, Table Out for the join used in the lossless test.
What the page leaves out
Armstrong's axioms, which prove that the closure algorithm finds every implied FD. The minimal cover of a set of FDs and the 3NF synthesis algorithm built on it, which always gives a lossless design that keeps every FD. The chase test for a lossless join of three or more tables at once (the page tests each two-way split, which is enough for a design built by splits). Projecting FDs onto a table in general: it can take a closure for every subset of the table. 4NF and multivalued dependencies, 5NF. MariaDB does not find or check functional dependencies for you: only keys, UNIQUE and foreign keys are enforced.