database - 什么是最有效地编辑 "schedule"的好算法？

Question

这是一个小型日程安排应用程序。我需要一种算法来有效地比较两个“计划”，找出差异，并仅更新已更改的数据行，以及另一个表中将该表作为外键的条目。这是一个大问题，所以我会马上说我正在寻找一般性建议或特定解决方案。

编辑:按照建议，我已经大大缩短了问题。

在一张表中，我将资源与使用它们的时间跨度相关联。

我还有第二个表(表 B)，它使用表 A 中的 ID 作为外键。

表 A 中与表 B 对应的条目的时间跨度包含表 B 中的时间跨度。并非表 A 中的所有条目都会在表 B 中有条目。

我正在为用户提供一个界面来编辑表 A 中的资源计划。他们基本上为表 A 提供了一组新数据，我需要将其视为与中版本的差异数据库。

如果他们从表 A 中完全删除表 B 指向的对象，我也想从表 B 中删除该条目。

因此，给定以下 3 组:

• 表A中的原始对象(来自数据库)
• 来自表 B 的原始对象(来自 DB)
• 表 A 中经过编辑的对象集(来自用户，因此没有唯一 ID)

我需要一个算法来:

• 如果不需要更改表 A 和表 B 中的这些对象，则保留这些行。
• 根据需要向表 A 添加行。
• 根据需要从表 A 和表 B 中删除行。
• 根据需要修改表 A 和表 B 中的行。

只需将对象排序为我可以应用适当的数据库操作的排列方式就足以解决问题。

再次强调，请根据您的喜好选择具体或一般，我正在寻求建议，但如果有人有完整的算法，那将让我开心。 :)

编辑:作为对 lassvek 的回应，我提供了一些额外的细节:

表 B 的项目始终完全包含在表 A 的项目中，而不仅仅是重叠。

重要的是，表 B 的项目是量化的，因此它们应该完全落在内部或完全落在外部。如果这没有发生，那么我有一个数据完整性错误，我必须单独处理。

例如(使用速记):

Table AID Resource    Start         End01 Resource A  10/6 7:00AM   10/6 11:00AM02 Resource A  10/6 1:00PM   10/6 3:00PMTable BID Table_A_ID  Start         End01 02          10/6 1:00PM   10/6 2:00PM

所以我想要以下行为:

• 如果我从表 A 中删除 ID 02，或将其缩短为下午 2:00 - 3:00，我应该从表 B 中删除 ID 01。
• 如果我将表 A ID 01 扩展到它在下午 1:00 结束的位置，这两个条目应该合并成一行，表 B ID 01 现在应该指向表 A ID 01 .
• 如果我从表 A ID 01 中删除 8:00AM-10:00AM，则该条目应分为两个条目:一个用于 7:00AM-8:00AM，一个新条目 (ID 03) 用于 10:00AM -11:00AM。

Answer 1

我广泛使用句点，但恐怕我不完全理解表 A 和 B 是如何协同工作的，也许是我不理解包含这个词。 p>

您能举一些具体的例子说明您想要做什么吗？

你的意思是A表中记录的时间跨度完全包含B表中的时间跨度，像这样吗？

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

或重叠？

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

或者相反，B 中的时间跨度与 A 包含/重叠？

假设它是第一个，其中 B 中的时间跨度在表 A 中/与表 A 中的链接时间跨度相同。

这是否意味着:

* 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，A2 以同样的方式移动/缩短:

|-------------- 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 -------|

到目前为止，总结一下我的看法，并提出问题:

• 您希望能够对 A 执行以下操作
  • 缩短
  • 加长
  • 相邻时合并，将两个或多个合并为一个
  • 通过删除一个句点在它们中打洞，从而将其拆分
• 在上述更新后仍然包含在 A 中的 B，必要时重新链接
• B 曾经被包含，但现在完全在外面，删除它们
• B 曾经包含在内，但现在部分位于外部，编辑:删除这些，引用数据完整性
• 对于上述所有操作，做最少的必要工作以使数据与操作一致(而不是只是删除所有内容并重新插入)

我将使用 C# 实现一个可能会在我下类回家后运行的实现，今晚晚些时候我会回来提供更多。

---

编辑这是算法的尝试。

1. 首先优化新列表(即合并相邻时段等)
2. 按以下方式将此列表与数据库中的主周期“合并”:
   1. 跟踪您在两个列表(即新列表和现有列表)中的位置
   2. 如果当前新周期完全在当前现有周期之前，添加它，然后移动到下一个新周期
   3. 如果当前新周期完全在当前现有周期之后，删除现有周期及其所有子周期，然后移至下一个现有周期
   4. 如果两者重叠，按以下方式将当前现有周期调整为等于新周期，然后继续下一个新的现有周期
      1. 如果新周期在现有周期之前开始，只需移动开始
      2. 如果新周期在现有周期之后开始，检查是否有任何子周期在差异周期中，并记住它们，然后移动开始
      3. 对另一端做同样的事情
3. 对于您“记住”的任何时间段，查看是否需要重新链接或删除它们

您应该创建大量单元测试，并确保涵盖所有修改组合。