Структура данных для неналожения диапазонов в единственном размере

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

(RoomId, StartTime)

В случае непрерывных диапазонов обязательно необходимо сохранить 2 вещи, одну границу и или вторая граница или длина. Это обычно делается путем хранения второй границы и затем создания ограничения на обе границы вида

(boundary not between colBoudaryA and colBoundaryB)

с дополнительным ограничением это

(startBoundary < endBoundary)

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

RoomID
ReservationID
PreviousReservationID
NextReservationID
StartTimeDate
EndTimeDate
Priority
UserID

Приоритет и UserID позволяют, чтобы расписания имели приоритеты (у преподавателя могло бы быть больше удара, чем студенческая группа) так, чтобы новый объект мог 'выбить' более низкие приоритетные объекты из пути во время вставки, и UserID позволяет электронному письму быть отправленным в ударенных организаторов встречи.

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

- Adam

Много зависит от того, что Вы будете делать с данными, и поэтому какие операции должны быть эффективными. Однако я рассмотрел бы двунаправленный связанный список Диапазонов с логикой в методах set Запуска и Конца проверке, перекрывает ли это теперь своих соседей, и уменьшать их раз так (или выдавать исключение, или однако Вы хотите обработать предпринятое перекрытие).

Это дает хороший простой связанный список заказанных периодов для чтения, но никакой контейнер, ответственный за поддержание правила без перекрытий.

Это называют "Унарным Ресурсом" ограничением в мире Программирования с использованием ограничительного языка. Существует большое исследование в этой области, специально для случая, когда времена события не фиксируются, и необходимо найти временные интервалы для каждого из них. Существует коммерческий пакет C++, который делает Вашу проблему и больше CP Ilog, но это - вероятное излишество. Существует также версия несколько с открытым исходным кодом, названная затмением (никакое отношение к IDE).

Это нетривиально, потому что (в мире базы данных) необходимо сравнить несколько строк для определения неперекрывающихся диапазонов. Очевидно, когда информация находится в памяти, затем другие представления, такие как списки в порядке времени возможны. Я думаю, тем не менее, что Вы были бы лучше всего выключены с Ваш, 'запускаются + конец' нотация, даже в списке.

Существуют целые книги по предмету - часть 'Временной Базы данных' обработка. Два Вы могли посмотреть на, Дарвен, Date и Lorentzos "Временные Данные и Реляционная модель" и (в радикально другом экстремальном значении) "Разработка, Ориентированная на время на Приложения базы данных в SQL", Richard T. Snodgrass, Morgan Kaufmann Publishers, Inc., Сан-Франциско, июль 1999, 504+xxiii страницы, ISBN 1-55860-436-7. Это распродано, но доступно как PDF на его веб-сайте по cs.arizona.edu (таким образом, поиск Google делает довольно легким найти).

Одна из соответствующих структур данных, я верю, R-дерево. Это часто используется для 2-мерных структур, но может также быть эффективно для 1-мерных структур.

Можно также искать "Отношения Allen" для интервалов - они могут быть полезны Вам.

Я успешно запомнил время начала и продолжительность. Тест на перекрытие был бы чем-то вроде

WHERE NOT EXISTS (
   SELECT 1 FROM table
   WHERE BeginTime < NewBeginTime AND BeginTime + Duration > NewBeginTime
)
AND NOT EXISTS (
   SELECT 1 FROM table
   WHERE NewBeginTime < BeginTime AND NewBeginTime + NewDuration > BeginTime
)

, думаю, без тестирования, но, надеюсь, вы получите дрейф

1. Для неперекрывающихся интервалов вы можете просто отсортировать интервалы по начальной точке. Когда вы добавляете новый интервал в эту структуру, вы можете просто проверить, что начальная и конечная точки не принадлежат этому набору интервалов. Чтобы проверить, принадлежит ли некоторая точка X набору интервалов, вы можете использовать двоичный поиск, чтобы найти ближайшую начальную точку и проверить, принадлежит ли X этому интервалу. Этот подход не так оптимален для операций модификации.

2. Вы можете посмотреть структуру Дерево интервалов - для неперекрывающихся интервалов оно имеет оптимальные операции запроса и изменения.