Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Как агрегировать последовательность дат (возможно gaps and islands)  [new]
uaggster
Member

Откуда:
Сообщений: 960
 		Коллеги, приветствую!

Не могу решить задачу.
Возможно, это gaps and islands, но не могу нормально адаптировать примеры.
Помогите!

Итак, есть энное, в разрезе каждого ключа, количество примыкающих временных отрезков, либо DBEG следующего = DEND предыдущего, либо DBEG следующего = DEND + 1 день предыдущего:
if object_id('tempdb..#t') is not null
	Drop table #t
go

Create table #t (N int, [KEY] int, DBEG DATE, DEND DATE)

insert into #t
Values 
(1, 1, '20190101', '20190109'),
(2, 1, '20190109', '20190109'),
(3, 1, '20190109', '20190109'),
(4, 1, '20190109', '20190109'),
(5, 1, '20190109', '20190109'),
(6, 1, '20190109', '20190111'),
(7, 1, '20190111', '20190112'),
(8, 1, '20190111', '20190111'),
(9, 1, '20190113', '20190116'),
(10, 1, '20190118', '20190119'),
(11, 2, '20190101', '20190109'),
(12, 2, '20190102', '20190109'),
(13, 2, '20190109', '20190109'),
(14, 2, '20190109', '20190109'),
(100, 1, '20190103', '20190109')

Select * from #t

Нужно получить следующий результат:
1 1 ;1;2;3;4;5;6;7;8;9;20190101 20190116
10 1 ;10;20190118 20190119
11 2 ;11;12;13;14;20190102 20190109
100 1 ;100; 20190103 20190109

Т.е. для каждой цепочки, соответствующей определенному ключу, указать, собственно ключ, N первой записи цепочки, перечень всех N цепочки, ну и даты начала цепочки и конца цепочки.
Дело осложняется тем, что даты, в разрезе ключей, не попавшие точно на границу предыдущей цепочки с точностью до одного дня, даже если они попали внутрь цепочки - это уже другие цепочки!
См. N=10 - вне цепочки, т.к. за пределами одного дня, 100 - внутри цепочки, но не попала точно на дату.

Причем, вот ведь какая заковыка... Цепочка 100 - могла бы тоже стать родоначальницей собственной цепочки, т.к. к ней могли бы прицепляться узлы 2, 3 и т.д.
Но этого быть не должно, т.к. эти узлы уже были использованы для построения цепочки, начинающейся в более раннюю дату.

Однако, как я понимаю, одним запросом - это не решить, поэтому интересно любое решение!

Примечание:
Выращивание цепочки максимальной длины - не интересует. Для построении цепочки - берется первый подходящий узел, в порядке возрастания N.
30 окт 19, 18:56    [22006451]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
 		uaggster, вопросы:

1) Не логичнее сделать в первом случае цепочку 1;2;3;4;5;6;8;7;9;, т.к. 7-й может быть продолжением 8-го, а 8-й продолжением 7-го быть не может?

2)Ветвления как учитываются?
такой набор будет одной цепочкой или двумя?
01-01
01-03
01-05
03-07
05-08

3) Почему 12 не является отдельной веткой, а продолжает 11-й элемент? он ведь не соответствует правилу
автор
DBEG следующего = DEND предыдущего, либо DBEG следующего = DEND + 1 день предыдущего:


4) почему цепочка для key=2 начинается с 20190102, если у 11-го элемента DBEG = 20190101?

Сообщение было отредактировано: 31 окт 19, 11:17
31 окт 19, 11:14    [22006914]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4805
 		uaggster,

Заведите отдельную таблицу календаря. От неё LEFT JOIN или OUTER APPLY на ваши данные и поверх этого агрегат или что-то такое
31 окт 19, 13:34    [22007122]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
uaggster
Member

Откуда:
Сообщений: 960
Minamoto
uaggster, вопросы:

1) Не логичнее сделать в первом случае цепочку 1;2;3;4;5;6;8;7;9;, т.к. 7-й может быть продолжением 8-го, а 8-й продолжением 7-го быть не может?

2)Ветвления как учитываются?
такой набор будет одной цепочкой или двумя?
01-01
01-03
01-05
03-07
05-08

3) Почему 12 не является отдельной веткой, а продолжает 11-й элемент? он ведь не соответствует правилу
автор
DBEG следующего = DEND предыдущего, либо DBEG следующего = DEND + 1 день предыдущего:


4) почему цепочка для key=2 начинается с 20190102, если у 11-го элемента DBEG = 20190101?

