java - 给定一组通用属性和功能依赖项列表，确定所有候选键

Question

现在我已经在java中实现了以下算法来确定所有可能的候选键，这些键工作正常。链接如下：-

但在最坏的情况下，即如果所有属性都存在于 FD 的两侧（如上面链接中定义的情况 M），则可以处理的 FD 数量减少到 12 或 13。

原因是java中的堆空间有限。引发以下错误：-

我的请求是帮助我实现这样的算法，该算法将具有更简单的复杂性（现在它是指数级的），以将处理的 FD 数量至少提高到 20。

我应该尝试使用多处理来计算它，还是应该转向另一种语言而不是 java。

score 1 · Accepted Answer

从 1978 年就知道并在所有关于数据库的好书中都有介绍，找到所有密钥的问题需要一个在最坏情况下具有指数复杂度的算法（例如，参见：Lucchesi, C. 和 Osborn, S. ( 1978). 关系的候选键. 计算机与系统科学杂志, 17(2):270–280 ). 此外，查找属性是否为素数的问题是NP Complete。

这是因为可能的键的数量本身与属性的数量成指数关系，或者与功能依赖的数量成指数关系。

因此，不可能找到具有属性数量或函数依赖关系的算法多项式。

1 回答 1