如何从函数依赖中获取最小键？ [英] How to obtain a minimal key from functional dependencies?

问题描述

我需要一些帮助和指导。

I need some help and guidelines.

我有以下关系： R = {A，B，C，D，E， F} 和函数依赖性集合

I have the following relation: R = {A, B, C, D, E, F} and the set of functional dependencies

F = {
  {AB -> C};
  {A  -> D};
  {D  -> AE};
  {E  -> F};
}

R的主键是什么？

如果我应用推理规则，我得到这些额外的函数依赖：

If i apply inference rules i get these additional Function dependencies:

D -> A
D -> E
D -> F

D -> AEF

A -> E
A -> F
A -> DEF

如何继续？

推荐答案

有一个众所周知的算法来做到这一点。我不记得了，但是练习似乎很简单，不能使用它。

There is a well known algorithm to do this. I don't remember it, but the excercise seems to be simple enough not to use it.

我认为这一切都是关于传递性：

I think this is all about transitivity:

CurrentKey = {A, B, C, D, E, F}

你知道D决定E和E决定F.因此，D通过传递性确定F.由于F不确定任何东西，我们可以删除它，并且E可以从D中获得，我们也可以删除它：

You know D determines E and E determines F. Hence, D determines F by transitivity. As F doesn't determine anything, we can remove it and as E can be obtained from D we can remove it as well:

CurrentKey = {A, B, C, D}

由于AB决定C和C确定我们知道它不能作为密钥的一部分，所以我们删除它：

As AB determines C and C doesn't determine anything we know it can't be part of the key, so we remove it:

CurrentKey = {A, B, D}

最后，我们知道A决定D，所以我们可以从密钥中删除后者：

Finally we know A determines D so we can remove the latter from the key:

CurrentKey = {A, B}

如果一旦你有这个可能的键，你可以重新创建所有的功能依赖它是一个可能的键。

If once you have this possible key, you can recreate all functional dependencies it is a possible key.

PS：如果你碰巧有算法，请张贴它，因为我很高兴重新学习：）

PS: If you happen to have the algorithm handy, please post it as I'd be glad to re-learn that :)

这篇关于如何从函数依赖中获取最小键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！