1. はじめに
SQL でテーブルを定義するときに PRIMARY KEY や UNIQUE を指定すると思いますが,皆さんはリレーション(スキーマ)のキー(key)を一体どのようにして見つけていますか?
そもそも,「キーとはタップルの一意識別能力を有する属性の極小組」であることは,リレーショナルデータモデルを学んだ人ならばデータベースのイロハといった事項でしょうが,具体的にリレーション(スキーマ)と所与の関数従属性の集合が指定されたときに,キーを求めなさいと言われると,結構難儀する場合もあるのではないか,と思います.
本稿では,次に示す 3 つの問題について改めて論じてみます.
- 候補キーを 1 つ見つける.
- 候補キーをすべて見つける.
- 候補キーの数の上限は?
2. 基礎的事項
リレーションスキーマ R とはリレーション名 R と属性のリスト A1, A2, …, An からなり,R(A1, A2, …, An)と表されます.ΩR (= { A1, A2, …, An })で R の全属性集合を表すことにします.R をリレーションスキーマとするとき,R に所与の(given)関数従属性の集合 F={f1, f2, …, fp},ここに (∀i= 1, 2, …, p)(fi=Xi→Yi ∧ Xi, Yi⊆Ω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(0)=X とおく.
ステップ 2 X(i)=X(i-1)∪{Z | Y→Z∈F ∧ Y⊆X(i-1) } (i≧1)
ステップ 3 もし X(i)=X(i-1) なら X+=X(i-1) とおく.そうでなければステップ 2 に行く.
ここで,関数従属性と閉包の関係性について記します.
【命題 1】
リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとする.X, Y⊆ΩR とするとき,次が成立する.
X→Y iff Y⊆X+
(証明)
X+ を求めるアルゴリズムでは,一般に X(i)=X(i-1)∪{Z | Y→Z∈F ∧ Y⊆X(i-1)} であるので,X(0)={X}としたとき X→Y∈F ならば Y はX(1)の元となり,結果的に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 つの立場から考察していきます.
(1) | リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとき,R の候補キーを(何でもよいので)1つ見つける. |
(2) | リレーションスキーマ R に所与の関数従属性の集合 F が指定されているとき,R の候補キーをすべて見つける |
3. 候補キーを 1 つ見つける
【問題 1】(候補キーを 1 つ見つける)
リレーションスキーマ R に所与の関数従属性の集合 F={f1, f2, …, fp}が指定されているとき,R の候補キーを(何でもよいので)1 つ求めなさい.
(解答)
リレーションスキーマ R の全属性集合 ΩR は R のスーパーキーであることに着眼する.すると,次に示すアルゴリズムで候補キーが 1 つ見つかる.
【候補キーを 1 つ見つけるアルゴリズム】
ステップ 1 | K=ΩR とおく. |
ステップ 2 | 属性A∈K を1つ選び,(K-A)+ を計算する.もし,(K-A)+=ΩR ならば,K=K-A とおいてステップ 2 に戻る.そうでなければ,K が求める候補キーである.ここに,-は差集合演算を表す. |
このアルゴリズムの正当性は明らかでしょう.注意するべき点は,どのような候補キーが返されるかはステップ 2 で取り除かれた属性 A の選択のされ方によることです.このような曖昧性はありますが,必ず候補キーは 1 つ返ってきます.このアルゴリズムの時間計算量は閉包を計算するアルゴリズムの時間計算量に依存し,それは多項式オーダーとなり扱いやすい問題です.
4. 候補キーをすべて見つける
【問題 2】(候補キーをすべて見つける)
リレーションスキーマ R に所与の関数従属性の集合 F={f1, f2, …, fp}が指定されているとき,R の候補キーをすべて求めなさい.
(解答)
R の候補キーをすべて求めるアルゴリズムを以下に示します.
【候補キーをすべて見つけるアルゴリズム】
ステップ 1 | ΩR の冪集合 2ΩR の元をその構成要素の数 i (i=0, 1, …, |ΩR|)で類別して,S0,S1,…, S|ΩR|を作る.すなわち,2ΩR = S0∪S1∪ … ∪S|ΩR|である. |
ステップ 2 |
i∈{1, …, |ΩR|}に対して i=1 から始めて順次,次の処理をする. Si={Xi,1, Xi,2, …, Xi,ni}の各元 Xi,j に対して Xi,j+ を計算する.ここに,ni=|ΩR|Ci (=|ΩR|! / (i!×(|ΩR|-i)!)) は組合せ(combination)を表す.このとき,もし Xi,j+=ΩRなら,Xi,j は候補キーである.このとき,各|ΩR|≧k≧i+1であるkに対して,Sk=Sk-{Y∈Sk|Y⊃Xi,j }とSk を再編成する(つまり,Xi,j を含むスーパーキーをこの後の候補キー探索処理から除外する). |
ステップ 3 | ステップ 2 の操作が終了した時点で得られていた候補キーが求める結果である. |
このアルゴリズムは ΩR のすべての部分集合(空集合を除く)について,その濃度の小さい方から大きい方の順,すなわちS1,S2,…, S|ΩR| の順に,Si の各元が候補キーとなっているか否かを総当たりで検証していくこと(Siの任意の 2元 Xi,j と Xi,k が包含関係になることはないのでどちらかが他方のスーパーキーになることはないことに注目すること),そして Skを再編成することでスーパーキーを除外していることから,その正当性は明らかでしょう.しかし,それが故に,その時間計算量は指数オーダーとなり,扱いにくい問題(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 の元を構成要素数で類別して,Si,i=0~5を作ると, S0=Φ(空集合),S1={A,B,C,D,E},S2={AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, ABC},S3={ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE},S4={ABCD, ABCE, ABDE, ACDE, BCDE},S5={ABCDE}となる.すなわち,2ΩR = S0∪S1∪S2∪S3∪S4∪S5である.
続いて,ステップ 2 の処理をする.
まず,S1 に対してステップ 2 の処理をすると,結果は次のとおりである.
A+=A,B+=B,C+=C,D+=ADE,E+=E.つまり,候補キーはない.
続いて,S2 に対しての処理結果は次のとおりである.
AB+=ABCDE, AC+=AC, AD+=ADE, AE+=AE, BC+=ABCDE, BD+=ABCDE, BE+=BE, CD+=ACDE, CE+=CE, DE+=ADE.つまり,AB,BC,BD が候補キーであることが分かった.そこで,S3~S5 の再編作業を行う.まず,S3 については,AB,BC,BD を含む要素を S3から除外して改めて S3 を作成すると次のとおりである.S3={ACD, ACE, ADE, CDE}.S4 と S5 に対しても同様な操作を行い,S4={ACDE}, S5=Φ となる.
続いて,再編成された S3 に対してステップ 2 の処理をすると次のとおりである.
ACD+=ACDE, ACE+=ACE, ADE+=ADE, CDE+=ACDE.つまり,候補キーはない.
続いて,S4 の処理を行うと,ACDE+=ACDE であり,候補キーはない.
S5=Φ なので候補キーはない.
よって,AB,BC,BD が R の候補キーの全てであることが分かる.
【例題 2】(2 の冪乗個の候補キーが見つかる例)
リレーションスキーマ R(A1, A2, B1, B2)に所与の関数従属性 Ai→Bi,Bi→Ai (i=1, 2)が指定されているとする.R の候補キーをすべて求めなさい.
(解答)
ΩR={A1, A2, B1, B2}とすると,S0=Φ,S1={A1, A2, B1, B2},S2={ A1A2, A1B1, A1B2, A2B1, A2B2, B1B2},S3={A1A2B1, A1A2B2, A1B1B2, A2B1B2},S4={ A1A2B1B2}となる.
そこで,S1 の各元に対してその閉包を計算する.Ai+=AiBi (i=1,2),Bi+=AiBi (i=1,2)であり,候補キーではない.そこで,S2 の各元に対してその閉包を計算する.A1A2+=A1A2B1B2, A1B1+=A1B1, A1B2+=A1A2B1B2, A2B1+=A1A2B1B2, A2B2+=A2B2, B1B2+=A1A2B1B2となる.従って,A1A2, A1B2, A2B1, B1B2 が候補キーであることが分かる.S3 の再編作業を行うと S3 は Φ となるので,ここで処理が終了する.
例題 2 を一般化してすべての候補キーを求める問題の時間計算量について補足説明を行います.リレーションスキーマ R(A1, A2, ···, An, B1, B2, ・・・, Bn)に所与の関数従属性集合 F = {Ai→Bi, Bi→Ai|i∈{1, 2, …, n}}が指定された場合,R は,A1A2・・・An, B1A2・・・An, A1B2A3・・・An, ・・・, B1B2・・・Bnと 2n個の候補キーを有することになるので,n が大きくなると実用的でなくなります.つまり,例題 2 では n=2 なので候補キーの数は 22=4 で済みましたが,このようなタイプの関数従属性集合 F を指定されたリレーションスキーマ R の候補キーの数は 2nなので,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 で 5C⌊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 でしたが,22<4C2=6 とこの結果に符合しています.
6. おわりに
リレーションの候補キーを求める問題を論じました.リレーションスキーマに所与の関数従属性集合が指定されたとき,候補キーを 1 つ見つけるためのアルゴリズムと,候補キーをすべて見つけるアルゴリズムを提示しました.上に見たように,同じく候補キーを求める問題ではあるのですが,「候補キーを 1 つ見つける問題」の時間計算量は多項式オーダーなので扱いやすい問題ですが,「候補キーをすべて見つける問題」の時間計算量は指数オーダーとなり扱いにくい問題であることを示しました.つまり,すべての候補キーを求めようとすると,リレーションスキーマの全属性数が小さいときには問題となりませんが,それが大きくなるととてつもない時間を要することとなり,現実的ではなくなるということです.とりあえず,候補キーが「1 つ」見つかればよいというなら話は簡単そうですが,「すべて」と言われると気長に根気よく見つけていくしか術はなさそうですね.
【文献】
[1]
増永良文.リレーショナルデータベース入門[第3版].サイエンス社,2017. |
[2]
J. Demetrovics. On the equivalence of candidate keys with Sperner systems. Acta Cybernetica 4, pp.247-252, 1979. |
[3]
J. Demetrovics and G.O.H. Katona. A survey of some combinatorial results concerning functional dependencies in database relations. Annals of Mathematics and Artificial Intelligence 7, pp.63-82, 1993. |