如何用SQL标记"传递组"？

Question

我有一个ID对的表,它具有传递关系 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"生成新的表或视图:

  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 个 itens 需要 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，是最耗时的操作，必须避免或可以在高连接性的情况下分开，这是最糟糕的。

要报告某种警报，您可以计算程序运行最后一个条件的次数比例，并且/或者可以分隔最后一次更新。

如果分开，您可以更好地分析和处理它们因此，消除最后一个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