How to maintain trees and their roots in SQLite

Question

I have a (SQLite) database with a table representing nodes in a forest (set of trees):

create table "Node" (
    "id" Text primary key,
    "parent" Text references "Node" ("id") -- parent node
        on update restrict on delete restrict,
    "root" Text references "Node" ("id") -- tree root node
        on update restrict on delete restrict
) without rowid;

It may happen that after inserting new nodes or updating existing ones, "root" attribute updates must be performed on the inserted nodes or nodes previously in the table, because the inserted nodes are connected to or existing trees.

Consider the following existing table:

"id" "parent" "root"
--------------------
'a'  null     'a'
'b'  'a'      'a'
'c'  'a'      'a'

• Case 1: we want to insert/ignore the following nodes

  "id" "parent" "root"
  --------------------
  'b'  null     'b'           -- ignore
  'd'  'b'      'b'           -- insert
  

  To end up with

  "id" "parent" "root"
  --------------------
  'a'  null     'a'
  'b'  'a'      'b'
  'c'  'a'      'a'
  'd'  'b'      'b'
  

• Case 2: we want to insert/update (in the original table, without the case 1 changes)

  "id" "parent" "root"
  --------------------
  'e'  null     'e'           -- insert
  'a'  'e'      'e'           -- update
  

  To end up with

  "id" "parent" "root"
  --------------------
  'e'  null     'e'
  'a'  'e'      'e'
  'b'  'a'      'e'
  'c'  'a'      'e'
  

Given these cases: what are insert/update statements (and perhaps triggers) that allow me to do obtain the correct resulting trees? One part is: when the node is already in the table, then I need to ‘merge’ it correctly with its version from the insert and then I need to propagate in some way the change of root.

One idea I had was to create a second table containing just a list of roots and then having "root" refer there, so that it could cascade on update. But then I don't know how to deal with updates that replace a root by an already existing one.

Answer 1

Finding all nodes in a subtree to update them requires a recursive common table expression:

-- update the root of all nodes in 'a's subtree to 'x'
WITH RECURSIVE subtree(id) AS (
    VALUES('a')
    UNION ALL
    SELECT Node.id
    FROM Node
    JOIN subtree ON Node.parent = subtree.id
)
UPDATE Node
SET root = 'x'
WHERE id IN subtree;

In SQLite, CTEs are not allowed in triggers.