Transitive Closure of Acyclic Graphs [PostgreSQL]

transitive_clojure_pg.sql

-- Maintaining Transitive Closure of Graphs in SQL (1999)
-- https://corescholar.libraries.wright.edu/knoesis/399/

-- Set up

DROP TABLE IF EXISTS graph;
DROP TABLE IF EXISTS transitive_closures;

CREATE TABLE graph (
  x VARCHAR(5) NOT NULL,
  y VARCHAR(5) NOT NULL
);

CREATE UNIQUE INDEX index_graph_edges ON graph (x, y);

CREATE TABLE transitive_closures (
  x VARCHAR(5) NOT NULL,
  y VARCHAR(5) NOT NULL
);

CREATE UNIQUE INDEX index_transitive_closure_edges ON transitive_closures (x, y);

-- 2 Transitive Closures of Acyclic Graphs

-- Set up

INSERT INTO graph (x, y) VALUES ('x', 'a'), ('b', 'y');
INSERT INTO transitive_closures (x, y) VALUES ('x', 'a'), ('b', 'y');

---
-- Maintenance Under Insertion

-- Insertion of edge (a, b).

INSERT INTO graph (x, y) VALUES ('a', 'b');

  WITH vars (a, b) AS (VALUES ('b', '1'))
SELECT *
  INTO TEMP tc_new
  FROM (SELECT a AS x, b AS y FROM vars
        UNION SELECT x, b AS y
          FROM transitive_closures, vars
         WHERE y = a
        UNION SELECT a, y
                FROM transitive_closures, vars
               WHERE x = b
        UNION SELECT tc1.x, tc2.y
                FROM transitive_closures AS tc1, transitive_closures AS tc2, vars
               WHERE tc1.y = a AND tc2.x = b
       ) AS _;

SELECT *
  INTO TEMP delta
  FROM tc_new AS t
 WHERE NOT EXISTS (
   SELECT *
     FROM transitive_closures
    WHERE transitive_closures.x = t.x AND transitive_closures.y = t.y
 );

INSERT INTO transitive_closures SELECT * FROM delta;

-- Expected outcome:
--
-- (x) -> old path -> (a) -> new path -> (b) -> old path -> (y)
--  +---> new path -----------------------^
--  |                  +---> new path -----------------------^
--  +---> new path ------------------------------------------^

---
-- Maintenance Under Deletions

-- Set up

INSERT
  INTO graph (x, y)
VALUES ('0', 'a'),
       ('0', 'c'),
       ('a', 'b'),
       ('c', 'a'),
       ('c', 'b'),
       ('b', '1');

INSERT
  INTO transitive_closures
VALUES ('0', 'a'),
       ('0', 'c'),
       ('a', 'b'),
       ('0', 'b'),
       ('c', 'b'),
       ('c', 'a'),
       ('c', '1'),
       ('a', '1'),
       ('0', '1'),
       ('b', '1');

-- Step 1: Finding the suspects

  WITH vars (a, b) AS (VALUES ('a', 'b'))
SELECT *
  INTO TEMP suspect
  FROM (SELECT tc1.x, tc2.y
          FROM transitive_closures AS tc1, transitive_closures AS tc2, vars
         WHERE tc1.y = a AND tc2.x = b
        UNION SELECT x, b
                FROM transitive_closures, vars
               WHERE y = a
        UNION SELECT a, y
                FROM transitive_closures, vars
               WHERE x = b
        UNION SELECT a, b FROM vars
       ) AS _;

-- Step 2: Finding the trusty guys

  WITH vars (a, b) AS (VALUES ('a', 'b'))
SELECT *
  INTO TEMP trusty
  FROM (
    SELECT * FROM transitive_closures WHERE NOT EXISTS (
      SELECT *
        FROM suspect
       WHERE suspect.x = transitive_closures.x AND suspect.y = transitive_closures.y
                      )
    UNION SELECT graph.*
            FROM graph, vars
           WHERE x <> a AND y <> b
       ) AS _;

-- Step 3: Deleting the bad guys

SELECT *
INTO TEMP tc_new
  FROM (SELECT * FROM trusty
        UNION SELECT t1.x, t2.y
                FROM trusty t1, trusty t2
                WHERE t1.y = t2.x
        UNION SELECT t1.x, t3.y
                FROM trusty t1, trusty t2, trusty t3
                WHERE t1.y = t2.x AND t2.y = t3.x
       ) AS _;

