多値依存関係
関係内の2つの属性セット間の完全な制約

データベース理論では、多値依存関係は、関係内の 2 つの属性セット間の完全な制約です。

関数従属性とは対照的に、多値従属性では、関係に特定のタプルが存在することが必須となります。したがって、多値従属性はタプル生成従属性の特殊なケースです。多値従属性は、4NFデータベース正規化において重要な役割を果たします。

多値依存関係は結合依存関係の特殊なケースであり、関係する値のセットが 2 つだけであり、つまりバイナリ結合依存関係です。

関係に少なくとも 3 つの属性(X、Y、Z など)があり、X の値に対して、Y の値のセットが明確に定義され、Z の値のセットも明確に定義されている場合、多値の依存関係が存在します。ただし、Y の値のセットは Z のセットとは独立しており、その逆も同様です。

正式な定義

正式な定義は次のとおりです。[1]

を関係スキーマとし、と を属性集合とします。任意の正当な関係と と のすべての組のペア（ ）に対して、 と が存在し、が以下の条件を満たす場合、 が多値依存関係（「多重決定」）となります。 R {\displaystyle R} α ⊆ R {\displaystyle \alpha \subseteq R} β ⊆ R {\displaystyle \beta \subseteq R} α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } α {\displaystyle \alpha} β {\displaystyle \beta} R {\displaystyle R} r （ R ） {\displaystyle r(R)} t 1 {\displaystyle t_{1}} t 2 {\displaystyle t_{2}} r {\displaystyle r} t 1 [ α ] ＝ t 2 [ α ] {\displaystyle t_{1}[\alpha]=t_{2}[\alpha]} t 3 {\displaystyle t_{3}} t 4 {\displaystyle t_{4}} r {\displaystyle r}

t 1 [ α ] ＝ t 2 [ α ] ＝ t 3 [ α ] ＝ t 4 [ α ] t 1 [ β ] ＝ t 3 [ β ] t 2 [ β ] ＝ t 4 [ β ] t 1 [ R ∖ （ α ∪ β ） ] ＝ t 4 [ R ∖ （ α ∪ β ） ] t 2 [ R ∖ （ α ∪ β ） ] ＝ t 3 [ R ∖ （ α ∪ β ） ] {\displaystyle {\begin{matrix}t_{1}[\alpha ]=t_{2}[\alpha ]=t_{3}[\alpha ]=t_{4}[\alpha ]\\t_{1}[\beta ]=t_{3}[\beta ]\\t_{2}[\beta ]=t_{4}[\beta ]\\t_{1}[R\setminus (\alpha \cup \beta )]=t_{4}[R\setminus (\alpha \cup \beta )]\\t_{2}[R\setminus (\alpha \cup \beta )]=t_{3}[R\setminus (\alpha \cup \beta )]\end{matrix}}}

非公式には、 の値が全体として に等しいタプルを で表す場合、にタプルと が存在するときは常に、にタプルとも存在するはずです。 （ × 、 y 、 z ） {\displaystyle (x,y,z)} α 、 {\displaystyle \alpha ,} β 、 {\displaystyle \beta ,} R − α − β {\displaystyle R-\alpha -\beta } × 、 {\displaystyle x,} y 、 {\displaystyle y,} z {\displaystyle z} （ 1つの 、 b 、 c ） {\displaystyle (a,b,c)} （ 1つの 、 d 、 e ） {\displaystyle (a,d,e)} r {\displaystyle r} （ 1つの 、 b 、 e ） {\displaystyle (a,b,e)} （ 1つの 、 d 、 c ） {\displaystyle (a,d,c)} r {\displaystyle r}

多値依存関係は、以下のように模式的に表すことができます。

タプル α β R ∖ （ α ∪ β ） t 1 1つの 1 。 。 1つの n b 1 。 。 b メートル d 1 。 。 d け t 2 1つの 1 。 。 1つの n c 1 。 。 c メートル e 1 。 。 e け t 3 1つの 1 。 。 1つの n b 1 。 。 b メートル e 1 。 。 e け t 4 1つの 1 。 。 1つの n c 1 。 。 c メートル d 1 。 。 d け {\displaystyle {\begin{matrix}{\text{tuple}}&\alpha &\beta &R\setminus (\alpha \cup \beta )\\t_{1}&a_{1}..a_{n}&b_{1}..b_{m}&d_{1}..d_{k}\\t_{2}&a_{1}..a_{n}&c_{1}..c_{m}&e_{1}..e_{k}\\t_{3}&a_{1}..a_{n}&b_{1}..b_{m}&e_{1}..e_{k}\\t_{4}&a_{1}..a_{n}&c_{1}..c_{m}&d_{1}..d_{k}\end{matrix}}}

例

大学のコース、そのコースで推奨されている書籍、そのコースを教える講師の関係を示す次の例を考えてみましょう。

大学のコース
コース 本 講師
ああ シルバーシャッツ ジョン・D
ああ ネダーペルト ジョン・D
ああ シルバーシャッツ ウィリアムM
ああ ネダーペルト ウィリアムM
ああ シルバーシャッツ クリスチャンG
ああ ネダーペルト クリスチャンG
オソ シルバーシャッツ ジョン・D
オソ シルバーシャッツ ウィリアムM

