2006年10月08日

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

シリーズになってしまった「主キーの設計」も今回でようやく終わりだ。前々回ではリレーションに対する代替案として「リレーション関数」なる概念をひねり出した。前回はリレーション関数モデルの上で正規形と正規化を再定義した。今回はリレーション関数モデルに関係代数を移築する。


関係代数とは

関係代数は、リレーションの集合と、その上に定義されたいくつかの演算からなる体系だ。演算の数え方は人によって違うようだが、制限(restriction)・射影(projection)・直積(production)・(union)・(difference)・共通部分(intersection)・結合(join)・(division)の8つを想定すれば十分だろう。ここでのポイントは、この体系がこれらの演算に関して「閉じている」という点だ。すなわち、リレーションに上記いずれかの演算をほどこして得られる結果は、やはりリレーションである。だから、これらの演算は何回でも繰り返して適用できる。関係代数をリレーション関数モデルに移築するにあたって、これは最低限守らなければならないお約束だ。

これらの演算の内容についてはご承知と想定して、ここでは、検討しやすいよう、手始めに、これらの演算を分類してみる:
主キーサンプルG−関係演算の分類

制限・射影はひとつのリレーションからひとつのリレーションを作り出すので、単項演算である。その他は二項演算である。二項演算には2種類がある。1番目は演算対象である2つのリレーションが同じ属性集合をもたなければならないという条件(すなわち、表形式にしたときに列数と列名が一致しなければならないということ。これを、union-compatible条件と呼ぶ)が付されるもので、和・差・共通部分がこれにあたる。残りの二項演算はそのような条件が付されないもので、直積・結合・商がこれにあたる。

それでは、これらの演算をリレーション関数の集合上に移植できるのか、カテゴリーごとにみていこう。

関係代数の移植

(1) 単項演算−制限・射影

まず「制限」については、もとのリレーション関数 r:E--->R から、制限の条件に従いEの部分集合を取り、それを定義域とするリレーション関数を作ればよい。制限の定義を式で書くと以下のようになる:

Restp(r) = {(e, t) | (e, t)∈r, p(e,t)}
p は制限の条件を表す述語である。なお、リレーション関数 r は、エンティティ e と、それに対応付けられたタプル t の対 (e, t)の集合である(だからこそエンティティとタプルを左右に並べた表として表すことができる)ことに注意されたい。

射影も簡単だ。もとのリレーション関数から、指定された属性だけを抜き出して新しいリレーション関数を作成するだけである:

Proja1,...,an(r) = {(e, t') | (e, t)∈r, t'=t[a1,...,an]}
ここで、a1,...,anは属性の並びであり、t[a1,...,an]は、タプル t から属性a1,....,anを抜き出して作ったタプルである。

制限、射影いずれにおいても、演算の結果は、(e, t)対の集合であり、リレーション関数となっている(脚注@)。

(2) union-compatible 二項演算−和・差・共通部分

リレーショナルモデルでは、これら三つの演算は集合論での「和(A∪B))」・「差(A−B)」・「共通部分(A∩B))」そのものだ。演算対象の2つのリレーションが union-compatible でなければ、結果がリレーションにならないので、そういう条件を付しているだけである。

リレーション関数も集合だから、同様に和・差・共通部分をとればよい、ということになるかというと、そうはいかない。(e, t)の集合が「関数」であるためには集合内で各タプルを e で識別できる(つまり e が決まれば t が決まる)という条件がつくからだ。だから、和と共通部分では、2つのリレーション関数 r1, r2に、同じエンティティに関する(e, t)対が含まれる場合には、r1 の方を優先するという約束をしておく。差については、(e, t)対の全体ではなく e が一致すればその要素は除去することにする。

r1r2 = {(e, t) | (e, t)∈r1 または 、(eが r1 の定義域に含まれず、かつ、(e, t)∈r2)}
r1r2 = {(e, t) | (e, t)∈r1 かつ 、eが r2 の定義域に含まれない}
r1r2 = {(e, t) | (e, t)∈r1 かつ 、eが r2 の定義域に含まれる}

リレーション関数モデルでは和と共通部分についても交換法則が成り立たなくなるが、別に大した問題はないだろう。

(3) 非union-compatible 二項演算−直積・結合・商

最後のこれが問題だ。

手っ取り早く言うと、直積と商はリレーション関数モデルに移植できないと僕は思う。商は直積の出来の悪い逆演算なので、直積についてその理由を説明すれば十分だろう。

リレーショナルモデルでの直積はどんな演算だろうか。3つのタプルを含むR1と、2つのタプルを含むR2という2つのリレーションがあるとしよう。直積R1×R2は、R1の各タプルとR2の各タプルの組合せからなり、6つ(=3×2)のタプルを含む。
1、R2の各タプルがそれぞれエンティティ集合E1、E2の要素と対応しているとするなら、R1×R2の各要素は、(エンティティではなく)E1とE2の直積の要素(すなわちエンティティ2つの組)に対応していることになる。これを踏まえてリレーション関数の直積を式で書いてみるとこのようになる:

