等しい部分集合を見つける
この問題は、1993年にデイトが提出して以来、非常に有名になったパズルです。サンプルには、彼が定番として使う供給業者-部品の関連を表すテーブルを使いましょう。
求めるのは、数も種類もまったく同じ部品を取り扱う供給業者のペアです。この例だと、A-CとB-Dの組み合わせです。AとEは扱う部品数は同じ3なのですが、部品の種類が異なるので対象外、Fは、数も種類も他のどの業者とも一致しないので論外です。
一見すると簡単そうなこの問題がなぜパズルになるかと言うと、SQLには集合の包含関係や相等性をテストするための述語が一切存在しないからです。INは、あくまで要素として含まれるかどうかを記述する述語（∈）であって部分集合の述語（⊆）ではありません。かつて、IBMが作ったリレーショナル・データベースの試作機第一号「System R」には、CONTAINSという集合の包含関係を記述する述語があったそうです。しかし、これは後にパフォーマンス上の理由から削除され、その後現在にいたるまで復活を見ていない「幻の述語」です。
この問題は、集合同士の比較を行うという点で、前問の関係除算と構造がよく似ています。ただし、除算においては比較対象の一方の集合は固定されていたのに対し（先の例だと「Skills」テーブルがそうです）、今度は、どちらの集合も固定せずに、部分集合同士の組み合わせ全部についてテストするため、より一般性の高い問題になっています。
まずは、業者の組み合わせを作りましょう。これは、おなじみの非等値結合で作れます。集約しているのは、単に重複を解消するためです。
SELECT SP1.sup AS s1, SP2.sup AS s2 FROM SupParts SP1, SupParts SP2 WHERE SP1.sup < SP2.sup GROUP BY SP1.sup, SP2.sup;
s1 s2 ---- ----- A B A C A D ： ： ： D E E F
次に、この業者ペアについて、(A ⊆ B ) かつ (A ⊇ B) ⇒ (A = B)の公式を当てはめます。この公式は、次の2つの条件と同値です。
- 条件1．どちらの業者も同じ種類の部品を扱っている
- 条件2．同数の部品を扱っている（すなわち全単射が存在する）
条件1は、素直に部品列で結合するだけですし、条件2はCOUNT関数によって記述できます。
SELECT SP1.sup AS s1, SP2.sup AS s2 FROM SupParts SP1, SupParts SP2 WHERE SP1.sup < SP2.sup --業者の組み合わせを作る AND SP1.part = SP2.part --条件1．同じ種類の部品を扱う GROUP BY SP1.sup, SP2.sup HAVING COUNT(*) = (SELECT COUNT(*) --条件2．同数の部品を扱う FROM SupParts SP3 WHERE SP3.sup = SP1.sup) AND COUNT(*) = (SELECT COUNT(*) FROM SupParts SP4 WHERE SP4.sup = SP2.sup);
s1 s2 ---- ---- A C B D
HAVING句の二つの条件は、厳密な関係除算と同じだと考えれば分かりやすいでしょう。これによって、集合AとBの要素が過不足なく一致する（＝全単射が存在する）ことを保証しています。そして、個数が一致するだけでなく、その種類もすべての部品について一致することを、条件1が保証しています。
このパズルは、さまざまな解法が考案されていますが、この「除算の一般化」は、集合指向という特性を利用した見事なものです。SQLでは、2つの集合を比較するときは、行単位で比較するのではなく、あくまで集合を全体として扱うというポイントをよく示しています。
重複行を削除する高速なクエリ
集合演算の応用方法として、最後に重複行の削除を取り上げましょう。これは、以前「自己結合の使い方」でも取り上げた問題です。再度、主キーなしの恐怖のテーブルにご登場願いましょう。
以前紹介した解法は、相関サブクエリを使うシンプルなものでした。
DELETE FROM Products WHERE rowid < ( SELECT MAX(P2.rowid) FROM Products P2 WHERE Products.name = P2. name AND Products.price = P2.price ) ;
これも悪くはないのですが、相関サブクエリはパフォーマンスに難点があります（ただでさえDELETEは時間のかかる処理です）。そこで、相関サブクエリを使わずに同じ処理を実現する方法を考えます。
上のクエリの考え方としては、{ 名前, 値段 }の組み合わせでまとめたときに、最大のrowidを求めて、反対にそれ以外の行を削除する、というものでした。削除対象の行を直接求めるのは難しいので、もっと簡単に求められる、残す行を先に求めて、それを全体から引く――いわゆる補集合の考え方です。相関サブクエリのバージョンでは、{ 名前, 値段 }の組み合わせごとにその処理を行っていました（=コントロール・ブレイク）。今度は、削除対象となるrowidを、サブクエリ内で全部求めきってしまいます。
いま、rowid列が次のように与えられているとします。
極値関数を使って残したいrowidを1つだけ取得する、という点は同じです。ポイントは、その集合を「Products」テーブル全体から引き算することです。次のクエリが答えになります。
DELETE FROM Products WHERE rowid IN ( SELECT rowid --全体のrowid FROM Products EXCEPT --引く SELECT MAX(rowid) --残すべきrowid FROM Products GROUP BY name, price) ;
非相関になったサブクエリは、定数のリスト（2, 3）を返します。EXCEPTで補集合を求める部分は、図で表せば次のようなイメージです。
EXCEPTを使うと、補集合を利用した解法が簡単に実現できることがお分かりいただけるでしょう。ちなみに、EXCEPTを NOT INで代用した次のようなコードも考えられます。
DELETE FROM Products WHERE rowid NOT IN ( SELECT MAX(rowid) FROM Products GROUP BY name, price);
どちらのがパフォーマンスが良いかは、テーブルの規模や、削除する行と残す行の比率によって変わるでしょう。ただ、後者の方がEXCEPTを持っていない実装でも使えるというメリットはあります。
なお、このようなレコードIDが使用できる実装は、OracleとPostgreSQLだけです。PostgreSQLの場合は、「oid」という列名になります。その場合、事前にCREATE TABLE文に「WITH OIDS」オプションを付けることを忘れないでください。他の実装でこのクエリを利用するときは、テーブル単位で一意な列を明示的に作成する必要があります。
おわりに
今回は、集合演算の使い方を紹介しました。序文でも述べましたが、このあたりは整備が遅れていたせいで、豊かな応用がたくさんあるにも拘わらず、まだあまり知られていません。皆さんもぜひ、面白いSQLを考えてみてください。
それでは、今回の要点です。
- SQLでは集合演算機能の整備が遅れていた。今でもDBによって実装状況にバラツキがあるので、利用するときは要注意。
- 集合演算子は、ALLオプションをつけないと重複排除を行う。その際、ソートも行われるのでパフォーマンス面ではマイナス。
UNIONとINTERSECTは、冪等性という重要な性質を持つ。EXCEPTは持たない。- 除算は標準的な演算子がないので、自前で作ること。
- 集合の相等性を調べる方法には、冪等性か全単射を利用する2通りがある。
EXCEPTを使うと、補集合を簡単に表現できる。
参考資料
- 『プログラマのためのSQL 第2版』 Joe Celko 著、ピアソンエデュケーション、2001年4月
IS NULLで行っていますが、これは多くの実装ではサブクエリが複数の値を返す場合にエラーになるでしょう。標準SQLではIS NULLが値のリストを引数に取ることができるので、間違いではないのですが、まだ一般的には実装されていない機能です。- 『SQLパズル 第2版』 Joe Celko 著、ミック 訳、翔泳社、2007年11月
- 『Relational Database Writings 1991-1994』 C. J. Date 著、Addison-Wesley Pub、1995年
UNIONとINTERSECTが冪等性を持つことの重要性について示唆を受けました。また、等しい集合を発見するパズルの初出は、「A Matter of Integrity (Part 2 of 3)」。
