Moving Subtrees in Closure Table Hierarchies

Hi Bill,

I’m actually currently researching how a closure tree will compare to a nested set tree for a reasonably sized tree, which led me to your blog post. You’re right about the solution being non-trivial, and your solution looks fairly similar to the one that you commented on here: http://jdobbie.blogspot.com/2009/07/closure-trees.html . While certainly not revolutionary, moving subtrees wasn’t mentioned in the paper, and I couldn’t find anyone who’d written code for it before me, so a link back would be greatly appreciated.

Thanks,
Jonathan Dobbie

Hi Bill,

I’m considering using a closure table to represent a hierarchical model allowing for multiple parents (say E as descendant of D as well as C in your last diagram).
There is however a problem I’ve hit which is moving or deleting a node that is present in two branches of the tree. As an example, let’s say we have a tree similar to the one in your last illustration, but with an extra E node below C: A-B, B-C, C-E, B-D, D-E, A-F (just the immediate connections), and we want to delete the node E descending from D (D-E). In this case we cannot delete the connections to all the other ancestors of E because those connections would still be valid for the node E descending from C. How can I implement a check to make sure we delete A-E, B-E, E-E if and only if they’re the last remaining links to E? Have you already worked on this problem?.

Thanks,
Ricardo Correa

Hi Bill,

I’m using the closure table hierarchy to store regions in a database using MySQL and I’m wondering how can I create a unordered list with indentation (for each level) with the datas. I know the level of each branch (with the length column) but they are different for each and can be more or less in the future. How can reordered the receive data correctly to do so ? I saw the article with the concatenate path of each entry but the order is not what I need to put it in html. With the tree traversal, it is easy to do so because you’re “walking the path”.

I’m using MySQL, PHP or Coldfusion (I have to do it in both languages so if you have any exemple in one of them) so maybe a query to reorder datas and then put it in an array or structure to loop over…

Thanks, Annie.

#RepeatString(”, currDepth-level)#

#regionName#

#RepeatString(”, currDepth-1)#

Thank you! Working pretty well now!

> It can be easier with the Adjacency List design,
> but in that design you don’t have a convenient way to query for all nodes of a tree

It is very easy using recursive queries which are supported by nearly all DBMS nowadays – MySQL and SQLite being the only ones not to.

Hi Bill,

I see you only defining the primary key over (ancestor, descendant). However, there are many accesses based on descendant. Since this table will also potentially be very long, don’t we create a KEY on descendant as well?

Bill,

Thank you for taking the time to write about this. The whole concept of a closure table and its implementation in MySQL is brilliant – it has saved me so much time and has allowed me to do things I would have otherwise not have been able to do.

Thanks so much!!

Tim,

are you aware that SQLite now also supports recursive queries?

http://sqlite.org/lang_with.html

Hans, your correct, problem is that even SQLite 3 on IOS 7 is at version 3.7 something. Not yet up to the 3.8.3 that supports recursion

Happy to report back that the two statements below work great on SQLite version 3.7.1:

DELETE FROM TreePaths
WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = ‘D’)
AND ancestor NOT IN (SELECT descendant FROM TreePaths WHERE ancestor = ‘D’);

INSERT INTO TreePaths (ancestor, descendant, length)
SELECT supertree.ancestor, subtree.descendant,
supertree.length+subtree.length+1
FROM TreePaths AS supertree JOIN TreePaths AS subtree
WHERE subtree.ancestor = ‘D’
AND supertree.descendant = ‘B’;

Hi Tim, none of the solutions for representing hierarchical data include any notion of sibling order by default.

Sorting by sibling order came up in this StackOverflow.com post I answered some time ago:
http://stackoverflow.com/questions/14069674/sorting-a-subtree-in-a-closure-table-hierarchical-data-structure/14074310#14074310

I took out the “ORDER BY breadcrumb.depth DESC” and getting the same result as in the posting:

Question: What is the implication of taking out this ORDER BY clause. Will it break something else in the future? Why doesn’t SQLite support this ORDER BY clause?

Result:

