Как в 1С запросом или программно разузловать цепочку связанных элементов и проверить зацикливание?

← На главную

В практике разработки на платформе 1С часто встречается задача разузлования или поиска всех связанных элементов. Классический пример: справочник ссылается сам на себя через реквизит, образуя ориентированный граф или цепочку вида Э1 → Э2 → Э3 → ... → ЭN. Подобные структуры применяются при описании спецификаций номенклатуры, технологических карт, этапов бизнес-процессов или маршрутов согласования.

Перед разработчиком встает вопрос: можно ли получить всю цепочку подчиненности одним запросом 1С, как обойти возможные зацикливания и какой подход обеспечит максимальное быстродействие на больших объемах данных? Разберем эту задачу детально, сопоставим теоретические возможности языка запросов и эффективные алгоритмы обработки данных в оперативной памяти.

Ограничения языка запросов 1С при работе с произвольными графами

Выясним причину, почему классический «один запрос» сталкивается с фундаментальными трудностями. Язык запросов 1С не поддерживает стандартные рекурсивные обобщенные табличные выражения (конструкции вида WITH RECURSIVE), которые присутствуют в некоторых СУБД. Конструкции языка В ИЕРАРХИИ и ИТОГИ ПО ... ИЕРАРХИЯ работают исключительно со стандартным системным реквизитом Родитель в иерархических справочниках. Если связь реализована через произвольный реквизит (например, Элемент) или отношение представляет собой ориентированный граф (у одного узла может быть несколько родителей и потомков), стандартная иерархия платформы оказывается неприменимой.

Вариант 1. Построение транзитивного замыкания пакетом запросов (метод удвоения шага)

Рассмотрим математический подход, позволяющий решить задачу на стороне СУБД с помощью формирования пакетного запроса. Этот алгоритм строит транзитивное замыкание графа методом возведения матрицы смежности в степень за счет последовательного удвоения длины пути. За $k$ итераций соединения таблицы самой с собой мы можем охватить путь длиной до $2^k$ узлов.

Разберем по шагам программное формирование такого пакетного запроса:

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

Посмотрим на пример реализации данного алгоритма:


// Определяем максимальную длину цепочки связей
ЗапросКоличество = Новый Запрос(
    "ВЫБРАТЬ КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Справочник.Ссылка) КАК ЧислоВершин 
    |ИЗ Справочник.Справочник КАК Справочник"
);
РезультатКоличество = ЗапросКоличество.Выполнить().Выгрузить();
МаксимальнаяДлинаПути = РезультатКоличество[0].ЧислоВершин;

Запрос = Новый Запрос;
Запрос.МенеджерВременныхТаблиц = Новый МенеджерВременныхТаблиц;

// Формируем начальный набор связей (длина пути = 1)
Пролог = 
"ВЫБРАТЬ РАЗЛИЧНЫЕ
|   Справочник.Ссылка КАК НачалоДуги,
|   Справочник.Ссылка КАК КонецДуги
|ПОМЕСТИТЬ ЗамыканияДлины1
|ИЗ
|   Справочник.Справочник КАК Справочник
|ОБЪЕДИНИТЬ
|ВЫБРАТЬ
|   Справочник.Ссылка,
|   Справочник.Элемент
|ИЗ
|   Справочник.Справочник КАК Справочник
|;
|";

// Шаблон итерации: соединение пар для удвоения длины пути
Рефрен = 
"ВЫБРАТЬ РАЗЛИЧНЫЕ
|   ПерваяДуга.НачалоДуги,
|   ВтораяДуга.КонецДуги
|ПОМЕСТИТЬ ЗамыканияДлины#2
|ИЗ
|   ЗамыканияДлины#1 КАК ПерваяДуга
|   ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЗамыканияДлины#1 КАК ВтораяДуга
|   ПО ПерваяДуга.КонецДуги = ВтораяДуга.НачалоДуги
|;
|УНИЧТОЖИТЬ ЗамыканияДлины#1
|;
|";

