database-design - 一维内非重叠范围的数据结构

Question

我需要一个可以在一个维度内存储非重叠范围的数据结构。尺寸的整个范围不必完全覆盖。

一个示例是 session 室调度程序。维度是时间。没有两个时间表可以重叠。 session 室并非总是预定的。换句话说，对于给定的时间，最多可以有一个时间表。

一种快速的解决方案是针对一个范围来存储开始时间和结束时间。

Range {
    Date start
    Date end
}

这是非规范的，需要容器不强制重叠。对于两个相邻的范围，前一个末端将与下一个起始处成为多余。

另一种方案可能涉及在每个范围内存储一个边界值。但是对于连续的范围序列，边界值总是比范围多一个。为了解决这个问题，可以将序列表示为交替的边界值和范围:

B =边界值，r =范围

B-r-B-r-B

数据结构可能类似于:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

从本质上讲，它是一个具有交替类型的双链表。

最终，无论我使用什么数据结构，都将在内存(应用程序代码)和关系数据库中表示。

我很好奇学术界或行业尝试过的解决方案是否存在。

Answer 1

表示数据的规范化方法是为每个时间单位存储一条记录。这可以在 session 安排应用程序的示例中完成。您的约束将是

(RoomId, StartTime)

在连续范围的情况下，您必须存储2个东西，一个边界，第二个边界或长度。通常是通过存储第二个边界，然后在该两个边界上创建约束来完成的

(boundary not between colBoudaryA and colBoundaryB)

附加的约束是

(startBoundary < endBoundary)