給定一組通用屬性和功能依賴列表

Question

現在我已經在java中實現了以下算法來確定所有可能的工作正常的候選鍵。該鏈接是下面： -

http://shubhamshoundic.blogspot.com/2012/08/an-algorithm-to-find-all-possible.html

但是在最壞的情況下，即，如果所有的屬性存在於FD的兩側（如在箱M上面鏈接所定義的），FD的數目，其可以處理減少到12或13。

原因是java中的堆空間有限。被拋出以下錯誤： -

OutOfMemoryError

我的要求是，以幫助我是在執行這樣的算法，這將有更簡單的複雜性（現在它的指數）改善FD的數量正在處理至少20。

我應該嘗試使用多重處理來計算它，還是應該轉換到另一種語言而不是java。

Answer 1

從1978年就已知，並且在所有有關數據庫的優秀書籍中都提到，找到所有密鑰的問題需要在最差情況下具有指數複雜度的算法（例如參見Lucchesi, C. and Osborn, S. (1978). Candidate keys for relations. Journal of Computer and System Sciences, 17(2):270–280）。此外，查找屬性是否爲素數的問題是NP Complete。

這是由於以下事實：可能的鍵的數目本身與指定數量的屬性或因子與功能依賴關係的數目。

因此，它是不可能找到一個算法多項式與屬性的數量或功能的依賴關係。