Equivalence of Functional dependency set

Question

Fd1 = {AB --> C, D --> E, E --> C}

Fd2 = { AB --> C, D --> E, AB --> E, E --> C}

are these two FD's are equivalent or not, i think they are. But in the answer it's shown as not equivalent.

Answer 1

You cannot produce AB → E from dependencies in the first set.

To mathematically prove their (in)equivalence, you should build closures for both sets and compare the closures.

There are a few simple induction rules to build the a closure. Quoting Wikipedia on Functional Dependency, the axioms are:

• Reflexivity: If Y is a subset of X, then X → Y
• Augmentation: If X → Y, then XZ → YZ
• Transitivity: If X → Y and Y → Z, then X → Z

with by a few rules that follow from them:

• Union: If X → Y and X → Z, then X → YZ
• Decomposition: If X → YZ, then X → Y and X → Z
• Pseudotransitivity: If X → Y and WY → Z, then WX → Z
• Composition: If X → Y and Z → W, then XZ → YW

Using these rules and axioms, one can build a closure for a FDS.

Omitting trivial dependencies (the ones where right side is included into left side), first set { AB → C (1), D → E (2), E → C (3) } gives:

AB → C                       (1)
ABD → CE, ABD → C, ABD → E   (composition 1+2, decomposition)
ABDE → CE, ABDE → C          (composition 1+2+3, decomposition)
ABE → C                      (composition 1+3)
D → E, D → C, D → CE         (2, transitivity 2+3, union)
DE → CE, DE → C              (composition 2+3, decomposition)
E → C                        (3)

And the second set { AB → C (1), D → E (2), E → C (3), AB → E (4) } gives:

AB → C, AB → E, AB → CE      (1, 4, union 1+4)
ABD → CE, ABD → C, ABD → E   (composition 1+2, decomposition)
ABDE → CE, ABDE → C          (composition 1+2+3, decomposition)
ABE → C                      (composition 1+3)
D → E, D → C, D → CE         (2, transitivity 2+3, union)
DE → CE, DE → C              (composition 2+3, decomposition)
E → C                        (3)

The second closure has AB → E, AB → CE, which is not present in the first closure, therefore original sets are different.