読者です 読者をやめる 読者になる 読者になる

Jの衝動書き日記

さらりーまんSEの日記でございます。

第3回 関係表から候補キーを導く手引き

データベースのワンポイント

 今回はデータベースというよりも、関係モデルという理論の話をとりあげる。データベーススペシャリスト試験で必ず出題される苦手な候補キーの導き方を考えてみた。より簡単な方法があるのであれば、是非教えて欲しいところである。

候補キーの作成手順

  1. 関係表Aの属性集合(a,b...)がもつ関数従属性をすべて列挙する
  2. 列挙した関数従属性から独立属性(X→YのX側)をすべて抜き出し、集合を作成する
  3. 作成した集合の要素間に関数従属性がある場合、集合から従属属性(X→YのY側)となる要素を取り除く
  4. 手順3において独立属性にも従属属性にもなる要素が集合内にある場合、その関数従属性が成立する要素のお互いをそれぞれ取り除いた要素の集合をそれぞれ作成し、候補キーとする


 これで、候補キーが作成できる。ここで上記手順3を実施出来た場合、関係表Aは第三正規化を行える。また、作成した候補キーの一部が、関係表Aの候補キー以外の属性集合に関数従属する場合、関係表Aは第二正規化を行える。


 各用語については、ググれカ(略ということで。
 ポイントだけ以下にしめす。

  • 関数従属性

 Xの属性値を決めたときYの属性値も一意に決まる場合、YはXに関数従属しているという。X→Yと表記する。属性Xを独立属性、属性Yを従属属性という。

 関数表のすべての属性を関数従属させる極小の属性集合のこと。ようするに主キーとなる候補の集合。主キーは関係表においてただ一つだが、候補キー自体は関係表の中に複数存在することもある。
 

実際に候補キーを作成してみる

 ある集合Sが、以下に示すような属性・関数従属性を持つものとする。
 これに対して、上記で示した手順を試していくことにする。手順1は実施済なので省略する(試験においてはここが一番手こずるポイントではあるが、それはまた別の問題ということで)。

集合S(A, B, C, D, E, F, G, H)
A → F
B, C → G
A, B, C → D
G → H
D → E

 まず、手順2を適用する。集合Sの中で成立する関数従属において、独立属性に相当するのは、A・(B,C)・ G・Dとなるので、候補キーは(A,B,C,D,G)となる。

 次に手順3を適用する。作成した候補キーの内部で、(B,C) → Gと(A,B,C) → Dとが成立するため、従属属性に相当するD・Gを候補キーから取り除く。ゆえに候補キーは(A,B,C)となる(※A→Fなどの部分関数従属性が存在するので、集合S自体は第二正規化が可能)。

 ちなみに関数従属図を用いればある意味一目瞭然だったりする。

もう一例をしめす。

集合M(A, B, C, D, E, F)
A → D
A, B → E
A, B → C
C → F
C → B

 まず、手順2を適用する。集合Mの中で成立する関数従属において、独立属性に相当するのは、A・(A,B)・Cとなるので、候補キーは(A,B,C)となる。

 つぎに手順3, 4を適用する。関数従属性(A,B) → CとC → Bとが存在するため、B・Cは独立属性・従属属性どちらにもなる。Cを取り除いたとき候補キーは(A,B)となり、Bを取り除いたとき候補キーは(A,C)となる。ゆえに、集合Mの候補キーは(A,B)と(A,C)と二つ存在することになる。

なぜこれで求めれるか考えてみる

 関数従属図をみれば候補キーは直感ではわかるが、なぜそう断定出来るのかは理論的に考えてないとわからない。というわけで考えてみた。その前に登場する用語だけ先にしめす。

  • 自明な関数従属性

 属性集合X,Yにおいて、YがXの部分集合であるときX→Yが必ず成立することを言う。集合A{学生番号,科目}において学生番号は集合Aの部分集合なので、{学生番号、科目}→学生番号は必ず成立する。当たり前のことだから自明。

  • 合併律

 属性集合X,Y,Zにおいて、X→YかつX→ZならばX→{Y,Z}が成立することを言う。くっつけたから合併。

  • 推移律

 属性集合X,Y,Zにおいて、X→YかつY→ZならばX→Zが成立することを言う。三段論法的。
 
 さて、上記の例でなぜ(A,B,C)が候補キーと断定出来るのかを考えてみる。これは(A,B,C)→(D,E,F,G,H)であることを示せばよい。
 たとえば、(A,B,C)→Fはなぜ成立するのかを考える。A→Fは成り立つが、A,B,C→Fはなぜ成り立つか? これは次のように考えればよい。AはA,B,Cの部分集合であるため、自明的な関数従属性より(A,B,C)→Aが成立する。また、A→Fが成立するため(A,B,C)→A→Fとなり、推移律から(A,B,C)→Fが導ける。他のものも同様に考えるとよい。

A → F : (A, B, C) → A → F  ⇒ (A, B, C) → F 
B, C → G: (A, B, C)→(B, C) → G  ⇒ (A, B, C) → G
G → H : (A, B, C) → (B, C) → G → H ⇒ (A, B, C) → H
D → E  : (A, B, C) → D → E ⇒ (A, B, C) → E
また、(A,B,C)→D

(A,B,C)以外の属性はすべて(A,B,C)に関数従属するため、合併律より(A,B,C)→(D,E,F,G,H)が成立する。

候補キーの罠を見破れ!(2010.02.06 追記)

 データベーススペシャリスト試験においては、関数従属図は未完成であることが多い。問題文の中からその隠れた関数従属性を見つけ出し、関数従属図を完成させねば候補キーはすべて洗い出せない。
では、どうしたらよいか? ポイントだけ載せておく。

  • 候補キーもしくはその一部が関数従属するものを探す

 未完成の関数従属図で候補キーを導き出せた場合、逆にその候補キーが関数従属しているものがないかをチェックする。具体的には、候補キーの記述に注目し、他の属性を用いることでその候補キーを一意に特定できないかをチェックする。
 たとえば(A,B,C)→(D,E,F,G,H)が成立する場合、A・B・Cの記述に注目し、D→A等の関数従属性が見つけられたとき、(B,C,D)も候補キーとする。
 まあ問題文の多くは、主キーっぽく見えるようなA――A→(B,C...)など――はあっさりとみつかり、Aを代換するような関係――(B,C)→Aのようなもの――はそうと気づかせないようにしている。いやらしいものである。一つ見つかったからといって安心してはいけない!

参考文献