id | name | active | _parent | breadcrumbs |
+—-+————+——–+———+————-+
| 1 | Cat 1 | 1 | NULL | 1 |
| 3 | Cat 1.1 | 1 | 1 | 1,3 |
| 4 | Cat 1.1.1 | 1 | 3 | 1,3,4 |
| 7 | Cat 1.1.2 | 1 | 3 | 1,3,7 |
| 6 | Cat 1.2 | 1 | 1 | 1,6

—- Working SQLite version ————-

SELECT c2.*, cc2.ancestor AS _parent,
GROUP_CONCAT(breadcrumb.ancestor ) AS breadcrumbs
FROM category AS c1
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id)
JOIN category AS c2 ON (cc1.descendant = c2.id)
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1)
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant)
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1
GROUP BY cc1.descendant
ORDER BY breadcrumbs;

Thanks Bill for explanation. It makes perfect sense.

I would really love to use the recursive approach, only thing is that I’m using mobile and currently only SQLite 3.7 is supported. This means no recursion. Your solution would have been perfect if SQLite supported the GROUP_CONCAT(). Would it be possible possible to construct a query to work without recursion and a limited GROUP_CONCAT.

Hi,

Is it possible to move all child nodes to the other node? Not the node, but only its children.

##### FIND NAME IN YOUR TREE OF Users ############################

SELECT * FROM
users u
WHERE name LIKE ‘Bob’
AND FIND_IN_SET(23,u.hierarchy);

Emmanuel, standard SQL JOIN requires an “ON” clause for the join condition. MySQL has permissive syntax that allows the join condition to be optional, but PostgreSQL requires it.

If you want a cross join with no condition, you can use CROSS JOIN, which is supported by both MySQL and PostgreSQL.

See http://www.postgresql.org/docs/9.3/static/queries-table-expressions.html#QUERIES-FROM

I want to thank you for sharing us this one.

But to add, I was testing the detach node sub-tree query using what you have provided:

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 = ‘D’ AND x.ancestor IS NULL;

and it was giving me some unexpected results when I’m reattaching the sub-tree back. Some path are removed.
I was checking if there is a workaround on using the original query in MySQL:

DELETE FROM TreePaths
WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = ‘D’)
AND ancestor NOT IN (SELECT descendant FROM TreePaths WHERE ancestor = ‘D’);

The query above doesn’t work in MySQL but I’ve seen a workaround to do just exactly like that.
http://stackoverflow.com/questions/4471277/mysql-delete-from-with-subquery-as-condition (not the accepted answer though — but the one with the highest votes)

DELETE t FROM TreePaths t
WHERE id IN
(SELECT id FROM
(SELECT id FROM TreePaths
WHERE
descendant IN (
SELECT descendant
FROM closure_table
WHERE ancestor = ‘D’
) AND
ancestor NOT IN (
SELECT descendant
FROM TreePaths
WHERE ancestor = ‘D’
)) as group
);

That query above gives you the same result as the original query you intend to use. It detaches the sub-tree and preserves its structure.

I hope this helps.

Thanks again.

Hi ChristianB,

The way you store data doesn’t have performance — queries have performance. So it depends on what type of queries you want to run on the tree-oriented data. Do you want to fetch a whole tree starting from the root with all its descendants? If so, I’d suggest storing a document with nested object references. Do you want to fetch a lower node with its chain of ancestors? If so, I’d suggest storing the materialized path of ancestors.

Modeling data for MongoDB, like many other NoSQL databases, is more or less the same exercise as modeling denormalized data in an SQL database. You can store the data optimally for certain queries, but you have to identify which queries you want to run, and then decide how you can store the data to serve those queries most efficiently.

I wanted to better understand the portion of the sub-tree relocation where the ancestry is truncated into a stand-alone tree, so I tried to remake it as I understood it, and got this instead:

