T-SQL наименьших наборов общих дат, включающих все идентификаторы строк

Question

Моя таблица (@MyTable) представляет собой список идентификаторов с датами начала и датами окончания (включительно), которые представляют собой интервал дней, когда идентификатор появляется в файле, который принимается один раз в день:

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 

Каждый идентификатор появляется только один раз, т.е. только имеет один временной интервал, связанный, а интервалы между Start_Dates и End_dates может (но не обязательно) перекрытия между различными идентификаторами. Мне нужен SQL-запрос для поиска наборов дат, где каждый ID будет отображаться хотя бы один раз, когда файлы из этих наборов дат будут объединены в наименьшее количество дат, насколько это возможно. В таблице выше решения может быть эти 2 даты:

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

Но для примера любой 1 день между ID (3) «ы Дата_начала и end_date & в сочетании с 1 дня между ID (4)» ы start_date и End_date будет решением.

Фактические данные состоят из 10 000 различных идентификаторов. Диапазон дат возможных дат файла: 04/01/2014 - 07/01/2015. Каждый ежедневный файл очень большой по размеру и должен быть загружен вручную, поэтому я хочу свести к минимуму число, которое я должен загрузить, чтобы включить все идентификаторы.

До сих пор я КТР, что приводит в отдельных строках для всех дат между Дата_начала и датой_окончания каждого ID:

;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... 

Мое мышление было определить наиболее распространенный File_Date среди всех идентификаторов, а затем выбрать следующий наиболее распространенный File_Date среди всех оставшихся идентификаторов и т. д. ... но я застрял. Чтобы выразить это более математически, я пытаюсь найти наименьшие множества (File_Dates), которые содержат все элементы (ID), похожие на https://softwareengineering.stackexchange.com/questions/263095/finding-the-fewest-sets-which-contain-all-items, но я не забочусь о минимизации дубликатов. Конечным результатам не нужно включать, какие идентификаторы появляются в файле File_Dates; Мне просто нужно знать все файлы File_Dates.

Я использую MS SQL Server 2008.

Answer 1

Просто идти с того, что вы начали. Результат, найденный этим методом, не является оптимальным, но может быть достаточно хорош для ваших целей.

Для каждого идентификатора генерируйте набор строк для каждого дня в диапазоне. Вы уже знаете, как это сделать, хотя я бы использовал для этого таблицу чисел, вместо того, чтобы генерировать ее «на лету» с помощью CTE каждый раз, но это не имеет большого значения.

Положить результат во временную таблицу. Он будет иметь 10 000 идентификаторов * ~ 400 дней = ~ 4M строк. Таблица темпа имеет два столбца (ID, FileDate). Создайте соответствующие индексы. Я бы начал с двух: на (ID, FileDate) и на (FileDate, ID). Сделайте один из них кластеризованным и первичным ключом. Я попытался бы сделать (FileDate, ID) в качестве кластеризованного первичного ключа.

Затем процесс в цикле:

Найти дату, которая имеет наибольшее количество идентификаторов:

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

Запомнить нашли дату (и необязательно его идентификаторы) в другой временной таблице для конечного результата.

Удалить дату и идентификаторы, которые соответствуют этой дате с большой таблицы.

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

Повторите цикл до тех пор, пока в #temp не будет строк.

Answer 2

Использование предложенного подхода В. Б. в и ответ от In SQL Server, how to create while loop in select в качестве модели:

;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 
    into #temp2 
FROM cte 
ORDER BY ID,d 
OPTION (MaxRecursion 500) 

Create Table #FileDates 
(
File_Date date 
) 

GO 

DECLARE @VarDate date 

WHILE EXISTS (select * from #temp2) 

BEGIN 

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

INSERT INTO #FileDates (File_Date) 
Values (@VarDate) 

DELETE from #temp2 
WHERE File_Date=@VarDate 
OR ID in 
(
    select t2.ID 
    from #temp2 as t2 
    where t2.File_Date = @VarDate 
) 

END 

SELECT * 
FROM #FileDates 
ORDER BY File_Date 

Взял 30 секунд, чтобы вернуть 40 даты файла в течение прибл. 4000 идентификаторов. Большое спасибо господину Баранову!