Новость из категории: Информация

Группирование связанных элементов в T-SQL

Содержание:
1. Часть I (Вы читаете данный раздел);
2. Часть II ;
3. Часть III.
Группирование связанных элементов в T-SQL

В этой статье я хочу представить вам интересную задачу, которую предложил мне мой друг, обладатель звания Data Platform MVP Дэвид Маури. Она была связана с конкретным приложением, важным для начинающей компании Sensoria, с которой Дэвид одно время работал, но проблема на самом деле гораздо шире. Мы рассмотрим задачу, в которой требуется группировать связанные элементы, и четыре различных решения T-SQL, в частности их производительность и возможности масштабирования. Решение CLR UDA с впечатляющей производительностью, предложенное Дэвидом, можно найти в его блоге (http://sqlblog.com/blogs/davide_mauri/archive/2017/11/12/lateral-thinking-transitive-closure-clustering-with-sql-server-uda-and-json.aspx).

Группирование связанных элементов в T-SQL
Рисунок 1. Группирование связанных элементов

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

Обратите внимание, что в этом примере нет прямого соединения между узлами 17 и 25, но они связаны непрямо, или транзитивно, через цепь 17-18-25, поэтому являются частью одной группы. Входной граф представлен таблицей (назовем ее T1) с ребрами. На экране 1 перечислены ребра графа, показанного на рисунке 1.

Группирование связанных элементов в T-SQL
Экран 1. Ребра графа, показанного на рисунке 1

На выходе должны быть получены идентификаторы отдельных узлов, каждому из которых назначен общий идентификатор группы; например, можно использовать минимальный идентификатор узла в группе в качестве группового идентификатора. На экране 2 приводится предпочтительный вывод для графа, показанного на рисунке 1.

Группирование связанных элементов в T-SQL
Экран 2. Желательный вывод для графа, показанного на рисунке 1

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

Тестовые данные

Группирование связанных элементов в T-SQL
Код 1. Создание таблицы T1 и заполнение ее данными

Используйте код 1 для создания таблицы Т1 и заполните его малым набором тестовых данных, представляющим граф, показанный на рисунке 1.

Обратите внимание: ограничение CHECK позволяет убедиться, что id1 меньше, чем id2. Это связано с тем, что граф ненаправленный, и сделано во избежание избыточности. Ненаправленное ребро 17—18 представляет два направленных ребра, 17->18 и 18->17, поэтому нет необходимости хранить в таблице оба. Если вы хотите разрешить вставку строк, где id2 > id1, но все же сохранять их с id1, имеющим меньшее значение, и id2, имеющим большее значение, чтобы исключить дубликаты, то можете поменять местами идентификаторы с помощью триггера INSTEAD OF (код 2).

Группирование связанных элементов в T-SQL
Код 2. Разрешение вставки строк с id2 > id1

Используйте малый набор тестовых данных для проверки логики и правильности решений. Для проверки производительности и масштабирования решений потребуется больший набор тестовых данных

Группирование связанных элементов в T-SQL
Код 3. Вспомогательная функция GetNums

Задействуйте программный код 3 для создания вспомогательной функции GctNums, которая возвращает последовательность целых чисел в требуемом диапазоне. Используйте программный код 4 для заполнения таблицы необходимым минимальным числом групп и строк на группу.

Группирование связанных элементов в T-SQL
Код 4. Заполнение таблицы необходимым минимальным числом групп и строк на группу

Назначьте собственные значения переменным @minnumgroups и @rowspcrgroup. Например, чтобы протестировать масштабируемость решения относительно количества групп, испытайте его с различными значениями @minnumgroups при неизменном @rowspergroup. Чтобы проверить масштабируемость решения относительно размера группы, испытайте его с различными значениями @rowspergroup при неизменном @minnumgroups.

И если вам нравятся задачи T-SQL, вы можете попытаться найти собственные решения, прежде чем знакомиться с моими. Желаю вам успеха!

Рейтинг статьи

Оценка
0/5
голосов: 0
Ваша оценка статье по пятибальной шкале:
 
 
   

Поделиться

Похожие новости

Комментарии

^ Наверх