2006年09月29日

主キーの設計D−数学をちょっとだけ(その2)

前回に引き続いて数学である。前回は「リレーション」の代わりに「リレーション関数」を土台としてリレーショナルモデルを再構築できないか、という提案をした。そして「リレーション関数」の数学的定義を作ってみた。今回は、この新たな基礎の上に、正規化理論を移築できないかを検討する。

ちょっと補足すると、正規化理論は関係代数に依拠しているので、先に関係代数を移築し、その後に正規化理論に取り組むのがスジかもしれない。しかしデータモデルを作る上で、まず必要なのは正規化理論であって関係代数ではない。なので、あまり堅いことを言わずに、正規化理論から始めることにするわけだ。

正規形の定義

出発点として、リレーショナルモデルでの「正規形」の定義を確認しておこう:

  1. リレーションを構成する属性値集合がいずれも、構造をもたない単純な値(=スカラ値)の集合であるとき、かつそのときに限り、そのリレーションは第1正規形 (1NF) である。
  2. リレーションが第1正規形で、かつ、候補キーでないすべての属性が各候補キーに完全関数従属するとき、かつそのときに限り、そのリレーションは第2正規形 (2NF) である。
  3. リレーションが第2正規形で、かつ、候補キーでないどの属性も各候補キーに非推移的に関数従属するとき、かつそのときに限り、そのリレーションは第3正規形 (3NF) である。
  4. リレーションが第1正規形で、かつ、候補キー以外を決定項とする完全関数従属性が存在しないとき、かつそのときに限り、そのリレーションはボイスコッド正規形 (BCNF) である。
なお、定義には明示されていないが、直観的に明らかなように、BCNFであれば3NFでもある。

正規形には上記以外に4NF、5NF、さらには6NFが存在するそうである。しかし、これらについては僕の理解が不十分であり、実務上もあまり強く意識されないため、検討対象外としておく。

リレーション関数モデルでは、正規形の定義は以下のように修正される。変更・追加部分に下線を付した:

  1. リレーション関数の値域であるリレーションを構成する属性値集合がいずれも、構造をもたない単純な値(=スカラ値)の集合であるとき、かつそのときに限り、そのリレーション関数第1正規形 (1NF) である(脚注@)。
  2. リレーション関数が第1正規形で、かつ一意キーを持つ場合リレーション関数の値域であるリレーションにおいて一意キーでないすべての属性が各一意キーに完全関数従属するとき、かつそのときに限り、そのリレーション関数第2正規形 (2NF) である。一意キーを持たないリレーション関数は、第1正規形であれば、第2正規形でもある。
  3. リレーション関数が第2正規形で、かつ一意キーを持つ場合リレーション関数の値域であるリレーションにおいて一意キーでないどの属性も各一意キーに非推移的に関数従属するとき、かつそのときに限り、そのリレーション関数第3正規形 (3NF) である。一意キーを持たないリレーション関数は、第2正規形であれば、第3正規形でもある。
  4. リレーション関数が第1正規形で、かつ、リレーション関数の値域であるリレーションにおいて一意キー以外を決定項とする完全関数従属性が存在しないとき、かつそのときに限り、そのリレーション関数ボイスコッド正規形 (BCNF) である。

上記の定義で気になるのは、一意キーを持たないリレーション関数では、1NFとBCNFの間が無い点である(1NFであれば、2NF,3NFの条件も満たすから)。リレーションをBCNFに分解する際は関数従属性が失われることがあるので、1NFから3NFまでとBCNFの間にはちょっとした断絶があると言わなければならない。この点を考慮すれば、関数従属性を失わずにここまでは分解できるという限界点を3NFは示しているといえる(だから3NFまで正規化すれば十分と一般に言われるのである)。一意キーをもたないリレーション関数について、上に示した3NF(=1NF)はそうした限界点を表していない。
もう一工夫が必要だ。

内容を損なわないように注意しながら、リレーショナルモデルでの3NFの定義を読み替えてみよう:

  1. リレーションが第2正規形で、かつ、候補キーでないどの属性も候補キー以外には完全関数従属しないとき、かつそのときに限り、そのリレーションは第3正規形 (3NF) である。
