多値依存関係

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

機能的依存関係とは対照的に、多値依存関係では、関係に特定のタプルが存在する必要があります。したがって、多値依存関係は、タプル生成依存関係の特殊なケースです。多値依存関係は、4NF データベース正規化で役割を果たします。

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

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

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

を関係スキーマとし、とを属性の集合とします。任意の正当な関係と となる と のすべての組のペアに対して、となるとの組が存在する場合、に多値依存関係(「多重決定」) が成立します。 ${\displaystyle R}$${\displaystyle \alpha \subseteq R}$${\displaystyle \beta \subseteq R}$${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle R}$${\displaystyle r(R)}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle r}$${\displaystyle t_{1}[\alpha ]=t_{2}[\alpha ]}$${\displaystyle t_{3}}$${\displaystyle t_{4}}$${\displaystyle 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}}}$

非公式には、 の値が集合的にに等しいタプルを で表す場合、にタプルと が存在するときは常に、にタプルとも存在するはずです。 ${\displaystyle (x,y,z)}$${\displaystyle \alpha ,}$ ${\displaystyle \beta ,}$ ${\displaystyle R-\alpha -\beta }$${\displaystyle x,}$ ${\displaystyle y,}$ ${\displaystyle z}$${\displaystyle (a,b,c)}$${\displaystyle (a,d,e)}$${\displaystyle r}$${\displaystyle (a,b,e)}$${\displaystyle (a,d,c)}$${\displaystyle r}$

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

${\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}}}$

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

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

• もし、${\displaystyle \alpha \twoheadrightarrow \beta }$${\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}$

完全な制約

データベース内のすべての属性について何かを表現する制約。(埋め込み制約とは対照的)。多値依存関係が完全な制約であることは、その定義からわかります。ここでは、属性について何かを述べています。${\displaystyle R-\beta }$

タプル生成依存関係

関係内に特定のタプルが存在することを明示的に要求する依存関係。

単純な多値依存関係 1

関係のすべての属性、つまり を含む多値依存関係。 単純な多値依存関係は、タプルおよびに対して、およびに等しいタプルおよびを意味します。${\displaystyle R=\alpha \cup \beta }$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{3}}$${\displaystyle t_{4}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$

単純な多値依存関係 2

対象となる多値依存関係。${\displaystyle \beta \subseteq \alpha }$

• 多値依存関係とリレーショナル データベースの新しい正規形 (PDF) - Ronald Fagin、IBM 研究所
• 関数従属性のアームストロング関係の構造について (PDF) - CATRIEL BEERI (ヘブライ大学)、MARTIN DOWD (ラトガース大学)、RONALD FAGIN (IBM 研究所)、RICHARD STATMAN (ラトガース大学)
• リレーショナル データベースにおける多値依存関係に関する Fagin の問題について (PDF) - Sven Hartmann、マッセイ大学