Skip to content

Instantly share code, notes, and snippets.

@martic

martic/closure-table-operations.sql

Forked from kentoj/closure-table-operations.sql
Created January 13, 2020 04:53
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save martic/a6f5eb5b6f855f4315327e1b613b2ee5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save martic/a6f5eb5b6f855f4315327e1b613b2ee5 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @kentoj kentoj renamed this gist Dec 16, 2017. 1 changed file with 0 additions and 0 deletions.
    0 file.sql → closure-table-operations.sql
    View file
    File renamed without changes.
  2. @kentoj kentoj revised this gist Dec 16, 2017. 1 changed file with 38 additions and 46 deletions.
    84 changes: 38 additions & 46 deletions file.sql
    View file
    Original file line number Diff line number Diff line change
    @@ -1,82 +1,74 @@
    -- 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;
    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;
    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;

    INSERT INTO TreePaths (ancestor, descendant)
    SELECT t.ancestor, 8
    FROM TreePaths AS t
    WHERE t.descendant = 5
    UNION ALL
    SELECT 8, 8;

    -- I believe this is the same as above, with path_length
    -- 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, 0;

    -- 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);
    WHERE descendant IN (SELECT descendant
    FROM TreePaths
    WHERE ancestor = 4);

    -- Move Subtree

    -- Move Subtree (2 steps)
    -- ============
    --
    -- reparent #6 from #4 -> #3
    --
    -- Step 1: Disconnect from current ancestors
    -- -----------------------------------------
    --
    -- delete all paths that end at descendants in the subtree
    -- or that begin with

    -- 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)
    FROM TreePaths
    WHERE ancestor = 6)
    AND ancestor IN (SELECT ancestor
    FROM TreePaths
    WHERE descendant = 6
    AND ancestor != descendant);
    FROM TreePaths
    WHERE descendant = 6
    AND ancestor != descendant);

    -- Step 2: Insert rows matching ancestors of insertion point and descendants of subtree
    -- ------------------------------------------------------------------------------------
    -- TODO: how to calculate the path length of the new row in this query?

    INSERT INTO TreePaths (ancestor, descendant)
    SELECT supertree.ancestor, subtree.descendant
    FROM TreePaths AS supertree
    CROSS JOIN TreePaths AS subtree
    WHERE supertree.descendant = 3
    AND subtree.ancestor = 6;
    -- 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;
  3. @emmanuel emmanuel revised this gist Jun 20, 2011. No changes.
  4. @emmanuel emmanuel revised this gist Jun 2, 2011. 1 changed file with 13 additions and 4 deletions.
    17 changes: 13 additions & 4 deletions file.sql
    View file
    Original file line number Diff line number Diff line change
    @@ -27,6 +27,14 @@ INSERT INTO TreePaths (ancestor, descendant)
    UNION ALL
    SELECT 8, 8;

    -- I believe this is the same as above, with path_length
    -- 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, 0;

    -- Delete Leaf node
    -- ================
    -- delete leaf node #7
    @@ -44,14 +52,14 @@ WHERE descendant IN (SELECT descendant

    -- Move Subtree
    -- ============
    --
    --
    -- reparent #6 from #4 -> #3
    --
    --
    -- Step 1: Disconnect from current ancestors
    -- -----------------------------------------
    --
    --
    -- delete all paths that end at descendants in the subtree
    -- or that begin with
    -- or that begin with

    DELETE FROM TreePaths
    WHERE descendant IN (SELECT descendant
    @@ -64,6 +72,7 @@ WHERE descendant IN (SELECT descendant

    -- Step 2: Insert rows matching ancestors of insertion point and descendants of subtree
    -- ------------------------------------------------------------------------------------
    -- TODO: how to calculate the path length of the new row in this query?

    INSERT INTO TreePaths (ancestor, descendant)
    SELECT supertree.ancestor, subtree.descendant
  5. @emmanuel emmanuel created this gist Jun 2, 2011.
    73 changes: 73 additions & 0 deletions file.sql
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,73 @@
    -- 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)
    SELECT t.ancestor, 8
    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
    -- ============
    --
    -- reparent #6 from #4 -> #3
    --
    -- Step 1: Disconnect from current ancestors
    -- -----------------------------------------
    --
    -- delete all paths that end at descendants in the subtree
    -- or that begin with

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

    INSERT INTO TreePaths (ancestor, descendant)
    SELECT supertree.ancestor, subtree.descendant
    FROM TreePaths AS supertree
    CROSS JOIN TreePaths AS subtree
    WHERE supertree.descendant = 3
    AND subtree.ancestor = 6;