増永教授のDB特論④「候補キーの見つけ方」

1. はじめに

 SQL でテーブルを定義するときに PRIMARY KEY や UNIQUE を指定すると思いますが，皆さんはリレーション（スキーマ）のキー（key）を一体どのようにして見つけていますか？
 そもそも，「キーとはタップルの一意識別能力を有する属性の極・小・組」であることは，リレーショナルデータモデルを学んだ人ならばデータベースのイロハといった事項でしょうが，具体的にリレーション（スキーマ）と所与の関数従属性の集合が指定されたときに，キーを求めなさいと言われると，結構難儀する場合もあるのではないか，と思います．
 本稿では，次に示す 3 つの問題について改めて論じてみます．

• 候補キーを 1 つ見つける．
• 候補キーをすべて見つける．
• 候補キーの数の上限は？

2. 基礎的事項

 リレーションスキーマ R とはリレーション名 R と属性のリスト A₁, A₂, _…, A_n からなり，R(A₁, A₂, _…, A_n)と表されます．Ω_R (= { A₁, A₂, _…, A_n })で R の全属性集合を表すことにします．R をリレーションスキーマとするとき，R に所与の（given）関数従属性の集合 F＝{f₁, f₂, _…, f_p}，ここに (∀_i= 1, 2, _…, p)(f_i=X_i→Y_i ∧ X_i, Y_i⊆Ω_R)，を指定できます．なお，一般に X, Y を集合とするとき，X⊆Y は X が Y の部分集合であることを，X⊂Y は X が Y の真部分集合（proper subset）であることを表します．

【定義 1】（候補キー）
 K⊆Ω_R がリレーションスキーマ R の候補キー（candidate key）と言われるのは，次が成立するときをいう．ここに，∀R∈R は「R の任意のインスタンス R に対して」を表す．

(∀R∈R)((∀t, t’∈R)(t[K]=t’[K] ⇒ t=t’) ∧

(∀H⊂K)(∃R∈R) ((∃t, t’∈R)(t[H]=t’[H] ∧ t≠t’)))

 リレーションは有限個のドメインの直積の有限部分集合と定義されているので ，いかなるリレーションにも候補キーがないということはなく，最も極端なケースはリレーションスキーマ R の全属性集合 Ω_R が候補キーとなることも皆さんにとっては常識でしょう．
 組織体管理者（enterprise administrator, すなわち組織のデータベース設計に責任を有する個人またはグループ）は，候補キーが一つしかなければそれを，複数ある場合にはデータベース構築の目的に合っていると考えられるものを一つを選んで主キー（primary key）とします．主キーとされなかった候補キーと主キーとの違いは，主キーにはキー制約（key constraint）が課せられることにあることもよくご存じのことでしょう．また，何らかの候補キーを含む属性集合をスーパーキー（super key）と言います．

【定義 2】（キー制約）
 K がリレーションスキーマ R の主キーであるならば，次が成立しなければならない．ここに，NULLは空（すなわち，値がないこと）を表す．

(∀R∈R) (∀t∈R)((∀A∈K)(t[A] IS NOT NULL))

 簡単な例を示すと，リレーションスキーマ 社員(社員番号，社員名，所属，給与，マイナンバー)では，社員番号 や マイナンバー は候補キーでしょうが，もし 社員番号 を主キーと選べば リレーション 社員 のいかなるタップルの社員番号がNULLとなってはいけないというデータベースの一貫性制約が「キー制約」です．このとき，勿論，マイナンバー にも社員を一意識別する力はあるものの，主キーと指定されなかったので，NULLであってもよいということです．主キーとそう指定されなかった候補キーとの違いはこの一点です．
 なお，主キーか否かを問わず，候補キーを構成している属性をキー属性と言い，キー属性でない属性を非キー属性と言います．候補キーと主キーを特段に区別する必要を感じないときには単にキーということも多く，また特段に混乱をきたさないと考えられる場合には本来リレーションスキーマと書くべきところをリレーションと書いているところもあるのであらかじめ断っておきます．

 さて，定義1で候補キーの定義を与えましたが，その定義を関数従属性（functional dependency, FD）を使って表現し直すことができます．多少くどいかもしれませんが，その定義を記しておきます．

【定義 3】（関数従属性，FD）
 X，Y をリレーションスキーマ R の属性集合 Ω_R の部分集合とするとき，X から Y への FD がある，このことを X→Y と書く，とは次が成立するときをいう．ここに，iff は if and only if（必要かつ十分）を，⇒ は論理的含意を表し，X→Y の X を決定子（determinant），Y を被決定子（resultant）という．