Да, Minamoto, вы правы. Иллюстрация, приведенная мной - не совсем некорректна. Цепочка 1;2;3;4;5;6;8;7;9;.
Но, в принципе, порядок перечисления узлов - не особо важен, главное, чтобы все узлы цепочки попали в перечисление. Но да, так правильнее.

Ветвления не учитываются. Если через узел прошла цепочка - он выпадает из других цепочек.

Т.е., на мой взгляд, должно быть что-то вроде такого:
1. Для данного key ищем N с минимальной датой начала.
2. Делаем узел текущим.
3. Для даты окончания текущего узла - ищем примыкающий узел, первый по N.
Хотя, наверное, логичнее, из всех примыкающих узлов вначале выбрать а) те, которые начинаются в ту же дату, что и дата окончания примыкающего узла, и если таковых не найдено - то б) начинающиеся в следующий день.
Выбираем 1 узел с минимальной N, ранее не помеченный как использованный ни в одной цепочке, относящейся к данному key.
4. Помечаем его в списке пути, дату его окончания - считаем датой окончания цепочки.
5. Повторяем 2-4 до исчерпания всех потенциальных начал цепочек для данного key.
6. Повторяем 1-5 для всех key.

Но это - императивно.
Можно ли как то это сделать с минимальным количеством курсоров? Ну, с циклами хотя бы.

Это вроде как путь в орграфе, но построение пути или кратчайшего пути между двумя узлами - не нужно.
Нужно определить, как далеко можно продвинутся, согласно правилам п.3.
1 ноя 19, 08:57    [22007721]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
uaggster
Member

Откуда:
Сообщений: 960
 		Появилось редактирование сообщений???
Дас ист фантастишь!
... И 20 лет не прошло.
Спасибо!
1 ноя 19, 09:02    [22007725]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8350
 		uaggster,

почему строка 10 выпала из дерева, а строка 8 и 9 не выпала. Обе строки не попадают в правило продолжения цепочки, т.е. ожидаемый результат не верный.
1 ноя 19, 11:41    [22007920]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Владислав Колосов
uaggster,

почему строка 10 выпала из дерева, а строка 8 и 9 не выпала. Обе строки не попадают в правило продолжения цепочки, т.е. ожидаемый результат не верный.
8 и 9 не выпадают - они как раз ложатся в условие, если 8 будет идти после 6, 7-я после 8, а 9 - после 7
1 ноя 19, 12:08    [22007968]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
 		uaggster, мне немного стыдно за код, плюс я не уверен, что учел все граничные условия, проверяйте на разных случаях.

uaggster
Ветвления не учитываются. Если через узел прошла цепочка - он выпадает из других цепочек.

Вот это я не понял, поэтому сделал так, чтобы ответвление стало отдельной веткой.

Собственно, вот. Свой кейс добавил для удобства проверки:


if object_id('tempdb..#t') is not null
	Drop table #t
go
if object_id('tempdb..#cte') is not null
	Drop table #cte
go

create table #t (N int, [KEY] int, DBEG DATE, DEND DATE)

insert into #t
Values 
(1, 1, '20190101', '20190109'),
(2, 1, '20190109', '20190109'),
(3, 1, '20190109', '20190109'),
(4, 1, '20190109', '20190109'),
(5, 1, '20190109', '20190109'),
(6, 1, '20190109', '20190111'),
(7, 1, '20190111', '20190112'),
(8, 1, '20190111', '20190111'),
(9, 1, '20190113', '20190116'),
(10, 1, '20190118', '20190119'),
(11, 2, '20190101', '20190109'),
(12, 2, '20190102', '20190109'),
(13, 2, '20190109', '20190109'),
(14, 2, '20190109', '20190109'),
(100, 1, '20190103', '20190109'),
(200, 3, '20190101', '20190101'),
(201, 3, '20190101', '20190103'),
(202, 3, '20190101', '20190105'),
(203, 3, '20190103', '20190107'),
(204, 3, '20190105', '20190108');

