Transitive Closure in SQL

A recursive query is one with the form:

WITH RECURSIVE
  under_alice(name,level) AS (
    VALUES('Alice',0)
    UNION ALL
    SELECT org.name, under_alice.level+1
      FROM org JOIN under_alice ON org.boss=under_alice.name
     ORDER BY 2 ASC
  )
SELECT substr('..........',1,level*3) || name FROM under_alice;

under_alice looks like a function that takes parameters, but it is not. What look to be parameters, are actually the column names of the return value, so org.name, under_alice.level+1 becomes under_alice.name, under_alice.level. The last SELECT statement just formats the result from under_alice. The under_alice query makes reference to the org table:

The SQLite article explains how recursive queries proceed. Stepping through that process with the under_alice query: When recursing, two tables are created, the recursive table and the queue. So stepping through the code: Initially VALUES('Alice',0) is stored in the queue, and the recursive table is empty. The part after the UNION ALL is the recursion loop. The statement, VALUES('Alice',0), does not get re-evaluated. In the first iteration, the top value from the queue is moved to the recursive table and it also becomes the value that under_alice refers to in the SELECT...FROM... statement. The org table gets joined with ('Alice',0) ON org.boss = 'Alice', and the table returned by the SELECT...FROM... statement gets stored at the bottom of the queue, resulting in the tables shown in step 1. The algorithm repeats, step 2, Bob is pulled from the queue and put into the recursive table, and the Bob record, ('Bob',1), gets joined with the org table. The result is then stored in the queue. This repeats until the queue is empty; which is only possible if the JOIN returns an empty table, which is does for Fred, Gail, Cindy, and Dave. Otherwise the query would loop infinitely. This query performs a breadth first search.

• Step 0

  Table 1: Queue

  Alice

  0

  The recursive table is empty.

• Step 1

  Table 2: Recursive Table

  Alice

  0

  Table 3: Queue

  Bob	1
  Cindy	1

• Step 2

  Table 4: Recursive Table

  Alice	0
  Bob	1

  Table 5: Queue

  Cindy	1
  Dave	2
  Emma	2

• Step 3

  Table 6: Recursive Table

  Alice	0
  Bob	1
  Cindy	1

  Table 7: Queue

  Dave	2
  Emma	2
  Fred	2
  Gail	2

• Step 4

  Table 8: Recursive Table

  Alice	0
  Bob	1
  Cindy	1
  Dave	2

  Table 9: Queue

  Emma	2
  Fred	2
  Gail	2

• Step 5

  Table 10: Recursive Table

  Alice	0
  Bob	1
  Cindy	1
  Dave	2
  Emma	2

  Table 11: Queue

  Fred	2
  Gail	2

• Step 6

  Table 12: Recursive Table

  Alice	0
  Bob	1
  Cindy	1
  Dave	2
  Emma	2
  Fred	2

  Table 13: Queue

  Gail

  2

• Step 7

  Table 14: Recursive Table

  Alice	0
  Bob	1
  Cindy	1
  Dave	2
  Emma	2
  Fred	2
  Gail	2

  The queue is empty.

The SQLite article also gives an example of depth first search.

WITH RECURSIVE
  under_alice(name,level) AS (
    VALUES('Alice',0)
    UNION ALL
    SELECT org.name, under_alice.level+1
      FROM org JOIN under_alice ON org.boss=under_alice.name
     ORDER BY 2 DESC
  )
SELECT substr('..........',1,level*3) || name FROM under_alice;

The ORDER BY number refers to the second column in the SELECT statement. The DESC means that elements get taken from the bottom of the queue instead of the top; that is, the queue acts as a stack.

• Step 0

  Table 15: Queue

  Alice

  0

  The recursive table is empty.

• Step 1

  Table 16: Recursive Table

  Alice

  0

  Table 17: Queue

  Bob	1
  Cindy	1

• Step 2

  Table 18: Recursive Table

  Alice	0
  Cindy	1

  Table 19: Queue

  Bob	1
  Fred	2
  Gail	2

• Step 3

  Table 20: Recursive Table

  Alice	0
  Cindy	1
  Gail	2

  Table 21: Queue

  Bob	1
  Fred	2

• Step 4

  Table 22: Recursive Table

  Alice	0
  Cindy	1
  Gail	2
  Fred	2

  Table 23: Queue

  Bob

  1

