从函数依赖中确定关键字

Question

我正在学习数据库理论课程，在阅读了相关材料之后，我还不清楚如何在给定一组函数依赖关系的情况下推断出键。

以下是一个例题：

找出关系R(ABCDEFG)的所有键，其中给定函数依赖关系。

AB → C
CD → E
EF → G
FG → E
DE → C
BC → A

展示你的知识，通过辨认以下哪个是密钥。

a. BCDEF             
b. ADFG           
c. BDFG           
d. BCDE 

有人能够引导我如何将函数依赖分解以得出某些属性组合是键吗？我预计将遇到许多这类问题，因此需要了解如何处理它。

- David

---

yrazlik的回答中的视频实际上使用了[1]中介绍的方法，如果您想知道为什么它有效（证明简短而直接），请参考。 [1] H. Saiedian和T. Spencer，“计算关系数据库模式的候选键的有效算法”，计算机杂志，第39卷，第2期，1996年2月[在线]. 可用：https://pdfs.semanticscholar.org/ab3f/f65010b50d78d583b1c2b6ce514fa072d23d.pdf。[访问日期：2019年7月31日] - Leponzo

@Leponzo，你在一些已删除的答案中提供的项目符号算法介绍是错误的，类似于你在此处被删除的答案。该算法要求F是包含有效的FDs而不仅仅是一组包含有效FDs的集合。请使用文字而非图像/链接来呈现文本，包括表格和ERDs。引用其他文本的概括或者直接引用。只有当某些内容无法用文字表达时才使用图像来增强文字。图像无法搜索或复制。如果使用图像，请附上图例/关键字及解释。 - philipxy

Answer 1

取一个函数依赖，例如AB→C。

扩展函数依赖直到包含所有属性，例如ABDEFG→CDEFG (注意这与ABDEFG→ABCDEFG等价，因为 A->A 和 B->B 是显然成立的)。

由此可知ABDEFG是超码。

检查其他左部是你的超码子集且右部包含一些超码属性的函数依赖。

有两个。EF→G和FG→E。从你的超码中移除这些右部属性。这样做会给你两个键，它们肯定是超码，但不一定是不可约的：ABDEF和ABDFG。

但是，从AB→C和CD→E，我们还可以推出ABD→E。因此，我们也可以从我们的ABDEF键中移除E。这里比较麻烦的是，当我说“检查其他函数依赖”时，这显然意味着您还应该检查在您的函数依赖闭包中出现的任何函数依赖(即可以从您给定的函数依赖集合中派生出的任何函数依赖)... 这在手工处理上有点不切实际...

一个验证您结果是否正确的有用网站：

http://raymondcho.net/RelationalDatabaseTools/

现在，您应该能够确定选项c是一个键。

- Erwin Smout

---

BDF不是候选键吗？由于DF->C，EF->G，CD->E，我们可以从BDF得到G。 - Niklas Rosencrantz

@NickRosencrantz：有四个候选键，BDF不是其中之一；它们恰好都有四个属性。我完全不明白你的演绎逻辑；你提到的任何FD都不包含B。 - Mike Sherrill 'Cat Recall'

他提到了DF->C，但没有明确指出。也许他误读了DE->C。 - Erwin Smout

@ErwinSmout，您能逐步说明如何将AB→C增强为ABDEFG→CDEFG吗？我不是很明白。 - Fjodor

增广规则指出，如果S1->S2和S3->S4，则(S1 U S3)->(S2 U S4)。其中，S1、S2、S3、S4是集合，U表示并集。只需将其应用于{AB}->{C}和平凡的{D}->{D}(以及其他集合)即可。 - Erwin Smout

很有趣，你在同一天四年后更新了你的答案 :) 除此之外，解释得很好。 - corecase

Answer 2

这应该很简单。您只需要获取给定键的闭包，并查看它是否包含R的所有属性。例如，BCDEF的闭包= ABCDEFG，因为BC -> A并且BC是BCDEF的子集，所以如果EF针对FD EF -> G。由于这个闭包包含了R的所有属性，BCDEF就是关键字。获取闭包的主要目的是看看我们是否可以从给定的属性集“到达”每个属性。闭包是我们实际上通过导航FDs可以到达的属性集。

- Parth Mehta

---

BCDEF不是候选键，因为它是可简化的（BC->E）。但是BCDF是其中一个候选键。 - Mike Sherrill 'Cat Recall'

Answer 3

由于你正在学习数据库理论课程，我会假设你有SQL经验，并尝试将理论与实现上下文联系起来。

基本上，关系是你在实现中所称的表格，而键是用于标识唯一行（在数据库理论中这被称为元组）的任何属性集合（也就是列）。最简单的类比是，键就是你的主键，以及你可以使用的任何其他可能的列集合来标识关系中的单个元组（表格中的一行）。因此，这里是执行此操作的基本步骤（我将演示示例A，然后你可以尝试其余部分）：

