Suponiendo que todos los pares existen en su combinación reflejada también (4,5) y (5,4) . Pero las siguientes soluciones también funcionan sin duplicados duplicados.
Caso sencillo
Todas las conexiones se pueden alinear en una secuencia ascendente única y complicaciones como las que agregué en el fiddle no son posibles, podemos usar esta solución sin duplicados en el rCTE:
Comienzo obteniendo el mínimo a_sno por grupo, con el mínimo asociado b_sno :
SELECT row_number() OVER (ORDER BY a_sno) AS grp
, a_sno, min(b_sno) AS b_sno
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
GROUP BY a_sno;
Esto solo necesita un único nivel de consulta ya que una función de ventana se puede construir en un agregado:
Resultado:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Evito ramas y filas duplicadas (multiplicadas), potencialmente mucho más caro con cadenas largas. Yo uso ORDER BY b_sno LIMIT 1 en una subconsulta correlacionada para hacer que vuele en un CTE recursivo.
La clave del rendimiento es un índice coincidente, que ya está presente proporcionado por la restricción PK PRIMARY KEY (a_sno,b_sno) :no al revés (b_sno, a_sno)
WITH RECURSIVE t AS (
SELECT row_number() OVER (ORDER BY d.a_sno) AS grp
, a_sno, min(b_sno) AS b_sno -- the smallest one
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
GROUP BY a_sno
)
, cte AS (
SELECT grp, b_sno AS sno FROM t
UNION ALL
SELECT c.grp
, (SELECT b_sno -- correlated subquery
FROM data
WHERE a_sno = c.sno
AND a_sno < b_sno
ORDER BY b_sno
LIMIT 1)
FROM cte c
WHERE c.sno IS NOT NULL
)
SELECT * FROM cte
WHERE sno IS NOT NULL -- eliminate row with NULL
UNION ALL -- no duplicates
SELECT grp, a_sno FROM t
ORDER BY grp, sno;
Caso menos sencillo
Se puede llegar a todos los nodos en orden ascendente con una o más ramas desde la raíz (menor sno ).
Esta vez, obtén todos mayor sno y elimine los nodos duplicados que se pueden visitar varias veces con UNION al final:
WITH RECURSIVE t AS (
SELECT rank() OVER (ORDER BY d.a_sno) AS grp
, a_sno, b_sno -- get all rows for smallest a_sno
FROM data d
WHERE a_sno < b_sno
AND NOT EXISTS (
SELECT 1 FROM data
WHERE b_sno = d.a_sno
AND a_sno < b_sno
)
)
, cte AS (
SELECT grp, b_sno AS sno FROM t
UNION ALL
SELECT c.grp, d.b_sno
FROM cte c
JOIN data d ON d.a_sno = c.sno
AND d.a_sno < d.b_sno -- join to all connected rows
)
SELECT grp, sno FROM cte
UNION -- eliminate duplicates
SELECT grp, a_sno FROM t -- add first rows
ORDER BY grp, sno;
A diferencia de la primera solución, aquí no obtenemos una última fila con NULL (causada por la subconsulta correlacionada).
Ambos deberían funcionar muy bien, especialmente con cadenas largas/muchas ramas. Resultado deseado:
SQL Fiddle (con filas añadidas para demostrar la dificultad).
Gráfico no dirigido
Si hay mínimos locales que no se pueden alcanzar desde la raíz con un recorrido ascendente, las soluciones anteriores no funcionarán. Considere la solución de Farhęg en este caso.
