Functional Dependency

📘 Learn Functional Dependency from zero

Start from zero. A functional dependency is a rule that says: "if you know the value of one column (or set of columns), you automatically know the value of another." We write it X → Y, read "X determines Y." Precisely: in any legal table, any two rows that agree on all of X must agree on all of Y.

Analogy — a vending machine. Press a button code (X) and you always get the same snack (Y). B4 today gives pretzels; B4 tomorrow still pretzels. The code functionally determines the snack. The reverse fails — pretzels might also come from B7 — so Snack → Code does not hold. That one-directional "same input ⟹ same output" is exactly a function, hence functional dependency.

Worked example. Table Student(RollNo, Name, Dept, DeptHead). Real-world semantics: each roll number is one student in one department; each department has one head. So:

• RollNo → Name (one roll number names one student)
• RollNo → Dept
• Dept → DeptHead (one head per department)

Does RollNo → DeptHead hold? Yes — RollNo fixes Dept and Dept fixes DeptHead, so the dependency chains. This is transitivity, one of Armstrong's three primary inference rules: reflexivity (if Y ⊆ X then X → Y — these are the trivial FDs), augmentation (if X → Y then XZ → YZ), and transitivity (if X → Y and Y → Z then X → Z). These axioms are sound (derive only valid FDs) and complete (derive all valid FDs); the handy secondary rules — union, decomposition, pseudotransitivity — follow from them. By contrast Dept → RollNo fails: one department has many students, so the determinant does not pin down one roll number.

Key insight: a functional dependency is a semantic promise about the real world — "same left side forces same right side, for every possible row" — not a coincidence in today's data. Keys, the FD taxonomy (trivial vs. non-trivial; full vs. partial; transitive), and all of normalization are built on this one idea.

✨ Added by the guide to build intuition — not from the source course.

🎯 Guided practice

1. Easy — verify an FD against a table. Relation R(A, B, C) with rows (1, x, true), (2, y, false), (1, x, true), (3, x, false). Does A → B hold? Does B → C hold?

   Reasoning (core pattern: group by the determinant, check the dependent). For A → B: group by A. A=1 appears twice, both with B=x — consistent; A=2→y and A=3→x are singletons. No two rows share A yet differ on B, so A → B holds (for this instance). For B → C: group by B. B=x appears in rows 1, 3, 4 with C = true, true, false — same B, different C. That is a counterexample, so B → C does not hold. Caveat: a single instance can only refute an FD or fail to refute it; it can never prove one holds for all legal instances — that comes from semantics. Pattern: an FD is violated the instant you find two rows equal on the left and unequal on the right.

2. Medium — find a candidate key via attribute closure. R(A, B, C, D, E) with F = { A → B, B → C, CD → E, E → A }. Is {C, D} a candidate key?

   Reasoning (core pattern: compute the closure X⁺, then check minimality). Initialize {C,D}⁺ = {C, D}. Repeatedly apply any FD whose entire left side is already in the set: CD → E ⟹ add E → {C,D,E}; E → A ⟹ add A → {A,C,D,E}; A → B ⟹ add B → {A,B,C,D,E}; B → C adds nothing. Closure = all five attributes, so {C,D} is a superkey. Now check minimality: is any proper subset already a superkey? {C}⁺ = {C} (no FD fires without D), {D}⁺ = {D}. Neither single attribute determines everything, so {C,D} is irreducible — therefore a candidate key. Pattern: X is a candidate key iff X⁺ = all attributes AND no proper subset has that property. (This same closure also answers "does X → Y follow from F?" — yes iff Y ⊆ X⁺, which is why we never enumerate the exponential F⁺.)

✨ Added by the guide — work these before the full problem set.