More than 5 years have passed since last update.

リレーショナルデータベース・正規系まとめ

Posted at 2019-04-03

初めに

本記事は以下の正規系についてまとめた記事となります。

第一正規系
第二正規系
第三正規系
ボイス・コッド正規系
第四正規系
第五正規系

第六正規形というものもあるみたいだけど、~~日本語ソースが少ないので~~本記事では扱いません。

正規化の定義

一つの関係を，属性間の冗長性及び矛盾を排除して，より単純な一つ以上の関係に変換する過程であって，参照整合性の維持に役立つ
byJIS X 0017:1997 情報処理用語(データベース)

全てのテーブルを１事実１箇所（各テーブルには１つの従属性のみが存在する状態）とすることにより、冗長性を排除し更新時異常を防ぐ。

本記事で使用するキー

スーパキー

行を一意に識別するための属性（あるいは属性の組合せ）

候補キー

スーパーキーのうち、行を一意に識別するために必要最低限の組合せ。

非キー

いかなる候補キーにも含まれない属性

情報無損失分解

リレーションがその分解されたリレーションの自然結合で復元される時、「その分解は情報無損失分解である」という。

関数従属性の定義

項目Xの値を一つ決めると、項目Yの値が一つきまる性質。

TODO定義の書き換え(属性が複数ある場合を考えていない。)

