Автор Тема: Задачка SQL'ная (разминка мозга)  (Прочитано 7587 раз)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Задачка SQL'ная (разминка мозга)
« : Октябрь 26, 2012, 11:02:01 am »
Попалась коллеге сегодня такая задачка:
Есть список дат (без ограничений) Например:

02.10.2012
05.10.2012
01.10.2012
03.10.2012
06.10.2012
19.10.2012
20.10.2012
15.10.2012
16.10.2012
17.10.2012
05.11.2012
18.10.2012

Нужно получить результат в виде таблицы с двумя колонками: [Начало, Конец]
Эта таблица должна содержать непрерывные периоды из исходного списка.
Т.е. для данного выше списка будет:

02.10.2012 (1)
05.10.2012 (2)
01.10.2012 (1)
03.10.2012 (1)
06.10.2012 (2)
19.10.2012 (3)
20.10.2012 (3)
15.10.2012 (3)
16.10.2012 (3)
17.10.2012 (3)
05.11.2012 (4)
18.10.2012 (3)

1) 01.10.2012 - 03.10.2012
2) 05.10.2012 - 06.10.2012
3) 15.10.2012 - 20.10.2012
4) 05.11.2012 - 05.11.2012

Периоды не должны пересекать границы месяца. Т.е. если у вас такой список:
30.10.2012
31.10.2012
01.11.2012
02.11.2012
то результат будет содержать два периода, а не один:
1) 30.10.2012 - 31.10.2012
2) 01.11.2012 - 02.11.2012

Интерес представляет решение на SQL (это ограничение реальной задачи)

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #1 : Октябрь 27, 2012, 12:44:12 pm »
Во-первых, даты нужно как-то связать в цепочки.
Я это сделал с помощью LEFT JOIN таблицы с самой собой. В  секции ON указал "T2.d = T1.d + 1". (Переход цепочки через месяц я не учитывал, но думаю, что достаточно в эту секцию добавить MONTH(T1.d) = MONTH(t2.d).)
При таком объединении таблиц вторая дата будет NULL, когда первая дата будет являться концом цепочки.
При RIGHT JOIN всё наоборот: первая дата NULL, когда вторая дата - начало цепочки.

Во-вторых, нужно выбрать начальные и конечные даты диапазонов.
Здесь всё просто: есть пара дат, и один из элементов пары NULL. Отображаем это в секции WHERE.

В-третьих, нужно оставшиеся даты упорядочить.
В MySQL с этим проблема, как в остальных местах - не знаю. Суть проблемы в том, что ORDER BY работает только на конечных запросах, а не в подзапросах. Пришлось изгалаться с помощью GROUP BY, с которым я не работал, поэтому не могу гарантировать, что запрос действительно правильный. Но если бы ORDER BY работал, то в результате получились бы две таблички с одинаковым количеством упорядоченных дат. В одной табличке - начала, а в другой - конец.

В четвёртых, объединим начальные и конечные даты.

Вот, что у меня получилось.
SELECT b, min(e) FROM
(SELECT T2.d AS b FROM dates_ilovb AS T1 RIGHT JOIN dates_ilovb AS T2 ON T2.d = T1.d + 1 WHERE T1.d IS NULL) AS TB
LEFT JOIN
(SELECT T1.d AS e FROM dates_ilovb AS T1 LEFT JOIN dates_ilovb AS T2 ON T2.d = T1.d + 1 WHERE T2.d IS NULL) AS TE
ON TB.b <= TE.e
GROUP BY b
ORDER BY b;


ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #2 : Октябрь 27, 2012, 03:17:53 pm »
Интересное решение.
Проверил:
ВЫБРАТЬ
    TB.b,
    МИНИМУМ(TE.e) КАК e
