3

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.

  • Please UPDATE your question. – CL. Apr 9 '16 at 15:40
  • @CL.: Sorry, but I do not understand what I should update exactly? – equaeghe Apr 10 '16 at 14:50
  • 1
    You are talking about inserting, but it is not possible to change any root this way. – CL. Apr 10 '16 at 16:00
  • @CL.: Can you explain why? Manually, I would in Case 1 insert 'd', 'b', 'a' and update 'd''s "root" to 'a'; in Case 2 I would insert 'e', null, 'e' and update 'a''s "parent" to 'e' and 'a', 'b', and 'c''s "root" to 'e'. I was hoping that this could be automated with the right insertion/updating approach and conflict resolution. – equaeghe Apr 10 '16 at 16:18
  • I've edited your question to clarify that you do not mean insert but "insert or update". – ypercubeᵀᴹ Apr 10 '16 at 18:13
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.