Functional Dependency in DBMS: Closure, Keys, Cover

A functional dependency (FD) is a rule of the form "if you know this, you know that": a roll number fixes a student's name, a course code fixes its title, a PIN code fixes its post office. Functional dependencies are the mathematics underneath keys and normalization. Every normal form is defined with them, and every "find the candidate keys" or "is this relation in BCNF" question is answered by computing with them. This note covers the definition, Armstrong's axioms, attribute closure, finding all candidate keys and computing a canonical cover, each worked by hand.

What a functional dependency is

For attribute sets X and Y of a relation R, X → Y ("X functionally determines Y", or "Y is functionally dependent on X") holds if any two rows that have the same values for X also have the same values for Y. X is the determinant (left-hand side) and Y the dependent (right-hand side).

An FD is a rule about every state the table is allowed to be in, which comes from the meaning of the data. An instance can only disprove one:

1. roll_no → name: the rows that agree on roll_no also agree on name. The rows are consistent with it, and the college's rules say it always holds.
2. name → roll_no is not a dependency: rows 1 and 4 agree on name (Asha) but differ on roll_no. One such pair disproves it for good.
3. roll_no → grade is not a dependency: rows 1 and 2 agree on roll_no (101) but differ on grade. One such pair disproves it for good.
4. No two rows share a (roll_no, course_id) pair, so nothing here can contradict roll_no, course_id → grade. It holds because of the college's rule, not because of these rows.
5. course_id → grade holds in these four rows by coincidence. No rule says every student in a course gets the same grade, so the next row may break it: data can only disprove a dependency.

The last test is the trap: the data satisfies course_id → grade, but nothing in the college's rules says every student in a course gets the same grade.

FDs generalize keys. K is a super key of R exactly when K → R, that is, K determines every attribute.

Trivial and non-trivial dependencies

Trivial FDs hold in every relation, so normal-form definitions only ever test non-trivial ones.

Armstrong's axioms

Given a set F of FDs, many more follow from it. The set of all FDs implied by F is its closure, written F+. Armstrong's axioms generate F+:

They are sound (they derive only FDs that really hold) and complete (every FD that holds can be derived with them). Four derived rules save time:

Decomposition works on the right side only. From AB → C you cannot conclude A → C or B → C.

1. Augment X → Y by X to get X → XY, and X → Z by Y to get XY → YZ. The right side of the first is the left side of the second, so transitivity gives X → YZ: the union rule, built from the three axioms alone.
2. Decomposition splits a right side, never a left one. These two rows satisfy AB → C, because no two rows share A and B, yet they break A → C: the same a1 gives c1 and c2.

Attribute closure

Computing F+ directly is exponential, so in practice you compute the closure of an attribute set, X+: everything X determines.

1. Set result = X.
2. For each FD Y → Z in F: if Y is entirely inside result, add Z to result.
3. Repeat step 2 until a full pass adds nothing.

Take R(A, B, C, G, H, I) with F = {A → B, A → C, CG → H, CG → I, B → H}, and compute (AG)+:

1. Start with the set itself: (AG)+ begins as {A, G}. Then go down F again and again; a dependency fires when its whole left side is already inside the set, and adds its right side.
2. A → B fires because A is inside: add B. The set is now {A, B, G}.
3. A → C fires because A is inside: add C. The set is now {A, B, C, G}.
4. CG → H fires because C and G are both inside: add H. The set is now {A, B, C, G, H}.
5. CG → I fires because C and G are both inside: add I. The set is now {A, B, C, G, H, I}.
6. B → H could fire, but H is already in the set, so it adds nothing new.
7. A second pass changes nothing, so the loop stops: (AG)+ = ABCGHI, every attribute, so AG is a super key. Neither part is: A+ = ABCH and G+ = G, so AG is a candidate key.

(AG)+ = ABCGHI, every attribute, so AG is a super key. Closure answers three questions:

• Is X a super key? Yes if X+ contains all of R.
• Does F imply X → Y? Yes if Y ⊆ X+. Does F imply B → C? B+ = {B, H}, which lacks C, so no.
• Is X a candidate key? X+ is everything and no proper subset's closure is. Here A+ = {A, B, C, H} (A → B, A → C, B → H; CG → H cannot fire without G) and G+ = {G}, so AG is a candidate key.

Finding all candidate keys

A method that never misses a key:

1. Sort the attributes. Left-only attributes (on some left side, no right side) and attributes that appear in no FD at all cannot be derived, so they belong to every key. Right-only attributes can always be derived from the rest, so they belong to no candidate key. The rest appear on both sides.
2. Compute the closure of the must-have set. If it covers R, it is the one and only candidate key.
3. Otherwise add "both" attributes to it, one at a time, then two at a time, and so on, keeping every set whose closure is R and skipping any set that contains a key already found.

Example 1. In the relation above, left-only attributes are A and G, right-only are H and I, and B and C appear on both sides. (AG)+ is everything, so AG is the only candidate key.

Example 2. R(A, B, C, D, E) with F = {A → BC, CD → E, B → D, E → A}. Every attribute appears on both sides, so no attribute is forced and we test sets by size.

