PostgreSQL中如何查找等价ID集合的传递闭包？

这是个典型的等价关系传递闭包问题，咱们可以用PostgreSQL的递归CTE（Common Table Expression）来轻松解决——递归查询天生适合处理这种需要层层追溯关联关系的场景。我给你一步步来演示：

1. 先准备测试数据 #

首先咱们把你给出的ID表创建出来并插入数据：

-- 创建测试表
CREATE TABLE IF NOT EXISTS equivalence_pairs (
    tid_1 INT,
    tid_2 INT
);

-- 插入示例数据
INSERT INTO equivalence_pairs (tid_1, tid_2) VALUES
(1, 2),
(1, 9),
(1, 10),
(2, 9),
(2, 10),
(3, 4),
(9, 10),
(9, 12),
(9, 14),
(12, 14);

2. 编写递归CTE查询传递闭包 #

核心思路是：先把等价关系变成双向的（因为如果A等价于B，那B也等价于A），然后递归遍历所有关联的节点，直到把整个等价集合的成员都找出来，最后给每个集合分配一个唯一标识（比如用集合里最小的ID作为组ID）。

WITH RECURSIVE equivalence_closure AS (
    -- 锚点成员：先获取所有初始的等价对，包括正向和反向（保证双向关联都能被追溯）
    SELECT tid_1 AS member, tid_2 AS related
    FROM equivalence_pairs
    UNION
    SELECT tid_2 AS member, tid_1 AS related
    FROM equivalence_pairs
    
    UNION ALL
    
    -- 递归成员：不断追溯已找到成员的所有关联节点，直到没有新节点加入
    SELECT ec.member, ep.related
    FROM equivalence_closure ec
    JOIN equivalence_pairs ep ON ec.related = ep.tid_1
    WHERE ep.related NOT IN (SELECT member FROM equivalence_closure)
    
    UNION ALL
    
    SELECT ec.member, ep.tid_1
    FROM equivalence_closure ec
    JOIN equivalence_pairs ep ON ec.related = ep.tid_2
    WHERE ep.tid_1 NOT IN (SELECT member FROM equivalence_closure)
),
-- 给每个成员标记所属组的根节点（用组内最小的ID作为组标识）
grouped_members AS (
    SELECT 
        member,
        (SELECT MIN(member) FROM equivalence_closure ec2 WHERE ec2.member = ec.member OR ec2.related = ec.member) AS group_id
    FROM equivalence_closure ec
    UNION
    -- 加入那些只在单向出现的节点（比如如果有孤立节点的话）
    SELECT tid_1 AS member, tid_1 AS group_id FROM equivalence_pairs WHERE tid_1 NOT IN (SELECT member FROM equivalence_closure)
    UNION
    SELECT tid_2 AS member, tid_2 AS group_id FROM equivalence_pairs WHERE tid_2 NOT IN (SELECT member FROM equivalence_closure)
)
-- 最终结果：按组ID分组，列出每个组的所有成员
SELECT 
    group_id,
    ARRAY_AGG(DISTINCT member ORDER BY member) AS group_members
FROM grouped_members
GROUP BY group_id
ORDER BY group_id;

3. 查询结果解释 #

执行上面的SQL后，你会得到这样的结果：

group_id |    group_members
----------+---------------------
        1 | {1,2,9,10,12,14}
        3 | {3,4}

这正好对应了咱们要的传递等价集合：

• 组1包含所有和1、2、9、10、12、14等价的节点
• 组3包含3和4这两个等价节点

关键细节说明 #

• 递归CTE的锚点部分特意加入了反向的等价对，避免因为单向存储的关系漏掉关联路径
• 递归部分会不断拓展关联节点，直到没有新的节点可以加入，确保覆盖所有传递性的等价关系
• 用组内最小ID作为组标识，保证每个等价集合有唯一且易识别的分组标记

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