Functional Dependencies

A functional dependency is a promise about data: whenever two rows agree on these columns, they agree on that one too. A good part of database design is writing those promises down and then arranging the tables so that each fact is stored in exactly one place. This note covers what a dependency says, how to reason from a few of them to everything they imply, and why a table that ignores them turns every update into a chance to contradict itself.

The idea

Write $X \to Y$ , read " $X$ determines $Y$ ", when knowing the values in columns $X$ fixes the value in column $Y$ . In a ticketing table, the ticket number determines the ticket type, and the type determines the price. The dependency is a claim about every table the system could ever hold, not only the rows in it today. That makes it a business rule, and it comes from what the columns mean.

A key is a set of columns that determines every other column, with nothing spare in it. Declaring a primary key is declaring a dependency from the key to the whole row, which is why a key chosen carelessly can quietly stop the table storing what actually happens.

Trouble starts when a dependency's left side is not a key. Picture one wide table of wing scans with the ticket type and price copied into every row. The Adult price now sits in every Adult scan. Change it and you must update every one of those rows, and if one is missed, the table holds two Adult prices at once. That is an update anomaly. You also cannot record the price of a new ticket type until someone is scanned with one, and deleting the last Member scan forgets what a Member ticket costs. Normalisation fixes all three by splitting the table so each dependency's left side becomes the key of its own table. The Database Systems topic walks through the normal forms that make this precise.

The maths

Formally, a relation satisfies $X \to Y$ when no two of its rows agree on $X$ and disagree on $Y$ .

X \to Y \iff \text{for all rows } t_1, t_2:\; t_1[X] = t_2[X] \;\Rightarrow\; t_1[Y] = t_2[Y]

One pair of rows is enough to break a dependency. No number of rows is enough to prove one.

From a declared set of dependencies $F$ , Armstrong's three rules derive every dependency that must also hold: reflexivity, augmentation and transitivity.

\frac{Y \subseteq X}{X \to Y} \qquad\qquad \frac{X \to Y}{XZ \to YZ} \qquad\qquad \frac{X \to Y \quad Y \to Z}{X \to Z}

The rules are sound, so they never derive a false dependency, and complete, so they derive every true one.

In practice you rarely apply the rules by hand. You compute a closure instead: start with $X$ , and whenever a declared dependency's left side sits inside the set, add its right side, until nothing changes.

X^{+} = \{\, A : X \to A \text{ follows from } F \,\}, \qquad X \text{ is a superkey} \iff X^{+} = R

A key is a superkey that stops being one if any column is removed.

Boyce–Codd normal form asks that every dependency that holds has a superkey on its left. Third normal form relaxes this slightly, allowing the right side to be part of some key, which keeps every dependency checkable inside a single table when BCNF cannot.

R \text{ is in BCNF} \iff \text{every non-trivial } X \to Y \text{ that holds has } X^{+} = R

Trivial means Y is already inside X, as in ticket, time determines time.

A split must not lose information. Joining the pieces back has to give exactly the original rows, no more, and that is guaranteed when the shared columns are a key of one of the pieces.

R \to R_1, R_2 \text{ is lossless} \iff (R_1 \cap R_2) \to R_1 \;\text{ or }\; (R_1 \cap R_2) \to R_2

Split on a dependency X to Y by making one table of X and Y, and keeping X in the other.

Try it

The widget holds a log of wing scans at a made-up museum, one row per scan, and the four rules its designer declared. Build a dependency with the buttons. The widget answers two separate questions about it: does this sample of rows break it, and does it follow from the declared rules?

Rules the designer declared

ticket → type
type → price
wing → level
ticket, time → wing

Left side, X (pick one or more)

Right side, Y

Rows in the sample16

Seed 1

ticket → wing

In this sample

Broken. Rows 1 and 4 agree on ticket (T08) but differ on wing: East against West.

From the declared rules

{ticket}⁺ = {ticket, type, price}. The closure does not contain wing, so the rules do not promise this. The left side is not a key.

Via ticket → type, then type → price.

