rozhnev 01 июля 2024
Базы данных Задачки
0
4473

🏝️ Решаем очень сложную SQL-задачу об островах и проливах

Пошаговый разбор решения SQL-задачи об островах и проливах на примере базы данных Sakila с использованием оконных функций и CTE.

Задача об островах и проливах – это классическая задача в SQL, часто используемая для оценки навыков программиста в работе с базами данных. Суть задачи заключается в том, чтобы в таблице, содержащей данные о событиях и их временных интервалах, объединить отдельные записи в непрерывные интервалы, представляющие собой «острова» (периоды, когда происходили события) и «проливы» (промежутки между ними).

Пример задачи

Рассмотрим задачу на примере задания с сайта SQLTest.online. Все задания на сайте ранжированы по сложности на основе оценок зарегистрированных пользователей, и эта задача в числе немногих имеет оценку «Очень сложно».

Условия задачи

Имеется таблица rental, в которой хранятся записи о фильмах, взятых напрокат пользователями сервиса Sakila. Для решения задачи нам понадобятся только три колонки из этой таблицы:

  • customer_id – идентификатор клиента
  • rental_date – дата и время аренды фильма
  • return_date – дата и время возврата фильма

Задача

Задача состоит в следующем:

Для клиента MARY SMITH (customer_id = 1) найдите все периоды, когда у нее был хотя бы один взятый напрокат фильм.
Задача с сайта SQLTest.online

Решение

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;

В результате этого запроса мы получим дополнительную колонку new_period, где значение 1 означает начало нового периода непрерывной аренды фильмов.

|-------------|---------|---------------------|---------------------|---------------------|------------|
| 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) и максимальной даты окончания (finish_date) для каждого периода непрерывной аренды. Для наглядности продолжим использовать CTE-подход:

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

Заключение:

  1. В статье использованы CTE (Common Table Expressions) для разделения сложных запросов на более мелкие и понятные части.
  2. Применялись оконные функции row_number() и lag() для нумерации строк и получения значений из предыдущих записей.
  3. Функция sum() использовалась для преобразования последовательности нулей и единиц в номера периодов («островов»).
  4. Группировка по номеру «острова» позволила получить информацию о начале и конце каждого периода непрерывной аренды.

ВАКАНСИИ

Добавить вакансию
Разработчик C++
Москва, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

admin
18 июля 2019

Логические задачи: 15 упражнений для тренировки мозга

Программистам без логики никуда. Поэтому время прокачать мозг: проверьте св...
admin
23 февраля 2017

SQL за 20 минут

Предлагаем вашему вниманию статью с кричащим названием "SQL за 20 минут". К...
admin
20 октября 2016

27 сайтов с задачками для оттачивания навыков программирования

<strong>Решение задач — хороший способ развить навыки разработки.</strong>