Angenommen, alle Paare existieren auch in ihrer gespiegelten Kombination (4,5) und (5,4) . Aber die folgenden Lösungen funktionieren genauso gut ohne gespiegelte Duplikate.
Einfacher Fall
Alle Verbindungen können in einer einfach aufsteigenden Reihenfolge aneinandergereiht werden und Komplikationen, wie ich sie in der Geige hinzugefügt habe nicht möglich sind, können wir diese Lösung ohne Duplikate im rCTE verwenden:
Ich fange an, indem ich mindestens a_sno erhalte pro Gruppe, mit dem zugehörigen Minimum 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;
Dies erfordert nur eine einzige Abfrageebene, da eine Fensterfunktion auf einem Aggregat aufgebaut werden kann:
Ergebnis:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Ich vermeide Verzweigungen und doppelte (multiplizierte) Zeilen - möglicherweise viel teurer mit langen Ketten. Ich verwende ORDER BY b_sno LIMIT 1 in einer korrelierten Unterabfrage, um dies in einem rekursiven CTE fliegen zu lassen.
Der Schlüssel zur Leistung ist ein passender Index, der bereits durch die PK-Einschränkung PRIMARY KEY (a_sno,b_sno) bereitgestellt wird :nicht umgekehrt (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;
Weniger einfacher Fall
Alle Knoten sind in aufsteigender Reihenfolge mit einem oder mehreren Zweigen von der Wurzel aus erreichbar (kleinste sno ).
Holen Sie sich dieses Mal alle größer sno und deduplizieren Sie Knoten, die möglicherweise mehrmals besucht werden, mit UNION am Ende:
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;
Anders als bei der ersten Lösung erhalten wir hier keine letzte Zeile mit NULL (verursacht durch die korrelierte Unterabfrage).
Beides sollte sehr gut funktionieren - gerade bei langen Ketten / vielen Verzweigungen. Ergebnis wie gewünscht:
SQL-Fiddle (mit zusätzlichen Reihen, um die Schwierigkeit zu demonstrieren).
Ungerichteter Graph
Wenn es lokale Minima gibt, die von der Wurzel mit aufsteigender Traversierung nicht erreicht werden können, funktionieren die obigen Lösungen nicht. Betrachten Sie Farhęgs Lösung in diesem Fall.
