函数依赖中的反身性

Question

我正在 class 学习数据库，并且正在做一个关于函数依赖的作业。作为使用阿姆斯特朗公理获取给定依赖关系并推导其他重要依赖关系的示例，助教写了这篇文章，我无法理解它。

考虑关系 R(c,p,h,s,e,n) 和 F 函数依赖集 {1. c->p, 2. hs->c, 3. hp->s, 4. ce->n, 5. he->s}:

迭代 1：

从 F 开始，我们可以构建 F1

6. hs->p (transitivity: 1+2)
7. hc->s (pseudo-transitive. 1+3)
8. hp->c
  1. hp->hs (reflexivity 3)
  2. hp->c (transitivity: 8.1+2)
9. he->c
  1. he->hs (reflexivity: 4)
  2. he->c (transitivity: 9.1+2)

除了使用 'reflexivity' 的情况（使用引号因为这与我的教科书中的自反性定义相去甚远）外，我大部分都理解得很好。谁能告诉我这是反身性吗？另外，我怎么知道迭代何时结束？难道你找不到无数种方法来重写函数依赖吗？

Answer 1

除了某人决定给某物起的名字，名字什么也告诉不了你。

Trivial FD X -> X 与 X 中的属性存在任何关系。即关系中的一组属性在功能上决定了自身。这被合理地称为自反。碰巧它在功能上决定了自身的每个子集。碰巧 "reflexivity" 被选为更通用规则的名称，而更通用的规则被选为一组足够但 non-redundant 规则中的一个。

阿姆斯特朗的公理已被证明是可靠和完整的。声音意味着它们只生成隐含的 FD。完全意味着如果你继续应用公理直到你没有通过应用任何新的 FD 获得任何新的 FD，那么你将获得所有可以从原始集合派生的 FD，即当原始的 FD 成立时也必须成立。任何教科书都告诉你，你可以通过这样做来生成一组 FD 的传递闭包。

FD + MVD 也有完善的公理集。但是没有 FDs + JDs。

Answer 2

这些是经典的阿姆斯特朗公理（例如 wikipedia）：

Reflexivity: If Y ⊆ X then X → Y
Augmentation: If X → Y then XZ → YZ for any Z
Transitivity: If X → Y and Y → Z, then X → Z

因此，在您的示例中，要导出 hp → c，您可以按以下方式进行：

1. hp → s (given)
2. hp → hs (by augmentation of 1 adding h)
3. hs → c (given)
4. hp → c (by transitivity of 2 + 3)

请注意，要从 hp → s 生成 hp → hs，要使用的公理是增广，其中 Z 的角色由 h 承担，而不是自反性，这也是用于推导 he → c 的公理（通过自反性，您只能推导例如 hp → hp、hp → p、hp → h）。

你也在问：

How do I know when an iteration is over? Couldn't you find an infinity of ways to rewrite functional dependencies?

阿姆斯特朗公理只能应用于一组函数依赖性有限次数，以产生新的函数依赖性。这很容易显示，因为属性的数量是有限的，并且给定 n 个属性，您最多可以拥有 2ⁿ * 2ⁿ 不同的函数依赖（因为你可以在左边和右边都有属性的任何子集，当然包括琐碎的依赖项）。

函数依赖中的反身性

Reflexivity in functional dependencies

database

database-normalization

functional-dependencies