Visualize SQL | Puzzle #9 Available Seats

# Beginning
This article is based on 『SQL Puzzle and Answers』
　⇒ #9 Available Seats
It is better with this book to read this article.

What I want to do is ・・
<font color="Blue">find the missing numbers</font> from "numbers"

There are about 20 seats in a restaurant

Customers are sitting in 
seats 1,2,3,8,9,10,16,18 and 19

Let's extract the empty seats(numbers) using SQL

**Operation confirmed with PostgreSQL**

:::note
【Part 1】
①　Find the start number of empty seats
②　Find the end number of empty seats
③　Create a combination of empty seats
④　Extract consecutive empty seat numbers

There is Part2
:::


# Restaurant Table & Data
```SQL:SQL
CREATE TABLE Restaurant(
   seat integer -- occupied seat number
);

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);
```

# Find the start number of empty seats
```SQL:SQL
--Start Number
WITH Firstseat AS (
	SELECT (seat + 1) AS seat -- one seat after
    FROM Restaurant
    WHERE (seat + 1) NOT IN (SELECT seat FROM Restaurant)
	AND (seat + 1) < 1001
)

SELECT * FROM Firstseat

-- Output
-- 4
-- 11
-- 17
-- 20
```

▼ Find a empty number(seat+1) next to <font color="orange">a occupied seat</font>
![pic_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/46ec338c-b2bc-4332-bd6a-55495d6599af.png)

**[Start] Empty Conditions**
　　next to <font color="orange">the occupyed seat</font>
 　　⇒ define as 『seat + 1』
 　　⇒ **↑ Conditions where this is empty**
 　　⇒ Do not include {<font color="orange">1,2,3,8,9,10,18,19</font>}
 　　⇒ {<font color="blue">4,11,17,20</font>} are left

# Find the end number of empty seats
```SQL:SQL
-- End Number
WITH Lastseat AS (
	SELECT (seat - 1) AS seat -- one seat ahead
    FROM Restaurant
	WHERE (seat - 1) NOT IN (SELECT seat FROM Restaurant)
	AND (seat - 1) > 0 -- There can be no number less than 0
)

SELECT * FROM Lastseat

-- Output
-- 7
-- 15
-- 17
```

▼ Find a empty number(seat-1) next to <font color="orange">the used number</font>
![pic_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/d3c56370-bc39-4a0a-8cd7-802c532171ac.png)



**[End] Empty Conditions**
　　next to <font color="orange">the occupied number</font>
 　　⇒ define as 『seat - 1』
 　　⇒ **↑ Conditions where this is empty**
 　　⇒ Do not include {<font color="orange">1,2,3,8,9,10,18,19</font>}
 　　⇒ {<font color="blue">7,15,17</font>} are left
   

# Visualize Empty Seats
『start & end』of empty seats are blue area
They are multiple <font color="blue">start and end numbers</font>
We are going to retrive these numbers・・next

![pic_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/fc91ebd7-3fb1-460b-bf43-3fc94c02cac2.png)



# Preparing to retrive『start & end』numbers
```SQL:SQL
-- Start Number of empty seats
WITH Firstseat AS (
	SELECT (seat + 1) AS seat FROM Restaurant
    WHERE (seat + 1) NOT IN (SELECT seat FROM Restaurant)
	AND (seat + 1) < 1001                                 
), 

-- End Number of empty seats
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 -- Start
 ,L1.seat AS finish -- End
 ,(SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2) -- list of End seats
 ,(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
```
▼ Output
|Start|End|list of End seats|***|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/ff963b80-f626-4f70-a493-fd419b5b2688.png)


**SELECT clause**
`SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2`
　⇒ Creating a list of『End of empty seats』
　⇒ {7,15,17}
　⇒ These three numbers are common

`SELECT ARRAY_AGG(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.sea`
　⇒ Add a condition where <font color="blue">the end is later than the start</font>
　⇒ **[Start=４]**
 　　"End numbers greater than 4" are {7,15,17}
 　⇒ **[Start=11]**
 　　"End numbers greater than 11" are {15,17}
 　⇒ same after ・・・
`SELECT MIN(L2.seat) FROM Lastseat AS L2 WHERE F1.seat <= L2.seat`
　⇒　Retrive <font color="red">the smallest number</font> in these lists
　⇒ **[Start=４]**
 　　 The minimum number in {7,15,17} is <font color="red">7</font>
 　⇒ **[Start=11]**
 　　 The minimum number in {15,17} is <font color="red">15</font>
 　⇒ same after ・・・

> This number(end of empty number) will be used next step
> Finding this number is the important part of this quiz
> 
> ・・well
> It's an interesting part

# Final Query(Part1)
```SQL:SQL
-- Start Number of empty seats
WITH Firstseat AS (
	SELECT (seat + 1) AS seat FROM Restaurant
    WHERE (seat + 1) NOT IN (SELECT seat FROM Restaurant)
	AND (seat + 1) < 1001                              
),

-- End Number of empty seats
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)
```
▼ Output

|start|finish|
|---|---|
|4|7|
|11|15|
|17|17|

First・・
　Crate combinations of『start & end』of empty numbers
　⇒　yellow dotted line
Second・・
　Add the condition to retrieve『end of empty numbers』
　in WHERE condition

