sql - Adjacent List Model Tree, preventing loop -

example table:

create table adj_list_model (     id int not null auto increment,     parent_id int,     my_string varchar(255),//some random information     primary key (id) ) 

the tree creating have multiple "root" users in same table (when parent_id = null). these "root" users may @ point acquire parent_id "leaf" user (user has no 1 under them). doubt have how make sure don't create "loop" similar following one:

example tree design:

• a
• • b
• • c
• • • d
• • • • e
• • • • f
• • • • • g

if user "a" acquires user "g" parent, loop created be:

a -> c -> d -> f -> g -> -> c... , on forever 

question: what's way check if user "g" under user "a" when user "a" wants go under user "g" in tree? (so in specific cases action can prevented)

key points consider: having 2 trees merging 1 happen often. if number of levels in tree hypothetically 80, amount of time might take checking prevent loops might considerable, why looking efficient method.

---

edited: current options have had (though skeptical) are:

1. creating column shows current "root" user each user in table. in cases, every time "root" user obtained parent, under him have updated new "root" user, , worries me how strain might put on server, if there lot of users , if there high frequency of "root" users obtaining parent.

2. checking "root" users path before giving him parent. if in case above user "g" had path checked looping through each user above g 1 1 (seeing parent was, on , on until getting root), , found root user "a", yes, action prevented, though not sure how straining on server. if has idea, let me know please!

for option additional root_id column, in mysql syntax:

create procedure change_root()  begin    # leaf node id, new parent of root user   set @new_parent = x;   # old root user id, new child of former leaf node   set @old_root = y;   # leaf's root   set @new_root = select root_id adj_list_model id=x;    # updating dataset possible long leaf not child of root user   if @new_root <> y      # link former leaf new child     update adj_list_model set parent_id=x id=y;      # @old_root no longer root, update occurences new root     update adj_list_model set root_id=@new_root root_id=@old_root;    end if;  end; 

this not complicated , faster recursive solution. in end depends on workload , needs.