sql - 如何用SQL标记 "transitive groups"？

Question

我有一个表，其中的 ID 对位于 transitive relation 中t，也就是说，如果“A t B”和“B t C”则“A t C ”。示例:

  table T1
  ID1 | ID2 
  1   | 2
  1   | 5
  4   | 7
  7   | 8
  9   | 1

所以有两组，

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

我需要通过“纯标准 SQL”生成一个新表或 View :

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

PS-1:我们可以通过

列出“传递组”

  SELECT DISTINCT label, id   
  FROM (SELECT id1 as id, * FROM T2) UNION (SELECT id2 as id, * FROM T2)
  ORDER BY 1,2;

PS-2:我正在使用 PostgreSQL 9.1，但如果有“标准 SQL”的解决方案，我更喜欢。

Answer 1

你可以在 Postgres 中做到这一点；您不能在所有数据库中执行此操作。这是查询:

with 
    recursive cte(id1, id2) as (
     select id1, id2, 1 as level
     from t
     union all
     select t.id1, cte.id2, cte.level + 1
     from t join
          cte
          on t.id2 = cte.id1
  )
select id1, id2,
       dense_rank() over (order by grp) as label
from (select id1, id2,
             least(min(id2) over (partition by id1), min(id1) over (partition by id2)) as grp,
             level
      from cte
     ) t
where level = 1;

使用 SQL Fiddle here .

您正在遍历树结构以分配标签(顺便说一句，循环可能会给这个特定版本带来问题)。在 Postgres 中，您可以使用显式 recursive CTE 来执行此操作。在 SQL Server 中，您可以使用隐式“递归”(不使用关键字)的 CTE 来执行此操作。在 Oracle 中，您可以使用 connect by 执行此操作。

递归 CTE 获取所有相互连接的对。主查询然后将 id1 和 id2 的最小值分配给该对，以识别所有相互连接的对。只需为 grp 分配一个顺序值即可生成最终标签。

编辑:

Egor 提出了一个很好的观点。以上假设 ids“下降”到较小的值。以下版本改为对分组的每个 id 使用最高级别(这确实是预期的):

with 
    recursive cte(id1, id2) as (
     select id1, id2, 1 as level
     from t
     union all
     select t.id1, cte.id2, cte.level + 1
     from t join
          cte
          on t.id2 = cte.id1
    --  where not exists (select 1 from cte cte2 where cte2.id1 = t.id1 and cte2.id2 = t.id2) 
  ) 
select id1, id2,
       dense_rank() over (order by topvalue) as label
from (select id1, id2,
             first_value(id2) over (partition by id1 order by level desc) as topvalue,
             level
      from cte
     ) t
where level = 1;

编辑二:

回应 Egor 的第二条评论。这个数据相对于原来的问题有点问题。以下将其分为两部分:

with 
    recursive cte as (
     select id1, id2, id2 as last, id1||','||id2 as grp, 1 as level
     from t
     where id2 not in (select id1 from t)
     union all
     select t.id1, t.id2, cte.last, cte.grp, cte.level + 1
     from t join
          cte
          on t.id2 = cte.id1
    --  where not exists (select 1 from cte cte2 where cte2.id1 = t.id1 and cte2.id2 = t.id2) 
  ) 
select *
from cte;

但是，不清楚这是否是原始人想要的。它会把原来的分成三个重叠的组，因为第二列中有三个 id 从不在第一列中。这里的问题是关于交换性。