2

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

编辑：正如建议的那样，我已经大大缩短了这个问题。

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

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

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

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

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

因此，给定以下 3 组：

  • 表 A 中的原始对象（来自数据库）
  • 表 B 中的原始对象（来自数据库）
  • 表 A 中已编辑的对象集（来自用户，因此没有唯一 ID）

我需要一个算法，它将：

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

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

再次，请根据您的喜好具体或一般地回答，我正在寻找建议，但如果有人有一个完整的算法，那会让我很开心。:)

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

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

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

例如（使用简写）：

表 A
ID资源开始结束
01 资源 A 10/6 7:00AM 10/6 11:00AM
02 资源 A 10/6 1:00PM 10/6 3:00PM

表 B
ID Table_A_ID 开始 结束
01 02 10/6 下午 1:00 10/6 下午 2:00

所以我想要以下行为：

  • 如果我从表 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。
4

5 回答 5

7

我在句号方面进行了广泛的工作，但恐怕我并不完全理解表 A 和 B 是如何协同工作的，也许是我不明白的包含这个词。

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

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

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

或重叠？

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

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

假设它是第一个，其中 B 中的时间跨度在表 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. 对于您“记住”的任何时期，看看它们是否需要重新链接或删除

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

于 2008-10-06T12:12:24.697 回答
2

我建议你将你的问题分解成两个独立的问题：第一个应该是这样的：“当将调度原子表示为具有开始时间和结束时间的资源时，我如何推理资源调度？” 在这里，ADept 使用区间代数的建议似乎很合适。请参阅Wikipedia 条目“间隔图”和SUNY 算法存储库条目关于调度。第二个问题是数据库问题：“给定一个算法，它调度间隔并指示两个间隔是否重叠或一个包含在另一个中，我如何使用这些信息来管理给定模式中的数据库？” 我相信一旦调度算法到位，数据库问题就会容易解决很多。HTH，尤瓦尔

于 2008-10-06T12:07:51.243 回答
1

您的帖子几乎属于“太长；未阅读”类别 - 缩短它可能会给您更多反馈。

无论如何，关于主题：您可以尝试研究一个名为“区间代数”的东西

于 2008-10-05T19:14:15.283 回答
1

据我了解，您的用户只能直接影响表 A。假设您使用 C# 编程，您可以使用简单的 ADO.Net DataSet 来管理对表 A 的修改。 TableAdapter 知道单独保留未触及的行并处理新的，适当地修改和删除行。

此外，您应该定义一个级联删除，以便自动删除表 B 中的相应对象。

唯一没有以这种方式处理的情况是，如果表 A 中的时间跨度被缩短，则它不再包含表 B 中的相应记录。您可以简单地在更新存储过程中检查这种情况，或者在表 A 上定义更新触发器。

于 2008-10-05T19:42:51.123 回答
1

在我看来，任何算法都将涉及通过 NewA，匹配 ResourceID、StartTime 和 EndTime，并跟踪来自 OldA 的哪些元素被命中。然后你有两组不匹配的数据，UnmatchedNewA 和 UnmatchedOldA。

我能想到的最简单的方法基本上是从这些重新开始：将所有 UnmatchedNewA 写入数据库，将 B 的元素从 UnmatchedOldA 转移到新的 A 键（刚刚生成）中，如果可能，则删除。然后清除所有UnmatchedOldA。

如果有很多变化，这肯定不是一个有效的方法。但是，在数据量不是很大的情况下，我更喜欢简单而不是巧妙的优化。

如果没有更多背景，就不可能知道这个最终建议是否有意义，但如果你没有这样想的话：

您可以使用事件侦听器或类似的东西来仅在需要更改的地方更新数据模型，而不是来回传递整个 A 集合吗？这样，被更改的对象将能够动态确定需要哪些数据库操作。

于 2008-10-05T19:56:14.170 回答