¿Cómo labelr "grupos transitivos" con SQL?

Tengo una tabla con pares de ID que están en una relación transitiva t , es decir, si "A t B" Y "B t C" luego "A t C". Muestra:

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

Entonces hay dos grupos,

  • g1 : {1,2,5,9} porque "1 t 2", "1 t 5" y "9 t 1"
  • g2 : {4,7,8} porque "4 t 7" y "7 t 8"

y necesito producir, por "SQL puro y estándar", una nueva tabla o vista:

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

PS -1: podemos enumerar los "grupos transitivos"

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

PD -2: estoy usando PostgreSQL 9.1, pero si prefiero una solución con "SQL estándar".

Puedes hacer esto en Postgres; no puedes hacer esto en todas las bases de datos. Aquí está la consulta:

 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; 

Con el SQL Fiddle aquí .

Usted está caminando a través de una estructura de tree para asignar la label (por cierto, los ciclos pueden plantear problemas con esta versión particular). En Postgres, puede hacer esto usando un CTE recursive explícito. En SQL Server, puede hacer esto con un CTE que es implícitamente "recursivo" (la palabra key no se usa). En Oracle, puedes hacer esto con connect by .

El CTE recursivo obtiene todos los pares que están conectados entre sí. La consulta principal luego asigna el valor mínimo de id1 e id2 al par, para identificar todos los pares que están conectados entre sí. La label final se produce simplemente asignando un valor secuencial a grp .

EDITAR:

Egor hace un muy buen punto. Lo anterior supone que los identificadores "descienden" a los valores más pequeños. En su lugar, la siguiente versión usa el nivel más alto para cada identificación para la agrupación (que en realidad es lo que se pretende):

 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; 

EDIT II:

En respuesta al segundo comentario de Egor. Esta información es un poco problemática con respecto al problema original. Lo siguiente lo divide en dos partes:

 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; 

Pero no está claro si eso es lo que el original quería. Rompería el original en tres grupos que se superponen, porque hay tres identificadores en la segunda columna que nunca están en la primera columna. La pregunta aquí es sobre la conmutatividad.

Ahora, una nueva demanda en 2013, necesito trabajar con 10000 itens : usando la elegante solución de @ GordonLinoff (arriba), con 1000 itens necesita 1 segundo, con 2000 necesita 1 día … No tiene un buen performance . El problema del performance también fue recordado aquí ,

El algorithm @NealB

(esta es la mejor solución , ¡tan rápido!) Consulte la descripción original y didáctica . Aquí la tabla T1 es la misma que el text de la pregunta, y una segunda tabla (temporal) R se usa para procesar y mostrar los resultados,

  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; 

Preparación y ejecución,

  -- 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 

Tratando con el peor de los casos

La última condición, cuando label1!=label2 , es la operación que más time consume, y debe evitarse o separarse en los casos de alta conectividad, que son los peores.

Para informar algún tipo de alerta, puede contar la proporción de veces que el procedimiento ejecuta la última condición y / cor puede separar la última actualización.

Si se separa, puede analizar y tratar un poco mejor con ellos Entonces, eliminando el último ELSIF y agregando después del primer ciclo sus cheques y este segundo ciclo:

  -- ... 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; -- ... 

Ejemplo del peor caso: un grupo con más de 1000 nodos (conectados) en 10000 nodos con una longitud promedio de "10 por grupo labeldo" (núcleos) y solo unas pocas routes que conectan núcleos.

Algoritmo orientado a matriz

Esta otra solución es más lenta (es un algorithm de fuerza bruta ), pero puede utilizarse cuando se necesita procesamiento directo con matrices, y no necesita una solución tan rápida (y no tiene los "peores casos").

Como @ peter.petrov y @RBarryYoung sugieren usar una estructura de datos más adecuada … Volví a mis matrices como "estructura de datos más adecuada". Después de todo, hay una buena aceleración (en comparación con el algorithm de @ GordonLinoff) con la solución a continuación (!) .

El primer paso es traducir la tabla t1 del text de pregunta a una temporal, transgroup1 , donde podemos calcular el nuevo process,

  -- 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; 

ellos, con estas dos funciones podemos resolver el problema,

  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; 

por supuesto, para ejecutar y ver resultados, puede usar

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

resultante

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