July 8, 2009 at 15:33Nested 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)