Задача об островах и проливах – это классическая задача в SQL, часто используемая для оценки навыков программиста в работе с базами данных. Суть задачи заключается в том, чтобы в таблице, содержащей данные о событиях и их временных интервалах, объединить отдельные записи в непрерывные интервалы, представляющие собой «острова» (периоды, когда происходили события) и «проливы» (промежутки между ними).
Пример задачи
Рассмотрим задачу на примере задания с сайта SQLTest.online. Все задания на сайте ранжированы по сложности на основе оценок зарегистрированных пользователей, и эта задача в числе немногих имеет оценку «Очень сложно».
Условия задачи
Имеется таблица rental
, в которой хранятся записи о фильмах, взятых напрокат пользователями сервиса Sakila. Для решения задачи нам понадобятся только три колонки из этой таблицы:
– идентификатор клиентаcustomer_id
– дата и время аренды фильмаrental_date
– дата и время возврата фильмаreturn_date
Задача
Задача состоит в следующем:
Для клиента MARY SMITH (customer_id = 1) найдите все периоды, когда у нее был хотя бы один взятый напрокат фильм.
Решение
1. Извлечение записей по заданному клиенту
Начнем с простого – напишем запрос для извлечения всех записей по данному клиенту:
select
customer_id,
rental_date as start_date,
return_date as finish_date
from rental
where customer_id = 1
Этот запрос вернет нам 32 записи о фильмах, арендованных MARY SMITH.
2. Нумерация строк и определение «проливов»
Воспользуемся оконной функцией
чтобы для каждой строки вычислить ее порядковый номер в порядке возврата дисков в пункт проката. К сортировке добавим дату начала проката, чтобы в случае одновременного возврата двух дисков первым был тот, что взят ранее.row_number()
,
Еще одна оконная функция –
– поможет нам для каждой записи получить дату возврата (lag()
) из предыдущей строки.return_date
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num;
Итак, если вы выполните этот запрос здесь, то получите следующий результат:
|-------------|---------|---------------------|---------------------|---------------------|
| customer_id | row_num | start_date | finish_date | prev_return_date |
|-------------|---------|---------------------|---------------------|---------------------|
| 1 | 1 | 2005-05-28 10:35:23 | 2005-06-03 06:32:23 | [null] |
| 1 | 2 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | 2005-06-03 06:32:23 |
| 1 | 3 | 2005-06-16 15:18:57 | 2005-06-17 21:05:57 | 2005-06-03 12:00:37 |
| 1 | 4 | 2005-06-15 18:02:53 | 2005-06-19 15:54:53 | 2005-06-17 21:05:57 |
| 1 | 5 | 2005-06-18 13:33:59 | 2005-06-19 17:40:59 | 2005-06-19 15:54:53 |
| 1 | 6 | 2005-06-18 08:41:48 | 2005-06-22 03:36:48 | 2005-06-19 17:40:59 |
| 1 | 7 | 2005-06-15 00:54:12 | 2005-06-23 02:42:12 | 2005-06-22 03:36:48 |
| 1 | 8 | 2005-06-15 21:08:46 | 2005-06-25 02:26:46 | 2005-06-23 02:42:12 |
| 1 | 9 | 2005-06-21 06:24:45 | 2005-06-28 03:28:45 | 2005-06-25 02:26:46 |
| 1 | 10 | 2005-07-08 07:33:56 | 2005-07-12 13:25:56 | 2005-06-28 03:28:45 |
| 1 | 11 | 2005-07-09 16:38:01 | 2005-07-13 18:02:01 | 2005-07-12 13:25:56 |
| 1 | 12 | 2005-07-08 03:17:05 | 2005-07-14 01:19:05 | 2005-07-13 18:02:01 |
| 1 | 13 | 2005-07-09 13:24:07 | 2005-07-14 14:01:07 | 2005-07-14 01:19:05 |
| 1 | 14 | 2005-07-11 10:13:46 | 2005-07-19 13:15:46 | 2005-07-14 14:01:07 |
| 1 | 15 | 2005-07-28 17:33:39 | 2005-07-29 20:17:39 | 2005-07-19 13:15:46 |
| 1 | 16 | 2005-07-28 19:20:07 | 2005-07-29 22:54:07 | 2005-07-29 20:17:39 |
| 1 | 17 | 2005-07-28 09:04:45 | 2005-07-30 12:37:45 | 2005-07-29 22:54:07 |
| 1 | 18 | 2005-07-28 16:18:23 | 2005-07-30 17:56:23 | 2005-07-30 12:37:45 |
| 1 | 19 | 2005-07-27 11:31:22 | 2005-07-31 06:50:22 | 2005-07-30 17:56:23 |
| 1 | 20 | 2005-07-29 03:58:49 | 2005-08-01 05:16:49 | 2005-07-31 06:50:22 |
| 1 | 21 | 2005-07-31 02:42:18 | 2005-08-02 23:26:18 | 2005-08-01 05:16:49 |
| 1 | 22 | 2005-08-02 18:01:38 | 2005-08-04 13:19:38 | 2005-08-02 23:26:18 |
| 1 | 23 | 2005-08-01 08:51:04 | 2005-08-10 12:12:04 | 2005-08-04 13:19:38 |
| 1 | 24 | 2005-08-02 15:36:52 | 2005-08-10 16:40:52 | 2005-08-10 12:12:04 |
| 1 | 25 | 2005-08-17 12:37:54 | 2005-08-19 10:11:54 | 2005-08-10 16:40:52 |
| 1 | 26 | 2005-08-19 09:55:16 | 2005-08-20 14:44:16 | 2005-08-19 10:11:54 |
| 1 | 27 | 2005-08-18 03:57:29 | 2005-08-22 23:05:29 | 2005-08-20 14:44:16 |
| 1 | 28 | 2005-08-21 23:33:57 | 2005-08-23 01:30:57 | 2005-08-22 23:05:29 |
| 1 | 29 | 2005-08-19 13:56:54 | 2005-08-23 08:50:54 | 2005-08-23 01:30:57 |
| 1 | 30 | 2005-08-22 01:27:57 | 2005-08-27 07:01:57 | 2005-08-23 08:50:54 |
| 1 | 31 | 2005-08-22 19:41:37 | 2005-08-28 22:49:37 | 2005-08-27 07:01:57 |
| 1 | 32 | 2005-08-22 20:03:46 | 2005-08-30 01:51:46 | 2005-08-28 22:49:37 |
3. Определение начала новых периодов
Из этой таблицы мы можем установить, является ли каждая следующая запись непрерывным продолжением предыдущей. Для этого нужно убедиться, что дата в колонке prev_return_date
больше или равна start_date
. Для удобства записи, воспользуемся CTE (Common Table Expression):
with d as (
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num
) select
*,
case when d.prev_return_date >= start_date then 0 else 1 end new_period
from d;
В результате этого запроса мы получим дополнительную колонку
, где значение 1 означает начало нового периода непрерывной аренды фильмов.new_period
|-------------|---------|---------------------|---------------------|---------------------|------------|
| customer_id | row_num | start_date | finish_date | prev_return_date | new_period |
|-------------|---------|---------------------|---------------------|---------------------|------------|
| 1 | 1 | 2005-05-28 10:35:23 | 2005-06-03 06:32:23 | [null] | 1 |
| 1 | 2 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | 2005-06-03 06:32:23 | 0 |
| 1 | 3 | 2005-06-16 15:18:57 | 2005-06-17 21:05:57 | 2005-06-03 12:00:37 | 1 |
| 1 | 4 | 2005-06-15 18:02:53 | 2005-06-19 15:54:53 | 2005-06-17 21:05:57 | 0 |
| 1 | 5 | 2005-06-18 13:33:59 | 2005-06-19 17:40:59 | 2005-06-19 15:54:53 | 0 |
| 1 | 6 | 2005-06-18 08:41:48 | 2005-06-22 03:36:48 | 2005-06-19 17:40:59 | 0 |
| 1 | 7 | 2005-06-15 00:54:12 | 2005-06-23 02:42:12 | 2005-06-22 03:36:48 | 0 |
| 1 | 8 | 2005-06-15 21:08:46 | 2005-06-25 02:26:46 | 2005-06-23 02:42:12 | 0 |
| 1 | 9 | 2005-06-21 06:24:45 | 2005-06-28 03:28:45 | 2005-06-25 02:26:46 | 0 |
| 1 | 10 | 2005-07-08 07:33:56 | 2005-07-12 13:25:56 | 2005-06-28 03:28:45 | 1 |
| 1 | 11 | 2005-07-09 16:38:01 | 2005-07-13 18:02:01 | 2005-07-12 13:25:56 | 0 |
| 1 | 12 | 2005-07-08 03:17:05 | 2005-07-14 01:19:05 | 2005-07-13 18:02:01 | 0 |
| 1 | 13 | 2005-07-09 13:24:07 | 2005-07-14 14:01:07 | 2005-07-14 01:19:05 | 0 |
| 1 | 14 | 2005-07-11 10:13:46 | 2005-07-19 13:15:46 | 2005-07-14 14:01:07 | 0 |
| 1 | 15 | 2005-07-28 17:33:39 | 2005-07-29 20:17:39 | 2005-07-19 13:15:46 | 1 |
| 1 | 16 | 2005-07-28 19:20:07 | 2005-07-29 22:54:07 | 2005-07-29 20:17:39 | 0 |
| 1 | 17 | 2005-07-28 09:04:45 | 2005-07-30 12:37:45 | 2005-07-29 22:54:07 | 0 |
| 1 | 18 | 2005-07-28 16:18:23 | 2005-07-30 17:56:23 | 2005-07-30 12:37:45 | 0 |
| 1 | 19 | 2005-07-27 11:31:22 | 2005-07-31 06:50:22 | 2005-07-30 17:56:23 | 0 |
| 1 | 20 | 2005-07-29 03:58:49 | 2005-08-01 05:16:49 | 2005-07-31 06:50:22 | 0 |
| 1 | 21 | 2005-07-31 02:42:18 | 2005-08-02 23:26:18 | 2005-08-01 05:16:49 | 0 |
| 1 | 22 | 2005-08-02 18:01:38 | 2005-08-04 13:19:38 | 2005-08-02 23:26:18 | 0 |
| 1 | 23 | 2005-08-01 08:51:04 | 2005-08-10 12:12:04 | 2005-08-04 13:19:38 | 0 |
| 1 | 24 | 2005-08-02 15:36:52 | 2005-08-10 16:40:52 | 2005-08-10 12:12:04 | 0 |
| 1 | 25 | 2005-08-17 12:37:54 | 2005-08-19 10:11:54 | 2005-08-10 16:40:52 | 1 |
| 1 | 26 | 2005-08-19 09:55:16 | 2005-08-20 14:44:16 | 2005-08-19 10:11:54 | 0 |
| 1 | 27 | 2005-08-18 03:57:29 | 2005-08-22 23:05:29 | 2005-08-20 14:44:16 | 0 |
| 1 | 28 | 2005-08-21 23:33:57 | 2005-08-23 01:30:57 | 2005-08-22 23:05:29 | 0 |
| 1 | 29 | 2005-08-19 13:56:54 | 2005-08-23 08:50:54 | 2005-08-23 01:30:57 | 0 |
| 1 | 30 | 2005-08-22 01:27:57 | 2005-08-27 07:01:57 | 2005-08-23 08:50:54 | 0 |
| 1 | 31 | 2005-08-22 19:41:37 | 2005-08-28 22:49:37 | 2005-08-27 07:01:57 | 0 |
| 1 | 32 | 2005-08-22 20:03:46 | 2005-08-30 01:51:46 | 2005-08-28 22:49:37 | 0 |
4. Нумерация «островов»
Воспользуемся оконной функцией sum()
, чтобы превратить последовательность нулей и единиц в номера периодов («островов»):
with d as (
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num
) select
*,
sum(case when d.prev_return_date >= start_date then 0 else 1 end) over (order by row_num) island_id
from d;
И немедленно получим результат:
|-------------|---------|---------------------|---------------------|---------------------|-----------|
| customer_id | row_num | start_date | finish_date | prev_return_date | island_id |
|-------------|---------|---------------------|---------------------|---------------------|-----------|
| 1 | 1 | 2005-05-28 10:35:23 | 2005-06-03 06:32:23 | [null] | 1 |
| 1 | 2 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | 2005-06-03 06:32:23 | 1 |
| 1 | 3 | 2005-06-16 15:18:57 | 2005-06-17 21:05:57 | 2005-06-03 12:00:37 | 2 |
| 1 | 4 | 2005-06-15 18:02:53 | 2005-06-19 15:54:53 | 2005-06-17 21:05:57 | 2 |
| 1 | 5 | 2005-06-18 13:33:59 | 2005-06-19 17:40:59 | 2005-06-19 15:54:53 | 2 |
| 1 | 6 | 2005-06-18 08:41:48 | 2005-06-22 03:36:48 | 2005-06-19 17:40:59 | 2 |
| 1 | 7 | 2005-06-15 00:54:12 | 2005-06-23 02:42:12 | 2005-06-22 03:36:48 | 2 |
| 1 | 8 | 2005-06-15 21:08:46 | 2005-06-25 02:26:46 | 2005-06-23 02:42:12 | 2 |
| 1 | 9 | 2005-06-21 06:24:45 | 2005-06-28 03:28:45 | 2005-06-25 02:26:46 | 2 |
| 1 | 10 | 2005-07-08 07:33:56 | 2005-07-12 13:25:56 | 2005-06-28 03:28:45 | 3 |
| 1 | 11 | 2005-07-09 16:38:01 | 2005-07-13 18:02:01 | 2005-07-12 13:25:56 | 3 |
| 1 | 12 | 2005-07-08 03:17:05 | 2005-07-14 01:19:05 | 2005-07-13 18:02:01 | 3 |
| 1 | 13 | 2005-07-09 13:24:07 | 2005-07-14 14:01:07 | 2005-07-14 01:19:05 | 3 |
| 1 | 14 | 2005-07-11 10:13:46 | 2005-07-19 13:15:46 | 2005-07-14 14:01:07 | 3 |
| 1 | 15 | 2005-07-28 17:33:39 | 2005-07-29 20:17:39 | 2005-07-19 13:15:46 | 4 |
| 1 | 16 | 2005-07-28 19:20:07 | 2005-07-29 22:54:07 | 2005-07-29 20:17:39 | 4 |
| 1 | 17 | 2005-07-28 09:04:45 | 2005-07-30 12:37:45 | 2005-07-29 22:54:07 | 4 |
| 1 | 18 | 2005-07-28 16:18:23 | 2005-07-30 17:56:23 | 2005-07-30 12:37:45 | 4 |
| 1 | 19 | 2005-07-27 11:31:22 | 2005-07-31 06:50:22 | 2005-07-30 17:56:23 | 4 |
| 1 | 20 | 2005-07-29 03:58:49 | 2005-08-01 05:16:49 | 2005-07-31 06:50:22 | 4 |
| 1 | 21 | 2005-07-31 02:42:18 | 2005-08-02 23:26:18 | 2005-08-01 05:16:49 | 4 |
| 1 | 22 | 2005-08-02 18:01:38 | 2005-08-04 13:19:38 | 2005-08-02 23:26:18 | 4 |
| 1 | 23 | 2005-08-01 08:51:04 | 2005-08-10 12:12:04 | 2005-08-04 13:19:38 | 4 |
| 1 | 24 | 2005-08-02 15:36:52 | 2005-08-10 16:40:52 | 2005-08-10 12:12:04 | 4 |
| 1 | 25 | 2005-08-17 12:37:54 | 2005-08-19 10:11:54 | 2005-08-10 16:40:52 | 5 |
| 1 | 26 | 2005-08-19 09:55:16 | 2005-08-20 14:44:16 | 2005-08-19 10:11:54 | 5 |
| 1 | 27 | 2005-08-18 03:57:29 | 2005-08-22 23:05:29 | 2005-08-20 14:44:16 | 5 |
| 1 | 28 | 2005-08-21 23:33:57 | 2005-08-23 01:30:57 | 2005-08-22 23:05:29 | 5 |
| 1 | 29 | 2005-08-19 13:56:54 | 2005-08-23 08:50:54 | 2005-08-23 01:30:57 | 5 |
| 1 | 30 | 2005-08-22 01:27:57 | 2005-08-27 07:01:57 | 2005-08-23 08:50:54 | 5 |
| 1 | 31 | 2005-08-22 19:41:37 | 2005-08-28 22:49:37 | 2005-08-27 07:01:57 | 5 |
| 1 | 32 | 2005-08-22 20:03:46 | 2005-08-30 01:51:46 | 2005-08-28 22:49:37 | 5 |
5. Группировка и вывод результата
Финальным шагом будет группировка полученного результата по номеру «острова» и извлечение минимальной даты начала (
) и максимальной даты окончания (start_date
) для каждого периода непрерывной аренды. Для наглядности продолжим использовать CTE-подход:finish_date
with d as (
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num
),
islands as (
select
*,
sum(case when d.prev_return_date >= start_date then 0 else 1 end) over (order by row_num) island_id
from d
)
select
island_id,
min(start_date) start_date,
max(finish_date) finish_date
from islands
group by island_id;
Сгруппировав строки, мы получим искомую таблицу:
|-----------|---------------------|---------------------|
| island_id | start_date | finish_date |
|-----------|---------------------|---------------------|
| 1 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 |
| 2 | 2005-06-15 00:54:12 | 2005-06-28 03:28:45 |
| 3 | 2005-07-08 03:17:05 | 2005-07-19 13:15:46 |
| 4 | 2005-07-27 11:31:22 | 2005-08-10 16:40:52 |
| 5 | 2005-08-17 12:37:54 | 2005-08-30 01:51:46 |
Таким образом, мы установили, что MARY SMITH имела в своем распоряжении арендованные диски в течение пяти непрерывных периодов. Вы можете убедиться в этом, выполнив проверку задачи на сайте SQLTest.online
Заключение:
- В статье использованы CTE (Common Table Expressions) для разделения сложных запросов на более мелкие и понятные части.
- Применялись оконные функции
row_number()
иlag()
для нумерации строк и получения значений из предыдущих записей. - Функция
sum()
использовалась для преобразования последовательности нулей и единиц в номера периодов («островов»). - Группировка по номеру «острова» позволила получить информацию о начале и конце каждого периода непрерывной аренды.
Комментарии