SQL for Smarties | SQL Programming Style | Trees and Hierarchies in SQL | SQL Puzzles and Answers | Data and Databases

Monday, July 17, 2006

Query to find amissing number

SQL Apprentice Question
I need to write a query to find out a set of missing number in a given
sequence.

Eg : a Column in some table has the following data

Col1

1
2
3
4
5
6
8
9
10

Here I need to write a query to find out that number 7 is missing in the
given sequence.

One possible solution is by using any loop. But I am looking out if the same
can be achieved using any query.

>> I need to write a query to find out a set of missing numbers in a given sequence. <<

Let's assume we have a table of people who bought tickets that are
supposed to be in sequential order and we want to make a list of what
is missing in each buyer's set of tickets.

CREATE TABLE Tickets
ticket_nbr INTEGER DEFAULT 1 NOT NULL
CHECK (ticket_nbr > 0),

INSERT INTO Tickets VALUES ('a', 2);
INSERT INTO Tickets VALUES ('a', 3);
INSERT INTO Tickets VALUES ('a', 4);
INSERT INTO Tickets VALUES ('b', 4);
INSERT INTO Tickets VALUES ('c', 1);
INSERT INTO Tickets VALUES ('c', 2);
INSERT INTO Tickets VALUES ('c', 3);
INSERT INTO Tickets VALUES ('c', 4);
INSERT INTO Tickets VALUES ('c', 5);
INSERT INTO Tickets VALUES ('d', 1);
INSERT INTO Tickets VALUES ('d', 6);
INSERT INTO Tickets VALUES ('d', 7);
INSERT INTO Tickets VALUES ('d', 9);
INSERT INTO Tickets VALUES ('e', 10);

If we can assume that there is a relatively small number of Tickets,
then you could use a table of sequential numbers from 1 to (n) and
write:

FROM Tickets AS T1, Sequence AS S1
WHERE seq <= (SELECT MAX(ticket_nbr) -- set the range
FROM Tickets AS T2
AND seq NOT IN (SELECT ticket_nbr -- get missing numbers
FROM Tickets AS T3

Another version:

BEGIN
SELECT *
INTO #foobar
FROM Tickets
UNION ALL
FROM Tickets;

(T1.ticket_nbr + 1) AS gap_start,
(MIN(T2.ticket_nbr) - 1) AS gap_end
FROM --Tickets AS T1,
#foobar AS T1,
Tickets AS T2
WHERE T1.ticket_nbr < T2.ticket_nbr
HAVING MIN(T2.ticket_nbr) - T1.ticket_nbr > 1;

END;

The trick here is to add a zero to act as a boundary when 1 is missing
from the sequence.

In Standard SQL-92, you could write the UNION ALL expression directly
in the FROM clause.