Recursive parent child problem in MariaDB-CodePudding

I have run into this a couple of times where a client is able to import data into a catalog with parent child relationships and I run into problems with said relationships. I need to find a way to prevent the following:

Object 1 has a child of Object 2
Object 2 has a child of Object 3
Object 3 has a child of Object 1

This throws the server into an infinite recursive loop and ultimately brings it to its knees. I can't seem to wrap my head around a SQL query that I could use to detect such recursive madness. The problem is prevalent enough that I need to find some solution. I've tried queries using CTE, nested selects/sub-selects and just can't seem to write one that will solve this issue. Any help would be greatly appreciated.

with recursive parents as (
    select
        s.id,
        s.parent_id,
        1 as depth
    from categories s
    where s.id = <passed in id>
    union all
    select
        t.id,
        t.parent_id,
        c.depth   1 as depth
    from categories t
        inner join parents c
            on t.id = c.parent_id
    where t.id <> t.parent_id)
select distinct parent_id from parents where parent_id <> 0 order by depth desc

CodePudding user response：

Looks like you have this figured out to stop a cycling event but are looking for ways to identify a cycle. In that case, consider using a path:

with recursive parents as (
    select
        s.id,
        s.parent_id,
        1 as depth,
        CONCAT(s.id,'>',s.parent_id) as path,
        NULL as cycle_detection
    from categories s
    where s.id = <passed in id>
    union all
    select
        t.id,
        t.parent_id,
        c.depth   1 as depth,
        CONCAT(c.path, '>', t.parent_id),
        CASE WHEN c.path LIKE CONCAT('%',t.parent_id,'>%') THEN 'cycle' END
    from categories t
        inner join parents c
            on t.id = c.parent_id
    where t.id <> t.parent_id)
select distinct parent_id, cycle_detection from parents where parent_id <> 0 order by depth desc

I may be a bit off my syntax since it's been forever since I wrote mysql/mariadb syntax, but this is the basic idea. Capture the path that the recursion took and then see if your current item is already in the path.

CodePudding user response：

If the depth of the resulting tree is not extremely deep then you can detect cycles by storing the bread crumbs that the recursive CTE is walking. Knowing the bread crumbs you can detect cycles easily.

For example:

with recursive
n as (
  select id, parent_id, concat('/', id, '/') as path 
  from categories where id = 2
 union all
  select c.id, c.parent_id, concat(n.path, c.id, '/')
  from n
  join categories c on c.parent_id = n.id
  where n.path not like concat('%/', c.id, '/%') -- cycle pruning here!
)
select * from n;

Result:

 id  parent_id  path    
 --- ---------- ------- 
 2   1          /2/     
 3   2          /2/3/   
 1   3          /2/3/1/

See running example at DB Fiddle.