その上で、これをリレーション関数版に焼きなおす:
  1. リレーション関数が第2正規形で、かつ、リレーション関数の値域であるリレーションにおいて一意キーでないどの属性も一意キー以外には完全関数従属しないとき、かつそのときに限り、そのリレーション関数第3正規形 (3NF) である。
これなら一意キーを持たないリレーションにも適用できる。なお、一意キーを持たないリレーション関数では、これは実質的にBCNFと同じことである(逆にいえば、一意キーを持たないリレーション関数は、関数従属性を犠牲にせずBCNFに正規化できる)。
リレーション関数についての正規形の定義の確定版を以下に掲げておく:
  1. リレーション関数の値域であるリレーションを構成する属性値集合がいずれも、構造をもたない単純な値(=スカラ値)の集合であるとき、かつそのときに限り、そのリレーション関数第1正規形 (1NF) である。
  2. リレーション関数が第1正規形で、かつ一意キーを持つ場合リレーション関数の値域であるリレーションにおいて一意キーでないすべての属性が各一意キーに完全関数従属するとき、かつそのときに限り、そのリレーション関数第2正規形 (2NF) である。一意キーを持たないリレーション関数は、第1正規形であれば、第2正規形でもある。
  3. リレーション関数が第2正規形で、かつ、リレーション関数の値域であるリレーションにおいて一意キーでないどの属性も一意キー以外には完全関数従属しないとき、かつそのときに限り、そのリレーション関数第3正規形 (3NF) である。
  4. リレーション関数が第1正規形で、かつ、リレーション関数の値域であるリレーションにおいて一意キー以外を決定項とする完全関数従属性が存在しないとき、かつそのときに限り、そのリレーション関数ボイスコッド正規形 (BCNF) である。

正規化の手順

リレーショナルモデルでは、1NFをBCNFにまで正規化するアルゴリズムが知られているそうだ。リレーション関数モデルでも同じことが可能だろうか。この判断は僕の手にあまるので、ここでは例示によってリレーション関数モデルの正規化の手順を示そう。

注文明細(注文日, 注文番号, 行No, 得意先名, 出荷予定日, 商品C, 商品名, 単価)
※ エンティティ集合とリレーションが同名のとき、関数表記を省略する。すなわち、上記は「注文明細--->注文明細(.....)」の略記である。

一意キー:

     
  1. {注文日,注文番号,行No}
完全関数従属性(一意キーを決定項とするものを除く): 
     
  1. {注文日,注文番号}→{得意先名}
  2. {注文日,注文番号}→{出荷予定日}
  3. {商品C}→{商品名}
  4. {商品C}→{単価}

このリレーション関数をまず2NFに分解しよう。
完全関数従属性のうち、一意キーの一部を決定項とするもの(1,2)を取り上げ、新しいリレーション関数(「注文」)を作成する:

注文(注文日, 注文番号, 得意先名, 出荷予定日)

つぎに、元のリレーション関数(「注文明細」)を修正する。上記で処理対象とした完全関数従属性の決定項({注文日,注文番号})をエンティティ参照に置き換えるとともに従属項(関数従属性の右辺)に現れる項目(得意先名, 出荷予定日)を削除する:

注文明細([注文], 行No, 商品C, 商品名, 単価, 個数)

注文(注文日, 注文番号, 得意先名, 出荷予定日)

以上で「注文明細」は2NFとなった。
さらに3NFに変換するには、一意キー以外を決定項とし非キー属性を従属項とする完全関数従属性を外出しする。この例では、残る2つの完全関数従属性(3,4)ともにこれに該当する。 2NFに変換したときと同様、これらの完全関数従属性の決定項({商品C})を一意キーとする新しいリレーション関数(「商品」)を作成する:

商品(商品C, 商品名, 単価)

元のリレーション関数を修正する手続きも2NF変換と同様である:

注文明細([注文], 行No, [商品], 個数)

注文(注文日, 注文番号, 得意先名, 出荷予定日)

