函数依赖集的等价性

Question

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

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

这两个 FD 是否等效，我认为它们是。但在答案中它显示为不等价。

Answer 1

您不能从第一组中的依赖项生成 AB → E。

为了从数学上证明它们的（不）等价性，您应该为两个集合构建闭包并比较闭包。

有一些简单的归纳规则可以构建闭包。引用 Wikipedia on Functional Dependency，公理是：

自反性：如果Y是X的子集，则X→Y
增广：如果X→Y，则XZ→YZ
传递性：如果X→Y且Y→Z，则X→Z

遵循他们的一些规则：

并集：如果X→Y且X→Z，则X→YZ
分解：如果X→YZ，则X→Y和X→Z
伪传递性：如果X→Y且WY→Z，则WX→Z
组成：如果X→Y且Z→W，则XZ→YW

使用这些规则和公理，可以为 FDS 构建闭包。

省略琐碎的依赖（右侧包含在左侧的那些），首先设置{ AB → C (1), D → E ( 2), E → C (3) } 给出：

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)

而第二组{ AB→C(1),D→E(2),E→C(3), AB → E (4) } 给出：

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)

第二个闭包有AB → E, AB → CE，第一个闭包不存在，因此原始集合不同。

函数依赖集的等价性

Equivalence of Functional dependency set

database-theory