作りたいものがありすぎる

40歳を過ぎてプログラミングを始めた人の顛末とこれからなど

【輪読会資料】達人に学ぶSQL徹底指南書 第2版  9, SQLで集合演算

以下の記事は2018/12/26 コワーキングスペース秋葉原Weeybleで行われる輪読会
[秋葉原] 達人に学ぶSQL徹底指南書 輪読会 第1部 魔法のSQL (集合演算/数列) の資料となります。
以下の書籍の 第一部 9 SQLで集合演算の要約です。

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)



9 SQLで集合演算

見出し一覧

  • SQL集合論
  • はじめに
  • 導入---集合演算に関するいくつかの注意点
  • テーブル同士のコンベア---集合の相等性チェック[基本編]
    • [Extra おさらい] UNION の簡単な使用例
  • テーブル同士のコンベア---集合の相等性チェック[応用編]
  • 差集合で関係除算を表現する
  • 等しい部分集合を見つける
  • 重複行を削除する高速なクエリ
  • まとめ
  • 演習問題

1版の記事、及びサンプルコードは以下リンク先よりDL可能
達人に学ぶSQL SQLで集合演算 集合指向言語としてのSQL:その4

サンプルコード
2版用に独自アレンジしたもの
Dropbox - 9_SQLで集合演算_サンプルコード.txt

SQLを手軽にシミュレートするにはこちらのサイト

sqlfiddle(但しdelete系は使用不可、またちょいちょい調子悪くなる)
http://sqlfiddle.com/

ORACLE Live SQL(アカウント登録が必要)
Oracle Live SQL



SQL集合論

近年までSQLは集合演算の整備をしていなかった為、その機能は十分活用されてこなかった。
が、最近になって機能が出揃ってきた。
ここは集合演算の背景にある考え方を理解する章となる。

[Extra] そもそも集合論とは?

高校位の数学でやった筈なので、おおよそのエンジニアさんには釈迦に説法かもですが、俺が再認識したいので以下にまとめます。

部分集合 included, subset

f:id:sakamata:20181224151819p:plain:w300
『 A は B の部分集合である 』といい

A ⊆ B
と表現される

また、日本の高等数学では
A ⊂ B
を使用する

俺要約 要は 不等号の ≦ でのイメージをそのまま転写して『含む』で思考すれば良い

A は B に包まれる(included; 包摂あるいは内包される)などともいう



和集合 union

和 合併集合 合併(union)  などともいう
f:id:sakamata:20181224151854p:plain:w300
『すくなくとも片方に入っているもの』を集めた集合

A ∪ B

と表現される 俺要約 要は OR関数(または)で定義する範囲の結果を示す 記号の覚え方は 広く囲む掌をイメージ



積集合 intersection

『両方ともにはいっているもの』を集めた集合
共通部分 ともいう
f:id:sakamata:20181224151906p:plain:w300
A ∩ B

と表現される 俺要約 要は AND関数(かつ)で定義する範囲の結果を示す 記号の覚え方は 『蓋をした範囲のみ』でイメージ




はじめに

SQLは「集合指向言語」と呼ばれている、本書のテーマも集合論に基づいたSQLにある。しかし、SQLはちょっと前まで高校で習うレベルの集合演算子すら持っていなかった。
それゆえSQLは不完全なものという批判があった。

集合 SQL 採用Ver 記号
UNION 86~ A ∪ B
交差 INTERSECT 92~ A ∩ B
EXCEPT 92~ A - B
除算 DIVIDE BY 未対応 A / B ?

しかし、現在ではSQLに基本的な集合演算子が出揃い、本格的な応用も可能となってきた。
この章では、集合演算を利用したSQLを紹介し、違った角度からSQLの本質に迫る。



導入---集合演算に関するいくつかの注意点

要は SQLの tableやview を引数に取って演算をする。中学・高校で習った集合台数と似ているが、独特な特徴もあり注意が必要。


注意1

SQLの扱う集合は重複行を許す多重集合。それに対応するALLオプションが存在する。

通常の学習における『集合論』は重複を認めないが、SQLは認める前提 多重集合(multiser, bag)である。
UNION, INTERSECT をそのまま使うと結果から重複行を排除する。
重複行を残したい際は ALL オプションを使う事(例: UNION ALL )
SELECT句のDISTINCTと反対の扱いだが これは間違い→ UNION DISTINCT

ALL オプションを付けるとパフォーマンスが向上する (ソートが行われない為)
付けないと重複を許容し、暗黙的なソートが発生するので重くなるらしい。
なのでパフォーマンスチューニングでじゃ ALLオプションを付けると良い


注意2

演算の順番に優先順位がある

UNION,EXCEPT に対して INTERSECT の方が先に実行される。
もしUNIONを優先的に実行したい場合は (カッコ) でくくって順序を指定する事(後で詳細あり)


