序文

• SQLを支える基礎理論は2つ

  • 集合論
  • 述語論理(predicate logic)

• SQLで使う述語論理は、「一階述語論理」…行の集合 = テーブルを対象とする

  • 0階: 行対象
  • 二階: 行の集合の集合 = テーブルの集合を対象とする

• EXISTSは「量化」(quantification)を実現するために導入されたもの

  • 全称量化 (ALL,∀)
  • 存在量化 (Exists,∃)

理論編

述語とは何か

• 論理値を返す関数

  • SQLは三値論理なのでt/f/u
• 命題の分析に関数的アプローチを持ち込んだ点が画期的
• テーブルは「行の集合」であるが、述語論理的に解釈すると、命題の集合(=文の集合)とみなせる

この表の1行目は「田中は男性で、28である」という命題を表す

• WHERE句も、述語を組み合わせて1つの述語を作っているとみなせる

  • WHERE句全体としてtrueに評価される命題のみを抽出

存在の階層

• =やBETWEENなどと、EXISTSとの違いは、引数

  • 前者: 1行を引数にとる(一階の述語)

    • 「1行」はスカラ、0階の存在

  • 後者: 行の集合を引数にとる(二階の述語)

    • 「行の集合」は集合、一階の存在
    • 高階関数である

全称量化と存在量化

全称量化

• 「すべてのxが条件Pを満たす」
• For All x, …
• ∀xPx

存在量化

• 「条件Pを満たすxが(少なくとも1つ)存在する」
• There Exists x that …
• ∃xPx

変換公式

• ∀xPx = ￢∃x￢Px

  • すべてのxが条件Pを満たす = 条件Pを満たさないxは一つも存在しない

• ∃xPx = ￢∀x￢Px

  • 少なくとも1つのxが条件Pを満たす = すべてのxが条件Pを満たさないわけではない

SQLには∃にあたるEXISTSのみがある