sql - 機能依存関係から最小限のキーを取得するには?

Question

ヘルプとガイドラインが必要です。

私は次の関係を持っています:R = {A, B, C, D, E, F}機能依存関係のセット

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

R の主キーは何ですか?

推論規則を適用すると、これらの追加の関数の依存関係が得られます。

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

D -> AEF

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

どうすれば続行できますか?

Answer 1

これを行うためのよく知られたアルゴリズムがあります。覚えていませんが、練習は使わないくらい簡単なようです。

これはすべて推移性に関するものだと思います。

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

DがEを決定し、EがFを決定することを知っています。したがって、Dは推移性によってFを決定します。Fは何も決定しないので、それを削除できます。EはDから取得できるので、次のように削除することもできます。

CurrentKey = {A, B, C, D}

ABがCを決定し、Cはキーの一部にできないことがわかっているものを決定しないため、次のように削除します。

CurrentKey = {A, B, D}

最後に、AがDを決定することがわかっているので、キーから後者を削除できます。

CurrentKey = {A, B}

この可能なキーを取得したら、それが可能なキーであるすべての機能依存性を再作成できます。

PS：アルゴリズムが手元にある場合は、それを投稿してください。再学習できてうれしいです:)

Answer 2

アルゴリズム: 鍵計算 (x = ∅ で呼び出す)

procedure key(x;A;F)
foreach  ! B 2 F do
if   x and B 2 x and B ̸2  then
return; /* x not minimal */
fi
od
if x+ = A then
print x; /* found a minimal key x */
else
X   any element of A  x+;
key(x [ fXg;A;F);
foreach  ! X 2 F do
key(x [ ;A;F);
od
fi