ИЗ
    (ВЫБРАТЬ
        T2.d КАК b
    ИЗ
        dates_ilovb КАК T2
            ЛЕВОЕ СОЕДИНЕНИЕ dates_ilovb КАК T1
            ПО (T2.d = ДОБАВИТЬКДАТЕ(T1.d, ДЕНЬ, 1))
    ГДЕ
        T1.d ЕСТЬ NULL ) КАК TB
        ЛЕВОЕ СОЕДИНЕНИЕ (ВЫБРАТЬ
            T1.d КАК e
        ИЗ
            dates_ilovb КАК T1
                ЛЕВОЕ СОЕДИНЕНИЕ dates_ilovb КАК T2
                ПО (T2.d = ДОБАВИТЬКДАТЕ(T1.d, ДЕНЬ, 1))
        ГДЕ
            T2.d ЕСТЬ NULL ) КАК TE
        ПО TB.b <= TE.e

СГРУППИРОВАТЬ ПО
    TB.b

УПОРЯДОЧИТЬ ПО
    TB.b

Без учета границ месяца результат верный.  :)

Спасибо за рассуждения. Очень интересно читать.

Цитата: Valery Solovey
В MySQL с этим проблема, как в остальных местах - не знаю. Суть проблемы в том, что ORDER BY работает только на конечных запросах, а не в подзапросах

Ну тут проблема не MySQL, а в SQL как языке вообще. Т.к. SQL оперирует неупорядоченными множествами. Ты все правильно сделал.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #3 : Октябрь 27, 2012, 04:48:57 pm »
Вот вариант который первым пришел в голову, когда мне озвучили задачу:
SELECT
    MIN(T.d1) AS d1,
    T.d2 AS d2
FROM
    (SELECT
        TA.d1 AS d1,
        MAX(TA.d2) AS d2
    FROM
        (SELECT
            TB.d1 AS d1,
            ISNULL(TB.d2, TB.d1) AS d2
        FROM
            (SELECT
                T1.d AS d1,
                ISNULL(T2.d, T1.d) AS d2,
                DATEDIFF(T1.d, ISNULL(T2.d, T1.d), DAY) AS DayCount
            FROM
                dates_ilovb AS T1
                    LEFT JOIN dates_ilovb AS T2
                    ON T1.d <= T2.d
                        AND (YEAR(T1.d) = YEAR(T2.d))
                        AND (MONTH(T1.d) = MONTH(T2.d))) AS TB
                LEFT JOIN dates_ilovb AS dates_ilovb
                ON TB.d1 < dates_ilovb.d
                    AND TB.d2 >= dates_ilovb.d
       
        GROUP BY
            TB.d1,
            TB.DayCount,
            ISNULL(TB.d2, TB.d1)
       
        HAVING
            COUNT(DISTINCT dates_ilovb.d) = TB.DayCount) AS TA
   
    GROUP BY
        TA.d1) AS T

GROUP BY
    T.d2

ORDER BY
    d1

Суть такая:
Соединяем таблицу саму с собой по условию T1.d <= T2.d AND (YEAR(T1.d) = YEAR(T2.d)) AND (MONTH(T1.d) = MONTH(T2.d)) и получаем набор периодов с количеством дней в каждом:
01.10.2012 - 01.10.2012 - 0
01.10.2012 - 02.10.2012 - 1
01.10.2012 - 03.10.2012 - 2
01.10.2012 - 05.10.2012 - 4
...
02.10.2012 - 02.10.2012 - 0
02.10.2012 - 03.10.2012 - 1
02.10.2012 - 05.10.2012 - 3
и т.д.

Затем соединяем получившуюся таблицу с исходной по условию TB.d1 < dates_ilovb.d AND TB.d2 >= dates_ilovb.d, т.е. собираем даты попадающие в эти периоды.
Далее сравниваем количество собранных дат с количеством дней в периодах и оставляем только совпадающие COUNT(DISTINCT dates_ilovb.d) = TB.DayCount.
В конце две группировки:
MAX(TA.d2) GROUP BY TA.d1 -> MIN(TA.d1) GROUP BY TA.d2

