Consider the relation R(A, satisfies the following FDs: B→A D→A
Consider the relation R(A, B, D) that satisfies the following FDs:
B→A
D→A
AB→D
What is the canonical cover for the FD set?
- A.
B→A, D→A, B→D
- B.
B→D, D→A
- C.
B→A, B→D
- D.
none of the above
Attempted by 142 students.
Show answer & explanation
Correct answer: B
Concept: A canonical (minimal) cover of a set of functional dependencies F is an equivalent set Fc in which every dependency has a single attribute on its right-hand side, no dependency has an extraneous left-hand-side attribute, and no dependency is itself implied by the others. Two closure tests build it: to check if a left-hand-side attribute is extraneous, compute the closure of the remaining left-hand-side attribute(s) under the COMPLETE original F — if that closure already contains the right-hand-side attribute, the dropped attribute was extraneous. To check if an entire dependency X→Y is redundant, compute the closure of X using every OTHER dependency in the set (excluding X→Y itself) — if that closure already contains Y, the dependency is redundant.
Application: Apply both tests to F = {B→A, D→A, AB→D}.
Every right-hand side (A, A, D) is already a single attribute, so this requirement is already met.
Extraneous-attribute test on AB→D: compute B+ using the complete original F, not a reduced set. Applying B→A gives B+ = {A, B}. Since AB ⊆ {A, B}, applying AB→D adds D, giving B+ = {A, B, D}. Because D is already reachable from B alone, A is extraneous in AB→D, and the dependency can be replaced by B→D.
This is exactly the step the reported concern is about: B→A does not replace AB→D — both B→A and AB→D are applied together, from the original F, purely to compute B's closure. That closure containing D is what licenses dropping A from the left-hand side; AB→D itself is never discarded until this closure test justifies it.
The working set is now F' = {B→A, D→A, B→D}. Redundancy test on B→A: compute B+ using only the other two dependencies, {D→A, B→D}. Applying B→D gives {B, D}; applying D→A then gives {A, B, D}. A is reachable without using B→A, so B→A is redundant and is removed.
Redundancy test on D→A: compute D+ using only the remaining dependency, {B→D}. No dependency has D on its left-hand side, so D+ stays {D} — A is not reachable, so D→A is NOT redundant and must stay.
Redundancy test on B→D: compute B+ using only {D→A}. No dependency has B on its left-hand side, so B+ stays {B} — D is not reachable, so B→D is NOT redundant and must stay.
Cross-check: The redundancy tests above already guarantee equivalence — the only dependency removed, B→A, was shown to be implied by the two that were kept, and each retained dependency was shown to be necessary, so no information was lost. As a spot check, B's closure under the reduced set — apply B→D to get {B, D}, then D→A to get {A, B, D} — matches B+ computed under the original F in step 2.
Canonical cover: {B→D, D→A}