全称量化と存在量化
SQLを支える基礎理論には、集合論と述語理論（predicate logic）があります。
SQLでいう述語とは、戻り値が真理値になる関数のことを言うそうです。
述語論理には、全称量化と存在量化が存在します。
それぞれ、以下のような意味です。
- 全称量化は「すべてのxが条件Pを満たす」
- 例：すべてのサメは肉食である
- 存在量化は「条件Pを満たすxが(少なくとも1つ)存在する」
- 例：魚類の中には肉食に分類されるものも存在する
SQLは、全称量化を実装していないそうです。
存在量化の表現を、ド・モルガンの法則を使って、全称量化表現ができるからです。それが NOT EXISTS です。
- 全称量化は
- 「すべてのxが条件Pを満たす」 = 「条件Pを満たさないxが 存在しない」（これは
NOT EXISTSで表現できる）- 二重否定で分かりにくいですが、結構使えます。
- 「すべてのxが条件Pを満たす」 = 「条件Pを満たさないxが 存在しない」（これは
- 存在量化
- 「条件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
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
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_id300のscoreの中に、50点以上のものが含まれてしまうからです。
先ほどのクエリは存在量化的なクエリだと言えます。
存在量化は「条件Pを満たすxが(少なくとも1つ)存在する」
先ほどのクエリでは
「50点以上の教科が（1つでも）存在する student_id を取得したい」
という条件になってしまっています。
今回欲しいのは 「すべての教科で50点以上の student_id を取得したい」 場合です。
こんな時に使うのが、全称量化的なクエリです。
全称量化は「すべてのxが条件Pを満たす」
NOT EXISTS を用いることで全称量化的な結果を取得できます。
日本語にすると、
「50点以下の教科が1つも存在しない」です。繰り返しますが、これはNOT EXISTSで表現できます。
Query
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
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で行数を数えればいいと思います。
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 |
以上です。
参照
89 - 95p
アウトプット100本ノック実施中