Pairs containing A or E are not minimal, so only BC, BD and CD needed testing. The only triple without A or E is BCD, which contains BC. The candidate keys are A, E, BC and CD, so every attribute here is prime. That fact matters in the next note: this relation is in 3NF, but B → D has a determinant that is not a super key, so it is not in BCNF.

1. Every attribute appears on both sides of some dependency, so none is forced into the key and none is ruled out. Test sets by size: A+ = ABCDE, B+ = BD, C+ = C, D+ = D, E+ = ABCDE. A and E reach everything.
2. A pair containing A or E holds a key already, so it cannot be minimal and is skipped (dashed). Of the other three, BC and CD reach everything and BD does not.
3. Every triple contains a key found already — the only one without A or E, BCD, contains BC — so the search stops. The candidate keys are A, E, BC, CD, and every attribute is prime.

Canonical cover

Two FD sets F and G are equivalent when F+ = G+: each FD of one follows from the other (check with closures). A canonical cover Fc is the simplest set equivalent to F, which makes integrity checks cheap. Removing from a dependency an attribute that does not change F+ is called removing an extraneous attribute.

1. Split every right side into single attributes (decomposition).
2. For each FD with two or more attributes on the left, test each left attribute: in XA → B, A is extraneous if B ∈ X+ computed with all of F. Drop it if so.
3. For each FD X → B, compute X+ using F without that FD. If B is still in it, the FD is redundant; delete it.
4. Combine FDs with the same left side (union).

The set after step 3 is a minimal cover; step 4 makes it the canonical cover. Work F = {A → B, AB → C, C → D, A → D} on R(A, B, C, D):

1. Start from F. Every right side is already a single attribute, so step 1 changes nothing. Step 2 looks for extraneous attributes on left sides; only AB → C has two.
2. Is A extraneous in AB → C? Without it the left side is B, and B+ under all of F is only B, which lacks C. A stays.
3. Is B extraneous in AB → C? Without it the left side is A, and A+ under all of F is ABCD, which contains C. So B is extraneous: AB → C becomes A → C.
4. Is A → B redundant? Without it, A+ is only ACD, with no B. Nothing else implies it, so it stays.
5. Is A → C redundant? Without it, A+ is only ABD, with no C. Nothing else implies it, so it stays.
6. Is C → D redundant? Without it, C+ is only C, with no D. Nothing else implies it, so it stays.
7. Is A → D redundant? Without it, A+ is still ABCD, which contains D, so the other dependencies imply it. Delete it.
8. The minimal cover is A → B, A → C, C → D. Joining the two with left side A gives the canonical cover {A → BC, C → D}, and A+ = ABCD under it confirms every original dependency still follows.

Minimal cover: {A → B, A → C, C → D}. Canonical cover: {A → BC, C → D}. To confirm equivalence, check each original FD under the cover: A+ = ABCD, so A → B, A → D and AB → C all follow, and C → D is in it.

A minimal cover is not always unique; the order in which you test can give different, equally valid answers.

Common mistakes

• Splitting a left side: AB → C does not give A → C.
• Treating sample rows as proof of an FD: they can only disprove one.
• Stopping the closure loop after one pass: a later FD can enable an earlier one; repeat until nothing changes.
• Calling any super key a candidate key without checking that its proper subsets are not super keys.
• Testing an extraneous left attribute against F minus the FD itself: left-side tests use all of F; redundancy tests drop the FD.
• Forgetting attributes that appear in no FD: they must be part of every key.

Interview questions

Define a functional dependency. X → Y holds in R if any two tuples that agree on X also agree on Y. It is a constraint on all legal instances of R, decided from the meaning of the data.

State Armstrong's axioms and say why they matter. Reflexivity, augmentation and transitivity. They are sound and complete, so every implied dependency can be derived with them and nothing false can.

Prove the union rule. From X → Y, augmenting by X gives X → XY. From X → Z, augmenting by Y gives XY → YZ. Transitivity on the two gives X → YZ.

How do you check whether a set of attributes is a super key? Compute its closure under F. It is a super key if the closure is every attribute of the relation, and a candidate key if additionally no proper subset has that property.

R(A, B, C, D) has F = {AB → C, C → D, D → A}. What are the candidate keys? B is left-only and must be in every key, but B+ = {B}. AB+ = ABCD, CB+ = BCDA and DB+ = BDAC, so the keys are AB, BC and BD.

What is the difference between a minimal cover and a canonical cover? Both have no redundant FDs and no extraneous attributes. A minimal cover has single attributes on every right side; a canonical cover merges FDs with the same left side into one.

What is an extraneous attribute? An attribute that can be removed from a dependency without changing the closure of the set. In AB → C with A → C also implied, B is extraneous on the left.

Why do we compute attribute closure instead of F+? F+ can have exponentially many dependencies. Every practical question (is X a key, does F imply X → Y) is answered by one attribute closure, which takes time polynomial in the size of F.

Next, use these tools to design good tables: Normalization in DBMS: 1NF to BCNF. Dependencies and keys are examined in the SQL (Intermediate) skill test.