16

I have a MySQL database holding hierarchical data using the Closure Table method. A simple sample database create script follows the question. My issue at the moment is how do I pull data out of the database in the correct order? I'm currently using the following select statement.

SELECT `TreeData`.`iD`, `TreeData`.`subsectionOf`,
       CONCAT(REPEAT('-', `TreePaths`.`len`),`TreeData`.`name`),
       `TreePaths`.`len`,`TreePaths`.`ancestor`,`TreePaths`.`descendant`
FROM `TreeData`
LEFT JOIN `TreePaths` ON `TreeData`.`iD` = `TreePaths`.`descendant`
WHERE `TreePaths`.`ancestor` = 1
ORDER BY `TreeData`.`subsectionOrder`

It pulls the correct information but not in the correct order.

The sample database create script with sample data.

-- Simple Sample
SET FOREIGN_KEY_CHECKS=0;
DROP TRIGGER IF EXISTS Tree_Insert;
DROP TRIGGER IF EXISTS Tree_Update;
DROP TABLE IF EXISTS TreePaths;
DROP TABLE IF EXISTS TreeData;
SET FOREIGN_KEY_CHECKS=1;


CREATE TABLE `TreeData` (
    `iD`              INT NOT NULL,             -- PK
    `subsectionOf`    INT,                      -- Parent ID & FK
    `subsectionOrder` INT,                      -- Oder of Subsections 
    `name`            NVARCHAR(500) NOT NULL,   -- Name for the entry
    PRIMARY KEY (`iD`),
    FOREIGN KEY (`subsectionOf`) REFERENCES TreeData(`iD`) ON DELETE CASCADE,
    INDEX(`name`)
) ENGINE = MYISAM;

-- Trigger to update the EntryPaths table for new entries
DELIMITER //
CREATE TRIGGER `Tree_Insert` AFTER INSERT ON `TreeData` FOR EACH ROW 
BEGIN
    INSERT INTO `TreePaths` (`ancestor`, `descendant`, `len`)
        SELECT `ancestor`, NEW.`iD`, len + 1 FROM `TreePaths`
            WHERE `descendant` = NEW.`subsectionOf`
            UNION ALL SELECT NEW.`iD`, NEW.`iD`, 0;
END; //
DELIMITER ;


