Transitive Closure of Acyclic Graphs [Original]

transitive_closures_1999.sql

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

-- 2) Transitive Closure of Acyclic Graphs

-- Maintenance Under Insertion

-- Insertion of edge (a, b).

   SELECT *
     FROM (SELECT Start = TC.Start, End = b
             FROM TC
            WHERE TC.End = a
           UNION SELECT Start = a, End = TC.End
                   FROM TC
                  WHERE b = TC.Start
           UNION SELECT Start = TC1.Start, End = TC2.End
                   FROM TC AS TC1, TC AS TC2
                  WHERE TC1.End = a AND TC2.Start = b
          ) AS T
INTO TEMP TC-NEW;

INSERT INTO TC-NEW (Start, End)
     VALUES (a, b);

SELECT *
  FROM TC-NEW AS T
 WHERE NOT EXISTS (
   SELECT *
     FROM TC
    WHERE TC.Start = T.Start AND TC.End = T.End
 )
INTO TEMP DELTA;

INSERT INTO TC SELECT * FROM DELTA;

-- Maintenance Under Deletions

-- Step 1: Finding the suspects

SELECT *
  FROM (SELECT Start = X.Start, End = Y.End
          FROM TC AS X, TC AS Y
         WHERE X.End = a AND Y.Start = b
        UNION SELECT Start = X.Start, End = b
                FROM TC AS X
               WHERE X.End = a
        UNION SELECT Start = a, End = X.End
                FROM TC AS X
               WHERE X.Start = b
        UNION SELECT Start = a, End = b
                FROM TC AS X
                WHERE X.Start = a AND X.End = b
       )
INTO TEMP SUSPECT;

-- Step 2: Finding the trusty guys

SELECT *
  FROM (
    SELECT *
      FROM TC
     WHERE NOT EXISTS (
      SELECT *
        FROM SUSPECT
       WHERE SUSPECT.Start = TC.Start AND SUSPECT.End = TC.End
                      )
    UNION SELECT *
            FROM G
           WHERE G.Start <> a AND G.End <> b
       )
INTO TEMP TRUSTY;

-- Step 3: Deleting the bad guys

SELECT *
  FROM (SELECT *
          FROM TRUSTY
        UNION SELECT T1.Start, T2.End
                FROM TRUSTY T1, TRUSTY T2
                WHERE T1.End = T2.Start
        UNION SELECT T1.Start, T3.End
                FROM TRUSTY T1, TRUSTY T2, TRUSTY T3
                WHERE T1.End = T2.Start AND T2.End = T3.Start
       )
INTO TEMP TC-NEW;

DELETE FROM TC
      WHERE NOT EXISTS (SELECT * FROM TC-NEW T WHERE T.Start = TC.Start AND T.End = TC.End);