Каков эффективный алгоритм для редактирования «графика» наиболее эффективно?

Question

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

EDIT: Как я уже говорил, я значительно укрепил вопрос.

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

У меня также есть вторая таблица (таблица B), которая использует идентификатор из таблицы A в качестве внешнего ключа.

Запись из таблицы А, соответствующая таблица B будет иметь промежуток времени, который вбирает промежутка времени из таблицы B. Не все записи в таблице A будут иметь запись в таблице B.

I 'm предоставляет интерфейс для пользователей, чтобы редактировать расписание ресурсов в таблице A. Они в основном предоставляют новый набор данных для таблицы A, которые мне нужно рассматривать как diff из версии в БД.

Если они полностью удаляют объект из таблицы A, на который указывает таблица B, я хочу также удалить запись из таблицы B.

Таким образом, учитывая следующие 3 комплекта:

• исходные объекты из таблицы А (из БД)
• исходные объекты из таблицы B (из БД)
• Отредактированное набор объекты из таблицы А (со стороны пользователя, так что никаких уникальных идентификаторов)

мне нужен алгоритм, который будет:

• Оставьте строки в таблице A и таблице B нетронутыми, если для этих объектов не требуются изменения.
• Добавьте строки в таблицу A по мере необходимости.
• При необходимости удалите строки из таблицы A и таблицы B.
• При необходимости измените строки в таблице A и таблице B.

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

Опять же, пожалуйста, ответьте, как конкретно или вообще, как вам нравится, я ищу советы, но если кто-то имеет полный алгоритм, который бы просто сделать мой день. :)

EDIT: В ответ на lassvek, я обеспечиваю некоторые дополнительные детали:

элементы таблицы Б всегда полностью содержится в таблице А элементов, а не только перекрытия.

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

Например (использовать сокращенную):

 
Table A 
ID Resource Start   End 
01 Resource A 10/6 7:00AM 10/6 11:00AM 
02 Resource A 10/6 1:00PM 10/6 3:00PM 

Table B 
ID Table_A_ID Start   End 
01 02   10/6 1:00PM 10/6 2:00PM 

Так что я хочу следующее поведение:

• Если удалить ID 02 из таблицы А, или сократить его до 2:00 вечера - 3:00 PM, я должен удалить ID 01 из таблицы B.
• Если я разворачиваю таблицу A ID 01 туда, где она заканчивается в 1:00 вечера, эти две записи должны быть объединены в один ряд, а таблица B ID 01 должен теперь указывать на идентификатор таблицы A 01.
• Если я удалю 8:00 AM-10:00AM из таблицы A ID 01, эта запись должна быть разделена на две записи: одна для 7:00 AM-8:00AM и новая запись (ID 03) для 10 : 00 am-11: 12 утра.

Answer 1

Я много работал с периодами, но я боюсь, что я не совсем понимаю, как таблицы А и Б работают вместе, возможно, это слово подводить, что я не понимаю.

Можете ли вы привести конкретные примеры того, что вы хотите сделать?

Вы имеете в виду, что временные регионы, записанные в таблице A, содержат полностью временные интервалы в таблице B, например?

|---------------- A -------------------| 
    |--- B ----|  |--- B ---| 

или перекрытия с?

|---------------- A -------------------| 
|--- B ----|      |--- B ---| 

или обратный путь, временные интервалы в B содержат/перекрываются с A?

Скажем, это первый один, где timespans в B внутри/так же, как связанный временный интервал в таблице А.

Означает ли это, что:

* A removed A-timespan removes all the linked timespans from B 
* An added A-timespan, what about this? 
* A shortened A-timespan removes all the linked timespans from B that now falls outside A 
* A lenghtened A-timespan, will this include all matching B-timespans now inside? 

Вот пример:

|-------------- A1 --------------| |-------- A2 --------------| 
    |---- B1 ----| |----- B2 ---|  |---- B3 ----| |-- B4 --| 

, а затем вы удлинить A1 и сократить и двигаться A2, так что:

|-------------- A1 ---------------------------------| |--- A2 --| 
    |---- B1 ----| |----- B2 ---|  |---- B3 ----| |-- B4 --| 

это означает, что вы хотите изменить данные, как это:

1. Lengthen (update) A1 
2. Shorten and move (update) A2 
3. Re-link (update) B3 from A2 to A1 instead 

как об этой модификации A1 удлиняется, но не достаточно, чтобы содержать B3 полностью, и А2 перемещается/укоротить таким же образом:

|-------------- A1 -----------------------------|  |--- A2 --| 
    |---- B1 ----| |----- B2 ---|  |---- B3 ----| |-- B4 --| 

Поскольку B3 теперь не полностью находится внутри A1 или A2, удалите его?

Мне нужны конкретные примеры того, что вы хотите сделать.

---

Редактировать Другие вопросы

Хорошо, как насчет:

|------------------ A -----------------------| 
    |------- B1 -------| |------- B2 ------| 
          |---|     <-- I want to remove this from A 

что по этому поводу?

Либо:

|------------------ A1 ----| |---- A2 -----| 
    |------- B1 -------| |B3| |--- B2 ---| 

или:

|------------------ A1 ----| |---- A2 -----| 
    |------- B1 -------| 

Итак, как я это вижу, с вопросами, до сих пор:

• Вы хотите быть в состоянии сделать следующее операции на А
  • Сокращенно
  • удлиняет
  • комбината, когда они являются смежными, сочетающий в себе два или более в один
  • пробивки отверстий в них путем удаления периода, и, таким образом, разделив его
• B о том, что все еще содержится внутри после обновления выше, перелинковать при необходимости
• в том, что содержались, но которые теперь полностью снаружи, удалить их
• Б, которые содержались, но теперь частично снаружи, Изменить: Удалить эти, реф целостности данных
• Для всех вышеуказанных операций, не наименьшую минимальную работу, необходимую для приведения данных в соответствии с операциями (вместо того, чтобы просто удалить все и вставить заново)

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

---

Редактировать Вот удар в алгоритме.

1. Оптимизация новый список первых
2. «объединить» этот список основных периодов в базе данных следующим образом (т.е. объединить смежные периоды и т.д..):
   1. уследить, где в обоих списках (т.е.новый и существующий), вы являетесь
   2. , если текущий новый период полностью до текущего текущего периода, добавьте его, затем перейдите к следующему новому периоду
   3. , если текущий новый период полностью после текущего существующего периода, удалите существующий период и все его дочерние периоды, затем перейдите к следующему существующему периоду
   4. , если эти два совпадения, отрегулируйте текущий существующий период, равный новому периоду, следующим образом, затем перейдите к следующему новому и существующему период
      1. если новый период начинается до начала периода, просто переместите начало
      2. , если новый период начинается после существующего периода, проверьте все дочерние периоды в разностной период, и помните их, а затем перенести начало
      3. сделать то же самое с другим концом
3. с любым периоды, которые вы «запомнили», посмотреть, нужно ли их пересадить или удалить.

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

Answer 2

Вы публикуете почти в категории «слишком долго, не читал» - сокращение будет, вероятно, даст вам больше отзывов.

Во всяком случае, на тему: вы можете попробовать смотришь на то, что называется "Interval Algebra"

Answer 3

Как я вас понимаю, пользователи могут только непосредственно влияют на таблицу А. Предполагая, что вы программируете на C#, вы можете использовать простой ADO. Net DataSet для управления изменениями в таблице A. TableAdapter знает, чтобы оставить нетронутые строки в одиночку и соответствующим образом обрабатывать новые, измененные и удаленные строки.

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

Единственный случай, который не обрабатывается подобным образом, если период, в таблице А укорочена S.T. он больше не относится к соответствующей записи в таблице B. Вы можете просто проверить этот случай в хранимой процедуре обновления или альтернативно определить триггер обновления в таблице A.

Answer 4

Мне кажется, что любой алгоритм для этого будет включать пропуск через NewA, соответствующий ResourceID, StartTime и EndTime, и отслеживать, какие элементы из OldA попадают. Затем у вас есть два набора несоответствующих данных, UnmatchedNewA и UnmatchedOldA.

Проще всего я могу придумать, чтобы продолжить, в основном, начать с них: Напишите все UnmatchedNewA в базу данных, передайте элементы B из UnmatchedOldA в новые ключи (только сгенерированные), где это возможно, удалив, когда нет , Затем уничтожьте все UnmatchedOldA.

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

---

Это невозможно знать, делает ли это окончательное предложение смысла не более фона, но на случай, если вы не думали об этом так:

Вместо прохождения всего Коллекция назад и вы могли бы использовать прослушиватели событий или что-то подобное обновлению модели данных только там, где необходимы изменения?Таким образом, изменяемые объекты смогут определять, какие операции БД требуются «на лету».

Answer 5

Предлагаю вам разобрать ваши вопросы на два отдельных: Первым должно быть что-то вроде: «Как я могу рассуждать о планировании ресурсов, представляя атом расписания как ресурс с временем начала и окончания?» Здесь предложение Адепта использовать интервальную алгебру кажется подходящим. См. The Wikipedia entry 'Interval Graph' и The SUNY algorithm repository entry on scheduling. Второй вопрос - вопрос с базой данных: «Учитывая алгоритм, который устанавливает интервалы и указывает, перекрываются ли два интервала или один из них, как использовать эту информацию для управления базой данных в данной схеме?» Я считаю, что как только алгоритм планирования будет на месте, вопрос с базой данных будет намного проще решить. НТН, Юваль