SQL Deduplicate Danh sách Tuples

Question

Tôi có một bảng với hai cột ID, như vậy:

╔════════╦══════╗ 
║ Master ║ Dupe ║ 
╠════════╬══════╣ 
║ 2  ║ 7 ║ 
║ 3  ║ 6 ║ 
║ 6  ║ 7 ║ 
║ 20  ║ 25 ║ 
║ 75  ║ 25 ║ 
╚════════╩══════╝ 

Mỗi hàng đại diện cho ID của hai hàng trong một bảng sql được coi là bản sao của nhau.

Bảng này có thể chứa hàng nghìn mục nhập, không đảm bảo cho dữ liệu ngoài cột Master đang được sắp xếp theo thứ tự tăng dần như được mô tả. Một trong hai cột có thể chứa cùng một ID với cột khác, có khả năng chống lại ID khác hoặc cùng một ID đối tác. Một lần nữa - không bảo đảm.

Từ bảng này, tôi muốn có được chỉ mục của Sư Phụ và tất cả các bản sao có thể có của nó. Như hình dưới đây.

kết quả mong muốn:

1. ID thấp nhất nên được giữ như là bậc thầy
2. Tất cả các giá trị nhân bản tiếp theo của một dupe nên lập bản đồ trở lại như nhau (ID thấp nhất) chủ

Đối với ở trên, đầu ra mong muốn sẽ trông giống như vậy (nhưng các cột KHÔNG phải được sắp xếp):

╔════════╦══════╗ 
║ Master ║ Dupe ║ 
╠════════╬══════╣ 
║ 2  ║ 3 ║ 
║ 2  ║ 6 ║ 
║ 2  ║ 7 ║ 
║ 20  ║ 25 ║ 
║ 20  ║ 75 ║ 
╚════════╩══════╝ 

Tôi thấy khó giải thích vấn đề này nên googling của tôi đã không trở lại nhiều. Tôi nghĩ rằng phải có một thuật toán một nơi nào đó cho iterating thông qua một danh sách các bộ dữ liệu như thế này và phát hiện trùng lặp.

Bất kỳ trợ giúp nào được đánh giá cao!

EDIT: Tôi đã sửa đổi các bảng mẫu để giải thích rõ hơn nội dung của chúng có thể trông như thế nào.

Một số lưu ý để xem xét,

• Không có bảo lãnh của một chuỗi. Tất cả có thể là một chuỗi lớn, rất nhiều chuỗi nhỏ hoặc không có gì cả.
• Không có đảm bảo rằng tất cả các cặp xuất hiện theo thứ tự ngược ở một nơi khác trong bảng

Từ những gì tôi có thể thấy, vấn đề có vẻ là đệ quy, tôi nghĩ LukStorms đang đi đúng hướng nhưng tôi có thể' t hoàn toàn tìm ra nó

TRẢ LỜI: Mặc dù cả hai giải pháp dưới đây từ @artm và @LukStorms dường như hoạt động, tôi nhận thấy giải pháp ngắn gọn hơn và dễ đọc hơn. Cảm ơn cả hai người! Trợ giúp tuyệt vời về một câu hỏi khó. Tôi chỉ ước tôi có thể trả lời cho cả hai bạn

Answer 1

Đây là ví dụ sử dụng CTE đệ quy để kết nối các bản sao đó.

Nhưng để đảm bảo rằng các bản sao đều theo cả hai hướng, CTUP DUPES được sử dụng.

declare @DuplicateTest table (Master int, Dupe int); 

insert into @DuplicateTest (Master, Dupe) values 
(3,6),(6,7),(2,7), 
(20,25),(75,25); 

