将函数依赖投射到另一个关系上

Question

考虑 R(ABCDE) 与以下 FD 的关系：

AB -> C
BC -> D
CD -> E
DE -> A
AE -> B

将这些 FD 投影到 S(ABCD) 的关系上。以下哪个 FD 在投影关系中成立？

A -> B
A -> D
BC -> A
AC -> B

上面问题的写法是直接抄作业的

给出的正确答案是 3。

因为最后 3 个 FD 包含 E，所以我相信它们在 R(ABCD) 的投影中不成立。所以这让我 AB -> C 和 BC -> D 我不知道如何从我当前的过程中确定正确答案。

Answer 1

你的问题不清楚。我假设您要问的是关系 R(ABCD) 中最后四个依赖项中的哪一个：答案是第三个。这可以通过计算原始依赖集中 BC 的闭包来简单证明：

BC+ = BC
BC+ = BCD    (using BC → D)
BC+ = BCDE   (using CD → E)
BC+ = BCDEA  (using DE → A)

所以，BC是候选键，决定A，所以BC → A在R(ABCD)中也成立。如果您尝试计算四个依赖项的所有其他左侧的闭包，您将永远找不到右侧，因此它们在 R(ABCD).

中不成立

为什么可以通过计算行列式的闭包得到答案？

我们称 FS 原始依赖集 F 在关系 S(ABCD) 上的投影。因此，对于一组依赖项的投影的定义，我们有：

FS = { X → Y ∈ F⁺ | X,Y ⊆ ABCD }

并且问题询问某些依赖项是否属于 FS。但是由于 FS 的计算需要计算 F⁺，这是一个指数任务，我们不计算它，而是检查，对于四个依赖项 X → Y 中的每一个，它是否属于到 F⁺。这相当于计算X的闭包并判断Y是否属于它的多项式任务（我们已经知道依赖关系具有集合ABCD中的所有属性）。

所以答案是计算依赖项的所有左侧部分的闭包，看看右侧部分是否包含在其中。这仅适用于第三个依赖项。

Answer 2

"Project these FD's onto the relation S(A,B,C,D)"是草率的写法。（尽管您评论说您正在引用您的作业。）大概这是想说，如果这些 FD 在 R(ABCDE) 中成立，那么以下哪些 FD 在其对 ABCD 的投影中成立。

当某些 FD 持有时，其他 FD 也必须持有，因为那些 FD 持有。因此，R 中保存的 FD 比你得到的 FD 多得多。此外，一些持有但未被持有的 FD 因为一些使用 E 的 FD 持有——即使它们本身不包含 E。所以首先你需要在 R 中找到更多的 FD，直到找到一个由于不涉及E.

投影后会保留

一种方法是求F+（FD集合的闭包）。但它可以非常大。我们可以做的是使用属性集闭包的概念。即由一个属性集决定的所有属性的集合。（根据确定的属性，我们知道所有与该行列式保持一致的 FD。）有一种算法可以找到它。如果答案 FD 行列式是 F 中的行列式，那么我们可以计算它在 R 中的闭包，看看它的答案 FD 是否也在 R 中成立。

如果 FD 的 none 行列式作为 F 中的行列式出现，那么我们将不得不开始在 F+ 中生成 FD，直到我们得到一个具有行列式的行列式，该行列式也是答案中的行列式。然后我们可以应用上一步。

将函数依赖投射到另一个关系上

projecting functional dependencies onto another relation

functional-dependencies