理論から学ぶデータベース実践入門 ch4 正規化理論(その2)

gihyo.jp

---

まとめ

• 結合従属性
  • 「無損失分解できるような状況」
  • 関数従属性の一般化
• 関数従属性以外の、自明でも暗黙的でもない結合従属性を取り除くと4NF, 5NFを得る
• 6NFは無駄な結合が多く、実用的ではない

結合従属性(JD)

• BCNFで関数従属性を完全に排除した
• まだ終わりではない
• 結合従属性 (JD: Join Dependency)
  • キー自身に冗長性が含まれる

A, B, ..., CをリレーションRの見出しの部分集合であるとする。
もしA, B, ..., Cの射影に対応するリレーションを結合した結果と、
Rが同じ場合かつその場合に限り、Rは次の結合従属性を満たすこととする

☆{A, B, ..., C}

• 候補キーの内部に結合従属性が含まれることは大いにあり得る
  • cf. 関数従属性はない
    • あったら、それは既約な「候補キー」ではない
• 自明な結合従属性
  • A, B, ..., CのどれかがRの見出し全体と同じ
  • リレーションRそのものとRの任意の射影との結合はR
    • 【補】述語の変数が落ちてるだけなので

結合従属性は無損失分解が可能

• 循環定義
• 「結合して元に戻る」ことが定義

関数従属性は結合従属性の一種である

• 関数従属性である ⊃ 無損失分解
• 無損失分解できる ≡ 結合従属性である
• したがって、関数従属性である ⊃ 結合従属性である
• 集合としてはS_関数従属性 ⊆ S_結合従属性

暗黙的な結合従属性

• Implied by Superkeys (スーパーキーによって、暗黙に定義される)
• リレーションRの見出しの部分集合A, B, ..., CがすべてRのスーパーキーである場合
• A, B, ..., Cは共通してRの候補キーを含む

非キー属性と結合従属性

• 下記条件のいずれかを満たすと、BCNFは自動的に5NFの要件を満たす
  • 非キー属性が存在する
    • {RK} → 非キー属性なる関数従属がある
    • RKをさらに分解すると関数従属が壊れるため、これ以上無損失分解できない
      • 分解してもなお非キー属性を特定できるとしたら、それは部分関数従属しており、2NFですらない
  • キーに含まれる属性は1つだけである
    • キー自身の冗長性がない(当然)
• サロゲートキー？？
  • いったん無視してDB設計を進めよ
  • 正規化はナチュラルキーを対象として考えるもの
    • SQLで言われる
      「複合キーを使わず単一キーを使え」
      というのは、リレーショナルモデルでは不可能

結合従属性による正規化(4NF〜6NF)

第4正規形(4NF)

• 一般的に「多値従属性(MVD: MultiValued Dependency)による正規化」と解説されるやつ
• MVDは結合従属性の特殊なパターン
  • 結合従属性を見つけやすくするための道具であるといえる

A, B, CをリレーションRの見出しの部分集合であるとする。
A, B, Cが次の結合従属性を満たす場合かつその場合に限り、
BおよびCはAに多値従属すると言う。

☆{AB, AC}

次のような記号を用いて表現する。

A →→ B
A →→ C

• 例

氏名(RK)	学科(RK)	授業(RK)
桂小五郎	コンピュータアーキテクチャ	リレーショナルモデル
桂小五郎	コンピュータアーキテクチャ	Javaプログラミング
勝海舟	コンパイラ	リレーショナルモデル
勝海舟	コンパイラ	RoR
勝海舟	コンパイラ	コンピュータアーキテクチャ原理
坂本龍馬	データベース	リレーショナルモデル
坂本龍馬	データベース	コンピュータアーキテクチャ原理
坂本龍馬	コンパイラ	リレーショナルモデル
坂本龍馬	コンパイラ	コンピュータアーキテクチャ原理

• 分解する
• 学科所属

氏名(RK)	学科(RK)
桂小五郎	コンピュータアーキテクチャ
勝海舟	コンパイラ
坂本龍馬	データベース
坂本龍馬	コンパイラ

• 授業所属

氏名(RK)	授業(RK)
桂小五郎	リレーショナルモデル
桂小五郎	Javaプログラミング
勝海舟	リレーショナルモデル
勝海舟	RoR
勝海舟	コンピュータアーキテクチャ原理
坂本龍馬	リレーショナルモデル
坂本龍馬	コンピュータアーキテクチャ原理

• 結合して元に戻る
• 【補】分解のしかたによっては無損失分解にならないので注意する:

氏名(RK)	学科(RK)
桂小五郎	コンピュータアーキテクチャ
勝海舟	コンパイラ
坂本龍馬	データベース
坂本龍馬	コンパイラ

学科(RK)	授業(RK)
コンピュータアーキテクチャ	リレーショナルモデル
コンピュータアーキテクチャ	Javaプログラミング
コンパイラ	リレーショナルモデル
コンパイラ	RoR
コンパイラ	コンピュータアーキテクチャ原理
データベース	リレーショナルモデル
データベース	コンピュータアーキテクチャ原理

• 結合するとタプルが増えちゃう

氏名(RK)	学科(RK)	授業(RK)
桂小五郎	コンピュータアーキテクチャ	リレーショナルモデル
桂小五郎	コンピュータアーキテクチャ	Javaプログラミング
勝海舟	コンパイラ	リレーショナルモデル
勝海舟	コンパイラ	RoR
勝海舟	コンパイラ	コンピュータアーキテクチャ原理
坂本龍馬	データベース	リレーショナルモデル
坂本龍馬	データベース	コンピュータアーキテクチャ原理
坂本龍馬	コンパイラ	リレーショナルモデル
坂本龍馬	コンパイラ	RoR
坂本龍馬	コンパイラ	コンピュータアーキテクチャ原理

• リレーションが表現する事実
  • 「坂本龍馬はコンパイラ学科に所属している」
  • 「コンパイラ学科の学生はリレーショナルモデル授業に所属している」
  • 「コンパイラ学科の学生はRoR授業に所属している」
  • 「コンパイラ学科の学生はコンピュータアーキテクチャ授業に所属している」
• 後ろ3つがダウト

第5正規形(5NF)

• 暗黙的ではないすべての結合従属性が取り除かれた状態
  • 3つ以上
    • ☆{AB, BC, CA}