WITH cte AS
(
    SELECT t1.N, t1.[KEY], ';' + CAST(t1.N AS varchar(MAX)) + ';' AS path, t1.DBEG, t1.DEND, CAST(1 AS int) AS rn, t1.N AS last_n
    FROM #t t1
    WHERE 
        NOT EXISTS (SELECT * 
                    FROM  #t t2 
                    WHERE  t2.[KEY] = t1.[KEY]
                        AND t2.N <> t1.N
                        AND (t2.DEND = t1.DBEG 
                             OR DATEADD(DAY, 1, t2.DEND) = t1.DBEG))
        OR EXISTS (SELECT * 
                    FROM #t t2 
                    WHERE t2.[KEY] = t1.[KEY]
                        AND t2.N < t1.N
                        AND (t2.DBEG = t1.DBEG
                             OR DATEADD(DAY, 1, t2.DBEG) = t1.DBEG)
                        AND t2.DEND > t2.DBEG
                        AND t1.DEND > t1.DBEG)
    UNION ALL
    SELECT cte.N, cte.[KEY], 
            cte.path + CAST(t1.N AS varchar(MAX)) + ';' AS path, 
            cte.DBEG, t1.DEND, 
            CAST(ROW_NUMBER() OVER (PARTITION BY cte.N ORDER BY t1.DBEG, t1.DEND) AS int),
            t1.N
    FROM #t t1
        INNER JOIN cte ON t1.[KEY] = cte.[KEY] AND (t1.DBEG = cte.DEND OR t1.DBEG = DATEADD(DAY, 1, cte.DEND))
    WHERE cte.rn = 1 
        AND cte.path NOT LIKE '%;' + CAST(t1.N AS varchar(MAX)) + ';%'
)
SELECT * INTO #cte FROM cte

--Удаляем хвосты одинаковых веток у старших N
DELETE
FROM t1
FROM #cte t1
    INNER JOIN #cte t2 ON t1.last_n = t2.last_n AND t1.N > t2.N

SELECT t1.N, t1.[KEY], t1.path, t1.DBEG, t1.DEND
FROM #cte t1
WHERE t1.rn = 1 
    AND NOT EXISTS (SELECT * 
                    FROM #cte t2 
                    WHERE (t2.path LIKE t1.path + '%' AND t2.path > t1.path))
ORDER BY t1.N
1 ноя 19, 12:10    [22007974]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8350
Minamoto
Владислав Колосов
uaggster,

почему строка 10 выпала из дерева, а строка 8 и 9 не выпала. Обе строки не попадают в правило продолжения цепочки, т.е. ожидаемый результат не верный.
8 и 9 не выпадают - они как раз ложатся в условие, если 8 будет идти после 6, 7-я после 8, а 9 - после 7


Насколько я владею арифметикой, порядок чисел такой: 6,7,8,9,10. То есть 8 никак не идет после 6, между ними 7. Т.е. "предыдущим" для 9 является 8, а не 7.
1 ноя 19, 12:30    [22008005]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Remind
Member

Откуда: UK
Сообщений: 523
 		Набросал решение, наверняка можно оптимизировать и уменьшить кол-во сканов.
Вывод самой цепочки зависит от версии SQL Server'a, можно сделать через STRING_AGG:
WITH cte AS
(
  SELECT t1.N AS N1, t1.[KEY], t1.DBEG, t1.DEND, t2.N AS N2, t2.DEND DEND2
  FROM #t t1
    LEFT JOIN #t t2
      ON t2.[KEY] = t1.[KEY] 
      AND t2.N > t1.N
      AND (DATEDIFF(DAY, t1.DEND, t2.DBEG) BETWEEN 0 and 1
        OR DATEDIFF(DAY, t1.DBEG, t2.DBEG) BETWEEN 0 and 1)
)
SELECT MIN(N1) as N, [KEY], MIN(DBEG) as DBEG, max(DEND2) as DEND
FROM cte
WHERE N2 is not null
GROUP BY [KEY]

UNION ALL

SELECT N1, [KEY], DBEG, DEND
FROM cte c1
WHERE N2 IS NULL
  AND NOT EXISTS (SELECT * FROM cte c2 WHERE c2.N2 = c1.N1)
1 ноя 19, 13:16    [22008065]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
 		Remind, добавляем в цепочку к 10-му 15-й элемент, и все разваливается...

insert into #t
Values 
(1, 1, '20190101', '20190109'),
(2, 1, '20190109', '20190109'),
(3, 1, '20190109', '20190109'),
(4, 1, '20190109', '20190109'),
(5, 1, '20190109', '20190109'),
(6, 1, '20190109', '20190111'),
(7, 1, '20190111', '20190112'),
(8, 1, '20190111', '20190111'),
(9, 1, '20190113', '20190116'),
(10, 1, '20190118', '20190119'),
(15, 1, '20190119', '20190121'),
(11, 2, '20190101', '20190109'),
(12, 2, '20190102', '20190109'),
(13, 2, '20190109', '20190109'),
(14, 2, '20190109', '20190109'),
(100, 1, '20190103', '20190109'),
(200, 3, '20190101', '20190101'),
(201, 3, '20190101', '20190103'),
(202, 3, '20190101', '20190105'),
(203, 3, '20190103', '20190107'),
(204, 3, '20190105', '20190108');
1 ноя 19, 13:26    [22008087]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Remind
Member

