45

我正在上一门数据库理论课程，在阅读了如何在给定一组功能依赖项的情况下推断密钥后，我并不清楚。

我有一个示例问题：

查找具有函数依赖关系的关系 R(ABCDEFG) 的所有键

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

通过确定以下哪些是关键来展示您的知识。

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

有人可以指导我如何分解功能依赖项以得出某些属性组合是关键的结论吗？我预计我将面临许多此类问题，我需要了解如何解决它。

4

6 回答 6

32

取一个FD，例如AB→C

增加直到所有属性都被提及，例如 ABDEFG → CDEFG（注意这等价于 ABDEFG → ABCDEFG，因为 A->A 和 B->B 是平凡的）。

这告诉您 ABDEFG 是一个超级键。

检查其他 FD，其中 LHS 是您的超级密钥的子集，并且在其 RHS 上包含您的超级密钥的其他属性。

那里有两个。EF→G 和 FG→E。从您的超级密钥中删除这些 RHS 的属性。这样做会给你两个密钥，它们肯定是超级密钥，但不一定是不可约的：ABDEF 和 ABDFG。

但是，从 AB→C 和 CD→E 我们也可以推导出 ABD→E。因此我们也可以从我们的 ABDEF 键中删除 E。这里令人讨厌的是，当我说“检查其他 FD”时，这显然意味着您还应该检查出现在您的 FD 集的闭包中的任何 FD（即任何可从您的给定 FD 集派生的 FD） ...而且手工操作有点不切实际...

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

http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools

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

于 2011-04-20T20:23:01.083 回答
3

那么这应该是相当简单的。您需要做的就是关闭给定的每个键，看看它是否包含 R 的所有属性。例如，BCDEF = ABCDEFG 的关闭，因为 BC -> A 和 BC 是 BCDEF 的子集，所以如果 EF 为 FD EF -> G。由于这个闭包包含了 R 的所有属性，所以 BCDEF 是关键。使用闭包的主要目的是看看我们是否可以从给定的一组属性中“到达”每个属性。闭包是我们可以通过导航 FD 实际访问的一组属性。

于 2011-12-05T22:42:23.920 回答
2

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

基本上，关系是您在实现中称为表的内容，键是可用于标识唯一行的任何属性集（读取列）（在数据库理论中，这将是一个元组）。这里最简单的类比是键是您的主键，以及您可以用来识别关系中的单个元组（表中的行）的任何其他可能的列集。因此，以下是执行此操作的基本步骤（我将介绍示例 A，然后您可以尝试其余的）：

  1. 列出所有不在您建议的密钥中的属性（因此 BCDEF 不包括 A 和 G）。

  2. 对于您缺少的每个属性，请查看功能依赖项列表，看看您提出的密钥是否能够推断出您缺少的属性。

                 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 的键。我知道有一个算法可以解决这个问题，它可能在你的课程文本中的某个地方。大概也有一个例子。您应该手动逐步完成，直到模式直观。

编辑：我会回过头来寻找这个算法的原因是你的考试很可能会被写出来，而不是多项选择，因为它是一门数据库理论课程。如果这是真的，那么如果您有条不紊地遵循课程文本/笔记中展示的符号，您将获得更多的部分学分。

主要目标是将密钥转换为关系，这应该证明提议的密钥实际上是密钥。

于 2011-04-20T20:04:28.723 回答
1

好吧，我不是这方面的专家，如果我错了，请纠正我，但我的方法是消除不可能的答案

在这种情况下：

您的 FD 都没有“给”您 B、D 或 F ... 因为它们是关系的一部分，所以没有不包含 B、D 和 F 的超级键...删除答案 b (B is missing) 。 .. 删除答案 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）...最后BC可以到达A（到达C之后）...

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

于 2011-04-20T20:03:18.323 回答
1

代码

如果代码对您的解释超过了冗长的解释，这里有一个 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"]]

于 2016-01-17T14:51:26.580 回答
-1 
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 是一个超级 Key。然后我们将使用依赖关系的结果来确定它们是否是键。（这就是我使用 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.
于 2014-04-24T15:38:00.270 回答