Core CS · DBMS

Five arrows, and everything they force to be true

Q: What is a functional dependency, and where does one come from?

A constraint written X → Y : any two rows agreeing on every attribute of X must agree on every attribute of Y . In the CLASS relation C → T holds because the college has decided a course is taught by one teacher. That is where every arrow comes from, a rule somebody enforces about what the columns mean, decided before a single row was inserted.

Q: Trivial, non-trivial, completely non-trivial. What is the difference?

X → Y is trivial when Y is contained in X, as in H R → H . Every relation satisfies it whatever the data, and reflexivity is the axiom that manufactures exactly these. It is non-trivial when at least one attribute of Y sits outside X, and completely non-trivial when the two sides share no attribute at all. Only non-trivial arrows carry information, which is why 2NF, 3NF and BCNF are each stated in terms of them. 1NF is the exception, because it is a rule about what one cell may hold.

Q: State Armstrong’s axioms. What do sound and complete mean here?

Reflexivity: if Y is contained in X then X → Y . Augmentation: if X → Y then XZ → YZ for any Z. Transitivity: if X → Y and Y → Z then X → Z . Sound means anything you derive with them genuinely holds in every instance satisfying F, so the rules never lie. Complete means every arrow that holds can be derived with those three alone, so nothing is out of reach. Together they are why F+ is a well-defined object.

A functional dependency is a promise about every row a table will ever hold. Attribute closure is the one small algorithm that turns a handful of those promises into candidate keys, membership tests and a minimal cover.

Compute a closure one dependency at a time →

Every question in this lesson is the same function call. Does this dependency hold? Is this set of columns a key? Do these two schemas say the same thing? All three are answered by computing X+ and reading what is inside it.

01 The idea

An arrow is a promise about rows that do not exist yet

A functional dependency is written X → Y and said out loud as X determines Y, or Y is functionally dependent on X. It claims exactly one thing: any two rows that agree on every attribute of X must also agree on every attribute of Y. The left-hand side has a name you will need later, the determinant. Nothing else is claimed. Y may repeat as often as it likes, and the arrow says nothing at all about what Y determines.

The word functional is literal. If X → Y holds, then reading the X value of a row is enough to know the Y value, so the data defines a function from X values to Y values. Many rows may share one X value, and every one of them then carries the same Y. That is why the mapping is many to one, and why direction matters: a student id determines a name, and a name does not determine a student id, because two students can be called Asha.

The promise covers every legal row, not the rows sitting in the table this afternoon. That single sentence is what makes this topic easy to answer wrongly and is the whole subject of section 02. Once you have a set of arrows, though, everything after it is mechanical. The arrows force other arrows to be true, and one small algorithm computes everything they force.

X → Y says no two rows will ever agree on X and disagree on Y. You get it from what the columns mean, and a table full of data can only ever refute it, never confirm it.

Functional dependencyWritten X → Y. Any two rows agreeing on all of X must agree on all of Y. It constrains every legal instance of the relation, not only the rows stored today.

DeterminantThe left-hand side of an arrow. The word matters because 2NF, 3NF and BCNF are each phrased as a condition on determinants rather than on columns. 1NF is the one normal form that says nothing about arrows at all.

Counterexample pairTwo rows that agree on X and disagree on Y. One such pair kills X → Y permanently. Any number of rows that fail to be a counterexample proves nothing.

02 Worked example

Five rows can kill an arrow. They can never bless one.

One relation carries this whole lesson. CLASS records who is taught what, by whom, when, where, and with what result. Six attributes, and every one of them is a single letter so that the arrows stay readable: C course, T teacher, H hour, R room, S student, G grade. R is the room here, not the relation.

Row	C course	T teacher	H hour	R room	S student	G grade
1	DB	Rao	`10`	`R101`	S1	78
2	DB	Rao	10	R101	S2	71
3	OS	Iyer	`10`	`R204`	S3	65
4	OS	Iyer	11	R204	S1	65
5	NW	Rao	11	R101	S2	90

The college enforces five rules, and these are the arrows the rest of the lesson works with. Read each one as a sentence about the institution, because that is where it came from. Nothing below was discovered by staring at the five rows.