Эпилог = 
"ВЫБРАТЬ
|   Дуга.КонецДуги КАК Элемент
|ИЗ
|   ЗамыканияДлины#2 КАК Дуга
|ГДЕ
|   Дуга.НачалоДуги = &Ссылка";

Запрос.Текст = Пролог;
МаксимальнаяДлинаЗамыканий = 1;

Пока МаксимальнаяДлинаЗамыканий < МаксимальнаяДлинаПути Цикл
    ТекстИтерации = СтрЗаменить(Рефрен, "#1", Формат(МаксимальнаяДлинаЗамыканий, "ЧГ=0"));
    ТекстИтерации = СтрЗаменить(ТекстИтерации, "#2", Формат(2 * МаксимальнаяДлинаЗамыканий, "ЧГ=0"));
    Запрос.Текст = Запрос.Текст + ТекстИтерации;
    МаксимальнаяДлинаЗамыканий = 2 * МаксимальнаяДлинаЗамыканий;
КонецЦикла;

Запрос.Текст = Запрос.Текст + СтрЗаменить(Эпилог, "#2", Формат(МаксимальнаяДлинаЗамыканий, "ЧГ=0"));
Запрос.УстановитьПараметр("Ссылка", ИсходныйЭлемент);

Результат = Запрос.Выполнить().Выгрузить();

Проанализируем эффективность этого решения. Декларативно код выглядит компактно, однако при большом числе вершин алгоритм соединения временных таблиц в базе данных порождает колоссальную нагрузку. В наихудшем случае сложность внутренних соединений растет как $O(N^4)$, а постоянная запись промежуточных таблиц во временную базу СУБД (TempDB) приводит к дисковым задержкам. Данный способ подходит только для небольших графов (до нескольких сотен вершин).

Вариант 2. Итеративный обход в памяти с предварительной индексацией таблицы

Рассмотрим альтернативный и значительно более производительный способ. Вместо генерации множества запросов или тяжелых соединений на стороне СУБД мы выполняем ровно один простой запрос, получающий весь список связей, выгружаем его в память и индексируем.

Разберем по шагам алгоритм последовательного обхода дерева/графа в ширину (BFS):

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

Посмотрим на пример кода:


Запрос = Новый Запрос(
    "ВЫБРАТЬ
    |   Справочник.Ссылка КАК Ссылка,
    |   Справочник.Элемент КАК Элемент
    |ИЗ
    |   Справочник.Справочник КАК Справочник
    |ГДЕ
    |   Справочник.Элемент <> ЗНАЧЕНИЕ(Справочник.Справочник.ПустаяСсылка)"
);

Дуги = Запрос.Выполнить().Выгрузить();
Дуги.Индексы.Добавить("Ссылка");

Результат = Новый СписокЗначений;
Результат.Добавить(ИсходныйЭлемент);

Отбор = Новый Структура("Ссылка");
Указатель = 0;

Пока Указатель < Результат.Количество() Цикл
    ТекущийУзел = Результат[Указатель].Значение;
    Отбор.Ссылка = ТекущийУзел;
    
    НайденныеДуги = Дуги.НайтиСтроки(Отбор);
    Для Каждого СтрДуга Из НайденныеДуги Цикл
        // Контроль зацикливания: добавляем только те узлы, которых еще нет в цепочке
        Если Результат.НайтиПоЗначению(СтрДуга.Элемент) = Неопределено Тогда
            Результат.Добавить(СтрДуга.Элемент);
        КонецЕсли;
    КонецЦикла;
    
    Указатель = Указатель + 1;
КонецЦикла;

Такой подход обрабатывает графы в сотни тысяч узлов за считанные секунды, так как основная работа выполняется в оперативной памяти без повторных обращений к СУБД.

Вариант 3. Оптимизированная рекурсия с кэшированием поддеревьев (динамическое программирование)

В реальных задачах разузлования (например, при расчете состава изделий в производстве) граф часто представляет собой ориентированный ациклический граф (DAG). Один и тот же полуфабрикат или узел может входить в состав десятка различных сборок на разных уровнях иерархии. Если раскручивать каждую ветку «в лоб», возникает комбинаторный взрыв, и число просматриваемых путей стремительно растет.