商品(商品C, 商品名, 単価)

これで3NFへ変換できた。この例では、一意キー以外を決定項としキー属性を従属項とする完全関数従属性はなかったので、これはBCNFでもある。だから、これ以上の正規化は必要ない。

以上でみたリレーション関数モデルの正規化の手順は、外部キーをエンティティ参照に置換することを除き、リレーショナルモデルでの手続きと大差ない。これから推測すると、正規化のアルゴリズムを作ることも可能ではないだろうか。

これに何か意味があるのか?

リレーション関数モデルで、正規形と正規化をこのように定義したからといって、何の意味があるのか。リレーショナルモデルからリレーション関数モデルへの変換が簡単にできるなら(僕はできると思っている)、リレーショナルモデルの上で十分に正規化したのちにリレーション関数モデルに変換すればすむ話ではないのか。

まったく正当なこの疑問に対しては、二つの答えがある。

ひとつ目の答えは、データモデルの作成は試行錯誤だ、ということである。リレーション関数モデルに変換してからも、エンティティや属性を追加することはごく普通にあると思われる。そんなとき、変換前のリレーショナルモデルにいったん戻らなければ正規形の判定ができないというのでは、いかにも不便だ。リレーション関数モデルの上で判定できる方がずっと便利だろう。

もうひとつは、正規形であるリレーション群をリレーション関数群に変換したときに正規形でなくなるケースがあるということである。これはおどろくべきことだ(少なくとも、僕はおどろいた)。どのような条件下でこうしたことが起きるのか、僕は正確に説明できないが、少なくともひとつ、例を示すことはできる。


主キーサンプルE−BCNF比較@
このモデル(リレーショナルモデル上のデータモデル)はBCNFであるとする。すなわち各リレーションでの決定項は候補キーのみである。
これを、リレーション関数モデル上に移し変えると以下のようになる:
主キーサンプルF−BCNF比較A
このモデル(リレーション関数モデル上のデータモデル)は3NFではあるがBCNFではない。なぜかというと、リレーション関数「在庫」上に、{[棚]}→{[倉庫]}という関数従属性があるからだ。この関数従属性はリレーション関数モデルへの変換によって挿入されたわけではない。もとのモデル上でも{倉庫C,棚記号}→{倉庫C}という形で存在していた。ただし従属項{倉庫C}が決定項{倉庫C,棚記号}に含まれているので、これは「自明な」関数従属性であり、正規形で問題にする「完全関数従属性」のひとつには数えられないのだ。複合キーによるリレーションの紐付けをエンティティ参照による紐付けに変える過程で、自明な関数従属性が非自明な関数従属性に昇格してしまったのである(また、それにともない{[商品], [棚]}という新たな一意キーが発生してしまった)。
じっさい、このモデルで仮に「倉庫棚」の[倉庫]が更新されたなら、「在庫」における[倉庫][棚]の組合せと合致しなくなるという更新時異状が発生する可能性がある。

リレーショナルモデルの方の例は、実は、渡辺さんのブログのエントリ「代理キーは『スタイル』ではなく『テクニック』」から拝借したものである。このエントリに対するコメント・トラックバックを読むと、かなりの人が不思議な違和感を感じたようである。もしかしたら何人かの方は、オリジナルモデルをリレーショナル関数モデルに脳内変換した上で、サブリミナルなレベルでBCNF違反に気付いていらっしゃったのではないか、と想像すると楽しい。

以上で、リレーション関数モデルでの正規形と正規化の話を終える。理論的にきちんとした証明には欠けているが、アイデアとしてはだいたい理解して頂けるのではないだろうか。

あとは関係代数をやっつければ終わりだ。....はぁ〜。

(脚注@)
エンティティはここでいう「スカラ値」に該当する。だからエンティティ集合を属性値集合としても1NFに違反しない。リレーション関数モデルで「構造」を担うのは、リレーションの要素であるタプルであって、エンティティは無構造なのだ。

posted by keis at 23:23| Comment(0) | TrackBack(0) | システム外部設計 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/393131352
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。