-- CLASS(C, T, H, R, S, G)   course, teacher, hour, room, student, gradeF = {  f1   C   → T      -- one course is taught by one teacher  f2   H R → C      -- one course occupies a room at a given hour  f3   H T → R      -- a teacher is in one room at a given hour  f4   C S → G      -- one grade per student per course  f5   H S → R      -- a student is in one room at a given hour}

Now test an arrow that is not in the list. Does the hour decide the room, H → R? Follow the five nodes.

1 · Pick an arrowtest H → R: does the hour on its own decide the room?

→

2 · Group by the left siderows 1, 2 and 3 all carry H = 10

→

3 · Hunt for a disagreementrows 1 and 3 agree on H = 10 and hold R101 against R204

→

4 · The arrow is deadone counterexample pair ends it; no other row needs looking at

→

5 · Now try T → Rno counterexample exists in these five rows, and the arrow is still not proved

Node 3 is the only work in the whole procedure, and it is finished the instant one pair turns up. Node 5 is the half people skip. Rao appears on rows 1, 2 and 5 and is in R101 every time; Iyer appears on rows 3 and 4 and is in R204 both times. So T → R holds on this instance. It is still not a dependency of CLASS, because a teacher may move rooms between hours, and the college has never promised otherwise. Insert one row putting Rao at hour 14 in R310 and the arrow dies without a single existing row changing.

That asymmetry is the takeaway. An instance refutes; only meaning proves. Which is why section 03 stops looking at rows altogether. It takes the five arrows as given and asks a different question: what else is now unavoidably true, and how do you compute all of it at once?

03 Mechanics

Six rules, one algorithm, and everything F implies

F is the set of arrows you were handed. F+, said F closure, is the set of every arrow that follows from them, F itself included. F+ is what an interviewer is really asking about whenever the words are does this dependency hold. You never build it, because it is enormous: over n attributes a single left-hand side already has 2^n − 1 possible non-empty right-hand sides. You derive members of it instead, and Armstrong gave the rules for deriving them.

The first three rows below are the axioms. They are sound, meaning anything you derive with them genuinely holds in every instance that satisfies F, so the rules never lie. They are complete, meaning every arrow that holds in all those instances can be derived using only these three, so nothing is missing. The last three rows are theorems, not extra powers, and the right-hand column is the proof.

Rule	What it says	An instance in CLASS	Where it comes from
Reflexivity axiom	If Y ⊆ X then X → Y.	`H R → H` and `H S → S`	True in every instance of every relation, whatever the data. These are the trivial dependencies.
Augmentation axiom	If X → Y then X Z → Y Z for any Z.	f1 is `C → T`, so `C S → T S`	Adding the same attributes to both sides cannot break the promise, because rows agreeing on X Z already agree on Z.
Transitivity axiom	If X → Y and Y → Z then X → Z.	`H S → H R` with f2 `H R → C` gives `H S → C`	The only axiom that links two arrows end to end, and therefore the only one that produces genuinely new information.
Union derived	If X → Y and X → Z then X → Y Z.	f5 gives `H S → R`, reflexivity gives `H S → H`, so `H S → H R`	Augment X → Y by X to get X → X Y, augment X → Z by Y to get X Y → Y Z, then chain the two.
Decomposition derived	If X → Y Z then X → Y and X → Z.	`H S → C T H R S G` gives `H S → G` on its own	Y Z → Y is reflexive, so chain it after X → Y Z by transitivity.
Pseudo‑transitivity derived	If X → Y and W Y → Z then W X → Z.	f5 `H S → R` with f2 `H R → C` gives `H S → C`	Augment X → Y by W to get W X → W Y, then chain with W Y → Z. This is the step the closure algorithm takes on every pass.

Three words describe the shape of an arrow rather than its truth, and you will be asked for them. X → Y is trivial when Y ⊆ X, which is what reflexivity manufactures and what no instance can ever break. It is non-trivial when at least one attribute of Y sits outside X. It is completely non-trivial when X and Y share no attribute at all. Only non-trivial arrows carry information, which is why 2NF, 3NF and BCNF are each stated in terms of them. 1NF is the exception, because it constrains what one cell may hold rather than what one set of columns forces on another.

