I have a database that implements a very simple tree structure with a table, hierarchy, which has two columns, parent and child.

 CREATE TABLE hierarchy (
     parent INTEGER,
     child  INTEGER,
     PRIMARY KEY(parent, child)
 );

I need to ensure that there are no cycles on the graph defined by the table's rows. For example, if hierarchy has (1, 2) and (2, 3), inserting (3, 1) or using UPDATE to change (2, 3) to (2, 1) should not be allowed. To do this, I figured the most appropiate way to do this would be defining two TRIGGERs (one for INSERT and another for UPDATE) that would check if the command would create a cycle in the database. I would also need recursion for this, so I would need the WITH clause.

However, according to section 5 of SQLite's documentation on the WITH clause, it cannot be used within a TRIGGER. Thus, I moved the WITH to a function defined in C++, which is lookForCycles, that is called from the TRIGGER.

CREATE TRIGGER prevent_cycles_insert 
     BEFORE INSERT ON hierarchy 
     FOR EACH ROW 
     BEGIN 
        SELECT
        CASE
           WHEN lookForCycles(NEW.parent, NEW.child) = 1 THEN
              RAISE(ABORT, 'Cycle detected in INSERT INTO hierarchy!')
        END;
     END;

CREATE TRIGGER prevent_cycles_update 
     BEFORE UPDATE ON hierarchy 
     FOR EACH ROW 
     BEGIN 
        SELECT
        CASE
           WHEN lookForCycles(NEW.parent, NEW.child) = 1 THEN
              RAISE(ABORT, 'Cycle detected in UPDATE hierarchy!')
        END;
     END; 

lookForCycles simply executes the following SQLite command. Note that the parameters (the question marks) are set to the values of lookForCycles 's arguments using sqlite3_bind_value .

WITH RECURSIVE ancestors(node) AS(
   SELECT ?
   UNION ALL
   SELECT h.parent
   FROM hierarchy h
   JOIN ancestors a ON h.child = a.node
)
SELECT 1 FROM ancestors WHERE node = ?;

I have tested this implementation, and it works as expected. For example, if I put the following rows into hierarchy: (1, 2) (1, 3), (2, 3) and (3, 4), trying to insert (4, 1) or updating (3, 4) to (3, 1) fails with "Cycle detected in INSERT INTO/UPDATE hierarchy!".

What worries me is that, even if the WITH clause is used in a completely different context than the TRIGGER, as it is called from a C++ function, I don't know if it works now, but is not guaranteed to do the same for all cases. If someone with more knowledge about SQLite could tell me if this is how I should do it, it would be great!

Two annotations:

1. I know I could implement this with recursive TRIGGERs and I have already thought about a possible algorithm, but I would rather avoid that option, as it would probably require using a temporary table and would be way more complex than simply using a WITH.

2. This also works, for some reason, even though I'm using WITH directly inside the TRIGGER:

   CREATE TRIGGER prevent_cycles
   BEFORE INSERT ON hierarchy
   FOR EACH ROW
   BEGIN
       WITH RECURSIVE ancestors(node) AS (
           SELECT NEW.parent
           UNION ALL
           SELECT h.parent
           FROM hierarchy h
           JOIN ancestors a ON h.child = a.node
       )
       SELECT
           CASE
               WHEN EXISTS (
                   SELECT 1 FROM ancestors WHERE node = NEW.child
               ) THEN
                   RAISE(ABORT, 'Cycle detected!')
           END;
   END;