Олимпиада SQL: разбор задачи про календарь

Здравствуйте, в эфире Радио SQL!

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

Настраивайтесь на нашу гравитационную волну, смахивайте слизь, поправляйте панцири и устраивайтесь поудобнее — мы начинаем!..

В этой статье я собираюсь провести разбор задачи про календарь, которую я давал на Олимпиаде по SQL, про которую я уже писал раньше. Захватывающая рекурсия и загадочные агрегатные функции, вложенные запросы и вооружённые группировки данных — всё это нас ждёт сегодня!

Обращаю внимание, что это именно разбор, а не готовое решение. Чтобы избежать тупого copy-paste, я намерено предприму пару действий, которые позволят получить готовый результат только тем, кто немного поработает головой.

Во-первых, я не буду приводить полный и окончательный код запроса. Чтобы получить финальное решение, придётся осмысленно собрать все части запроса в одно целое. Для человеков это несложно, достаточно задействовать головные ганглии. Также я опущу некоторые громоздкие, но совершенно неинтересные части (типа выравнивания названий месяцев по центру) для доработки желающими напильником по месту самостоятельно. Соответственно, собранный результат без некоторой доводки формально не будет правильным решением исходной задачи. Но меня это не волнует ни капли, так как моя цель — показать как подобные задачи решаются в принципе, а не получить готовый результат в данном частном случае.

Во-вторых, я возьму другой, не оракловый диалект SQL. Конечно любая сколько-нибудь нетривиальная задача требует всяких плюшек, которые в разных вариантах SQL поддерживаются слегка по-разному, вызывая размышления о том, что наша матрица всё же слегка сбоит. Нам существенным образом нужны будут CTE, которые позволяют собирать части запроса с подвыражением WITH ..., да и входные параметры в условии задачи так заданы. Также нам будут нужны рекурсивные запросы или их аналог для генерации последовательностей заранее неизвестной длины, и, наконец, агрегатная функция склейки строк, чтобы собрать всё вместе. С такими мягкими ограничениями на роль SQL-сервера может претендовать любая кофемолка почти что угодно, где в описании встречается аббревиатура SQL. Это и PostgreSQL, и SQLite, и даже MySQL наконец-то стал поддерживать CTE. Коммерческие БД само собой всё это давно умеют.

Поколебавшись некоторое время, я остановил свой выбор на PostgreSQL, чтобы пощупать поближе, как он по сравнению с оракловой базой будет смотреться в этой задаче. Выразить все необходимые шаги решения на другом диалекте SQL не должно быть проблемой, лично я с этим справился быстро. Напомню, что на олимпиаде, откуда взята задача, использовался именно Oracle SQL, на котором и было изначально написано референсное решение. Ну и мне интереснее будет, не всё же только публике развлечения.

Что ж, шутки в сторону, приступим к разбору. Напомню условие.

with param(year, c, r) (…)

with param(year, c, r) as (select 2016, 3, 4 from dual)

                                  2016
         Январь                 Февраль                   Март
              1  2  3     1  2  3  4  5  6  7        1  2  3  4  5  6
  4  5  6  7  8  9 10     8  9 10 11 12 13 14     7  8  9 10 11 12 13
 11 12 13 14 15 16 17    15 16 17 18 19 20 21    14 15 16 17 18 19 20
 18 19 20 21 22 23 24    22 23 24 25 26 27 28    21 22 23 24 25 26 27
 25 26 27 28 29 30 31    29                      28 29 30 31
         Апрель                   Май                     Июнь
              1  2  3                       1           1  2  3  4  5
  4  5  6  7  8  9 10     2  3  4  5  6  7  8     6  7  8  9 10 11 12
 11 12 13 14 15 16 17     9 10 11 12 13 14 15    13 14 15 16 17 18 19
 18 19 20 21 22 23 24    16 17 18 19 20 21 22    20 21 22 23 24 25 26
 25 26 27 28 29 30       23 24 25 26 27 28 29    27 28 29 30
                         30 31
          Июль                   Август                 Сентябрь
              1  2  3     1  2  3  4  5  6  7              1  2  3  4
  4  5  6  7  8  9 10     8  9 10 11 12 13 14     5  6  7  8  9 10 11
 11 12 13 14 15 16 17    15 16 17 18 19 20 21    12 13 14 15 16 17 18
 18 19 20 21 22 23 24    22 23 24 25 26 27 28    19 20 21 22 23 24 25
 25 26 27 28 29 30 31    29 30 31                26 27 28 29 30
        Октябрь                  Ноябрь                 Декабрь
                 1  2        1  2  3  4  5  6              1  2  3  4
  3  4  5  6  7  8  9     7  8  9 10 11 12 13     5  6  7  8  9 10 11
 10 11 12 13 14 15 16    14 15 16 17 18 19 20    12 13 14 15 16 17 18
 17 18 19 20 21 22 23    21 22 23 24 25 26 27    19 20 21 22 23 24 25
 24 25 26 27 28 29 30    28 29 30                26 27 28 29 30 31
 31

Подход к решению

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

