在SQL中实现两列递归匹配并生成关联集群

问题背景 #

现有包含Col_X和Col_Y两列的关联数据，示例如下：

需要将所有直接或间接关联的元素聚合为一个集群字符串，最终输出如下结果：

测试数据可通过以下SQL生成：

select 'a' as x, 'b' as y union all 
select 'b' as x, 'c' as y union all 
select 'c' as x, 'd' as y union all 
select 'd' as x, 'e' as y union all 
select 'f' as x, 'g' as y union all 
select 't' as x, 'y' as y union all 
select 'y' as x, 'r' as y union all 
select 'q' as x, 'w' as y union all 
select 'n' as x, 'm' as y union all 
select 'm' as x, 'k' as y union all 
select 'm' as x, 'z' as y

解决方案（支持递归CTE的数据库） #

使用递归公共表表达式（CTE）识别所有连通分量，再聚合为集群字符串：

WITH RECURSIVE all_nodes AS (
    -- 提取所有唯一节点
    SELECT x AS node FROM (
        select 'a' as x, 'b' as y union all 
        select 'b' as x, 'c' as y union all 
        select 'c' as x, 'd' as y union all 
        select 'd' as x, 'e' as y union all 
        select 'f' as x, 'g' as y union all 
        select 't' as x, 'y' as y union all 
        select 'y' as x, 'r' as y union all 
        select 'q' as x, 'w' as y union all 
        select 'n' as x, 'm' as y union all 
        select 'm' as x, 'k' as y union all 
        select 'm' as x, 'z' as y
    ) t
    UNION
    SELECT y AS node FROM (
        select 'a' as x, 'b' as y union all 
        select 'b' as x, 'c' as y union all 
        select 'c' as x, 'd' as y union all 
        select 'd' as x, 'e' as y union all 
        select 'f' as x, 'g' as y union all 
        select 't' as x, 'y' as y union all 
        select 'y' as x, 'r' as y union all 
        select 'q' as x, 'w' as y union all 
        select 'n' as x, 'm' as y union all 
        select 'm' as x, 'k' as y union all 
        select 'm' as x, 'z' as y
    ) t
),
connected_components AS (
    -- 初始：每个节点自身作为根节点
    SELECT node AS root, node AS member
    FROM all_nodes
    UNION ALL
    -- 递归：遍历所有双向关联的节点，扩展连通分量
    SELECT cc.root, an.node
    FROM connected_components cc
    JOIN (
        -- 构建双向关联关系
        select x, y from (
            select 'a' as x, 'b' as y union all 
            select 'b' as x, 'c' as y union all 
            select 'c' as x, 'd' as y union all 
            select 'd' as x, 'e' as y union all 
            select 'f' as x, 'g' as y union all 
            select 't' as x, 'y' as y union all 
            select 'y' as x, 'r' as y union all 
            select 'q' as x, 'w' as y union all 
            select 'n' as x, 'm' as y union all 
            select 'm' as x, 'k' as y union all 
            select 'm' as x, 'z' as y
        ) t
        UNION
        select y, x from (
            select 'a' as x, 'b' as y union all 
            select 'b' as x, 'c' as y union all 
            select 'c' as x, 'd' as y union all 
            select 'd' as x, 'e' as y union all 
            select 'f' as x, 'g' as y union all 
            select 't' as x, 'y' as y union all 
            select 'y' as x, 'r' as y union all 
            select 'q' as x, 'w' as y union all 
            select 'n' as x, 'm' as y union all 
            select 'm' as x, 'k' as y union all 
            select 'm' as x, 'z' as y
        ) t
    ) links ON cc.member = links.x
    JOIN all_nodes an ON links.y = an.node
    -- 避免重复添加已在当前分量中的节点
    WHERE an.node NOT IN (SELECT member FROM connected_components WHERE root = cc.root)
),
unique_clusters AS (
    -- 为每个节点确定唯一的集群根节点（取最小根节点去重）
    SELECT member, MIN(root) AS cluster_id
    FROM connected_components
    GROUP BY member
)
-- 聚合每个集群的节点为有序字符串
SELECT GROUP_CONCAT(DISTINCT member ORDER BY member) AS Cluster
FROM unique_clusters
GROUP BY cluster_id;

逻辑说明 #

1. all_nodes：收集所有出现在Col_X和Col_Y中的唯一节点，确保没有遗漏任何元素。
2. connected_components：通过递归遍历，把所有直接或间接关联的节点归到同一个连通分量下，同时处理双向关联（比如a→b和b→a都被纳入）。
3. unique_clusters：由于递归过程中一个节点可能被多个根节点关联，这里取每个节点对应的最小根节点，保证每个集群只被统计一次。
4. 最后通过GROUP_CONCAT将同一集群的节点按顺序拼接成字符串，得到目标结果。

内容的提问来源于stack exchange，提问作者MarcoPolo