Skip to content

Instantly share code, notes, and snippets.

@zanbaldwin

zanbaldwin/Hierarchal CTE in SQL.md

Last active August 22, 2018 18:08
Show Gist options
  • Save zanbaldwin/03f4d1f1ae6a6b2546b33cc24f56ce94 to your computer and use it in GitHub Desktop.
Save zanbaldwin/03f4d1f1ae6a6b2546b33cc24f56ce94 to your computer and use it in GitHub Desktop.
Download ZIP
Playing around with Hierarchal Tree Structures and Common Table Expressions
Raw
Hierarchal CTE in SQL.md

Accessing Tree Hierarchies using Common Table Expressions

Examples have been tested with MySQL 8.0.12.

Table Structure

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;

Example Data

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

Queries

Listing All Nodes

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 from its Fully Qualified Path

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

Fetching a Node via its ID

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

Fetching the Linear Hierarchy of a Node

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment