Вычисление пересекающихся интервалов в линейных, и замкнутых системах счисления

Здравствуйте! И сразу прошу прощение, за слишком мудрёное название, но оно наиболее полно отражает излагаемый ниже материал.

Я думаю многие из вас сталкивались с необходимостью вычисления пересекающихся интервалов. Но задача с которой я столкнулся на днях — оказалась не столь тривиальной. Но, обо всем по порядку.

Вычисление пересекающихся интервалов в линейной системе счисления

Если у вас уже есть представление о пересечении интервалов, то пройдите сразу сюда ^[1].

Вычисление пересечений временных интервалов (отрезков времени) на прямой линии времени не составляет особого труда. Мы можем условно иметь пять видов временных пересечений.
Обозначим один отрезок времени как " ", а другой "/ /"

1. Смещение вперед по оси времени "/ / "
2. Смещение назад по оси времени " / /"
3. Вхождение " / / "
4. Поглощение " / / "
5. Совпадение «X X»

Таким образом, мы можем выразить каждое конкретное пересечение с помощью знаков <, > и =. А имея в арсенале знаки <= и >= мы можем сократить количество шаблонов для вычисления до четырех (срастив, таким образом, «вхождение» и «совпадение» либо «поглощение» и «совпадение» или даже «смещние» и «совпадение»). Кроме того, либо «вхождение» либо «поглощение»(но не то и другое вместе) можно также упразднить, считая его частным случаем «смещения».
Итак, имея таблицу вида:

Для выборки из таблицы всех пользователей пересекающих заданный интервал (допустим 4-8), используем запрос:

SET @start:=4;
SET @end:=8;
SELECT * FROM `table`
WHERE
(`start` >= @start  AND `start` < @end)  /*смещение вперед*/
OR
(`end` <= @end AND `end` > @start)  /*смещение назад*/
OR
(`start` < @end AND `end` > @start) /*вхождение - на самом деле здесь не обязательно оно обработается одним из предыдущих выражений*/
OR
(`start` >= @start AND `end` <= @end)/*поглощение и совпадение*/

Данный запрос вернет первого, второго и третьего пользователей. Всё довольно просто.

Хм. А что если нужно выбрать непересекающиеся интервалы?
На самом деле всё еще проще: в отличии от пересечения, случаев НЕпересечения всего два:

• Смещение назад " / /"
• Смещение вперед "/ / "

а на непрерывной линии времени нам нужно лишь проверить меньше ли конец одного интервала, чем начало другого.
А занчит SQL запрос сводится к

SET @start:=4;
SET @end:=8;

SELECT * FROM `table`
WHERE
`start` >= @end  OR `end` <= @start  /*оба случая смещения*/

И вот тут мы вспоминаем про отрицания выражений. Если вычислять непересечения намного проще чем пересечения, то почему бы просто не отбросить все непересечения?

WHERE 
NOT ( `start` >=  @end  OR `end` <= @start  )

Вуа-ля! Все намного лаконичнее!

Всё это очень прекрасно, и замечательно работает… пока линия времени прямая.

Вычисление пересекающихся интервалов в замкнутых системах счисления

С вычислениями на линии времени мы разобрались. Так что же такое «замкнутая» система счисления?

Предположим, что у нас есть таблица с расписанием графика работы (пусть это будет круглосуточный колл-центр):
*минуты «00» опущены для простоты выражений

Я работаю с 10 до 19 и хочу знать какие именно работники будут пересекать мой график работы.
Делаем выборку, заданной ранее схеме:

SET @start:=10;
SET @end:=19;
SELECT * FROM `table`
WHERE 
NOT ( `start` >=  @end  OR `end` <= @start )

Все отлично! Я получил данные трёх работников, чей интервал пересекается с моим.

Ок, а если я работаю в ночь? Допустим с 20 до 6? То есть начало моего интервала больше его конца. Выборка из таблицы по этим условиям вернет полную ахинею. То есть крах случается, когда мой временной интервал пересекает «нулевую» отметку суток. Но ведь и в базе могут хранится интервалы пересекающие «нулевую» отметку.
С подобной проблемой я столкнулся два дня назад.

Проблема выборки интервалов по линейной методике из таблицы с данными нелинейной структуры была на лицо.
Первое, что мне пришло в голову — это расширить пространство суток до 48 часов, тем самым избавляясь от «нулевой» отметки. Но эта попытка потерпела крах — потому что интервалы между 1 и 3 никак не могли попасть в выборку между 22 и 27(3).

Я предпринял попытку найти решение этой проблемы в интернете. Информации по пересечению интервалов на «линейном» времени было сколько угодно. Но то ли этот вопрос не имел широкого обсуждения, то ли гуру SQL держали решение «для себя» — решения по замкнутой системе нигде небыло.

В общем, поспрашивав на форумах советов от гуру, я получил решение: нужно было разбить пересекающие «ноль» интервалы на две части, тем самым получив два линейных интервала, и сравнивать их оба с интервалами в таблице (которые тоже нужно было разбить на две части, если они пересекают ноль). Решение работало и вполне стабильно, хоть и было громоздким. Однако меня не покидало ощущение, что всё «намного проще».
И вот, выделив пару часов для этого вопроса, я взял тетрадь и карандаш… Привожу то, что у меня получилось:

Суть в том, что сутки — есть замкнутая линия времени — окружность.
А временные интервалы — суть дуги этой окружности.
Таким образом, мы для отрицания непересечений (см. первую часть поста), можем построить пару схем непересечения:

В первом случае мы имеем обычную линейную схему для отрицания непересечений. Во втором одна из дуг пресекает «нулевую» отметку. Есть и третий случай, который можно сразу принять как пересечение ( без отрицаний непересечения ): Оба интервала пересекают «нулевую» отметку, а значит пересекаются по определению. Кроме того, есть еще два случая, когда интервалы (вводимый и взятый из таблицы) «меняются» местами.
Немного наколдовав с базой (где-то даже методом высоконаучного тыка), мне удалось собрать вот такой запрос:

SET @start:= X ;
SET @end:= Y;

SELECT * FROM `lparty_ads`
	WHERE
	((`prime_start` < `prime_end` AND @start < @end) 
		AND  NOT (`prime_end`<= @start AND  XOR  @end <=`prime_start` )
 	OR 
	(( (`prime_start` < `prime_end` AND @start > @end) OR (`prime_start` > `prime_end` AND @start < @end))
		AND NOT 
		( `prime_end` <= @start AND @end <= `prime_start` ))
	OR (`prime_start` > `prime_end` AND @start > @end))

Запрос вполне работоспособен и, что самое забавное, справедлив для любых замкнутых систем счисления — будь то час, сутки, неделя, месяц, год. А еще, этот метод не использует «костылей», вроде дополнительных полей.

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

Автор: greabock

Источник ^[2]