-
-
Save kentoj/872cbefc68f68a2a97b6189da9cd6e23 to your computer and use it in GitHub Desktop.
| -- Retrieve descendants | |
| -- ==================== | |
| -- retrieve descendants of #4 | |
| SELECT c.* | |
| FROM Comments AS c | |
| JOIN TreePaths AS t ON c.comment_id = t.descendant | |
| WHERE t.ancestor = 4; | |
| -- Retrieve ancestors | |
| -- ================== | |
| -- retrieve ancestors of #6 | |
| SELECT c.* | |
| FROM Comments AS c | |
| JOIN TreePaths AS t ON c.comment_id = t.ancestor | |
| WHERE t.descendant = 6; | |
| -- Insert Leaf node | |
| -- ================ | |
| -- insert leaf node #8 as a child of #5 | |
| INSERT INTO TreePaths (ancestor, descendant, path_length) | |
| SELECT t.ancestor, 8, t.path_length + 1 | |
| FROM TreePaths AS t | |
| WHERE t.descendant = 5 | |
| UNION ALL | |
| SELECT 8, 8; | |
| -- Delete Leaf node | |
| -- ================ | |
| -- delete leaf node #7 | |
| DELETE FROM TreePaths WHERE descendant = 7; | |
| -- Delete Subtree | |
| -- ============== | |
| -- delete #4 and all children from the tree | |
| DELETE FROM TreePaths | |
| WHERE descendant IN (SELECT descendant | |
| FROM TreePaths | |
| WHERE ancestor = 4); | |
| -- Move Subtree (2 steps) | |
| -- ============ | |
| -- reparent #6 from #4 -> #3 | |
| -- | |
| -- Step 1: Disconnect from current ancestors | |
| -- ----------------------------------------- | |
| -- delete all paths that end at descendants in the current node's subtree | |
| -- and that begin at ancestors of the current node (6). | |
| DELETE FROM TreePaths | |
| WHERE descendant IN (SELECT descendant | |
| FROM TreePaths | |
| WHERE ancestor = 6) | |
| AND ancestor IN (SELECT ancestor | |
| FROM TreePaths | |
| WHERE descendant = 6 | |
| AND ancestor != descendant); | |
| -- Step 2: Insert rows matching ancestors of insertion point and descendants of subtree | |
| -- ------------------------------------------------------------------------------------ | |
| -- This uses CROSS JOIN to get the cross product of the new parent's ancestors, including the new parent, | |
| -- with the subtree's nodes. This is one case where the full cartesian product is useful. | |
| INSERT INTO TreePaths (ancestor, descendant, path_length) | |
| SELECT | |
| supertree.ancestor, | |
| subtree.descendant, | |
| supertree.path_length + subtree.path_length + 1 AS path_length | |
| FROM TreePaths AS supertree | |
| CROSS JOIN TreePaths AS subtree | |
| WHERE supertree.descendant = 3 | |
| AND subtree.ancestor = 6; |
Line 27 should be SELECT 8, 8, 0;, otherwise Postgres throws the error each UNION query must have the same number of columns.
Can you elaborate what does reparent #6 from #4 -> #3 mean?
@SharmaTushar Consider the tree
post1
-post2
--post3
-post4
post5
if we want to change post4's parent from post1 to post5, the move subtree code will do so,
#4 from #1 -> #5
in his notation.
The tree after we do so:
post1
-post2
--post3
post5
-post4
On a side note for insertion, andrewsuzuki's fix applies to MySQL as well.
I had to change the insert leaf node query for MySQL up a bit as it would not run as written. Fixed version:
INSERT INTO TreePaths (ancestor, descendant, path_length)
SELECT * FROM (SELECT t.ancestor, 8, t.path_length + 1
FROM TreePaths AS t
WHERE t.descendant = 5
UNION ALL
SELECT 8, 8, 0) as tmp
Thank you @kentoj for these! A real life saver, especially if you can't use stored procedures or triggers.
The delete part of reparenting should be like the following:
DELETE a FROM TreePaths AS a
JOIN TreePaths AS d ON a.descendant = d.descendant
LEFT JOIN TreePaths AS x
ON x.ancestor = d.ancestor AND x.descendant = a.ancestor
WHERE d.ancestor = 6 AND x.ancestor IS NULL;
Otherwise we get an error at MySQL "You can’t specify target table ‘TreePaths’ for update in FROM clause"
Hi How to get all the root nodes ?
A
B
C
D
E
F
Result: A, D, E
how is the 1st root node inserted?
lets say the very 1st comment which doesn't have a parent comment or ancestor, what's the initial depth?
how is the 1st root node inserted? lets say the very 1st comment which doesn't have a parent comment or ancestor, what's the initial depth?
The depth is 0. It's the entry where ancestor = descendant. You can postpone the insertion to the TreePaths table to when it will be assigned to a node, since the query (line 22-27) guarantees the self-referential insertion.
Good work! Thanks for this