Иерархия без "В ИЕРАРХИИ"
Разработка - Математика и алгоритмы
Введение
Судя по статье Что делает "В ИЕРАРХИИ" в запросе?, интерес к теме работы с иерархическими данными в запросах еще не исчез. В то же время, решения, приведенные в статье Уровни, глубина, прародители, циклы и аналоги запросом, нуждаются в уточнениях и дополнениях.
Для этого есть несколько причин. Во-первых, запросы в статье Уровни, глубина, прародители, циклы и аналоги запросом были написаны как пример применения более общего приема "транзитивного замыкания". Но оказалось, что в частых случаях некоторых конкретных задач, таких как определения глубины, уровней и прародителей в справочниках, запросы могут быть реализованы эффективнее. Во-вторых, в исходной статье для удобства были приведены не запросы, а универсальные функции для их построения. Из-за чего у многих сложилось неверное представление, что речь идет об ограниченно используемой или не о чисто запросной технике. Это желательно поправить. В третьих, есть смысл посмотреть на проблему шире, с точки зрения того, как еще можно представлять иерархию. В четвертых, в запросах с того времени появились новые конструкции, одна из которых оказалась полезной при работе с иерархиями.
Итак, при представлении иерархических справочников в платформе 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 одним пакетным запросом было описано в [Уровни, глубина, прародители, циклы и аналоги запросом]. Предлагалось использовать следующий запрос:
К запросу можно сделать следующие комментарии:
В первом запросе пакета существующие связи иерархии дополняются самосоединениями элементов. Это нужно для накопления связей в формируемых временных таблицах. Затем получившаяся временная таблица соединяется сама с собой для нахождения в два раза более длинных связей. И так происходит несколько раз, пока длина найденных связей не превысит максимальный уровень иерархии. Этот уровень лучше задавать с запасом, чтобы каждый раз не менять запрос. Например, приведенный запрос может обработать иерархию, содержащую максимум шестнадцать уровней, что достаточно для большинства практических применений.
Для справочников из большого количества элементов со значительной глубиной иерархии число записей в таблице CT может оказаться довольно большим. Его можно оценить по формуле N*L, где N - число элементов в справочнике, L - средний уровень иерархии. Большое число записей приводит к пропорциональному росту времени соединений в процессе получения таблицы CT. Таким образом, получается, что подход работает для относительно небольших справочников - до нескольких тысяч элементов. Подход работает, но некоторые думают, что "...держать всех родителей на каждую запись — ужас тихий, особенно на глубоких случаях...".
Поэтому рассмотрим способы, свободные от этого недостатка.
2. Использование материализации путей
В этом случае элементы справочника дополнительно содержат строковое поле, содержащее путь к этому элементу от корня дерева иерархии. Для кодирования отрезков пути в большинстве случаев удобно использовать уникальные коды групп и элементов справочника. Для приводимого ранее примера таблица MP будет иметь вид:
Для получения таблицы MP по таблице AL можно использовать следующий пакетный запрос:
Приведенный запрос отличается от предыдущего тем, что временные таблицы хранят только по одному пути в направлении корня для каждого элемента. Для этого в первом запросе пакета добавляется не множество записей - по одной на каждую ссылку, а всего одна запись для корня, которая и будет использоваться для накопления путей.
Способ кодирования пути определяет ограничение представляемой иерархии. Максимальная длина строки, хранящейся в базе, равна 1024 символа. Следовательно, при девятизначном коде и одном разделителе возможно представить иерархию не более чем из 64 уровней. Очевидно, что для практики это несущественное ограничение.
Принцип построения приведенного запроса позволяет примерно в L раз быстрее получить уровни, глубину и прародителей элементов справочника. Вот пример запроса для уровней:
Сокращение до минимума числа записей представления иерархии, наглядность такого представления, возможность построения эффективного индекса по полю "путь" для различных, связанных с иерархией запросов - это все плюсы рассматриваемого представления.
Минус представления MP заключается в его недостаточной компактности по сравнению со способом, рассматриваемом далее.
3. Использование вложенных множеств (Nested Sets)
Этот способ заключается в том, что группы и элементы справочника нумеруются в порядке левостороннего обхода дерева иерархии таким образом, что все подчиненные группы и элементы получают диапазон номеров, входящий в диапазон номеров предков.
Для приводимого ранее примера таблица NS будет иметь вид
Данную таблицу можно построить по таблице MP следующим запросом, опирающимся на недавно появившуюся в запросах функцию АВТОНОМЕРЗАПИСИ().
Необходимо обратить внимание, что суффикс "\" в таблице "Триггер" выбран не просто так, а исходя из того, что он в таблице ASCII старше символа "/", который выбран в качестве разделителя пути. Из-за этого пути исходящих из узла веток будут при упорядочивании размещаться между значениями Путь + "" и Путь + "\", что и дает возможность их правильно пронумеровать. Поэтому при выборе другого разделителя пути следует не забыть выбрать соответствующий суффикс в таблице Триггер.
В принципе, существует возможность и непосредственного построения таблицы NS по таблице AL пакетным запросом, но для его демонстрации нужно было бы пожертвовать наглядностью, что делать не хочется.
Плюсом представления NS является его компактность, так как при этом вся развернутая иерархия справочника реализуется двумя простыми числовыми реквизитами, не требующими много места для своего хранения. Некоторым минусом может быть то, что при этом подходе отдельные редкие задачи будут переводить запросы на иерархию в запросы на интервалы, у которых есть свои сложности с использованием индексов. Хотя и это решается, например, при помощи приема из статьи Простой способ индексирования интервалов.
4. Заключение
В идеале статью можно было бы закончить вопросником, содержащим вопросы типа: "укажите относительную частоту чтения и записи в справочник", "укажите размер справочника", "укажите среднюю глубину иерархии в справочнике", "какую СУБД вы используете" и прочее. И дать потом расшифровку ответов в виде рекомендаций, что использовать: AL, CT, MP или NS. Но это невозможно без более подробных исследований и пока непонятно, насколько такое глубокое и "скучное" (по сравнению с составлением запросов) исследование вообще нужно.
Возможно, в статье также маловато примеров запросов для использования полученных представлений. Их предлагается придумать самостоятельно. А в качестве упражнений можно попробовать решить следующие задачи:
- Запросом определить все группы справочника, не содержащие подчиненных (на любом уровне вложенности) элементов.
- Запросом определить ближайшего общего предка списка заданных элементов.
- Определить число элементов, рекурсивно включенных в каждую группу справочника.
5. Использованные источники:
- Что делает "В ИЕРАРХИИ" в запросе?
- Уровни, глубина, прародители, циклы и аналоги запросом
- Иерархические структуры данных и Doctrine
- Деревья в SQL. Некоторые ответы на некоторые общие вопросы о деревьях и иерархиях SQL. Джо Селко
- Реализация иерархии — объединение Adjacency List и Materialized Path через one-to-many
- Строим Nested Set дерево без рекурсии
- Простой способ индексирования интервалов
Специальные предложения
См. также
[После]Новогодние задачи 5
30.12.2019 1149 Alxby 23
Готовые переносы данных из различных конфигураций 1C Промо
Рекомендуем готовые решения для переноса данных из различных конфигураций 1C. C техподдержкой от разработчиков и гарантией от Инфостарт.
Регистры бухгалтерии. Общая информация 116
05.09.2019 10344 YPermitin 22
"Хочу универсально!" [Часть 1] 67
02.09.2019 6424 SeiOkami 35
Новый раздел на Инфостарте - Electronic Software Distribution Промо
Инфостарт напоминает: на нашем сайте можно купить не только ПО, связанное с 1С. В нашем арсенале – ESD-лицензии на ПО от ведущих вендоров: Microsoft, Kaspersky, ESET, Dr.Web, Аскон и другие.
- Низкие цены, без скрытых платежей и наценок
- Оперативная отгрузка
- Возможность оплаты с личного счета (кешбек, обмен стартмани на рубли и т.п.)
- Покупки идут в накопления для получения скидочных карт лояльности Silver (5%) и Gold (10%)
EnterpriseData – часть 3. Загрузка данных, идентификация объектов 65
22.08.2019 6292 ids79 7
Обработчики событий при записи объектов. Зачем и что за чем? 247
25.07.2019 18979 4 AlbinaAAA 24
Перенос данных КА 1.1 / УПП 1.3 => БП 3.0 (перенос остатков, документов и справочников из "1С:Комплексная автоматизация 1.1" / УПП 1.3 в "1С:Бухгалтерия 3.0"). Обновлен до версий КА 1.1.115.х, УПП 1.3.130.х! Промо
Разработка позволяет перенести остатки по всем счетам бух.учета в программу "1С:Бухгалтерия предприятия 8", ред. 3.0 на выбранную дату начала ведения учета. Также переносятся документы за период и вся необходимая справочная информация. Правила оперативно обновляю при выходе новых релизов. Рассылка обновлений правил бесплатно в течение 12 месяцев. Есть видеодемонстрация проведения переноса данных. Конфигурации при использовании обмена остаются полностью типовыми. Перенос данных возможен в Бухгалтерию 3.0 версии ПРОФ, КОРП или базовую.
24700 руб.
Как проводятся документы в типовых конфигурациях от 1С 167
24.07.2019 19283 skv_79 35
FizzBuzz на 1С. Чем короче, тем веселее. Варианты принимаются... 8
24.07.2019 3508 vandalsvq 16
Онлайн-курс "Подготовка к экзамену 1С:Эксперт и 1С:Профессионал по технологическим вопросам" с 7 по 24 апреля 2020 г. Промо
На курсе вы получите практические навыки решения задач производительности 1С, в том числе характерных для высоконагруженных информационных систем (более 1000 пользователей). Подготовка к экзамену – только одна из составляющих курса. 70% слушателей приходят за знаниями, которые позволят расти и зарабатывать, делать сложные задачи на крупных проектах.
16450 рублей
Управление качеством кода 144
22.07.2019 10493 Stepa86 33
Что делает "В ИЕРАРХИИ" в запросе? 102
16.07.2019 11267 YPermitin 34
Перенос данных УПП 1.3 => ERP 2 (ЕРП) / УТ 11 / КА 2.х (обработка переноса документов, остатков и справочников из "1С:Управление производственным предприятием, ред. 1.3" в ERP / УТ 11 / КА 2). Обновлен до УПП 1.3.130.х, КА 2.4.11.х и ERP 2.4.11.х! Промо
Обработка позволяет переносить из УПП 1.3 в ERP 2 документы за выбранный период и остатки. Типовая обработка от фирмы 1С документы не переносит. Также исправлены ошибки типовой обработки. При выходе новых релизов обновление высылается бесплатно в течение года. Разработка будет полезна фирмам-франчайзи, которые периодически выполняют такой перенос данных для заказчиков. Вы можете один раз приобрести обработку переноса, и потом бесплатно получать обновления при выходе новых релизов конфигураций 1С.
29700 руб.
Создание отчетов с помощью СКД - основные понятия и элементы 225
25.06.2019 27700 ids79 17
Реализуем Стек, Очередь и Приоритетную очередь в 1С 52
24.06.2019 8813 RonX01 63
Подборка программ для взаимодействия с ЕГАИС Промо
ЕГАИС (Единая государственная автоматизированная информационная система) - автоматизированная система, предназначенная для государственного контроля за объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции. Инфостарт рекомендует подборку проверенных решений для взаимодействия с системой.
Организация хранения промежуточных данных 3
29.05.2019 2489 scientes 1
Вычисление 200 тысяч знаков числа pi 74
28.05.2019 4733 Oleg_nsk 96
Открыто голосование за доклады на INFOSTART MEETUP Krasnodar Промо
Выбирайте и голосуйте за самые интересные доклады, лучшие из них попадут в окончательную программу митапа. Голосование продлится до 30 января 2020 года.
Регистры накопления. Виртуальные таблицы. Часть №1: Обороты 88
20.05.2019 14469 YPermitin 5
Даем названия переменным: как префиксы экономят наше время 10
06.05.2019 3986 Designer1C 69
Подборка решений для взаимодействия со ФГИС «Меркурий» Промо
С 1 июля 2019 года все компании, участвующие в обороте товаров животного происхождения, должны перейти на электронную ветеринарную сертификацию (ЭВС) через ФГИС «Меркурий». Инфостарт предлагает подборку программ, связанных с этим изменением.
Заметки по SQL: Срез последних - аналог запроса 17
15.01.2019 7234 IVC_goal 5
Разработка и сценарное тестирование с Vanessa-ADD. Концепция, теория и сквозной пример создания сценария 236
09.01.2019 32047 Vladimir Litvinenko 69
INFOSTART MEETUP Krasnodar. 14 февраля 2020 г. Промо
Краснодар станет первым в 2020 году местом, где пройдет региональная встреча IT-специалистов сообщества Инфостарт. Тема мероприятия - управление и технологии автоматизации учета на платформе "1С: Предприятие". Стоимость участия - 5000 рублей. Цена действительна до 26.12.2019.
Многопоточное восстановление последовательностей 42
05.12.2018 8337 _ASZ_ 29
Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С 132
10.11.2018 25019 ids79 40
Программы для исполнения 54-ФЗ Промо
С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.
Основные понятия и механизмы оптимизации клиент-серверного взаимодействия в 1C 150
23.08.2018 26140 Rain88 44
Теорема номер тринадцать 15
15.03.2018 10100 vasilev2015 24
Базовый курс для начинающих 1С-программистов. Пятый поток. Онлайн-курс с 12 февраля по 15 апреля 2020 г. Промо
Данный онлайн-курс является начальной ступенью по изучению базовых принципов программирования в системе “1С:Предприятие” и предназначен для обучения 1С-программированию “с нуля”.
4500/9500 рублей
Введение в CI для 1С 87
21.11.2017 20366 real_MaxA 22
Как работает серверный вызов в 1С 463
18.11.2017 46841 pahich 77
Перенос документов, остатков и справочников КА 1.1 => КА 2 / УТ 11. Обновлено до КА 2.4.12.х и УТ 11.4.11.х! Промо
Более 130 компаний выполнили переход на КА 2 или УТ 11 с помощью нашей разработки! Позволяет перенести не только остатки и справочники (как типовая обработка), но и документы за нужный период времени. Предоставляем техподдержку, оперативно исправляем замечания, выпускаем обновления при выходе новых релизов программ 1С. Вы можете проверить разработку до покупки: сделаем бесплатный тестовый перенос из вашей базы КА 1.1 и предоставим доступ к базе-результату через веб-клиент!
29700 руб.
#Область ВНЕШНИЕ_ВЫЗОВЫ или MVC в 1С, библиотечность и упрощение интеграции кода 44
12.10.2017 15554 for_sale 58
Групповая разработка конфигураций в крупном холдинге 69
15.08.2017 18480 stas_ganiev 15