Integrity rules in tree tables

from the Artful Common Queries page

A tree is a connected graph with no cycles, so the edge list table tree( id int, parentid int ) needs these rules enforced ...
  1. id values must not repeat, so id must be the primary key
  2. a non-null parentid must exist uniquely as an id in another row
  3. no cycles: no id may be equal to its parentid or occur as a parentid in its ancestor rows
  4. no id that is a parent to another id may be deleted

Enforcing the first three of these rules prevents Inserts from creating non-unique ids and new cycles, but it won't do so for Updates. Since version 8.0, MySQL implements CHECK CONSTRAINT, so you might expect that a constraint like … 

  check( id <> parentid and exists( select 1 from tree where id=parentid ) )
… would prevent both new within-row cycles and orphaned ids, but MySQL's CHECK CONSTRAINT prohibits the non-deterministic EXISTS() call. Neither can CHECK CONSTRAINT provide user-friendly error messaging by invoking SIGNAL, or prevent deletion of parent rows.

So a tree table needs Insert, Update and Delete Triggers. These Triggers work with MySQL 5.7 nd 8.0 ...

Insert Trigger

An Insert Trigger in a tree table without PRIMARY KEY(id) needs to check that the id does not already exist in the tree. With or without PRIMARY KEY(id), it must check that the id value does not cycle with its own parentid.

When id is auto_increment, this query finds the next auto_increment value for table `tree` in schema `test` ... 

select auto_increment
from information_schema.tables
where table_name = 'tree' and table_schema = 'test';
So, the Insert Trigger where id is auto_increment ... 
drop trigger if exists tree_ins;
delimiter go
create trigger tree_ins before insert on tree for each row
begin  
  declare idnew int;
  set idnew = (select auto_increment
               from information_schema.tables
               where table_name = 'tree' and table_schema = 'test'
              );
  if exists( select 1 from tree where id=idnew) then
    signal sqlstate '45000' set message_text='id already exists';
  elseif new.id=new.parentid then
    signal sqlstate '45000' set message_text='id must not equal parentid';
  elseif not exists( select 1 from tree where id=new.parentid) then
    signal sqlstate '45000' set message_text = 'Invalid parentid';
  end if;
end;
go
delimiter ;
If id is not auto_increment, the Insert Trigger is simpler ... 
drop trigger if exists tree_ins;
delimiter go
create trigger tree_ins before insert on tree for each row
begin  
  if exists( select 1 from tree where id=new.id) then
    signal sqlstate '45000' set message_text='id already exists';
  elseif new.id=new.parentid then
    signal sqlstate '45000' set message_text='id must not equal parentid';
  elseif not exists( select 1 from tree where id=new.parentid) then
    signal sqlstate '45000' set message_text = 'Invalid parentid';
  end if;
end;
go
delimiter ;

Update Trigger

The Update Trigger needs to enforce all the tree rules ... 
drop trigger if exists tree_upd;
delimiter go
create trigger tree_upd before update on tree for each row
begin
  if new.id<>old.id and exists( select 1 from tree where id=new.id ) then
    signal sqlstate '45000' set message_text = 'id already exists';
  elseif new.parentid is not null 
         and not exists( select id from tree where id=new.parentid) then 
    signal sqlstate '45000' 
      set message_text='parentid not found as id in the table';
  elseif new.id=new.parentid then
    signal sqlstate '45000' set message_text = 'id may not equal parentid';
  else
    set @thisparent=new.parentid, @ret=1;
    repeat                    -- WALK THE ANCESTOR PATH
      select parentid,count(*) into @parentid,@rows from tree where id=@thisparent;
      if @rows>0 then
        if @parentid=new.id then
          set @ret=0;
          signal sqlstate '45000' set message_text='cycle detected';
        else
          set @thisparent=@parentid;
        end if;
      end if;
    until @ret=0 or @parentid is null or @rows=0 end repeat;  
  end if;
end;
go
delimiter ;

Delete Trigger

create trigger tree_del before delete on tree for each row
begin
  if exists(select parentid from tree where parentid=old.id) then
    signal sqlstate '45000' 
      set message_text = 'Row id referenced by other row(s), may not be deleted';    
  end if;
end;

Last updated 30 Aug 2022