Единственное действительно нетривиальное, что тут есть — это представить себе, как можно сгенерировать матрицу календаря, когда ширина и высота задаются параметрами. С высотой всё совсем просто — все диалекты SQL так или иначе позволяют генерировать запросами заданное параметром количество записей. Обычно это рекурсивные запросы, хотя иногда и попадаются специальные конструкции. Например, в том же PostgreSQL нашлась специальная конструкция generate_series(MIN, MAX), которая генерирует серию значений от MIN до MAX. Можно воспользоваться и "классическим" рекурсивным запросом вида:

with recursive seq(n) as (
    select MIN
        union all 
    select n+1 from seq where n<MAX)

, но специальная конструкция будет короче. Так можно получить нужное количество строк.

Теперь определимся с тем, как сгенерировать количество столбцов, заданных параметром. В принципе всё так же, как и со строками выше, можно сгенерировать необходимое количество записей. А потом, когда их надо будет вывести, сгруппируем и склеим эти записи агрегатной функцией для работы со строками. В PostgreQSL для этого нашлась подходящая функция string_agg():

select string_agg(t::text,'-') from generate_series(MIN,MAX) as s(t);

С помощью этой техники мы сгенерируем матрицу-заготовку для календаря, в которой по горизонтали и вертикали будет нужное количество месяцев, заданное в параметрах. Каждый месяц будем представлять в виде знакомест в 6 строк по 7 столбцов для каждого из дней месяца, вот так:

xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx

Назовём каждую такую конструкцию месяцеместом, так дальше будет удобно ссылаться. По столбцам месяцеместа мы потом будем расставлять числа в соответствии с днями недели. А по строкам в соответствии с номером недели в месяце — сначала первую строчку заполнять, потом вторую и так далее. Столбцов нужно семь по количеству дней недели, строк пусть будет шесть. Больше шести недель в месяце никак не может быть. Я конечно имею в виду земной Григорианский календарь. Просьба жителям других планет отнестись с пониманием, эта задача была придумана в первую очередь для землян XXI века (013 в тентуре, налево от БМ).

Теперь, когда с самым нетривиальным стало всё понятно, займёмся остальными техническими деталями. Нам нужно будет сгенерировать все дни года, чтобы потом их расставить в полученную выше матрицу. Тут закавыка может быть с тем, чтобы правильно определить это количество дней. Например, с учётом того, что год может быть високосный. Или вот в земном Григорианском календаре в 1582 году отсутствуют дни с 05 по 14 октября (и Oracle честно это показывает!). Так что дни нужного года будем получать так: все дни с первого дня года, указанного в параметрах, и до (но не включая) первого дня следующего года.

И последним шагом нам нужно будет аккуратно собрать всё вместе, добавить названия месяцев и номер года сверху, убрать пустые строчки и т.п.

Итого по порядку:

1. Сгенерировать все дни года.
2. Сгенерировать матрицу-заготовку с нужным количеством строк и столбцов.
3. Вписать дни года в матрицу календаря на нужные места.
4. Собрать всё вместе для вывода результатов.

Реализация

Поехали.

Вот наши исходные параметры для задачи:

with params(year, r, c) as (select 2016, 3, 4)

Генерация всех дней года. Сами дни можно сгенерировать через generate_series(START_DATE, END_DATE), указав началом первый день года и концом предыдущий день от первого дня следующего года. Дальше нам кроме самой даты понадобится из неё получить некоторые полезные данные, которые нам пригодятся: номер дня недели, номер месяца, номер дня в месяце и день недели для первого дня месяца. Мы можем получать эти данные по мере надобности, но это будет громоздко, лучше посчитать сразу. Посмотрев документацию по функциям работы с датами в PostgreSQL, я вижу, что для этого можно воспользоваться функцией extract().

...
days(day, moy, dom, dow, fdow) as
  (select d                                -- day of year (date)
        , extract(month from d)::int-1     -- month, 0-11
        , extract(day from d)::int         -- day of month, 1-31
        , extract(isodow from d)::int-1    -- day of week, 0-6
        , extract(isodow from date_trunc('month', d))::int-1   -- day of week of first day in month, 0-6
    from params p
       , generate_series( (p.year   ||'-01-01')::date
                       , ((p.year+1)||'-01-01')::date - 1, '24:00') as s(d))

Теперь сгенерируем матрицу календаря с нужным количеством месяцев в колонках и строках. Для удобства дальнейшей расстановки дат по местам, в каждом месяцеместе (которое 7х6 клеточек) мы сразу запишем номер месяца, который будем на это место подставлять, и номер позиции дня в месяце по порядку. Понадобится некоторое количество мутноватой целочисленной арифметики с делением нацело и остатками, зато потом расстановка дат будет простой и удобной:

...
matrix(c, r, moy, pos) as
  (select c.c, r.r, c.c/7 + r.r/6*p.c, c.c%7 + r.r%6*7 + 1
     from params p
        , generate_series(0, p.c*7-1) as c(c) -- columns
        , generate_series(0, p.r*6-1) as r(r)) -- rows

