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.
6 Answers
Answers 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 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 Answers 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 :)
Answers 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.
Answers 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!
Answers 5
Do you mind if you need to add an additional table?
A SQL way and efficient way to do this is to create an additional table which contains ALL parents for every child. And then check to see if the potential child exists in the parent list of the current node before the inheritance is established.
The parent_list table would be something like this:
CREATE TABLE parent_list ( list_id INT UNSIGNED NOT NULL, parent_list_id INT UNSIGNED NOT NULL, PRIMARY KEY (list_id, parent_list_id) ); Now, let's start at the very beginning.
2 inherit from 1 and 4.
parent_listis empty, which means both 1 and 4 have no parents. So it's fine in this case.
After this step,parent_listshould be:list_id, parent_list_id
2, 1
2, 43 inherit from 2.
2 have two parents, 1 and 4. 3 isn't one of them. So it's fine again.
Nowparent_listbecomes(Note that 2's parents should be 3's parents also):list_id, parent_list_id
2, 1
2, 4
3, 1
3, 4
3, 24 inherit from 3.
4 exists in 3's parent list. This will lead to a cycle. NO WAY!
To check whether the cycle will happen, you just need one simple SQL:
SELECT * FROM parent_list WHERE list_id = potential_parent_id AND parent_list_id = potential_child_id; Want to do all these things with one call? Apply a stored procedure:
CREATE PROCEDURE 'inherit'( IN in_parent_id INT UNSIGNED, IN in_child_id INT UNSIGNED ) BEGIN DECLARE result INT DEFAULT 0; DECLARE EXIT HANDLER FOR SQLEXCEPTION BEGIN ROLLBACK; SELECT -1; END; START TRANSACTION; IF EXISTS(SELECT * FROM parent_list WHERE list_id = in_parent_id AND parent_list_id = in_child_id) THEN SET result = 1; -- just some error code ELSE -- do your inserting here -- update parent_list INSERT INTO parent_list (SELECT in_child_id, parent_list_id FROM parent_list WHERE list_id = in_parent_id); INSERT INTO parent_list VALUES (in_child_id, in_parent_id); END IF; COMMIT; SELECT result; END When it comes to a multiple inheritance, just call inherit multiple times.
Answers 6
In the example you provide, the errant relationship is simple. It's the 3 -> 1 and 1-> 3 relationships. You could simply look for the inverse relationships when inserting a new row. If it exists, don't insert the new row.
If you add an auto-incrementing column, you could then identify the offending rows specifically.
On the other hand, if you are looking at existing rows, you could identify the errant rows using a simple SQL statement like:
SELECT a.parent_id, a.child_id FROM list_relation a JOIN list_relation b ON a.child_id = b.parent_id AND a.parent_id = b.child_id If you add an auto-incrementing column, you could then identify the offending rows specifically.
Your question title includes the word "prevent", so I presume you want to avoid adding the rows. To do so, you would need a ON BEFORE INSERT trigger that checks for an existing row and prevents the insert. You could also use an ON BEFORE UPDATE trigger to prevent existing rows from being changed to values that would be a problem.
0 comments:
Post a Comment