初めに
この問題は、SQLパズル #9
『席空いてますか』を解説します
手元に『SQL パズル』があればわかりやすいです
やりたい事は
並んでいる数字の中から
歯抜けの番号を探す・・です
とあるレストランには20席程？の
席があるとします
1,2,3,8,9,10,16,18,19番には
お客さんが座っています
空白の席をSQLで取出してみます
PostgreSQLで動作確認してます
【手法１】
① 空白席の開始位置を探す
② 空白席の終了位置を探す
③ 空白席の組合せを作る
④ 連続する空白席を取出す
Restaurant Table & Data
CREATE TABLE Restaurant(
seat integer -- 着席してる席番号
);
INSERT INTO Restaurant VALUES(1);
INSERT INTO Restaurant VALUES(2);
INSERT INTO Restaurant VALUES(3);
INSERT INTO Restaurant VALUES(8);
INSERT INTO Restaurant VALUES(9);
INSERT INTO Restaurant VALUES(10);
INSERT INTO Restaurant VALUES(16);
INSERT INTO Restaurant VALUES(18);
INSERT INTO Restaurant VALUES(19);
空席の番号を見つける[開始]
-- 開始番号
WITH Firstseat AS (
SELECT (seat + 1) AS seat -- 1つ先
FROM Restaurant
WHERE (seat + 1) NOT IN (SELECT seat FROM Restaurant)
AND (seat + 1) < 1001
)
SELECT * FROM Firstseat
-- 出力
-- 4
-- 11
-- 17
-- 20
▼ 埋まっている数字の次が空白の数字(seat+1)を探す
[開始] 空白席の条件
埋まっている数字(seat)の１つ先の数字
⇒ seat + 1 とする
⇒ ↑ ココが空白である条件
⇒ {1,2,3,8,9,10,18,19} 含まない
⇒ {4,11,17,20} が残る
空席の番号を見つける[終了]
-- 終了番号
WITH Lastseat AS (
SELECT (seat - 1) AS seat -- 1つ前
FROM Restaurant
WHERE (seat - 1) NOT IN (SELECT seat FROM Restaurant)
AND (seat - 1) > 0 -- 0 より小さい数字はあり得ない
)
SELECT * FROM Lastseat
-- 出力
-- 7
-- 15
-- 17
▼ 埋まっている数字の前が空白の数字(seat-1)を探す
[終了] 空白席の条件
埋まっている数字(seat)の１つ前の数字
⇒ seat - 1 とする
⇒ ↑ ココが空白である条件
⇒ {1,2,3,8,9,10,18,19} 含まない
⇒ {7,15,17} が残る
空席部分を可視化
空白席の開始と終了の部分を青く色づけしてます
複数の開始位置と終了位置が存在するので
ここを取出す必要があります
開始・終了の場所を取る・・準備
-- 空席の開始番号
WITH Firstseat AS (
SELECT (seat + 1) AS seat FROM Restaurant
WHERE (seat + 1) NOT IN (SELECT seat FROM Restaurant)
AND (seat + 1) < 1001
),
-- 空席の終了番号
Lastseat AS (
SELECT (seat - 1) AS seat FROM Restaurant
WHERE (seat - 1) NOT IN (SELECT seat FROM Restaurant)
AND (seat - 1) > 0
)
SELECT
F1.seat AS start -- 開始
,L1.seat AS finish -- 終了
,(SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2) -- 終了一覧
,(SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.seat)
,(SELECT MIN(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.seat)
FROM Firstseat AS F1, Lastseat AS L1
ORDER BY finish
▼ 出力
| 開始 | 終了 | 終了一覧 | 終了一覧 | MIN |
|---|---|---|---|---|
| 4 | 7 | {7,15,17} | {7,15,17} | 7 |
| 4 | 15 | {7,15,17} | {7,15,17} | 7 |
| 4 | 17 | {7,15,17} | {7,15,17} | 7 |
| 11 | 7 | {7,15,17} | {15,17} | 15 |
| 11 | 15 | {7,15,17} | {15,17} | 15 |
| 11 | 17 | {7,15,17} | {15,17} | 15 |
| 17 | 7 | {7,15,17} | {17} | 17 |
| 17 | 15 | {7,15,17} | {17} | 17 |
| 17 | 17 | {7,15,17} | {17} | 17 |
| 20 | 7 | {7,15,17} | NULL | NULL |
| 20 | 15 | {7,15,17} | NULL | NULL |
| 20 | 17 | {7,15,17} | NULL | NULL |
SELECTの中身
SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2
⇒ 『空白の終了番号』をリスト化
⇒ {7,15,17}
⇒ この３つは共通
SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.sea
⇒ この中で、開始より終了が後となる条件を追加
⇒ [開始=４]
４より大きい終了は {7,15,17}
⇒ [開始=11]
１１より大きい終了は {15,17}
⇒ 後も同じ・・・
SELECT MIN(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.seat
⇒ この中で、最小の数字を取る
⇒ [開始=４]
{7,15,17}の最小は 7
⇒ [開始=11]
{15,17}の最小は 15
⇒ 後も同じ・・・
この数字(空白終了番号)を次に利用します
この数字を探す所がこのクイズの重要な所です・・といいますか
面白い所です
回答SQL その１
-- 空席の開始番号
WITH Firstseat AS (
SELECT (seat + 1) AS seat FROM Restaurant
WHERE (seat + 1) NOT IN (SELECT seat FROM Restaurant)
AND (seat + 1) < 1001
),
-- 空席の終了番号
Lastseat AS (
SELECT (seat - 1) AS seat FROM Restaurant
WHERE (seat - 1) NOT IN (SELECT seat FROM Restaurant)
AND (seat - 1) > 0
)
SELECT
F1.seat AS start
, L1.seat AS finish
FROM Firstseat AS F1, Lastseat AS L1
WHERE L1.seat = (SELECT MIN(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.seat)
▼ 出力
| start | finish |
|---|---|
| 4 | 7 |
| 11 | 15 |
| 17 | 17 |
最初に・・
空白席の『開始＆終了』の組合せを作る
⇒ 黄色の点線
次に・・
空白席の終了を取出す条件をWHERE句に記述
別の方法で書いてみる
【手法２】
別の方法で取得してみます・・が
基本は同じです
違いはCTEを使わず、１つのQueryで書きます
・『開始位置』『終了位置』の組合せを作成
・ここから、連続する空白席を取出す
本書での記述を少し書き換えています
着席番号の全組合せ作る①
-- 全組合せを作る
SELECT R1.seat
,R2.seat
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
本書籍ではINNER JONで記述していますが
ここではCROSS JOINで解説します
▼ 出力(画像右側)
Restaurant テーブルをCROSS JOINして
全組み合わせを作ります
９行 x ９行 = ８１行になります
着席番号の全組合せ作る②
-- 全組合せを作る
SELECT R1.seat
,R2.seat
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat -- 条件追加
WHERE R2.seat > R1.seat
R2.seatはR1.seatより大きいという条件を追加
⇒ 既に埋まっている番号の組合せ
⇒ R1.seat を始点として見ると・・
R2.seat は次に埋まっている番号
重複番号の組合せは必要ない
例：(R1.seat, R2.seat) = (1,1)
(R1.seat, R2.seat) = (3,3)
R1より小さい番号は R2は必要ない
例：(R1.seat, R2.seat) = (3,1)
(R1.seat, R2.seat) = (16,3)
▼ 出力(画像右側)
『開始・終了』番号の全組合せ作る①
-- 開始位置と終了位置の組合せ
SELECT R1.seat -- 着席
,R1.seat+1 -- 開始位置
,R2.seat -- 着席
,R2.seat-1 -- 終了位置
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat
ここからが本丸です
空白席の開始と終了を取出します空白席の番号を
『上から』、『下から』探します
R1.seat は着席してる番号です
その次の番号(R1.seat + 1)は空白なのか？
⇒ 空白席だろう？ と想定して
R1.seat+1 を開始位置 とします
R2.seat も同じく着席してる番号です
その１つ前の番号(R2.seat - 1)は空白なのか？
⇒ 空白席だろう？ と想定して
R2.seat-1 を終了位置 とします
▼出力(画像青色)
『開始・終了』番号の全組合せ作る②
-- 開始位置と終了位置の組合せ
SELECT R1.seat -- 着席
,R1.seat + 1 AS start -- 開始位置
,MIN(R2.seat)-1 AS end -- 終了位置
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat
GROUP BY R1.seat
ORDER BY R1.seat
ここでは GROUP BY R1.seat を追記している
⇒ 開始位置をユニークにする
⇒ R1.seat + 1
⇒ 開始位置が決まる・・がまだ確定ではない
終了位置を決めるMIN(R2.seat)が大事なポイント
連続する空白番号を探すので
開始位置 R1.seat+1 に対する終了位置は
選択肢の中で最小番号としますあと、もう少しです
ココから不要なデータを除外します
▼出力(画像右側)
回答SQL その２
SELECT
R1.seat + 1 AS start -- 開始位置
,MIN(R2.seat)-1 AS end -- 終了位置
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat
GROUP BY R1.seat
HAVING (R1.seat + 1) <= MIN(R2.seat)-1 -- 追記
▼ 出力
| start | end |
|---|---|
| 4 | 7 |
| 11 | 15 |
| 17 | 17 |
条件を追記しています
⇒ HAVING (R1.seat + 1) <= MIN(R2.seat)-1
連続する空白席を取得したいので
終了位置は
開始位置と 同じor後・・の番号になる
最後にHAVINGで条件を追加して
⇒ 開始位置 <= 終了位置
画像左のテーブルから
条件に合う行だけを取出します
▼ 出力(画像右側を取出す)
最後に・・
『回答SQL その２』で使用されてる
GROUP BY と HAVING・・ですが
ここにフォーカスしてみます
GROUP BY の処理
・組合せの中からユニークな開始位置を決める
・MINを使って、終了位置も決める
HAVING の処理
・GROUP BY で決めた開始位置、終了位置から
取出したい場所の条件を追記してる
たった２行のクエリですが
データを集合として扱うSQLの特徴というか
優位性を表しているかと思いますJavaやC++で同じデータを取出すと
何回Loop処理が走るのでしょうか？こんな所にSQLの面白さを感じます
▼ イメージ図