Теперь собираем вместе, расставляя дни по местам. Как я и сказал, с учётом предварительной подготовки, это делается на раз:

...
cal (r,c,dom) as
  (select r,c,dom
     from matrix m
   left outer join days d
                on d.moy = m.moy       -- same month
              and d.fdow+d.dom = m.pos  -- position is day no plus weekday of first day
)

Что характерно, если в параметрах задачи матрица календаря по размерам получится больше или меньше 12 месяцев, то всё сработает корректно. Либо заполнятся все месяцеместа и часть останется пустыми, либо лишние месяцы не поместятся, но в обоих случаях матрица не разъедется.

Всё, основная часть сделана. Осталось всё аккуратно собрать вместе в cal_all. Начнём с месяцемест с числами:

...
cal_all (no, line) as
  (-- days in cal matrix
   select r, string_agg(lpad(coalesce(dom::text,' '), 3+case when c%7=0 then 2 else 0 end) ,'' order by c)
     from cal
   group by r
...

Тут склеивается в одну строчку функцией string_agg() всё, что попало в одну строку матрицы календаря. При этом пустые значения дней заменяются на пробелы, и все числа дополняются слева пробелами, чтобы их выровнять. Причём внутри одного месяцеместа на каждое число отводится по 3 знакоместа, а между месяцами (условие c%7=0) — по 5. Это позволяет визуально отделить месяцы друг от друга. Также обращаю внимание на то, что мы сохраняем номер строки. По нему будет определяться правильный порядок в финальном выводе.

Дальше добавляем сюда же названия месяцев. Для этого выбираем из уже сделанного ранее представления days только первые дни месяца, группируем их по params.c штук в строке и склеиваем с помощью string_agg(). Если в матрицу календаря не помещаются все месяцы, то возьмём названия только тех, что помещаются. Не забываем дополнить каждое имя пробелами, чтобы месяцы были над своими месяцеместами, а также дать каждой получившейся строке такой номер, чтобы в финальной сортировке месяцы встали на свои места. То есть первая строчка с месяцами должна встать перед первой строкой с числами, вторая перед седьмой (помните, что мы по шесть строк на месяц отводили?) и так далее. Всё вместе получается так:

...
   union all
   -- month names
   select (moy/p.c)*6-0.5, string_agg(lpad(to_char(day, 'Month'), 7*3+2) , '' order by moy)
     from days d, params p
    where dom = 1  -- first days of months only
      and moy < p.r*p.c
   group by (moy/p.c)

Осталось сверху посередине дописать год:

...
   union all
   select -1, lpad(year::text, (7*3+2)*c/2+length(year::text)/2) from params

Теперь осталось из cal_all выбрать все строки в правильном порядке и отбросить пустые, если таковые найдутся:

...
select line from cal_all
 where trim(line) <> ''
order by no

Это и есть финальная часть нашего запроса.

Что осталось за кадром. Напрашивается сделать представление params2 и вынести в него константы типа "количество знакомест на каждое число месяца" и "количество пробелов между месяцеместами". Потому что если вдруг понадобится их поменять, то придётся выискивать эти числа в коде, который не везде очевиден, что чревато ошибками. Ну и все функции выравнивания я упростил, чтобы не перегружать код. А по условию задачи всё нужно выравнивать по центру.

Выводы

Главный и основной, который я старался донести до аудитории: нет ничего сверхсложного в решении подобных задач.

Что можно сказать про PostgreSQL в сравнении с Oracle по итогам данной задачи. Функционально всё соответствует, выразить можно приблизительно то же и приблизительно так же. Некоторые нюансы удобнее в одном диалекте, некоторые в другом. Функции отличаются, но на то и документация нам дана. Есть ли в чём-то существенная разница? Да, есть. На примере данной задачи я вижу по крайней мере в двух местах.

Во-первых, Oracle поддерживает локали, и в разных локалях неделя может начинаться с разных дней недели. Например, в большей части Европы неделя начинается понедельником, а в США с воскресенья. В PostgreSQL нет настроек локали для первого дня недели и невозможно сгенерировать календарь так, чтобы он начинался с привычного пользователю дня.

Во-вторых, отличается поддержка преобразования дат и работа с календарём. В Oracle за 04 октября 1582 года идёт 15 октября (как и было определено при вводе Григорианского календаря), в PostgreSQL есть 05 и все остальные числа октября 1582 года. Вопрос не так прост, как может показаться сходу, в документации PostgreSQL есть даже специальный раздел, объясняющий проблему и почему в PostgreSQL она решена таким образом. Но факт остаётся фактом: календари в Oracle и PostgreSQL разные, хоть оба и Григорианские, и, соответственно, логика работы с датами существенно отличается. Это может быть важно при портировании.

Если вам понравилось изложение, и у вас есть идеи о чём ещё околоSQLном следует написать, жду вас в комментариях. Также можете ответить на вопрос внизу, поддерживаете ли вы публикацию разбора олимпиадных задач.

На этом сегодня я прощаюсь с нашей аудиторией, stay tuned!..

Автор: bzq

Источник