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

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

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

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

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

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

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

Источник