LINUX.ORG.RU

Как можно было бы контролировать пересекаемость интервалов времени?

 


0

1

Здравствуйте уважаемые жители страны ЛОР!

Есть некоторая задачка, к которой я пока не пойму как подступиться...

Немного терминологии

Интервал - это некая запись в «БД» имеющая два свойства: дата/время начала и дата/время окончания:

2012-09-05 12:34:08 - 2012-09-05 15:07:33

«БД» в кавычках, потому что пока нет никакой определённости будет ли она в реальности СУРБД или плоским файлом или еще чем. В каком формате записывается дата/время, всё в тумане.

Пока я только экспериментирую, и сделал табличку в MySQL где есть три поля: intervalID (autoincrement), intervalStart (unixtime) и intervalStop (unixtime).

Немного рассуждений

Есть (точнее её еще нет) некая программа, которая учитывает интервалы времени.

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

В течении некоего времени этот дядька может учесть несколько интервалов. Он записывает эти интервалы в базу. Дядька очень строгий и никогда не позволит чтобы учитываемые интервалы наложились друг на друга полностью или частично.

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

Выглядит это примерно так:

...
218 - 2012-09-03 01:34:08 - 2012-09-03 01:42:31
219 - 2012-09-03 01:54:12 - 2012-09-03 01:59:42
220 - 2012-09-03 02:18:22 - 2012-09-03 02:25:21
221 - 2012-09-03 02:27:03 - 2012-09-03 04:41:13
222 - 2012-09-03 06:45:58 - 2012-09-03 06:46:22
...

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

Например. Если предыдущий интервал времени закончился в 2012-09-03 02:25:21, то следующий не может начаться в 2012-09-03 02:24:01. Ну вот, вроде объяснил, и даже сам понял что объяснял :)

Теперь собственно сложный момент

Однако, возможна ситуация, когда дядька с таймером не выполнил свою работу. То ли он не получил команды, то ли обленился... Однако возникла необходимость внести в базу некий интервал «задним числом». Это будет делать тётя Маша - пользователь. Для тёти Маши будет подготовлен красочный и функциональный интерфейс, где она посредством несложных манипуляций мыши и/или клавиатуры сможет ввести новый интервал задав точки его начала и окончания.

Конечно тёте Маше будет показано, какие интервалы в базе существуют на данный момент. Править эти интервалы тётя Маша не умеет, не хочет и страшно боится. Но записать новый интервал - это всегда пожалуйста.

Однако, тётя Маша человек, и ей, как и всем нам свойственны ошибки.

Необходимо проконтролировать работу тёти Маши. И ни в коем случае не позволить ей ввести новый интервал, который бы каким-либо образом пересекся (наложился) с уже имеющимся интервалом. Тётя Маша может вводить только интервалы, которые лягут строго между двумя соседними по времени.

Конечно было бы интересно найти решение в виде SQL-запроса. Но подойдут и любые другие варианты. Например можно выбрать из базы все варианты одного дня с вводимым интервалом и произвести валидацию каким-нибудь хитрым алгоритмом. Пока рассматриваю способы не учитывающие возможность множественной правки базы, т.е. если с программой одновременно решили воспользоваться тётя Маша, тётя Даша и новенькая девушка Ира :) Пусть, условно, тётя Маша единственный и неповторимый пользователь.

Собственно вопрос

Какие могут быть варианты валидации вводимого интервала на предмет пересечения с имеющимися в базе?
Рассматриваем любые варианты, от идеального до самых безумных :)

P.S.: Прошу прощения за многословность. Эта задачка вращается у меня в фоне уже некоторое время, а взяться за нее всерьез никак не могу, вариантов вроде не нащупал дельных. Видимо она там в подсознании уже произвела некоторую свалку. Выговорился и легче стало, как будто на кушетке у психолога побывал :)

P.P.S.: Кстати, вроде кое-что придумал в процессе. Надо будет проверить, если получится - отпишусь.

Ситуация: тётя Маша внесла заведомо неверные данные. Что должна сделать программа в этом случае? Один вариант - выкинуть ошибку; второй - автоматически скорректировать данные к ближайшим валидным.

Delirium_veritas ()
Ответ на: комментарий от Delirium_veritas

Программа должна выкинуть ошибку. Никаких интеллектуальных действий не нужно. Это просто программа учёта, а тётя Маша опытный учётчик :)

Munhgauzen ()

Ааааа, рождается мысль!

Когда тётя Маша хочет ввести новый интервал, она же уже знает какой, правильно? Значит надо сделать первый этап ввода, когда она выбирает промежуток в который хочет добавить интервал. А уж потом второй этап, когда она вводит точное время. Тогда наверное проверять будет проще.

Чёрт побери. Надо было давно этот пост написать :) Думаю дальше. Да и утро видимо сказывается...

Munhgauzen ()

