相交集的并集

Question

我有一个 table 表示像

这样的记录集

set_id | record_id
     a |         1
     a |         2
     a |         3
     b |         2
     b |         4
     b |         5
     c |         6
     c |         7
     d |         9
     d |        11
     e |        10
     f |        11
     f |        12

我想产生这样的输出

output
{1, 2, 3, 4, 5}
{6, 7}
{9, 11, 12}
{10}

其中相交集合合并（注意集合a和集合b已合并；d 和 f 也合并了）。

是否有使用 SQL 执行此操作的好方法，而不是存储过程。我知道我正在寻找一种 Union-Find 程序。

Answer 1

准备：

so=> create table so75(set_id text, record_id int);
CREATE TABLE
so=> copy so75 from stdin;
Enter data to be copied followed by a newline.
End with a backslash and a period on a line by itself.
>> ^CERROR:  COPY from stdin failed: canceled by user
CONTEXT:  COPY so75, line 1
so=> copy so75 from stdin delimiter '|';
Enter data to be copied followed by a newline.
End with a backslash and a period on a line by itself.
>>      a |         1
 a |         2
 a |         3
 b |         2
 b |         4
 b |         5
 c |         6
 c |         7
 d |         9
 d |        11
 e |        10
 f |        11
 f |        12   
>> >> >> >> >> >> >>
>> \.
COPY 14

求问：

so=> with keys as (
  with a as (
    select *,count(1) over (partition by record_id) c, array_agg(set_id) over(partition by record_id) cc
    from so75
  )
  select set_id, cc
  from a where c > 1
)
select distinct array_agg(distinct record_id)
from so75
left outer join keys on keys.set_id = so75.set_id
group by case when array_length(cc,1) > 1 then cc::text else so75.set_id end;
  array_agg
-------------
 {6,7}
 {10}
 {1,2,3,4,5}
 {9,11,12}
(4 rows)

相交集的并集

Unions of intersecting sets

postgresql

union-find