Избавляемся от колец (циклов) в иерархических/древовидных таблицах MSSQL

Категория: Код

– Автор: Игорь (Администратор)

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

Если вы не совсем понимаете о чем идет речь, то как пример, представьте, что у вас есть два каталога "A" и "Б". При этом каталог "А" содержит директорию "Б". И директория "Б" содержит каталог "А". В этом случае получается кольцо. Открывая директорию "А" вы увидите каталог "Б". Открыв каталог "Б" вы увидите директорию "А". И так далее. Иллюстрация на картинка чуть ниже. Та же самая проблема актуальна и для таблиц базы данных, которые ссылаются на себя. 

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

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

begin try
    drop table ##temptable;
end try
begin catch
end catch;
 
create table ##temptable (ID int, PID int null);
 
-- Создаем кольцо 1<->2
-- и вставляем обычный родительский элемент
insert into ##temptable(ID, PID)
values (1,2), (2,1), (3,null);
 
-- CTE для получения дерева
with tree
as (
    select ID, PID
    from ##temptable
    where PID is null
    union all
    select ##temptable.ID, ##temptable.PID
    from tree
        join ##temptable
            on tree.ID = ##temptable.PID
)
 
-- Вызов рекурсивного запроса для получения дерева
-- вернет только одну запись (3, null), проигнорировав записи из кольца
select *
from tree;
 
-- CTE для получения ветки для узла (1)
with treeProblem
as
(
    select ID, PID
    from ##temptable
    -- Указываем узел 1 как стартовый
    where ID = 1
    union all
    select ##temptable.ID, ##temptable.PID
    from treeProblem
        join ##temptable
            on treeProblem.ID = ##temptable.PID
)
 
-- Следующий запрос приведет к ошибке
-- Msg 530, Level 16, State 1, Line 31
-- The statement terminated. The maximum recursion 100 has been exhausted before statement completion.
select * 
from treeProblem
-- А если убрать комментарий с option (maxrecursion 0)
-- то такой запрос будет выполняться бесконечно, блокируя записи 1 и 2
--option(maxrecursion 0)
;
 
drop table ##temptable;

Примечание: Помните, что без специальных настроек и операндов, sql-запросы блокируют записи в таблицах.

Из-за чего происходит проблема с кольцами в иерархических таблицах MSSQL

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

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

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

Обычно, вся обработка такого рода ситуаций, если это предусмотрено в приложении, выносится на клиентский уровень, так как на клиенте уже имеется вся необходимая информация (тот же простой упорядоченный выпадающий список для выбора родительской категории). При этом, оставляя в базе данных лишь процедуру для обычной вставки в таблицу (или на web-сервере, если используется какой-либо генератор запросов по типу hibernate, linq и так далее).

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

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

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

Как обезопаситься при редактировании записей в древовидных таблицах MSSQL

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

begin try
    drop table ##temptable;
end try
begin catch
end catch;
 
create table ##temptable (ID int, PID int null);
 
-- Создаем небольшое дерево
insert into ##temptable(ID, PID)
values (1,null), (2,1), (3,2), (4,2), (5,1);
 
-- Попытаемся элементу 1 назначить в качестве родителя 
-- его дочерний элемент (4)
declare @ID int;
declare @PID int;
declare @IsExist int;
 
select @ID = 1, @PID = 4, @IsExist = 0;
 
-- Без специальной проверки, такое изменение возможно
-- Чтобы предусмотреть возможность создания кольца,
-- используем специальный рекурсивный запрос
with treeCheck
as
(
    select @ID as ID
    union all
    select t.ID
    from treeCheck tc
        join ##temptable t
            on tc.ID = t.PID
    -- Дальше найденного элемента нет необходимости искать
    where t.PID != @PID
)
 
-- Устанавливаем флаг, в случае если среди потомков 
-- нашелся дочерний элемент с ID равным PID
select @IsExist = 1
from treeCheck
where ID = @PID
;
 