• Step 5

  Table 24: Recursive Table

  Alice	0
  Cindy	1
  Gail	2
  Fred	2
  Bob	1

  Table 25: Queue

  Dave	2
  Emma	2

• Step 6

  Table 26: Recursive Table

  Alice	0
  Cindy	1
  Gail	2
  Fred	2
  Bob	1
  Emma	2

  Table 27: Queue

  Dave

  2

• Step 7

  Table 28: Recursive Table

  Alice	0
  Cindy	1
  Gail	2
  Fred	2
  Bob	1
  Emma	2
  Dave	2

  The queue is empty.

In the previous examples, some of the row orderings were random. For example, in step 1, the row order of (Bob,1; Cindy,1) could have been reversed; so if determinism matters, you could sub-sort the recursive query: ORDER BY 2 DESC, 1 DESC.

The following Python code uses relational.py and Emacs Org mode. See my previous post in the thread for more on that.

import sys
sys.path.append("/home/devin/projects/relational/")
from relational.relation_org import RelationOrg
flights = RelationOrg(flights)
flight_ids = flights.projection("id")
# use Warshall's algorithm to compute indirect connections
flight_num = len(flights)

# add one-stop connections to the connections table
connections = flights.thetajoin(flights.rename({"id":"dest_id",
                                                "source":"source_d",
                                                "dest":"dest_d",
                                                "departs":"departs_d",
                                                "arrives":"arrives_d"}),
                                "dest == source_d and arrives <= departs_d")\
                     .projection("id", "dest_id").rename({"id":"source_id"})
connections_org = connections.rename({"source_id": "source_id_c",
                                      "dest_id": "dest_id_c"})

# store intermediate results, currently only have one-stop flight itineraries
itineraries = connections.thetajoin(connections.projection("source_id")\
                                    .rename({"source_id":"connection_id"}),
                                    "source_id == connection_id")
itineraries_org = itineraries.rename({"connection_id":"connection_id_n",
                                      "source_id":"source_id_n",
                                      "dest_id":"dest_id_n"})

if len(connections) > 0:
    i = 0
    while i < flight_num:
        # find secondary connections and remove known connections from
        # new_connections list so as to not insert existing connections,
        connections = connections.thetajoin(connections_org,
                                            "dest_id == source_id_c")\
                                 .projection("source_id", "dest_id_c")\
                                 .rename({"dest_id_c":"dest_id"})\
                                 .union(connections)

        # add connections to the itineraries table
        itineraries = itineraries.thetajoin(itineraries_org,\
                                            "dest_id == source_id_n")\
                                 .projection("dest_id", "dest_id_n", "connection_id")\
                                 .rename({"dest_id": "source_id", "dest_id_n":"dest_id"})\
                                 .union(itineraries)
        i += 1

result = flights.product(flights.rename({"id":"dest_id",
                                         "source":"source_d",
                                         "dest":"dest_d",
                                         "departs":"departs_d",
                                         "arrives":"arrives_d"}))\
         .rename({"id":"source_id"})\
         .semijoin_left(connections)\
         .projection("source_id", "dest_id", "source", "dest_d", "departs", "arrives_d")
#return str(RelationOrg(connections))
#return str(RelationOrg(itineraries))
return str(RelationOrg(result))

flights refers to the before mentioned flights table. Initially, the connections variable is a two-column, many-to-many relation table describing possible one-stop connections between source_id and dest_id. The itineraries variable adds an extra column, connection_id, to the connections table, that being the starting connection ID. The code only needs to iterate N times because the two inner loops are accomplished by the thetajoin. Renaming is necessary because thetajoin does not allow for duplicate column names. Intermediate results are aggregated into the connections and itineraries variables by UNION-ing the known connections with the new found connections. The only difference between connections and itineraries is that the source_id is projected in the former, while the dest_id is projected in the later. The result variable shows the flight information associated with the entries in the connections table. It is created by computing all possible connections between nodes and keeping only those connections that exist in the connections table, joining on dest_id and source_id.

Given example table