氏名(RK)	学科(RK)	授業(RK)
勝海舟	コンパイラ	C++
勝海舟	コンパイラ	Java
坂本龍馬	コンパイラ	C++
坂本龍馬	コンパイラ	RoR
坂本龍馬	データベース	RoR
坂本龍馬	データベース	リレーショナルモデル
桂小五郎	コンパイラ	Java
桂小五郎	コンピュータアーキテクチャ	Java
桂小五郎	コンピュータアーキテクチャ	OS
桂小五郎	コンピュータアーキテクチャ	コンピュータアーキテクチャ原理

• 分解

氏名(RK)	学科(RK)
勝海舟	コンパイラ
坂本龍馬	コンパイラ
坂本龍馬	データベース
桂小五郎	コンパイラ
桂小五郎	コンピュータアーキテクチャ

氏名(RK)	授業(RK)
勝海舟	C++
勝海舟	Java
坂本龍馬	C++
坂本龍馬	RoR
坂本龍馬	リレーショナルモデル
桂小五郎	Java
桂小五郎	OS
桂小五郎	コンピュータアーキテクチャ原理

学科(RK)	授業(RK)
コンパイラ	C++
コンパイラ	Java
コンパイラ	RoR
データベース	RoR
データベース	リレーショナルモデル
コンピュータアーキテクチャ	Java
コンピュータアーキテクチャ	OS
コンピュータアーキテクチャ	コンピュータアーキテクチャ原理

• 学科により受講可能な授業が制限されている場合など
• 【補】桂小五郎氏に関わるタプルのみ見てみる
• 元の見出し

氏名(RK)	学科(RK)	授業(RK)
桂小五郎	コンパイラ	Java
桂小五郎	コンピュータアーキテクチャ	Java
桂小五郎	コンピュータアーキテクチャ	OS
桂小五郎	コンピュータアーキテクチャ	コンピュータアーキテクチャ原理

• 分割

氏名(RK)	学科(RK)
桂小五郎	コンパイラ
桂小五郎	コンピュータアーキテクチャ

氏名(RK)	授業(RK)
桂小五郎	Java
桂小五郎	OS
桂小五郎	コンピュータアーキテクチャ原理

• ここまでだけだと無損失分解にならない
  • 結合すると余計なタプルが現れる

氏名(RK)	学科(RK)	授業(RK)
桂小五郎	コンパイラ	Java
桂小五郎	コンパイラ	OS
桂小五郎	コンパイラ	コンピュータアーキテクチャ原理
桂小五郎	コンピュータアーキテクチャ	Java
桂小五郎	コンピュータアーキテクチャ	OS
桂小五郎	コンピュータアーキテクチャ	コンピュータアーキテクチャ原理

• 学科による受講可能な授業の制限

学科(RK)	授業(RK)
コンパイラ	C++
コンパイラ	Java
コンパイラ	RoR
コンピュータアーキテクチャ	Java
コンピュータアーキテクチャ	OS
コンピュータアーキテクチャ	コンピュータアーキテクチャ原理

• 下記赤タプルは、上記リレーションの述語に入れると偽になる
  • ので、結合後のリレーションには含まれない

氏名(RK)	学科(RK)	授業(RK)
桂小五郎	コンパイラ	Java
桂小五郎	コンパイラ	OS
桂小五郎	コンパイラ	コンピュータアーキテクチャ原理
桂小五郎	コンピュータアーキテクチャ	Java
桂小五郎	コンピュータアーキテクチャ	OS
桂小五郎	コンピュータアーキテクチャ	コンピュータアーキテクチャ原理

接続の罠(Connection Trap)

• 分解後のリレーションが元のリレーションと同じ事実を表しているように見えない現象

• 坂本龍馬はデータベース学科に所属しており、「ある授業」を受講する
• 坂本龍馬は「ある学科」に所属しており、リレーショナルモデルの授業を受講する
• 「ある生徒」はデータベース学科に所属しており、リレーショナルモデルの授業を受講する

• 【補】「ある〜〜」は射影により落ちた変項
• 罠っぽいだけで、実際には何の罠もない
  • 結合従属性により、元のリレーションに復元できることが保証されるから

結合従属性を発見するのは難しい？

• まず非キー属性を持たず、属性が複数であることで絞りこめる
• 実際に射影をとってみる
  • SQLのSELECT DISTINCT
  • 結合して元のリレーションと同じになれば、結合従属性が存在している可能性がある

第6正規形(6NF)

• 自明な結合従属性以外すべての結合従属性を排除
  • 暗黙的な結合従属性も排除
• 5NFであり6NFでないケース: 非キー属性が複数
• 非キー属性の個数が0個または1個になるまで分解
• 無駄な結合が多く、実用的でない

理論から学ぶデータベース実践入門 ch3 正規化理論(その1)

gihyo.jp

---

まとめ

• BCNFまでの知識だけでも威力高い
  • 自動的に5NFまで満たしていることが多い
    • どういう時そうなるのかは次章
  • BCNFでは自明でない関数従属性が存在しない
• まだ先がある
  • 結合従属性の排除

なぜDB設計は重要なのか

• データと操作はセット
  • OOP
    • 適切にオブジェクトが設計されていないとメソッドは複雑怪奇に
  • RDB
    • 適切に個々のテーブルが設計されていないとクエリは複雑怪奇に
• 正規化理論 (Normalization Theory)
  • リレーショナルモデルにおける設計の王道

正規化

リレーショナルモデルを補完する理論

• リレーショナルモデルそのものの一部ではない
  • 正規化されていなくてもリレーショナルモデル自体は扱える
  • 扱いやすくはない
• 正規化理論はリレーショナルモデルの上に立脚する補完的な理論

異常を防ぐことができる

• 異常(Anomalies)
  • 矛盾が生じている状態
• 矛盾
  • データが論理的な不整合を起こしている状態
• 矛盾が生じたDBに問い合わせて導き出されたデータは一切信用ならない(前章より)
  • Principle of explosion
• 矛盾はなぜ生じるの
  • 重複
• 正規化は重複を排除する

正規形

正規形の種類

• 第1正規形
• 第2正規形
• 第3正規形
• BCNF
• 第4正規形
• 第5正規形
• 第6正規形

第1正規形(1NF)

