Supponendo che tutte le coppie esistano anche nella loro combinazione speculare (4,5) e (5,4) . Ma le seguenti soluzioni funzionano altrettanto bene senza duplicati con mirroring.
Caso semplice
Tutti i collegamenti possono essere allineati in una unica sequenza ascendente e complicazioni come ho aggiunto nel violino non sono possibili, possiamo usare questa soluzione senza duplicati in rCTE:
Comincio ottenendo un minimo di a_sno per gruppo, con il minimo associato 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;
Questo richiede solo un singolo livello di query poiché una funzione di finestra può essere costruita su un aggregato:
Risultato:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Evito i rami e le righe duplicate (moltiplicate), potenzialmente molto più costoso con catene lunghe. Uso ORDER BY b_sno LIMIT 1 in una sottoquery correlata per farlo volare in un CTE ricorsivo.
La chiave per le prestazioni è un indice di corrispondenza, già presente fornito dal vincolo PK PRIMARY KEY (a_sno,b_sno) :non il contrario (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 meno semplice
Tutti i nodi possono essere raggiunti in ordine crescente con uno o più rami dalla radice (il più piccolo sno ).
Questa volta, prendi tutti maggiore sno e deduplica i nodi che possono essere visitati più volte con UNION alla fine:
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 differenza della prima soluzione, qui non otteniamo un'ultima riga con NULL (causata dalla sottoquery correlata).
Entrambi dovrebbero funzionare molto bene, specialmente con catene lunghe/molti rami. Risultato desiderato:
SQL Fiddle (con righe aggiunte per dimostrare la difficoltà).
Grafico non orientato
Se ci sono minimi locali che non possono essere raggiunti dalla radice con attraversamento ascendente, le soluzioni di cui sopra non funzioneranno. Prendi in considerazione la soluzione di Farhęg in questo caso.
