Prevent loops in many-to-many self-referencing relationship (Postgres)

Question

Suppose you want to have a hierarchy of things where a thing can have multiple thing parents and children:

CREATE TABLE thing (
    id SERIAL PRIMARY KEY
);

CREATE TABLE thing_association (
    parent_id INTEGER NOT NULL,
    child_id INTEGER NOT NULL,
    PRIMARY KEY (parent_id, child_id),
    CHECK (parent_id != child_id),
    FOREIGN KEY (parent_id) REFERENCES thing(id),
    FOREIGN KEY (child_id) REFERENCES thing(id)
);

The CHECK constraint prevents a thing from having a relationship with itself, and the PRIMARY KEY constraint prevents duplicate relationships, but can loops be prevented?

More precisely, if row (x, y) exists in the thing_association table, can the row (y, x) be prevented from being inserted?

Going a step further, if rows (x, y) and (y, z) exist in the thing_association, can the row (z, x) be prevented from being inserted?

Answer 1

I was hoping to accomplish this without triggers, but I'm not sure that's possible. I was able to accomplish this with a BEFORE INSERT trigger:

CREATE TABLE thing (
    id SERIAL PRIMARY KEY
);

CREATE TABLE thing_association (
    parent_id INTEGER NOT NULL,
    child_id INTEGER NOT NULL,
    PRIMARY KEY (parent_id, child_id),
    CHECK (parent_id != child_id),
    FOREIGN KEY (parent_id) REFERENCES thing(id),
    FOREIGN KEY (child_id) REFERENCES thing(id)
);

/* maps every thing to all of it's parents */
CREATE VIEW thing_hierarchy AS
WITH RECURSIVE children AS (
    SELECT
        child_id,
        parent_id
    FROM thing_association
    UNION SELECT
        children.child_id,
        parents.parent_id
    FROM thing_association AS parents
    INNER JOIN children
        ON children.parent_id = parents.child_id
) SELECT * FROM children;

CREATE FUNCTION check_thing_association_loop() RETURNS TRIGGER AS $$
BEGIN
    IF ((NEW.parent_id, NEW.child_id) in (SELECT child_id, parent_id FROM thing_hierarchy)) THEN
    RAISE EXCEPTION 'Cannont create a hierarchy loop';
    END IF;
    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER thing_association_insert_check
    BEFORE INSERT ON thing_association
    FOR EACH ROW EXECUTE FUNCTION check_thing_association_loop();

You could merge the view into the trigger function, but the view is useful on its own and it keeps things succint.