if @IsExist = 1
    select 'Указываемый родительский элемент является дочерним. Редактирование запрещено';
else
    select 'Редактирование разрешено';
 
drop table ##temptable;

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

Теперь, уловка с клиентскими скриптами уже не поможет. Четвертый пункт (сохранение второй страницы) не пройдет успешно, так как перед каждым сохранением проверяются актуальные данные.

Примечание: Так как задачей данной статьи не является построение абсолютно устойчивой системы, то в статье не рассматривается решение для случая возникновения очень маловероятного риска возникновения колец в ходе выполнения параллельных запросов. Когда в нескольких параллельно выполняемых запросах одновременно успешно проходят проверки до момента изменения данных. По сути, как и в примере с клиентскими скриптами, только в очень маленький промежуток времени. Если вам все же интересно построение такого решения, то стоит начинать поиск решения в использовании блокировок и встраивании корректирующих проверок при обращении к дереву. 

Как проверить и обнаружить ошибки в существующих таблицах MSSQL

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

begin try
    drop table ##temptable;
end try
begin catch
end catch;
 
begin try
    drop table ##resultCircle;
end try
begin catch
end catch;
 
-- Древовидная таблица
create table ##temptable (ID int, PID int null);
create table ##resultCircle (ID int, [path] varchar(max));
 
-- Создадим небольшое дерево
insert into ##temptable(ID, PID)
values (1,null), (2,1), (3,2), (4,2), (5,1);
 
-- А так же наполним таблицу несколькими кольцами
insert into ##temptable(ID, PID)
values    (11,12), (12,13), (13,14), (14,11),
        (111,112), (112,113), (113,112);
 
-- переменные для поиска
declare @ID int;
declare @PID int;
declare @IsExist int;
declare @Path varchar(max);
 
-- Определяем курсор
declare cursorTempTable cursor for 
select ID, PID
from ##temptable
-- исключаем корневые элементы
where PID is not null 
 
open cursorTempTable
fetch next from cursorTempTable into @ID, @PID;
 
while @@FETCH_STATUS = 0
begin
    select @IsExist = 0;
 
    -- Чтобы не плодить записи в результирующей таблице с кольцами,
    -- исключаем элементы из уже найденных колец
    if not exists (select top 1 1
                    from ##resultCircle
                    where [path] like '% -> ' + rtrim(cast(@ID as varchar)) + ' -> %')
    begin
        -- Проходим по всем дочерним элементам 
        -- и составляем путь
        with treeCheck (ID, [path])
        as
        (
            select @ID as ID, cast(@ID as varchar(max)) as [path]
            union all
            select t.ID, 
                -- Строим путь кольца
                cast((rtrim(tc.[path]) + ' -> ' + rtrim(cast(t.ID as varchar(max)))) as varchar(max)) as [path]
            from treeCheck tc
                join ##temptable t
                    on tc.ID = t.PID
            -- Дальше найденного элемента нет необходимости искать
            where t.PID != @PID
        )
 
        -- Устанавливаем флаг, в случае если обнаружено кольцо,
        -- Записываем путь
        select @IsExist = 1,
            @Path = [path]
        from treeCheck
        where ID = @PID
        ;
 
        -- Записываем путь найденного кольца
        if @IsExist = 1
            insert into ##resultCircle (ID, [path])
            values (@ID, cast((rtrim(@Path) + ' -> ' + rtrim(cast(@ID as varchar(max)))) as varchar(max)));
    end
    
    -- Переходим к следующему элементу
    fetch next from cursorTempTable into @ID, @PID;
end
 
-- Выводим список всех колец
select *
from ##resultCircle
;
 
-- Закрываем курсор
close cursorTempTable;
deallocate cursorTempTable;
 
-- Удаляем темповые таблицы
drop table ##temptable;
drop table ##resultCircle;

Учитывайте, что если у вас большие таблицы, то запрос будет выполняться достаточно долго (в основном из-за необходимости строить дерево для большинства записей таблицы).

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