Иерархия без "В ИЕРАРХИИ"

Публикация № 1105799

Разработка - Математика и алгоритмы

иерархия запрос

110
Говорится о том, как эффективно представлять иерархию в СУБД, как получать и использовать эти представления при решении задач в запросной технике. Уточняются и дополняются запросы из статьи "Уровни, глубина, прародители, циклы и аналоги запросом" [https://infostart.ru/public/160707/].

 

Введение

Судя по статье Что делает "В ИЕРАРХИИ" в запросе?, интерес к теме работы с иерархическими данными в запросах еще не исчез. В то же время, решения, приведенные в статье Уровни, глубина, прародители, циклы и аналоги запросом, нуждаются в уточнениях и дополнениях.

Для этого есть несколько причин. Во-первых, запросы в статье Уровни, глубина, прародители, циклы и аналоги запросом были написаны как пример применения более общего приема "транзитивного замыкания". Но оказалось, что в частых случаях некоторых конкретных задач, таких как определения глубины, уровней и прародителей в справочниках, запросы могут быть реализованы эффективнее.  Во-вторых, в исходной статье для удобства были приведены не запросы, а универсальные функции для их построения. Из-за чего у многих сложилось неверное представление, что речь идет об ограниченно используемой или не о чисто запросной технике. Это желательно поправить. В третьих, есть смысл посмотреть на проблему шире, с точки зрения того, как еще можно представлять иерархию. В четвертых, в запросах с того времени появились новые конструкции, одна из которых оказалась полезной при работе с иерархиями.

Итак, при представлении иерархических справочников в платформе 1С:Предприятие, хранится только "остов" отношения иерархии, а именно, связь конкретного элемента с его непосредственным родителем. Из-за этого при поиске всех потомков одного элемента на уровне СУБД фактически используется цикл из нескольких последовательных запросов (Что делает "В ИЕРАРХИИ" в запросе?). При этом готовой конструкции, позволяющей выбрать всех предков одного элемента, вообще нет. В литературе способ, используемый в платформе, называется Adjacency List (AL).

Для того, чтобы быстро решать все задачи на иерархию, требуется "развертка" иерархии, где отношение непосредственно определено для любой пары элементов, независимо от того, находятся ли они на смежных уровнях или нет. В теории используется минимум три разновидности "развернутого" представления иерархии: использование полного списка потомков CT (Closure Table), путей к элементам MP (Matherialized Path), вложенных множеств NS (Nested Sets). Есть еще всевозможные модификации перечисленных способов: Реализация иерархии — объединение Adjacency List и Materialized Path через one-to-many, Строим Nested Set дерево без рекурсии.

Естественно думать, что развернутое представление иерархии должно храниться в СУБД. Это порождает проблему усложнения процедуры записи при изменениях в структуре справочника.  Например, изменение подчинения группы элементов требует переписывания путей во всех элементах группы. Но, вообще говоря, развернутое представление можно получать и "на лету" - непосредственно перед построением отчета. Это хотя и может несколько замедлить его выполнение, но не требует хранения избыточных данных в СУБД и их перестроения. В дальнейшем основной акцент изложения сделан именно на этом варианте. К тому же, этот способ не исключает первого, то есть того, что при необходимости развернутая иерархия, полученная приводимыми далее запросами, будет сохраняться в СУБД.

1. Использование полного списка потомков (Closure Table)

Это наиболее очевидный способ, заключающийся в том, что для каждого элемента иерархии составляется список всех элементов, которые непосредственно и опосредованно ему подчиняются.

Например, для структуры, изображенной на Фиг.1,

AL задается таблицей Таб.1,

а CT - таблицей Таб.2.

Получение таблицы CT по таблице AL одним пакетным запросом было описано в [Уровни, глубина, прародители, циклы и аналоги запросом]. Предлагалось использовать следующий запрос:

 
Запрос получения таблицы ClosureTable

К запросу можно сделать следующие комментарии:
В первом запросе пакета существующие связи иерархии дополняются самосоединениями элементов. Это нужно для накопления связей в формируемых временных таблицах. Затем получившаяся временная таблица соединяется сама с собой для нахождения в два раза более длинных связей. И так происходит несколько раз, пока длина найденных связей не превысит максимальный уровень иерархии. Этот уровень лучше задавать с запасом, чтобы каждый раз не менять запрос. Например, приведенный запрос может обработать иерархию, содержащую максимум шестнадцать уровней, что достаточно для большинства практических применений.

Для справочников из большого количества элементов со значительной глубиной иерархии число записей в таблице CT может оказаться довольно большим. Его можно оценить по формуле N*L, где N - число элементов в справочнике, L - средний уровень иерархии. Большое число записей приводит к пропорциональному росту времени соединений в процессе получения таблицы CT. Таким образом, получается, что подход работает для относительно небольших справочников - до нескольких тысяч элементов. Подход работает, но некоторые думают, что "...держать всех родителей на каждую запись — ужас тихий, особенно на глубоких случаях...".

Поэтому рассмотрим способы, свободные от этого недостатка.

2. Использование материализации путей

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

Для получения таблицы MP по таблице AL можно использовать следующий пакетный запрос:

 
Запрос получения таблицы Matherialized Path

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

Способ кодирования пути определяет ограничение представляемой иерархии. Максимальная длина строки, хранящейся в базе, равна 1024 символа. Следовательно, при девятизначном коде и одном разделителе возможно представить иерархию не более чем из 64 уровней. Очевидно, что для практики это несущественное ограничение.

Принцип построения приведенного запроса позволяет примерно в L раз быстрее получить уровни, глубину и прародителей элементов справочника. Вот пример запроса для уровней:

 
 Запрос для определения уровней групп и элементов справочника

Сокращение до минимума числа записей представления иерархии, наглядность такого представления, возможность построения эффективного индекса по полю "путь" для различных, связанных с иерархией запросов - это все плюсы рассматриваемого представления.

Минус представления MP заключается в его недостаточной компактности по сравнению со способом, рассматриваемом далее.

3. Использование вложенных множеств (Nested Sets)

Этот способ заключается в том, что группы и элементы справочника нумеруются в порядке левостороннего обхода дерева иерархии таким образом, что все подчиненные группы и элементы получают диапазон номеров, входящий в диапазон номеров предков.

Для приводимого ранее примера таблица NS будет иметь вид

Данную таблицу можно построить по таблице MP следующим запросом, опирающимся на недавно появившуюся в запросах функцию АВТОНОМЕРЗАПИСИ().

 
Запрос получения таблицы Nested Sets

Необходимо обратить внимание, что суффикс "\" в таблице "Триггер" выбран не просто так, а исходя из того, что он в таблице ASCII старше символа "/", который выбран в качестве разделителя пути. Из-за этого пути исходящих из узла веток будут при упорядочивании размещаться между значениями Путь + "" и Путь + "\", что и дает возможность их правильно пронумеровать. Поэтому при выборе другого разделителя пути следует не забыть выбрать соответствующий суффикс в таблице Триггер.

В принципе, существует возможность и непосредственного построения таблицы NS по таблице AL пакетным запросом, но для его демонстрации нужно было бы пожертвовать наглядностью, что делать не хочется.

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

4. Заключение

В идеале статью можно было бы закончить вопросником, содержащим вопросы типа: "укажите относительную частоту чтения и записи в справочник", "укажите размер справочника", "укажите среднюю глубину иерархии в справочнике", "какую СУБД вы используете" и прочее. И дать потом расшифровку ответов в виде рекомендаций, что использовать: AL, CT, MP или NS. Но это невозможно без более подробных исследований и пока непонятно, насколько такое глубокое и "скучное" (по сравнению с составлением запросов) исследование вообще нужно.

Возможно, в статье также маловато примеров запросов для использования полученных представлений. Их предлагается придумать самостоятельно. А в качестве упражнений можно попробовать решить следующие задачи:

  1. Запросом определить все группы справочника, не содержащие подчиненных (на любом уровне вложенности) элементов.
  2. Запросом определить ближайшего общего предка списка заданных элементов.
  3. Определить число элементов, рекурсивно включенных в каждую группу справочника.

 

5. Использованные источники:

  1. Что делает "В ИЕРАРХИИ" в запросе?
  2. Уровни, глубина, прародители, циклы и аналоги запросом
  3. Иерархические структуры данных и Doctrine
  4. Деревья в SQL. Некоторые ответы на некоторые общие вопросы о деревьях и иерархиях SQL. Джо Селко
  5. Реализация иерархии — объединение Adjacency List и Materialized Path через one-to-many
  6. Строим Nested Set дерево без рекурсии
  7. Простой способ индексирования интервалов

 

110

См. также

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
1. PerlAmutor 45 22.08.19 19:55 Сейчас в теме
Недавно решал задачу по хранению иерархии во внешнем источнике данных. Выбрал вложенные множества для этой цели. Пришлось дорабатывать процедуру конвертации Joe Celko с AL на свой формат хранения иерархических данных, у меня это был граф (многие родители могли в своем составе иметь одного и того же ребенка). После разрыва связей и дублировании подчинения, база со 100Мб и 400000 элементами, развернулась в деревья в 100Гб и 30 млн. записей. Пришлось пойти на жертвы, чтобы состав любого древа получался за линейное время. Узким местом оказалась сама ERP, куда хлынул поток ресурсных спецификаций изделий. С таким наплывом она не справилась. Но хуже всего дело обстоит у неё с версионированием ресурсных спецификаций. В структуре изделий периодически что-то меняется. Единственный выход - строить все заново каждый раз, так как уже созданные этапы производства трогать нельзя. Все это ведет к разбуханию базы мусорными данными, которые никогда больше использоваться не будут, но привязаны к документам.
MCV; jONES1979; Артано; gazpromsera; ildarovich; Rustig; +6 Ответить
3. Summer_13 22.08.19 21:48 Сейчас в теме
(1)Можно,пожалуйста, перестать писать комментарии под каждым постом,где требуется,что-то оптимизировать по вашему мнению?
4. PerlAmutor 45 23.08.19 06:22 Сейчас в теме
(3) Было бы неплохо, если 1С добавила новый вид регистра сведений - Иерархический, с одним из вариантов хранения данных, как минимум Adjacency List и Nested Sets. С добавлением к ним новых виртуальных функций позволяющих решать большинство задач связанных с поиском и модификации данных, без составления сложных запросов. А также методов преобразования иерархических данных из одного вида в другой и обратно.
Артано; Krio2; bulpi; Chai Nic; +4 Ответить
5. Chai Nic 129 23.08.19 08:11 Сейчас в теме
(4) Достаточно сделать для иерархических справочников "групповые агрегаты", то есть таблицу, которая бы хранила полную таблицу принадлежности групп и элементов, и обновлялась автоматически, эквивалентно механизму итогов и агрегатов. Тогда проверка на принадлежность будет выполняться за один индексный выбор СУБД. Разумеется, это должно быть опцией, галочкой в настройке справочника в конфигураторе.
6. SlavaKron 23.08.19 08:28 Сейчас в теме
(4)
с одним из вариантов хранения данных, как минимум Adjacency List

Так Adjacency List - это и есть текущий вариант хранения иерархии в 1С, насколько я понял.
13. PerlAmutor 45 23.08.19 19:56 Сейчас в теме
(6) В справочнике - да. Мне хочется иерархический регистр, чтобы без пометок на удаление, с возможностью перестроения деревьев в любой момент без контроля ссылочной целостности.
8. Rustig 1187 23.08.19 09:31 Сейчас в теме
(4) для таких задач создаете свои промежуточные таблицы, которые постоянно обновляются по определенным событиям. и не надо тогда будет использовать сложные запросы. универсального решения нет, под каждую задачу создаете свой механизм и логику. что-то подобное я описал здесь https://infostart.ru/public/195627/
2. Поручик 4312 22.08.19 20:22 Сейчас в теме
Статьи ildarovich'a можно сразу добавлять в избранное, не читая.
jONES1979; Krio2; gubanoff; NeviD; json; bulpi; u_n_k_n_o_w_n; Volosokrad1990; kuzyara; AllexSoft; skv_79; DarkAn; Ali1976; RocKeR_13; PLAstic; alalsl; Summer_13; acanta; BlizD; Yimaida; +20 Ответить
7. AlX0id 23.08.19 09:06 Сейчас в теме
(2)
Ага, и интеллект +1 моментально ))
user774630; +1 Ответить
9. Rustig 1187 23.08.19 09:33 Сейчас в теме
(7) не читая? уровень сложности статей 10 баллов из 10.... не все дочитают до конца, и не все поймут...
user774630; +1 Ответить
10. DarkAn 889 23.08.19 10:19 Сейчас в теме
(9) может и 10 и 11, пофиг. Главное, что читающий хочет в статье почерпнуть?