DELIMITER //
CREATE TRIGGER `Tree_Update` BEFORE UPDATE ON `TreeData` FOR EACH ROW 
BEGIN
    -- From http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/
    IF OLD.`subsectionOf` != NEW.`subsectionOf` THEN
        -- Remove the node from its current parent
        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` = OLD.`iD` AND x.`ancestor` IS NULL;

        -- Add the node to its new parent
        INSERT `TreePaths` (`ancestor`, `descendant`, `len`)
        SELECT supertree.`ancestor`, subtree.`descendant`, supertree.`len`+subtree.`len`+1
        FROM `TreePaths` AS supertree JOIN `TreePaths` AS subtree
        WHERE subtree.`ancestor` = OLD.`iD`
        AND supertree.`descendant` = NEW.`subsectionOf`;
    END IF;
END; //
DELIMITER ;


CREATE TABLE `TreePaths` (
    `ancestor`      INT NOT NULL,
    `descendant`    INT NOT NULL,
    `len`           INT NOT NULL,
    PRIMARY KEY (`ancestor`, `descendant`),
    FOREIGN KEY (`ancestor`) REFERENCES TreeData(`iD`) ON DELETE CASCADE,
    FOREIGN KEY (`descendant`) REFERENCES TreeData(`iD`) ON DELETE CASCADE
) ENGINE = MYISAM;

INSERT INTO `TreeData` VALUES(1, NULL, NULL, 'Root A');
INSERT INTO `TreeData` VALUES(2, 1, 1, 'Item 1');
INSERT INTO `TreeData` VALUES(3, 1, 2, 'Item 2');
INSERT INTO `TreeData` VALUES(4, 1, 3, 'Item 3');
INSERT INTO `TreeData` VALUES(5, 2, 2, 'Item 1 Sub Item 2');
INSERT INTO `TreeData` VALUES(6, 2, 1, 'Item 1 Sub Item 1');
INSERT INTO `TreeData` VALUES(7, 1, 3, 'Item 4');
INSERT INTO `TreeData` VALUES(8, 4, 1, 'Item 3 Sub Item 1');
INSERT INTO `TreeData` VALUES(9, 4, 2, 'Item 3 Sub Item 2');
INSERT INTO `TreeData` VALUES(10, NULL, NULL, 'Root B');
INSERT INTO `TreeData` VALUES(11, 10, 1, 'Item A');
INSERT INTO `TreeData` VALUES(12, 10, 2, 'Item B');
INSERT INTO `TreeData` VALUES(13, 10, 3, 'Item C');
Justin808
  • 20,859
  • 46
  • 160
  • 265

1 Answers1

21
SELECT d.`iD`, d.`subsectionOf`,
       CONCAT(REPEAT('-', p.`len`), d.`name`) as hier,
       p.`len`, p.`ancestor`, p.`descendant`,
       GROUP_CONCAT(crumbs.`ancestor`) AS breadcrumbs
FROM `TreeData` AS d
JOIN `TreePaths` AS p ON d.`iD` = p.`descendant`
JOIN `TreePaths` AS crumbs ON crumbs.`descendant` = p.`descendant`
WHERE p.`ancestor` = 1
GROUP BY d.`iD`
ORDER BY breadcrumbs;

+----+--------------+---------------------+-----+----------+------------+-------------+
| iD | subsectionOf | hier                | len | ancestor | descendant | breadcrumbs |
+----+--------------+---------------------+-----+----------+------------+-------------+
|  1 |         NULL | Root A              |   0 |        1 |          1 | 1           | 
|  2 |            1 | -Item 1             |   1 |        1 |          2 | 1,2         | 
|  5 |            2 | --Item 1 Sub Item 2 |   2 |        1 |          5 | 1,2,5       | 
|  6 |            2 | --Item 1 Sub Item 1 |   2 |        1 |          6 | 1,2,6       | 
|  3 |            1 | -Item 2             |   1 |        1 |          3 | 1,3         | 
|  4 |            1 | -Item 3             |   1 |        1 |          4 | 1,4         | 
|  8 |            4 | --Item 3 Sub Item 1 |   2 |        1 |          8 | 1,4,8       | 
|  9 |            4 | --Item 3 Sub Item 2 |   2 |        1 |          9 | 1,4,9       | 
|  7 |            1 | -Item 4             |   1 |        1 |          7 | 1,7         | 
+----+--------------+---------------------+-----+----------+------------+-------------+
Bill Karwin
  • 538,548
  • 86
  • 673
  • 828
  • 4
    This only works if your tree was created sequentially. Imagine your root item wasn't 1, it was 12, this would no longer work. Move a couple nodes around here to remove the sequence and this printing will break. Anybody have another solution? –  Dec 03 '11 at 04:43
  • 1
    If your closure table also includes a `pathlength` column you can use `GROUP_CONCAT(crumbs.ancestor ORDER BY pathlength)`. – Bill Karwin Dec 03 '11 at 09:20
  • 1
    @Thomas GROUP_CONCAT(DISTINCT crumbs.`ancestor` ORDER BY crumbs.`ancestor`) will do the job, also – kukipei Feb 19 '12 at 18:07
  • I can't understand why, but I had to `ORDER BY pathlength DESC` in order to have the breadcrumbs to be in the correct order (that is to begin with ancestor's ID). – Lebugg Mar 25 '14 at 10:16
  • I got this to work, but how do I achieve this if i have multiple root items (Root A, Root B, Root C, ...) and I want the full tree starting with the root items. The root items have subsectionOf to NULL – Frederik Heyninck May 15 '15 at 20:00
  • I forgot, how can I take subsectionOrder order in to account? – Frederik Heyninck May 15 '15 at 21:14
  • @FrederikHeyninck, get multiple trees with `WHERE p.ancestor IN (1,24,92)` that is for each root node. For ordering by an explicit subsectionOrder instead of by node id, use the subsectionOrder as you produce the breadcrumbs string. – Bill Karwin May 15 '15 at 21:25
  • @BillKarwin Thanks, the multiple trees are working, but still cant figure out the sorting. For each branch so parents and children are sorting based on there own branch sequence. – Frederik Heyninck May 16 '15 at 06:25
  • In this gist you can see it is sorting based on the id and not sequence: https://gist.github.com/freshface/07490f45ff58766de64a It should be - Parent A --- first child of A --- second child of A - Parent B – Frederik Heyninck May 16 '15 at 06:40
  • @FrederikHeyninck, my guess is to use `GROUP_CONCAT(crumbs.sequence ORDER BY crumbs.length DESC) as breadcrumbs`. – Bill Karwin May 16 '15 at 07:13
  • @BillKarwin Thanks for the reply, your solution states that I should add a sequence field in the shop_categories_treepaths table? Now the parent table shop_categories has the sequence. – Frederik Heyninck May 16 '15 at 11:25
  • @FrederikHeyninck, then you'll have to join `crumbs` to another instance of `shop_categories` to get the sequence. – Bill Karwin May 16 '15 at 15:51
  • @BillKarwin, I'm hoping you might have an answer for this. I read your blog posts about closure tables. I'm using a similar structure, but I want to return the query in an order that is analogous to converting a general tree to a binary tree - similar to what is described here: http://faculty.salina.k-state.edu/tmertz/Java/328trees/convertinganonbinarytreetobinaryform.pdf Any thoughts on this? – OldTimeGuitarGuy Jan 24 '18 at 22:09
  • @OldTimeGuitarGuy, Typically trees in SQL tables are stored with the child referencing the parent, not the other way around. So you have no downside to N-ary trees as described in that article. Anyway, I'm not going to attempt to write a closure table query to implement that algorithm in a comment. Please ask a new question. – Bill Karwin Jan 24 '18 at 22:36