全称(普遍)量化子と存在量化子

SQLに関する記事を読み漁っていて、全称(普遍)量化子と存在量化子の話：

• SQLの中の述語論理

を読んでいたときに、片方が定義されていればもう片方は論理的に導出できるというのを見て、導出しようとしたら一瞬考え込んでしまったので、ちゃんと裏を取ってみるテスト。

まず自力で導出

「∀xPx」は『すべてのxについてPxである』ということだから、逆に言うと、『Pxでないxは存在しない』ということになる。
『Pxでない』は「¬Px」。
『〜なxは存在しない』は「¬∃〜」。
だから『Pxでないxは存在しない』は「¬∃¬Px」。

文書探索

一応、調べてみる。

• 全称記号 - Wikipedia

‥まんま書いてあった。

SQLでの量化子

SQLではEXISTS述語が存在量化子にあたる。逆に、全称量化子にあたるものは定義されていない。
なぜ全称量化子が定義されていないかというと、先に示したように、存在量化子が定義されていれば導出可能だからである。(いや、本当の理由は知らないけど‥)
SQLのEXISTS述語を使って全称量化子を表すには、先のことと同様のことをやればよい。

• ろんりぃ読書会:達人に学ぶSQL徹底指南書 - 1.8

つまり、存在量化子を使ったクエリ：

SELECT *
FROM hogehoge
WHERE EXISTS ( SELECT * FROM foofoo WHERE 条件 )

に対して、全称量化子は

SELECT *
FROM hogehoge
WHERE NOT EXISTS ( SELECT * FROM foofoo WHERE NOT ( 条件 ) )

とすればよい。

シンプルな例

例えば、次のようなテーブルがあるとする。

-- ある部署のマネージャ。1部署に複数いる場合もある。
CREATE TABLE manager (
      name varchar(8) not null
    , dept varchar(8) not null
    , age int not null
    , primary key(name)
) ;
-- 作業員。マネージャの指示の元に仕事をする。
CREATE TABLE worker (
      name varchar(8) not null
    , dept varchar(8) not null
    , age int not null
    , primary key(name)
) ;

INSERT INTO worker ( name, dept, age ) VALUES ( 'W_AAA', 'dept_A', 30 ) ;
INSERT INTO worker ( name, dept, age ) VALUES ( 'W_BBB', 'dept_A', 40 ) ;
INSERT INTO worker ( name, dept, age ) VALUES ( 'W_CCC', 'dept_A', 50 ) ;
INSERT INTO worker ( name, dept, age ) VALUES ( 'W_DDD', 'dept_B', 30 ) ;
INSERT INTO worker ( name, dept, age ) VALUES ( 'W_EEE', 'dept_B', 40 ) ;
INSERT INTO worker ( name, dept, age ) VALUES ( 'W_FFF', 'dept_C', 60 ) ;
INSERT INTO worker ( name, dept, age ) VALUES ( 'W_GGG', 'dept_D', 50 ) ;

INSERT INTO manager ( name, dept, age ) VALUES ( 'M_aaa', 'dept_A', 25 ) ;
INSERT INTO manager ( name, dept, age ) VALUES ( 'M_bbb', 'dept_A', 45 ) ;
INSERT INTO manager ( name, dept, age ) VALUES ( 'M_ccc', 'dept_B', 35 ) ;
INSERT INTO manager ( name, dept, age ) VALUES ( 'M_ddd', 'dept_B', 55 ) ;
INSERT INTO manager ( name, dept, age ) VALUES ( 'M_eee', 'dept_C', 65 ) ;
INSERT INTO manager ( name, dept, age ) VALUES ( 'M_fff', 'dept_D', 45 ) ;

で、「部署(dept)は関係なく、workerより年齢が高いmanager」について考えてみる。
まず、「あるworkerより年齢が高いmanager」を得るクエリは次のような感じ。

-- 部署は関係なく、あるworkerより年齢が高いmanagerを取得
--                 (自分より年齢が若いworkerがいるmanagerを取得)
SELECT m.name, m.dept, m.age
FROM manager AS m
WHERE EXISTS (
        SELECT *
        FROM worker AS w
        WHERE
                m.age >= w.age
    )