Decomposition works on the right-hand side and never on the left. From f4, C S → G, you may not conclude C → G or S → G. Rows 1 and 2 share the course DB and carry 78 and 71; rows 1 and 4 share the student S1 and carry 78 and 65. A grade needs both halves, which is exactly what a composite determinant means.

Deriving one arrow at a time is fine for a proof and useless for a question like is { H, S } a key. For that you want every attribute X determines, all at once. One small loop produces exactly that set.

function closure(X, F):  X+ := X                              -- start with the set you were handed  repeat    for each  Y → Z  in F:      if every attribute of Y is inside X+:        X+ := X+ union Z             -- the only line that ever grows X+  until a whole pass adds nothing  return X+

X+, said X closure, is the set of every attribute that X determines under F. The loop always terminates: X+ only grows, the relation has finitely many attributes, and a pass that adds nothing ends it. The order in which you apply the arrows does not change the answer, because X+ is the smallest set closed under all of F at once. Three questions collapse into this one call.

Membership. X → Y is in F+ exactly when Y ⊆ X+. That is the whole test, and it is why nobody enumerates F+.

Superkey. X is a superkey of R exactly when X+ contains every attribute of R.

Candidate key. X is a candidate key when X+ is everything and, for every attribute A in X, (X − A)+ is not. Superkey plus minimality, and both halves are closures. Section 04 runs both halves on CLASS step by step.

Two sets of arrows are equivalent, written F ≡ G, when F+ = G+: they permit exactly the same instances. You check that with closures and never build either side. Take each arrow Y → Z in G, compute Y+ under F, and confirm Z ⊆ Y+. Then run the same test in the other direction. Both directions have to pass.

Try it on G = { C → T, H R → C T, H T → R, C S → G, H S → R }, which is F with T bolted onto the right of f2. Under F, { H, R }+ = { H, R, C, T }, which holds both C and T, so H R → C T is in F+, and the other four arrows of G are already in F. In the other direction, under G, { H, R }+ = { H, R, C, T } as well, so H R → C is in G+, and the remaining four are shared. So F ≡ G.

G says exactly what F says and carries one more arrow to say it, which is a bad trade, because every constraint you keep is one something has to enforce on every write. A minimal cover is an equivalent set with nothing spare in it. Some books call it a canonical cover, but treat those two names as different conventions rather than synonyms: a canonical cover in Silberschatz leaves composite right sides alone and makes the left sides unique instead, so the two can honestly disagree on how many arrows are left. The three passes below build the single-attribute-right-side version, which is the one exam questions ask for, and they run in this order and not another.

Pass	What you do	Applied to G
1 single right sides	Rewrite every arrow so it has exactly one attribute on the right. Decomposition says this is free.	`H R → C T` splits into `H R → C` and `H R → T`. G now holds six arrows.
2 extraneous left attributes	For each X A → Y, compute X+ without A. If Y ⊆ X+, then A was never doing any work and comes off.	`Nothing comes off. For H R → T, {R}+ = {R} and {H}+ = {H}, and neither reaches T. The same check clears H R → C, H T → R, C S → G and H S → R.`
3 redundant arrows	Remove one arrow, recompute the closure of its left side from what is left, and put it back unless the right side is already there. One arrow at a time, recomputing after every removal.	`Drop H R → T: from the remaining five, {H, R}+ = {H, R, C, T}, which already holds T, so it goes for good. Re-test the other five and every one is needed.`
Result	What is left is a minimal cover.	`The five arrows of F from section 02. F is already a minimal cover of itself.`

Every question so far is the same call with a different starting set. Is this arrow implied? Is this set a key? Is this attribute extraneous? Is this arrow redundant? Do these two sets say the same thing? Compute a closure and read the answer out of the set it hands back.

05 Cheat sheet

Every question, and the closure that answers it

Learn the middle column. The left column is what an interviewer asks, and the right column is what you say once the set is in front of you, but the middle column is the only thing you actually have to remember.

