5

関数依存関係のセットのクロージャーを (手動で) 計算するための、理解しやすいアルゴリズムを探しています。私のインストラクターを含む一部の情報源は、アームストロングの公理で遊んで、何が得られるかを確認する必要があると言います。私にとって、それはそれを行うための体系的な方法ではありません (つまり、何かを見逃すのは簡単です)。

私たちのコースのテキスト (DB システム - 完全な本、第 2 版) にも、このためのアルゴリズムは示されていません。

4

3 に答える 3

1

FD の集合 F の下で α によって関数的に決定されるすべての属性の集合。

例えば。これらの開始 FD があり、以下を 1 回使用してすべてのクロージャを計算したいとします。

A -> BC 
AC -> D
D -> B
AB -> D

上記で計算されたより多くの FD が一度存在する

A+ -> (A,B,C,D)
B+ -> (B)

同様に、C+、D+、(AC)+、(AB)+ などを計算できます...

非常に簡単なアルゴリズムがあります。ただし、FDのすべてのセットを計算するには

RESULT <- α
MODIFIED <- TRUE

WHILE(MODIFIED) {
   MODIFIED <- FALSE
   ∀ FD A->B IN F DO{
       IF A ⊂ RESULT {
           RESULT <- (RESULT) ∪ (B)
              MODIFIED <- TRUE IF RESULT CHANGES
       }
   }
}
于 2015-04-22T01:14:00.503 に答える
1

より「体系的な」方法で言えば、これが探しているアルゴリズムになる可能性があります。最初の 3 つのアームストロングの公理を使用します。

  • 閉鎖 = S
  • ループ
    • S の各 F に対して、再帰規則と拡張規則を適用します。
    • クロージャーに新しい FD を追加する
    • S の FD の各ペアに対して、推移性ルールを適用します。
    • 新しい Fd を Closure に追加する
  • 閉鎖がこれ以上変わらないまで`

これは、このプレゼンテーション ノートから取ったものです。ただし、次のアプローチの方が実装が簡単であることがわかりました。

  • /*F は FD のセットです */
  • F⁺ = 空集合
  • 各属性セット X
    • F 上の X の閉包 X⁺ を計算する
    • X⁺ の各属性 A
      • F⁺ に FD を追加: X -> A
  • F⁺を返す</li>

ここから取られる

于 2014-02-07T20:23:39.653 に答える