なので、「すべてのworkerより年齢が高いmanager」を得るクエリは次のようになる。

-- 部署は関係なく、すべてのworkerより年齢が高いmanagerを取得
SELECT m.name, m.dept, m.age
FROM manager AS m
WHERE NOT EXISTS (
        SELECT *
        FROM worker AS w
        WHERE
            NOT (
                m.age >= w.age
            )
    )

それぞれの結果は次のとおり。

NAME     DEPT     AGE
-------- -------- -----------
M_bbb    dept_A            45
M_ccc    dept_B            35
M_ddd    dept_B            55
M_eee    dept_C            65
M_fff    dept_D            45

NAME     DEPT     AGE
-------- -------- -----------
M_eee    dept_C            65

不安な方は、机上デバッグをされたし。

罠のある例

先ほどと同じテーブルを使用する。
今度は、「自部署のworkerより年齢が高いmanager」について考えてみる。
まず、「自部署のあるworkerより年齢が高いmanager」を得るクエリは次のような感じ。

-- 自部署のあるworkerより年齢が高いmanagerを取得
-- (自部署に自分より年齢が若いworkerがいるmanagerを取得)
SELECT m.name, m.dept, m.age
FROM manager AS m
WHERE EXISTS (
        SELECT *
        FROM worker AS w
        WHERE
                m.dept = w.dept
            AND
                m.age >= w.age
    )

こちらは問題ないと思う。部署ごとにworkerとmanagerをグループ分けして、その中で年齢の大小を比較するため、サブクエリの条件が一つ増えている(m.dept = w.dept)。
では、「自部署のすべてのworkerより年齢が高いmanager」を得るクエリはどうなるだろうか。
まずは、机上でその答えを求めてみる。

• 'dept_A'では、最年長のworkerが50歳だが、'dept_A'には51歳以上のmanagerはいない。
• 'dept_B'では、最年長のworkerが40歳で、'dept_B'には55歳のmanagerである'M_ddd'がいる。
• 'dept_C'では、最年長のworkerが60歳で、'dept_C'には65歳のmanagerである'M_eee'がいる。
• 'dept_D'では、最年長のworkerが50歳だが、'dept_D'には51歳以上のmanagerはいない。

したがって、求めるものは「M_ddd」と「M_eee」の2人である。
さて、先の規則にしたがって単純にクエリを書き換えてみる。

-- 自部署のすべてのworkerより年齢が高いmanagerを取得
-- (間違い)
SELECT m.name, m.dept, m.age
FROM manager AS m
WHERE NOT EXISTS (
        SELECT *
        FROM worker AS w
        WHERE
          NOT (
                m.dept = w.dept
            AND
                m.age >= w.age
          )
    )

さて、これを実行してみると‥

NAME     DEPT     AGE
-------- -------- -----------

机上での計算と実際の結果が異なる。
なぜこういうことになってしまったかというと、問題はサブクエリのWHERE句すべてを"NOT"でくくってしまったことにある。
ここで、WHERE句にある2つの条件を見てみる。
まず、「m.age >= w.age」は先の単純な例でもそうであったように、論理式で書くところの『Px』に相当する条件である。
一方「m.dept = w.dept」はどうかというと、これは『Px』には含まれない。それではこの条件は何かというと、『x』の範囲を定めるための条件である。つまり、あるmanagerの年齢と比較するworkerを、この条件によって「自部署の」workerに限定している。
または、「条件「m.dept = w.dept」は『x』に含まれている」と考えてもよいかもしれない。つまり、「『x』=『自部署内のworker』」という具合である。
それを念頭に置くと、条件「m.dept = w.dept」は"NOT"の外に置かなければならないことが分かる。
正しいクエリは次のとおり。

-- 自部署のすべてのworkerより年齢が高いmanagerを取得
-- (正解)
SELECT m.name, m.dept, m.age
FROM manager AS m
WHERE NOT EXISTS (
        SELECT *
        FROM worker AS w
        WHERE
                m.dept = w.dept
            AND
            NOT (
                m.age >= w.age
            )
    )

これを実行した結果は、次のとおりとなる。

NAME     DEPT     AGE
-------- -------- -----------
M_ddd    dept_B            55
M_eee    dept_C            65

今度は期待通り。