如何基于section_and_time表实现无重复重叠课程查询？

需求背景 #

已知通过以下关系代数生成section_and_time表：

section_and_time =
    π course_id, sec_id, semester, year, day, start_hr, start_min, end_hr, end_min
        (section ⨝ time_slot)

需要仅基于该表，生成无重复的重叠课程关系，结果格式为(course_id_1, sec_id_1, semester_1, year_1, course_id_2, sec_id_2, semester_2, year_2)，且不能出现互为镜像的重复条目（例如(A,B)和(B,A)只能保留一条）。

原SQL的问题 #

你提供的原查询存在三个核心问题：

1. 时间重叠判断逻辑错误：仅否定S1.end_hr < S2.start_hr AND S1.end_min < S2.start_min，会误判大量实际重叠的情况（比如S1结束小时小于但分钟大于S2开始分钟，或者S1的时间段完全包含S2）。
2. 未避免镜像重复：仅用S1.course_id != S2.course_id会同时生成(A,B)和(B,A)两条重复结果。
3. 未限定同一学期/学年/日期：不同学期、不同天的课程即使时间数值重叠，也不属于需要统计的重叠课程。

解决方案 #

关系代数表达式

通过自连接、严格的过滤条件实现需求：

π course_id_1, sec_id_1, semester_1, year_1, course_id_2, sec_id_2, semester_2, year_2
    (σ 
        -- 限定同一学期、学年、同一天
        (semester_1 = semester_2 ∧ year_1 = year_2 ∧ day_1 = day_2) 
        ∧ 
        -- 判断时间重叠：两个时间段有交集
        ( (start_hr_1 < end_hr_2) 
          ∨ (start_hr_1 = end_hr_2 ∧ start_min_1 < end_min_2) 
          ∨ (start_hr_2 < end_hr_1) 
          ∨ (start_hr_2 = end_hr_1 ∧ start_min_2 < end_min_1) )
        ∧
        -- 避免镜像重复：通过ID排序确保每对组合只出现一次
        (course_id_1 < course_id_2 ∨ (course_id_1 = course_id_2 ∧ sec_id_1 < sec_id_2))
    -- 对自连接的两张表重命名，区分列
    (ρ (course_id_1, sec_id_1, semester_1, year_1, day_1, start_hr_1, start_min_1, end_hr_1, end_min_1) section_and_time 
     × 
     ρ (course_id_2, sec_id_2, semester_2, year_2, day_2, start_hr_2, start_min_2, end_hr_2, end_min_2) section_and_time )
)

修正后的SQL查询

对应SQL写法，逻辑更直观且符合需求：

SELECT 
    S1.course_id, S1.sec_id, S1.semester, S1.year,
    S2.course_id, S2.sec_id, S2.semester, S2.year
FROM section_and_time S1
JOIN section_and_time S2
    -- 限定同一学期、学年、同一天
    ON S1.semester = S2.semester
    AND S1.year = S2.year
    AND S1.day = S2.day
    -- 时间重叠判断：S1开始早于S2结束，且S2开始早于S1结束
    AND (
        (S1.start_hr < S2.end_hr)
        OR (S1.start_hr = S2.end_hr AND S1.start_min < S2.end_min)
    )
    AND (
        (S2.start_hr < S1.end_hr)
        OR (S2.start_hr = S1.end_hr AND S2.start_min < S1.end_min)
    )
    -- 避免镜像重复：确保S1的标识严格小于S2，每对组合只出现一次
    AND (
        S1.course_id < S2.course_id
        OR (S1.course_id = S2.course_id AND S1.sec_id < S2.sec_id)
    );

关键逻辑说明 #

• 时间重叠判断：通过双向判断（A开始早于B结束，且B开始早于A结束）覆盖所有时间段交集场景，包括包含、部分重叠等情况。
• 去重逻辑：利用课程ID或小节ID的严格排序，确保每对重叠课程只生成一条结果，彻底避免镜像重复。
• 范围限定：仅统计同一学期、学年、同一天的课程，过滤掉无意义的跨期匹配。

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