X→Y iff (∀R∈R)(∀t, t’∈R)( t[X]=t’[X] ⇒ t[Y]=t’[Y])

 また，FD については，Armstrong の公理系が成立することも皆さん，よくご存じのことと思います．

【公理 1】（Armstrong の公理系）
 A1. Y⊆X ならば，X→Y である（反射律）．
 A2. X→Y かつ Z⊆W ならば，X∪W→Y∪Z である（添加律）．
 A3. X→Y かつ Y→Z ならば，X→Z である（推移律）．

 さて，定義 1 で候補キーの定義を与えましたが，FD を使ってこの定義を表現し直してみると，次のようになります．

【定義 4】（FD を用いた候補キーの定義）
 K⊆Ω_R がリレーションスキーマ R の候補キーと言われるのは，次が成立するときをいう．ここに，↛ は FD が成立しないことを表す．

(K→Ω_R) ∧ (∀H⊂K)(H↛Ω_R)

 さらに，この定義はリレーションスキーマ R に所与の関数従属性の集合 F が指定されたとき，属性集合 X の閉包（closure），これを X⁺ と記す，を用いて以下のように書き直せます．

 まず，リレーションスキーマ R に所与の関数従属性の集合 F が指定されたとき，R の属性集合 X の閉包の求め方を示しておきます．このアルゴリズムの時間計算量（time complexity）はO(n×p)，ここにn=|Ω_R|，p=|F|，と多項式オーダーであり扱いやすい問題（tractable problem）です．したがって X⁺ は問題なく求められます．

 【X⁺ を求めるアルゴリズム】

ステップ 1　X⁽⁰⁾=X とおく．

ステップ 2　X⁽ⁱ⁾=X^(i-1)∪{Z | Y→Z∈F ∧ Y⊆X^(i-1) } (i≧1)

ステップ 3　もし X⁽ⁱ⁾=X^(i-1) なら X^＋=X^(i-1) とおく．そうでなければステップ 2 に行く．

 ここで，関数従属性と閉包の関係性について記します．

【命題 1】
 リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとする．X, Y⊆Ω_R とするとき，次が成立する．

X→Y iff Y⊆X⁺

（証明）
 X⁺ を求めるアルゴリズムでは，一般に X⁽ⁱ⁾=X^(i-1)∪{Z | Y→Z∈F ∧ Y⊆X^(i-1)} であるので，X⁽⁰⁾={X}としたとき X→Y∈F ならば Y はX⁽¹⁾の元となり，結果的にY⊆X⁺である．逆に，Y⊆X⁺ならば，X⁺の元は X に関数従属した属性からなるので，X→X⁺である．Y⊆X⁺なので反射律から X⁺→Y が成立する．従って，推移律から X→Y である．

 そうすると，定義 4で与えた FD を用いた候補キーの定義は閉包の概念を用いて定義 5 のように書き直せます．これは，命題 1 より，K→Ω_R iff K⁺=Ω_R が成立することから明らかでしょう．

【定義 5】（閉包の概念を用いた候補キーの定義）
 リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとする．K⊆Ω_R が R の候補キーと言われるのは，次が成立するときをいう．

(K⁺=Ω_R) ∧ (∀H⊂K)(H⁺≠Ω_R)

 ここまで準備完了です．では，続けて，リレーションスキーマの候補キーを求める問題を考えてみましょう．2 つの立場から考察していきます．

3. 候補キーを 1 つ見つける

【問題 1】（候補キーを 1 つ見つける）
 リレーションスキーマ R に所与の関数従属性の集合 F＝{f₁, f₂, _…, f_p}が指定されているとき，R の候補キーを（何でもよいので）1 つ求めなさい．
（解答）
 リレーションスキーマ R の全属性集合 Ω_R は R のスーパーキーであることに着眼する．すると，次に示すアルゴリズムで候補キーが 1 つ見つかる．

 【候補キーを 1 つ見つけるアルゴリズム】

 このアルゴリズムの正当性は明らかでしょう．注意するべき点は，どのような候補キーが返されるかはステップ 2 で取り除かれた属性 A の選択のされ方によることです．このような曖昧性はありますが，必ず候補キーは 1 つ返ってきます．このアルゴリズムの時間計算量は閉包を計算するアルゴリズムの時間計算量に依存し，それは多項式オーダーとなり扱いやすい問題です．

4. 候補キーをすべて見つける