• リレーションであること
  • リレーショナルモデルの世界では当然満足される
  • リレーショナルモデルではなくSQLに対して課される条件
• つまりどういうこと
  • 行/列が順序付けされていない
    • ダメ:
      • SELECT *して全カラムの値を取り出し、アプリケーションがカラムの位置によってデータにアクセスする
      • ORDER BY 1
  • 重複する行が存在しない
    • 一意性制約により保証できる
      • 必須ではない。実際に重複さえなければ
  • 列の値がアトミックであること
    • 「アトミックである」ってなに
      • ドメインに属する要素の1つであること
  • すべての列の値は定義されたものだけであり、かつそれぞれの行において常に存在する
    • NULLはダメ
      • 「ない」ことをNULLで表現するくらいならテーブル分割しろ

コラム: 列の値はスカラであるべき？

• いいえ
• スカラであることとアトミックであることとは異なる概念
• 列の値はベクトルでもなんでもいい。ドメイン次第
  • リレーショナルモデル的にはリレーションでもよい
    • RVA: Relation Valued Attribute
    • ただしSQLでは非対応

繰り返しグループ

• よくあるダメなやつ
• ドメインの要素を,区切りで1つの列の値に突っ込むなど
• 列持ちもダメ
  • データ1、データ2といった命名になるため、順序を持ってしまう
  • 欠員がある場合NULLが生じる
• リレーションは「事実」
  • 真の命題
• 単に事実を複数述べればよいのである(行持ち)

候補キーとスーパーキー

• 候補キー(RK)
  • そのリレーションに含まれるタプルの値を一意に決められる属性の集合
  • 1種類とは限らないため「候補」
  • リレーショナルモデルの世界では「主キー」はない
    • どれを選ぶかは主観にすぎないため
  • 【疑問点】なんのRなんだろう
    • 参照キー(Reference Key)ってとこか
• スーパーキー(SK)
  • 余計な属性を含むものも含める
• 1NFでは最低でも1つの候補キーが存在する
  • タプルが重複しないため、全属性指定すれば必ずスーパーキーとなり、タプルの値を一意に決められる

関数従属性(FD)

• FD: Functional Dependency

あるリレーションRの見出しの2つの部分集合をA, Bとする。
Rの要素のすべてのタプルにおいて、Aの値が同じならばBの値も同じである場合
かつその場合だけに限り、BはAに関数従属すると言う。 このような関係をA→Bと記述する。

• 自明な関数従属性
  • リレーションの任意の属性はスーパーキーに関数従属する
  • リレーションから取り除くことはできない
• 自明ではない関数従属性
  • 候補キーの真部分集合から非キー属性(Non-Prime Attribute)へのFD (部分関数従属)
  • 非キー属性から非キー属性へのFD (推移的関数従属)
  • 非キー属性から候補キーの真部分集合へのFD (名前ない？)
• 正規化とは、自明ではない関数従属性を排除する作業
  • 隠れたキーを探し出す

コラム: 候補キー内部に自明ではない関数従属性は存在しないのか

• ないよ
• 背理法
  • (前提) 候補キー内部の自明ではない関数従属性があるとする
  • 候補キーの真部分集合をA, Bとする
  • A→B なるFDがある
  • Aだけでキーとしての機能を有することになる
  • 候補キー=キーとして余計な属性を持たないことに矛盾する
  • 前提が誤っている

第2正規形(2NF)

• 部分関数従属(Partial Functional Dependency)を取り除く
• 分解: 射影演算
• 無損失分解(Non-loss Decomposition)
  • 結合で元に戻る
• 無損失分解ができるかどうかの基準が「従属性」

第3正規形(3NF)

• 推移的関数従属(Transitive Dependency)を取り除く
• 無損失分解

ボイスコッド正規形(BCNF)

• 非キー属性から候補キーの真部分集合へのFDを取り除く
• 3NFであるがBCNFでない例

氏名(RK)	学科(RK)	研究室
桂小五郎	コンピュータアーキテクチャ	デバイスドライバ
勝海舟	コンパイラ	最適化
坂本龍馬	データベース	リレーショナルデータベース
坂本龍馬	コンパイラ	最適化
西郷隆盛	データベース	分散データベース
高杉晋作	コンパイラ	並列化コンパイラ
高杉晋作	コンピュータアーキテクチャ	割り込み処理

• このリレーションでは、研究室がわかれば学科がわかる

{研究室} → {学科}

• 3NFであるがBCNFでないリレーションは、候補キーが複数存在する
  • {氏名, 学科}
  • {氏名, 研究室}
• 後者に注目すると…

氏名(RK)	学科	研究室(RK)
桂小五郎	コンピュータアーキテクチャ	デバイスドライバ
勝海舟	コンパイラ	最適化
坂本龍馬	データベース	リレーショナルデータベース
坂本龍馬	コンパイラ	最適化
西郷隆盛	データベース	分散データベース
高杉晋作	コンパイラ	並列化コンパイラ
高杉晋作	コンピュータアーキテクチャ	割り込み処理

• 部分関数従属があるため2NFですらなかった
• 第2正規化する
• 研究室配属リレーション

氏名(RK)	研究室(RK)
桂小五郎	デバイスドライバ
勝海舟	最適化
坂本龍馬	リレーショナルデータベース
坂本龍馬	最適化
西郷隆盛	分散データベース
高杉晋作	並列化コンパイラ
高杉晋作	割り込み処理

• 正規形の次数
  • 非キー属性がないので低くともBCNF
• 研究室学科リレーション

研究室(RK)	学科
デバイスドライバ	コンピュータアーキテクチャ
最適化	コンパイラ
リレーショナルデータベース	データベース
分散データベース	データベース
並列化コンパイラ	コンパイラ
割り込み処理	コンピュータアーキテクチャ

• 正規形の次数
  • 候補キーが1属性しかなく、部分関数従属がないため2NF
  • 非キー属性が1つしかなく、推移的関数従属がないため3NF
  • {学科}から{研究室}への関数従属がないためBCNF
• 3NFではあるがBCNFではない、という場合は、候補キーが他にないかということから検討するとよい

理論から学ぶデータベース実践入門 ch2 述語論理とリレーショナルモデル 3/3

gihyo.jp

---

リレーションの演算と述語論理

• 各種リレーションの演算を述語論理の側面から見る
  • リレーションは集合
  • 集合と述語は1対1対応

