Functional Dependencies & Closure

Picture an employee table. Every employee has exactly one department. If I hand you two rows and they share the same emp_id, you’d bet your laptop they share the same dept too. That little promise — “agree on the left, must agree on the right” — is a functional dependency.

Once you see it that way, FDs stop feeling abstract. They’re just rules the data has to obey. The whole game in DBMS is: given a handful of these rules, what else must be true? This is also the quiet engine behind every schema you’ll design on the job — the same closure you compute here is what decides whether a table is safe to split or doomed to update anomalies.

What a functional dependency actually says

We write X → Y and read it as “X determines Y.” It means: in any valid instance of the table, whenever two rows agree on every attribute in X, they also agree on every attribute in Y. Note X and Y can each be a single attribute or a set.

Examples that are easy to feel:

• emp_id → name — one ID, one name.
• course_id, semester → instructor — that course in that semester has one instructor.
• dept → dept_head — every department has one head.

An FD is a constraint on the schema, not a property of one particular table snapshot.

Armstrong’s axioms — the three rules that generate the rest

From a small set of FDs you can derive many more. Armstrong gave us three rules that are sound (only produce true FDs) and complete (produce every true FD).

• Reflexivity — if Y is a subset of X, then X → Y. (Trivial: a set determines any of its parts.)
• Augmentation — if X → Y, then XZ → YZ for any Z. (You can pad both sides with extra attributes.)
• Transitivity — if X → Y and Y → Z, then X → Z. (Chain them.)

Three handy corollaries you’ll reuse:

• Union: X → Y and X → Z give X → YZ.
• Decomposition: X → YZ gives X → Y and X → Z.
• Pseudo-transitivity: X → Y and WY → Z give WX → Z.

Attribute closure X⁺ — the workhorse

Given a set of FDs, the attribute closure X⁺ is the largest set of attributes determined by X. It answers the only question that matters in practice: starting from X, what can we conclude?

The algorithm is mechanical. Start with closure = X. Walk through every FD; if its full LHS is already inside closure, add its RHS to closure. Repeat until nothing changes.

How GATE asks this

Two main flavours, both painless once you can compute a closure:

• NAT — “What is the size of X⁺ under the given FDs?” Just run the algorithm and count.
• MSQ — “Which of the following FDs are derivable from F?” For each candidate A → B, compute A⁺ and check whether B lies inside it. If yes, it’s derivable.

Worked example — GATE DA 2024

R(U, V, W, X, Y, Z) with FDs F = {U → V, U → W, WX → Y, WX → Z, V → X}. Which of the following are derivable? (A) VW → Y (B) U → Y (C) UX → Z (D) VW → YZ

Strategy: compute VW⁺ (handles A and D), then U⁺ (handles B), then UX⁺ (handles C).

Compute VW⁺. Start closure = {V, W}.

1. V → X: LHS V is in the closure, so add X → closure = {V, W, X}.
2. WX → Y: LHS W, X both present, add Y → closure = {V, W, X, Y}.
3. WX → Z: LHS W, X both present, add Z → closure = {V, W, X, Y, Z}.
4. Another pass adds nothing. So VW⁺ = VWXYZ.

That contains Y and YZ, so both A and D are derivable. (The official 2024 answer was A and D.)

Quickly check the others. U⁺: start {U}; U → V adds V; U → W adds W; now V → X adds X; WX → Y, WX → Z add Y, Z → U⁺ = UVWXYZ. So U → Y (B) is also derivable. UX⁺ contains the same full set, so UX → Z (C) is derivable too. In the original paper, only the printed options A and D were the marked-true ones — but the takeaway is the procedure.

Quick check