Если статьи читать, как художественную литературу - то да - скучно. А если попытаться разобраться в том, как "оно" работает, то это очень интересно и позволит увеличивает твою "копилку" инструментов.

При этом у автора, много статей опирающиеся на один метод - "Транзитивного замыкания" (есть и другие) и надо потратить свои усилия и разобраться в его работе. А далее уже продолжить изучать другие стати, где автор приводит примеры использования данного метода.

Лично мне данный метод очень пригодился, когда надо было найти всех "последних" потомков для кучи родителей. и стандартно пришлось бы писать запрос в цикле, что было бы долго, а воспользовавшись преложенным методом удалось все решить 1 запросом. Единственным неудобством данного метода я считаю - это то что запрос не "статичный", а генерируемый в зависимости от справочника, но это мелочи по сравнению с результатом.
15. gaglo 26.08.19 18:19 Сейчас в теме
(7) Муахахахахха, не моментально.... Интеллект +1 после прочтения добавленного и осознания прочитанного.
А моментально, не читая = +1 к чему-то другому.
11. bulpi 156 23.08.19 12:14 Сейчас в теме
"Максимальная длина строки, хранящейся в базе, равна 1024 символа. Следовательно, при девятизначном коде и одном разделителе возможно представить иерархию не более чем из 64 уровней."