制限(Restrict)

• 対象のリレーションに対して新たな述語を導入

P(t)∧Q(t)

• where
  • P(t): リレーションRの述語
  • Q(t): 制限を表現する述語

直積(Product)

• R1とR2という2つの前提となる事実(の集合)から、どのような新たな事実(の集合)が導き出されるか

P(t1)∧Q(t2)

結合(Join)

• 直積は結合の特殊なパターン

P(t1)∧Q(t2)

• 共通の属性が存在
  • zは自由変項なので、P(x, z)のzとQ(y, z)のzとは同じ意味

P(x, y)∧Q(x, z)

R1

shinovi	school
両備	蛇女
雪泉	月閃

R2

shinovi	cup
両備	AAA
両奈	I

R3

shinovi	school	cup
両備	蛇女	AAA

• 他のタプルはP(x, y)またはQ(x, y)を真にしない
• 結合後の述語は1つの意味を持つため、次のようにも表現できる

F(x, y, z)

積(Intersect)

• 結合の特殊なケース
• タプルの属性が完全に一致する

P(t)∧Q(t)

コラム: 結合と制限

• 積と制限は同じ形

P(t)∧Q(t)

• 本質的に同じもの
• 制限: ドメインのすべての組み合わせのうち、Q(t)に適合するものの集合との積

和(Union)

P(t)∨Q(t)

差(Difference)

• ベン図省略

P(t)∧¬Q(t)

• NOT EXISTSで代用できることがひと目でわかる

射影(Projection)

• 述語の変数が落ちる

「xはyという学校に通っている」

• 射影をとると

「xは学校に通っている」

• 「射影」
  • タプルの属性が減る = 次元が低くなる感じ

属性名変更(Rename)

• 論理式としての構造に変化はない

拡張(Extend)

• 論理演算以外の何らかの法則で新たな事実を導き出す
  • 身長と体重からBMIとか

コラム: 外部結合について

• 外部結合はリレーショナルモデルの観点でいう「結合」ではない
• むしろ集合和
  • 【補】ただし、タプルの属性にNULLを含むので集合ですらない説

SELECT t1.x, t2.y
  FROM t1
  LEFT OUTER JOIN t2
    ON t1.z = t2.z;

• 意味的に同じクエリ

SELECT t1.x, t2.y
  FROM t1
 INNER JOIN t2
    ON t1.z = t2.z
 UNION
SELECT t1.x, NULL
  FROM t1
 WHERE t1.z NOT IN (SELECT z
                      FROM t2);

理論から学ぶデータベース実践入門 ch2 述語論理とリレーショナルモデル 2/3

gihyo.jp

---

述語論理とリレーショナルモデル(続き)

命題論理の限界と量化

• 対象となる命題を記号として表現できる限りは十分に実践的
• PとかQとかで表現できない問題がある
  • 集団を対象にした真偽値を問うもの

• この村のすべての村人が正直者だというわけではない
• この村の村人は全員誰かと友達である

• 量化
  • 全称量化 (∀)
    • ある集団の要素のすべてがある性質を満たすか
  • 存在量化 (∃)
    • ある集団の要素にはある性質を満たすものが存在するか

量子化と述語論理

述語論理

• 命題論理の拡張
  • 集団についての性質を記した文章を、変数・量化子・関数を用いて論理式として表現
• 量化子
  • 前述の∀や∃
• 関数・変数
  • 「xは誰かと友達である」をF(x)のように表現
  • xの値により真または偽を返す
  • 命題関数、あるいは述語と呼ぶ
    • だから「述語論理」

この村の村人は全員誰かと友達である

• 上記の文章は次の論理式で表せる

∀xF(x)

この村には正直でない者がいる

• 上記の文章は次の論理式で表せる

∃x¬F(x)

量化子とともに用いる束縛変数

∃xF(x) ∧ ∀xG(x)

• 束縛変数
  • 上記論理式のx
  • 束縛変項とも
• スコープは対象の論理式の中のみ
  • ∧の前後のxは意味が異なる

量化子を伴わない自由変数

• 関数単体で見てみる

F(x) ⊃ G(x)

• 自由変数
  • 上記のx
  • 自由変項とも
• 上記論理式のxはいずれのxも同じ意味

述語論理と集合論

述語と集合とは等価に置き換えが可能

象は草食動物である

∀x(F(x)⊃G(x))

• where
  • F(x): 「xは象である」
  • G(x): 「xは草食動物である」
• すべてのxについてF(x)を評価すると、F(x)が真となるすべてのxが得られる
• 「F(x)が真となるすべてのx」とは、すべての象を含んだ集合
• この集合をS_Fとする

F(x)

• は集合の要素の包含に置き換えられる
  • これも真偽値を返す

x∈S_F

• 同様にG(x)も置き換えて

∀x(x∈S_F ⊃ x∈S_G)

集合の包含関係

• ⊃ (包含、IMP)

P	Q	P⊃Q
T	T	T
T	F	F
F	T	T
F	F	T

• P⊃Qが真となるのは
  • Pが真ならQも真
  • Pが偽ならQは真偽問わない
• つまり、Pが偽でQが真のケースがあるということ
• x∈S_Fが偽でx∈S_Gが真
  • 象ではないが草食動物である
    • 【補】xがシマウマであるケースとか
• 集合の包含関係

S_F ⊆ S_G

• 【補】紛らわしいが、これのオペランドは集合
  • cf. 結合子の⊃のオペランドは真偽値

述語論理の公理系

∀xF(x)

• 集合で置き換え

∀x{x∈S_F}

• S_Fをn個の要素を持つ集合だと仮定
  • 【補】有限集合だけ考えればよい

S_F := {a1, a2, ..., an}

• 具体的な要素を代入して得られる命題と等価

F(a1)∧F(a2)∧...∧F(an)

• 同様に

∃xF(x)

• は下記と等価

F(a1)∨F(a2)∨...∨F(an)

• ∀や∃は∧や∨と似た性質を持つ
• ド・モルガン

¬∃xF(x) ≡ ∀x¬F(x)
¬∀xF(x) ≡ ∃x¬F(x)

• 「この村のすべての村人が正直者だというわけではない」
• 「この村には正直者でない者がいる」

述語論理の公理系の導出規則