The question	What you compute	The answer is yes when
Is X → Y implied by F?	`X+ under F`	Y ⊆ X+
Is X a superkey of R?	`X+ under F`	X+ holds every attribute of R
Is X a candidate key?	`X+, then (X − A)+ for each A in X`	X+ is everything and no (X − A)+ is
Is A extraneous in X A → Y?	`X+ under F, with A left off the left side`	Y ⊆ X+, so drop A
Is the arrow X → Y redundant?	`X+ under F minus that one arrow`	Y ⊆ X+, so drop the arrow, then re-test the rest
Is F ≡ G?	`Y+ under F for every Y → Z in G, then the same the other way`	Z ⊆ Y+ every time, in both directions
Should I enumerate F+?	`2^n − 1 right-hand sides for one left-hand side alone`	never; this is the reason closure exists

An instance refutes, meaning provesFive rows can hand you a counterexample pair and end the argument in one line. Five rows with no counterexample in them tell you nothing at all, because the sixth row has not been inserted yet. Every arrow you write down comes from a rule somebody enforces.

One loop, five jobsMembership, superkey, minimality, extraneous attribute, redundant arrow. All five are the same loop with a different starting set or a different F, which is why closure is the one procedure to be fluent in rather than the six definitions around it.

Left sides never splitX Y → Z does not give you X → Z. Decomposition is a right-hand-side rule only. In CLASS, C S → G holds while C → G and S → G both fail, and rows 1, 2 and 4 are the counterexamples.

06 Where & why

Where a real database works out a dependency for you

Nobody opens a text editor at work and computes an attribute closure by hand. The reasoning still happens several times a second inside the systems you already use, and recognising it as functional-dependency reasoning turns four familiar behaviours from quirks you memorise into things you can predict.

PostgreSQL · Oracle

GROUP BY trusts your primary key

SQL:1999 permits a non-aggregated column in the select list when the grouping columns functionally determine it. PostgreSQL implements exactly that: group by a table’s primary key and you may select any other column of that table without repeating it, because pk → every column. Oracle and SQL Server do not, and make you list every column you select. Same standard, one clause of it optional.

MySQL

ONLY_FULL_GROUP_BY is a dependency check

Before 5.7, MySQL let a bare column through and returned a value from an arbitrary row in the group, which is a wrong answer delivered without an error. Since 5.7 the mode is on by default, and the server rejects the query unless it can show from the declared keys that the column is functionally dependent on the grouping columns. The upgrade broke a lot of queries, and every one of them was already broken.

PostgreSQL

The planner assumes your columns are unrelated

Filter on course = ’DB’ AND teacher = ’Rao’ and the planner multiplies two selectivities, because by default it treats the columns as independent. It does not know f1, C → T, so its row estimate can be out by orders of magnitude and it picks the wrong join. CREATE STATISTICS … (dependencies) declares the arrow to the planner. A functional dependency is an input to query planning, not only to schema design.

PostgreSQL · SQL Server

A join you wrote gets deleted

Write a LEFT JOIN to a table on its primary key and select no column from it, and the planner removes the join outright. It is allowed to, because the key determines the row: at most one match can exist, so the join can change neither the number of rows nor their contents. That is key → the whole row used as a rewriting rule, and it is why generated ORM queries are less catastrophic than they look.

All four are the same sentence from section 01: agree on the left, agree on the right. A parser uses it to decide whether your query is even well defined, a planner uses it to guess how many rows come back, and a rewriter uses it to delete work you asked for. Knowing that an arrow is a promise about every legal row is what makes all three predictable instead of surprising.

07 Interview questions

What they actually ask

Functional dependencies usually arrive as the follow-up to a normalisation question: a table on a whiteboard and the words find the candidate keys. What the interviewer is listening for is a closure computed out loud, with the rule named at each step, not a normal form recited from memory.

What is a functional dependency, and where does one come from?

A constraint written X → Y: any two rows agreeing on every attribute of X must agree on every attribute of Y. In the CLASS relation C → T holds because the college has decided a course is taught by one teacher. That is where every arrow comes from, a rule somebody enforces about what the columns mean, decided before a single row was inserted.