(X→Y)⇔(∀t, t' ∈ R, t[X] = t'[X] ⇒ t[Y] =t'[Y])

tはデータベースの一行(tuple)を指す。

情報無損失分解ができるための十分条件である。

多値従属性の定義

R.Fagin(1977)により提案された概念。
項目Xの値を一つ決めると、項目Yの値が一つ以上きまる性質。

属性A、B、Cを関係Rの属性集合の任意の部分集合とする。Rのある(A-値、C-値) の対に対応するBの値の集合がAの値にのみ依存して、C の値と独立である場合、かつそのときに限りB はAに多値従属しているといい、次のように表す

A →→ B | C

換言すると、属性Bと属性Cに因果関係が存在しないこと、つまり直交していることを表す。
関数従属性の一般系であり、情報無損失分解ができるための必要十分条件である。

結合従属性の定義

R を関係とし、A、B、…、ZをR の属性集合の任意の部分集合とする。このとき、R がA、B、…、Z 上の射影の結合と等しいとき、その時に限り、Rは結合従属性＊(A、B、…、Z) を満たす。

多値従属性の一般系である。

第一正規系の定義

リレーション$R(A_1,A_2…,A_n)$は、その各ドメイン$dom(A_i)$が原始的なとき第一正規系であるという

つまり、各ドメインが他のドメインの直積空間の元であったり、あるドメインの冪集合でないことを要求している。関係代数・関係論理を適用するための条件である。

第一正規形でない例

属性「社員名」に対応するドメインは、属性「性」と属性「名」に対応するドメインの直積空間の元となっており、属性「趣味」に対応するドメインは、冪集合の元となっている。
上述の表のような状態を非正規形と呼ぶ。

第一正規形の更新時異常

第一正規形であるだけでは、そのリレーションの更新時に異常が発生する。以下の例を基に説明する。

タプル挿入時異常

(null,PC,4,150000,null)のようなタプルを挿入しようとしても、顧客名の主キー制約により登録することが出来ない。

タプル削除時異常

(鈴木三郎,洗濯機,4,120000,480000)のタプルを注文取消し等の理由で削除する際に、洗濯機の価格情報が削除されてしまう。

タプル修正時異常

テレビの価格が変更となった場合、二本のタプルを修正しなければならない。
鈴木三郎から注文が洗濯機からテレビに変更された場合、洗濯機の価格情報が削除されてしまう。

更新時異常が発生する理由

二つの異なった事象が一つのリレーションに記述されているからである。具体的に言うと、注文情報と商品の価格という二つの切り離しうる事象を一つのリレーションで管理しているため、上述の更新時異常が発生している。そのため、更に正規化をするべきである。

第二正規系の定義

リレーションRが次の二つの条件を満たす。

第一正規系であること
すべての非キー属性が、すべての候補キーに対して完全関数従属する

TODO完全関数従属の説明

TODO定義より候補キーが単一の属性である場合、第一正規形に変換した時点で第二正規形の定義を満たす。

第二正規形への変換

先ほどのリレーション「注文」を第二正規形に変換する。
以下の関数従属性が存在する。

{顧客名,商品名}⇒{数量,金額}
{商品名}⇒{単価}

数量・金額は候補キーに完全関数従属しているが、単価は商品名のみに完全関数従属している。そのため、リレーション「注文」は第二正規形ではない。
第二正規形に変換するため{商品名}⇒{単価}を利用してリレーション注文を以下の二つの射影に分解する。

第一正規形の際に生じていた更新時異常は発生しないこと・上記テーブルの分割は情報無損失分解であることを確認していただきたい。

第二正規形の更新時異常

第二正規形であるだけでは、そのリレーションの更新時に異常が発生する。以下の例を基に説明する。

候補キーが単一キーであるため、リレーション「社員」は第二正規形である。

タプル挿入時異常

(null,null,null,技術本部,岡山)のようなタプルを挿入しようとしても、主キー制約により登録することが出来ない。

タプル削除時異常

鈴木三郎が会社を辞めた場合、財務部の勤務地情報が削除されてしまう。

タプル修正時異常

経理部の勤務地が変更となった場合、2本のタプルを修正しなければならない。
鈴木三郎が経理部に異動となった場合、財務部の勤務地情報が削除されてしまう。

更新時異常が発生する理由

第二正規形であるため全ての非キー属性は候補キーに完全関数従属するが、$社員番号→勤務地$という候補キーからの関数従属性は、以下のような推移的関数従属性である。
$ 社員番号 → 所属 ∧ 所属 → 勤務地 ⇒ 社員番号 → 勤務地 $

つまり、所属が決まれば勤務地が決まるという関数関係は、リレーション「社員」からは分離されて格納されていてよい事象である。

TODOX→Y∧Y→Xならば、Yは候補キーの一部となってしまうため、この場合を除外して考える。

第三正規系の定義

リレーションRが次の二つの条件を満たす。

第二正規系であること
すべての非キー属性が、いかなる候補キーにも推移的関数従属しない

第三正規形への変換

先ほどのリレーション「社員」を第三正規形に変換する。
以下の二つの関係が成立している。

$ 社員番号 → 所属 ∧ 所属 → 勤務地 ⇒ 社員番号 → 勤務地 $
$ ￢(所属 →　社員番号)$

よって $ 社員番号 → 所属 ∧ 所属 → 勤務地 ⇒ 社員番号 → 勤務地 $は推移的関数従属である。
上述の推移的関数従属性を排除することで第三正規形のテーブルとなる。

第二正規形の際に生じていた更新時異常は発生しないこと・上記テーブルの分割は情報無損失分解であることを確認していただきたい。

第三正規形の更新時異常

第三正規形であるだけでは、そのリレーションの更新時に異常が発生する。以下の例を基に説明する。

タプル挿入時異常
科目「社会」を担当する教官「佐藤四朗」が赴任した場合、(null,社会,佐藤四朗)をリレーション「受講」に登録できない。
タプル削除時異常

学生「鈴木三郎」が履修を取り消すと、科目「理科」を教官「佐藤三郎」が担当していたという情報が消えてしまう。

タプル修正時異常

学生「鈴木三郎」が履修を数学に変更すると、科目「理科」を教官「佐藤三郎」が担当していたという情報が消えてしまう。

更新時異常が発生する理由

リレーション「受講」には以下の二つの関数従属性が存在する。

{学生,科目}⇒{教官}
{教官}⇒{科目}

教官を決めれば科目が決定するという、候補キー(スーパキー)からではない関数従属性が存在しているため、one fact in one relationの原則を抵触している。

ボイス・コッド正規形の定義

リレーションRに存在するあらゆる関数従属性に関して、次のいずれかが成立する。

$X→Y$は自明な関数従属性である
Xは$R$の候補キー(スーパーキー)である※

※参照する文書により候補キーとするものと、スーパーキーと記載してあるものに分かれるため、正確な定義は要調査。

ボイス・コッド正規形への変換

候補キー(スーパーキー)が決定子でない関数従属性{教官}⇒{科目}を排除する。

第三正規形にとどめる理由

関数従属性を保存するとは限らない。
先ほどの例であると、{学生,科目}⇒{教官}という関数従属性が失われているため、当該関数従属性が担保されるとは限らない。
例えば、元のテーブルでは(鈴木一郎、数学、佐藤四朗)というタプルを挿入することはできないが、分解後のテーブルでは挿入することが出来てしまうため、事実と異なるタプルの挿入を許してしまう。