• p.39の公理系を拡張

∀の導入

P(c) ⊃ ∀xP(x)

• cは任意の値
• すべての値に対して普遍的に成り立つ規則から、全称記号を用いた表現を導出

∀の除去

∀xP(x) ⊃ P(c)

∃の導入

P(a)⊃∃xP(x)

• P(x)を満たす定項あるいは変項aが存在すれば
  存在量子化を用いた表現の論理式を導出してよい

∃の除去

(∃xP(x)∧(P(c)⊃Q))⊃Q

• 前提1: P(c)⊃Q
  • 任意のcについて普遍的にP(c)⊃Q
• 前提2: ∃xP(x)
  • P(x)を満たすxが存在する
• 結論:
  • Q
• 【所感】前件肯定式の一般化？
  • P(x)が前件にあたる

ドメイン

• 議論領域、領域とも
• 「任意のc」に実際に入れてよいものの集合
  • 「この村の村人」とか

一階述語論理

• ここまで触れてきた述語論理
• 古典論理とも
• リレーショナルモデルのよりどころ

二階述語論理

• 述語の特徴を表現する述語を扱う

「xは、真となるパラメータが1つ以上存在するが、恒真ではない述語である」

• 述語と集合とは1対1対応
• 集合を要素にした集合を扱う論理ともいえる
• 自己言及がある
  • 二階述語自身が二階述語の対象となりうる
• リレーショナルモデルの守備範囲外

リレーションの真の姿

• リレーションには対応する述語がある
  • リレーションは集合
  • 集合には1対1で対応する述語がある
• 述語をF(t)とするとリレーションは∀tF(t)
  • tupleの意

リレーションの意味は論理演算

• リレーションは真の命題の集合である
  • リレーション∀tF(t)の個々のタプルtは、F(t)に代入すると真になる
  • 真の命題すなわち事実
    • リレーションは事実の集合である
• したがって、リレーション演算は論理演算である
  • 本章後半にて対応関係を確認する

閉世界仮説

• Closed World Assumption
  • 述語に代入して真となるのは、リレーションに含まれるタプルだけ
  • 真となる命題は、すべて漏れなく、リレーションに含まれている
• リレーションは事実のすべてを過不足なく含んでいる
• 演算結果の新しいリレーションも、事実のすべてを過不足なく含んでいる
• すべての問いがリレーションの演算だけで解決する

矛盾したDBは役に立たない

• Principle of explosion
  • 矛盾からはいかなる帰結も導出できる
• 矛盾したデータを持つリレーションから導き出された問い合わせの結果はまったく信用ならない

コラム: リレーショナルモデルの限界

• リレーショナルモデルは述語論理(集合論)に基づく
• その枠から外れたデータや演算を表現できない
  • 例
    • グラフ
    • 時系列データ (順序をもつ)
• リレーショナルモデルの範疇を見極めて適用することが肝要

理論から学ぶデータベース実践入門 ch2 述語論理とリレーショナルモデル 1/3

gihyo.jp

---

まとめ

• クロージャ(閉包)
  • リレーションの演算結果はリレーション
  • 述語を組み合わせた結果は述語
• クエリを記述する際の目標: 述語で集合から新しい集合を導出
  • 述語論理と集合論は1:1で対応

述語論理とリレーショナルモデル

• リレーショナルモデルは述語論理に基づいたデータモデルでもある
• 正規化の理解に必須

命題

• ある物事について記述した文で、真か偽か問えるもの

命題論理

• ある命題の真偽値から別の命題の真偽値を導出することに特化した学問
  • 大切なのは真偽値のみ
  • 他の意味を取り去るために命題をPやQなどの記号で表現する
• 結合子
  • 2つあるいは1つの命題から新たな真偽値を導出するための記号
  • 複雑な命題を構築する
  • 種類
    • ¬(否定、NOT)
    • ∧(連言、論理積、AND)
    • ∨(選言、論理和、OR)
    • ⊃(包含、IMP)
    • ≡(同値、EQ)
    • ↑(否定論理積、NAND)
    • ↓(否定論理和、NOR)
    • ⊻(排他的論理和)

P	Q	¬P	P∧Q	P∨Q	P⊃Q
T	T	F	T	T	T
T	F	F	F	T	F
F	T	T	F	T	T
F	F	T	F	F	T

P	Q	P≡Q	P↑Q	P↓Q	P⊻Q
T	T	T	F	F	F
T	F	F	T	F	T
F	T	F	T	F	T
F	F	T	T	T	F

トートロジーと定理

• トートロジー(恒真式)
  • PやQなどの命題の真偽値が何であっても式全体としてつねに真
  • 命題論理では、トートロジーは定理になっている

同一律 P⊃P

P	P⊃Q
T	T
F	T

排中律 P∨¬P

P	¬P	P∨¬P
T	F	T
F	T	T

二重否定律 ¬¬P≡P

P	¬P	¬¬P	¬¬P≡P
T	F	T	T
F	T	F	T

矛盾律 ¬(P∧¬P)

P	¬P	P∧¬P	¬(P∧¬P)
T	F	F	T
F	T	F	T

• P∧¬Pは恒偽式

Principle of explosion (P∧¬P)⊃Q

P	¬P	P∧¬P	Q	(P∧¬P)⊃Q
T	F	F	T	T
T	F	F	F	T
F	T	F	T	T
F	T	F	F	T

• 「前提が矛盾していればいかなる結論も導出できてしまう」というやつ

対偶律 (P⊃Q)⊃(¬Q⊃¬P)

P	Q	P⊃Q	¬Q	¬P	¬Q⊃¬P	(P⊃Q)⊃(¬Q⊃¬P)
T	T	T	F	F	T	T
T	F	F	T	F	F	T
F	T	T	F	T	T	T
F	F	T	T	T	T	T

推移律 ((P⊃Q)∧(Q⊃R))⊃(P⊃R)

P	Q	R	P⊃Q	Q⊃R	(P⊃Q)∧(Q⊃R)	P⊃R	((P⊃Q)∧(Q⊃R))⊃(P⊃R)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	F	T	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	F	T	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

分配律1 P∧(Q∨R) ≡ (P∧Q)∨(P∧R)

P	Q	R	Q∨R	P∧(Q∨R)
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	T	F
F	T	F	T	F
F	F	T	T	F
F	F	F	F	F

