32

次の機能依存関係を考えると、最小限のカバーをどのように計算しますか:

A -> B, ABCD -> E, EF -> GH, ACDF -> EG

講義ノートでは、最小限のカバーの派生を示していますが、私はそれを理解していません。

たとえば、ACDF を取り除く場合 -> E :

A -> B => AACD -> BACD -> E => ACD -> E => ACDF -> E

そして彼らは言う、同様に我々はACDF を保持しない -> G

そして、A -> Bであるため、 ABCD -> EがACD -> Eに推定されることは理解していますが、そこに到達する方法の正式なプロセスは理解していません。

だから私の質問は、セットの機能依存関係の最小限のカバーを生成する方法の説明を誰かが提供できますか?

4

2 に答える 2

87

最小限のカバーを取得するには、2 つの手順を実行する必要があります。実演するために、まず依存関係を複数に分割し (右側の属性は 1 つだけ)、よりクリーンにします。

A -> B
ABCD -> E
EF -> G
EF -> H
ACDF -> E
ACDF -> G

次の手順は、この順序 (#1、次に #2) で実行する必要があります。そうしないと、誤った結果が得られる可能性があります。

1) 冗長な属性を取り除きます (左側を減らします):

各左側を取り、一度に 1 つの属性を 1 つずつ削除してから、右側を推測してみてください (すべての依存関係に対して 1 つの属性のみになります)。成功した場合は、その文字を左側から削除して続行します。複数の正しい結果が存在する可能性があることに注意してください。これは、リダクションを実行する順序によって異なります。

(use first dep.) および fromであるためB、依存関係から削除できることがわかります。完全な依存関係を使用できます。今削減していると、最初は戸惑うこともありますが、考えてみれば、それができることが明らかになります。ABCD -> EACD -> ABCDABCD -> E

同様に、FからACDF -> Eを削除できACD -> ABCD -> ABCDE -> Eます (文字自体から 1 文字を推測できることは明らかです)。このステップの後、次のようになります。

A -> B
ACD -> E
EF -> G
EF -> H
ACD -> E
ACDF -> G

これらのルールは、元のルールと同じ依存関係を表しています。ルールが重複していることに注意してくださいACD -> E。全体を (数学的な意味で) セットとして見ると、もちろん、同じ要素を 1 つのセットに 2 回含めることはできません。とりあえず、次のステップで取り除かれるので、ここでは 2 回だけ残しておきます。

2) 冗長な依存関係を取り除く

次に、ルールごとにそれを削除してみて、他のルールのみを使用して同じルールを推測するかどうかを確認します。もちろん、このステップでは dep を使用できません。現在、削除しようとしています (前の手順で可能です)。

最初のルールの左辺を取ると、今のところ隠します。単独でA -> Bは何も推測できないことがわかります。Aしたがって、このルールは冗長ではありません。他のすべての人についても同じことを行います。(明らかに) 重複するルールの 1 つを削除できることがわかりますがACD -> E、厳密に言えば、アルゴリズムも使用できます。2 つの同じルールの 1 つだけを非表示にして、左側 ( ACD) を取得し、もう 1 つを使用して右側を推測します。したがって、削除できますACD -> E（もちろん一度だけ）。

ACDF -> Gを削除できることもわかりますACDF -> ACDFE -> G。結果は次のとおりです。

A -> B
EF -> G
EF -> H
ACD -> E

オリジナルセットの最小限のカバーです。

于 2012-04-23T16:33:55.243 に答える
-3

私によると、上記の機能的な最小限の依存関係 ACDF -> G も含める必要があります。これは、左側の各文字とそれらの組み合わせを閉じると、F を含めずに G を生成しないためです。

したがって、次のようになります。

(A -> B、EF -> G、EF -> H、ACD -> E、ACDF -> G)

于 2015-05-01T07:39:32.097 に答える