Update nested sets when changing parent or deleting

Question

I have the following table structure, which is also on sqlfiddle for convenience:

+---------+-----------+---------+----------+-----------+-------------------+-----------------------------------+--------+--------------+-------------+---------------+-----------+
| rule_id | parent_id | left_id | right_id | rule_type | rule_title        | rule_description                  | public | parse_bbcode | parse_links | parse_smilies | group_ids |
+---------+-----------+---------+----------+-----------+-------------------+-----------------------------------+--------+--------------+-------------+---------------+-----------+
|       1 |         0 |       1 |        6 | cat       | Sample Category 1 |                                   |      1 |            0 |           0 |             0 | 1 2 7     |
|       2 |         1 |       2 |        3 | rule      | Sample Rule 1     | This is a sample rule description |      1 |            1 |           1 |             1 | 1 2 7     |
|       3 |         0 |       7 |        8 | cat       | Sample category 2 |                                   |      1 |            0 |           0 |             0 | 1 7 2     |
|       4 |         0 |       9 |       10 | cat       | Sample category 3 |                                   |      1 |            0 |           0 |             0 | 1 7 2     |
|       5 |         1 |       4 |        5 | rule      | Sample rule 3     | lol                               |      1 |            1 |           1 |             1 | 1 2 7     |
+---------+-----------+---------+----------+-----------+-------------------+-----------------------------------+--------+--------------+-------------+---------------+-----------+

As you see, rule_type can be either 'cat' or 'rule'.

cat stands for category, and categories are root nodes: so parent_id is always 0. In my code, we can identify categories by checking either if rule_type = 'cat' or parent_id = 0.

You can also see that I am using nested sets for my project and this is where the problem stands.

I have successfully created functions that:

• move rules & categories up or down; and

• put a new rule or category in the end of their respective place.

BUT I am failing to set the RULES' right_id & left_id if we change its parent_id! I'm also failing to set right_id & left_id if we delete a rule OR category.

Example

I'll try to explain with an example. Note that this is just an example, not the actual case and I need a general answer.

From the table above, we see that we have 3 categories with rule_id IN (1, 3, 4) and two rules with rule_id IN (2, 5).

The rule with rule_id = 2 is part of the category with rule_id = 1, we can see that from the parent_id column. What if I change the parent_id to 4? How would the right_id & left_id get set so everything is in place again? I know we need to update both rule_id IN (1, 4) to reorder everything, but I don't know how my query would look like.

Same goes for deleting... For example I delete rule_id = 2 (which is a rule), how would I set right_id & left_id for parent_id = 1 in the correct order? Or when I delete a category? How would I reorder the categories?

I didn't really try doing anything here, as I have no vision how I would do such a thing, therefore I'm asking for your help, folks.

I hope I made myself clear. If not, let me know and I'll try to be even more descriptive.

Wraith

This may help: mikehillyer.com/articles/managing-hierarchical-data-in-mysql – Figurant

@Figurant Thanks, but it doesn't suffice. – Wraith

Just out of curiosity why are you trying to do this with one table instead of two tables like rules and rule_categories? – Bethel

Answer 1

I assume you have successfully set up the PDO connection.

Also, be aware the following examples only work if all the categories are root nodes (like in the subject). It's not a problem to change this code to work with nested categories.

Deleting a rule

1. Retrieve its right_id and left_id value.

2. Delete row from the database.

3. Update the table set right_id - 2 where right_id greater then the right_id of deleting rule.

4. Same for left_id

