SQL の相関サブクエリ (5) – forall (∀) の exists (∃) への読み替え

「SQL の相関サブクエリ (4) - SELECT 句で使う」のつづき

今回も前回と同じデータベースを使う。構造は以下の通り。

ここから、

すべての 「グループ」に「割当て」られたことがある「人」

を抽出したい。

データベースの内容をオブジェクト図で示すと、一見して目的の人がわかる。

Tarou だけが 3 つのグループすべてに「割当て」られた。 Jirou, Saburou は割当てがされてるものの 1 グループに対してのみ。

では、これを SQL で書くにはどうしたらいいのか？

これまでと同じように、特定の条件に一致する「人」を抽出したいので、

select *
from persons
where exists (select *
              from ...

と書き始めてみたものの、

「すべての x は p である」

という形式をどのように表現するのだろう？

exists 述語は、サブクエリで返される結果が一つでもあれば True となる。

「すべての…」

を表現してるのではなく、

「 p である x が少なくとも一つ存在する」

ということを表すために用いる述語なので、このように使用するのは不適切。

全称命題と存在命題

全称命題

http://ja.wikipedia.org/wiki/%E5%85%A8%E7%A7%B0%E8%A8%98%E5%8F%B7

全称記号
- Wikipedia
via kwout

ところで、「すべての x は p である」という表現は、「論理記号」によると、

「任意のx に対し
(＝すべてのx について・どのようなxをとっても)
P(x)である」
（ただし、P(x)はxに関するある性質・条件を表す）
は、
論理記号「 ( ∀x ) ( P(x) ) 」で表される。 …

全称命題を表す論理記号「∀」を
全称記号、全称量化子、普遍量化universal quantifierなどと呼ぶ。

存在命題

http://ja.wikipedia.org/wiki/%E5%AD%98%E5%9C%A8%E8%A8%98%E5%8F%B7

存在記号 >
- Wikipedia
via kwout

これに対して、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 に割当てられていないグループはないので、抽出されるものはない。

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 グループが抽出される。

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)

全てのグループが抽出される。

よって、割当てられていないグループがない 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 )

すぐに忘れる脳みそのためのメモ

2010年11月6日土曜日