PostgreSQL dependency tree design without cyclic dependencies

Question

I have a table, call it EVENTS, where each row can depend on 0 or more other rows in the table. I need a way to represent this relationship that also prevents circular dependencies (i.e. a group of events returning to an event in the same group).

I currently have a link table external to EVENTS, name it EVENTS_DEP. This table associates dependent rows with the rows on which they depend, and allows you to use multiple dependencies on the same row. How can I prevent circular dependencies using such a table?

NOTE. If at all it is only possible to do with the design of the database (not with scripts, triggers, etc.), this would be ideal.

In addition, if this can only be done using triggers, tell me which trigger (that is, at what event) it should be fired (on the inset, maybe?).

Answer 1

INSERT Trigger to check this out.

Assuming the following table structure

CREATE TABLE event ( id bigserial PRIMARY KEY, foo varchar ); CREATE TABLE event_deps ( parent bigint REFERENCES event(id), child bigint REFERENCES event(id), PRIMARY KEY (parent, child), CHECK (parent <> child) ); 

The following INSERT trigger is required

 CREATE FUNCTION deps_insert_trigger_func() RETURNS trigger AS $BODY$ DECLARE results bigint; BEGIN WITH RECURSIVE p(id) AS ( SELECT parent FROM event_deps WHERE child=NEW.parent UNION SELECT parent FROM p, event_deps d WHERE p.id = d.child ) SELECT * INTO results FROM p WHERE id=NEW.child; IF FOUND THEN RAISE EXCEPTION 'Circular dependencies are not allowed.'; END IF; RETURN NEW; END; $BODY$ LANGUAGE plpgsql; CREATE TRIGGER before_insert_event_deps_trg BEFORE INSERT ON event_deps FOR EACH ROW EXECUTE PROCEDURE deps_insert_trigger_func(); 

What he does when a new link is added between parent A and child B, he uses the query A WITH RECURSIVE to find all the ancestors of A. B should not be one of them.

The UPDATE trigger is more complicated, because when you start the trigger on the old link, you still have one, so the test from the INSERT trigger can give a false positive value when used for UPDATE.

So, for UPDATE we need to add additional conditions to hide the old data.

 CREATE FUNCTION deps_update_trigger_func() RETURNS trigger AS $BODY$ DECLARE results bigint; BEGIN WITH RECURSIVE p(id) AS ( SELECT parent FROM event_deps WHERE child=NEW.parent AND NOT (child = OLD.child AND parent = OLD.parent) -- hide old row UNION SELECT parent FROM p, event_deps d WHERE p.id = d.child AND NOT (child = OLD.child AND parent = OLD.parent) -- hide old row ) SELECT * INTO results FROM p WHERE id=NEW.child; IF FOUND THEN RAISE EXCEPTION 'Circular dependencies are not allowed.'; END IF; RETURN NEW; END; $BODY$ LANGUAGE plpgsql; CREATE TRIGGER before_update_event_deps_trg BEFORE UPDATE ON event_deps FOR EACH ROW EXECUTE PROCEDURE deps_update_trigger_func(); 

Answer 2

This cannot be done using SQL engines and without programming triggers. To support the SQl mechanism, it must support recursive SQL (also WITH recursive expressions or CTE recursive), as well as robust ASSERTION support.

Many have support for CTE / WITH expressions, although it is possible that not all of them also support a recursive version of this function. As for ASSERTIONs otoh, they tell me that there is only one system that supports them, but the implementation is so erroneous and erroneous that it is ridiculous to take it seriously.

There are systems that allow you to do what you ask, but don't expect SQL to talk to such systems. The authors of such systems are proud that their children are relational.