sql - T-SQL 包含所有行 ID 的最少公共(public)日期集

Question

我的表 (@MyTable) 是一个包含开始日期和结束日期(含)的 ID 列表，表示当 ID 出现在每天接收一次的文件中的天数间隔:

ID    Start_Date    End_Date
1     10/01/2014    12/15/2014
2     11/05/2014    03/03/2015
3     12/07/2014    12/09/2014
4     04/01/2015    04/15/2015

每个 ID 只出现一次，即只有 1 个关联的时间间隔，Start_Dates 和 End_dates 之间的间隔可以(但不一定)跨不同的 ID 重叠。我需要一个 SQL 查询来查找日期集，当这些日期集的文件合并时，每个 ID 将至少出现一次，并且日期数尽可能少。在上表中，解决方案可能是这两个日期:

File_Date     ID(s)
12/07/2015    1,2,3
04/01/2015    4

但是对于这个例子，ID(3) 的 Start_date 和 End_date 之间的任何 1 个日期加上 ID(4) 的 Start_date 和 End_date 之间的 1 个日期都是一个解决方案。

实际数据由 10,000 个不同的 ID 组成。可能的文件日期的日期范围是 04/01/2014 - 07/01/2015。每个日常文件都非常大，必须手动下载，因此我想尽量减少我必须下载的数量以包含所有 ID。

到目前为止，我有一个 CTE，它为每个 ID 的 Start_Date 和 End_date 之间的所有日期生成单独的行:

;WITH cte (ID, d)
AS
(
    SELECT 
        tbl.ID AS ID,
        tbl.Start_Date AS d
    FROM @MyTable tbl
    UNION ALL
    SELECT 
        tbl.ID AS ID,
        DATEADD(DAY, 1, cte.d) AS d
    FROM cte
    INNER JOIN 
    @MyTable tbl ON cte.ID = tbl.ID
    WHERE cte.d < tbl.End_Date
)
SELECT
    ID AS ID,
    d AS File_Date 
FROM cte
ORDER BY ID,d
OPTION (MaxRecursion 500)

使用@MyTable 的示例结果是:

ID    File_Date
1     10/01/2014
1     10/02/2014
1     10/03/2014
1     etc...

我的想法是确定所有 ID 中最常见的 File_Date，然后在所有剩余的 ID 中选择下一个最常见的 File_Date，依此类推……但我被卡住了。用更数学的术语来说，我试图找到包含所有项目 (ID) 的最少集合 (File_Dates)，类似于 https://softwareengineering.stackexchange.com/questions/263095/finding-the-fewest-sets-which-contain-all-items ，但我不关心最小化重复项。最终结果不必包括哪些 ID 出现在哪些 File_Dates 中；我只需要知道所有的 File_Dates。

我正在使用 MS SQL Server 2008。

Answer 1

继续您开始的工作。通过此方法找到的结果不是最佳的，但对于您的目的来说已经足够好了。

对于每个 ID，为范围内的每一天生成一组行。你已经知道如何去做了，虽然我会使用一个数字表，而不是每次都用 CTE 即时生成它，但这并不重要。

将结果放入临时表。它将有 10,000 个 ID * ~400 天 = ~400 万行。临时表有两列 (ID, FileDate)。创建适当的索引。我将从两个开始:(ID, FileDate) 和 (FileDate, ID)。使其中之一聚集和主键。我会尝试将 (FileDate, ID) 作为集群主键。

然后循环处理:

查找具有最多 ID 的日期:

SELECT TOP(1) @VarDate = FileDate
FROM #temp
GROUP BY FileDate
ORDER BY COUNT(*) DESC;

在最终结果的另一个临时表中记住找到的日期(以及可选的 ID)。

从大表中删除日期和该日期对应的ID。

DELETE FROM #temp
WHERE FileDate = @VarDate
OR ID IN
(
    SELECT t2.ID
    FROM #temp AS t2
    WHERE t2.FileDate = @VarDate
)

重复循环直到#temp 中没有行。