Обнаружение наличия пересечений в интервалах — классическая задача, в которой, имея под рукой таблицу с набором интервалов, требуется проверить наличие пересечений. Часто это делается для того, чтобы проверить допустимость данных, содержащих интервалы, для которых не предполагается пересечений. Например, если вы ведете журнал изменений в строках, сохраняя несколько версий строки, та же строка не должна иметь пересекающихся версий. В данной статье сначала будет описано классическое решение задачи и даны пояснения, почему я считаю его несостоятельным, а затем предложено более эффективное решение.

В моем примере используется таблица, именуемая Intervals, со столбцами keycol, low и high. В обоих предложенных решениях с успехом используется индекс (low, high, keycol). Low и high — целочисленные столбцы, представляющие собой разделители интервалов. На практике вы, вероятно, работаете в основном с разделителями даты и времени, а не с целыми числами, но предлагаемые решения будут работать в любом случае. Интервалы в моей таблице закрыто-открытые, то есть ограничитель low инклюзивный, а ограничитель high — эксклюзивный.

Наша задача заключается в том, чтобы подготовить запрос, который возвращает 1, если в данных существуют пересечения, и 0 — в противном случае. Пересечения существуют, если имеется хотя бы два интервала Iw и Iz, в которых Iw.low < Iz.high и Iw.high > Iz.low. Например, интервалы (10, 20) и (19, 21) пересекаются, как и (10, 20), (15, 15). Последний интервал называется вырожденным (low = high). Однако интервалы (10, 20) и (20, 30) не пересекаются.

Тестовые данные

Чтобы заполнить таблицу Intervals тестовыми данными, используется вспомогательная функция, именуемая GetNums, которая формирует последовательность целых чисел в указанном диапазоне. Для создания функции используйте программный код листинга 1.

Выполните программный код листинга 2, чтобы создать таблицу Intervals вместе с поддерживающим индексом.

Далее воспользуемся программным кодом листинга 3, чтобы заполнить таблицу нужным количеством непересекающихся интервалов.

Этот программный код заполняет таблицу сначала 10 000 интервалов, но вы можете протестировать решения с различными размерами таблиц. Используйте программный код, приведенный в листинге 4, чтобы запросить выборку из 10 строк из таблицы.

Этот программный код формирует выходные данные, показанные на экране 1.

 

Выходные данные запроса 10 строк
Экран 1. Выходные данные запроса 10 строк

 

Обратите внимание, что я использую тестовые данные с непересекающимися интервалами для тестирования производительности в худшем случае. Чтобы проверить правильность решения, имеющего целью обнаружение наличия пересечений, добавьте пересекающийся интервал с помощью программного кода листинга 5.

Впоследствии вы можете использовать следующий программный код, чтобы удалить пересекающийся интервал:

DELETE FROM dbo.Intervals WHERE
   keycol = 2147483647;

Традиционное решение

В традиционном решении (назовем его решением 1) используется два предиката EXISTS. Внутренний предикат EXISTS с вложенным запросом идентифицирует интервалы, пересекающиеся с другими интервалами. Внешний предикат EXISTS проверяет, возвращает ли внутренний запрос хотя бы один интервал, пересекающийся с другими интервалами. Программный код дает псевдоним I1 внешнему экземпляру таблицы...

Это не вся статья. Полная версия доступна только подписчикам журнала. Пожалуйста, авторизуйтесь либо оформите подписку.
Купить номер с этой статьей в PDF