Example:

    $ruleIdForDel = 2;
    $leftId = 2;
    $rightId = 3;

    $pdo->beginTransaction();
    try {
        $pdo->exec("DELETE FROM rules WHERE rule_id = $ruleIdForDel");
        $pdo->exec("UPDATE rules
                    SET left_id = CASE
                            WHEN left_id > $leftId THEN left_id - 2
                            ELSE left_id
                        END,
                        right_id = CASE
                            WHEN right_id > $rightId THEN right_id - 2
                            ELSE right_id
                        END");
        $pdo->commit();
    } catch (Exception $e) {
        $pdo->rollBack();
        throw $e;
    }

Updating rule's parent_id

Suppose we are going to move node to the last position of new parent

1. Retrieve updating rule's left_id and right_id ($ruleLeftId and $ruleRightId)

2. Retrieve new parent rule's left_id and right_id ($newParentRuleLeftId and $newParentRuleRightId)

3. Check wether a node moving up or down the tree and depending on it generate new left_id and right_id values for the updating rule ($ruleNewLeftId and $ruleNewRightId)

4. Update rules left_id and right_id depending on the updating rule's destination

5. Update parent_id, left_id, right_id of the updating rule

If the updating rule's right_key less then new parent rule's right_id then the rule moves down the tree, otherwise it moves up the tree.

If the rule moves down the tree we are going to shift left_id value by minus 2 on the rules located between the updating rule's left_id ($ruleLeftId) and new left_id ($ruleNewLeftId) + 1. Otherwise, shift left_id value by 2 on the rules located between new left_id ($ruleNewLeftId) and initial left_id ($ruleLeftId).

Same for right_id.

Example:

    // Updating rule
    $ruleId = 2;
    $ruleLeftId = 2;
    $ruleRightId = 3;

    // New parent rule
    $newParentRuleId = 3;
    $newParentRuleLeftId = 7;
    $newParentRuleRightId = 8;


    // Generate new rule's left and right keys
    // Moves up
    if ($newParentRuleRightId < $ruleRightId) {
        $ruleNewLeftId = $newParentRuleRightId;
        $ruleNewRightId = $newParentRuleRightId + 1;
    // Moves down
    } else {
        $ruleNewLeftId = $newParentRuleRightId - 2; // 6
        $ruleNewRightId = $newParentRuleRightId - 1; // 7
    }

    $pdo->beginTransaction();
    try {
        $pdo->exec("UPDATE rules
                            SET left_id = CASE
                                /* Moves down */
                                WHEN $ruleNewRightId > $ruleRightId AND
                                     left_id > $ruleLeftId AND
                                     left_id <= $ruleNewLeftId + 1 THEN left_id - 2
                                /* Moves up */
                                WHEN $ruleNewRightId < $ruleRightId AND
                                     left_id >= $ruleNewLeftId AND
                                     left_id < $ruleLeftId THEN left_id + 2
                                ELSE left_id
                            END,
                            right_id = CASE
                                WHEN $ruleNewRightId > $ruleRightId AND
                                     right_id > $ruleRightId AND
                                     right_id <= $ruleNewRightId THEN right_id - 2
                                WHEN $ruleNewRightId < $ruleRightId AND
                                     right_id >= $ruleNewLeftId AND
                                     right_id <= $ruleRightId THEN right_id + 2
                                ELSE right_id
                            END");
        $pdo->exec("UPDATE rules
                    SET parent_id = $newParentRuleId,
                        left_id = $ruleNewLeftId,
                        right_id = $ruleNewRightId
                    WHERE rule_id = $ruleId");
        $pdo->commit();
    } catch (Exception $e) {
        $pdo->rollBack();
        throw $e;
    }

I didnt use any PDO::Statement just to save space.

I have not tested it properly so post an issue if you find some.

Reichard

Thank you. I only had to read through your description, that was the only part I was unable to do, the logic behind deleting and updating. – Wraith

Answer 2

The rule with rule_id = 2 is part of the category with rule_id = 1, we can see that from the parent_id column. What if I change the parent_id to 4? How would the right_id & left_id get set so everything is in place again? I know we need to update both rule_id IN (1, 4) to reorder everything, but I don't know how my query would look like.

Try something like this, i haven't tested it yet, but it might get you on the right track

UPDATE table SET parent_id = 4, 
                 right_id = (CASE WHEN parent_id = 4 THEN 1 END), 
                 left_id = (CASE WHEN parent_id = 4 THEN 2 END)

Inhospitality

Nope that did not get me in the right track at all. Also note what I said in the first post: "I'll try to explain with an example. Note that this is just an example, not the actual case and I need a general answer.". Thanks anyway. – Wraith