;with DUPES as 
(
    select distinct Master as Dupe1, Dupe as Dupe2 from @DuplicateTest 
    union 
    select distinct Dupe, Master from @DuplicateTest 
) 
,RCTE as 
(
    select Dupe1 as Base, 0 as Level, Dupe1, Dupe2 
    from DUPES 

    union all 

    select r.Base, (r.Level + 1), d.Dupe1, d.Dupe2 
    from RCTE r 
    join DUPES d on (r.Dupe2 = d.Dupe1 
        and r.Dupe1 != d.Dupe2 -- don't loop on the reverse 
        and r.Base != d.Dupe2 -- don't repeat what we started from 
        and r.Level < 100) -- if the level gets to big it's most likely a loop 
) 
select min(Dupe2) as Master, Base as Dupe 
from RCTE 
group by Base 
having Base > min(Dupe2) 
order by Base; 

Answer 2

Hãy thử điều này. Lấy min của master từ bảng của bạn với một CTE và cross tham gia vào tất cả các giá trị khác trong bảng.

;WITH minmaster as (select MIN(MASTER) master 
FROM myTable) 
select distinct m.master 
, i.dupe 
from minmaster m 
cross join (select dupe dupe from myTable union all select master from myTable) i 
WHERE i.dupe <> m.master 

Cập nhật:

Sau khi chỉnh sửa của bạn với nhiều hàng dưới đây làm việc mặc dù tôi không chắc chắn nếu đó là giải pháp tốt nhất.Logic được bắt đầu với dupe chính đầu tiên (vì dữ liệu được sắp xếp bởi master), nếu dupe tồn tại trên cột thứ 2, nơi cột đầu tiên không bằng master hiện tại, sau đó lấy cùng một master, nếu không thì dùng master tiếp theo. Thật khó để giải thích, một người khác có thể tìm thấy một giải pháp dễ dàng hơn.

;WITH myTable AS 
(SELECT 2 MASTER, 7 dupe 
UNION all SELECT 3, 6 
UNION all SELECT 6, 7 
UNION all SELECT 20, 25 
UNION all SELECT 75, 25 
UNION all SELECT 100, 125 
UNION all SELECT 150, 300 
UNION all SELECT 180, 300 
) 
, cte AS 
(
SELECT m.master L, m.dupe R, ROW_NUMBER() OVER (ORDER BY master) rnkC 
FROM myTable m 
) 
, cte2 AS 
(
SELECT m.master L, m.dupe R, ROW_NUMBER() OVER (ORDER BY master) rnkC2 
FROM myTable m 
) 
, cteCur AS 
(
SELECT TOP 1 cte.l, cte.R, cte.rnkC 
FROM cte 
UNION ALL 
SELECT 
CASE WHEN cteCur.r IN (SELECT dupe 
         FROM myTable 
         WHERE MASTER <> cteCur.L AND dupe = cteCur.R) 
    THEN cteCur.L 
    ELSE (SELECT cte2.L 
      FROM cte2 
      WHERE cte2.rnkC2 = cteCur.rnkC + 1) 
    END 
, CASE WHEN cteCur.r IN (SELECT dupe 
          FROM myTable 
          WHERE MASTER <> cteCur.L AND dupe = cteCur.R) 
     THEN (SELECT cte2.L 
       FROM cte2 
       WHERE cte2.R = cteCur.R AND cte2.L <> cteCur.L) 
     ELSE (SELECT cte2.R 
       FROM cte2 
       WHERE cte2.rnkC2 = cteCur.rnkC + 1) 
     END 
, cteCur.rnkC + 1 
FROM cteCur 
WHERE cteCur.L IS NOT NULL 
) 
SELECT cteCur.L Master 
, cteCur.R Dupe 
FROM cteCur 
WHERE L IS NOT NULL 
ORDER BY L, R 

Answer 3

Đến muộn bữa tiệc, nhưng điều bạn muốn là tìm các tập hợp rời nhau. Nếu bạn quan tâm về hiệu quả, có một thuật toán cực kỳ nhanh cho điều này, và nó liên quan đến cấu trúc dữ liệu được gọi là UnionFind. Nó có vẻ là nhanh hơn thậm chí sắp xếp ...

Googling cho triển khai SQL, tôi đã dẫn there