Förutsatt att alla par finns i deras speglade kombination också (4,5) och (5,4) . Men följande lösningar fungerar lika bra utan speglade duper.
Enkelt fall
Alla anslutningar kan radas upp i en en stigande sekvens och komplikationer som jag lade till i fiol inte är möjliga kan vi använda den här lösningen utan dubbletter i rCTE:
Jag börjar med att få minsta a_sno per grupp, med minsta associerade 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;
Detta behöver bara en enskild frågenivå eftersom en fönsterfunktion kan byggas på ett aggregat:
Resultat:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Jag undviker grenar och dubblerade (multiplicerade) rader - potentiellt mycket dyrare med långa kedjor. Jag använder ORDER BY b_sno LIMIT 1 i en korrelerad underfråga för att få detta att flyga i en rekursiv CTE.
Nyckeln till prestanda är ett matchande index, som redan finns tillhandahållet av PK-begränsningen PRIMARY KEY (a_sno,b_sno) :inte tvärtom (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;
Mindre enkla fall
Alla noder kan nås i stigande ordning med en eller flera grenar från roten (minsta sno ).
Den här gången får du alla större sno och de-duplicera noder som kan besökas flera gånger med UNION i slutet:
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;
Till skillnad från den första lösningen får vi inte en sista rad med NULL här (orsakad av den korrelerade underfrågan).
Båda ska prestera mycket bra - speciellt med långa kedjor / många grenar. Resultat som önskat:
SQL Fiddle (med tillagda rader för att visa svårighetsgraden).
Oriktat diagram
Om det finns lokala minima som inte kan nås från roten med stigande traversering, fungerar inte ovanstående lösningar. Överväg Farhęgs lösning i det här fallet.