"No Loop" Constraint for hierarchical data in postgresql I've got table like this in postgres:


id primary key
parent_id foreign key on id
some data columns


I need no a constrain which prevents cycles on the parent relations. There might be more tree in the table (root of a tree is null in parent_id).

How to achieve this goal?

Thanks

Daniel
You can't express the constraint that an edge-list must be acyclic as a CHECK constraint.

It would have to be an ASSERTION constraint, which PostgreSQL does not support.

You'll have to LOCK TABLE to prevent concurrent INSERTs or UPDATEs and check it with an AFTER trigger. 

The resulting lock upgrade issues will result in frequent deadlocks. To prevent them your app will have to lock the table before inserting/updating, e.g.

BEGIN;
LOCK TABLE my_table IN EXCLUSIVE MODE;
INSERT INTO my_table (...) VALUES (...);
-- Trigger runs to sanity check table here
COMMIT;


You might find it useful to make the trigger a deferred constraint trigger, so the table is allowed to temporarily enter invalid states so long as it's valid again by the time you commit.