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 ・・
find the missing numbers 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

【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

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

--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 a occupied seat

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

Find the end number of empty seats

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 the used number

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

Visualize Empty Seats

『start & end』of empty seats are blue area
They are multiple start and end numbers
We are going to retrive these numbers・・next

Preparing to retrive『start & end』numbers

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

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 the end is later than the start
　⇒ [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 the smallest number in these lists
　⇒ [Start=４]
　　 The minimum number in {7,15,17} is 7
　⇒ [Start=11]
　　 The minimum number in {15,17} is 15
　⇒ 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

-- 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

Another Query

【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 ↑

I have changed the original query a little

Create combination of occupied numbers①

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

Create combination of occupied numbers②

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
　⇒ R2.seat is greater than R1.seat
　⇒ 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)

Create a combination of empty numbers①

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 R1.seat+1 as a start number

R2.seat is also occupied number
Is the previous number(R2.seat - 1) empty?
　⇒ Assuming it is empty・・
　　 see R2.seat-1 as an end number

▼ Output(blue letters)

Create a combination of empty numbers②

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 not confirmed yet

The important column is MIN(R2.seat)
which determines the end number

Since we are looking for consecutive empty numbers,
the end number related to the start number is
the lowest number among the choices

Almost done!
Exclude unnecessary numbers・・next

▼ Output(right side of image)

Final Query(Part2)

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 later or equal to the start number

Add HAVING clause in the end
　⇒　start number <= end number

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

▼ Output(right side of image)

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 just two lines query
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

References

Joe Celko's SQL Puzzles and Answers