Giả sử rằng tất cả các cặp cũng tồn tại trong kết hợp được sao chép của chúng (4,5) và (5,4) . Nhưng các giải pháp sau đây cũng hoạt động mà không bị trùng lặp.
Trường hợp đơn giản
Tất cả các kết nối có thể được xếp theo một trình tự tăng dần duy nhất và các biến chứng như tôi đã thêm trong fiddle không thể, chúng tôi có thể sử dụng giải pháp này mà không có bản sao trong rCTE:
Tôi bắt đầu bằng cách đạt được a_sno tối thiểu mỗi nhóm, với b_sno được liên kết tối thiểu :
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;
Điều này chỉ cần một cấp truy vấn duy nhất vì một hàm cửa sổ có thể được xây dựng dựa trên tổng thể:
Kết quả:
grp a_sno b_sno
1 4 5
2 9 10
3 11 15
Tôi tránh các nhánh và hàng trùng lặp (nhiều lần) - có khả năng nhiều đắt hơn với chuỗi dài. Tôi sử dụng ORDER BY b_sno LIMIT 1 trong một truy vấn con tương quan để làm cho điều này bay trong CTE đệ quy.
Chìa khóa để đạt được hiệu suất là một chỉ mục phù hợp, đã được cung cấp bởi ràng buộc PK PRIMARY KEY (a_sno,b_sno) :không phải ngược lại :(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;
Trường hợp ít đơn giản hơn
Tất cả các nút có thể đạt được theo thứ tự tăng dần với một hoặc nhiều nhánh từ gốc (sno nhỏ nhất ).
Lần này, nhận được tất cả lớn hơn sno và loại bỏ các nút trùng lặp có thể được truy cập nhiều lần với UNION ở cuối:
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;
Không giống như giải pháp đầu tiên, chúng tôi không nhận được hàng cuối cùng có NULL ở đây (do truy vấn con tương quan gây ra).
Cả hai đều sẽ hoạt động rất tốt - đặc biệt là với chuỗi dài / nhiều nhánh. Kết quả như mong muốn:
SQL Fiddle (có thêm các hàng để thể hiện độ khó).
Biểu đồ vô hướng
Nếu có cực tiểu cục bộ không thể truy cập từ gốc với truyền tải tăng dần, các giải pháp trên sẽ không hoạt động. Xem xét giải pháp của Farhęg trong trường hợp này.