(E1->R1) × (E2->R2) = (E1×E2) -> (R1×R2
ところで、リレーション関数の要素である(e, t)対は明らかにエンティティと1対1対応する。ところが上式の右辺の要素はそうではない(エンティティ2つの組と1対1対応する)。ここから考えると、リレーション関数の直積はリレーション関数ではないということになる。であるなら、直積はリレーション関数の集合上で閉じた演算ではなく、したがって、リレーション関数モデルの一部でもない。

直積や商は絶対に必要なのだろうか。僕はプログラムを書いていて直積と商を使いたいと思ったことは一度も無い(商はSQLで書けるのだろうか)。だからこの2つについては忘れることにしよう(^-^)。しかし結合は絶対に必要だ。実用的な見地にたっても必要だし、理論の上でもそうだ。正規化を理論的に定義するためには「結合」が絶対に必要だからだ。
これにはちょっと補足説明が必要だろう。前回エントリで十分に踏み込めなかったが、「正規化」には「無損失分解」でなければならないという条件がついている。無損失分解とは、分解した結果をもとに、再び過不足なくもとのリレーションを組み立て直せるような、そんな分解を意味する。機械をバラして組み立て直すとき、ネジが余ったり、足りなかったりしたことはないだろうか。そんなことではダメですよというルールだ。この「組み立てる」という操作が「結合」なので、正規化には結合が必要なのだ(脚注A)。

では結合を定義しよう。直観的にいうと、結合とは、基本となるタプルのある属性の値をキーに、他のリレーションのタプルを検索してくっつけることだ。キーとなる属性は「エンティティ参照」であると考えて構わないはずだ。この考えを式であらわすと以下のようになる:
r1 Joina r2 = {(e, t1∩t2) | (e, t1)∈r1, (t1.a, t2)∈r2}
表記法に関する説明が必要だ。Joinは結合演算子、それに添えられた a は、結合のキーとなる属性の名前である。これはr1中のリレーションの属性である。この属性の属性値集合は、r2中のエンティティ集合(の部分集合)でなければならない。次に右辺について。t1∩t2は、タプル t1 と t2 をつなぎ合せて作ったタプルである。t1=(a1,...,an)、t2=(b1,...,bn) なら、t1∩t2=(a1,...,an, b1,...,bn) だ。t1.a は、タプル t1 の属性 a の値を意味する。

この「結合」の定義は、正規化をきちんと定義するツールとして十分に機能するだろう。正規化の各ステップで分解されてできる2つのリレーション関数はエンティティ参照で結び付けられているのだから。また、主キーと外部キーによる結合はすべて上の式で扱うことができるから(リレーション関数モデルでは外部キーはすべてエンティティ参照になるので)、実用の面でもこれで十分だろう。

むすび

えんえんと書き連ねてしまった。
リレーショナルモデルに代えて、リレーション関数モデルというものをデータ設計の基礎に据えることが、もしかしたら可能かもしれないと、ご共感頂けただろうか。やり残したことはたくさんある。一番気になっているのは、正規化のアルゴリズムをリレーション関数モデル上で再現する仕事だ。正規形が設計上の規範として機能するには、これこれの正規形ならこれこれの更新時異状が起きないというだけでは足りない。非正規形のリレーション関数があれば、かならずそれを正規形に分解することができるという確信が、設計者の間で共有されている必要がある。いくら天国がきれいでも、そこに至る道を見つけようもないのなら、目的地にはならないわけだ。誰か、ちゃんとした数学のスキルを持つ方がやって下さると嬉しいのだが。

この一連のエントリを書くために、リレーショナルモデルを久しぶりに勉強した。普段の仕事の中でこうした基礎理論を意識することは、正直いってそれほどない。とはいえ、仕事の基礎に単純な理論があるのは良いことだ。理論で判断できることは理論に任せてしまって、僕らはもっと人間的な機微を要する仕事に集中できる。正規化の目標を第2正規形とするか第3正規形とするかを論争する人はいない。第3正規形にすればよいのである(非正規化はまた別のレベルの話だ)。しかし「正規形」が定義されていなかったとしたら、こんなに簡単に決着はつかないだろう。単純に理論で判断できることがらを多くしていくことが、実務のためにこそ必要なのだ。大部分の時間は現場の仕事に集中する一方で、現場で僕らが直面する問題を解けるように、古き良き理論をすこしずつ衣替えしていこう。コッド博士から受け継いだリレーショナルモデルを教科書の中の墓場に眠らせてしまうのは、博士に対して失礼ではないか。



(脚注@)
(e,t)対の集合がリレーション「関数」であるためには、この後の箇所で説明されているように、その集合内で各(e,t)対が e によって一意に識別されるという条件が必要だが、ここで定義された制限・射影いずれについても、その条件は満たされている。

(脚注A)
リレーショナルモデルにおいて、組み立てる操作が「結合」なら、分解する操作は「射影」である。ところが、リレーション関数モデルでは射影をとるだけでは分解することにならない。本当は、この点についてもなんらかの対応が必要だ。
--- 興味のある人は、リレーショナルモデルの射影では重複タプルが排除されタプルの数が減少することがあるのに(SQL の SELECT DISTINCT の動作に対応)、リレーション関数モデルの射影では、タプルの数は常に変わらないということを手がかりに考えてみてください。

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

メールアドレス:

ホームページアドレス:

コメント:

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


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

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

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