Figuring out closure tables.Using a billion blogs, slideshares and implementations that are half complete, or in languages I don't understand.

001_explanation.rst

Closure tables, how the hell do they work?

Attempting to combine piece-meal examples of closure tables into a concrete demonstration.

Bits taken from Rendering Trees with Closure Tables, Closure Table part deux – Nodes and Adjacencies – A tree in MySQL, The simplest(?) way to do tree-based queries in SQL, Moving Subtrees in Closure Table Hierarchies, What is the most efficient/elegant way to parse a flat table into a tree? and Models for hierarchical data and a bunch of others I'll document as I re-find them.

data.sql

TRUNCATE TABLE `nodes`;
TRUNCATE TABLE `adjacencies`;
BEGIN;

INSERT INTO `nodes` (`title`) VALUES ('Node A');
INSERT INTO `nodes` (`title`) VALUES ('Node B');
INSERT INTO `nodes` (`title`) VALUES ('Node C');
INSERT INTO `nodes` (`title`) VALUES ('Node D');
INSERT INTO `nodes` (`title`) VALUES ('Node E');
INSERT INTO `nodes` (`title`) VALUES ('Node F');
INSERT INTO `nodes` (`title`) VALUES ('Node G');

INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 1, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (2, 2, 0);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (1, 2, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 2, 2);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (3, 3, 0);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 3, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (4, 4, 0);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (2, 4, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (1, 4, 2);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 4, 3);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (5, 5, 0);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (3, 5, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 5, 2);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (6, 6, 0);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (1, 6, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 6, 2);      
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (7, 7, 0);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (1, 7, 1);
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (NULL, 7, 2);

COMMIT;

database_structure_mysql.sql

-- the database itself, if you need one.
-- CREATE DATABASE `closure_test` DEFAULT CHARACTER SET `utf8`;

BEGIN;
-- simplified Node items.
-- These are the actual things we want to 'see'
-- If you're playing along at home, this is the table you should be
-- able to change to match the data you want/need to store. As long
-- as you keep the `id` field in play, the rest should work, though
-- any INSERTs into `nodes` will need to be modified appropriately.
DROP TABLE IF EXISTS `nodes`;
CREATE TABLE `nodes` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `title` varchar(255) NOT NULL,
    PRIMARY KEY (`id`)
) CHARSET=utf8;
 
-- This is the adjacency list table, which is a Many to Many of nodes.
-- It shouldn't need to be touched, as it is a self-contained adjacency list.
DROP TABLE IF EXISTS `adjacencies`;
CREATE TABLE `adjacencies` (
    `id` integer NOT NULL PRIMARY KEY AUTO_INCREMENT,
    `ancestor_id` integer REFERENCES `nodes` (`id`),
    `descendant_id` integer NOT NULL REFERENCES `nodes` (`id`),
    `lvl` integer unsigned NOT NULL,
    UNIQUE (`ancestor_id`, `descendant_id`)
) CHARSET=utf8;

-- recommended indexes for the many to many table.
CREATE INDEX `adjacencies_parent` ON `adjacencies` (`ancestor_id`);
CREATE INDEX `adjacencies_child` ON `adjacencies` (`descendant_id`);
CREATE INDEX `adjacencies_depth` ON `adjacencies` (`lvl`);

COMMIT;

queries.sql

-- Query to show, in an SQL resultset, what the tree should look like.
-- Shouldn't be treated as something to use in a live environment, I don't think
-- especially if you're trying to wedge this into an ORM.
-- Note: This doesn't correctly handle NULL ancestors, so needs work.
SELECT `n`.`id`,
       CONCAT(REPEAT('-', `ance`.`lvl`), `n`.`title`) AS hier,
       `ance`.`lvl`,
       `ance`.`ancestor_id`,
       `ance`.`descendant_id`,
       GROUP_CONCAT(`crumbs`.`ancestor_id`) AS `breadcrumbs`
FROM `nodes` AS `n`
JOIN `adjacencies` AS `ance` ON `n`.`id` = `ance`.`descendant_id`
JOIN `adjacencies` AS `crumbs` ON `crumbs`.`descendant_id` = `ance`.`descendant_id`
WHERE `ance`.`ancestor_id` = 1
GROUP BY `n`.`id`
ORDER BY breadcrumbs ;

-- get descendants of a node, including itself.
-- In this example, find all children of "Node A."
SELECT n.*
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `ance`.`descendant_id` = `n`.`id`
WHERE `ance`.`ancestor_id` = 1 ;

-- get descendants of a node, excluding itself.
-- In this example, find all children of "Node A."
SELECT n.*
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `ance`.`descendant_id` = `n`.`id`
WHERE `ance`.`ancestor_id` = 1
    AND NOT `ance`.`descendant_id` = 1 ;

-- get ancestors of a node, including itself.
-- In this example, find all ancestors of "Node G."SELECT `n`.*
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `n`.`id` = `ance`.`ancestor_id`
WHERE `ance`.`descendant_id` = 7 ;


-- get ancestors of a node, excluding itself
-- In this example, find all ancestors of "Node G."
SELECT `n`.*
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `n`.`id` = `ance`.`ancestor_id`
WHERE `ance`.`descendant_id` = 7
    AND NOT `ance`.`ancestor_id` = 7 ;

-- this might do nodes to delete? not really sure yet.
-- In this example, everything related to "Node D"
SELECT *
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `n`.`id` = `ance`.`descendant_id`
WHERE `ancestor_id` IN
    ( SELECT `ancestor_id`
     FROM `adjacencies`
     WHERE `descendant_id` = 4
       AND NOT `ancestor_id` = 4 )
  AND `descendant_id` IN
    ( SELECT `descendant_id`
     FROM `adjacencies`
     WHERE `ancestor_id` = 4 )
-- Note to self: can I just re-use the code for getting descendants including self?


-- get all direct descendants of a node, excluding self
-- Same as getting all descendants, with the additional where clause:
-- AND `ance`.`lvl` = 1
-- Note: AND NOT `ance`.`descendant_id` = 1 isn't really needed here
-- because that result will also have a lvl of 0
-- Note: changing `lvl` to > 1 will find all children that distance away,
-- making 2 == grand-children, 3 == great grand-children, etc.
SELECT n.*
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `ance`.`descendant_id` = `n`.`id`
WHERE `ance`.`ancestor_id` = 1
    AND NOT `ance`.`descendant_id` = 1 
    AND `ance`.`lvl` = 1;


-- adding a new node
-- manually is as follows:
SELECT `ancestor_id`,
       2,
       `lvl`+1 AS `new_level`
FROM `adjacencies`
WHERE `descendant_id` = 1;
-- for each result:
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (?, ?, ?);
-- finally, add self.
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`) VALUES (2, 2, 0);

-- adding a new node
-- automatically is as follows:
INSERT INTO `adjacencies` (`ancestor_id`, `descendant_id`, `lvl`)
SELECT `ancestor_id`,
       2,
       lvl+1
FROM `adjacencies`
WHERE `descendant_id` = 1
UNION ALL
SELECT 2,
       2,
       0;

-- finding root notes (that is, those with no ancestor)
SELECT `n`.*
FROM `nodes` AS `n`
LEFT JOIN `adjacencies` AS `ance` ON `n`.`id` = `ance`.`descendant_id`
WHERE `ance`.`ancestor_id` IS NULL
  AND `ance`.`lvl` = 1;