コースに割り当てられた講師とコースに割り当てられた書籍は互いに独立しているため、このデータベース設計には多値の依存関係があります。つまり、AHA コースに新しい書籍を追加する場合は、そのコースの講師ごとに 1 つのレコードを追加する必要があり、その逆も同様です。
正式に言うと、この関係には 2 つの多値の依存関係があります。{course}   {book} と、それと同等の {course}   {lecturer} です。 したがって、多値の依存関係を持つデータベースは冗長性を示します。データベースの正規化では、第 4 正規形では、すべての非自明な多値の依存関係X Yについて、Xがスーパーキーである必要があります。多値の依存関係X Y は、 Y がXのサブセットである場合、または が関係の属性の集合全体である 場合に自明です。 ↠ {\displaystyle \twoheadrightarrow} ↠ {\displaystyle \twoheadrightarrow}
  ↠ {\displaystyle \twoheadrightarrow}   ↠ {\displaystyle \twoheadrightarrow} X ∪ はい {\displaystyle X\cup Y}

プロパティ

  • もし、 α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } α ↠ R − β {\displaystyle \alpha \twoheadrightarrow R-\beta }
  • もし、そして、ならば α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } γ ⊆ δ {\displaystyle \gamma \subseteq \delta } α δ ↠ β γ {\displaystyle \alpha \delta \twoheadrightarrow \beta \gamma }
  • かつならば、 α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } β ↠ γ {\displaystyle \beta \twoheadrightarrow \gamma } α ↠ γ − β {\displaystyle \alpha \twoheadrightarrow \gamma -\beta }

以下の場合にも機能依存関係が関係します。

  • もし、 α → β {\displaystyle \alpha \rightarrow \beta } α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta }
  • かつならば、 α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } β → γ {\displaystyle \beta \rightarrow \gamma } α ↠ γ − β {\displaystyle \alpha \twoheadrightarrow \gamma -\beta }

上記のルールは健全かつ完全です。

  • R を( X ,  Y ) と ( X ,  R  −  Y )に分解することは、RでX Y が成り立つ 場合にのみ、ロスレス結合分解となります。  ↠ {\displaystyle \twoheadrightarrow}  
  • すべてのFD (機能的依存性) はMVD (多値依存性) です。X がY の場合、X に一致するタプル間で Y を交換しても新しいタプルは作成されないためです。 → {\displaystyle \rightarrow}
  • 分割は成立しません。FDと同様に、MVDの左側を分割することは一般的にできません。しかし、FDとは異なり、右側も分割できません。右側に複数の属性を残しておく必要がある場合もあります。
  • MVD の集合の閉包とは、次の規則 (アームストロングの公理)を使用して推論できるすべての MVD の集合です。
    • 補集合：X YならばX R - Y ↠ {\displaystyle \twoheadrightarrow} ↠ {\displaystyle \twoheadrightarrow}
    • 拡張：X Y、Z Wの場合、XW YZ ↠ {\displaystyle \twoheadrightarrow} ⊆ {\displaystyle \subseteq } ↠ {\displaystyle \twoheadrightarrow}
    • 推移性：X YかつY Zならば、X Z - Y ↠ {\displaystyle \twoheadrightarrow} ↠ {\displaystyle \twoheadrightarrow} ↠ {\displaystyle \twoheadrightarrow}
    • レプリケーション: X Yの場合、X Y → {\displaystyle \rightarrow} ↠ {\displaystyle \twoheadrightarrow}
    • 合体：X YとWがW Y = 、W Z、Z Yの場合、X Z ↠ {\displaystyle \twoheadrightarrow} ∃ {\displaystyle \exists } ∩ {\displaystyle \cap} ∅ {\displaystyle \emptyset } → {\displaystyle \rightarrow} ⊆ {\displaystyle \subseteq } → {\displaystyle \rightarrow}

定義

完全な制約
データベース内のすべての属性について何かを表現する制約。(埋め込み制約とは対照的)。多値依存関係が完全な制約であることは、その定義からわかります。つまり、属性について何かを述べています。 R − β {\displaystyle R-\beta }
タプル生成依存関係
関係内に特定のタプルが存在することを明示的に要求する依存関係。
単純な多値依存関係 1
関係のすべての属性、すなわち を含む多値依存関係。 自明な多値依存関係は、タプルおよびに対して、およびと等しいタプルおよび を意味します。 R ＝ α ∪ β {\displaystyle R=\alpha \cup \beta } t 1 {\displaystyle t_{1}} t 2 {\displaystyle t_{2}} t 3 {\displaystyle t_{3}} t 4 {\displaystyle t_{4}} t 1 {\displaystyle t_{1}} t 2 {\displaystyle t_{2}}
単純な多値依存関係 2
対象となる多値依存関係。 β ⊆ α {\displaystyle \beta \subseteq \alpha }

参考文献

  1. ^ シルバーシャッツ、アブラハム、コルト、スダルシャン (2006).データベースシステムコンセプト（第5版）.マグロウヒル. p. 295. ISBN 0-07-124476-X。
  • 多値依存関係とリレーショナルデータベースの新しい正規形 (PDF) - Ronald Fagin、IBM 研究所
  • 関数従属性におけるアームストロング関係の構造について (PDF) - CATRIEL BEERI (ヘブライ大学)、MARTIN DOWD (ラトガース大学)、RONALD FAGIN (IBM研究所)、RICHARD STATMAN (ラトガース大学)
  • リレーショナルデータベースにおける多値依存関係に関するFaginの問題について（PDF） - スヴェン・ハートマン、マッセイ大学
Retrieved from "https://en.wikipedia.org/w/index.php?title=Multivalued_dependency&oldid=1319890623"