-1

現在、正常に機能しているすべての可能な候補キーを決定するために、Java で次のアルゴリズムを実装しました。リンクは以下です： -

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

ただし、最悪の場合、つまり、すべての属性が FD の両側に存在する場合 (上記のリンクで定義された M の場合のように)、処理できる FD の数は 12 または 13 に減少します。

理由は、Java のヒープ領域が限られているためです。次のエラーがスローされています:-

OutOfMemoryError

私の要求は、処理される FD の数を少なくとも 20 に改善するために、より単純な複雑さ (現在は指数関数) を持つアルゴリズムを実装するのを手伝ってくれることです。

マルチプロセッシングを使用して計算しようとするか、Java ではなく別の言語に移行する必要があります。

4

1 に答える 1

1

1978 年から知られており、データベースに関するすべての優れた本で提示されているように、すべてのキーを見つける問題には、最悪の場合には指数関数的な複雑さを持つアルゴリズムが必要です (たとえば、Lucchesi, C. および Osborn, S. ( 1978). 関係の候補キー. Journal of Computer and System Sciences, 17(2):270–280 ). さらに、属性が素数であるかどうかを見つける問題はNP Completeです。

これは、可能なキーの数自体が属性の数で指数関数的であるか、関数の依存関係の数で階乗であるという事実によるものです。

したがって、属性の数または関数の依存関係を持つアルゴリズム多項式を見つけることは不可能です。

于 2016-08-30T04:29:35.500 に答える