P	Q	R	P∧Q	P∧R	(P∧Q)∨(P∧R)
T	T	T	T	T	T
T	T	F	T	F	T
T	F	T	F	T	T
T	F	F	F	F	F
F	T	T	F	F	F
F	T	F	F	F	F
F	F	T	F	F	F
F	F	F	F	F	F

合同

分配律2 P∨(Q∧R) ≡ (P∨Q)∧(P∨R)

P	Q	R	Q∧R	P∨(Q∧R)
T	T	T	T	T
T	T	F	F	T
T	F	T	F	T
T	F	F	F	T
F	T	T	T	T
F	T	F	F	F
F	F	T	F	F
F	F	F	F	F

P	Q	R	P∨Q	P∨R	(P∨Q)∧(P∨R)
T	T	T	T	T	T
T	T	F	T	T	T
T	F	T	T	T	T
T	F	F	T	T	T
F	T	T	T	T	T
F	T	F	T	F	F
F	F	T	F	T	F
F	F	F	F	F	F

合同

ド・モルガン1 ¬(P∨Q)≡¬P∧¬Q

P	Q	¬P	¬Q	P∨Q	¬(P∨Q)	¬P∧¬Q	¬(P∨Q)≡ ¬P∧¬Q
T	T	F	F	T	F	F	T
T	F	F	T	T	F	F	T
F	T	T	F	T	F	F	T
F	F	T	T	F	T	T	T

ド・モルガン2 ¬(P∧Q)≡¬P∨¬Q

P	Q	¬P	¬Q	P∧Q	¬(P∧Q)	¬P∨¬Q	¬(P∧Q)≡ ¬P∨¬Q
T	T	F	F	T	F	F	T
T	F	F	T	F	T	T	T
F	T	T	F	F	T	T	T
F	F	T	T	F	T	T	T

前件肯定式 ((P⊃Q)∧P)⊃Q

P	Q	P⊃Q	(P⊃Q)∧P	((P⊃Q)∧P)⊃Q
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

• 【補】例
  • (前提1) P⊃Q: セックスしたら出られる部屋
  • (前提2) P: セックスした
  • (結論) Q: 出られる
• 後件肯定は誤謬:

P	Q	P⊃Q	(P⊃Q)∧Q	((P⊃Q)∧Q)⊃P
T	T	T	T	T
T	F	F	F	T
F	T	T	T	F
F	F	T	F	T

• 例(誤謬)
  • (前提1) P⊃Q: セックスしたら出られる部屋
  • (前提2) Q: 出られた
  • (結論) P: セックスした
• セックスしていないが出られるケースが存在しうる
  • 実はキスでも出られる部屋かもしれない

後件否定式 ((P⊃Q)∧¬Q)⊃¬P

P	Q	¬P	¬Q	P⊃Q	(P⊃Q)∧¬Q	((P⊃Q)∧¬Q)⊃¬P
T	T	F	F	T	F	T
T	F	F	T	F	F	T
F	T	T	F	T	F	T
F	F	T	T	T	T	T

• 【補】例
  • (前提1) P⊃Q: セックスしたら出られる部屋
  • (前提2) ¬Q: 出られていない
  • (結論) ¬P: セックスしなかった
• 前件否定は誤謬:

P	Q	¬P	¬Q	P⊃Q	(P⊃Q)∧¬P	((P⊃Q)∧¬P)⊃¬Q
T	T	F	F	T	F	T
T	F	F	T	F	F	T
F	T	T	F	T	T	F
F	F	T	T	T	T	T

• 例(誤謬)
  • (前提1) P⊃Q: セックスしたら出られる部屋
  • (前提2) ¬P: セックスしなかった
  • (結論) ¬Q: 出られない
• セックスしていないが出られるケースが存在しうる
  • 実はキスでも出られる部屋かもしれない

選言的三段論法

P	Q	¬P	P∨Q	(P∨Q)∧¬P	((P∨Q)∧¬P)⊃Q
T	T	F	T	F	T
T	F	F	T	F	T
F	T	T	T	T	T
F	F	T	F	F	T

命題論理と公理系

• 定理には前提となる別の定理がある
• どこまでさかのぼれるの？
• 公理
  • 他の定理の出発点となる定理
  • 一切の前提なく正しいと認めましょう、という合意
• 公理系
  • 公理の集合
  • 満たすべき性質
    • 無矛盾性
      • 公理として定義された命題同士に矛盾のなきこと
    • 完全性
      • 扱うテーマにとって包括的に全体をカバーするものであること
  • 1通りではない
• 命題論理の公理系のうち代表的なもの
  • 長いので略(P.39)
• 以下、公理系を出発点とした定理証明
  • 間違ってるかも

Principle of explosion

1. 仮定
   • P∧¬P
2. ∧の除去
   • P
3. ∧の除去
   • ¬P
4. ∨の導入
   • P∨Q
5. 選言的三段論法
   • Q
6. ⊃の導入
   • (P∧¬P)⊃Q
   • 仮定の解消

対偶律

1. 仮定1
   • P
2. 仮定2
   • P⊃Q
3. ⊃の除去
   • Q
4. 仮定3
   • ¬Q
5. ∧の導入
   • Q∧¬Q
6. ⊃の導入
   • P⊃(Q∧¬Q)
   • 仮定1を解消
7. ¬の導入
   • ¬P
8. ⊃の導入
   • ¬Q⊃¬P
   • 仮定3を解消
9. ⊃の導入
   • (P⊃Q)⊃(¬Q⊃¬P)
   • 仮定2を解消

推移律

1. 仮定1
   • (P⊃Q)∧(Q⊃R)
2. 仮定2
   • P
3. ∧の除去
   • P⊃Q
4. ∧の除去
   • Q⊃R
5. ⊃の除去
   • Q
6. ⊃の除去
   • R
7. ⊃の導入
   • P⊃R
   • 仮定2を解消
8. ⊃の導入
   • ( (P⊃Q)∧(Q⊃R))⊃(P⊃R)
   • 仮定1を解消

前件肯定式

1. 仮定
   • ((P⊃Q)∧P)
2. ∧の除去
   • (P⊃Q)
3. ∧の除去
   • P
4. ⊃の除去
   • Q
5. ⊃の導入
   • ((P⊃Q)∧P)⊃Q
   • 仮定を解消

