北川 博之著「データベースシステム（オーム社）」を参考に，データベースシステムの知識をまとめます。
多値従属性の定義
リレーションスキーマ$RS$と属性集合$X,Y\subseteq RS$が与えられたとき，$RS$の任意のインスタンス$R$において
(\forall t\in R)(\forall u\in R)(t[X]{=}u[X]\rarr
&(\exists v\in R)(\exists w\in R)(t[X]{=}u[X]{=}v[X]{=}w[X]\notag\\[0.7em]
&\wedge t[Y]{=}v[Y]\wedge t[RS-XY]{=}w[RS-XY]\notag\\[0.7em]
&\wedge u[Y]{=}w[Y]\wedge u[RS-XY]{=}v[RS-XY])
\end{align}
が成立するとき，多値従属性$X\twoheadrightarrow Y$が成り立つといいます。
多値従属性の英語表記はmultivalued dependencyであるため，MVDと略されます。$Y$と$RS-XY$の対称性から，多値従属性$X\twoheadrightarrow Y$が成り立つならば，多値従属性$X\twoheadrightarrow RS-XY$も成り立ちます。
補足1
非常に難解な定義ですが，紐解いていきましょう。まず，リレーション$R$中の二つのタプル$t,u$に着目します。多値従属性は，$R$から二つのタプルを任意に選んできたときに成立する性質であることを宣言しています。どのような性質かというと，$t$と$u$が属性$X$の値が等しいならば，別の二つのタプル$v,w$が存在する性質です。どのような$v,w$が存在するかというと，
- タプル$v,w$とも，タプル$t,u$と属性$X$の値が等しいこと
- タプル$v$はタプル$t$と属性$Y$の値が等しいこと
- タプル$v$はタプル$u$と属性$Y$以外の値が等しいこと
- タプル$w$はタプル$u$と属性$Y$の値が等しいこと
- タプル$w$はタプル$t$と属性$Y$以外の値が等しいこと
を満たすような$v,w$です。ここまで噛み砕いても抽象的ですので，以下のようなリレーションを考えてみます。
| プロジェクト番号 | 社員番号 | ミーティング日 |
|---|---|---|
| $p_{1}$ | $e_{1}$ | 月 |
| $p_{1}$ | $e_{2}$ | 月 |
| $p_{1}$ | $e_{1}$ | 木 |
| $p_{1}$ | $e_{2}$ | 木 |
| $p_{2}$ | $e_{1}$ | 月 |
| $p_{2}$ | $e_{3}$ | 月 |
| $p_{2}$ | $e_{1}$ | 金 |
| $p_{2}$ | $e_{3}$ | 金 |
このリレーション中の上二つのタプル($p_{1}$,$e_{1}$,月)と($p_{1}$,$e_{2}$,木)に着目します。これらが上の定義における$t,u$に該当します。これらのタプルは{プロジェクト番号}の値がそれぞれ等しいですので，$X$を{プロジェクト番号}，そして残りは適当に$Y$を{社員番号}とします。このとき，別のタプルで定義を満たすような$v,w$が存在する場合は，{プロジェクト番号}$\twoheadrightarrow${社員番号}が成り立つことになります。
$v,w$を見つけてみましょう。$v$から探します。
- タプル$v$はタプル$t$と属性$Y$の値が等しいこと
- タプル$v$はタプル$v$と属性$Y$以外の値が等しいこと
とありますので，$v$のプロジェクト番号は$e_{1}$で，ミーティング日は木となります。そのようなタプルはリレーションに存在するか確認すると，三行目に見つかりました。同様に，$w$を探します。
- タプル$w$はタプル$u$と属性$Y$の値が等しいこと
- タプル$w$はタプル$t$と属性$Y$以外の値が等しいこと
とありますので，$v$のプロジェクト番号は$e_{2}$で，ミーティング日は月となります。そのようなタプルはリレーションに存在するか確認すると，四行目に見つかりました。以上より，定義を満たす$v,w$が見つかりましたので，{プロジェクト番号}$\twoheadrightarrow${社員番号}が成り立つことが分かりました。同様に，先ほど適当に決めた$Y$をミーティング日とすると，{プロジェクト番号}$\twoheadrightarrow${ミーティング日}も成り立つことが分かります。これは，前述の通り定義中の$Y$と$RS-XY$の対称性から明らかともいえます。
以上の議論を踏まえると，多値従属性とは「ある属性$X$の値が等しいような二つのタプルが見つかった場合，$X$以外の属性$Y$と$X,Y$以外の属性の塊$RS{-}XY$に対し，タスキ掛けのように2通りの組み合わせが必ず存在する」ような性質であることが分かります。
補足2
多値従属性は，関数従属性の拡張概念と捉えることができます。実際に，$X\rarr Y$という関数従属性が存在する場合は，$t,u,v,w$の全てのタプルで$(X,Y,RS-XY)$の値が等しくなりますので，定義の条件を満たすような$v,w$は$t,u$自身として多値従属性$X\twoheadrightarrow Y$が存在することになります。
イメージとしては，関数従属性は1対1対応，多値従属性は1対多対応です。
補足3
多値従属性には，分解の過程が進む中で突然出現するという局所多値従属性という性質もあります。例えば，以下のようなリレーションを分解することを考えます。
| プロジェクト番号 | 社員番号 | ミーティング日 | ミーティング数 |
|---|---|---|---|
| $p_{1}$ | $e_{1}$ | 月 | 2 |
| $p_{1}$ | $e_{2}$ | 月 | 1 |
| $p_{1}$ | $e_{1}$ | 木 | 1 |
| $p_{1}$ | $e_{2}$ | 木 | 1 |
| $p_{2}$ | $e_{1}$ | 月 | 2 |
| $p_{2}$ | $e_{3}$ | 月 | 1 |
| $p_{2}$ | $e_{1}$ | 金 | 1 |
| $p_{2}$ | $e_{3}$ | 金 | 1 |
先ほどと同様に考えると，このリレーションには多値従属性が存在しません。そこで，このリレーションを{プロジェクト番号,社員番号,ミーティング日}と{社員番号,ミーティング日,ミーティング数}に分解したとします。このとき，前者は上で挙げたリレーションと同一であり，多値従属性が存在する例になっています。この例から分かる通り，多値従属性は分解の過程が進む中で突然出現するという，関数従属性にはあり得なかった性質を有するため，注意が必要です。
コメント