注意3

DBMSごとに集合演算子の実装にバラツキがある MySQLは2018年現在 INTERSECT,EXCEPT サポートしてない。
Oracle は EXCEPT が MINUS という名になっている


注意4

除算の標準的な定義がない

  • 和 UNION
  • 差 EXCEPT
  • 積 CROSS JOIN

はあるが、

  • 商 DIVIDE BY
    は、標準化が遅れている。
    (詳しくはP105 HAVING句の力 を参照の事)
    除算を行う際は自前でクエリを作る必要がある等



テーブル同士のコンベア---集合の相等性チェック[基本編]

さて、では実践編
下記の2つのtableの中身が全て等しいか検証するには?

tbl_a
+------+-------+-------+-------+
| key  | col_1 | col_2 | col_3 |
+------+-------+-------+-------+
| A    |     2 |     3 |     4 |
| B    |     0 |     7 |     9 |
| C    |     5 |     1 |     6 |
+------+-------+-------+-------+

tbl_b
+------+-------+-------+-------+
| key  | col_1 | col_2 | col_3 |
+------+-------+-------+-------+
| A    |     2 |     3 |     4 |
| B    |     0 |     7 |     9 |
| C    |     5 |     1 |     6 |
+------+-------+-------+-------+

--等しいテーブル同士のケース

DELETE FROM Tbl_A;
INSERT INTO Tbl_A VALUES('A', 2, 3, 4);
INSERT INTO Tbl_A VALUES('B', 0, 7, 9);
INSERT INTO Tbl_A VALUES('C', 5, 1, 6);

DELETE FROM Tbl_B;
INSERT INTO Tbl_B VALUES('A', 2, 3, 4);
INSERT INTO Tbl_B VALUES('B', 0, 7, 9);
INSERT INTO Tbl_B VALUES('C', 5, 1, 6);


[Extra おさらい] UNION の簡単な使用例

    SELECT * FROM tbl_a
UNION
    SELECT * FROM tbl_b;


    SELECT * FROM tbl_a
UNION ALL
    SELECT * FROM tbl_b;

UNIONだけを使う方法

2つのtableが完全同一か確認したい。しかしレコード数が多い場合は以下のクエリが便利

SELECT COUNT(*) AS row_cnt
  FROM ( SELECT * 
           FROM   Tbl_A 
         UNION
         SELECT * 
           FROM   Tbl_B ) TMP;

SQL文末のTMP は仮で定義するtable名みたいなもの。 適当にhogeでもOK
このクエリの結果が tbl_a と tbl_b の行数と一致すれば、両者は等しいテーブル

SELECT count("key") from  tbl_a;  => 3
SELECT count("key") from  tbl_b;  => 3

--「B」の行が相違するケース

DELETE FROM Tbl_A;
INSERT INTO Tbl_A VALUES('A', 2, 3, 4);
INSERT INTO Tbl_A VALUES('B', 0, 7, 9);
INSERT INTO Tbl_A VALUES('C', 5, 1, 6);

DELETE FROM Tbl_B;
INSERT INTO Tbl_B VALUES('A', 2, 3, 4);
INSERT INTO Tbl_B VALUES('B', 0, 7, 8);
INSERT INTO Tbl_B VALUES('C', 5, 1, 6);

再度 UNION のクエリを実行すると結果は 4 となり、2つのtableが異なる事がわかる。 例は * による全カラム対象だが、特定のカラムや where で特定の行範囲での比較も可能。

再度コレ

SELECT COUNT(*) AS row_cnt
  FROM ( SELECT * 
           FROM   Tbl_A 
         UNION
         SELECT * 
           FROM   Tbl_B ) TMP;

このクエリ文は以下の様な構造として読み取れる

Tbl_A UNION Tbl_B = TMP   
↓   
S UNION S = S   

これは数学でいう冪等性(べきとうせい idenpotency)と呼ばれる性質のもの
プログラムでは「繰り返し処理をしても最初の一度に実行したものと結果が同じになる」という事柄のニュアンスで使われる。

  • C言語 ファイルインクルードを何度しても結果が変わらない特質設計
  • HTTPのGETコマンド 同じ要求を繰り返し発行しても大丈夫な様になっている。
  • UIのボタンを連打しても1回として認識する

これらは冪等と言える
また、この式は2つだけの比較ではなく 3個以上の値でも比較可能。

S UNION S UNION S UNION ... UNION S = S

しかし、 UNION ALL テメーは駄目だ。
重複したら冪等性が失われる。したがって冪等性を確保するためにも ユニークキーは大事だね。 という事らしい。


おさらい 積集合 intersection

『両方ともにはいっているもの』を集めた集合
共通部分 ともいう
f:id:sakamata:20181224151906p:plain:w300