CREATE TABLE Flights (
       id NUMBER,
       source TEXT(2),
       dest TEXT(2),
       departs NUMBER,
       arrives NUMBER,
       CONSTRAINT FlightsPK PRIMARY KEY (id)
);
INSERT INTO Flights(id, source, dest, departs, arrives) VALUES (0, 'A', 'B', 0, 1);
INSERT INTO Flights(id, source, dest, departs, arrives) VALUES (1, 'A', 'B', 3, 4);
INSERT INTO Flights(id, source, dest, departs, arrives) VALUES (2, 'B', 'C', 0, 1);
INSERT INTO Flights(id, source, dest, departs, arrives) VALUES (3, 'B', 'C', 3, 4);
INSERT INTO Flights(id, source, dest, departs, arrives) VALUES (4, 'C', 'D', 4, 5);
INSERT INTO Flights(id, source, dest, departs, arrives) VALUES (5, 'D', 'E', 5, 6);

the transitive closure and itineraries can be generated by using recursive CTEs. The following code returns the transitive closure.

WITH RECURSIVE
connections(source_id, dest_id) AS (
                   SELECT DISTINCT S.id, D.id
                   FROM flights AS S JOIN flights AS D
                   ON S.dest = D.source AND S.arrives <= D.departs
),

iterations(x) AS (
              SELECT COUNT(*) FROM Flights
),

trans_closure(source_id, dest_id) AS (
                   SELECT source_id, dest_id FROM connections
                   UNION ALL
                   SELECT A.source_id, B.dest_id
                   FROM trans_closure AS A JOIN connections AS B
                   ON A.dest_id = B.source_id
                   LIMIT (SELECT (SELECT x FROM iterations) * (SELECT x FROM iterations))
)
SELECT source_id, dest_id FROM trans_closure ORDER BY 1,2;

The connections function is just a regular CTE that results in a table of one-stop connections. iterations caches the Flight table length. The trans_closure CTE is recursive. The SELECT statement before the UNION ALL creates a table that the recursive operation, the code after the UNION ALL, iterates through. The table connections has the value

The table is copied into a queue. One of the rows is extracted from the queue and inserted into trans_closure's table. The trans_closure table is joined with the connections table ON A.dest_id = B.source_id and the result is added to the queue. The number of recursions is limited to the square of the Flights table length. The LIMIT is not strictly needed in this example because the Flights table is not circular.

A list of all itineraries can be produced by:

WITH RECURSIVE
itineraries(id, source_id, connection_id) AS
(
        SELECT DISTINCT S.id, S.id, D.id
        FROM flights AS S JOIN flights AS D
        ON S.dest = D.source AND S.arrives <= D.departs
),

sub_graphs(id, source_id, connection_id) AS
(
        SELECT id, source_id, connection_id FROM itineraries
        UNION ALL
        SELECT A.id, A.connection_id, B.connection_id
        FROM sub_graphs AS A JOIN itineraries AS B
        ON A.connection_id = B.source_id
)
SELECT DISTINCT id, source_id, connection_id FROM sub_graphs ORDER BY 1,2,3;

There are only minor differences between this code and the transitive closure query. itineraries is like connections in the previous example, except the first node is used to group itinerary parts together. In the recursive query, the JOIN ON is the same, dest_id is renamed connection_id (This was done to be consistent with the relational algebra example, and it was done there to avoid naming collisions.), and the fields returned is changed.

If the Flights table were cyclic, the recursive queries would require a limit or an iterator. Unlike the relational algebra example, where the entire intermediate result was joined with the entire original table, this query is joining one of the intermediate results with the original table, so loops are needed. The iterative version has the advantage of being order-able. The ORDER BY clause requires a numeric field to sort on. This controls whether the queue virtual table is treated as a stack or a queue.

WITH RECURSIVE
connections(source_id, dest_id) AS (
     SELECT DISTINCT S.id, D.id
     FROM flights AS S JOIN flights AS D
     ON S.dest = D.source AND S.arrives <= D.departs
),

iterations(x) AS (
SELECT COUNT(*) FROM Flights
),

trans_closure(itter, source_id, dest_id) AS (
     SELECT 0, source_id, dest_id FROM connections
     UNION ALL
     SELECT itter + 1, A.source_id, B.dest_id
     FROM trans_closure AS A JOIN connections AS B
     ON A.dest_id = B.source_id
     WHERE itter < (SELECT (SELECT x FROM iterations) * (SELECT x FROM iterations))
     ORDER BY 1 ASC
)
SELECT DISTINCT source_id, dest_id FROM trans_closure ORDER BY 1,2;