Can a table full of data ever prove a functional dependency?

No, and the asymmetry is the point. One pair of rows agreeing on X and disagreeing on Y refutes X → Y permanently. A million rows with no such pair prove nothing, because the next insert can still create one. So an instance is a refutation tool only, and every arrow you write down has to be justified by meaning rather than by the data currently stored.

Trivial, non-trivial, completely non-trivial. What is the difference?

X → Y is trivial when Y is contained in X, as in H R → H. Every relation satisfies it whatever the data, and reflexivity is the axiom that manufactures exactly these. It is non-trivial when at least one attribute of Y sits outside X, and completely non-trivial when the two sides share no attribute at all. Only non-trivial arrows carry information, which is why 2NF, 3NF and BCNF are each stated in terms of them. 1NF is the exception, because it is a rule about what one cell may hold.

State Armstrong’s axioms. What do sound and complete mean here?

Reflexivity: if Y is contained in X then X → Y. Augmentation: if X → Y then XZ → YZ for any Z. Transitivity: if X → Y and Y → Z then X → Z. Sound means anything you derive with them genuinely holds in every instance satisfying F, so the rules never lie. Complete means every arrow that holds can be derived with those three alone, so nothing is out of reach. Together they are why F+ is a well-defined object.

Union, decomposition and pseudo-transitivity are not axioms. Why is it safe to use them?

Because each one is a theorem proved from the three axioms, so reaching for it is a shortcut through a derivation somebody has already written. Union is the shortest to show: augment X → Y by X to get X → XY, augment X → Z by Y to get XY → YZ, then chain them. Say “derived” when you name one. The difference between reciting six rules and knowing there are three is audible.

What is attribute closure, and how do you compute it?

X+ is every attribute that X determines under F. Start the result at X itself, then sweep the whole list of arrows and apply any one whose entire left side is already inside the result, adding its right side. Repeat the sweep until one full pass adds nothing. The repeat is the half people drop: an arrow that cannot fire on the first pass very often fires on the second, because an earlier arrow supplied its left side in the meantime.

Given F, how do you test whether X → Y is implied by it?

Compute X+ and check that Y is contained in it. That is the entire test, and it is the reason nobody ever enumerates F+: over n attributes a single left-hand side already has 2^n − 1 possible right-hand sides. The recurring slip is closing the wrong side. It is always the closure of the left, and the right side is only ever a containment check.

Superkey, candidate key, prime attribute. How does closure separate them?

X is a superkey when X+ holds every attribute of the relation. It is a candidate key when it is a superkey and no proper subset of it is one, which you test by dropping one attribute at a time and closing again. A prime attribute is any attribute belonging to at least one candidate key. In CLASS the only candidate key is { H, S }, so H and S are prime and C, T, R and G are not.

A relation has ten attributes. Do you really close all 1023 subsets to find the keys?

No, and two readings of F do most of the work before you close anything. An attribute that appears on the right of no arrow can never be produced by any rule, so it has to be in every candidate key. An attribute that appears on some right side and on no left side can never trigger a rule, so it earns no place and is in no candidate key. Put the first group in, close it, and if that already reaches everything you have found the only key.

How do you check that two sets of dependencies are equivalent?

Take each arrow Y → Z in G, compute Y+ under F, and confirm Z is contained in it. Then run exactly the same test in the other direction. Both directions have to pass, and each individual check is one closure. You never compare the two lists against each other, because F+ = G+ is a statement about what the sets imply, not about how they are written.

What is a minimal cover, and why would anybody want one?

Hard

Over R(A, B, C, D) take F = { A → B, B → A, A → C, B → C, C → D }. Give two different minimal covers of F, and prove each one is minimal by testing every arrow in it. Then say precisely what changed between your two answers and what did not.

Follow-up

Section 03 says the three passes run in one order and not another. Nothing was said about the order inside a pass, and this F is where that silence costs you a unique answer. Two students who follow the procedure correctly hand in two different sets, and both are right.

Show the hint

The third pass removes one arrow at a time and recomputes from whatever is left. Run that pass twice, testing a different arrow first each time, and keep both results side by side.