後件否定式

1. 仮定
   • ((P⊃Q)∧¬Q)
2. ∧の除去
   • (P⊃Q)
3. ∧の除去
   • ¬Q
4. 対偶律
   • (P⊃Q)⊃(¬Q⊃¬P)
5. ⊃の除去
   • (¬Q⊃¬P)
6. ⊃の除去
   • ¬P
7. ⊃の導入
   • ((P⊃Q)∧¬Q)⊃¬P
   • 仮定を解消

選言式三段論法

1. 仮定
   • (P∨Q)∧¬P
2. 分配律 (A)
   • (P∧¬P)∨(Q∧¬P)
3. Principle of explosion (B)
   • (P∧¬P)⊃(Q∧¬P)
4. 同一律 (C)
   • (Q∧¬P)⊃(Q∧¬P)
5. (A), (B), (C)より、∨の除去
   • Q∧¬P
6. ∧の除去
   • Q
7. ⊃の導入
   • ((P∨Q)∧¬P)⊃Q
   • 仮定を解消

コラム: プリミティブな演算子

• 導出規則に含まれる結合子
  • ⊃
  • ¬
  • ∧
  • ∨
• 本当にすべて必要なのか？
• いいえ
  • 上記の中では下記の組で全てを表せる
    • ¬と∧
    • ¬と∨
  • 上記にないものでは、NANDあるいはNORひとつで全てを表せる

理論から学ぶデータベース実践入門 ch1 SQLとリレーショナルモデル

gihyo.jp

---

まとめ

• SQLを使う以上、リレーショナルモデルから逃れることはできない
• リレーショナルモデルのリレーションとSQLのテーブルとの間にはさまざまな相違がある
• テーブルをリレーション(集合の一種)の性質に少しでも近づけることが重要

そもそもSQLって？

• リレーショナルデータベースに問い合わせを行う言語
• したがって、リレーショナルモデルがベースになっている

リレーショナルモデルを知らなくてもSQLは書ける？

• そういう人は多い
• が、新にスキルのあるDBエンジニアになるには必修

SQLとリレーショナルモデルって実はあんまり似てないよね？

RDBはリレーショナルモデルを正しく実践してこそ真価を発揮する！

• SQLはリレーショナルモデルをベースとしている
• ので、リレーショナルモデルに沿った演算が得意
• しかし柔軟さゆえ、リレーショナルモデルから逸脱した使い方もできてしまう
  • いつの間にか非常に効率の悪いクエリばかり書くことに
  • SQL文が複雑怪奇に

リレーショナルモデル

• データモデル
  • データをどのように表現するか
• リレーショナルモデル
  • データモデルの一種
    • 他には、KVSとか
• リレーション
  • リレーショナルモデルにおける最重要概念

リレーションの定義

• ERD: Entity Relationship DiagramのRelationshipは関係ない
• Relationに相当するのはテーブルそのもの
• リレーションの構成要素
  • 見出し(Heading)
    • n個の属性の集合
    • 属性(Attribute)
      • 名前とデータ型とのペア
  • 本体(Body)
    • タプルの集合
    • タプル(tuple)
      • 属性値の集合
      • 属性値は見出しで定義されたものと一致すること
• リレーショナルモデルとSQLにおける各オブジェクトの対応
  • ただし厳密に対応するものではない(後述)

リレーショナルモデル	SQL
リレーション	テーブル
タプル	行
属性	カラム

集合とリレーショナルモデル

• リレーションは集合の一種
  • 集合の性質をもつ
• 集合(Set)
  • ものの集まり
• 要素、元(Element)
  • 集合に含まれる個々のもの
  • 満たすべき要件
    • 集合に含まれているかを不確定要素がなく判定できる
      • unknownはダメ
    • 重複してはいけない
      • 含まれているか、いないかのみ
      • 何個含まれているか、が演算結果に影響を及ぼしてはならない
    • それ以上分割できない
• リレーショナルモデルとNULL
  • NULLはunknownを表すマーカーなので集合には含められない
  • よってリレーションにも含められない
• 有限集合と無限集合
  • 異なる性質をもつもの
  • コンピュータで表現する以上、有限集合のみ考えれば良い

リレーションの演算

• データと演算はセットになって初めて役に立つ
• 演算
  • 制限(Restrict)
    • 特定の条件に合うタプルのみ含んだリレーションを返す
    • 元のリレーションの部分集合
  • 射影(Projection)
    • 特定の属性だけを含んだリレーションを返す
    • タプルに重複が生ずることがある
      • その場合、同一のタプルとみなされる
        • 集合だから「何個含まれるか」は演算結果に影響しない
  • 拡張(Extend)
    • 属性を増やす
      • たいていderivative
  • 属性名変更(Rename)
  • 和(Union)
    • 2つのリレーションに含まれるすべてのタプルで構成されるリレーションを返す
    • 重複は解消
  • 積/交わり(Intersect)
    • 2つのリレーションの共通部分になっているリレーションを返す
  • 差(Difference)
    • 2つのリレーションのうち一方のリレーションにのみ含まれるタプルから構成されるリレーションを返す
    • 交換則成り立たない
  • 直積(Product)
    • 2つのリレーションのタプルをそれぞれ組み合わせたリレーションを返す
    • 生成されたリレーションの見出しには2つのリレーションの見出しが持つ属性がすべて含まれる
  • 結合(Join)
    • 共通の属性を持つ2つのリレーションを、その共通の属性の値が同じタプル同士組み合わせたリレーションを返す
• SQLの「外部結合」はリレーションの演算には含まれない
  • 結果にNULLを含む可能性があるため
• 積、直積は結合の特殊なパターン
  • 積: 属性がすべて共通
  • 直積: 共通の属性が存在しない

コラム: 要素にNULLが含まれていると……

• NULLはリレーショナルモデルを根底から覆す不穏因子
• unknownが絡むため論理的に正しい答えは得られようもない

クロージャという性質

• リレーションの演算は閉包
  • 数珠つなぎのように演算を記述できるため非常に重要
  • リレーショナルモデルの真骨頂

リレーショナルモデルにおけるデータ型

• ドメインとも
• とりうる値の集合
• タプルが取りうる値は、属性のドメインの直積
• リレーショナルモデルはなにもかも集合
  • リレーション
    • 見出し
    • 本体
      • タプル
        • 属性のデータ型

