PostgreSQL递归SQL查询：查找与John Smith最多3度分隔的同专业学生

需求说明 #

需要找出与学生John Smith最多3度分隔的所有同专业学生，分隔度定义如下：

• 1度分隔：两名学生修读同一门课程
• 2度分隔：存在中间学生，分别与两人修读同一门课程
• 3度分隔：存在中间学生，分别与两名2度分隔的学生修读同一门课程

仅计算同专业学生间的分隔度，一名学生可拥有多个专业。

涉及表结构 #

假设存在以下3张表（补充专业关联表以满足同专业筛选需求）：

• students: 存储学生基本信息
  • sid: 学生唯一ID（主键）
  • name: 学生姓名
• StudentInCourse: 存储学生选课关系
  • sid: 学生ID
  • courseNumber: 课程编号
• student_majors: 存储学生与专业的关联（一名学生对应多条记录）
  • sid: 学生ID
  • major: 专业名称

递归SQL查询实现 #

WITH RECURSIVE student_connections AS (
    -- 锚点：获取John Smith的信息，以及所有与他同专业的学生初始集合，分隔度为0（自己）
    SELECT
        s1.sid AS source_sid,
        s2.sid AS target_sid,
        0 AS degree
    FROM students s1
    JOIN student_majors m1 ON s1.sid = m1.sid
    JOIN student_majors m2 ON m1.major = m2.major
    JOIN students s2 ON m2.sid = s2.sid
    WHERE s1.name = 'John Smith'
    GROUP BY s1.sid, s2.sid

    UNION ALL

    -- 递归部分：通过课程关联，找到下一度分隔的同专业学生
    SELECT
        sc.source_sid,
        s_new.sid AS target_sid,
        sc.degree + 1 AS degree
    FROM student_connections sc
    -- 找到当前目标学生修读的课程
    JOIN StudentInCourse sic_current ON sc.target_sid = sic_current.sid
    -- 通过课程找到修读同一门课的其他学生
    JOIN StudentInCourse sic_new ON sic_current.courseNumber = sic_new.courseNumber
        AND sic_new.sid != sc.target_sid
    -- 确保新学生与源学生（John Smith）同专业
    JOIN student_majors m_source ON sc.source_sid = m_source.sid
    JOIN student_majors m_new ON sic_new.sid = m_new.sid
        AND m_source.major = m_new.major
    JOIN students s_new ON sic_new.sid = s_new.sid
    -- 排除已经记录过的连接，避免循环
    WHERE NOT EXISTS (
        SELECT 1
        FROM student_connections sc_exist
        WHERE sc_exist.source_sid = sc.source_sid
            AND sc_exist.target_sid = s_new.sid
    )
    -- 限制分隔度不超过3
    AND sc.degree < 3
)
-- 最终查询：获取所有符合条件的学生姓名，排除John Smith自己
SELECT DISTINCT s.name
FROM student_connections sc
JOIN students s ON sc.target_sid = s.sid
WHERE sc.degree BETWEEN 1 AND 3
ORDER BY s.name;

代码说明 #

1. 锚点部分：先定位John Smith，通过student_majors表找到所有和他共享至少一个专业的学生，作为初始集合，分隔度设为0（代表John Smith自己）。
2. 递归部分：
   • 从当前已找到的学生集合出发，通过StudentInCourse找到他们修读的课程，进而找到修读同一课程的其他学生。
   • 再次通过student_majors确保这些新学生和John Smith同专业。
   • 使用NOT EXISTS避免重复记录同一学生连接，防止循环。
   • 限制递归深度，确保分隔度不超过3。
3. 最终查询：去重后获取所有分隔度1-3的学生姓名，排除John Smith本人。

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