2NF・3NF・BCNFは自動生成できる データベース正規化アルゴリズムとその実装
前回のおさらい – データベース正規化を自動化してみようと思った経緯
- 超高速開発ツールの普及が進んでおり、弊社でも「Web Performer」を導入
- 各社のツールを比較検討してみたけど、どれも現時点ではまだ、AIではない
- もっとAIチックな機能を持たせてみたら、ユーザーが喜ぶのでは？
- 例えば、「最適なデータベース設計の提案」はどうだろう？
- 正規化という王道の手法があるので、実験がしやすそう
- やってみよう
前回の記事でやったこと
第一正規形のデータベースを入力すると、すべての候補キーを検出するアルゴリズム（擬似コード）を記述。二分木を使った処理の内容を解説しました。
今回は、アルゴリズム（擬似コード）だけでなく、C++のソースコードも掲載しています。ぜひ、データベースの自動正規化を実行してみてください。
目的
第一正規形で与えられた任意の単一テーブルについて、ボイスコッド正規形への無損失分解を行うアルゴリズムを構築する。
目標としてはボイスコッド正規形までの分解でしたが、今回は尺の都合で、第二正規形（2NF）までの正規化を行うアルゴリズムを提案・実装しています。
2NF、3NF、BCNFはいずれも、関数従属性を取り扱うという点で共通しています。なので、2NFの自動化ができれば、3NFやBCNFへのステップアップにはさほどの困難はなさそうです。
今回も、用語については下記の書籍に則っています。
第一正規形(1st normal form, 1NF)とは？
正規化の対象であるRDBのRは「リレーショナル(Relational)」の頭文字ですが、これはリレーショナルモデルという数学的モデルに立脚しているということから付いた呼称です。同モデルの主要概念である「リレーション」の定義を満たすデータベースを第一正規形と呼び、具体的には、以下の条件を満たす必要があります。
- 繰り返しグループ（同一セルに２つの値を含むなど）が存在しない
- データにNULLは含まれない
今回は、入力されるテーブルが第一正規形であることを仮定して、議論を進めます。
第二正規形（2nd normal form, 2NF）を自動生成するアルゴリズム
第二正規化を自動化するにあたり、まずは第二正規形の定義を見てみましょう。
2NFの定義
1NFの条件を満たし、部分関数従属性を持たないテーブルは2NFである。
さて、この定義の中で「部分関数従属性」及び「関数従属性」についてご存知ない方は、以下の段落を読んでおいてください。
関数従属性(Functional depenency, FD)とは？
関数従属性とは、テーブルにおける、２つのカラム集合に関する概念です。
あるテーブルにおいて、AAというカラム集合の値が同じなら、BBというカラム集合の値も同じである時、BBはAAに関数従属していると言います。
この概念を説明する喩えとして、以下のテーブルを見てください。
上図は、与えられた「名詞」と「動詞」の組み合わせが「自然であるかどうか」を表すテーブルです。
この時、「鉛筆」という名詞だけに対して「自然」か「不自然」かの判定はできません。 「食べる」という動詞に対しても同様です。 しかし、「鉛筆」「食べる」という組み合わせに対しては、それが「不自然」であるという判定を下すことができます。
このことから、評価評価というカラム集合は、名詞名詞や動詞動詞といったカラム集合には関数従属しておらず、名詞,動詞名詞,動詞というカラム集合には関数従属していることが分かります。 なお、上記のテーブルには、他のいかなる関数従属関係もありません。
ここでは分かりやすさのために、カラム同士の関係性が明確な例をあえて選びました。 勿論一般に、関数従属関係はカラムの名称ではなく、テーブルの内容によって決まります。 例えば、以下のテーブルを見てみましょう。
上図は、はじめの図とよく似ていますが、「名詞と動詞の組み合わせが自然だと思うか？」というアンケートの結果をイメージした表に変わっています。 着目すべきは、「トマト」「投げる」という組み合わせについて、ある人は「自然」、またある人は「不自然」と答えていることです。テーブルがこのような状態になっていると、「トマト」「投げる」という組み合わせが自然か不自然か、データからは一意に定まりません。ゆえにこのテーブルでは、評価評価は名詞,動詞名詞,動詞に関数従属していないことになります。
このように、関数従属関係は、テーブル内のデータによって定まることに注意してください。
また、説明する相手がエンジニアであれば、以下の説明は分かりやすいかもしれません。
- カラム集合AAの値をkey、BBの値をvalueとして、両者の関係を一つの連想配列に格納可能であるとき、BBはAAに関数従属しているという
上記の定義は、これから行う関数従属性の判定において活用することになります。
部分関数従属性(Partial functional dependency)とは？
部分関数従属性は、ある条件を満たす関数従属性のことです。 定義の紹介の前に、まず候補キーについて復習しておきましょう。
復習：候補キーとは？
以下の条件を満たすカラム集合を「候補キー」と呼びます。
- テーブル内のデータを一意に定めることができる
- カラムを一つ除くと、データを一意に定めることができなくなる（既約性）
例えば上図においては、回答者ID,名詞,動詞回答者ID,名詞,動詞が唯一の候補キーです。
また、ある集合に対し、要素を一つ以上取り除いた別の集合を真部分集合と呼びます。たとえば、回答者ID,名詞,動詞回答者ID,名詞,動詞に対して名詞,動詞名詞,動詞は真部分集合です。
以上の用語を用いると、部分関数従属性とは、ある候補キーの真部分集合から、その候補キーに含まれないカラム集合への関数従属性であると定義できます。
そして、第二正規形は、第一正規形であり、部分関数従属性を含まないデータベースとして定義されます。
実は、上図のテーブルは部分関数従属性を持たないため、第二正規形になっています（もっと言うと、さらに高次の正規形であるボイスコッド正規形になっています）。よって、この条件を満たさないような別の例を考えてみましょう。
上表は、３人の生徒に対し、３つの科目の試験を行った結果をイメージしたテーブルです。 各生徒について、各科目の評点の平均値を丸めたものを総合点としています。 テーブルより、評点評点は氏名,科目氏名,科目に関数従属しており、総合点総合点は氏名氏名に関数従属していることが分かります。 このテーブルには、部分関数従属性が存在するでしょうか？
まず、候補キーは氏名,科目氏名,科目であることが分かります。候補キーの真部分集合は氏名氏名もしくは科目科目の２通りですが、氏名氏名から総合点総合点への関数従属性が存在しており、これが部分関数従属性であることが分かります。
このような、部分関数従属性を持つ（第二正規化されていない）テーブルの弱点の一つとして、「更新による異常が起きやすい」という性質があります。例えば、上記のテーブルに対し、第４の科目である「Ruby on Rails」の評点を加えたとしましょう。 その際、全科目の平均値である総合点を更新する必要に迫られますが、以下のようなテーブルへと更新してしまう恐れがあります。
- 各生徒に関する「Ruby on Rails」の評点を追加
- 総合点の数値を再計算し、追加行に格納
- しかし、元々テーブル内にあった「PHP」「HTML5」「JavaScript」行の総合点を更新し忘れてしまった
テーブルがこのような状態になっていると、氏名氏名に対して総合点総合点が一意に定まらず、複数ある値のどれが正しい値かわからない状態になります。テーブルの性質上総合点総合点は氏名氏名に関数従属すべきなのに、そうなっていない状態は一種の矛盾です。第二正規形でないテーブルは、更新による矛盾が起きやすいテーブルと言えます。
このテーブルから部分関数従属性を取り除くには、テーブルの分解が必要です。分解には射影（MySQLで言うところの、DISTINCT指定したSELECTコマンド）を用います。
今回の場合、以下の２つのテーブルに分解すれば、情報を損失させずに分解が可能です（無損失分解）。
第二正規化を自動で行うには？
第二正規化の自動化は、大きく３つのステップからなります。
- 候補キーを検出する
- 部分関数従属性を検出する
- 射影によって部分関数従属性を取り除く
このうち、1.については前回の記事でアルゴリズムを設計しましたので、今回は候補キーの一覧が手に入ることを前提に話を進めます。
部分関数従属性の検出
アルゴリズムを記述するために、幾つかの記法を決めておきましょう。 まず、カラム集合AAからカラム集合BBへの部分関数従属性が存在することを、A→BA→Bと表記します。先の例で言えば、氏名→総合点氏名→総合点が成り立っていました。 また、検出される全ての関数従属性をPFDPFDで表します（Partial Functional Dependencyの略）。 実装上は、PFDPFDは連想配列を使うと良いでしょう。
テーブルの全ての候補キーの集合をKK（花文字のKK）で表すこととし、個々の候補キーをK(∈K)K(∈K)で表します。 また、集合の記法にしたがって、カラム集合AAが候補キーKKの真部分集合であることを、A⊊KA⊊Kと表すことにします。 テーブルに含まれる全てのカラムからなる集合をCCとすると、KKに対する非候補キーの集合は、差集合C∖KC∖Kで表されます。（差集合C∖KC∖Kは、集合CCの要素のうち、KKに含まれない要素からなる集合のことです。）
アルゴリズムのアイデアは、候補キーの集合KKから任意の候補キーKKを取って、その真部分集合A⊊KA⊊Kが非キー属性c(c∈C∖K)c(c∈C∖K)に対する関数従属性A→cA→cを持つかどうか、しらみ潰しに調べるというものです。 まだ調べていない候補キーの集合をˆKK^で表すこととし（アルゴリズム開始時はˆK=KK^=K）、調べ終わった候補キーはˆKK^から取り除きます。 そして、ˆK=∅K^=∅（空集合）となった時にアルゴリズムが停止するようにします。
前回と同様、レコード数（テーブルの行数）をmmで表すこととし、テーブル全体をRR、個々のレコードをr1,r2,…,rm∈Rr1,r2,…,rm∈Rで表します。
以上の記法を用いて、すべての部分関数従属性を検出するアルゴリズムを記述してみましょう。
上記の擬似コードはアルゴリズム分野の書き方に倣い、代入を==ではなく:=:=、等値演算子を====ではなく==で書いていますので、ご注意ください。
下記は、擬似コードにコメントをつけたものです。
実装に関するコメント
候補キーK(∈K)K(∈K)について、その全ての真部分集合を列挙する際には、前回も活用した二分木を使うのが筋の良い方法です。
第二正規化の方法
部分関数従属性の検出ができれば、第二正規化を自動的に行うのはさほど難しくありません。部分関数従属性にしたがってテーブルを分解していくことで、第二正規化を行うことができます。
ただし、候補キーが複数あるような場合は処理が複雑になりますので、ある候補キーKKについて部分関数従属性が検出された場合、一旦それを取り除いておいてから、分解後のテーブルに対してもう一度部分関数従属性の検出を行うといった段階的な実装をしたほうが、バグは少なくなりそうです。 また、分解の順序によって、結果として得られるテーブルの構成がどのように変わるかという点について、議論の余地があります。
第二正規化を自動で行うC++プログラム
ディレクトリ構造は以下のようになっています。
.
├── makeDB_test.cpp
├── table.hpp
├── makeDependentData.hpp
├── dependency.hpp
└── hashVI.hpp各ファイルの機能は以下の通りです。
| ファイル | 説明 |
|---|---|
| makeDB_test.cpp | 正規化を行う対象のテーブルがもつ関数従属性を指定して生成、第二正規化を実行 |
| table.hpp | RDBMSのテーブル操作（SELECT, SELECT DISTINCT, etc.）や、候補キー検出・関数従属性検出・第二正規化アルゴリズムを実装。本プログラムの心臓部 |
| makeDependentData.hpp | 指定された関数従属性をもつテーブル生成機能を実装 |
| dependency.hpp | 関数従属性のプログラム上での表現（dependency構造体）を定義 |
| hashVI.hpp | vector<int>型からハッシュ値を発行する関数オブジェクトを定義 |
プログラムに関する補足
各テーブルを二次元vector（vector< vector <int> >型オブジェクト）で擬似的に表現し、RDBMSのSELECT DISTINCTコマンドはハッシュを使って自力で実装しています。 対象テーブルの行数をmm, カラム数をnnとしたとき、SELECTコマンド、SELECT DISTINCTコマンドの計算量は以下の通りです。
| コマンド | 計算量 |
|---|---|
| SELECT | O(mn)O(mn) |
| SELECT DISTINCT | O(mn)O(mn) |
ハッシュを使うなどデータ構造の工夫をしないと、両者の計算量は一致しません（DISTINCT指定すると遅くなってしまう）。 具体的な要件としては、vectorをkeyとして用いることのできるハッシュ（連想配列）が必要になります。今回はデータ型がintのみだったので簡単でしたが、任意の型の組み合わせだとややこしいことになりそうです。
第三正規化とボイスコッド正規化
さらに高度の正規化である第三正規化、ボイスコッド正規化についても、第二正規化と類似した手続きで行うことができます。
- 取り除くべき関数従属系を検出
- 検出された関数従属性に従い、テーブルを分解
その具体的な方法についても、本記事に反響があれば追記していきたいと思います。
