具有功能依赖性的候选键识别
我无法理解如何识别函数依赖项中的键。我一直在看例子，例如：
给定一个关系ABCD，找到不包括超级键的所有键
A -> BC, C -> D, CD -> AB.
这给出了键C和A。我认为解决这个问题的方式是BC和D都依赖于A和C ，AB 依赖于 CD，这意味着它们三个都是密钥，但由于 CD 是超级密钥（C 是也是密钥的子集），因此 CD 不被视为最小超级密钥。
然而，在另一个例子中，
ABCDE
AB → CD
E → A
D → A
这里唯一的关键显然是BE。为什么这是真的？任何人都可以澄清查找这些问题的密钥所采取的步骤吗？
谢谢。
I'm having trouble understanding how to identify keys in functional dependencies. I've been looking at examples, for example:
Given a relation ABCD, find all keys not including superkeys of the
A -> BC, C -> D, CD -> AB.
This gives keys C and A. The way I thought this problem was approached was that BC and D both depend on A and C, and AB depends on CD, meaning all three of them are keys, but since CD is a superkey (C is a subset that is also a key), CD is not considered a minimal superkey.
However, in another example,
ABCDE
AB → CD
E → A
D → A
The only key here is apparently BE. Why is this true, and can anyone clarify the steps to take in finding keys with these problems?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一个稍微正式一点的程序。
取FD，例如（例2），AB→光盘。
使用简单的 FD 来增强这一点，直到您拥有 RHS 上的所有属性。
您在 RHS 上缺少 ABE，因此您必须使用简单的 FD ABE -> 进行增强。 ABE获得ABE-> ABCDE。
这告诉您 ABE 是一个超级键，因为知道 ABE 某一行中的值将足以确定该行中所有属性的值。
现在检查其他 FD，看看其中是否有任何允许您在这种情况下减少 LHS (ABE)。 E-> A 允许您从 ABE 中删除 A，从而仅保留 BE -> ABCDE。减少的规则是：如果另一个 FD (E) 的 LHS 是您尝试减少的超级密钥 (ABE) 的真子集，那么您可以从超级密钥中删除仅在该超级密钥的右侧提到的所有属性其他 FD（如果您正在查看“其他”FD，例如 E -> EA，则无法删除 E！！！）。
该过程不适合机械实现，因为您可能还需要查看其他 FD 的“组合”。然而，大多数用例甚至大多数虚构的课堂练习通常都不够复杂，不会导致此过程失败（即为您留下一个适当的超级密钥，而不是一个不可约的超级密钥）。
（PS 要找到所有密钥，您需要将其应用于所有给定的 FD）
A procedure that is a little more formal.
Take an FD, e.g. (example 2), AB -> CD.
Augment this using trivial FDs until you have ALL the attributes on the RHS.
You lack ABE on the RHS, so you must augment using the trivial FD ABE -> ABE to obtain ABE -> ABCDE.
That tells you that ABE is a superkey, because knowing the values in a certain row for ABE will be sufficient to determine the values for all attributes in that row.
Now inspect the OTHER FDs to see if any of them allow you to reduce the LHS (ABE) in this case. E -> A allows you to remove A from ABE, keeping thus only BE -> ABCDE. The rule for reduction is : if the LHS of another FD (E) is a proper subset of the superkey you are trying to reduce (ABE), then you can remove all the attributes from the superkey that are mentioned ONLY in the RHS of that other FD (you cannot remove E if you are looking at an "other" FD such as E -> EA !!!).
This procedure is not apt for mechanical implementation, because you might also have to take a look at "combinations" of other FDs. However, most use cases and even most fabricated class exercises typically are not complex enough to cause this procedure to fail (i.e. leaving you with a proper superkey instead of an irreducible one).
(PS to find ALL the keys, you will need to apply this to ALL given FDs)
第二个比较简单，所以先看第二个。 。 。你知道 B 一定是任意调，因为它不在任何右手边。 （也就是说，即使你有 ACDE 的值，你也无法推断出 B 的值。）E 也类似；因此，任何键都必须包含 BE。但 BE 本身就是一个足够的密钥，因为 E 给你 A（因此 BE → ABE），AB 给你 CD（因此 BE → ABCDE）。
在第一个中，我们可以看到A是一把钥匙，因为A给你B和C，C给你D。同样，C是一把钥匙，因为C给你D，C和D一起给你A和B. 相反，我们看到 A 和/或 C 必须是任意调，因为每个左侧都至少包含其中一个。
The second one's a bit simpler, so taking it first . . . you know that B must be in any key, because it's not on any right-hand side. (That is, even if you have the values of ACDE, you couldn't infer the value of B.) Similarly for E; so, any key must include BE. But BE is by itself a sufficient key, because E gives you A (hence BE → ABE) and AB gives you CD (hence BE → ABCDE).
In the first one, we can see that A is a key, because A gives you B and C, and C gives you D. Similarly, C is a key, because C gives you D, and C and D together give you A and B. Conversely, we see that A and/or C must be in any key, because every left-hand-side includes at least one of them.
参考
http://www.ict .griffith.edu.au/~jw/normalization/assets/Functional%20Dependencies%20and%20Normalization.pdf
算法证明（简短明了，第 3 节）
H. Saiedian 和 T. Spencer，“计算关系数据库模式候选键的有效算法”，计算机杂志，卷。 39，没有。 1996 年 2 月 2 日 [在线]。可用： https://pdfs.semanticscholar.org/ab3f/f65010b50d78d583b1c2b6ce514fa072d23d.pdf。 [访问日期：2019 年 7 月 31 日]
视频说明
https://www.youtube.com/watch?v=s1DNVWKeQ_w
Reference
http://www.ict.griffith.edu.au/~jw/normalization/assets/Functional%20Dependencies%20and%20Normalization.pdf
Proof of Algorithm (short and straightforward, section 3)
H. Saiedian and T. Spencer, “An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema,” The Computer Journal, vol. 39, no. 2, Feb. 1996 [Online]. Available: https://pdfs.semanticscholar.org/ab3f/f65010b50d78d583b1c2b6ce514fa072d23d.pdf. [Accessed: 31-Jul-2019]
Video Explanation
https://www.youtube.com/watch?v=s1DNVWKeQ_w