関係と正規形の話 2011/02/01 [email protected] NTTPC Communications, Inc. リレーショナルデータベースと関係の 関係 • エドガー・コッド先生が、集合論と述語論理をもとに関係モデルを発明し た(IBM, 1969～1970)。 • この関係モデルをもとにできたのがリレーショナルデータベース(関係 データベース)。その頃はSQLはまだなかった（SEQUEL)。 • それ以前のデータベースは、ネットワーク型や階層型と呼ばれるものが 多く、レコードポインタの嵐でよく壊れていたらしい… (今のファイルシステ ムに近いものかも) • 集合論を基礎にした関係モデルによるRDBはデータの整合性とレコード ポインタの追放により、データベースの世界を変革した。 • あまりに凄すぎて、今では関係モデル以外の「データモデル」はほぼ死滅 w （実装にはポインタ使っている) • でも、意外に関係モデルそのものは正確には知られていないし、完全な 関係モデルを実装していないものも多いらしい…. – http://ja.wikipedia.org/wiki/関係データベース管理システム – http://ja.wikipedia.org/wiki/コッドの12の規則 関係って? • 属性と属性のすべての組み合わせの集合の 部分集合(集合なので順番は関係ない)。 • 属性とは、名前と定義域を持つ。 – 定義域は取りうる値を書き下してもよいし、式で 表現してもよい。 – 値はスカラ値や複雑な構造をとっても良いが、一 つとして扱うもの。 • スカラ値とは、それ以上分割できない値のことで、一般 には数値や文字列を指す(扱うプログラム言語により スカラ値の定義は異なる) 例 属性名 管理者 • 以下の属性 – 管理者 – 担当 – 業務内容 薗課長 日浦課長 横井課長 業務内容 設備管理 ホスティング基盤開発 MailLuck?開発運用 サービス運用 定義域 担当 設備 第一開発 第二開発 例:関係{管理者,担当,業務内容} 全部の組み合わせ とその部分集合が 管理者と担当と業 務内容の関係とな ります。文句ある? このように、静的に 考えることで、DBを 考えやすくなる(抜 け・漏れがないよ ね) 管理者 担当 業務内容 薗課長 設備 設備管理 薗課長 設備 ホスティング基盤開発 薗課長 設備 MailLuck?開発運用 薗課長 設備 サービス運用 薗課長 第一開発 設備管理 薗課長 第一開発 ホスティング基盤開発 薗課長 第一開発 MailLuck?開発運用 薗課長 第一開発 サービス運用 薗課長 第二開発 設備管理 薗課長 第二開発 ホスティング基盤開発 薗課長 第二開発 MailLuck?開発運用 薗課長 第二開発 サービス運用 日浦課長 設備 設備管理 薗課長 設備 ホスティング基盤開発 薗課長 設備 MailLuck?開発運用 日浦課長 設備 サービス運用 日浦課長 第一開発 設備管理 日浦課長 第一開発 ホスティング基盤開発 日浦課長 第一開発 MailLuck?開発運用 日浦課長 第一開発 サービス運用 日浦課長 第二開発 設備管理 日浦課長 第二開発 ホスティング基盤開発 日浦課長 第二開発 MailLuck?開発運用 日浦課長 第二開発 サービス運用 横井課長 設備 設備管理 横井課長 設備 ホスティング基盤開発 横井課長 設備 MailLuck?開発運用 横井課長 設備 サービス運用 横井課長 第一開発 設備管理 横井課長 第一開発 ホスティング基盤開発 横井課長 第一開発 MailLuck?開発運用 横井課長 第一開発 サービス運用 横井課長 第二開発 設備管理 横井課長 第二開発 ホスティング基盤開発 横井課長 第二開発 MailLuck?開発運用 横井課長 第二開発 サービス運用 第一正規形 • 関係として扱うものを第一正規形 – 属性の重複はない(属性の集合なので) – 同じタプル(行)はない(全部の組み合わせの部分集 合なので) • タプルを識別するために最低限必要な属性の組 み合わせを候補キーという。いわゆる主キーは 候補キーの一つを選ぶことになる。場合によって は複数の候補キーが現れる。 – 以下、太線を候補キーとして表記します • 正規化とは、属性間の関係を現実のルールに 従って整理していくことに他ならないです。 第一正規形の例 • {管理者,担当,業務内容}の現実に合わせたルールはこちら(ちょっとあっ てないけどゆるしてちょ) – 管理者は、複数の担当を兼務できる – 担当は、複数の業務を行う – 業務は、複数の担当で共同で行うものもある • 書き下してみたw 管理者 担当 業務内容 薗課長 設備担当 設備管理 薗課長 第一開発 ホスティング基盤開発 薗課長 第一開発 MailLuck?開発運用 薗課長 第一開発 サービス運用 日浦課長 第二開発 サービス運用 横井課長 第二開発 サービス運用 太線が候補キー 関数従属と候補キー・非キー • • • • • 属性を追加。フロアと火気責任者を入れてみましょう。管理者は一つのフロアにいて、フロアごと に火気責任者がいます。 これでも第一正規形 でも、担当が決まればフロアや火気責任者が決まるので無駄が多いよね このような、Xが決まればYが一つに決まる関係が、関数従属性。例: {担当}{フロア}。Xを決定項 という また、一意に識別するための属性が候補キーといい、そうでない属性を非キー属性 管理者 担当 業務内容 フロア 火気責任者 薗課長 設備 設備管理 4F 小島 薗課長 第一開発 ホスティング基盤開発 4F 小島 薗課長 第一開発 MailLuck?開発運用 4F 小島 薗課長 第一開発 サービス運用 4F 小島 日浦課長 第二開発 サービス運用 2F 日浦 横井課長 第二開発 サービス運用 2F 日浦 候補キー{管理者,担当,業務内容} 候補キー{管理者,担当,業務内容} 非キー属性 関数従属性の例 • さっきの関係から、関数従属性の組を挙げてみよう。 – – – – – – {担当}{管理者} {管理者}{フロア} {担当}{フロア} === {担当}{管理者}{フロア} {フロア}{火気責任者} {管理者}{火気責任者}etc… {業務内容}{フロア}はダメ!(サービス運用は2Fと4Fでやってる) 管理者 担当 業務内容 フロア 火気責任者 薗課長 設備 設備管理 4F 小島 薗課長 第一開発 ホスティング基盤開発 4F 小島 薗課長 第一開発 MailLuck?開発運用 4F 小島 薗課長 第一開発 サービス運用 4F 小島 日浦課長 第二開発 サービス運用 2F 日浦 横井課長 第二開発 サービス運用 2F 日浦 第二正規形への道 • 非キー属性{フロア}が、{担当}{フロア}のように、 候補キーを決定項としない関数従属しか存在し ない場合は、第二正規形とは言えない。 • 候補キーを決定項としない関数従属の関係を結 合関係に書き換えると、第二正規形になる 管理者 担当 業務内容 担当 フロア 火気責任者 薗課長 設備 設備管理 設備 4F 小島 薗課長 第一開発 ホスティング基盤開発 第一開発 4F 小島 薗課長 第一開発 MailLuck?開発運用 第二開発 2F 日浦 薗課長 第一開発 サービス運用 日浦課長 第二開発 サービス運用 横井課長 第二開発 サービス運用 第二正規形の定義 • 第一正規形で、非キー属性がすべて候補 キーを決定項とする関数従属の場合 • 非キー属性がない場合も、もちろん第二正規 形 候補キーは、{管理者,担当,業務内容}なので非キー属性なし 管理者 担当 業務内容 担当 フロア 火気責任者 薗課長 設備 設備管理 設備 4F 小島 薗課長 第一開発 ホスティング基盤開発 第一開発 4F 小島 薗課長 第一開発 MailLuck?開発運用 第二開発 2F 日浦 薗課長 第一開発 サービス運用 日浦課長 第二開発 サービス運用 横井課長 第二開発 サービス運用 {担当}が候補キー {担当}{フロア} {担当}{火気責任者} あと、{フロア}{火気責任者} 第三正規形への道 • よく見ると、まだ冗長だね 担当 フロア 火気責任者 設備 4F 小島 第一開発 4F 小島 第二開発 2F 日浦 • 関数従属性は – {担当}{フロア}, – {フロア}{火気責任者}, – {担当}{フロア}{火気責任者} フロアと火気責任者が冗長 • こういうAB, BC, ACといった関数従属性を、「推移的な関数 従属」という 第三正規形の定義 • 第二正規形のうち、すべて非推移的な関数従属と なっているもの • 平たく言うと、表の主キー以外の属性は、主キーから 一意に決まるようになっていること。主キーを構成する 属性がどうなっているかは問わない。 • 推移的な関数従属性があった場合、結合関係に置き 換えれば第三正規形になる 担当 フロア フロア 火気責任者 設備 4F 4F 小島 第一開発 4F 2F 日浦 第二開発 2F 第三正規形の例 • ルール 学生 科目 顧問 加藤 国語 井上 加藤 理科 太田 加藤 算数 小原 多田 国語 井上 • 候補キーと関数従属性は、 多田 算数 大原 – 学生は、科目を受講す ると、顧問が決まる。 – 顧問は一つの科目の担 当になる。 – 学生は複数の科目を受 講する。 – {学生,科目}顧問 – {学生,顧問}科目 の二通り考えられる。 • ・・・なんかおかしくない? 井上先生が国語の顧問であることが冗長 ｛顧問}{科目} という関数従属性があるが、科目は候補 キーを構成する属性なので第三正規形で はあるが… Boyce/Codd normal form; BCNF! • 候補キーを構成する属性が、非 キー属性を決定項とする関数従属 がない場合 • つまり、関係上の関数従属性の決 定項がすべて候補キーである場合 をBCNFといいます。 • 平たく言うと、表のすべての属性は、 表の主キーだけに従属して決まると いう状況のこと(ふつうそう作るよね) • 単一のキーの場合、第三正規形ま で分解すると、BCNFも必ず満たしま す 学生 顧問 加藤 井上 加藤 太田 加藤 小原 多田 井上 多田 大原 顧問 科目 井上 国語 太田 理科 小原 算数 大原 算数 BCNFの例 • 候補キーは{担当,業務内容, 管理者}。 – 担当は、複数の業務内容 をもつ。 – 担当は、複数の管理者を 持つ – 非キー属性がないので、 BCNFだが…. • なんか変? – ここで第二開発に管理者 追加すると、業務内容も入 れないといけない。 – 担当を決めると管理者群 が決まり、担当を決めると 業務内容群が決まるが、管 理者と業務内容は独立し ている。 管理者 担当 業務内容 薗課長 設備 設備管理 薗課長 第一開発 ホスティング基盤開発 薗課長 第一開発 MailLuck?開発運用 薗課長 第一開発 サービス運用 日浦課長 第二開発 サービス運用 横井課長 第二開発 サービス運用 多値従属性と第四正規形 • 多値従属とは、 – • ３つの属性A,B,Cについて、ある属性Aの値をを決めると属性Bの値集合が決まり、属性Cには関係しない という従属性(1:nの関係) 先の例だと、候補キーが{担当,業務内容,管理者}に対して、 – 担当を決めると、{管理者}にかかわらず業務内容群が決まる。 – 担当を決めると、{業務内容}にかかわらず管理者群が決まる • • • {担当}->->{業務内容} {担当}->->{管理者} 候補キーではない属性への多値従属性がないのが第四正規形 – 先のBCNFの例では、担当名が決まると、業務内容群が決まるが、担当名は候補キーではない。 管理者 担当 業務内容 薗課長 設備 設備管理 薗課長 第一開発 ホスティング基盤開発 薗課長 第一開発 MailLuck?開発運用 薗課長 第一開発 サービス運用 日浦課長 第二開発 サービス運用 横井課長 第二開発 サービス運用 第四正規形の例 • 先の例は、 – {担当}->->{サービス}, – {担当}->->{管理者} へ分割すると第四正規 形になる 担当 業務内容 設備 設備管理 第一開発 ホスティング基盤開発 第一開発 MailLuck?開発運用 第一開発 サービス運用 第二開発 サービス運用 付録: 第2正規形から第3正規形へ分解するときに分 離した関係 担当 管理者 設備 薗課長 第一開発 薗課長 担当 フロア 設備 4F フロア 火気責任者 第二開発 日浦課長 第一開発 4F 4F 小島 第二開発 横井課長 第二開発 2F 2F 日浦 第四正規形で十分かな? • ルール – – – 組織は複数の指定された拠 点をもつ 組織は指定された複数の業 務を行う 業務は指定された複数の拠 点で行うことができる 組織 拠点 業務 CS 神田 監視 CS 神田 保守 CS 西新橋 運用 DC 西新橋 運用 西新橋 保守 候補キーでない属性への多値 DC 従属性はないので第四正規形。 (３つの属性で独立しているの はないよね) でもなんか変?... 西新橋が運用拠点であるとい う事実が冗長 もっとなんとかできそうな気が するけど…. 第五正規形 • 第五正規形 (fifth normal form; 5NF) を満た すリレーションは、そのリレーションが第四正 規形であり、さらにそのリレーションに含まれ る結合従属性の決定項が候補キーのみであ る場合 – 結合従属性とは、関係RをA,Bに分解しても、結合 してもとに戻せる場合にRは、*{A,B}の結合従属 性があるという。結合条件となる属性を決定項と いいます。 再構成できるように分解できるか? 実はルール を関係として 書き下せばで きる! 組織 拠点 業務 CS 神田 監視 CS 神田 保守 CS 西新橋 運用 DC 西新橋 運用 組織は複数の指定され た拠点をもつ DC 西新橋 保守 組織は複数の指定され た業務を行う 組織 拠点 拠点 業務 組織 業務 CS 神田 神田 監視 CS 監視 CS 西新橋 神田 保守 CS 保守 DC 西新橋 西新橋 運用 CS 運用 拠点は複数の指定され た業務で行うことが できる 西新橋 保守 DC 運用 DC 保守 まとめ • 第二正規形 – 非キー属性は、候補キーに関数従属すること • 第三正規形 – 第二正規形で、非キー属性が候補キーに非推移的関数従属すること • 推移的従属性がある場合、関係を分けて結合従属性に置き換えることができる • BCNF – 候補キーの部分属性が、非キー属性に関数従属していないこと • 候補キーの部分属性が、非キー属性に関数従属している場合、関係を分けて結合従 属性に置き換えることができる。 以下は、複合キーを持つ場合や、「関係(表)間の結合関係」を表す関係(表) の場合に必要となる正規形 • 第四正規形 – 候補キーでない属性への多値従属性(属性間の独立関係)がないこと • 候補キーでない属性への多値従属性を結合従属性におきかえることができる。 • 第五正規形 – 結合従属性の決定項が候補キーのみで構成されること まとめ(ふたたび) さて、最初に出て きた、この{管理者, 担当,業務内容}の 関係は、どんな関 係? 多値従属性があ るので分割できそ う 管理者 担当 業務内容 薗課長 設備 設備管理 薗課長 設備 ホスティング基盤開発 薗課長 設備 MailLuck?開発運用 薗課長 設備 サービス運用 薗課長 第一開発 設備管理 薗課長 第一開発 ホスティング基盤開発 薗課長 第一開発 MailLuck?開発運用 薗課長 第一開発 サービス運用 薗課長 第二開発 設備管理 薗課長 第二開発 ホスティング基盤開発 薗課長 第二開発 MailLuck?開発運用 薗課長 第二開発 サービス運用 日浦課長 設備 設備管理 日浦課長 設備 ホスティング基盤開発 日浦課長 設備 MailLuck?開発運用 日浦課長 設備 サービス運用 日浦課長 第一開発 設備管理 日浦課長 第一開発 ホスティング基盤開発 日浦課長 第一開発 MailLuck?開発運用 日浦課長 第一開発 サービス運用 日浦課長 第二開発 設備管理 日浦課長 第二開発 ホスティング基盤開発 日浦課長 第二開発 MailLuck?開発運用 日浦課長 第二開発 サービス運用 横井課長 設備 設備管理 横井課長 設備 ホスティング基盤開発 横井課長 設備 MailLuck?開発運用 横井課長 設備 サービス運用 横井課長 第一開発 設備管理 横井課長 第一開発 ホスティング基盤開発 横井課長 第一開発 MailLuck?開発運用 横井課長 第一開発 サービス運用 横井課長 第二開発 設備管理 横井課長 第二開発 ホスティング基盤開発 横井課長 第二開発 MailLuck?開発運用 横井課長 第二開発 サービス運用 まとめ(ふたたびその２) • 多値従属性があ るので分割して みたが、まだ残っ ている。 管理者 担当 管理者 業務内容 薗課長 設備 薗課長 設備管理 薗課長 第一開発 薗課長 ホスティング基盤開発 薗課長 第二開発 薗課長 MailLuck?開発運用 日浦課長 設備 薗課長 サービス運用 日浦課長 第一開発 日浦課長 設備管理 日浦課長 第二開発 日浦課長 ホスティング基盤開発 横井課長 設備 日浦課長 MailLuck?開発運用 横井課長 第一開発 日浦課長 サービス運用 横井課長 第二開発 横井課長 設備管理 横井課長 ホスティング基盤開発 横井課長 MailLuck?開発運用 横井課長 サービス運用 – {管理者}->->{担 当} – {管理者}->->{業 務内容} 業務内容 無関係という 設備管理 ホスティング基盤開発 MailLuck?開発運用 サービス運用 管理者 担当 薗課長 設備 日浦課長 第一開発 横井課長 第二開発 まとめのまとめ • 候補キーが単一属性の場合、第三正規形とBCNFは同じ。 • 正規化は、さまざまな従属性というビジネスルールという か制約を、結合従属性で関係を表現する手法。 – 第三正規形(BCNF)まではキーと非キーのn:1関係を、第四、第 五は関係(表)間の1:nやn:m関係がターゲットになっている • 正規化は、無損失で分解可能なものを指しているが、間 違えて分解すると、元に戻せなくなる(従属性の損失)こと がある。それは、正規化がいけないのではなく、間違った 分解をしているだけ。 • 第五正規形は、復元可能な分解を極限まで行っているこ とから、きちんと結合しないと、嘘の情報をだすことがある。 – 第３正規形や第２正規形へ分解・結合するときにも間違えるこ とがある。これは気を付けよう。
© Copyright 2024 ExpyDoc
