SQLite Forum

cycle detection in CHECK constraint with recursive CTE
Login
I think your schema is to blame. If you want a DAG, then use a single table, with a self-referential parent.

Most DBMS's implement ***immediate*** Foreign-Keys by default, <s>unlike SQLite.</s> (see correction in follow-up posts)  
So with a table such as:
```
CREATE TABLE IF NOT EXISTS "tag" (
  "id" integer NOT NULL PRIMARY KEY AUTOINCREMENT, 
  "name" varchar(40) NOT NULL UNIQUE,
  "parent" integer REFERENCES "tag" ("id"),
  UNIQUE(parent, name) -- or UNIQUE(name), depends what you want
);
```
You cannot event insert a cycle with that schema, ensuring a DAG.

With deferred FKs, <s>the only mode in SQLite</s> (see later posts), you then need to resort  
to a TRIGGER to detect cycles, but that trigger can be much faster,  
since starting from the leaves, instead of the roots like yours above.  
It only has to detect a duplicate ID when traversing from the one leaf  
(that fired the trigger) to its root, which is log(N).

Maybe I missed something, and the above is wrong. I'll know soon I guess :)

PS: AFAIK, a CHECK constraint can only access the local row, not do an arbitrary query,   
so that approach was flawed from the get go I believe. Happy to be corrected on that.