A ∩ B



テーブル同士のコンベア---集合の相等性チェック[応用編]

集合の相等性を調べる公式
1. (A ⊆ B) かつ (A ⊇ B) ⇔ (A = B) 2. (A ∪ B) = (A ∩ B) ⇔ (A = B)

(ド・モルガンの法則に近い理屈)

ここでは2番を使う 2番をSQLに訳すると

A UNION B  =  A INTERSECT B  なら AとBは等しい となる。

そして

A UNION B =  A=B       ならば
A INTERSECT B =  A=B   が成り立つ

二つのテーブルが相等なら「等しい」、そうでなければ「異なる」を返すクエリ

SELECT CASE WHEN COUNT(*) = 0 
                     THEN '等しい'
                     ELSE '異なる' END AS result
  FROM ((SELECT * FROM  Tbl_A
         UNION
         SELECT * FROM  Tbl_B) 
         MINUS  --  EXCEPT は oracle  では MINUS
        (SELECT * FROM  Tbl_A
         INTERSECT 
         SELECT * FROM  Tbl_B)) TMP;

相違した行を表示する。(oracleでerrorとなって確認できず)

  --テーブルに対するdiff:排他的和集合を求める。 
  (SELECT * FROM  Tbl_A
     MINUS -- EXCEPT
   SELECT * FROM  Tbl_B)
   UNION ALL
  (SELECT * FROM  Tbl_B
     MINUS -- EXCEPT
   SELECT * FROM  Tbl_A);



差集合で関係除算を表現する

現在のSQLには除算の演算子が無い為以下の方法などで自前でクエリを書く必要がある。

  1. NOT EXSIST を入れ子にする
  2. HAVING句を使った一対一対応を利用する
  3. 割り算を引き算で表現する

ここでは3番の方法を紹介

以下の様なtableがあるとする。

select * from Skills;
+--------+
| skill  |
+--------+
| Java   |
| Oracle |
| UNIX   |
+--------+

select * from EmpSkills;
+-----------+--------+
| emp       | skill  |
+-----------+--------+
| 平井      | C++    |
| 平井      | Oracle |
| 平井      | PHP    |
| 平井      | Perl   |
| 平井      | UNIX   |
| 渡来      | Oracle |
| 相田      | C#     |
| 相田      | Java   |
| 相田      | Oracle |
| 相田      | UNIX   |
| 神崎      | Java   |
| 神崎      | Oracle |
| 神崎      | UNIX   |
| 若田部    | Perl   |
+-----------+--------+

ここからSkills Tableにある全ての技術(Java,Oracle, UNIX)に
精通した社員を探すクエリはどう書けば良いか?

以下が答え しかし、注意!
MySQLは2018年現在 INTERSECT,EXCEPT サポートしてない。
Oracle は EXCEPT が MINUS という名になっている
Oracle LiveSQLで実践)

--差集合で関係除算(剰余を持った除算)
SELECT DISTINCT emp  -- empの重複をまとめる
  FROM EmpSkills ES1
 WHERE NOT EXISTS       -- サブクエリ結果の否定のものを該当させる
        (SELECT skill
           FROM Skills
         EXCEPT        -- 差集合 引き算をさせる
         SELECT skill
           FROM EmpSkills ES2
          WHERE ES1.emp = ES2.emp);

--oracleの場合は EXCEPT が MINUS となる
SELECT DISTINCT emp
  FROM EmpSkills ES1
 WHERE NOT EXISTS
        (SELECT skill
           FROM Skills
         MINUS          -- oracle の場合の差集合
         SELECT skill
           FROM EmpSkills ES2
          WHERE ES1.emp = ES2.emp);


解説

サブクエリ内(カッコ内)でしている事
平井さんの場合

| skill  |
+--------+
| Java   |
| Oracle |
| UNIX   |

引くことの(EXCEPT,MINUS)   
| 平井      | C++    | 無関係
| 平井      | Oracle | 消える
| 平井      | PHP    | 無関係
| 平井      | Perl   | 無関係
| 平井      | UNIX   | 消える

= Java が残る

相田さんの場合

| skill  |
+--------+
| Java   |
| Oracle |
| UNIX   |

引くことの(EXCEPT,MINUS)
| 相田      | C#     | 無関係
| 相田      | Java   | 消える
| 相田      | Oracle | 消える
| 相田      | UNIX   | 消える

= 空集合 Φ つまりここでは該当しない

このサブクエリの結果の NOT EXISTS つまり否定なので、空集合となった結果を表示させる。
すなわち、全てのスキルを持つ社員のみ表示。となる。

EMP
相田
神崎



等しい部分集合を見つける

