Prevent cycles in tree tables

from the Artful Common Queries page


A tree is a connected graph with no cycles, so in tree(id int primary key, parentid int), id must not be equal to parentid.

CHECK CONSTRAINT would seem a natural way to enforce this data integrity rule, but ...

  • before version 8.0, MySQL ignores CHECK CONSTRAINT syntax altogether, and
  • since version 8.0, a column CHECK CONSTRAINT may not refer to other columns; only a table CHECK CONSTRAINT can do this.
So with MySQL 8.0, to prevent same-row cycles in the database layer, give the table a table-level CHECK CONSTRAINT, e.g.,...
create table tree( 
  id int, 
  parentid int default null, 
  constraint check(id <> parentid)
);
But if ...
  • CHECK CONSTRAINT is unavailable, or
  • you prefer constraint failure to elicit a user-friendly message, e.g., from SIGNAL, or
  • a table-level CHECK CONSTRAINT is not possible
... then write Insert and Update Triggers that invoke SIGNAL messaging.

Insert Trigger

When id is auto_increment, this query finds the next auto_increment value for table `tree` in schema `trees` ...
select auto_increment
from information_schema.tables
where table_name = 'tree' and table_schema = 'trees';
... so an Insert Trigger to prevent cycles in a graph table would be ...
delimiter ;
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 = 'trees'
              );
  if new.parentid=idnew then
    signal sqlstate '45000' 
      set message_text = 'tree parentid may not equal id';
  end if;
end
go
delimiter ;

Update Trigger

Updates don't generate new auto_increment values, so the corresponding Update Trigger is simpler ...
drop trigger if exists tree_upd;
delimiter go
create trigger tree_upd before update on tree
for each row
begin
  if new.parentid=new.id then
    signal sqlstate '45000' 
      set message_text = 'tree parentid may not equal id';
  end if;
end$
delimiter ;

Last updated 7 May 2022