Examples have been tested with MySQL
8.0.12
.
CREATE TABLE `nodes` (
`id` INT(11) NOT NULL AUTO_INCREMENT,
`parent` INT(11) DEFAULT NULL,
`slug` VARCHAR(512) NOT NULL,
`title` VARCHAR(64) DEFAULT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `unique_siblings` (`parent`, `slug`),
CONSTRAINT `node_parents` FOREIGN KEY (`parent`)
REFERENCES `nodes` (`id`)
ON DELETE CASCADE
ON UPDATE CASCADE
)
ENGINE=InnoDB
DEFAULT CHARSET=utf8mb4
COLLATE=utf8mb4_0900_ai_ci;
INSERT INTO `nodes` (`id`, `parent`, `slug`, `title`) VALUES (1, NULL, 'animalia', 'Animalia'), (13, NULL, 'blog', 'Blog'), (4, 1, 'anthropoda', 'Anthropoda'), (2, 1, 'chordate', 'Chordate'), (5, 1, 'insect', 'Insect'), (14, 13, 'carnivora', 'Interesting facts about Carnivora'), (3, 2, 'mammal', 'Mammal'), (8, 5, 'diptera', 'Diptera'), (7, 3, 'carnivora', 'Carnivora'), (6, 3, 'primate', 'Primate'), (12, 8, 'muscidae', 'Muscidae'), (11, 7, 'felidae', 'Felidae'), (9, 6, 'hominidae', 'Hominidae'), (10, 6, 'pongidae', 'Pongidae'), (18, 12, 'musca', 'Musca'), (17, 11, 'felis', 'Felis'), (15, 9, 'homo', 'Homo'), (16, 10, 'pan', 'Pan'), (23, 18, 'domestica', 'Domestica'), (21, 17, 'domestica', 'Domestica'), (22, 17, 'leo', 'Leo'), (19, 15, 'sapiens', 'Sapiens'), (20, 16, 'troglodytes', 'Troglodytes'), (29, 23, 'housefly', 'Housefly'), (27, 21, 'house-cat', 'House Cat'), (28, 22, 'lion', 'Lion'), (25, 19, 'human', 'Human'), (26, 20, 'chimpanzee', 'Chimpanzee');
+----+--------+-------------+-----------------------------------+
| id | parent | slug | title |
+----+--------+-------------+-----------------------------------+
| 1 | NULL | animalia | Animalia |
| 2 | 1 | chordate | Chordate |
| 3 | 2 | mammal | Mammal |
| 4 | 1 | anthropoda | Anthropoda |
| 5 | 1 | insect | Insect |
| 6 | 3 | primate | Primate |
| 7 | 3 | carnivora | Carnivora |
| 8 | 5 | diptera | Diptera |
| 9 | 6 | hominidae | Hominidae |
| 10 | 6 | pongidae | Pongidae |
| 11 | 7 | felidae | Felidae |
| 12 | 8 | muscidae | Muscidae |
| 13 | NULL | blog | Blog |
| 14 | 13 | carnivora | Interesting facts about Carnivora |
| 15 | 9 | homo | Homo |
| 16 | 10 | pan | Pan |
| 17 | 11 | felis | Felis |
| 18 | 12 | musca | Musca |
| 19 | 15 | sapiens | Sapiens |
| 20 | 16 | troglodytes | Troglodytes |
| 21 | 17 | domestica | Domestica |
| 22 | 17 | leo | Leo |
| 23 | 18 | domestica | Domestica |
| 25 | 19 | human | Human |
| 26 | 20 | chimpanzee | Chimpanzee |
| 27 | 21 | house-cat | House Cat |
| 28 | 22 | lion | Lion |
| 29 | 23 | housefly | Housefly |
+----+--------+-------------+-----------------------------------+
List all nodes in the tree, including their fully-qualified path and depth.
WITH RECURSIVE tree (id, parent, path, title, depth) AS (
SELECT node.id, node.parent, CONCAT('/', node.slug) AS path, node.title, 1 AS depth
FROM nodes AS node
WHERE node.parent IS NULL
UNION
SELECT node.id, node.parent, CONCAT(tree.path, '/', node.slug) AS path, node.title, tree.depth + 1 AS depth
FROM tree
JOIN nodes AS node ON tree.id = node.parent
) SELECT * FROM tree;
+------+--------+-----------------------------------------------------------------------+-----------------------------------+-------+
| id | parent | path | title | depth |
+------+--------+-----------------------------------------------------------------------+-----------------------------------+-------+
| 1 | NULL | /animalia | Animalia | 1 |
| 13 | NULL | /blog | Blog | 1 |
| 4 | 1 | /animalia/anthropoda | Anthropoda | 2 |
| 2 | 1 | /animalia/chordate | Chordate | 2 |
| 5 | 1 | /animalia/insect | Insect | 2 |
| 14 | 13 | /blog/carnivora | Interesting facts about Carnivora | 2 |
| 3 | 2 | /animalia/chordate/mammal | Mammal | 3 |
| 8 | 5 | /animalia/insect/diptera | Diptera | 3 |
| 7 | 3 | /animalia/chordate/mammal/carnivora | Carnivora | 4 |
| 6 | 3 | /animalia/chordate/mammal/primate | Primate | 4 |
| 12 | 8 | /animalia/insect/diptera/muscidae | Muscidae | 4 |
| 11 | 7 | /animalia/chordate/mammal/carnivora/felidae | Felidae | 5 |
| 9 | 6 | /animalia/chordate/mammal/primate/hominidae | Hominidae | 5 |
| 10 | 6 | /animalia/chordate/mammal/primate/pongidae | Pongidae | 5 |
| 18 | 12 | /animalia/insect/diptera/muscidae/musca | Musca | 5 |
| 17 | 11 | /animalia/chordate/mammal/carnivora/felidae/felis | Felis | 6 |
| 15 | 9 | /animalia/chordate/mammal/primate/hominidae/homo | Homo | 6 |
| 16 | 10 | /animalia/chordate/mammal/primate/pongidae/pan | Pan | 6 |
| 23 | 18 | /animalia/insect/diptera/muscidae/musca/domestica | Domestica | 6 |
| 21 | 17 | /animalia/chordate/mammal/carnivora/felidae/felis/domestica | Domestica | 7 |
| 22 | 17 | /animalia/chordate/mammal/carnivora/felidae/felis/leo | Leo | 7 |
| 19 | 15 | /animalia/chordate/mammal/primate/hominidae/homo/sapiens | Sapiens | 7 |
| 20 | 16 | /animalia/chordate/mammal/primate/pongidae/pan/troglodytes | Troglodytes | 7 |
| 29 | 23 | /animalia/insect/diptera/muscidae/musca/domestica/housefly | Housefly | 7 |
| 27 | 21 | /animalia/chordate/mammal/carnivora/felidae/felis/domestica/house-cat | House Cat | 8 |
| 28 | 22 | /animalia/chordate/mammal/carnivora/felidae/felis/leo/lion | Lion | 8 |
| 25 | 19 | /animalia/chordate/mammal/primate/hominidae/homo/sapiens/human | Human | 8 |
| 26 | 20 | /animalia/chordate/mammal/primate/pongidae/pan/troglodytes/chimpanzee | Chimpanzee | 8 |
+------+--------+-----------------------------------------------------------------------+-----------------------------------+-------+
Finding a node given its fully-qualified path means calculating the FQ path for every node. Working backwards from a
known slug
can decrease load:
<?php
function findNodeFromPath(string $path)
{
$slug = substr(strrchr(rtrim($path, '/'), '/'), 1) ?: trim($path, '/');
return $database->query($SQL, [
'path' => $path,
'slug' => $slug,
]);
}
WITH RECURSIVE backwards_tree (id, parent, path, title, depth) AS (
SELECT
node.id AS id,
node.parent AS parent,
CONCAT('/', node.slug) AS path,
node.title AS title,
1 AS depth
FROM nodes AS node
WHERE node.slug = :slug
UNION
SELECT
backwards_tree.id AS id,
node.parent AS parent,
CONCAT('/', node.slug, backwards_tree.path) AS path,
backwards_tree.title AS title,
backwards_tree.depth + 1 AS depth
FROM backwards_tree
JOIN nodes AS node ON backwards_tree.parent = node.id
)
SELECT *
FROM backwards_tree
WHERE parent IS NULL
AND path = :path;
Given a path of /animalia/chordate/mammal/carnivora
:
+------+--------+-------------------------------------+-----------+-------+
| id | parent | path | title | depth |
+------+--------+-------------------------------------+-----------+-------+
| 7 | NULL | /animalia/chordate/mammal/carnivora | Carnivora | 4 |
+------+--------+-------------------------------------+-----------+-------+
WITH RECURSIVE backwards_tree (id, parent, path, title, depth) AS (
SELECT
node.id AS id,
node.parent AS parent,
CONCAT('/', node.slug) AS path,
node.title AS path,
1 AS depth
FROM nodes AS node
WHERE node.id = :nodeId
UNION
SELECT
backwards_tree.id AS id,
node.parent AS parent,
CONCAT('/', node.slug, backwards_tree.path) AS path,
backwards_tree.title AS title,
backwards_tree.depth + 1 AS depth
FROM backwards_tree
JOIN nodes AS node ON backwards_tree.parent = node.id
)
SELECT * FROM backwards_tree
WHERE parent IS NULL;
Given an ID of 17
:
+------+--------+---------------------------------------------------+-------+-------+
| id | parent | path | title | depth |
+------+--------+---------------------------------------------------+-------+-------+
| 17 | NULL | /animalia/chordate/mammal/carnivora/felidae/felis | Felis | 6 |
+------+--------+---------------------------------------------------+-------+-------+
The following takes a node ID and returns the fully qualified paths for itself, its parent (and grand-parent and so on until a root node), and a variable number of child nodes. It includes the absolute depth of each node returned and the relative depth according to the node queried for.
WITH RECURSIVE
backwards (id, parent, title, depth) AS (
SELECT
page.id AS id,
page.parent AS parent,
page.title AS title,
0 AS depth
FROM pages AS page
WHERE page.id = :nodeId
UNION
SELECT
page.id AS id,
page.parent AS parent,
page.title AS title,
backwards.depth - 1 AS depth
FROM backwards
JOIN pages AS page ON backwards.parent = page.id
),
forwards (id, parent, title, depth) AS (
SELECT
page.id AS id,
page.parent AS parent,
page.title, 0 AS depth
FROM pages AS page
WHERE page.id = :nodeId
UNION
SELECT
page.id AS id,
page.parent AS parent,
page.title AS title,
forwards.depth + 1 AS depth
FROM forwards
JOIN pages AS page ON forwards.id = page.parent
WHERE forwards.depth <= :childDepth - 1
),
paths (id, parent, path, title, depth) AS (
SELECT page.id, page.parent, CONCAT('/', page.slug) AS path, page.title, 1 AS depth
FROM pages AS page
WHERE page.parent IS NULL
UNION
SELECT page.id, page.parent, CONCAT(path.path, '/', page.slug) AS path, page.title, path.depth + 1 AS depth
FROM paths AS path
JOIN pages AS page ON path.id = page.parent
)
SELECT
`linear`.id AS id,
`linear`.title AS title,
`linear`.depth AS relative,
path.depth AS absolute,
path.path AS path
FROM (SELECT * FROM forwards UNION SELECT * FROM backwards) AS `linear`
JOIN paths AS path ON `linear`.id = path.id
ORDER BY relative, path;
If it were executed with the parameters [nodeId => 3, childDepth => 2]
the following results would be returned:
+------+-----------+----------+----------+---------------------------------------------+
| id | title | relative | absolute | path |
+------+-----------+----------+----------+---------------------------------------------+
| 1 | Animalia | -2 | 1 | /animalia |
| 2 | Chordate | -1 | 2 | /animalia/chordate |
| 3 | Mammal | 0 | 3 | /animalia/chordate/mammal |
| 7 | Carnivora | 1 | 4 | /animalia/chordate/mammal/carnivora |
| 6 | Primate | 1 | 4 | /animalia/chordate/mammal/primate |
| 11 | Felidae | 2 | 5 | /animalia/chordate/mammal/carnivora/felidae |
| 9 | Hominidae | 2 | 5 | /animalia/chordate/mammal/primate/hominidae |
| 10 | Pongidae | 2 | 5 | /animalia/chordate/mammal/primate/pongidae |
+------+-----------+----------+----------+---------------------------------------------+
Unfortunately this singular query requires the use of the first query defined in this document, meaning the fully
qualified path for all nodes must be calculated (the computational complexity would be O(∑d)
meaning the sum of the depth of each node and would depend on the relations/foreign keys of the data rather than number of rows). To remove this requirement either a function/routine must be defined to
calculate only the paths of the nodes returned, or know more about Common Table Expressions that I can learn in one day
(because I can't be bothered to do this anymore).