「SQL の相関サブクエリ (4) - SELECT 句で使う」 のつづき
今回も 前回と同じデータベース を使う。構造は以下の通り。
![CropperCapture[3]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vBxqVMyPraUL9V_KB18iaYSFbIlzf9w8cm4-Q3pHO0wnglEw6MKfQsh0Duivao3fuM8LB74xJ9otZKxr9MZ_jJwBUEoJ5nQ-CUohjzCqkTkwjVZkwYMjNm7WzPXTci5g=s0-d)
ここから、
すべての 「グループ」 に 「割当て」 られたことがある 「人」
を抽出したい。
データベースの内容をオブジェクト図で示すと、一見して目的の人がわかる。
![CropperCapture[1]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tzBwruOvpgsCkiRWnEhP_LFHTp6jJjMUsgpwXWyMNIBbPSEWBLyg07R8eGmAHHyG6jSbaN6uFkwejgdEWV0qBIu-D0nh30SCL1vAf774gypXHUQCeF0VU5NI0YbSVYqQ=s0-d)
Tarou だけが 3 つのグループすべてに 「割当て」 られた。 Jirou, Saburou は割当てがされてるものの 1 グループに対してのみ。
では、これを SQL で書くにはどうしたらいいのか？
これまでと同じように、特定の条件に一致する 「人」 を抽出したいので、
select *
from persons
where exists (select *
from ...
と書き始めてみたものの、
「すべての x は p である」
という形式をどのように表現するのだろう？
exists 述語は、サブクエリで返される結果が一つでもあれば True となる。
「すべての…」
を表現してるのではなく、
「 p である x が少なくとも一つ存在する」
ということを表すために用いる述語なので、このように使用するのは不適切。
全称命題と存在命題
全称命題
ところで、「すべての x は p である」 という表現は、「論理記号」 によると、
「任意のx に対し
(＝すべてのx について・どのようなxをとっても)
P(x)である」
（ただし、P(x)はxに関するある性質・条件を表す）
は、
論理記号「 ( ∀x ) ( P(x) ) 」で表される。 …
全称命題を表す論理記号「∀」を
全称記号、全称量化子、普遍量化universal quantifierなどと呼ぶ。
存在命題
これに対して、SQL の EXISTS 述語に対応している 「論理記号」は、
「 P (x)を満たすxが（ 少なくとは一つは ）存在する」
（ただし、P(x)はxに関するある性質・条件を表す）
は、
論理記号「 ( ∃x ) ( P(x) ) 」で表される。 …
存在命題を表す論理記号「∃」を
存在記号、存在量化子existential quantifierなどと呼ぶ。
「SQL の相関サブクエリ (2) – EXISTS 述語」 で見たように、
「グループ」 に 「割当て」 られた 「人」
を抽出したい場合、以下のように記述した。
select *
from persons as p
where exists (select *
from assignments as a
where p.id = a.p_id)
求めるものを言い換えると、
「グループ」 に 「割当て」 られたことがある 「人」
「グループ」 に 「割当て」 られたことが少なくとも一度ある 「人」
繰り返すが、EXISTS 述語は一行でも結果を返せば True となる。
日常的な言葉の表現における言い換え
「すべての x は p である」 という命題は別の表現で表すことができる。
全称命題 - Wikipedia によると、
全称命題は、存在命題の否定と論理的に等値である。それゆえ、「全ての牛は空を飛ぶ」という命題を主張することは、「少なくとも一頭は空を飛べない牛がいる」という命題を否定することと等値である。
例えば、日常的な言葉の使い方で考えるなら、
「すべてのプログラマは面倒なことが嫌い」
の意味は、
「面倒なことが嫌いでないプログラマはいない」
と言うのと同じ。
もう少し言い換え、上記の引用と同じ表現にするなら、
『少なくとも一人は面倒なことが嫌いでないプログラマがいる』 を否定すること
に等しい。
これを記号を用いて表すなら、全称記号 – Wikipedia によると、
「∀xPx」は存在記号と否定記号とを用いて、「￢∃x￢Px」と表現することもできる。「￢∃x￢Px」は「P でないような x は存在しない」という意味だから、これはすなわち「すべての x は Pである」ということである。
「すべての…」 を SQL の EXISTS 述語で書く
プログラマのためのSQL 第2版
(pp.193-194) には、上記のような 「すべての…」 という表現を変換して SQL で記述する方法が述べられている。
「すべての人間は死ぬ」が、「死なない人間はいない」を包含するというのは誰もが賛成するでしょう …
… 「すべてのセールスマンは嘘つきである」 という述語を、 SQL の EXISTS 述語を使って書きたいかもしれません。これについては、今議論していた変換ルールを使います。
NOT EXISTS (SELECT *
FROM Personnel AS P1
WHERE P1.job = 'Salesman'
AND P1.name NOT IN (SELECT L1.name
FROM Liars AS L1));
これを平易にいえば、「嘘つきでないセールスマンはいない」 ということです。
この SQL を順に読んで行くと、
- 冒頭の `NOT EXISTS’ は、以降で指定するものが「存在しない」 ということを意味し、
- 何が存在しないかと言えば、とある 「人」 なんだけれど、
- その人の仕事は 「セールスマン」 であり、
- かつ、名前が、「嘘つき」の名前には含まれてない人である
という流れで書かれている。
まとめると、
- 「すべてのセールスマンは嘘つきである」 を
- 「嘘つきでないセールスマンはいない」 に言い換え、
- SQL の定義で言えば、
- いないですよ
- とある「人」で
- セールスマンであり
- かつ、嘘つきでない人
により表現する。
forall (∀) と exist (∃) の変換
C.J.Date の 「データベース実践講義」 (pp.204-205) では、forall (∀) と exist (∃) による表現を相互に変換できることが述べられている。
以下の文は、
EXISTS x ( p ( x ) )
論理的には以下の文に等しい (この場合、述語 p は x に加えてほかのパラメータを含んでいてもよい。
NOT ( FORALL x ( NOT ( p ( x ) ) ) )
つまり、「p である x が少なくとも一つ存在する」 は、「『すべての x は p ではない』ということはない」に等しい。
同様に、以下の文は
FORALL x ( p ( x ) )
論理的には以下の文に等しい (この場合も、述語 p は x に加えてほかのパラメータを含んでいてもよい。)
NOT ( EXISTS x ( NOT ( p ( x ) ) ) )
これは プログラマのためのSQL 第2版 で書かれていたこと同じ。
繰り返しになるが、「すべての x は p である」 は、「『ある x は p ではない』ということはない」 に等しい。
この説明の上で、C.J.Date はEXIST しかサポートしていない SQL に対して、次のように述べている。
… EXISTS で表わすほうが「自然な」問題と、FORALL で表わすほうが「自然な」問題があるからだ。たとえば、SQL は EXISTS をサポートするが、FORALL をサポートしない。結果として、SQL で表現しようとすると非常にやっかいなクエリが存在する。
(同上より)
この後に示されている例を参考にして、最初の問題、
すべての 「グループ」 に 「割当て」 られたことがある 「人」
を SQL で表現する。
ただし、C.J.Date が以下のように強調していることを予め心得ておくこと。
単一否定でも十分に問題なのに(多くのユーザは理解するのに苦労する)、この SQL クエリのような二重否定はもってのほかである。
( 「データベース実践講義」 、p205 より)
二重否定の SQL
さて、Date 曰く 「もってのほか」 な SQL を書いてみる。
日本語で言い換える
抽出したいのは、
すべての 「グループ」 に 「割当て」 られたことがある 「人」
これを言い換えるには、FORALL x ( P(x) ) を NOT ( EXISTS x ( NOT P(x) ) にすることを考えればよかった。
ここで P に相当するのが、
「グループ」 に 「割当て」 られたことがある
だから、全体では、
『「グループ」 に 「割当て」 られたことが少なくとも一度もない人』の否定
つまり、
『「グループ」 に 「割当て」 られたことが少なくとも一度もない』ことがない 「人」
… と書いたところで、何だかよくわからない日本語。 (@_@; これあってるのかな？
そのままで考える
もとい。日本語で考えず、そのまま考えた方が良さげ。
FORALL x ( グループに割当てられたことがある (x) )
この意味は、「すべてのグループに割当てられたことがある x」。
単純に変換のための式に当てはめると、
NOT ( EXISTS x ( NOT ( グループに割当てられたことがある (x) ) )
NOT ( EXISTS x ( グループに割当てられたことがない (x) ) )
対象は 「人」 なので、 SQL 風に書くなら、
人 WHERE FORALL x ( グループに割当てられたことがある (x) )
変換した場合、
人 WHERE NOT ( EXISTS x ( NOT ( グループに割当てられたことがある (x) ) )
人 WHERE NOT ( EXISTS x ( グループに割当てられたことがない (x) ) )
SQL で書く
次に SQL で書き直す。いきなり書くのは難しいので徐々に、上記を見ながら、
select *
from persons as p
where not exists(グループに割当てられたことがない)
次に、「グループに割当てられたことがない」 の部分を書いて完成。
select *
from persons as p
where not exists (select *
from groups as g
where not exists (select *
from assignments as a
where a.g_id = g.id and
a.p_id = p.id))
動作をイメージする
上記 SQL の動作を確かめるため、各々の人ごとに固定してサブクエリを考える。
Tarou が割当てられていないグループを取得するには、
select *
from groups as g
where not exists (select *
from assignments as a
where a.g_id = g.id and
a.p_id = 1)
Tarou に割当てられていないグループはないので、抽出されるものはない。
![111-06-2010CropperCapture[1]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_s-W9LxTPjx25lV5qxK7xF7MwtLxGC6Re9iHxoz0BP-gVlBCJPAAWZQBCjN3itFkqqx1DqJfL-X5uK7DGMAkSq3zlWd4OzaumqrGDM5rSIlWwLACgu79tBj2U3niB9tOQ=s0-d)
Hanako の場合は、
select *
from groups as g
where not exists (select *
from assignments as a
where a.g_id = g.id and
a.p_id = 2)
Take, Ume グループが抽出される。
![211-06-2010CropperCapture[2]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sNlPLzgqrRZ-FrVbbcEM8ZxCneUFTkFa-IxN445PThC5CJsQF26xrmWWzmSXnWV7qTLRbzra6KzVXKlSZ-zC08RDVyGymbmE0W1T_1izGWRHIdK6CZSAhLcUn4FmwD0zQ=s0-d)
Saburou はどのグループにも割当てられていないので、
select *
from groups as g
where not exists (select *
from assignments as a
where a.g_id = g.id and
a.p_id = 4)
全てのグループが抽出される。
![311-06-2010CropperCapture[3]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v4fqdt8nhdFecHn9nwkqb2oLp80UO28VOqkmgB62DVS9pa1ZW5rdb6qB6t-G3WVdvPYZitvb7Rpwqs6MzgdXYdJN2NrupHDIRi6qcShdHnjHKmDR2MV4siUWoP4dmbafY=s0-d)
よって、割当てられていないグループがない Tarou だけが以下の SQL によって抽出される。
select *
from persons as p
where not exists(select *
from groups as g
where not exists (select *
from assignments as a
where a.g_id = g.id and
a.p_id = p.id))
… とは言ったものの、パッと理解できないなぁ。。 (+_+)
FORALL 述語があれば…
もし、SQL に forall 述語があるなら、以下のように書けるのかな？
select *
from persons as p
where forall groups as g
exists (select *
from assignments as a
where a.g_id = g.id and
a.p_id = p.id))
ちなみに Tutorial D には exists だけでなく forall もあるので、以下のように書けるらしい。 (未確認)
persons where forall groups exists assignments
(assginments.g_id = groups.id and
assignments.p_id = persons.id)
Haskell で書く
Haskell で類似したものを書いてみる。わかりずらい二重否定を使うなら、
[p | p <- persons
, null [g | g <- groups
, null [a | a <- assignments
, a_g_id a == g_id g
, a_p_id a == p_id p]]]
( cf. gist: 645292 – GitHub )
「すべてのグループに割当てられたことがある人」 を素直に書くなら、
[p | p <- persons
, all (\g -> exists [a | a <- assignments
, a_g_id a == g_id g
, a_p_id a == p_id p])
groups]
( cf. gist: 645292 – GitHub )
![311-12-2010CropperCapture[3]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TN0gynO90aI/AAAAAAAAAuk/aKnvW5JhF0Q/311122010CropperCapture34.png?imgmax=800 "311-12-2010CropperCapture[3]")
![411-12-2010CropperCapture[4]](http://lh6.ggpht.com/_2IbZQWoiKQ0/TN0gzWIP1QI/AAAAAAAAAuo/n3UmDsQYMfw/411122010CropperCapture43.png?imgmax=800 "411-12-2010CropperCapture[4]")
![511-12-2010CropperCapture[5]](http://lh6.ggpht.com/_2IbZQWoiKQ0/TN0gz7D5v6I/AAAAAAAAAus/J4jlrJ32zns/511122010CropperCapture53.png?imgmax=800 "511-12-2010CropperCapture[5]")
![611-12-2010CropperCapture[6]](http://lh4.ggpht.com/_2IbZQWoiKQ0/TN0g0SNF6iI/AAAAAAAAAuw/wjz6jO4wQ5g/611122010CropperCapture63.png?imgmax=800 "611-12-2010CropperCapture[6]")
![811-12-2010CropperCapture[8]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TN0g0yS4VoI/AAAAAAAAAu0/FjZWVqsKmck/811122010CropperCapture83.png?imgmax=800 "811-12-2010CropperCapture[8]")
![711-12-2010CropperCapture[7]](http://lh6.ggpht.com/_2IbZQWoiKQ0/TN0g1cfHX6I/AAAAAAAAAu4/Mo-ODDXwUxM/711122010CropperCapture73.png?imgmax=800 "711-12-2010CropperCapture[7]")
![211-12-2010CropperCapture[2]](http://lh4.ggpht.com/_2IbZQWoiKQ0/TN0UYhH0UtI/AAAAAAAAAug/ARtSmj-oI-M/211122010CropperCapture24.png?imgmax=800 "211-12-2010CropperCapture[2]")
![111-11-2010CropperCapture[1]](http://lh4.ggpht.com/_2IbZQWoiKQ0/TNvo_AXIF1I/AAAAAAAAAt4/FTbR8VQUF6U/111112010CropperCapture17.png?imgmax=800 "111-11-2010CropperCapture[1]")
![211-11-2010CropperCapture[2]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TNvpAGxVzTI/AAAAAAAAAt8/eNHdAzlMYqM/211112010CropperCapture25.png?imgmax=800 "211-11-2010CropperCapture[2]")
![411-11-2010CropperCapture[4]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TNvpAuS_SXI/AAAAAAAAAuA/uKSvIRGFZBM/411112010CropperCapture45.png?imgmax=800 "411-11-2010CropperCapture[4]")
![311-11-2010CropperCapture[3]](http://lh4.ggpht.com/_2IbZQWoiKQ0/TNvpBE904LI/AAAAAAAAAuE/s-1E17Myv9M/311112010CropperCapture36.png?imgmax=800 "311-11-2010CropperCapture[3]")
![1011-11-2010CropperCapture[10]](http://lh6.ggpht.com/_2IbZQWoiKQ0/TNvpB97vaQI/AAAAAAAAAuI/zmcctnRMLxg/1011112010CropperCapture103.png?imgmax=800 "1011-11-2010CropperCapture[10]")
![1111-11-2010CropperCapture[11]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TNvpCt0rwII/AAAAAAAAAuM/0oVXGi9veFI/1111112010CropperCapture113.png?imgmax=800 "1111-11-2010CropperCapture[11]")
![911-11-2010CropperCapture[9]](http://lh6.ggpht.com/_2IbZQWoiKQ0/TNvpDAxmJsI/AAAAAAAAAuQ/QB7F5RNP4QE/911112010CropperCapture94.png?imgmax=800 "911-11-2010CropperCapture[9]")
![1211-11-2010CropperCapture[12]](http://lh6.ggpht.com/_2IbZQWoiKQ0/TNvpDkKYbCI/AAAAAAAAAuU/qeewPtIvf3c/1211112010CropperCapture123.png?imgmax=800 "1211-11-2010CropperCapture[12]")
![111-11-2010CropperCapture[1][4]](http://lh4.ggpht.com/_2IbZQWoiKQ0/TNvpEbuDYpI/AAAAAAAAAuY/uq158KhRQgw/111112010CropperCapture143.png?imgmax=800 "111-11-2010CropperCapture[1][4]")
![111-10-2010CropperCapture[1][4]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TNqXJVlhPaI/AAAAAAAAAto/UjFSu5MfTKI/111-10-2010CropperCapture%5B1%5D%5B4%5D%5B2%5D.png?imgmax=800 "111-10-2010CropperCapture[1][4]"){kind=small}
![311-10-2010CropperCapture[3]](http://lh5.ggpht.com/_2IbZQWoiKQ0/TNqXJ_cf47I/AAAAAAAAAts/mYrqUe9PeCg/311-10-2010CropperCapture%5B3%5D%5B3%5D.png?imgmax=800 "311-10-2010CropperCapture[3]")
![411-10-2010CropperCapture[4]](http://lh4.ggpht.com/_2IbZQWoiKQ0/TNqXKVTY8UI/AAAAAAAAAtw/Q-jpvFt30tU/411-10-2010CropperCapture%5B4%5D%5B3%5D.png?imgmax=800 "411-10-2010CropperCapture[4]")
![111-02-2010CropperCapture[1]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uj_To1xmYKjGisd2gV_YeUtAEFZpS8It2Ih662MEE9gN8EOn6RndWj2-vHVov2bjb9TA5gRyj56ATrX3CSRZmoP17hIImpNPwSI1MHtN7c2AuvD-iLkUYj357apP907w=s0-d)
![111-01-2010CropperCapture[1]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u7XoD6SElfkMt5haO7rRrw6DPRz7C7ZWvubbg8031y7LQYXNEeNdsEcvtxKBo_U7QHK8sYormf3DZeK_ZtP2XJi9MUJHAk9MBzqpHXq_lZmjpvLE3Gn_ITk3Ne8h2ODLo=s0-d)