The first 16 wing scans, in time order. X columns are marked (X), Y is (Y).
#	ticket (X)	type	price	wing (Y)	level	time
1clash	T08	Member	0	East	L2	09:10
2	T03	Adult	22	East	L2	09:14
3	T01	Adult	22	West	L0	09:17
4clash	T08	Member	0	West	L0	09:18
5	T01	Adult	22	East	L2	09:57
6	T08	Member	0	North	L1	09:59
7	T01	Adult	22	West	L0	10:02
8	T02	Adult	22	West	L0	10:25
9	T05	Adult	22	West	L0	10:41
10	T04	Member	0	West	L0	10:53
11	T02	Adult	22	West	L0	11:08
12	T04	Member	0	East	L2	11:12
13	T04	Member	0	North	L1	11:54
14	T06	Adult	22	East	L2	12:10
15	T07	Adult	22	North	L1	12:38
16	T06	Adult	22	West	L0	12:43

Split the table along the rules

Broken. Rows 1 and 4 agree on ticket (T08) but differ on wing: East against West. The closure does not contain wing, so the rules do not promise this.

Scans come from a seeded generator that obeys the four declared rules, so any break you find is a dependency nobody promised.

The default asks whether ticket determines wing. The data breaks it, because a ticket visits several wings, and the closure of ticket holds only ticket, type and price.
Add time to the left side. Ticket and time together determine the wing, the closure reaches every column, and the pair is a key.
Try price determines type. At 16 rows it holds. Drag the rows to 24, and a Child ticket and a Member ticket turn out to cost the same 0. Type determines price, and the reverse was never a rule.
Try time determines ticket. Up to 32 rows every scan falls on a different minute, so the sample cannot refute it. At 40 rows several minutes are shared. A sample can break a dependency and never prove one.
Tick the split. Three declared rules have a left side that is not a key, and splitting on them stores fewer cells and keeps the Adult price in one row.

Where I used it

INFO20003 · COMP90050

In INFO20003 in 2020 I designed an entity-relationship model for a Louvre ticketing and visitor database, an individual assignment, in a subject that taught dependencies and normal forms alongside ER modelling. When I revived it in 2026 as Louvre Ops DB, I replayed five years of synthetic activity into the 2020 tables, and several of the design review's twelve findings are dependency problems. The Wings table was keyed by the wing's name alone, which claims that the name determines every other column in the row, so it could hold 3 of 19,545 wing visits. The Entrance key could not record a visitor re-entering through the same gate, which the brief allowed. A Business Day flag repeated what the date already says, and a stored visitor count copied rows that a query could compute. The refined schema gives wing scans and entries their own keyed tables.

COMP90050 Advanced Database Systems in 2023 picked up where schema design stops. Our group survey covered self-driving databases, and I co-wrote its index-selection half. In its 2026 revival, Self-Driving DB Lab, the Louvre database from INFO20003 ships as a second dataset with a museum workload, so the same schema meets the index advisors.

Easy to get wrong

Five traps

Reading dependencies off the data. A sample can refute $X \to Y$ but never establish it, as time and ticket show above. Dependencies come from what the columns mean, so ask the people who know the rules.
Reading a dependency backwards. Type determines price. Price does not determine type, and a design that assumes it will merge every free ticket into one.
Choosing a key that claims too much. A key says that two rows can never share its values. Before declaring one, ask whether two real events could, as two visits to the same wing obviously can.
Splitting without checking the join. A decomposition whose shared columns are not a key of either side produces extra rows when joined back. Check it is lossless before you drop the wide table.
Treating normalisation as the last word. Read-heavy reporting tables are often denormalised on purpose. That is a trade for speed, and it is safest when the duplicates are derived from a normalised source rather than typed in twice.

Sources

A relational model of data for large shared data banksCodd, Communications of the ACM 13(6), 1970, pp. 377–387.The paper that started relational databases, including the first discussion of normalising relations.
A simple guide to five normal forms in relational database theoryKent, Communications of the ACM 26(2), 1983, pp. 120–125.Short and plain, with one example per normal form. Still the quickest way to see what each form forbids.
Database Management SystemsRamakrishnan and Gehrke, 3rd edition, McGraw-Hill, 2003. Chapter 19.A standard textbook chapter on schema refinement: closures, keys, BCNF and 3NF, and lossless, dependency-preserving decompositions.