【問題 2】（候補キーをすべて見つける）
 リレーションスキーマ R に所与の関数従属性の集合 F＝{f₁, f₂, _…, f_p}が指定されているとき，R の候補キーをすべて求めなさい．

（解答）
 R の候補キーをすべて求めるアルゴリズムを以下に示します．

【候補キーをすべて見つけるアルゴリズム】

 このアルゴリズムは Ω_R のすべての部分集合（空集合を除く）について，その濃度の小さい方から大きい方の順，すなわちS₁，S₂，…, S_|ΩR| の順に，S_i の各元が候補キーとなっているか否かを総当たりで検証していくこと（S_iの任意の 2元 X_i,j と X_i,k が包含関係になることはないのでどちらかが他方のスーパーキーになることはないことに注目すること），そして S_kを再編成することでスーパーキーを除外していることから，その正当性は明らかでしょう．しかし，それが故に，その時間計算量は指数オーダーとなり，扱いにくい問題（intractable problem）となります．

 さて，復習がてらに上述のアルゴリズムを使って，候補キーをすべて求める問題と解を 2 つ例示しましょう．

【例題 1】（データベーススペシャリスト平成29年春期 午前Ⅱ 問4）
関係 R(A，B，C，D，E)において，
 関数従属 {A，B}→C，{B，C}→D，D→{A，E}
が成立する．これらから決定できるRの候補キーを全て挙げたものはどれか．
 {A，B，C}
 {A，B}，{B，C}
 {A，B}，{B，C}，{B，D}
 {B，C}，{C，D}

（解答）
 {A，B}，{B，C}，{B，D} が正解である．
 これを本稿に示した「候補キーをすべて見つけるアルゴリズム」に則り示すと次の通りである．なお，見やすさのために，{A，B} を AB，{A，B}→C を AB→C という具合に表現し直している．
 まず，ステップ 1 の処理をする．
 Ω_R={ A，B，C，D，E }なので，|Ω_R|=5，Ω_R の冪べき集合 2^Ω_R の元を構成要素数で類別して，S_i，i=0～5を作ると， S₀=Φ（空集合），S₁={A，B，C，D，E}，S₂={AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, ABC}，S₃={ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE}，S₄={ABCD, ABCE, ABDE, ACDE, BCDE}，S₅={ABCDE}となる．すなわち，2^Ω_R = S₀∪S₁∪S₂∪S₃∪S₄∪S₅である．
 続いて，ステップ 2 の処理をする．
 まず，S₁ に対してステップ 2 の処理をすると，結果は次のとおりである．
 A⁺=A，B⁺=B，C⁺=C，D⁺=ADE，E⁺=E．つまり，候補キーはない．
 続いて，S₂ に対しての処理結果は次のとおりである．
 AB⁺=ABCDE, AC⁺=AC, AD+=ADE, AE⁺=AE, BC⁺=ABCDE, BD⁺=ABCDE, BE⁺=BE, CD⁺=ACDE, CE⁺=CE, DE⁺=ADE．つまり，AB，BC，BD が候補キーであることが分かった．そこで，S₃～S₅ の再編作業を行う．まず，S₃ については，AB，BC，BD を含む要素を S₃から除外して改めて S₃ を作成すると次のとおりである．S₃={ACD, ACE, ADE, CDE}．S₄ と S₅ に対しても同様な操作を行い，S₄={ACDE}, S₅=Φ となる．
 続いて，再編成された S₃ に対してステップ 2 の処理をすると次のとおりである．
 ACD⁺=ACDE, ACE⁺=ACE, ADE⁺=ADE, CDE⁺=ACDE．つまり，候補キーはない．
 続いて，S₄ の処理を行うと，ACDE⁺=ACDE であり，候補キーはない．
 S₅=Φ なので候補キーはない．
 よって，AB，BC，BD が R の候補キーの全てであることが分かる．

【例題 2】（2 の冪べき乗個の候補キーが見つかる例）
 リレーションスキーマ R(A₁, A₂, B₁, B₂)に所与の関数従属性 A_i→B_i，B_i→A_i (i=1, 2)が指定されているとする．R の候補キーをすべて求めなさい．

