Forudsat at alle par også eksisterer i deres spejlede kombination (4,5) og (5,4) . Men de følgende løsninger fungerer lige så godt uden spejlede duper.
Simpelt tilfælde
Alle forbindelser kan opstilles i en enkelt stigende rækkefølge og komplikationer som jeg tilføjede i spillespillet ikke er mulige, kan vi bruge denne løsning uden dubletter i rCTE:
Jeg starter med at få minimum a_sno pr. gruppe, med det mindste tilhørende 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;
Dette kræver kun et enkelt forespørgselsniveau, da en vinduesfunktion kan bygges på et aggregat:
Resultat:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Jeg undgår grene og duplikerede (multiplikerede) rækker - potentielt meget dyrere med lange kæder. Jeg bruger ORDER BY b_sno LIMIT 1 i en korreleret underforespørgsel for at få denne til at flyve i en rekursiv CTE.
Nøglen til ydeevne er et matchende indeks, som allerede er til stede leveret af PK-begrænsningen PRIMARY KEY (a_sno,b_sno) :ikke omvendt (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 simpel sag
Alle noder kan nås i stigende rækkefølge med en eller flere grene fra roden (mindste sno ).
Denne gang får du alle større sno og de-duplikatnoder, der kan besøges flere gange med UNION til sidst:
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;
I modsætning til den første løsning får vi ikke en sidste række med NULL her (forårsaget af den korrelerede underforespørgsel).
Begge skal fungere rigtig godt - især med lange kæder / mange grene. Resultat efter ønske:
SQL Fiddle (med tilføjede rækker for at demonstrere sværhedsgrad).
Udirigeret graf
Hvis der er lokale minima, der ikke kan nås fra roden med stigende traversering, vil ovenstående løsninger ikke fungere. Overvej Farhęgs løsning i dette tilfælde.