Перекрытие интервалов - это если начало и/или конец вводимого интервала попадает в любой другой интервал. Вот и проверяй. На оракле будет выглядеть примерно так:

for i in (select * from intervals where inbdate between bdate and edate or inedate between bdate and edate) loop
	-- Ошибка
end loop;
bdate и edate - поля таблицы, содержащие начало и конец интервала. inbdate и inedate - обозначают новый интервал. Оформить можно в виде процедуры, триггера или вообще записать в виде констреинтов.

winlook38 ★★ ()
Ответ на: комментарий от Munhgauzen

В моём варианте не надо такой проверки. Просто, если в результате запроса есть хоть одна строка - значит тётя Маша накосячила. Если интервал верен, то в результате вернётся 0 строк.

Delirium_veritas ()

Наверное можно выделить два подхода к этой задаче.

Первый - это создание сложного суперинтеллектуального алгоритма проверки. Это когда тётя Маша вводит два момента времени с календарика.

И второй - может быть стоит создать что-то вроде «мастера», который разобьёт процедуру ввода нового интервала на несколько этапов, и проведет по ним тётю Машу не дав ей совершить ошибку.

Munhgauzen ()
Ответ на: комментарий от Munhgauzen

Равноценно - применить сложный валидатор на проверку всего набора значений или разбить этот валидатор на пачку простых условий и применять их по мере ввода данных.

Delirium_veritas ()

Переформулируй условие так: если есть хоть одно пересечение, то существует хотя бы одно значение из базы (начальное или конечное), лежащее внутри добавляемого интервала.
Соответствующий SQL-запрос (проверяется пуст/непуст) тривиален, хотя, может быть и неэффективен.
А тёте Маше лучше не просто показать существующие интервалы, а предложить на выбор в качестве начальных значений список из интервалов-дополнений, с возможностью только сужать интервал.

ABW ★★★★★ ()
Ответ на: комментарий от Delirium_veritas

Ага, спасибо, есть пища для тестов. Буду пробовать.

P.S.: Но предложения еще принимаются :)

Munhgauzen ()
Ответ на: комментарий от ABW

Переформулируй условие так: если есть хоть одно пересечение, то существует хотя бы одно значение из базы (начальное или конечное), лежащее внутри добавляемого интервала.

Тоже мысль, спасибо!

Munhgauzen ()

Чего-то я не пойму, зачем эта стена текста и полёт фантазии? Проверяй при добавлении что начало или конец добавляемого не лежит между остальными промежутками и всё.

Kalashnikov ★★★ ()

Чорт, а я все время думал, что ТС адекватен. Может тебе выспаться надо, отдохнуть?

anonymous ()
Ответ на: комментарий от anonymous

Может тебе выспаться надо, отдохнуть?

Некагда, насяльника!

Munhgauzen ()
Ответ на: комментарий от Munhgauzen

Конечно прикольно реализовать проверку интервала через CONSTRAINT CHECK или RANGE TYPE и т.д. но при этом тебе все равно придется потом ответить на вопрос: как только Маша первый раз ошибется, тебя попросят добавить вывод в каком именно значение она ошиблась и с каким интервалом он пересеклась, т.к. вдруг он тоже был введен ей же и она ошиблась еще раньше и по этому надо будет сделать возможность редактирования ранее введенных интервалов. Так что скорее всего надо реализовать самую простую перебиралку интервалов, ну и если интервалом много для ускорения поиска и уменьшения размера можно подумать над разделение поля записи интервала на сутки,месяца,года и т.д.

alnkapa ()

У тебя ровно 2 (два) контрольных случая:

  1. Маша вводит MASHA_START (MASHA_STOP еще неизвестен)
    выбираешь все такие записи, у которых
    intervalStart <= MASHA_START < intervalStop
    
    если существует хоть одна такая запись — ERROR

  2. Маша вводит MASHA_STOP (MASHA_START успешно прошло предыдущую проверку)
    выбираешь все такие записи, у которых
    MASHA_START <= intervalStart < MASHA_STOP
    
    если существует хоть одна такая запись — ERROR

Примечание:

  • допускается
    intervalStop  == MASHA_START
       MASHA_STOP == intervalStart
    
  • не допускается
    intervalStart == MASHA_START
    
anonymous ()
Ответ на: комментарий от alnkapa

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

Всё возможно в этом подлунном мире. Детализацию работы оператора тоже еще предстоит рассмотреть и запротоколировать.

если интервалом много для ускорения поиска и уменьшения размера можно подумать над разделение поля записи интервала на сутки,месяца,года

В MySQL есть богатый набор функций для работы с типом даты-времени. Наверное можно будет положиться на таковую и в других SQL-серверах.

Тем не менее спасибо! Ценное замечание.

Munhgauzen ()
Ответ на: комментарий от anonymous

Поэтапный мастер ввода скорее всего придется делать, как один из вариантов ввода.

Munhgauzen ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.