（解答）
 Ω_R={A₁, A₂, B₁, B₂}とすると，S₀=Φ，S₁={A₁, A₂, B₁, B₂}，S₂={ A₁A₂, A₁B₁, A₁B₂, A₂B₁, A₂B₂, B₁B₂}，S₃={A₁A₂B₁, A₁A₂B₂, A₁B₁B₂, A₂B₁B₂}，S₄={ A₁A₂B₁B₂}となる．
 そこで，S₁ の各元に対してその閉包を計算する．A_i⁺=A_iB_i (i=1,2)，B_i⁺=A_iB_i (i=1,2)であり，候補キーではない．そこで，S₂ の各元に対してその閉包を計算する．A₁A₂⁺=A₁A₂B₁B₂, A₁B₁⁺=A₁B₁, A₁B₂⁺=A₁A₂B₁B₂, A₂B₁⁺=A₁A₂B₁B₂, A₂B₂⁺=A₂B₂, B₁B₂⁺=A₁A₂B₁B₂となる．従って，A₁A₂, A₁B₂, A₂B₁, B₁B₂ が候補キーであることが分かる．S₃ の再編作業を行うと S₃ は Φ となるので，ここで処理が終了する．

 例題 2 を一般化してすべての候補キーを求める問題の時間計算量について補足説明を行います．リレーションスキーマ R(A₁, A₂, ···, A_n, B₁, B₂, ・・・, B_n)に所与の関数従属性集合 F = {A_i→B_i, B_i→A_i|i∈{1, 2, _…, n}}が指定された場合，R は，A₁A₂・・・A_n, B₁A₂・・・A_n, A₁B₂A₃・・・A_n, ・・・, B₁B₂・・・B_nと 2ⁿ個の候補キーを有することになるので，n が大きくなると実用的でなくなります．つまり，例題 2 では n=2 なので候補キーの数は 2²=4 で済みましたが，このようなタイプの関数従属性集合 F を指定されたリレーションスキーマ R の候補キーの数は 2ⁿなので，n が大きくなるにつれて，それ数え上げるには指数時間かかり，一般にすべての候補キーを求める問題は扱いにくい問題であることが直感できると思います．

5. 候補キーの数の上限は？

 1 つのリレーションスキーマには幾つ候補キーが存在しうるのか，その上限について次の結果[2, 3]が示されているので，紹介しておきたいと思います．

【命題 2】（候補キーの数の上限）
 リレーションスキーマ R の候補キーの数は高々 _nC_⌊n/2⌋である．ここに，C は組合せ，⌊r⌋ は r を越えない最大の自然数を表し，|Ω_R|=n とする．
（証明）
 濃度 n の集合 S において，候補キーの集合はお互いが集合の包含関係にないという意味でスパナー族（Sperner family）をなし，従って，比較不可能な S の部分集合の数は高々 _nC_⌊n/2⌋ となる．

 例えば，n=2 なら _nC_⌊n/2⌋=2 であるので，候補キーの数は高々 2 です．R(A, B)とすれば，もし上限の 2 個の候補キーがあった場合には，それらは {A} と {B} です．n=3 なら _nC_⌊n/2⌋=3 であるので，R(A, B, C)とすれば，もし上限の 3 個の候補キーがあった場合には，それらは {A, B}，{A, C}，{B, C} です．n=4 なら _nC_⌊n/2⌋=6 であるので，R(A, B, C, D)とすれば，もし上限の 6 個の候補キーがあったとすれば，それらは {A, B}，{A, C}，{A, D}，{B, C}，{B, D}，{C, D}です．R(A, B, C, D, E)とすれば，n=5 で ₅C_⌊5/2⌋=10 であるので，もし上限の 10 個の候補キーがあったとすれば，それらは {A, B}，{A, C}，{A, D}，{A, E}, {B, C}，{B, D}，{B, E}, {C, D}, {C, E}, {D, E} です．例題 2 の候補キーの数は 4 でしたが，2²＜₄C₂=6 とこの結果に符合しています．

6. おわりに

 リレーションの候補キーを求める問題を論じました．リレーションスキーマに所与の関数従属性集合が指定されたとき，候補キーを 1 つ見つけるためのアルゴリズムと，候補キーをすべて見つけるアルゴリズムを提示しました．上に見たように，同じく候補キーを求める問題ではあるのですが，「候補キーを 1 つ見つける問題」の時間計算量は多項式オーダーなので扱いやすい問題ですが，「候補キーをすべて見つける問題」の時間計算量は指数オーダーとなり扱いにくい問題であることを示しました．つまり，すべての候補キーを求めようとすると，リレーションスキーマの全属性数が小さいときには問題となりませんが，それが大きくなるととてつもない時間を要することとなり，現実的ではなくなるということです．とりあえず，候補キーが「1 つ」見つかればよいというなら話は簡単そうですが，「すべて」と言われると気長に根気よく見つけていくしか術すべはなさそうですね．

【文献】

[1]

[2]

[3]