Skip to content

Instantly share code, notes, and snippets.

@kentoj
Forked from emmanuel/file.sql
Last active December 31, 2021 07:12
Show Gist options
  • Save kentoj/872cbefc68f68a2a97b6189da9cd6e23 to your computer and use it in GitHub Desktop.
Save kentoj/872cbefc68f68a2a97b6189da9cd6e23 to your computer and use it in GitHub Desktop.
Closure Table operations SQL fragments
-- 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;
@andrewsuzuki
Copy link

Good work! Thanks for this

@andrewsuzuki
Copy link

Line 27 should be SELECT 8, 8, 0;, otherwise Postgres throws the error each UNION query must have the same number of columns.

@SharmaTushar
Copy link

Can you elaborate what does reparent #6 from #4 -> #3 mean?

@toxyy
Copy link

toxyy commented Jun 24, 2018

@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.

@vparaskevas
Copy link

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"

@djoyrocks
Copy link

Hi How to get all the root nodes ?
A
B
C
D
E
F

Result: A, D, E

@chibyk101
Copy link

chibyk101 commented Apr 18, 2021

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment