sql - 如何用约束标记一大组 “transitive groups”？

Question

在@NealB 解决方案之后进行编辑:与any another one 相比，@NealB 的解决方案非常非常快, 并免除了这个关于“添加约束以提高性能”的新问题。 @NealB 不需要任何改进，有 O(n) 时间并且非常简单。

---

“label transitive groups with SQL”的问题有an elegant solution using recursion and CTE ...但是这个解决方案消耗了指数时间(!)。我需要处理 10000 个项目:1000 个项目需要 1 秒，2000 个项目需要 1 天...

约束:在我的例子中，可以将问题分解为 ~100 个或更少的小块，但只选择一组 ~10 个 iten，并丢弃所有其他 ~90 个标记的 iten ...

有一种通用算法可以添加和使用这种“预选”，以减少二次方 O(N^2) 时间？也许，如评论和@wildplasser 所示，O(N log(N)) 时间；但我希望通过“预选”减少到 O(N) 时间。

---

(编辑)

我尝试使用 alternative algorithm ，但它需要一些改进才能用作此处的解决方案；或者，要真正提高性能(到 O(N) 时间)，需要使用“预选”。

“预选”(约束)是基于一个“超集分组”... 原文"How to label 'transitive groups' with SQL?" question t1 表，

  table T1
  (original T1 augmented by "super-set grouping label" ssg, and more one row)
  ID1 | ID2 | ssg
  1   | 2   | 1
  1   | 5   | 1
  4   | 7   | 1
  7   | 8   | 1 
  9   | 1   | 1
  10  | 11  | 2

所以分为三组，

• g1:{1,2,5,9} 因为“1 t 2”、“1 t 5”和“9 t 1"
• g2:{4,7,8} 因为“4 t 7”和“7 t 8”
• g3:{10,11} 因为“10 t 11”

super 组只是辅助分组，

• ssg1: {g1,g2}
• ssg2: {g3}

如果我们有 M 个 super 组项目和 N 总 T1 个项目，平均组长度将小于 N/M .我们还可以假设(对于我的典型问题)ssg 最大长度为~N/M。

所以， the "label algorithm"如果它使用 ssg 约束，则只需运行 M 次 ~N/M 项。

Answer 1

只有 SQL 的解决方案在这里似乎有点问题。在一些程序的帮助下在 SQL 之上编程解决方案似乎非常简单有效。这是一个简要概述可以使用任何调用 SQL 的过程语言来实现的解决方案。

使用主键ID 声明表R，其中ID 对应于与ID1 和 相同的域表 T1 的 ID2。表 R 包含另一个非键列，一个 Label 数字

使用在 T1 中找到的值范围填充表 R。将 Label 设置为零(无标签)。使用您的示例数据，R 的初始设置如下所示:

Table R
ID Label
== =====
 1 0
 2 0
 4 0
 5 0
 7 0
 8 0
 9 0

使用宿主语言游标和辅助计数器，从 T1 中读取每一行。在 R 中查找 ID1 和 ID2。你会发现其中之一四种情况:

 Case 1: ID1.Label == 0 and ID2.Label == 0

在这种情况下，这些 ID 中的任何一个之前都没有被“看到”:将 1 添加到计数器，然后更新两者R 的行到计数器的值:update R set R.Label = :counter where R.ID in (:ID1, :ID2)

 Case 2: ID1.Label == 0 and ID2.Label <> 0

在这种情况下，ID1 是新的，但 ID2 已经分配了标签。 ID1 需要分配给与 ID2 相同的标签:update R set R.Lablel = :ID2.Label where R.ID = :ID1

 Case 3: ID1.Label <> 0 and ID2.Label == 0

在这种情况下，ID2 是新的，但 ID1 已经分配了标签。 ID2 需要分配给与 ID1 相同的标签:update R set R.Lablel = :ID1.Label where R.ID = :ID2

 Case 4: ID1.Label <> 0 and ID2.Label <> 0

在这种情况下，该行包含冗余信息。 R 的两行应包含相同的 Label 值。如果不，存在某种数据完整性问题。啊……不太明白编辑……

编辑 我刚刚意识到，在某些情况下，此处的 Label 值可能不为零且不同。如果两者都非零且不同，则此时需要合并两个 Label 组。您需要做的就是选择一个 Label 并更新其他标签以匹配以下内容:update R set R.Label to ID1.Label where R.Label = ID2.Label。现在这两个组已合并为相同的 Label 值。

游标完成后，表 R 将包含更新 T2 所需的标签值。

Table R
ID Label
== =====
 1 1
 2 1
 4 2
 5 1
 7 2
 8 2
 9 1

进程表T2使用类似以下内容的内容:set T2.Label to R.Label where T2.ID1 = R.ID。最终结果应该是:

  table T2
  ID1 | ID2 | LABEL 
  1   | 2   | 1
  1   | 5   | 1
  4   | 7   | 2
  7   | 8   | 2
  9   | 1   | 1

这个过程是非常迭代的，应该可以毫无困难地扩展到相当大的表。