SQLで全称量化（全ての集合xは条件Pを満たす）を存在量化の同値変換（NOT EXISTS）で表現する方法

## 全称量化と存在量化

SQLを支える基礎理論には、集合論と述語理論（predicate logic）があります。

SQLでいう述語とは、戻り値が真理値になる関数のことを言うそうです。

述語論理には、全称量化と存在量化が存在します。

それぞれ、以下のような意味です。

- 全称量化は「すべてのxが条件Pを満たす」
    - 例：すべてのサメは肉食である
- 存在量化は「条件Pを満たすxが(少なくとも1つ)存在する」
    - 例：魚類の中には肉食に分類されるものも存在する

SQLは、全称量化を実装していないそうです。

存在量化の表現を、ド・モルガンの法則を使って、全称量化表現ができるからです。それが `NOT EXISTS` です。 

- 全称量化は
    - 「すべてのxが条件Pを満たす」 = 「条件Pを満たさないxが 存在しない」（これは`NOT EXISTS`で表現できる）
        - 二重否定で分かりにくいですが、結構使えます。
- 存在量化
    - 「条件Pを満たすxが(少なくとも1つ)存在する」 = 「すべてのxが条件Pを満たさない　わけではない」

## 実践してみましょう(1)

EXISTS述語を使った全称量化、つまり、`NOT EXISTS`の表現の練習です。

下記のようなテストの結果テーブルがあるとします。

その中から **「すべての教科で50点以上の student_id を取得したい」** 場合、どうしますか？

| id  | student_id | subject | score |
| --- | ---------- | ------- | ----- |
| 1   | 100        | math    | 100   |
| 2   | 100        | lang    | 80    |
| 3   | 100        | science | 80    |
| 4   | 200        | math    | 80    |
| 5   | 200        | lang    | 95    |
| 6   | 300        | math    | 40    |
| 7   | 300        | lang    | 90    |
| 8   | 300        | history | 55    |
| 9   | 400        | math    | 80    |

Schema

```sql
CREATE TABLE scores (
  id INT NOT NULL PRIMARY KEY auto_increment,
  student_id INT,
  subject TEXT,
  score INT
);
    
INSERT INTO scores VALUES
   (1, 100, 'math',   100),
   (2, 100, 'lang',    80),
   (3, 100, 'science', 80),
   (4, 200, 'math',    80),
   (5, 200, 'lang',    95),
   (6, 300, 'math',    40),
   (7, 300, 'lang',    90),
   (8, 300, 'history', 55),
   (9, 400, 'math',    80);
```

目視で確認できるので、してみると、`100, 200, 400` だと分かります。

Query

```sql
SELECT DISTINCT student_id
FROM scores S1
WHERE EXISTS (
	SELECT *
	FROM scores S2
	WHERE S2.student_id = S1.student_id
 		AND S2.score > 50
)
```

Results

| student_id |
| ---------- |
| 100        |
| 200        |
| 300        |
| 400        |

これはでは、`student_id` 300 が含まれてしまいます。

なぜか

`student_id`300の`score`の中に、50点以上のものが含まれてしまうからです。

先ほどのクエリは存在量化的なクエリだと言えます。

> 存在量化は「条件Pを満たすxが(少なくとも1つ)存在する」

先ほどのクエリでは

　「50点以上の教科が（1つでも）存在する student_id を取得したい」

という条件になってしまっています。

今回欲しいのは **「すべての教科で50点以上の student_id を取得したい」** 場合です。

こんな時に使うのが、全称量化的なクエリです。

> 全称量化は「すべてのxが条件Pを満たす」

`NOT EXISTS` を用いることで全称量化的な結果を取得できます。

日本語にすると、

「50点以下の教科が1つも存在しない」です。繰り返しますが、これは`NOT EXISTS`で表現できます。

Query

```sql
SELECT DISTINCT student_id
FROM scores S1
WHERE NOT EXISTS (
	SELECT *
	FROM scores S2
	WHERE S2.student_id = S1.student_id
 		AND S2.score < 50
)
```

Results

| student_id |
| ---------- |
| 100        |
| 200        |
| 400        |

## 実践してみましょう(2)

次の条件を満たす結果を出力するクエリを書いてください。

```
- math が 80 以上
- lang が 50 以上
```

（langのデータが無い場合も含めます）

上の条件を以下のように読み替えれば、全称量化

```
ある学生のすべての行について、教科がmathならば80以上あり、langならば50以上ある
```

Query

```sql
SELECT DISTINCT student_id
FROM scores S1
WHERE subject IN ('math', 'lang')
AND NOT EXISTS
    (SELECT *
     FROM scores S2
     WHERE S2.student_id = S1.student_id
     AND 1 = CASE WHEN subject = 'math' AND score < 80 THEN 1
                  WHEN subject = 'lang' AND score < 50 THEN 1
                  ELSE 0 END)
```

まず、mathとlang以外は見ないので、絞る。

math が 80 以上、 lang が 50 以上という条件を裏返しにして、`NOT EXISTS`のサブクエリを入れれば完成です。

Results

| student_id |
| ---------- |
| 100        |
| 200        |
| 400        |

では次に、langのデータが存在しない生徒を除外する方法を考えます。

これは、2教科分、存在せねばいけないので、`GROUP BY` した結果に対して、`HAVING`で行数を数えればいいと思います。

```sql
SELECT student_id
FROM scores S1
WHERE subject IN ('math', 'lang')
AND NOT EXISTS (
    SELECT *
    FROM scores S2
    WHERE S2.student_id = S1.student_id
    AND 1 = CASE WHEN subject = 'math' AND score < 80 THEN 1
                 WHEN subject = 'lang' AND score < 50 THEN 1
                 ELSE 0 END)
GROUP BY student_id
HAVING COUNT(*) = 2
```

（DISTINCT が消えている点にも注意）

Results

| student_id |
| ---------- |
| 100        |
| 200        |

以上です。

## 参照

https://hhelibex.hatenablog.jp/entry/20100430/1272641321

https://shayashiyasugi.com/wwwshayashijp/courses/2015/getu5kouki/20151207.html

https://codezine.jp/article/detail/1420

https://www.amazon.co.jp/dp/4798157821/

89 - 95p

## アウトプット100本ノック実施中

https://qiita.com/ryosuketter/items/713474dbd009870e4103