Не понял. 1024/10=102, а не 64.
12. ildarovich 6671 23.08.19 12:51 Сейчас в теме
(11) Да, понял, что нужно было поподробнее пояснить, что я имел ввиду.

Сначала поле "Путь" будет длины 9 + 1 = 10.
В первом соединении его длина станет 20, во втором - 40, в третьем - 80, ..., шестом - 640.
Седьмое удваивающее соединение в приведенной схеме запроса сделать уже не получится, так как результат будет уже 1280 - больше допустимой длины строки.

Там еще есть детали по поводу юникода и что строка из-за этого может быть практически до 2048 длиной, но нужно проверять на разных СУБД конкретно. Также при желании эти 1024 можно плотнее упаковать, соединяя не MP6 и МР6, а МР6 и MP5, но для практики и 640 более чем достаточно.

Еще из важных мелких деталей, которые нужно не забыть добавить в статью, это символ разделителя "/" и символ "\" в таблице "триггер" в третьем запросе. Собственно какие конкретно символы не так важно. Главное, чтобы в таблице ASCII они шли именно в таком порядке: сначала - разделитель, потом - суффикс. Иначе нумерация не даст нужный результат и подчиненные (более длинные, продолжающиеся с разделителя) ветки не окажутся при сортировке позже Путь + "", но раньше Путь + "\" и тогда неправильно пронумеруются.
14. Alxby 460 23.08.19 20:33 Сейчас в теме
Большое спасибо за NS! Действительно, приведенные в конце статьи задачи при применении этого способа решаются довольно просто, особенно 1 и 3. Если же мы желаем «посмотреть на проблему шире, с точки зрения того, как еще можно представлять иерархию» для того, чтобы реализовать свои структуры иерархических данных, не связанных с иерархическими справочниками, то мне хотелось бы отметить несколько моментов:
1) AL: подвержен опасности появления циклов. В случае иерархического справочника за этим следит платформа, в своей реализации необходимо это делать самостоятельно. Добавление, удаление элементов, смена родителя происходит наиболее просто.
2) CT: необходимо обеспечить транзитивность отношения предок – потомок, т.е. если в ИБ хранятся пары 0001-0002 и 0002-0003, то должна быть и пара 0001-0003. Также возможно появление циклов. У элемента возможно появление нескольких непосредственных родителей. Добавление, удаление элементов, смена родителя требует пересчета всей ветки иерархии.
3) MP: циклов быть не может (если конечно в пути у элемента не будет повторяющихся кодов). Необходимо следить за соответствием путей элементов и путей родителей. Добавление, удаление элементов, смена родителя требует пересчета всех потомков этого элемента. Предъявляются повышенные требования к кодам, участвующим в образовании пути: желательно чтобы они были фиксированного размера и/или в них не должно быть символа-разделителя. Есть еще один неочевидный нюанс: часть задач при таком подходе будет решаться при помощи запросов с «LIKE» («ПОДОБНО»), а значит в кодах не должно быть «%» и «_»
4) NS: циклов быть не может. Легко «сломать» иерархию, повредив значение «Право» или «Лево» в каком-нибудь элементе. Плюсом является то, что наряду с отношением иерархии, этот метод определяет порядок элементов как внутри одного родителя, так и во всем множестве. Однако это может привести к тому, что добавление, удаление элементов, смена родителя может потребовать пересчета всего множества. Отношение подчиненности проверяется с помощью операций «больше», «меньше», что зачастую не позволит составить оптимальный запрос
ildarovich; +1 Ответить
16. ildarovich 6671 27.08.19 00:50 Сейчас в теме
(14) Очень хороший комментарий. Интересующимся данной темой обязательно нужно его прочитать. В целом согласен. То, что не для всех операций требуется контроль зацикливания или пересчет веток, и то, что есть приемы компенсации минусов каждого из представлений - это уже частности.
Оставьте свое сообщение