Проанализируем оптимизацию: чтобы избежать повторного обхода одних и тех же ветвей, необходимо запоминать уже рассчитанный результат разузлования каждого узла (мемоизация). Для ускорения поиска и контроля циклов вместо линейного поиска следует использовать объект Соответствие, обеспечивающий время поиска $O(1)$.

Посмотрим, как организовать процедуру обхода с контролем зацикливания:


// СтекТекущейВетки - Соответствие: хранит вершины текущего пути для отслеживания циклов
// КэшРазузлования - Соответствие: Ключ - Узел, Значение - Таблица материалов
Функция РазузловатьВетку(ТекущийУзел, ТаблицаСвязей, СтекТекущейВетки, КэшРазузлования)
    
    // Проверка зацикливания в текущей ветке
    Если СтекТекущейВетки[ТекущийУзел] <> Неопределено Тогда
        ВызватьИсключение "Обнаружен цикл в графе для узла: " + Строка(ТекущийУзел);
    КонецЕсли;
    
    // Проверка наличия уже готового результата в кэше
    Если КэшРазузлования[ТекущийУзел] <> Неопределено Тогда
        Возврат КэшРазузлования[ТекущийУзел];
    КонецЕсли;
    
    СтекТекущейВетки.Вставить(ТекущийУзел, Истина);
    
    СтрокиПодчиненных = ТаблицаСвязей.НайтиСтроки(Новый Структура("Владелец", ТекущийУзел));
    ИтоговыйСостав = Новый ТаблицаЗначений;
    ИтоговыйСостав.Колонки.Добавить("Номенклатура");
    ИтоговыйСостав.Колонки.Добавить("Количество");
    
    Для Каждого Стр Из СтрокиПодчиненных Цикл
        // Рекурсивно получаем состав подчиненного элемента
        СоставДочернего = РазузловатьВетку(Стр.Номенклатура, ТаблицаСвязей, СтекТекущейВетки, КэшРазузлования);
        
        Если СоставДочернего.Количество() = 0 Тогда
            // Листовой элемент (материал)
            Нов = ИтоговыйСостав.Добавить();
            Нов.Номенклатура = Стр.Номенклатура;
            Нов.Количество = Стр.Количество;
        Иначе
            // Добавляем узлы с учетом коэффициента вхождения
            Для Каждого СтрПодч Из СоставДочернего Цикл
                Нов = ИтоговыйСостав.Добавить();
                Нов.Номенклатура = СтрПодч.Номенклатура;
                Нов.Количество = СтрПодч.Количество * Стр.Количество;
            КонецЦикла;
        КонецЕсли;
    КонецЦикла;
    
    // Сворачиваем одинаковые материалы
    ИтоговыйСостав.Свернуть("Номенклатура", "Количество");
    
    // Снимаем узел со стека текущего пути и помещаем в глобальный кэш
    СтекТекущейВетки.Удалить(ТекущийУзел);
    КэшРазузлования.Вставить(ТекущийУзел, ИтоговыйСостав);
    
    Возврат ИтоговыйСостав;
КонецФункции

Архитектурные рекомендации по хранению графов в 1С

Если задача разузлования является регулярной операцией в системе, имеет смысл пересмотреть способ хранения связей:

Рекурсивные связи в СКД. Система компоновки данных умеет связывать наборы данных «сами с собой» через вкладку «Связи наборов данных». Внутренний механизм СКД выполняет порционную выборку и строит иерархическое дерево без риска зависания сеанса.
Таблица транзитивных замыканий (Closure Table). Создается периодический или независимый регистр сведений с измерениями Предок, Потомок и ресурсом Глубина. Все связи пересчитываются один раз при записи элемента или спецификации. В этом случае получение всего дерева подчиненности любой глубины решается тривиальным запросом: ГДЕ Предок = &ВыбранныйУзел.
Кэш разузлования. Для производственных спецификаций плоский состав готового изделия записывается в отдельный регистр при утверждении спецификации. При проведении документов списание выполняется по регистру без динамического пересчета деревьев.