CODEWITHSUNDEEP
sqlpostgresqldatabase-designtreecircular-dependency
Adam
Adam

Reputation: 3778

PostgreSQL design of dependency tree without circular dependencies

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?).

Upvotes: 10

Views: 3448

Answers (2)

Eelke
Eelke

Reputation: 22023

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();

Upvotes: 11

Erwin Smout
Erwin Smout

Reputation: 18408

It is not possible to do this with SQL engines and without programming triggers. For an SQl engine to support this, it would need to support recursive SQL (aka recursive WITH expressions, or recursive CTE's), as well as reliable support for ASSERTIONs.

Many have support for CTE's/WITH expressions, though perhaps not all of them also support the recursive version of the feature. As for ASSERTIONs otoh, I'm told there is only one systems that supports them, but the implementation is so flawed and bug-ridden that it's laughable to consider using it seriously.

There are systems that allow you to do exactly as you ask, but don't expect to talk SQL to such systems. The authors of such systems take a pride in keeping their babies relational.

Upvotes: 1

Related Questions