![pic_9.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/b50c0838-32f7-45ab-8e3d-35843294b5ef.png)


# Another Query
:::note
【Part２】
Try to get the empty seats by a different way・・
but the basic idea is the same


The difference is that it does not use CTE 
and it is written with one query

・Make a combination of『start & end』empty numbers
・Extract consecutive empty seats from here ↑


<font color="red">I have changed the original query a little</font>

:::
# Create combination of occupied numbers①
```SQL:SQL
-- Create combination
SELECT R1.seat
	  ,R2.seat
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
```

> the original query uses INNER JON
> but I will explain using CROSS JOIN

▼　Output(right side of image)
Use CROSS JOIN to create a all combinations of
occupied numbers
　⇒ ９ x ９ = ８１rows

![pic_10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/6b33ab57-7c5f-4621-b280-5ccff1a8ba4a.png)



# Create combination of occupied numbers②
```SQL:SQL
-- Create combination
SELECT R1.seat
	  ,R2.seat
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat  -- add condition
```

Add condition
　⇒ <font color="deeppink">R2.seat is greater than R1.seat</font>
　⇒ this is a combination of occupied numbers
　⇒ Considering R1.seat as a starting point
　　 R2.seat would be the next occupied number


**Duplicate numbers are not required**
ie：(R1.seat, R2.seat) = (1,1)
　　(R1.seat, R2.seat) = (3,3)

**R2 smaller than R1 is not required**
ie：(R1.seat, R2.seat) = (3,1)
　　(R1.seat, R2.seat) = (16,3)
  
▼　Output(right side of image)
![pic_11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/264ddcb6-f8fa-4f9e-8e37-555759335f01.png)


# Create a combination of empty numbers①
```SQL:SQL
-- Combination of empty numbers
SELECT 
  R1.seat   -- occupied
 ,R1.seat+1 -- empty start number
 ,R2.seat   -- occupied
 ,R2.seat-1 -- empty end number
FROM Restaurant AS R1
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat
```
> We are goint to ・・
> 
> Look for empty seat numbers
> from top(↓) and from down(↑)

R1.seat is occupied number
Is **the next number**(R1.seat + 1) empty?
　⇒ Assuming it is empty・・
　　 see <font color="blue">R1.seat+1</font> as a start number

R2.seat is also occupied number
Is **the previous number**(R2.seat - 1) empty?
　⇒ Assuming it is empty・・
　　 see <font color="blue">R2.seat-1</font> as an end number
 
 
▼ Output(blue letters)
![pic_12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/ba5663df-ee67-46b2-9386-877eb4622f6e.png)


# Create a combination of empty numbers②
```SQL:SQL
-- Combination of empty numbers
SELECT 
  R1.seat   -- occupied
  ,R1.seat + 1 AS start -- empty start number
  ,MIN(R2.seat)-1 AS end -- empty end number
FROM Restaurant AS R1      
CROSS JOIN Restaurant AS R2
WHERE R2.seat > R1.seat
GROUP BY R1.seat
ORDER BY R1.seat
```
Add `GROUP BY R1.seat`
　⇒　Make starting number unique
　⇒　R1.seat + 1
　⇒　starting numbers are decided, but it is <font color="deeppink">not confirmed</font> yet


> The important column is <font color="deeppink">MIN(R2.seat)</font>
> which determines the end number
> 
> Since we are looking for consecutive empty numbers,
> the end number related to the start number is 
> <font color="deeppink">the lowest number among the choices</font>
> 
> Almost done!
> Exclude unnecessary numbers・・next

▼ Output(right side of image)
![pic_13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/78a082d4-ecfb-4349-9086-abae1aba033e.png)



# Final Query(Part2)
```SQL:SQL
SELECT
  R1.seat + 1 AS start -- start number	
 ,MIN(R2.seat)-1 AS end -- end number
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 -- Add
```
▼ Output
|start|end|
|---|---|
|4|7|
|11|15|
|17|17|

Add HAVING condition
　⇒ `HAVING (R1.seat + 1) <= MIN(R2.seat)-1`

we want to retrive **consecutive empty numbers**,
the end number will be <font color="deeppink">later or equal</font> to the start number

Add HAVING clause in the end
　⇒　<font color="blue">start number <= end number</font>

Extract the rows that meet the HAVING condition
from left side of image

▼ Output(right side of image)
![pic_15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/09c9951e-8bd0-473d-87c8-7db9a109b7e4.png)


# in the end・・
Let's focus on `GROUP BY` and `HAVING`
that are used in 『Final Query(Part2)』


**what GROUP BY is done**
・Determine unique start numbers among combinations
・Also determine end numbers using MIN()
**what HAVING is done**
・Add conditions to retrive『start & end』numbres 
　that are determined using **GROUP BY**

> It's <font color="deeppink">just two lines query</font>
> I think this shows the superiority of SQL, 
> which treats data as a set
> 
> How many Loop processes will be executed 
> if the same data is retrieved by Java or C++?
> 
> This is the interesting part of SQL

![pic_16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1242736/ff286429-d33f-49b6-ab69-816b69f17355.png)




# References 
[Joe Celko's SQL Puzzles and Answers](https://www.amazon.com/Puzzles-Answers-Kaufmann-Management-Systems/dp/0123735963)