Za předpokladu, že všechny páry existují ve své zrcadlené kombinaci také (4,5) a (5,4) . Ale následující řešení fungují bez zrcadlených dupů stejně dobře.
Jednoduchý případ
Všechna spojení lze seřadit v jednom vzestupném pořadí a komplikace, jako jsem přidal do housle nejsou možné, můžeme toto řešení použít bez duplikátů v rCTE:
Začnu tím, že získám minimum a_sno na skupinu, s minimálním přidruženým 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;
To vyžaduje pouze jednu úroveň dotazu, protože funkci okna lze sestavit na agregaci:
Výsledek:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Vyhýbám se větvím a duplicitním (multiplikovaným) řádkům – potenciálně hodně dražší s dlouhými řetězy. Používám ORDER BY b_sno LIMIT 1 v korelovaném poddotazu, aby to přeletělo v rekurzivním CTE.
Klíčem k výkonu je odpovídající index, který je již přítomen a poskytuje PK omezení PRIMARY KEY (a_sno,b_sno) :ne naopak (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;
Méně jednoduchý případ
Všechny uzly lze dosáhnout ve vzestupném pořadí s jednou nebo více větvemi od kořene (nejmenší sno ).
Tentokrát získejte vše větší sno a de-duplikovat uzly, které lze pomocí UNION navštívit vícekrát na konci:
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;
Na rozdíl od prvního řešení zde nezískáme poslední řádek s NULL (způsobený korelovaným poddotazem).
Obojí by mělo fungovat velmi dobře - zvláště u dlouhých řetězů / mnoha větví. Výsledek podle potřeby:
SQL Fiddle (s přidanými řádky pro demonstraci obtížnosti).
Neorientovaný graf
Pokud existují lokální minima, kterých nelze dosáhnout z kořene se vzestupným procházením, výše uvedená řešení nebudou fungovat. Zvažte Farhęgovo řešení v tomto případě.