Смежное дерево моделей списков, предотвращающее цикл

Question

Пример таблицы:

CREATE TABLE adj_list_model (
    id INT NOT NULL AUTO INCREMENT,
    parent_id INT,
    my_string varchar(255),//some random information
    PRIMARY KEY (id)
)

Дерево, которое я создаю, будет иметь несколько "корневых" пользователей в одной таблице (когда parent_id = NULL). Эти "корневые" пользователи могут в какой-то момент получить parent_id у какого-то "конечного" пользователя (пользователя, у которого под ним никого нет). У меня есть сомнение, как убедиться, что я не создаю "цикл", подобный следующему:

Пример дерева дизайна:

• • б
• • с
• • • d
• • • • е
• • • • е
• • • • • г

если пользователь "a" получает пользователя "g" в качестве его родителя, то созданный цикл будет:

a -> c -> d -> f -> g -> a -> c... and so on forever

ВОПРОС: Каков хороший способ проверить, находится ли пользователь "g" под пользователем "a", когда пользователь "a" хочет перейти под пользователем "g" в дереве? (чтобы в этих конкретных случаях действие можно было предотвратить)

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

---

РЕДАКТИРОВАНИЕ: Текущие варианты, которые я имел (хотя я скептически отношусь):

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

2. Проверка пути "корневого" пользователя перед тем, как дать ему родителя. Если в указанном выше случае пользователь "g" проверил свой путь, просматривая каждого пользователя выше g 1 на 1 (просматривая, каков был его родитель, снова и снова, пока не достигал корня), и обнаружил, что root был пользователем "a" тогда да, действие можно было бы предотвратить, хотя я не уверен, насколько напряженным будет это на сервере. Если у кого-то есть идея, дайте мне знать, пожалуйста!

Answer 1

Для опции с дополнительным столбцом root_id в синтаксисе MySql:

CREATE PROCEDURE change_root() 
BEGIN

  # this is the leaf node id, which will be the new parent of a root user
  SET @new_parent = x;
  # this is the old root user id, which will be the new child of the former leaf node
  SET @old_root = y;
  # get the leaf's root
  SET @new_root = SELECT root_id FROM adj_list_model WHERE id=x;

  # updating the dataset is possible as long as the leaf is not a child of the root user
  IF @new_root <> y THEN

    # link the former leaf to its new child
    UPDATE adj_list_model SET parent_id=x WHERE id=y;

    # @old_root is no longer a root, so update all occurences to the new root
    UPDATE adj_list_model SET root_id=@new_root WHERE root_id=@old_root;

  END IF;

END;

Это действительно не так сложно и гораздо быстрее, чем рекурсивное решение. Но, в конце концов, это зависит от вашей рабочей нагрузки и потребностей.