可視化 SQL | パズル#9  席あいてますか？

# 初めに
この問題は、SQLパズル #9
『席空いてますか』を解説します
手元に『SQL パズル』があればわかりやすいです

やりたい事は
並んでいる数字の中から
<font color="Blue">歯抜けの番号を探す</font>・・です

とあるレストランには20席程？の
席があるとします

1,2,3,8,9,10,16,18,19番には
お客さんが座っています

空白の席をSQLで取出してみます

**PostgreSQLで動作確認してます**

:::note
【手法１】
①　空白席の開始位置を探す
②　空白席の終了位置を探す
③　空白席の組合せを作る
④　連続する空白席を取出す
:::


# Restaurant Table & Data
```SQL:SQL
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);
```

# 空席の番号を見つける[開始]
```SQL:SQL
-- 開始番号
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
```

▼ <font color="orange">埋まっている数字</font>の次が空白の数字(seat+1)を探す
![pic_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/2118ddc6-7aa5-3cc9-2134-c12e9fa69712.png)




**[開始] 空白席の条件**
　　<font color="orange">埋まっている数字</font>(seat)の１つ先の数字
 　　⇒ seat + 1　とする
 　　⇒ **↑ ココが空白である条件**
 　　⇒ {<font color="orange">1,2,3,8,9,10,18,19</font>} 含まない
 　　⇒ {<font color="blue">4,11,17,20</font>} が残る

# 空席の番号を見つける[終了]
```SQL:SQL
-- 終了番号
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
```

▼ <font color="orange">埋まっている数字</font>の前が空白の数字(seat-1)を探す
![pic_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/153256f1-ebfa-177a-6acc-c0fb8cb0af93.png)


**[終了] 空白席の条件**
　　<font color="orange">埋まっている数字</font>(seat)の１つ前の数字
 　　⇒ seat - 1　とする
 　　⇒ **↑ ココが空白である条件**
 　　⇒ {<font color="orange">1,2,3,8,9,10,18,19</font>} 含まない
 　　⇒ {<font color="blue">7,15,17</font>} が残る

# 空席部分を可視化
空白席の開始と終了の部分を青く色づけしてます
複数の<font color="blue">開始位置</font>と<font color="blue">終了位置</font>が存在するので
ここを取出す必要があります

![pic_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/4cd066e6-b503-1921-0cce-59f1fa11fe6d.png)

# 開始・終了の場所を取る・・準備
```SQL: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 -- 終了
 ,(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|

![pic_7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/9eb7d51d-3b46-4900-9847-d1a40e9ab901.png)




**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`
　⇒ この中で、<font color="blue">開始より終了が後</font>となる条件を追加
　⇒ **[開始=４]**
 　　４より大きい終了は {7,15,17}
 　⇒ **[開始=11]**
 　　１１より大きい終了は {15,17}
 　⇒ 後も同じ・・・
`SELECT MIN(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.seat`
　⇒　この中で、<font color="red">最小の数字</font>を取る
　⇒ **[開始=４]**
 　　 {7,15,17}の最小は <font color="red">7</font>
 　⇒ **[開始=11]**
 　　 {15,17}の最小は <font color="red">15</font>
 　⇒ 後も同じ・・・

> この数字(空白終了番号)を次に利用します
> この数字を探す所がこのクイズの重要な所です
> 
> ・・といいますか
> 面白い所です




# 回答SQL その１
```SQL: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句に記述

![pic_9.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/c4e750f7-ce01-9824-d6c5-5b2700b6022b.png)

# 別の方法で書いてみる
:::note
【手法２】
別の方法で取得してみます・・が
基本は同じです
違いはCTEを使わず、１つのQueryで書きます

・『開始位置』『終了位置』の組合せを作成
・ここから、連続する空白席を取出す

<font color="red">本書での記述を少し書き換えています</font>
:::
# 着席番号の全組合せ作る①
```SQL:SQL
-- 全組合せを作る
SELECT R1.seat
	  ,R2.seat
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
```
> 本書籍ではINNER JONで記述していますが
> ここではCROSS JOINで解説します
> 


▼　出力(画像右側)
Restaurant テーブルをCROSS JOINして
全組み合わせを作ります
９行 x ９行 = ８１行になります
![pic_10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/fa64077a-ae53-931b-3b87-4cdc1c41ef12.png)


# 着席番号の全組合せ作る②
```SQL:SQL
-- 全組合せを作る
SELECT R1.seat
	  ,R2.seat
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat  -- 条件追加
```
> WHERE R2.seat > R1.seat

<font color="deeppink">R2.seatはR1.seatより大きい</font>という条件を追加
　⇒ 既に埋まっている番号の組合せ
　⇒ 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)
  
▼ 出力(画像右側)
![pic_11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/99bff52e-3fe9-7006-8d97-70e05b82bc44.png)



# 『開始・終了』番号の全組合せ作る①
```SQL:SQL
-- 開始位置と終了位置の組合せ
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)は空白なのか？
　⇒ 空白席だろう？ と想定して
　　 <font color="blue">R1.seat+1 を開始位置</font> とします
 
R2.seat も同じく着席してる番号です
**その１つ前の番号**(R2.seat - 1)は空白なのか？
　⇒ 空白席だろう？ と想定して
　　 <font color="blue">R2.seat-1 を終了位置</font> とします
 
▼出力(画像青色)
![pic_12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/f9466f3a-7241-44e5-b27e-ce3ff6bef61a.png)

# 『開始・終了』番号の全組合せ作る②
```SQL:SQL
-- 開始位置と終了位置の組合せ
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
　⇒　開始位置が決まる・・がまだ<font color="deeppink">確定ではない</font>

> 終了位置を決める<font color="deeppink">MIN(R2.seat)</font>が大事なポイント
> 連続する空白番号を探すので
> 開始位置 R1.seat+1 に対する終了位置は
> <font color="deeppink">選択肢の中で最小番号</font>とします
> 
> あと、もう少しです
> ココから不要なデータを除外します

▼出力(画像右側)
![pic_13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/606ab19f-17c8-45be-bd61-6c05dd9c2f20.png)



# 回答SQL その２
```SQL: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`

**連続する空白席**を取得したいので
終了位置は
<font color="deeppink">開始位置と 同じor後</font>・・の番号になる

最後にHAVINGで条件を追加して
　⇒ <font color="blue">開始位置 <= 終了位置</font>
画像左のテーブルから
条件に合う行だけを取出します


▼ 出力(画像右側を取出す)
![pic_15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/dd2897af-3327-44ba-b506-7c2459149874.png)

# 最後に・・
『回答SQL その２』で使用されてる
`GROUP BY` と `HAVING`・・ですが
ここにフォーカスしてみます

**GROUP BY の処理**
・組合せの中からユニークな開始位置を決める
・MINを使って、終了位置も決める
**HAVING の処理**
・GROUP BY で決めた開始位置、終了位置から
　取出したい場所の条件を追記してる

> <font color="deeppink">たった２行のクエリ</font>ですが
> データを集合として扱うSQLの特徴というか
> 優位性を表しているかと思います
> 
> JavaやC++で同じデータを取出すと
> 何回Loop処理が走るのでしょうか？
> 
> こんな所にSQLの面白さを感じます

▼ イメージ図
![pic_16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/9d854a91-4b3f-45c3-9a2f-4db65760fc44.png)




# 参考文献
[SQLパズル 第2版~プログラミングが変わる書き方/考え方 | Joe Celko, ミック](https://www.shoeisha.co.jp/book/detail/9784798114132)