以下のtableから数も種類も全て同じ部品を扱う供給業者のペアを求めるにはどうしたた良いか?
一応答えは AとC, BとD となっている

+-----+--------------+
| sup | part         |
+-----+--------------+
| A   | ナット       |
| A   | パイプ       |
| A   | ボルト       |
| B   | パイプ       |
| B   | ボルト       |
| C   | ナット       |
| C   | パイプ       |
| C   | ボルト       |
| D   | パイプ       |
| D   | ボルト       |
| E   | ナット       |
| E   | パイプ       |
| E   | ヒューズ     |
| F   | ヒューズ     |
+-----+--------------+

実は結構難しいパズル、理由はSQLには∅の包含関係や相当性をテストする記述がない為、集合と集合を一発で比較出来る書き方は出来ないので、ひねって答えを求める必要がある。 IN は要素として含まれるかを探す( ∈ )に相当する。 集合と集合に使うべき状態 ( ⊂ )足り得ない。
つまり、最初の比較対象である『まず定義すべき集合』が無い状態で、なんとかして、同一のものを探さないといけない訳。

ではどうするか?
まずは非等値結合で sup の組み合わせの総当たり表を作る。

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  |
| A  | E  |
| B  | C  |
| B  | D  |
| B  | E  |
| C  | D  |
| C  | E  |
| D  | E  |
| E  | F  |
+----+----+

次にこのペアについて
(A ⊆ B) かつ (A ⊇ B) ⇔ (A = B) の公式を当てはめる

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) -- s1カラムで数が同じものを探す
   AND COUNT(*) = (SELECT COUNT(*) 
                     FROM SupParts SP4 
                    WHERE SP4.sup = SP2.sup); -- かつ s2カラムで数が同じものを探す

うーん、かなりややこしい…。
筆者もパズルと言っているので、無理に理解しなくともよいかと
上記クエリの結果

+----+----+
| s1 | s2 |
+----+----+
| A  | C  |
| B  | D  |
+----+----+

しかし、もし将来的に集合の除算が可能になったら以下のようなクエリで書けるかもしれないらしい。

SELECT 'A CONTAINS B'
  FROM SupParts
WHERE ( SELECT part
          FROM SupParts
        WHERE sup = 'A')
    CONTAINS   -- こんなのあったらいいな、ということらしい
      ( SELECT part
          FROM SupParts
        WHERE sup = 'B')

業者Bび扱う部品全てを業者Aが扱っていれば 'A CONTAINS B' と表示させる。
というクエリがあったらなー。みたいな話



重複行を削除する高速なクエリ

再度、3 自己結合の使い方[P49 重複行を削除する] で使った tableで重複行を削除する問題を扱う。

Products table
+-----------+-------+
| name      | price |
+-----------+-------+
| りんご    |    50 |
| みかん    |   100 |
| みかん    |   100 |
| みかん    |   100 |
| バナナ    |    80 |
+-----------+-------+

3 自己結合の使い方 に出ていたクエリを再度確認
※ rowid はMySQL使えないので注意

--重複行を削除するSQL :相関サブクエリの利用
DELETE FROM Products
 WHERE rowid < ( SELECT MAX(P2.rowid)
                   FROM Products P2
                  WHERE Products.name = P2.name
                    AND Products.price = P2.price ) ;

上記はパフォーマンスに問題あり、相関サブクエリを使わない方法を求める。
今度は削除対象となるrowidをサブクエリ内で全部求めてしまう。

--高速版1:削除すべき行のrowidを求めて、その行を削除
DELETE FROM Products 
 WHERE rowid IN ( SELECT rowid                 -- 全体のrowid
                    FROM Products 
                   EXCEPT -- oracleなら MINUS   引く
                  SELECT MAX(rowid)            -- 残すべきrowid
                    FROM Products 
                   GROUP BY name, price);      -- グループ複数定義で一意性を求める
table 全体
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |

引くことの
残すべきID
| 1 |
| 4 |
| 5 |

残った削除対象のID
| 2 |
| 3 |
--高速版2:残すべき行のrowidを求めて、それ以外の行を削除
DELETE FROM Products 
 WHERE rowid NOT IN ( SELECT MAX(rowid)
                        FROM Products 
                       GROUP BY name, price);



まとめ

  1. SQLでは集合演算機能の整備が遅れている、使える内容もDBによって異なるので注意が必要
  2. 集合演算子はALLオプションを付けないと重複排除を行う。その際、ソートも行われるので、パフォーマンスが悪くなる。
  3. UNION,INTERSECTは、冪等性を持つ、 EXCEPTは持たない
  4. 除算は標準的な演算子が無いので自前で作る必要がある。
  5. 集合の相等性を調べるには、冪等性か全単射を利用する2通りがある
  6. EXCEPTを使うと、補集合を簡単に表現できる



演習問題

省略