如何用SQL标记“传递组”？

Question

我有一个ID对在传递关系 t中的表，也就是说，如果“AND”和" B“那么”AND“。示例：

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

所以有两组，

• g1：{1,2,5,9}因为“1t2”、“1t5”和“9t1”
• g2：{4,7,8}因为“4t7”和“7t8”

我需要通过“纯标准SQL”生成一个新的表或视图：

  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

现在，2013年的新需求，我需要与10000 itens：使用@GordonLinoff的优雅解决方案(上图)，1000 itens需要1秒，2000年需要1天.没有很好的性能。性能的问题也是记在这里，

@NealB算法

(这是--最好的解决方案，太快了！)见原创性和教学性描述。这里，表T1与问题文本相同，第二个(临时)表R用于处理和显示结果，

 CREATE TABLE R (
   id integer NOT NULL, -- PRIMARY KEY,
   label integer NOT NULL DEFAULT 0
 );
 CREATE FUNCTION t1r_labeler() RETURNS void AS $funcBody$
   DECLARE
      label1 integer;
      label2 integer;
      newlabel integer;
      t t1%rowtype;
   BEGIN
       DELETE FROM R;
       INSERT INTO R(id) 
           SELECT DISTINCT unnest(array[id1,id2]) 
           FROM T1 ORDER BY 1;
      newlabel:=0;
      FOR t IN SELECT * FROM t1
      LOOP   -- --  BASIC LABELING:  -- --
         SELECT label INTO label1 FROM R WHERE id=t.id1;
         SELECT label INTO label2 FROM R WHERE id=t.id2;
         IF label1=0 AND label2=0 THEN 
              newlabel:=newlabel+1;
              UPDATE R set label=newlabel WHERE ID in (t.id1,t.id2);
         ELSIF label1=0 AND label2!=0 THEN 
              UPDATE R set label=label2 WHERE ID=t.id1;
         ELSIF label1!=0 AND label2=0 THEN 
              UPDATE R set label=label1 WHERE ID=t.id2;
         ELSIF label1!=label2 THEN -- time consuming
              UPDATE tmp.R set label=label1 WHERE label = label2;
         END IF;
      END LOOP;
    END;
 $funcBody$ LANGUAGE plpgsql VOLATILE; 

准备和运行，

 -- same CREATE TABLE T1 (id1 integer, id2 integer);
 DELETE FROM T1; 
 INSERT INTO T1(id1,id2)  -- populate the standard input
 VALUES (1, 2), (1, 5), (4, 7), (7, 8), (9, 1);
   -- or  SELECT id1, id2 FROM table_with_1000000_items;

 SELECT t1r_labeler();       -- run
 SELECT * FROM R ORDER BY 2; -- show

处理最坏的情况

最后一个条件，当label1!=label2是最耗时的操作时，必须避免或在连接性高的情况下分离，这是最糟糕的情况。

要报告某种警报，您可以计算过程运行最后一个条件的时间比例，并且/cor可以分隔最后一个更新。

如果分开，您可以更好地分析和处理它们，从而消除最后一个ELSIF，并在第一个循环之后添加检查和第二个循环：

      -- ... first loop and checks here ...
      FOR t IN SELECT * FROM tmp.t1 
      LOOP   -- --  MERGING LABELS:  -- --
         SELECT label INTO label1 FROM R WHERE id=t.id1;
         SELECT label INTO label2 FROM R WHERE id=t.id2;
         IF label1!=0 AND label2!=0 AND label1!=label2 THEN
             UPDATE R set label=label1 WHERE label=label2;
         END IF;
      END LOOP;
      -- ...

最坏的情况:一个组有超过1000个(连接)节点到10000个节点，平均长度为“每个标记组10”(核心)，只有很少的路径连接核心。

面向数组的算法

另一种解决方案速度较慢(是一种强力算法)，但在需要直接处理数组时可以使用，而不需要这么快的解决方案(而且没有“最坏的情况”)。

作为@peter.petrov和@RBarryYoung建议使用更充分的数据结构..。我回到了我的数组“更充分的数据结构”。毕竟，有很好的速度(与@GordonLinoff的算法相比)和(!)下面的解决方案。

第一步是将问题文本的表t1转换为临时的表transgroup1，在那里我们可以计算新的进程，

 -- DROP table transgroup1;
 CREATE TABLE transgroup1 (
   id serial NOT NULL PRIMARY KEY,
   items integer[], -- two or more items in the transitive relationship
   dels integer[] DEFAULT array[]::integer[]
 );
 INSERT INTO transgroup1(items)
   SELECT array[id1, id2] FROM t1; -- now suppose t1 a 10000 items table;

有了这两个功能，我们就能解决这个问题，

 CREATE FUNCTION array_uunion(anyarray,anyarray) RETURNS anyarray AS $$
     -- ensures distinct items of a concatemation
    SELECT ARRAY(SELECT  unnest($1) UNION SELECT  unnest($2))
 $$ LANGUAGE sql immutable;


  CREATE FUNCTION transgroup1_loop() RETURNS void AS
  $BODY$
    DECLARE
       cp_dels integer[];
       i integer;
       max_i integer;
    BEGIN
       i:=1;
       max_i:=10; -- or 100 or more, but need some control to be secure
       LOOP
           UPDATE transgroup1
           SET items = array_uunion(transgroup1.items,t2.items),
               dels =  transgroup1.dels || t2.id
           FROM transgroup1 AS t1, transgroup1 AS t2
           WHERE transgroup1.id=t1.id AND t1.id>t2.id AND t1.items && t2.items;

           cp_dels := array(
               SELECT DISTINCT unnest(dels) FROM transgroup1
           ); -- ensures all itens to del
           EXIT WHEN i>max_i OR array_length(cp_dels,1)=0;

           DELETE FROM transgroup1 WHERE id IN (SELECT unnest(cp_dels));
           UPDATE transgroup1 SET dels=array[]::integer[];
           i:=i+1;
       END LOOP;
       UPDATE transgroup1         -- only to beautify
       SET items = ARRAY(SELECT unnest(items) ORDER BY 1 desc);
     END;
  $BODY$ LANGUAGE plpgsql VOLATILE;

当然，要运行并查看结果，可以使用

 SELECT transgroup1_loop(); -- not 1 day but some hours!     
 SELECT *, dense_rank() over (ORDER BY id) AS group from transgroup1;

结果

 id |   items   | ssg_label | dels | group 
----+-----------+-----------+------+-------
  4 | {8,7,4}   | 1         | {}   |     1
  5 | {9,5,2,1} | 1         | {}   |     2

Answer 2

您可以在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 这里。

为了分配标签，您正在遍历树结构(顺便说一句，周期可能会给这个特定版本带来问题)。在Postgres中，您可以使用显式的recursive CTE来实现这一点。在Server中，可以使用隐式“递归”(不使用关键字)的CTE来实现这一点。在甲骨文中，您可以使用connect by完成此操作。

递归CTE获取彼此连接的所有对。然后，主查询将id1和id2的最小值分配给这对，以标识彼此连接的所有对。最后的标签是通过给grp分配一个顺序的值来产生的。

编辑：

埃戈尔提出了一个很好的观点。以上假设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;

编辑二：

回应埃戈尔的第二条评论。对于最初的问题，这个数据有点问题。以下内容将其分为两部分：

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;

但是，目前还不清楚这是否是最初想要的。它会将原始信息分成三个重叠的组，因为第二列中有三个in从未出现在第一列中。这里的问题是关于交换性。