1. List all of the attributes which are NOT in your proposed key (so BCDEF does not include A and G).

2. For each attribute you're missing, go through the list of functional dependencies and see if your proposed key is capable of inferring the attribute you're missing.

                a. So for A, you have BC -> A.  Since both B and C are in the proposed
                   key BCDEF, you can infer that BCDEF -> A.  Your set now becomes
                   BCDEFA.
                b. For G, again going through your FDs you find EF -> G.  Since both
                   E and F are in BCDEFA, you can infer BCDEFA -> G.
   

因为你能够从BCDEF推断出A和G，所以选项a是关系ABCDEFG的一个键。我知道有一个算法可以实现这个功能，在你的课程文本中可能会有。还可能有一个例子。您应该手动遍历它，直到模式变得直观。

编辑：我会回到文本中寻找这个算法的原因是，由于这是db理论课程，你的考试很可能是笔试而不是多项选择题。如果是这样，那么如果您能系统地按照课程文本/笔记中演示的符号方法操作，您将获得更多的部分分。

主要目标是将关键转化为关系，这应该证明所提议的关键实际上是一个关键。

- Dave

---

选项a确实是一个关键选项，但不是不可约的。不可约的是选项c。 - Erwin Smout

是的，我只是仔细看了选项a。我没有考虑指定/找出哪些键是最小键，因为这不是问题的一部分。我记得从我的数据库理论课程中，确定最小键是一个不同的主题，与确定任何键不同。所以我选择在我的答案中省略它，以避免混淆。 - Dave

@Erwin，经过进一步的研究，我理解了你的观点。我认为问题中使用的“key”这个词比较模糊。对于这个问题的答案会因为“key”是否指候选键而有所不同。如果是指候选键，那么你是正确的，选项a不是一个键，因为它的子集仍然是一个有效的超键。 - Dave

是的，非常抱歉之前表述不够清晰。我对 SQL 和数据库中关系模型的设计很熟悉，但理论方面还有些新颖的东西需要学习。您的回答也帮助了我。谢谢！ - David

Answer 4

代码

如果代码比冗长的解释更能让您理解，那么这里有一个基于函数依赖性查找键的算法的25行实现：

https://github.com/lovasoa/find-candidate-keys/blob/master/find-candidate-keys.js

示例

candidate_keys(["A","B","C","D","E","F","G"], [ [['A','B'], 'C'], [['C','D'], 'E'], [['E','F'], 'G'], [['F','G'], 'E'], [['D','E'], 'C'], [['B','C'], 'A'] ]) 返回 [["B","D","F","G"],["B","D","E","F"],["B","C","D","F"],["A","B","D","F"]]

- lovasoa

Answer 5

嗯，我对这个东西不是专家，如果我错了，请纠正我，但我的方法是消除不可能的答案。

在这种情况下：

你的任何FD都没有给你B、D或F...因为它们是关系的一部分，所以没有超级键不包含B、D和F...删除答案b（缺少B）...删除答案d（缺少F）

现在让我们检查剩下的答案是否包含足够的信息来获取关系的所有部分

答案a（BCDEF）将给你B、C、D、E和F，所以你需要使用FD找到A和G... A可以通过BC到达，G可以通过EF到达，所以答案a是一个关键字

答案c（BDFG）将给你B、D、F和G，所以你需要使用FD找到A、C和E... E可以通过FG到达... C可以通过DE到达（在通过FG到达E之后）...最后，A可以通过BC到达（在到达C之后）...

因此，答案C是某种键，因为可以通过这种方式访问整个关系...但我不知道这是否足以符合正式的定义...如果必须猜测，我会说不

- DarkSquirrel42

---

答案a是一个适当的超键，这意味着存在一些适当的子集也是关键字。通常，“关键字”一词意味着“不可约”，但对于a并非如此。但是这样的细节可能因课程而异... - Erwin Smout

Answer 6

step1: since AB->C and CD->E.  then we get ABD->ABCDE(1)
step2: Given (1) and EF->G, then we get ABDF->ABCDEF, then ABDF->ABCDEFG(2), 

所以ABDF是一个超级键。然后我们将使用依赖关系的结果来确定它们是否为键。(这里为什么我使用BC->A，因为A是我的超级键的一部分，它依赖于BC)。

step3: Given (2) and BC->A, we get BCDF->ABDF, so BCDF->ABCDEFG(3)   
step4: Given (3) and DE->C, we get BDEF->BCDE, so BDEF->ABCDEFG(4)   
step5: Given (4) and FG->E, we get BDFG->BDEF, so BDFG->ABCDEFG,    
So the Answer BDFG is right.

- user3569580