Nested Sets + MySQL TRIGGER
Task
The task is the same as in the previous article , only applicable to MySQL.
Rake
Good news guys! There is no problem with recursive triggers in MySQL ! MySQL developers just stupidly lock a mutable table even at the trigger level, here are the radishes. But, in fact, only a power outage can stop us.
There is a small loophole, with ... joined tables. Although I did not find confirmation in the documentation that it was so specially conceived, there was no denying either. True, there is a possibility that this loophole can be covered, although I do not see the point.
Alas, the trigger mechanism in MySQL is new and rather crude, which imposes some restrictions on its use, but still it is enough to solve our problem.
So, the source table:
SQL code (1)
CREATE TABLE `ns_tree` ( `id` int (11) NOT NULL auto_increment, `left_key` int (11) NOT NULL default '0', `right_key` int (11) NOT NULL default '0', `level` int (11) NOT NULL default '0', `parent_id` int (11) NOT NULL default '0', `tree` int (11) NOT NULL default '1', `field1` text, PRIMARY KEY (`id`) ) ENGINE = MyISAM;
Based on it, we make exactly the same table, with exactly the same set of fields:
SQL code (2)
CREATE TABLE `_ns_tree` ( `id` int (11) NOT NULL auto_increment, `left_key` int (11) NOT NULL default '0', `right_key` int (11) NOT NULL default '0', `level` int (11) NOT NULL default '0', `parent_id` int (11) NOT NULL default '0', `tree` int (11) NOT NULL default '1', `field1` text, PRIMARY KEY (`id`) ) ENGINE = MERGE INSERT_METHOD = LAST UNION = (`ns_tree`);
Keyword - MERGE essentially we create a view of our table, with which we can work as a table. In general, the MERGE mechanism is also a bit damp. The structure of the joined table must be exactly the same as the original.
IMPORTANT!!! When you change the structure of the original table, the connection between the tables is lost, but between the already connected rows - NO! Be careful. When you change the structure of the source table, you must apply the same change to the combined one!
Also, the source table must be MyISAM, it is understandable, transactions in this case are not applicable due to the fact that the tables can not lock each other, and the data in them is the same. However, this is not scary for us, since the source table will be locked within the trigger, and we will change the data from the combined table from the triggers, so there can be no intersections of queries.
Also, what I wanted to draw attention to: I strongly recommend that you do not use root nodes within the same tree (as I mentioned in the previous article), since the table is completely blocked, and too long a queue can be formed.
Create Record
The MySQL trigger dialect is slightly different from the PostgreSQL dialect :
- It is not necessary to declare variables at the beginning of the procedure;
- It is impossible to interrupt the execution of a trigger, it must work out completely;
- As mentioned above, we are not afraid of recursion, therefore we will not need extra checks and additional fields;
- Variables appear in the course of the code;
- Instead of returning from the trigger, we wrap the code with conditions;
- All changes concerning the structure of the tree are applied to the auxiliary joint table;
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_ins_tr` BEFORE INSERT ON` ns_tree` FOR EACH ROW BEGIN SET @left_key: = 0; SET @level: = 0; - If we indicated the parent: IF NEW.parent_id IS NOT NULL AND NEW.parent_id> 0 THEN SELECT right_key, `level` + 1 INTO @left_key, @level FROM ns_tree WHERE id = NEW.parent_id AND tree = NEW.tree; END IF; - If we specified the left key: IF NEW.left_key IS NOT NULL AND NEW.left_key> 0 AND (@left_key IS NULL OR @left_key = 0) THEN SELECT id, left_key, right_key, `level`, parent_id INTO @tmp_id, @tmp_left_key, @tmp_right_key, @tmp_level, @tmp_parent_id FROM ns_tree WHERE tree = NEW.tree AND (left_key = NEW.left_key OR right_key = NEW.left_key); IF @tmp_left_key IS NOT NULL AND @tmp_left_key> 0 AND NEW.left_key = @tmp_left_key THEN SET NEW.parent_id: = @tmp_parent_id; SET @left_key: = NEW.left_key; SET @level: = @tmp_level; ELSEIF @tmp_left_key IS NOT NULL AND @tmp_left_key> 0 AND NEW.left_key = @tmp_right_key THEN SET NEW.parent_id: = @tmp_id; SET @left_key: = NEW.left_key; SET @level: = @tmp_level + 1; END IF; END IF; - If the parent or left key is not specified, or we did not find anything IF @left_key IS NULL OR @left_key = 0 THEN SELECT MAX (right_key) + 1 INTO @left_key FROM ns_tree WHERE tree = NEW.tree; IF @left_key IS NULL OR @left_key = 0 THEN SET @left_key: = 1; END IF; SET @level: = 0; SET NEW.parent_id: = 0; END IF; - Set new key values SET NEW.left_key: = @left_key; SET NEW.right_key: = @left_key + 1; SET NEW.`level`: = @level; - Form a gap in the tree UPDATE _ns_tree SET left_key = CASE WHEN left_key> = @left_key THEN left_key + 2 ELSE left_key + 0 END, right_key = right_key + 2 WHERE tree = NEW.tree AND right_key> = @left_key; END
Edit Record
The principle is the same with the use of the dialect.
SQL code (4)
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_upd_tr` BEFORE UPDATE ON` ns_tree` FOR EACH ROW BEGIN - We prohibit changing fields, or sending nasty things SET NEW.tree: = OLD.tree; SET NEW.right_key: = OLD.right_key; SET NEW.`level`: = OLD.`level`; SET @return_flag: = 0; IF NEW.parent_id IS NULL THEN SET NEW.parent_id: = 0; END IF; - Check if there are changes related to the structure of the tree IF NEW.parent_id <> OLD.parent_id OR NEW.left_key <> OLD.left_key THEN - We are rebuilding the tree, well, let's proceed: SET @left_key: = 0; SET @level: = 0; SET @skew_tree: = OLD.right_key - OLD.left_key + 1; - Determine where we are moving it: - If parent_id is changed: IF NEW.parent_id <> OLD.parent_id THEN - If in subjection to another evil: IF NEW.parent_id> 0 THEN SELECT right_key, level + 1 INTO @left_key, @level FROM ns_tree WHERE id = NEW.parent_id AND tree = NEW.tree; - Otherwise, we transfer to the root of the tree: ELSE SELECT MAX (right_key) + 1 INTO @left_key FROM ns_tree WHERE tree = NEW.tree; SET @level: = 0; END IF; - If suddenly the parent is in the range of the moved node, check: IF @left_key IS NOT NULL AND @left_key> 0 AND @left_key> OLD.left_key AND @left_key <= OLD.right_key THEN SET NEW.parent_id: = OLD.parent_id; SET NEW.left_key: = OLD.left_key; SET @return_flag: = 1; END IF; END IF; - If not parent_id, then left_key is changed, or if changing parent_id yields nothing IF @left_key IS NULL OR @left_key = 0 THEN SELECT id, left_key, right_key, `level`, parent_id INTO @tmp_id, @tmp_left_key, @tmp_right_key, @tmp_level, @tmp_parent_id FROM ns_tree WHERE tree = NEW.tree AND (right_key = NEW.left_key OR right_key = NEW.left_key - 1) LIMIT 1; IF @tmp_left_key IS NOT NULL AND @tmp_left_key> 0 AND NEW.left_key - 1 = @tmp_right_key THEN SET NEW.parent_id: = @tmp_parent_id; SET @left_key: = NEW.left_key; SET @level: = @tmp_level; ELSEIF @tmp_left_key IS NOT NULL AND @tmp_left_key> 0 AND NEW.left_key = @tmp_right_key THEN SET NEW.parent_id: = @tmp_id; SET @left_key: = NEW.left_key; SET @level: = @tmp_level + 1; ELSEIF NEW.left_key = 1 THEN SET NEW.parent_id: = 0; SET @left_key: = NEW.left_key; SET @level: = 0; ELSE SET NEW.parent_id: = OLD.parent_id; SET NEW.left_key: = OLD.left_key; SET @return_flag = 1; END IF; END IF; - Now we know where we are moving the tree - We check whether it is worth doing IF @return_flag IS NULL OR @return_flag = 0 THEN SET @skew_level: = @level - OLD.`level`; IF @left_key> OLD.left_key THEN - Move up the tree SET @skew_edit: = @left_key - OLD.left_key - @skew_tree; UPDATE _ns_tree SET left_key = CASE WHEN right_key <= OLD.right_key THEN left_key + @skew_edit ELSE CASE WHEN left_key> OLD.right_key THEN left_key - @skew_tree ELSE left_key End END, `level` = CASE WHEN right_key <= OLD.right_key THEN `level` + @skew_level ELSE `level` END, right_key = CASE WHEN right_key <= OLD.right_key THEN right_key + @skew_edit ELSE CASE WHEN right_key <@left_key THEN right_key - @skew_tree ELSE right_key End End WHERE tree = OLD.tree AND right_key> OLD.left_key AND left_key <@left_key AND id <> OLD.id; SET @left_key: = @left_key - @skew_tree; ELSE - Moving down the tree: SET @skew_edit: = @left_key - OLD.left_key; UPDATE _ns_tree SET right_key = CASE WHEN left_key> = OLD.left_key THEN right_key + @skew_edit ELSE CASE WHEN right_key <OLD.left_key THEN right_key + @skew_tree ELSE right_key End END, `level` = CASE WHEN left_key> = OLD.left_key THEN `level` + @skew_level ELSE `level` END, left_key = CASE WHEN left_key> = OLD.left_key THEN left_key + @skew_edit ELSE CASE WHEN left_key> = @left_key THEN left_key + @skew_tree ELSE left_key End End WHERE tree = OLD.tree AND right_key> = @left_key AND left_key <OLD.right_key AND id <> OLD.id; END IF; - The tree was rebuilt, only our current node remained SET NEW.left_key: = @left_key; SET NEW.`level`: = @level; SET NEW.right_key: = @left_key + @skew_tree - 1; END IF; END IF; END
ATTENTION!!! In MySQL, the order in which the fields are listed in the UPDATE query matters , since the fields that are changed during the query in the same query change the value to a new one, so if we use these fields further in the query under conditions, the result will be inadequate.
Delete record
Due to the lack of problems with trigger recursion, deleting generally becomes a trivial task.
Trigger for option: “delete the entire branch”:
SQL code (5)
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_del_tr` AFTER DELETE ON` ns_tree` FOR EACH ROW BEGIN - Delete the child nodes: DELETE FROM _ns_tree WHERE tree = OLD.tree AND left_key> OLD.left_key AND right_key <OLD.right_key; - We remove the gap in the keys: SET @skew_tree: = OLD.right_key - OLD.left_key + 1; UPDATE _ns_tree SET left_key = CASE WHEN left_key> OLD.left_key THEN left_key - @skew_tree ELSE left_key END, right_key = right_key - @skew_tree WHERE right_key> OLD.right_key AND tree = OLD.tree AND id <> OLD.id; END
Trigger for option: “deleting a node with moving child nodes upward”:
SQL code (6)
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_del_tr` AFTER DELETE ON` ns_tree` FOR EACH ROW BEGIN - We remove the gap in the keys: UPDATE _ns_tree SET left_key = CASE WHEN left_key <OLD.left_key THEN left_key ELSE CASE WHEN right_key <OLD.right_key THEN left_key - 1 ELSE left_key - 2 End END, parent_id = CASE WHEN right_key <OLD.right_key AND `level` = OLD.level + 1 THEN OLD.parent_id ELSE parent_id END, `level` = CASE WHEN right_key <OLD.right_key THEN `level` - 1 ELSE `level` END, right_key = CASE WHEN right_key <OLD.right_key THEN right_key - 1 ELSE right_key - 2 End WHERE (right_key> OLD.right_key OR (left_key> OLD.left_key AND right_key <OLD.right_key)) AND tree = OLD.tree; END
I want to draw attention to the fact that changes affecting the structure of the tree need not be made in batches, but sequentially for each node, so that its integrity is maintained.
Actually everything. It remains only to put down the indexes (again, I am lazy to write SQL commands here, so I’ll just voice them):
- Composite is not unique to fields ( left_key, right_key, level, tree );
- Not unique on the field ( parent_id );
Enjoy ;-)
Sergey Tomulevich aka Phoinix (07/08/2009)