SELECT X.*
FROM toolbox.closure AS X #These will be entries with ancestors above THIS but descendants at/below THIS
INNER JOIN toolbox.closure AS A #These will be links in which THIS is the descendant
ON A.ancestor=X.ancestor
INNER JOIN toolbox.closure AS D #These will be links in which THIS is the ancestor
ON D.descendant=X.descendant
WHERE A.descendant=@this AND D.ancestor=@this AND X.ancestor != @this;

On my limited testing, on MySQL 5.6, it seems to get the same set. Will my query work correctly?

If so, other than the long WHERE clause, is there a disadvantage to what I came up with? I noticed that mine is dependent on range matching. Yours seems to have a very stable explain plan, whereas mine changes its plan a few times as I add more entries.

This is my setup:

DROP TABLE IF EXISTS toolbox.closure;
CREATE TABLE toolbox.closure (
ancestor INT UNSIGNED NOT NULL,
descendant INT UNSIGNED NOT NULL,
PRIMARY KEY (ancestor, descendant));

DROP TABLE IF EXISTS toolbox.thetable;
CREATE TABLE toolbox.thetable (
id INT UNSIGNED NOT NULL AUTO_INCREMENT,
PRIMARY KEY (id));

INSERT INTO toolbox.thetable VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9);

#Insert this tree
INSERT INTO toolbox.closure VALUES
(1,1), #1 is root of tree
(2,2), (1,2), #2 is child of 1
(3,3), (1,3),(2,3), #3 is child of 2
(4,4), (1,4),(2,4),(3,4), #4 is child of 3
(5,5), (1,5),(2,5),(3,5),(4,5), #5 is child of 4
(6,6), (1,6),(2,6),(3,6), #6 is child of 3
(7,7), (1,7),(2,7),(3,7),(6,7), #7 is child of 6
(8,8), (8,2),(8,1), #8 is a child of 2
(9,9), (9,8),(9,2),(9,1) #9 is a child of 8
;

#Lets make more
INSERT INTO toolbox.thetable SELECT id+10 FROM toolbox.thetable;
INSERT INTO toolbox.thetable SELECT id+20 FROM toolbox.thetable;
INSERT INTO toolbox.thetable SELECT id+40 FROM toolbox.thetable;
INSERT INTO toolbox.thetable SELECT id+80 FROM toolbox.thetable;
INSERT INTO toolbox.closure SELECT ancestor+10, descendant+10 FROM toolbox.closure;
INSERT INTO toolbox.closure SELECT ancestor+20, descendant+20 FROM toolbox.closure;
INSERT INTO toolbox.closure SELECT ancestor+40, descendant+40 FROM toolbox.closure;
INSERT INTO toolbox.closure SELECT ancestor+80, descendant+80 FROM toolbox.closure;

SET @this=3;
#Get the hunk of links to remove if making branch into a new tree at 3
SELECT X.*
FROM toolbox.closure AS X #These are entries with ancestors above THIS but descendants at/below THIS
INNER JOIN toolbox.closure AS A #These will be links in which THIS is the descendant
ON A.ancestor=X.ancestor
INNER JOIN toolbox.closure AS D #These will be links in which THIS is the ancestor
ON D.descendant=X.descendant
WHERE A.descendant=@this AND D.ancestor=@this AND X.ancestor != @this;

Hello, has anyone seen the closure table concept implemented using JPA / Hibernate? I am relatively new to Hibernate, but its a requirement for the project I am working on.

Those who write: “Wow, this is cool …” Did you really read article???
What is the relationship of the C-D or C-E, it’s funny.

To answer my own question … 🙂 I found a workable start (for DB2) here http://flylib.com/books/en/4.64.1.23/1/

WITH CT (parentId, childId, depth, name) AS (
SELECT ROOT.parentId, ROOT.id, 0, ROOT.name
FROM Organization ROOT
WHERE ROOT.parentId is NULL

UNION ALL

SELECT CHILD.parentId, CHILD.id, PARENT.depth+1 as depth, CHILD.name
FROM CT PARENT, Organization CHILD
WHERE PARENT.childId = CHILD.parentId
) SELECT DISTINCT parentId, childId, depth, name
FROM CT
ORDER BY depth, parentId, childId;