DELETE FROM transitive_closures
      WHERE NOT EXISTS(
                  SELECT *
                    FROM tc_new AS t
                   WHERE t.x = transitive_closures.x AND t.y = transitive_closures.y
                );

And here are the triggers to make this behavior automatic on INSERT, DELETE, and TRUNCATE.

CREATE OR REPLACE FUNCTION fn_truncate_transitive_closure() RETURNS TRIGGER AS
$$
BEGIN
  TRUNCATE transitive_closures;
  RETURN NEW;
END
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS tr_graph_after_truncate ON graph;

  CREATE TRIGGER tr_graph_after_truncate AFTER TRUNCATE
              ON graph
EXECUTE FUNCTION fn_truncate_transitive_closure();

CREATE OR REPLACE FUNCTION fn_insert_transitive_closure() RETURNS TRIGGER AS
$$
BEGIN
  CREATE TEMP TABLE IF NOT EXISTS tc_new AS
  SELECT *
    FROM (SELECT NEW.x, NEW.y
          UNION SELECT x, NEW.y
            FROM transitive_closures
           WHERE y = NEW.x
          UNION SELECT NEW.x, y
                  FROM transitive_closures
                 WHERE x = NEW.y
          UNION SELECT tc1.x, tc2.y
                  FROM transitive_closures AS tc1, transitive_closures AS tc2
                 WHERE tc1.y = NEW.x AND tc2.x = NEW.y
         ) AS _;

  CREATE TEMP TABLE IF NOT EXISTS delta AS
  SELECT *
    FROM tc_new AS t
   WHERE NOT EXISTS (
     SELECT *
       FROM transitive_closures tc
      WHERE tc.x = t.x AND tc.y = t.y
   );

  INSERT INTO transitive_closures SELECT * FROM delta;

  DROP TABLE tc_new;
  DROP TABLE delta;

  RETURN NEW;
END
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS tr_graph_after_insert ON graph;

  CREATE TRIGGER tr_graph_after_insert AFTER INSERT
              ON graph
             FOR EACH ROW
EXECUTE FUNCTION fn_insert_transitive_closure();

CREATE OR REPLACE FUNCTION fn_delete_transitive_closure() RETURNS TRIGGER AS
$$
BEGIN
  CREATE TEMP TABLE IF NOT EXISTS suspect AS
  SELECT *
    FROM (SELECT tc1.x, tc2.y
            FROM transitive_closures AS tc1, transitive_closures AS tc2
           WHERE tc1.y = OLD.x AND tc2.x = OLD.y
          UNION SELECT x, OLD.y
                  FROM transitive_closures
                 WHERE y = OLD.x
          UNION SELECT OLD.x, y
                  FROM transitive_closures
                 WHERE x = OLD.y
          UNION SELECT OLD.x, OLD.y
         ) AS _;

  CREATE TEMP TABLE IF NOT EXISTS trusty AS
  SELECT *
    FROM (
      SELECT * FROM transitive_closures WHERE NOT EXISTS(
        SELECT *
          FROM suspect
         WHERE suspect.x = transitive_closures.x AND suspect.y = transitive_closures.y
                        )
      UNION SELECT graph.*
              FROM graph
             WHERE x <> OLD.x AND y <> OLD.y
         ) AS _;

  CREATE TEMP TABLE IF NOT EXISTS tc_new AS
  SELECT *
    FROM (SELECT * FROM trusty
          UNION SELECT t1.x, t2.y
                  FROM trusty t1, trusty t2
                  WHERE t1.y = t2.x
          UNION SELECT t1.x, t3.y
                  FROM trusty t1, trusty t2, trusty t3
                  WHERE t1.y = t2.x AND t2.y = t3.x
         ) AS _;

  DELETE FROM transitive_closures
        WHERE NOT EXISTS(
                    SELECT *
                      FROM tc_new AS t
                     WHERE t.x = transitive_closures.x AND t.y = transitive_closures.y
                  );

  DROP TABLE suspect;
  DROP TABLE trusty;
  DROP TABLE tc_new;

  RETURN OLD;
END
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS tr_graph_after_delete ON graph;

  CREATE TRIGGER tr_graph_after_delete AFTER DELETE
              ON graph
             FOR EACH ROW
EXECUTE FUNCTION fn_delete_transitive_closure();