SQL Server: упаковываем интервалы с приоритетами
Содержание:
1.Постановка задачи (Вы читаете данный раздел);
2. Шаг 1 ;
3. Шаг 2, 3;
4. Шаг 4 и оптимизация решения с использованием APPLY.
Одна из монументальных задач, которую может предложить T-SQL, - упаковка интервалов. Ее решение сводится к совмещению ряда пересекающихся интервалов в один сплошной (непрерывный). Впрочем и здесь есть свои нюансы, которые мы рассмотрим на примере задачи, которую мне прислал один из читателей NH.
«Здравствуйте. Существуют две таблицы - Users и Sessions. Мне необходимо определить непрерывные периоды с активными сеансами для каждого пользователя. При этом каждому интервалу назначен приоритет. Например, рассмотрим интервал для User 2 от 08.00 до 10.30. Предположим, что интервал
• от 08.00 до 10.30 имеет приоритет 3;
• от 08.30 до 10.00 имеет приоритет 2;
• от 09.00 до 09.30 имеет приоритет 1.
Приоритет 1 — высший или самый важный.
После объединения результат будет следующим:
• 08.00—08.30, приоритет 3;
• 08.30—09.00, приоритет 2;
• 09.00—09.30, приоритет 1;
• 09.30—10.00, приоритет 2;
• 10.00—13.30, приоритет 3.
Я перепробовал много способов, и все безуспешно. Что вы можете посоветовать?»
Как выяснилось, предложенная задача весьма сложная, но одновременно очень интересная. В этой статье я представлю свое решение, но, как всегда, рекомендую сначала попытаться решить ее самостоятельно. Предупреждаю: мне пришлось потратить несколько дней на поиск эффективного решения. Я много часов размышлял над графическим представлением задачи и желаемого результата. Но усилия мои не были напрасны.
Тестовые данные и желаемый результат
Воспользуйтесь программным кодом, представленным ниже, чтобы создать таблицы Users и Sessions со вспомогательными индексами и заполнить их малым набором тестовых данных.
DDL и малый набор тестовых данных
Интервалы в таблице Sessions — закрыто-открытые интервалы, то есть значение starttime включается, а значение endtime исключается. Условная запись таких интервалов следующая: [starttime, endtime). Квадратная скобка представляет закрытый ограничитель (включающий), а круглая скобка представляет открытый ограничитель (исключающий).
Графическое представление входных данных и желательные выходные данные для User2
В качестве примера на рисунке выше дано графическое представление входных данных и желательные выходные данные для User2.
Пока не обращайте внимания на голубоватые значения ptybitmap; они являются частью решения, я объясню их позже. Как показано в средней части рисунка, предполагается упаковывать группы пересекающихся интервалов с одинаковым приоритетом. Например, обратите внимание, что четыре входных интервала, активные в период с 11:00 до 13:00, преобразуются в два упакованных интервала. Как мы видим в нижней части рисунка, при наличии перекрывающихся сегментов упакованных интервалов с различными приоритетами следует возвратить сегмент с самым высоким приоритетом (наименьшим целочисленным значением). Как и в приведенном примере читателя, обратите внимание, что входные данные содержат три интервала в период с 8:00 до 10:30:
Эти входные интервалы преобразуются в следующие выходные интервалы:
Желаемый результат для малого набора тестовых данных
В таблице (см. выше) содержится полный желаемый результат для малого набора тестовых данных.
Вспомогательная функция GetNums
После того как будет найдено рабочее решение, нужно проверить его, сравнив результат с желаемым в таблице выше. Чтобы протестировать эффективность решения, потребуется более крупный набор тестовых данных. Выполните программный код, показанный в коде выше 2, чтобы создать вспомогательную функцию GetNums, а программный код, представленный ниже, заполняет таблицы более крупным набором тестовых данных.
Большой набор тестовых данных
Теперь у вас есть все необходимое, чтобы приступить к решению задачи. Желаю успеха!
Далее я изложу свое решение в четырех шагах.
1.
2. Шаг 1 ;
3. Шаг 2, 3;
4. Шаг 4 и оптимизация решения с использованием APPLY.
Одна из монументальных задач, которую может предложить T-SQL, - упаковка интервалов. Ее решение сводится к совмещению ряда пересекающихся интервалов в один сплошной (непрерывный). Впрочем и здесь есть свои нюансы, которые мы рассмотрим на примере задачи, которую мне прислал один из читателей NH.
«Здравствуйте. Существуют две таблицы - Users и Sessions. Мне необходимо определить непрерывные периоды с активными сеансами для каждого пользователя. При этом каждому интервалу назначен приоритет. Например, рассмотрим интервал для User 2 от 08.00 до 10.30. Предположим, что интервал
• от 08.00 до 10.30 имеет приоритет 3;
• от 08.30 до 10.00 имеет приоритет 2;
• от 09.00 до 09.30 имеет приоритет 1.
Приоритет 1 — высший или самый важный.
После объединения результат будет следующим:
• 08.00—08.30, приоритет 3;
• 08.30—09.00, приоритет 2;
• 09.00—09.30, приоритет 1;
• 09.30—10.00, приоритет 2;
• 10.00—13.30, приоритет 3.
Я перепробовал много способов, и все безуспешно. Что вы можете посоветовать?»
Как выяснилось, предложенная задача весьма сложная, но одновременно очень интересная. В этой статье я представлю свое решение, но, как всегда, рекомендую сначала попытаться решить ее самостоятельно. Предупреждаю: мне пришлось потратить несколько дней на поиск эффективного решения. Я много часов размышлял над графическим представлением задачи и желаемого результата. Но усилия мои не были напрасны.
Тестовые данные и желаемый результат
Воспользуйтесь программным кодом, представленным ниже, чтобы создать таблицы Users и Sessions со вспомогательными индексами и заполнить их малым набором тестовых данных.
DDL и малый набор тестовых данных
Интервалы в таблице Sessions — закрыто-открытые интервалы, то есть значение starttime включается, а значение endtime исключается. Условная запись таких интервалов следующая: [starttime, endtime). Квадратная скобка представляет закрытый ограничитель (включающий), а круглая скобка представляет открытый ограничитель (исключающий).
Графическое представление входных данных и желательные выходные данные для User2
В качестве примера на рисунке выше дано графическое представление входных данных и желательные выходные данные для User2.
Пока не обращайте внимания на голубоватые значения ptybitmap; они являются частью решения, я объясню их позже. Как показано в средней части рисунка, предполагается упаковывать группы пересекающихся интервалов с одинаковым приоритетом. Например, обратите внимание, что четыре входных интервала, активные в период с 11:00 до 13:00, преобразуются в два упакованных интервала. Как мы видим в нижней части рисунка, при наличии перекрывающихся сегментов упакованных интервалов с различными приоритетами следует возвратить сегмент с самым высоким приоритетом (наименьшим целочисленным значением). Как и в приведенном примере читателя, обратите внимание, что входные данные содержат три интервала в период с 8:00 до 10:30:
Эти входные интервалы преобразуются в следующие выходные интервалы:
Желаемый результат для малого набора тестовых данных
В таблице (см. выше) содержится полный желаемый результат для малого набора тестовых данных.
Вспомогательная функция GetNums
После того как будет найдено рабочее решение, нужно проверить его, сравнив результат с желаемым в таблице выше. Чтобы протестировать эффективность решения, потребуется более крупный набор тестовых данных. Выполните программный код, показанный в коде выше 2, чтобы создать вспомогательную функцию GetNums, а программный код, представленный ниже, заполняет таблицы более крупным набором тестовых данных.
Большой набор тестовых данных
Теперь у вас есть все необходимое, чтобы приступить к решению задачи. Желаю успеха!
Далее я изложу свое решение в четырех шагах.