Откуда: UK
Сообщений: 523
 		Minamoto, точно, забыл про самое главное. Думаю теперь должно работать.
;WITH cte AS
(
  SELECT N1, [KEY], DBEG, DEND, N2, DEND2, SUM(RangeStart) OVER (PARTITION BY [KEY] ORDER BY N1) as grp
  FROM
  (
    SELECT t1.N AS N1, t1.[KEY], t1.DBEG, t1.DEND, t2.N AS N2, t2.DEND DEND2, 
      CASE WHEN LAG(t2.N) OVER (PARTITION BY t1.[KEY] ORDER BY t1.N) IS NULL THEN 1 ELSE 0 END AS RangeStart
    FROM #t t1
      LEFT JOIN #t t2
        ON t2.[KEY] = t1.[KEY] 
        AND t2.N > t1.N
        AND (DATEDIFF(DAY, t1.DEND, t2.DBEG) BETWEEN 0 and 1
          OR DATEDIFF(DAY, t1.DBEG, t2.DBEG) BETWEEN 0 and 1)
  ) t
)
SELECT MIN(N1) AS N, [KEY], MIN(DBEG) AS DBEG, MAX(DEND2) AS DEND
FROM cte
WHERE N2 IS NOT NULL
GROUP BY [KEY], grp

UNION ALL

SELECT N1, [KEY], DBEG, DEND
FROM cte c1
WHERE N2 IS NULL
  AND NOT EXISTS (SELECT * FROM cte c2 WHERE c2.N2 = c1.N1)
1 ноя 19, 14:13    [22008130]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
uaggster
Member

Откуда:
Сообщений: 960
 		Remind, вот одним местом чувствую, что здесь что-то не то!
 SELECT t1.N AS N1, t1.[KEY], t1.DBEG, t1.DEND, t2.N AS N2, t2.DEND DEND2, 
      CASE WHEN LAG(t2.N) OVER (PARTITION BY t1.[KEY] ORDER BY t1.N) IS NULL THEN 1 ELSE 0 END AS RangeStart
    FROM #t t1
      LEFT JOIN #t t2
        ON t2.[KEY] = t1.[KEY] 
        AND t2.N > t1.N
        AND (DATEDIFF(DAY, t1.DEND, t2.DBEG) BETWEEN 0 and 1
          OR DATEDIFF(DAY, t1.DBEG, t2.DBEG) BETWEEN 0 and 1

Дело в том, что первое подходящее продолжение цепочки - не обязательно с большим N по отношению к текущему узлу.
Подходящий N - может быть любым, в т.ч. и меньшим, чем текущий N.
Да, из подходящих продолжений цепочки - выбираем с меньшим N.
Нет, никто не гарантирует, что этот N больше N текущего узла.
1 ноя 19, 15:03    [22008174]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
uaggster
Member

Откуда:
Сообщений: 960
 		Minamoto, в целом, мысль понял. Попробую покатать на примерах.
Ну, после того как вкурю.

Не могу понять, где лошадь припрягается, как обходится момент, когда кончилась одна цепочка с для данного key, а следующая цепочка для данного key должна стартовать изнутри интервала предыдущей цепочки, попадись в ней "непримыкающий узел".
Ну, пример с узлом 100.
1 ноя 19, 15:12    [22008183]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
uaggster
Minamoto, в целом, мысль понял. Попробую покатать на примерах.
Ну, после того как вкурю.

Не могу понять, где лошадь припрягается, как обходится момент, когда кончилась одна цепочка с для данного key, а следующая цепочка для данного key должна стартовать изнутри интервала предыдущей цепочки, попадись в ней "непримыкающий узел".
Ну, пример с узлом 100.
Это в delete. Мы сначала строим все "правильные" цепочки, потом в delete удаляем те варианты, которые включают узел, встречающийся в другой цепочке, но имеют айдишник выше, чем у другой цепочки.
1 ноя 19, 15:24    [22008198]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
 		uaggster,

Сначала показалось, что монструозный WHERE в первой части CTE, предназначенный, чтобы найти правильные начала веток не нужен - мы можем построить вообще все варианты веток, и потом удалить неправильные.
Оказалось - поторопился - если ветку с 10, 15 развернуть, чтобы она начиналась с большего N (заменить 10 на 50), то ветка разваливается, а с WHERE - нет.

Сообщение было отредактировано: 1 ноя 19, 15:42
1 ноя 19, 15:39    [22008218]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Remind
Member

Откуда: UK
Сообщений: 523
uaggster
Remind, вот одним местом чувствую, что здесь что-то не то!
Дело в том, что первое подходящее продолжение цепочки - не обязательно с большим N по отношению к текущему узлу.
Подходящий N - может быть любым, в т.ч. и меньшим, чем текущий N.
Да, из подходящих продолжений цепочки - выбираем с меньшим N.
Нет, никто не гарантирует, что этот N больше N текущего узла.

А жаль :) Попробую еще покурить, но похоже реально без рекурсии тут не обойтись.
1 ноя 19, 16:47    [22008296]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4805
 
