Preventing circular joining, recursive searches

Question

So in my situation I have three tables: list, item and list_relation.

Each item will be linked to a list through the list_id foreign key.

the list_relation looks like this:

CREATE TABLE list_relation
    (
        parent_id INT UNSIGNED NOT NULL,
        child_id INT UNSIGNED NOT NULL,

        UNIQUE(parent_id, child_id)

        FOREIGN KEY (parent_id)
            REFERENCES list (id)
                ON DELETE CASCADE,    

        FOREIGN KEY (child_id)
            REFERENCES list (id)
                ON DELETE CASCADE
    );

I want to be be able to inherit from multiple lists as well (which includes the related items).

For example I have list: 1, 2, 3.

I was wondering if there was any SQL way to prevent there from being a circular relation. E.g.

List 1 inherits from List 3, List 2 inherits from List 1, List 3 inherits from List 1.

1 -> 2 -> 3 -> 1

My current idea is that I would have to find out whether it would be circular by validating the desired inheritance first then inserting it into the DB.

Answer 1

If you use MySQL 8.0 or MariaDB 10.2 (or higher) you can try recursive CTEs (common table expressions).

Assuming the following schema and data:

CREATE TABLE `list_relation` (
  `child_id`  int unsigned NOT NULL,
  `parent_id` int unsigned NOT NULL,
  PRIMARY KEY (`child_id`,`parent_id`)
);
insert into list_relation (child_id, parent_id) values
    (2,1),
    (3,1),
    (4,2),
    (4,3),
    (5,3);

Now you try to insert a new row with child_id = 1 and parent_id = 4. But that would create cyclic relations (1->4->2->1 and 1->4->3->1), which you want to prevent. To find out if a reverse relation already exists, you can use the following query, which will show all parents of list 4 (including inherited/transitive parents):

set @new_child_id  = 1;
set @new_parent_id = 4;

with recursive rcte as (
  select *
  from list_relation r
  where r.child_id = @new_parent_id
  union all
  select r.*
  from rcte
  join list_relation r on r.child_id = rcte.parent_id
)
select * from rcte

The result would be:

child_id | parent_id
       4 |         2
       4 |         3
       2 |         1
       3 |         1

Demo

You can see in the result, that the list 1 is one of the parents of list 4, and you wouldn't insert the new record.

Since you only want to know if list 1 is in the result, you can change the last line to

select * from rcte where parent_id = @new_child_id limit 1

or to

select exists (select * from rcte where parent_id = @new_child_id)

BTW: You can use the same query to prevent redundant relations. Assuming you want to insert the record with child_id = 4 and parent_id = 1. This would be redundant, since list 4 already inherits list 1 over list 2 and list 3. The following query would show you that:

set @new_child_id  = 4;
set @new_parent_id = 1;

with recursive rcte as (
  select *
  from list_relation r
  where r.child_id = @new_child_id
  union all
  select r.*
  from rcte
  join list_relation r on r.child_id = rcte.parent_id
)
select exists (select * from rcte where parent_id = @new_parent_id)

And you can use a similar query to get all inherited items:

set @list = 4;

with recursive rcte (list_id) as (
  select @list
  union distinct
  select r.parent_id
  from rcte
  join list_relation r on r.child_id = rcte.list_id
)
select distinct i.*
from rcte
join item i on i.list_id = rcte.list_id

Answer 2

For those who do no have MySQL 8.0 or Maria DB and would like to use recursive method in MySQL 5.7. I just hope you don't have to exceed the max rec.depth of 255 manual:)

MySQL does not allow recursive functions, however it does allow recursive procedures. Combining them both you can have nice little function which you can use in any select command.

the recursive sp will take two input parameters and one output. First input is the ID you are searching the node tree for, second input is used by the sp to preserve results during the execution. Third parameter is the output parameter which carries the the end result.

CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_list_relation_recursive`(
    in itemId       text,
    in iPreserve    text,
    out oResult     text

)
BEGIN

    DECLARE ChildId text default null;

    IF (coalesce(itemId,'') = '') then
        -- when no id received retun whatever we have in the preserve container
        set oResult = iPreserve;
    ELSE
        -- add the received id to the preserving container
        SET iPreserve = concat_ws(',',iPreserve,itemId);
        SET oResult = iPreserve;

        SET ChildId = 
        (
            coalesce(
            (
                Select 
                    group_concat(TNode.child_id separator ',') -- get all children
                from 
                    list_relation as TNode 
                WHERE 
                    not find_in_set(TNode.child_id,     iPreserve) -- if we don't already have'em
                    AND find_in_set(TNode.parent_id,    itemId) -- from these parents
            )
        ,'')
        );

        IF length(ChildId) >0 THEN
            -- one or more child found, recursively search again for further child elements
            CALL sp_list_relation_recursive(ChildId,iPreserve,oResult);
        END IF;

    END IF;

    -- uncomment this to see the progress looping steps
    -- select ChildId,iPreserve,oResult;
END

test this:

SET MAX_SP_RECURSION_DEPTH = 250;
set @list = '';
call test.sp_list_relation_recursive(1,'',@list);
select @list;

+----------------+
|     @list      |
+----------------+
| ,1,2,3,6,4,4,5 |
+----------------+

don't mind about the duplicate parents or extra commas, we just want to know if an element exist in the node without having much if's and whens.

Looks fine sofar, but SP can't be used in select command so we just create wrapper function for this sP.

CREATE DEFINER=`root`@`localhost` FUNCTION `fn_list_relation_recursive`(
    NodeId int
) RETURNS text CHARSET utf8
    READS SQL DATA
    DETERMINISTIC
BEGIN

    /*
        Returns a tree of nodes
        branches out all possible branches
    */
    DECLARE mTree mediumtext;
    SET MAX_SP_RECURSION_DEPTH = 250;


    call sp_list_relation_recursive(NodeId,'',mTree);

    RETURN mTree;
END

now check it in action:

SELECT 
    *,
    FN_LIST_RELATION_RECURSIVE(parent_id) AS parents_children
FROM
    list_relation;

+----------+-----------+------------------+
| child_id | parent_id | parents_children |
+----------+-----------+------------------+
|        1 |         7 | ,7,1,2,3,6,4,4,5 |
|        2 |         1 |   ,1,2,3,6,4,4,5 |
|        3 |         1 |   ,1,2,3,6,4,4,5 |
|        4 |         2 |             ,2,4 |
|        4 |         3 |           ,3,4,5 |
|        5 |         3 |           ,3,4,5 |
|        6 |         1 |   ,1,2,3,6,4,4,5 |
|       51 |        50 |           ,50,51 |
+----------+-----------+------------------+

your inserts will look like this:

insert into list_relation (child_id,parent_id)
select
    -- child, parent
    1,6
where 
    -- parent not to be foud in child's children node
    not find_in_set(6,fn_list_relation_recursive(1));

1,6 should add 0 records. However 1,7 should work.

As always, i'm just proving the concept, you guys are more than welcome to tweak the sp to return a parent's children node, or child's parent node. Or have two separate SP for each node tree or even all combined so from a single single id it returns all parents and children.

Try it.. it's not that hard :)

Answer 3

Q: [is there] any SQL way to prevent a circular relation

A: SHORT ANSWER

There's no declarative constraint that would prevent an INSERT or UPDATE from creating a circular relation (as described in the question.)

But a combination of a BEFORE INSERT and BEFORE UPDATE trigger could prevent it, using queries and/or procedural logic to detect that successful completion of the INSERT or UPDATE would cause a circular relation.

When such a condition is detected, the triggers would need to raise an error to prevent the INSERT/UPDATE operation from completing.

Answer 4

Isn't better to put a column parent_id inside the list table?

Then you can get the list tree by a query with LEFT JOIN on the list table, matching the parent_id with the list_id, e.g:

SELECT t1.list_id, t2.list_id, t3.list_id
FROM list AS t1
LEFT JOIN list as t2 ON t2.parent_id = t1.list_id
LEFT JOIN list as t3 ON t3.parent_id = t2.list_id
WHERE t1.list_id = #your_list_id#

Is it a solution to your case? Anyway, I suggest you to read about managing hierarchical data in mysql, you can find a lot about this issue!