ps Решение Valery Solovey более простое и эффективное  :)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #4 : Ноябрь 19, 2013, 09:58:08 pm »
Еще задачка.
Есть 4 таблицы (в фигурных скобках ключи):
Номенклатура [{Код}, Наименование]
Характеристики [{Код}, Наименование, {Номенклатура}]
Свойства [{Код}, Наименование]
ЗначенияСвойств [{Свойство, Характеристика}, Значение]

Т.е. у одной номенклатуры может быть несколько характеристик.
У характеристик может быть несколько свойств со значениями.

Нужно выбрать запросом дубликаты характеристик по свойствам в пределах номенклатуры.
Т.е. если у данной номенклатуры есть две характеристики у которых все свойства совпадают по значению, то она должна попасть в результат.
Результат:
[Номенклатура, Характеристика, ДубликатХарактеристики]

adva

  • Sr. Member
  • ****
  • Сообщений: 385
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #5 : Ноябрь 20, 2013, 12:42:55 am »
Ломал я как-то голову над подобной задачей (объединял номенклатуру с одинаковым составом и количеством в составе), но чисто запросами это сложно (хоть и одолел). Очень не хватает в запросах процедуры нумерации таблиц, а при использовании для этого МАКСИМУМ на больших объемах данных загибаются запросы. Да к тому же нет приведерния типов в запросе, не соединишь ссылку со строкой. Еще дополнительно приходиться извращаться.

Можно конечно в нескоьких запросах это сделать, промежуточные результаты в коде обработав, но СКД например это усложнит.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #6 : Ноябрь 20, 2013, 02:40:17 am »
Еще задачка.

Это не разминка, это жестокий и беспощадный SQL :)

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #7 : Ноябрь 20, 2013, 06:46:48 am »
А нормализация не спасёт отца русской демократии?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #8 : Ноябрь 20, 2013, 09:34:16 am »
А при чем тут нормализация?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #9 : Ноябрь 20, 2013, 03:20:05 pm »
Задачка, кстати, примечательна тем, что с наскока ее еще никто не решил (из тех, кому я ее предлагал)

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #10 : Ноябрь 22, 2013, 09:11:17 pm »
А при чем тут нормализация?
При том, что {Свойство, Характеристика} - это тип данного. И если завести табличку под это, а потом в другой табличке связывать значения и тип данных, то проблема решится на уровне БД. Или я не прав?
« Последнее редактирование: Ноябрь 22, 2013, 09:14:00 pm от Valery Solovey »

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #11 : Ноябрь 22, 2013, 09:20:45 pm »
Номенклатура [{Код}, Наименование]
Характеристики [{Код}, Наименование]
Свойства [{Код}, Наименование]
СодержаниеНоменклатуры [{id}, {Номенклатура, Характеристика}]
ОписаниеХарактеристики [{id}, {Свойство, Характеристика}]
ЗначенияСвойств [{ОписаниеХарактеристики}, Значение]

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #12 : Ноябрь 23, 2013, 09:11:55 am »
Это ничего не дает.

Пример.
Есть номенклатура "Табурет"
Есть три характеристики (в скобках свойства):
"Класс1" (цвет = белый, высота = 80 см.)
"Класс2" (цвет = белый, высота = 60 см.)
"Класс3" (цвет = белый, высота = 80 см.)

Класс1 и Класс3 разные характеристики, но свойства у них одинаковые.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Задачка SQL'ная (разминка мозга)
« Ответ #13 : Ноябрь 23, 2013, 03:22:22 pm »
Значит, я неправильно понял задачу. Тогда нужно уточнить цель. Нужно, чтобы характеристики были уникальными не по имени, а по значению/содержанию? А номенклатуры не должны соответствовать такому же условию?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка SQL'ная (разминка мозга)
« Ответ #14 : Ноябрь 23, 2013, 03:32:30 pm »
Нужно выбрать запросом дубликаты характеристик по свойствам в пределах номенклатуры.
Т.е. если у данной номенклатуры есть две характеристики у которых все свойства совпадают по значению, то она должна попасть в результат.
Результат:
[Номенклатура, Характеристика, ДубликатХарактеристики]

Тут вроде уже все сказано. Номенклатура выступает в задаче только как владелец характеристики.