database 从功能依赖确定键

Determine Keys from Functional Dependencies

提问by David

I'm taking a database theory course, and it's not clear to me after doing the reading how I can infer keys, given a set of functional dependencies.

我正在学习数据库理论课程，在阅读了如何推断键后，我不清楚给定一组函数依赖项。

I have an example problem:

我有一个示例问题：

Find all keys of the relation R(ABCDEFG) with functional dependencies

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

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

Demonstrate your knowledge by identifying which of the following is a key.

通过确定以下哪一项是关键来证明您的知识。

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

Can someone walk me through how I should decompose the functional dependencies to conclude that some combination of attributes is a key? I expect I'll face a number of these types of problems and I need to understand how to approach it.

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

采纳答案by Erwin Smout

Take an FD, e.g. AB→C

取一个FD，例如AB→C

Augment until all attributes are mentioned, e.g. ABDEFG → CDEFG (note that this is equivalent to ABDEFG → ABCDEFG because it is trivially true that A->A and B->B).

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

This tells you that ABDEFG is a superkey.

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

Check the other FDs in which the LHS is a subset of your superkey, and that on its RHS contains some other attribute of your superkey.

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

There are two. EF→G and FG→E. Remove the attributes of the RHS of these from your superkey. Doing so gives you two keys, that are certainly superkeys, but not necessarily irreducible ones: ABDEF and ABDFG.

那里有两个。EF→G 和 FG→E。从您的超级键中删除这些 RHS 的属性。这样做会为您提供两个键，它们当然是超级键，但不一定是不可约的：ABDEF 和 ABDFG。

However, from AB→C and CD→E we can also derive that ABD→E. Hence we can also remove the E from our ABDEF key. The nasty thing here is that when I said "Check the other FDs", that apparently means that you should also check any FD that appears in the closure of your set of FDs (i.e. any FD that is derivable from your given set of FDs)... And that's a bit impractical to do by hand ...

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

A useful site for verifying whether your results are correct:

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

http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools

http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools

You should now be able to determine that option c is a key.

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

回答by Parth Mehta

Well this should be rather straightforward. All you need to do is to take the closure of every key given and see if it contains all attributes of R. For example, closure of BCDEF = ABCDEFG since BC -> A and BC is a subset of BCDEF and so if EF for FD EF -> G. Since this closure contains all attributes of R, BCDEF is the key. The main aim of taking closures is to see if we can "reach" every attribute from a given set of attributes. The closure is the set of attributes that we can actually reach by navigating the FDs.

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

回答by Dave

Since you're in a db theory course, I'm going to assume you have SQL experience and try and relate the theory to the implementation context.

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

Basically, a relation is what you would refer to as a table in implementation and a key is ANY set of attributes (read columns) which can be used to identify a UNIQUE row (in db theory this would be a tuple). The simplest analogy here is that a key is your primary key, as well as any other possible set of columns you can use to identify a single tuple in your relation (row in your table). So, here are the basic steps for doing this (I'll walk through example A, and then you can try the rest):

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

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.
   

Because you were able to infer both A and G from BCDEF, option a is a key of the relation ABCDEFG. I know there is an algorithm for this, and it is probably in your course text somewhere. There is also probably an example. You should step through it manually until the pattern is intuitive.

因为您能够从 BCDEF 推断出 A 和 G，所以选项 a 是关系 ABCDEFG 的键。我知道有一个算法，它可能在你的课程文本中的某个地方。大概也有一个例子。您应该手动逐步完成，直到模式变得直观。

EDIT: The reason I would go back through the text to look for this algorithm is that chances are your exam is going to be written as opposed to multiple choice since it is a db theory course. If this is true then you would get more partial credit if you can methodically follow notation demonstrated in your course text/notes.

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

The main goal is to turn the key into the relation, which should prove that the proposed key is in fact a key.

主要目标是将密钥变成关系，这应该证明提议的密钥实际上是一个密钥。

回答by lovasoa

Code

代码

If code talks to you more than long explanations, here is a 25 lines implementation of an algorithm that finds keys based on functional dependencies:

如果代码与您交谈的不仅仅是冗长的解释，这里有一个 25 行的算法实现，该算法根据函数依赖关系查找键：

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

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

Example

例子

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'] ]) returns [["B","D","F","G"],["B","D","E","F"],["B","C","D","F"],["A","B","D","F"]]

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"]]

回答by DarkSquirrel42

well, i'm no expert for this stuff, so correct me if i'm wrong, but my approach would be to eliminate impossible answers

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

in this case:

在这种情况下：

none of your FDs "gives" you B, D or F ... since those are part of the relation there can be no super key that does not contain B, D and F ... remove answer b (B is missing) ... remove answer d (F is missing)

您的任何 FD 都不会“给”您 B、D 或 F……因为它们是关系的一部分，因此不可能有不包含 B、D 和 F 的超级键……删除答案 b（缺少 B）。 .. 删除答案 d（缺少 F）

now let's check the remaining answers if they contain enough information to get all parts of the relation

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

answer a (BCDEF) will "give" you B, C, D, E and F so you need to find A and G using the FDs ... A can be reached by BC and G can be reached by EF, so answer a is a key

答案 a (BCDEF) 将“给”您 B、C、D、E 和 F，因此您需要使用 FD 找到 A 和 G……BC 可以到达 A，EF 可以到达 G，因此请回答 a是一把钥匙

answer c (BDFG) will "give" you B, D, F and G so you need to find A, C and E using the FDs ... E can be reached by FG ... C can be reached by DE (after reaching E by FG) ... and finally A can be reached by BC (after reaching C) ...

答案 c (BDFG) 将“给”您 B、D、F 和 G，因此您需要使用 FD 找到 A、C 和 E……E 可以通过 FG 到达……C 可以通过 DE 到达（之后通过 FG 到达 E) ...最后可以通过 BC 到达 A（到达 C 之后）...

so answer c is some sort of key since the whole relation can be accessed this way ... but i don't know if this is enough to fit the formal definition ... if i'd have to guess, i'd say no

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

回答by user3569580

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), 

so ABDF is a super Key. Then we will use the result of the depnedencies to determine whether they are keys. (here why I use BC->A, because A is part of my superkey, which is dependent on BC).

所以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.