SQLにおけるリレーション操作

• DMLとの対応関係

SELECTの基本形

  FROM テーブルのリスト  -- 直積
 WHERE 検索条件  -- 制限
SELECT カラムのリスト  -- 射影
;

• RDBの中核たるSELECT文からして3つのリレーション演算からなる
• 論理的には上記の順番
  • 実装上は最適化が行われ、変わるだろうが…
    • 行の直積集合全部をフェッチするわけはない
  • SELECT句の中で定義したエイリアス(拡張、属性名変更)をWHERE句で使えない理由

INSERT(挿入)

• SQLにおけるテーブルは値と変数の両方の役割をもつ
• リレーションは値である
  • 値そのものをmodifyするわけではない

a = a + 1;

• Relvar(Relation Variable, 関係変数)
  • 値の入れ物
• INSERT:Relvarに格納されたリレーションを新しいリレーションに置き換える操作
  • 新しいリレーション: 和集合

R := R ∪ {T}

DELETE(削除)

R := R - {T}

• 差集合

UPDATE(更新)

R := (R - {T}) ∪ {T2}

1. WHERE句の条件に適合するリレーション{T}との差集合をとり
2. 修正を加えたリレーション{T2}との和集合をとる

SQLにあってリレーショナルモデルにないもの

• SQLをリレーショナルモデルに沿って使うためには封印する必要がある

要素の重複

• 制約がない場合、行が重複してもSQL上エラーにならない
• ここにおいて、テーブルはそもそも集合(Set)でない
  • あえて言えばMultiset
  • SetとMultisetの性質は異なる
• テーブルを集合と同じように使うには何らかの一意性制約が必要

要素間の順序

• SQLには順序が存在する
  • カラム
    • カラム位置
  • 行
    • ROWNUM関数、ORDER BY句

リレーションの更新

• テーブルは値と変数の両方の機能を有し、mutable
• リレーションは値であり、immutable

トランザクション

• 値と変数の両方の機能を有する、SQLのテーブルならでは
  • cf. リレーションはそもそも更新できないためACID特性は一切関係ない
  • SQLだからこそ意味のある概念

ストアドプロシージャ

• 集合演算を真っ向から否定する行為

NULL

• Not Applicable / Unknown
• 値ではないため集合に含めることはできない

コラム: リレーショナルモデルは古典的か

• 重要なのは、リレーショナルモデルの限界を知ること
  • リレーショナルモデルを適用できる部分と、そうでない部分とを見極めよ
  • 適用可能な部分ではしっかりと実践せよ
• リレーショナルモデルの解釈自体を歪めるのはNG
  • 例
    • NULLの許容
    • 属性やタプルに順序があるものと考える
  • 数学的な正しさから乖離する
• 【所感】関数型プログラミングと似たものを感じる
  • 完全に副作用を排すると目の前の箱が熱くなるだけ
  • 純粋関数部分と副作用のある部分とを分けることが肝要

Laravel shibuya #2 IRTメモ

PHP

テストコードについて学んだほうが良いのか

自分が思ったやつとか思い出したやつとかは【補】

• テストコード書くと工数が減るってほんと？？
  • そもそも工数が減ると聞いたことが無い
  • 不具合減る
• コストかかるよね
  • あとから効いてくる
    • 【補】Economics of Test Automation (xUnit Test Patterns)
      • qiita
  • そもそもテストしやすいコードを書こう
    • テストの工数削減に効いてくる
    • 設計能力の向上も見込める
  • 【補】テストコードのリファクタ
• 仕様変更時などにありがたみがある
  • ケースによりありがたみが変わる
    • お硬いB2B: そもそも直させてもらえるまでが長い
      • あまりありがたみがない
    • B2C: 契約とか結んでなくてもユーザが困ってるから直す
      • 何度も回すのでありがたみがある
• ちょっとずつ積み上げ
  • いきなりドカッと書くのは無理
• どこまで書く
  • 結局プロジェクトによる
    • レイヤードアーキテクチャでレイヤー切りまくり？
    • M・V・C？
  • ユニットテストは書かず、結合テストのみという選択
    • カバレッジは見る
• テストコードはエンジニアの不安を解消する
  • 一歩一歩仕様を固めていく
• テスト書けるのはエンジニアとして結構レベル高い
• エッジケースは自動テストが有用
• テストをしない理由
  • 対象機能の重要度が低い
    • 非常に軽微で、かつ全然使われていない画面
  • 対象機能への改修がない
  • スピード重視
• 内外どちらから書く
  • unit/featureどちらも同じくらい

Laravelはできるけど、PHPのOOPがわからない

• クラスをどう切ってどう置くの
  • F/Wに乗っかる
• クラス切るときとかにテスト必要だよね
  • テスト書かないリファクタはNG
• SOLID原則勉強しよう
  • クラスが永遠に増え続けるのどうするの
    • 巨大なクラスよりはよいのでは
    • 人手が少ないとつらい
      • IDE(PHPStorm)の力があればそんなにつらくない
• やりすぎてもいけない
  • 勘と経験
    • 元も子もない...
    • 痛い目を見て覚える
• 先人の「痛い目」の追体験としてのデザインパターン
  • 勉強するうえでも、経験と照らすと腹落ちしやすい
• OOPもデザインパターンも手段にすぎない
  • 目的にならぬよう
  • その手段が解決しようとしているものは何なのか？

Laravel

• 参加してないので「まとめ」のみ聞いた

コード保守に秩序をもたらすには

• みんなが「俺の設計が最高」と言う
• 民主主義
  • メリットとデメリットで比較衡量して多数決

フルスクラッチノーF/Wべた書きPHPをLaravelに移行したい

• そもそもOOPじゃない、とか
• まず仕様をテストコードで表現することから始める
  • 外部仕様(E2Eテスト)はseleniumとかで
  • いきなりがっつり書くのは大変なので並行運用できるとよい

LaravelのAPI開発何を気をつける

• 既存の複雑なDBをEloquentにしていくのはつらい
  • DBリファクタリング
• テストデータどう作る
  • Factory
    • パターンたくさん
      • そもそも全部テストする必要あんの
      • FactoryにFactoryを重ねる？？(よくわからない)

フロント

• Vue.js
  • 別repo?