Ervan uitgaande dat alle paren ook in hun gespiegelde combinatie bestaan (4,5) en (5,4) . Maar de volgende oplossingen werken net zo goed zonder gespiegelde dupes.
Eenvoudig geval
Alle verbindingen kunnen worden opgesteld in een enkele oplopende reeks en complicaties zoals ik heb toegevoegd in de viool zijn niet mogelijk, kunnen we deze oplossing gebruiken zonder duplicaten in de rCTE:
Ik begin met het verkrijgen van minimaal a_sno per groep, met het minimum geassocieerde 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;
Dit heeft slechts een enkel zoekniveau nodig, aangezien een vensterfunctie op een aggregaat kan worden gebouwd:
Resultaat:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Ik vermijd vertakkingen en dubbele (vermenigvuldigde) rijen - mogelijk veel duurder met lange kettingen. Ik gebruik ORDER BY b_sno LIMIT 1 in een gecorreleerde subquery om deze in een recursieve CTE te laten vliegen.
De sleutel tot prestatie is een overeenkomende index, die al aanwezig is door de PK-beperking PRIMARY KEY (a_sno,b_sno) :niet andersom (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;
Minder eenvoudig geval
Alle knooppunten zijn in oplopende volgorde te bereiken met een of meer takken vanaf de wortel (kleinste sno ).
Krijg deze keer alle grotere sno en ontdubbel knooppunten die meerdere keren kunnen worden bezocht met UNION aan het einde:
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;
In tegenstelling tot de eerste oplossing krijgen we hier geen laatste rij met NULL (veroorzaakt door de gecorreleerde subquery).
Beide zouden zeer goed moeten presteren - vooral met lange kettingen / veel takken. Resultaat naar wens:
SQL Fiddle (met toegevoegde rijen om de moeilijkheidsgraad aan te tonen).
Ongerichte grafiek
Als er lokale minima zijn die niet kunnen worden bereikt vanaf de wortel met oplopende traversal, zullen de bovenstaande oplossingen niet werken. Overweeg Farhęg's oplossing in dit geval.