Forbidding insertion of integer not in rowid in SQLite (keep directed acyclic graph table consistent)

Question

I'd like to express:

"insertion of record with 'parent' value that is not included in 'rowid' AFTER INSERTION is forbidden."

My intention is to keep the table internally consistent as a directed acyclic graph, with every record being a node referring to its parent (root nodes are their own parent). How can I do that?

Here's what I have (with rowid used as the primary key):

CREATE TABLE Heap (                                                                                                       
                   name   TEXT     CHECK(typeof(name) = 'text')                                                           
                                   NOT NULL                                                                               
                                   UNIQUE                      ,                                       
                   parent INTEGER  DEFAULT rowid               ,                                       
                   color  INTEGER  CHECK(color BETWEEN 0 AND 2)                                                           
                  );                                                                                                    
                                                                                                                      
CREATE TRIGGER parent_not_in_rowid                                                                                        
BEFORE INSERT ON Heap                                                                                                     
BEGIN                                                                                                                     
 SELECT RAISE(FAIL, 'parent id inconsistent') FROM Heap                                                                   
 WHERE NOT EXISTS(SELECT 1 FROM Heap WHERE NEW.rowid = NEW.parent);                                                       
END;

Answer 1

I would suggest to use null values in the column parent for root nodes, because this way all you have to do is add referential integrity to your table.

Add a column id defined as INTEGER PRIMARY KEY, so that it is an alias of the rowid and also make the column parent to reference id:

CREATE TABLE Heap ( 
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL UNIQUE CHECK(typeof(name) = 'text'),
  parent INTEGER REFERENCES Heap(id),                                       
  color INTEGER CHECK(color BETWEEN 0 AND 2)                                                           
); 

Now, turn on foreign key support:

PRAGMA foreign_keys = ON;

and insert rows:

INSERT INTO Heap (name, parent, color) VALUES ('name1', null, 1);
INSERT INTO Heap (name, parent, color) VALUES ('name2', 1, 1);

This will fail:

INSERT INTO Heap (name, parent, color) VALUES ('name3', 5, 2);

because there is no row in the table with id = 5.

See the demo.