SQL去重元组列表

Question

SQL去重元组列表

6

我有一个包含两列ID的表格，如下所示：

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

每行代表一个SQL表中被认为是彼此重复的两行记录的ID。

这个表可以包含许多千条目，除了Master列按升序排列之外，没有数据保证。任何一列都可能包含与另一列相同的ID，可能是不同的或相同的伙伴ID。再次强调-没有保证。

我希望从这张表中得到主ID及其所有可能的副本索引，如下所示。

期望的结果：

1.应保留最低ID作为主ID

2.所有后续的重复项都应映射回同一个（最低ID）主ID

对于上述要求，所需输出如下所示（但列不必排序）：

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

我发现这个问题很难解释，所以我的谷歌搜索没有得到太多的结果。我想必须有一个算法可以迭代遍历这样的元组列表并发现重复。

感谢任何帮助！

编辑：我修改了示例表以更好地解释它们可能的内容。

一些注意事项：

没有连锁的保证。它可能是一个大链，许多小链或根本没有链。
不能保证所有对在表中的反向顺序出现在其他地方

从我所看到的，这个问题似乎是递归的，我认为LukStorms走在正确的轨道上，但我还不能完全弄清楚

回答：虽然@artm和@LukStorms的两个解决方案都似乎可以工作，但我发现后者更加简洁易读。非常感谢您们在一个难题上提供的帮助。我只希望能把答案授予你们两个。

- Sean Missingham

3

你能否更好地解释你的逻辑？从原始表中看，你的结果集中的2和3之间的关系是什么性质？请翻译此内容。 - Tim Biegeleisen

当然，3和6是重复的，6和7是重复的，7和2也是重复的。保留集合中最小的ID（2），ID为3、6和7都是2的副本。 - Sean Missingham

3个回答

2

这里有一个使用递归CTE连接那些重复数据的示例。

但是要确保重复数据是双向的，需要使用DUPES CTE。

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;

- LukStorms

我喜欢你对RCTE的想法，但是这个过程似乎假定整个过程是一个链，并且它是循环的，因为它以原始对相反的方式关闭。如果你在底部去掉了7,2对，它就不再起作用了，而结果应该仍然相同。如果可以，请看一下修改后的例子 :) - Sean Missingham

1

@SeanMissingham确实，基于之前的测试数据有这样的假设。但我不认为它是“一个链”，更像是获取分支。答案已经更新。 - LukStorms

1

来晚了，但是你似乎想要找到不连通的集合。如果你关心效率，有一个非常快的算法可以做到这一点，它涉及到称为并查集的数据结构。它似乎比排序甚至更快...

在谷歌中搜索SQL实现，我被引导到那里。

- ntg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- artm · Accepted Answer

尝试这个方法。使用CTE从表中获取主键的最小值，并与表中的所有其他值进行交叉连接。

;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

更新：

在您添加了更多的行之后，下面的解决方案可以工作，尽管我不确定是否是最佳解决方案。逻辑是从第一个主副本开始（因为数据按主副本排序），如果该副本存在于第二列中且第一列不等于当前主副本，则取相同的主副本；否则取下一个主副本。这很难解释，其他人可能能找到一个更简单的解决方案。

;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