PostgreSQL design of dependency tree without circular 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 of representing this relationship that also prevents circular dependencies (i.e. a group of events leading back into an event in that same group).

I currently have a link table external to EVENTS, call it EVENTS_DEP. This table links dependent rows to the rows they depend on and allows for multiple dependencies on one row. How would I prevent circular dependencies using such a table?

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

Also, if this can only be done using triggers, please let me know what kind of trigger (i.e. on what event) it should be run on (on insert, maybe?).

Answer 1

INSERT Trigger to check this.

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 would be needed

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 it does is when a new link is added between parent A and child B it uses A WITH RECURSIVE query to find all ancestors of A. B shouldn't be one of them.

The UPDATE trigger is harder because when the trigger is executed to old link is still there so the test from the INSERT trigger could give a false positive when used for UPDATEs.

So for the UPDATE we need to add some extra 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();