Упаковка интервалов — это классическая задача SQL, которая подразумевает переупаковку групп пересекающихся интервалов в соответствующие им непрерывные интервалы. В математике интервал — это подмножество всех значений данного типа, например целых чисел, между двумя некоторым разными значениями. В базах данных интервалы могут проявляться в виде интервалов даты и времени, представляющие такие вещи, как сеансы, периоды назначения, периоды госпитализации, расписания или числовых интервалов, представляющие такие вещи, как диапазоны мильных столбов на дороге, диапазоны температур и т.д.
Хорошим примером задачи упаковки интервалов может послужить упаковка интервалов, представляющих сеансы с целью выставления счетов. Если вы погуглите термин packing intervals SQL, то найдете огромное множество статей на эту тему, включая и мою.
В прошлом я имел дело со многими задачами упаковки интервалов и использовал различные техники для их решения. Но у всех них было нечто общее, что в целом ограничивало их сложность — они представляли из себя всевозможные вариации одномерных задач упаковки интервалов. То есть каждый вход представлял собой один интервал. Одномерные интервалы можно пространственно изобразить как отрезки на прямой, а задачу упаковки можно проиллюстрировать как определение разделителей групп пересекающихся отрезков.
На занятиях по T-SQL, обсуждая задачи упаковки, Пол Уилкокс (Paul Wilcox) из Университета Джона Хопкинса поинтересовался, сталкивался ли я с задачами двумерной упаковки и есть ли у меня ссылки на ресурсы с их решениями. Он показал мне пост на форуме, который он отправил несколькими годами ранее, с задачей, которая возникла из-за проблем с расписанием, с которыми он столкнулся во время работы в предыдущем школьном округе. Я помню, как Пол пытался использовать жесты рук, изображающие двумерные многоугольники, чтобы проиллюстрировать идею. До этого момента мне даже не приходило в голову, что задачи двумерной упаковки вообще существуют, так что, очевидно, мне нечего было ему тогда посоветовать. Однако я пообещал взглянуть на нее после занятий и обратиться к нему следующим утром.
Иногда я называю решения или методы элегантными. Что было интересно в этой задаче, так это то, что сама задача была очень элегантной и интригующей. Более того, я мог сказать, что Пол был очень опытным и умным человеком, поэтому, если спустя годы, прошедшие с тех пор, как он впервые столкнулся с этой задачей, он все еще искал дополнительные решения, значит, она была очень интересной.
В этой статье я рассказываю о задаче двухмерной упаковки Пола и о своем решении. Некоторые из иллюстраций, которые я использую, отражают логические шаги, которые Пол сам изобразил в решении.
Я рекомендую вам попытаться решить задачу самостоятельно, прежде чем смотреть на мои с Полом решения — это будет хорошая тренировка для вас. Я также настоятельно рекомендую прочитать пост Пола, чтобы понять суть задачи, но на всякий случай приведу полную информацию о задаче и здесь.
Примечание: код из этой статьи можно скачать здесь.
Задача двумерной упаковки интервалов
Задача оперирует расписаниями занятий студентов, хранящимися в таблице Schedule, которую вы создаете и заполняете с помощью следующего кода:
SET NOCOUNT ON;
USE tempdb;
DROP TABLE IF EXISTS dbo.Schedule;
CREATE TABLE dbo.Schedule
(
id INT NOT NULL
CONSTRAINT PK_Schedule PRIMARY KEY,
student CHAR(3) NOT NULL,
fromdate INT NOT NULL,
todate INT NOT NULL,
fromperiod INT NOT NULL,
toperiod INT NOT NULL
);
INSERT INTO dbo.Schedule(id, student, fromdate, todate,
fromperiod, toperiod) VALUES
(1, 'Amy', 1, 7, 7, 9),
(2, 'Amy', 3, 9, 5, 8),
(3, 'Amy', 10, 12, 1, 3),
(4, 'Ted', 1, 5, 11, 14),
(5, 'Ted', 7, 11, 13, 16);В каждой строке указан студент, дата начала (fromdate) и дата окончания (todate), а также время начала периода (fromperiod) и время окончания периода (toperiod). Обратите внимание, что в примере данных для простоты вместо значений даты и времени используются целые числа.
Чтобы лучше представить эти данные, мы можем достаточно удобно изобразить их графическом виде. Этого можно добиться с помощью следующего пространственного запроса, формирующего из каждой строки прямоугольник:
SELECT student,
GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('
+ STRING_AGG(CONCAT('POLYGON((',fromdate,' ',fromperiod, ',',
fromdate,' ',toperiod + 1, ',',
todate + 1,' ',toperiod + 1,',',
todate + 1,' ',fromperiod,',',
fromdate,' ',fromperiod ,
'))'), ',')
+ ')', 0) AS shape
FROM dbo.Schedule
GROUP BY student;На рисунке 1 показан графический результат этого запроса, который можно увидеть на вкладке Spatial results SSMS.
Ось X представляет диапазоны дат, а ось Y представляет диапазоны периодов.
Обратите внимание, что у студента могут быть перекрывающиеся расписания, как в случае с расписаниями 1 и 2 Эми (Amy). Вы можете считать, что текущие данные представляют собой ненормализованную форму расписания.
Иногда необходимо запрашивать данные, чтобы найти расписание, содержащее определенную дату и период. Например, следующий запрос ищет расписание Эми, содержащее дату 4 и период 8:
SELECT id, student, fromdate, todate, fromperiod, toperiod
FROM dbo.Schedule
WHERE student = 'Amy'
AND 4 BETWEEN fromdate AND todate
AND 8 BETWEEN fromperiod AND toperiod;Этот запрос выдает следующие результаты, показывая несколько совпадений:
id student fromdate todate fromperiod toperiod
----------- ------- ----------- ----------- ----------- --------
1 Amy 1 7 7 9
2 Amy 3 9 5 8Множественные совпадения для одной точки (дата, период) возможны только из-за ненормализованности расписания. Задача состоит в том, чтобы создать нормализованное состояние расписания с отдельными, непересекающимися комбинациями диапазонов дат и периодов. Если предположить, что такое нормализованное состояние хранится в таблице, то можно гарантировать не более одной совпадающей строки на каждую вводимую точку (дата, период).
Сложность заключается в том, что может быть несколько механизмов, которые могут достичь этой цели. Для решения этой задачи вам просто нужно выбрать тот, который дает детерминированный результат. Например, можно сформировать строку результата для каждого последовательного диапазона дат с тем же диапазоном периодов. На рисунке 2 представлено графическое изображение искомого нормализованного расписания.
Если говорить неформально, то вы формируете наименьшее количество прямоугольников, используя только вертикальные разрезы. Очевидно, что вы можете выбрать стратегию, использующую горизонтальные разрезы. Или даже что-то более сложное, использующее комбинацию вертикальных и горизонтальных разрезов. В любом случае, если использовать подход с вертикальными разрезами, то на выходе вы получите следующее решение:
student fromdate todate fromperiod toperiod
------- ----------- ----------- ----------- -----------
Amy 1 2 7 9
Amy 3 7 5 9
Amy 8 9 5 8
Amy 10 12 1 3
Ted 1 5 11 14
Ted 7 11 13 16Я же говорил, что это непростая задача. А теперь за работу!
Решение с распаковкой/упаковкой для задачи одномерной упаковки
Мой подход к решению проблемы двумерной упаковки заключается в том, чтобы на нескольких этапах решения опираться на классическую технику работы с одномерной упаковкой, которую можно назвать техникой распаковки/упаковки (Unpack/Pack). Итак, сначала позвольте мне описать технику распаковки/упаковки для одномерной упаковки.
Предположим, что в нашей таблице Schedule у нас есть только диапазоны периодов и вам нужно их нормализовать. Это, конечно, совершенно надуманный пример, но я использую его для удобства, поскольку у нас уже есть примеры данных, с которыми можно работать. Вот запрос, показывающий только периоды:
SELECT id, student, fromperiod, toperiod
FROM dbo.Schedule
ORDER BY student, fromperiod, toperiod;Этот запрос возвращает следующий вывод:
id student fromperiod toperiod
----------- ------- ----------- -----------
3 Amy 1 3
2 Amy 5 8
1 Amy 7 9
4 Ted 11 14
5 Ted 13 16Предположим, что задача состоит в том, чтобы переупаковать пересекающиеся периоды для каждого ученика. Вот желаемый результат решения с упакованными периодами:
student fromperiod toperiod
------- ----------- -----------
Amy 1 3
Amy 5 9
Ted 11 16Как уже говорилось выше, существует множество решений для упаковки интервалов. Решение с распаковкой/упаковкой включает в себя следующие шаги:
Распакуйте каждый интервал на отдельные значения, составляющие множество.
Вычислите групповой идентификатор, используя классическую технику островов.
Сгруппируйте данные по групповому идентификатору, чтобы сформировать упакованные интервалы.
Давайте начнем с шага 1. Вы должны распаковать каждый интервал до отдельных значений, составляющих множества интервалов. Напомним, что интервал — это множество всех значений между двумя разными значениями, представляющими собой разделители интервалов. Например, учитывая, что в нашем примере данных в качестве разделителей периодов используется тип integer, интервал Эми с fromperiod 5 и toperiod 8 должен быть распакован в множество {5, 6, 7, 8}.
Если вы используете Azure SQL или SQL Server 2022 или более поздней версии, вы можете добиться этого с помощью функции GENERATE_SERIES, как показано ниже:
SELECT S.id, S.student, P.value AS p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
ORDER BY S.student, p, S.id;Этот запрос вернет следующий вывод:
id student p
----------- ------- -----------
3 Amy 1
3 Amy 2
3 Amy 3
2 Amy 5
2 Amy 6
1 Amy 7
2 Amy 7
1 Amy 8
2 Amy 8
1 Amy 9
4 Ted 11
4 Ted 12
4 Ted 13
5 Ted 13
4 Ted 14
5 Ted 14
5 Ted 15
5 Ted 16Если функции GENERATE_SERIES нет в вашем распоряжении, вы можете либо создать свою собственную реализацию, либо использовать таблицу чисел.
Шаг 2 включает вычисление уникального идентификатора группы для каждого упакованного интервала. Обратите внимание, что каждый упакованный интервал содержит последовательный диапазон неупакованных значений p, возможно, с дубликатами. В качестве примера можно привести диапазон Эми между 5 и 9: {5, 6, 7, 7, 8, 8, 9}. Идентификатор группы можно вычислить как значение p, минус значение плотного ранга (поскольку могут быть дубликаты) на основе порядка значений p, в пределах раздела студентов. Вот запрос, в котором это достигается, для наглядности отдельно показаны значения плотного ранга:
SELECT S.id, S.student, P.value AS p,
DENSE_RANK() OVER(PARTITION BY S.student ORDER BY P.value)
AS drk,
P.value - DENSE_RANK() OVER(PARTITION BY S.student
ORDER BY P.value) AS grp_p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
ORDER BY S.student, p, S.id;Этот запрос возвращает следующий вывод:
id student p drk grp_p
----------- ------- ------ --------- --------
3 Amy 1 1 0
3 Amy 2 2 0
3 Amy 3 3 0
2 Amy 5 4 1
2 Amy 6 5 1
1 Amy 7 6 1
2 Amy 7 6 1
1 Amy 8 7 1
2 Amy 8 7 1
1 Amy 9 8 1
4 Ted 11 1 10
4 Ted 12 2 10
4 Ted 13 3 10
5 Ted 13 3 10
4 Ted 14 4 10
5 Ted 14 4 10
5 Ted 15 5 10
5 Ted 16 6 10Вы получаете идентификатор группы (grp_p), который одинаков для каждой группы упакованных интервалов и является уникальным для каждой группы.
Затем на шаге 3 распакованные данные группируются по студентам и идентификатору группы и вычисляются разделители упакованных интервалов с помощью агрегатов MIN(p) и MAX(p) агрегаты, как показано ниже:
WITH C AS
(
SELECT S.id, S.student, P.value AS p,
DENSE_RANK() OVER(PARTITION BY S.student ORDER BY P.value)
AS drk,
P.value - DENSE_RANK() OVER(PARTITION BY S.student
ORDER BY P.value) AS grp_p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
)
SELECT student, MIN(p) AS fromperiod, MAX(p) AS toperiod
FROM C
GROUP BY student, grp_p
ORDER BY student, fromperiod;Этот запрос возвращает следующий искомый результат:
student fromperiod toperiod
------- ----------- -----------
Amy 1 3
Amy 5 9
Ted 11 16Очевидно, что эта техника не очень оптимальна, когда множества, представляющие интервалы, могут содержать большое количество членов. Но она отлично работает на небольших множествах и необходима для решения задачи двумерной упаковки.
Решение для двумерной упаковки
Вооружившись техникой распаковки/упаковки, мы готовы к решению задачи двумерной упаковки. Хитрость заключается в том, чтобы понять, что мы можем использовать ее в решении несколько раз — по одному разу на каждое измерение.
На шаге 1 мы распаковываем двумерный диапазон значений дат и периодов до отдельных значений date (d), period (p). Вероятно, проще всего представить этот шаг в графическом виде, как пикселизацию (спасибо Полу за терминологию!) прямоугольников, представляющих расписание занятий каждого студента с рисунка 1, показанного ранее. Вот код для выполнения этого шага:
SELECT S.id, S.student, D.value AS d, P.value AS p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
ORDER BY S.student, d, p, S.id;Этот запрос возвращает следующий вывод:
id student d p
----------- ------- ----------- -----------
1 Amy 1 7
1 Amy 1 8
1 Amy 1 9
1 Amy 2 7
1 Amy 2 8
1 Amy 2 9
2 Amy 3 5
2 Amy 3 6
1 Amy 3 7
2 Amy 3 7
1 Amy 3 8
2 Amy 3 8
1 Amy 3 9
2 Amy 4 5
2 Amy 4 6
1 Amy 4 7
2 Amy 4 7
1 Amy 4 8
2 Amy 4 8
1 Amy 4 9
2 Amy 5 5
2 Amy 5 6
1 Amy 5 7
2 Amy 5 7
1 Amy 5 8
2 Amy 5 8
1 Amy 5 9
2 Amy 6 5
2 Amy 6 6
1 Amy 6 7
2 Amy 6 7
1 Amy 6 8
2 Amy 6 8
1 Amy 6 9
2 Amy 7 5
2 Amy 7 6
1 Amy 7 7
2 Amy 7 7
1 Amy 7 8
2 Amy 7 8
1 Amy 7 9
2 Amy 8 5
2 Amy 8 6
2 Amy 8 7
2 Amy 8 8
2 Amy 9 5
2 Amy 9 6
2 Amy 9 7
2 Amy 9 8
3 Amy 10 1
3 Amy 10 2
3 Amy 10 3
3 Amy 11 1
3 Amy 11 2
3 Amy 11 3
3 Amy 12 1
3 Amy 12 2
3 Amy 12 3
...Мы можем использовать следующий вспомогательный запрос, чтобы отобразить результат шага 1 графически:
WITH Pixels AS
(
SELECT S.id, S.student, D.value AS d, P.value AS p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
)
SELECT student,
GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('
+ STRING_AGG(CONCAT('POLYGON((', d , ' ', p , ',',
d , ' ', p + 1, ',',
d + 1, ' ', p + 1, ',',
d + 1, ' ', p , ',',
d , ' ', p , '))'), ',')
+ ')', 0) AS shape
FROM Pixels
GROUP BY student;На рисунке 3 представлен графический результат с вкладки Spatial results в SSMS.
Теперь нам нужно определиться со стратегией нормализации, которую мы хотим использовать. Если мы решили использовать то, что я ранее назвал подходом вертикальных срезов, мы можем перейти к шагу 2. Чтобы применить вертикальные срезы, нам нужно упаковать диапазоны периодов по студентам и датам. Это достигается путем присвоения группового идентификатора grp_p каждому отдельному диапазону p последовательных значений для каждого студента и группы d. Вот код, с помощью которого это можно сделать:
WITH PixelsAndPeriodGroupIDs AS
(
SELECT S.id, S.student, D.value AS d, P.value AS p,
P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value
ORDER BY P.value) AS grp_p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
)
SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod
FROM PixelsAndPeriodGroupIDs
GROUP BY student, d, grp_p
ORDER BY student, d, grp_p;Вот результат внутреннего запроса, определяющего CTE (обобщенное табличное выражение) PixelsAndPeriodGroupIDs, показывающий вычисленное значение grp_p для каждого пикселя, если вам интересно:
id student d p grp_p
----------- ------- ----------- ----------- --------------------
1 Amy 1 7 6
1 Amy 1 8 6
1 Amy 1 9 6
1 Amy 2 7 6
1 Amy 2 8 6
1 Amy 2 9 6
2 Amy 3 5 4
2 Amy 3 6 4
2 Amy 3 7 4
1 Amy 3 7 4
1 Amy 3 8 4
2 Amy 3 8 4
1 Amy 3 9 4
2 Amy 4 5 4
2 Amy 4 6 4
2 Amy 4 7 4
1 Amy 4 7 4
1 Amy 4 8 4
2 Amy 4 8 4
1 Amy 4 9 4
2 Amy 5 5 4
2 Amy 5 6 4
2 Amy 5 7 4
1 Amy 5 7 4
1 Amy 5 8 4
2 Amy 5 8 4
1 Amy 5 9 4
2 Amy 6 5 4
2 Amy 6 6 4
2 Amy 6 7 4
1 Amy 6 7 4
1 Amy 6 8 4
2 Amy 6 8 4
1 Amy 6 9 4
2 Amy 7 5 4
2 Amy 7 6 4
2 Amy 7 7 4
1 Amy 7 7 4
1 Amy 7 8 4
2 Amy 7 8 4
1 Amy 7 9 4
2 Amy 8 5 4
2 Amy 8 6 4
2 Amy 8 7 4
2 Amy 8 8 4
2 Amy 9 5 4
2 Amy 9 6 4
2 Amy 9 7 4
2 Amy 9 8 4
3 Amy 10 1 0
3 Amy 10 2 0
3 Amy 10 3 0
3 Amy 11 1 0
3 Amy 11 2 0
3 Amy 11 3 0
3 Amy 12 1 0
3 Amy 12 2 0
3 Amy 12 3 0
…А вот результат внешнего запроса, показывающий упакованные диапазоны периодов после группировки:
student d fromperiod toperiod
------- ----------- ----------- -----------
Amy 1 7 9
Amy 2 7 9
Amy 3 5 9
Amy 4 5 9
Amy 5 5 9
Amy 6 5 9
Amy 7 5 9
Amy 8 5 8
Amy 9 5 8
Amy 10 1 3
Amy 11 1 3
Amy 12 1 3
Ted 1 11 14
Ted 2 11 14
Ted 3 11 14
Ted 4 11 14
Ted 5 11 14
Ted 7 13 16
Ted 8 13 16
Ted 9 13 16
Ted 10 13 16
Ted 11 13 16Здесь важно отметить, что мы создали упакованные диапазоны периодов для каждого учащегося и даты. Это удобно изобразить графически с помощью следующего пространственного запроса:
WITH PixelsAndPeriodGroupIDs AS
(
SELECT S.id, S.student, D.value AS d, P.value AS p,
P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value
ORDER BY P.value) AS grp_p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
),
DailyPeriodRanges AS
(
SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod
FROM PixelsAndPeriodGroupIDs
GROUP BY student, d, grp_p
)
SELECT student,
GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('
+ STRING_AGG(CONCAT('POLYGON((',d,' ',fromperiod , ',',
d,' ',toperiod + 1,',',
d + 1,' ',toperiod + 1, ',',
d + 1,' ',fromperiod ,',',
d,' ',fromperiod,'))'),',')
+ ')', 0) AS shape
FROM DailyPeriodRanges
GROUP BY student;На рисунке 4 показаны выходные данные со вкладки Spatial results в SSMS.
То, чего мы здесь добились, — это своего рода подневный бинниг (еще раз спасибо Полу за терминологию) упакованных диапазонов периодов. Затем на шаге 3 осталось упаковать последовательные диапазоны дат для каждого студента и диапазона периодов. Вот код для достижения этой цели:
WITH PixelsAndPeriodGroupIDs AS
(
SELECT S.id, S.student, D.value AS d, P.value AS p,
P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value
ORDER BY P.value) AS grp_p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
),
PeriodRangesAndDateGroupIDs AS
(
SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod,
D - DENSE_RANK() OVER(PARTITION BY student, MIN(p), MAX(p)
ORDER BY d) as grp_d
FROM PixelsAndPeriodGroupIDs
GROUP BY student, d, grp_p
)
SELECT student, MIN(d) AS fromdate, MAX(d) AS todate,
fromperiod, toperiod
FROM PeriodRangesAndDateGroupIDs
GROUP BY student, fromperiod, toperiod, grp_d
ORDER BY student, fromdate, fromperiod;Главная хитрость заключается в том, что во втором CTE (PeriodRangesAndDateGroupIDs), где вы второй раз применяете классическую технику островов, при вычислении значения плотного ранга вы разбиваете его по студентам и диапазону периодов (student, MIN(p), MAX(p)), а затем упорядочиваете по d.
Вот результат внутреннего запроса второго CTE:
student d fromperiod toperiod grp_d
------- ----------- ----------- ----------- ----------
Amy 10 1 3 9
Amy 11 1 3 9
Amy 12 1 3 9
Amy 8 5 8 7
Amy 9 5 8 7
Amy 3 5 9 2
Amy 4 5 9 2
Amy 5 5 9 2
Amy 6 5 9 2
Amy 7 5 9 2
Amy 1 7 9 0
Amy 2 7 9 0
Ted 1 11 14 0
Ted 2 11 14 0
Ted 3 11 14 0
Ted 4 11 14 0
Ted 5 11 14 0
Ted 7 13 16 6
Ted 8 13 16 6
Ted 9 13 16 6
Ted 10 13 16 6
Ted 11 13 16 6А вот выходные данные внешнего запроса, показывающие окончательный искомый результат с нормализованным расписанием:
student fromdate todate fromperiod toperiod
------- ----------- ----------- ----------- -----------
Amy 1 2 7 9
Amy 3 7 5 9
Amy 8 9 5 8
Amy 10 12 1 3
Ted 1 5 11 14
Ted 7 11 13 16Если вы хотите проиллюстрировать результат графически, вы можете использовать следующий вспомогательный пространственный запрос:
WITH PixelsAndPeriodGroupIDs AS
(
SELECT S.id, S.student, D.value AS d, P.value AS p,
P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value
ORDER BY P.value) AS grp_p
FROM dbo.Schedule AS S
CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D
CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P
),
PeriodRangesAndDateGroupIDs AS
(
SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod,
d - DENSE_RANK() OVER(PARTITION BY student, MIN(p), MAX(p)
ORDER BY d) as grp_d
FROM PixelsAndPeriodGroupIDs
GROUP BY student, d, grp_p
),
NormalizedSchedule AS
(
SELECT student, MIN(d) AS fromdate, MAX(d) AS todate,
fromperiod, toperiod
FROM PeriodRangesAndDateGroupIDs
GROUP BY student, fromperiod, toperiod, grp_d
)
SELECT student,
GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('
+ STRING_AGG(CONCAT('POLYGON((',fromdate,' ',fromperiod,',',
fromdate,' ',toperiod+1,',',
todate + 1,' ',toperiod+1,',',
todate + 1,' ',fromperiod,',',
fromdate , ' ', fromperiod ,
'))'),
',')
+ ')', 0) AS shape
FROM NormalizedSchedule
GROUP BY student;Вывод на вкладке Spatial results в SSMS аналогичен тому, что я показывал ранее на рисунке 2, в виде графического изображения искомого результата.
Заключение
Еще раз спасибо Полу Уилкоксу за то, что представил задачу о двухмерной упаковке. Это прекрасная головоломка, и я получил огромное удовольствие от работы над ней. Надеюсь, что и вы тоже.
Вы увидели, как важно развивать инструментарий фундаментальных техник, таких как классическая техника островов и основанная на ней техника распаковки/упаковки. Они были необходимы для решения этой более сложной задачи. Вы также увидели, как полезно представлять некоторые задачи в графическом виде и даже использовать для этого пространственные инструменты T-SQL.
Удачных запросов!
Напоминаем про открытый урок «MSSQL vs PostgreSQL основные отличия», который пройдет сегодня в 20:00. Рассмотрим следующие ключевые аспекты:
Архитектурные различия MS SQL и PostgreSQL
Разница в обработке транкцизй в MSSQL и PostgreSQL
Почему в PostgreSQL бессмыленно делать обновление блоками?
Основные различия T-SQL и PL/pgSQL
Записаться на урок можно по ссылке.
Tzimie
Сегодня в 20:00?
Судя по всему, как то поздно вы написали