IF OBJECT_ID('tempdb..#C') IS NOT NULL
	DROP TABLE #C;

if object_id('tempdb..#t') is not null
	Drop table #t
if object_id('tempdb..#DList') is not null
	Drop table #DList
go

WITH D AS 
( -- диапазон дат
	SELECT '2019-01-01' AS Start_Date, '2025-12-31' AS End_Date 
),
N100 AS 
( -- цифры от 0 до 99
	SELECT 0 AS N
	UNION ALL 
	SELECT N100.N + 1 FROM N100
	WHERE N100.N < 99
), -- цифры от 0 до 9999
N10000 AS 
(
	SELECT N = N1.N * 100 + N2.N FROM N100 N1, N100 N2
),
DT AS 
( -- цифры -> даты 
	SELECT 
		N, 
		DT = CAST(DateAdd(day, N, Start_Date) AS DATE)
	FROM N10000, D
)
SELECT DT, N
INTO #C
FROM DT;

--SELECT * FROM #C
--ORDER BY DT;

Create table #t (N int, [KEY] int, DBEG DATE, DEND DATE);

insert into #t
Values 
(1, 1, '20190101', '20190109'),
(2, 1, '20190109', '20190109'),
(3, 1, '20190109', '20190109'),
(4, 1, '20190109', '20190109'),
(5, 1, '20190109', '20190109'),
(6, 1, '20190109', '20190111'),
(7, 1, '20190111', '20190112'),
(8, 1, '20190111', '20190111'),
(9, 1, '20190113', '20190116'),
(10, 1, '20190118', '20190119'),
(15, 1, '20190119', '20190121'),
(11, 2, '20190101', '20190109'),
(12, 2, '20190102', '20190109'),
(13, 2, '20190109', '20190109'),
(14, 2, '20190109', '20190109'),
(100, 1, '20190103', '20190109'),
(200, 3, '20190101', '20190101'),
(201, 3, '20190101', '20190103'),
(202, 3, '20190101', '20190105'),
(203, 3, '20190103', '20190107'),
(204, 3, '20190105', '20190108');

SELECT tg.[KEY], DT, N
INTO #DList
FROM #C C
CROSS JOIN 
(
	SELECT DISTINCT [KEY] FROM #t
) tg
CROSS APPLY
(
	SELECT TOP 1 1 AS X FROM #t t WHERE tg.[KEY] = t.[KEY] AND C.DT BETWEEN DBEG AND DEND 
) t;

SELECT [KEY], DBEG = MIN(DT), DEND = MAX(DT)  FROM 
(
	SELECT 
		[KEY],
		RN = N - ROW_NUMBER() OVER (PARTITION BY [KEY] ORDER BY DT),
		DT
	FROM #DList
) X
GROUP BY [KEY], RN
ORDER BY [KEY], MIN(DT)


1 2019-01-01 2019-01-16
1 2019-01-18 2019-01-21
2 2019-01-01 2019-01-09
3 2019-01-01 2019-01-08
1 ноя 19, 18:11    [22008352]     Ответить | Цитировать Сообщить модератору
 Re: Как агрегировать последовательность дат (возможно gaps and islands)  [new]
Remind
Member

Откуда: UK
Сообщений: 523
 		a_voronin, у Вас классический gaps and islands, у автора не все так просто.

insert into #t
Values 
(1, 1, '20190101', '20190109'),
(2, 1, '20190103', '20190124');
1 ноя 19, 18:41    [22008386]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить