用户的 PHP/MYSQL 日期时间范围重叠

Question

我需要帮助(为了更好地理解，请参阅附图)，因为我完全无助。

如您所见，我有用户，他们将开始和结束日期时间存储在我的数据库中，格式为 YYYY-mm-dd H:i:s。现在我需要根据最频繁的时间范围重叠(对于大多数用户)找出所有用户的重叠。我想为大多数用户获得 3 个最常出现的数据时间重叠。我该怎么做？

我不知道应该使用哪个 mysql 查询，或者从数据库中选择所有日期时间(开始和结束)并在 php 中处理它可能会更好(但是如何处理？)。如图像结果所示，例如时间 8.30 - 10.00 是用户 A+B+C+D 的结果。

Table structure:
UserID | Start datetime | End datetime
--------------------------------------
A | 2012-04-03 4:00:00 | 2012-04-03 10:00:00
A | 2012-04-03 16:00:00 | 2012-04-03 20:00:00
B | 2012-04-03 8:30:00 | 2012-04-03 14:00:00
B | 2012-04-06 21:30:00 | 2012-04-06 23:00:00
C | 2012-04-03 12:00:00 | 2012-04-03 13:00:00
D | 2012-04-01 01:00:01 | 2012-04-05 12:00:59
E | 2012-04-03 8:30:00 | 2012-04-03 11:00:00
E | 2012-04-03 21:00:00 | 2012-04-03 23:00:00

Answer 1

您实际上拥有的是集合的集合，并且想要确定其中是否有任何集合具有非零交集。当试图在嵌套集中查找节点的所有祖先时，这正是人们提出的问题。

我们可以证明，对于每个重叠，至少有一个时间窗口的开始时间落在所有其他重叠时间窗口内。使用这个花絮，我们不需要在一天中实际构建人工时间段。只需要一个开始时间，看看它是否与任何其他时间窗口相交，然后计算相交的数量。

那么查询是什么？

/*SELECT*/
SELECT DISTINCT
    MAX(overlapping_windows.start_time) AS overlap_start_time,
    MIN(overlapping_windows.end_time) AS overlap_end_time ,
    (COUNT(overlapping_windows.id) - 1) AS num_overlaps
FROM user_times AS windows
INNER JOIN user_times AS overlapping_windows
ON windows.start_time BETWEEN overlapping_windows.start_time AND overlapping_windows.end_time
GROUP BY windows.id
ORDER BY num_overlaps DESC;

根据您的表大小和您计划运行此查询的频率，在其上删除空间索引可能是值得的(见下文)。

更新

如果您经常运行此查询，则需要使用空间索引。由于基于范围的遍历(即 start_time 是否落在开始/结束范围之间)，BTREE 索引不会为您做任何事情。它必须是空间性的。

ALTER TABLE user_times ADD COLUMN time_windows GEOMETRY NOT NULL DEFAULT 0;
UPDATE user_times SET time_windows = GeomFromText(CONCAT('LineString( -1 ', start_time, ', 1 ', end_time, ')'));
CREATE SPATIAL INDEX time_window ON user_times (time_window);

然后您可以更新上面查询中的 ON 子句以读取

ON MBRWithin( Point(0,windows.start_time), overlapping_windows.time_window )

这将为您提供查询的索引遍历。同样，仅当您计划经常运行查询时才执行此操作。

空间索引归功于 Quassoni's blog .