SQL query for topological sort

Question

I have a directed acyclic graph:

DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);

I want to list all nodes, always listing a to node before its from node. For example: 2, 3, 4, 1, 5.

It is also called a topological ordering. How can it be done in SQL ?

Answer 1

I needed a topological sort for a SQLite application and the following works for SQLite 3.37.0, using @Tomáš's code and data. In SQLite, DISTINCT works within a recursive CTE. I have added an additional dependency between his nodes 'C' and 'F' to make things a little more interesting, but it works the same without this edge.

I need to determine the order of processing entities in a dependency management system, similar to @Ludovic's need, so I changed the sorting order to DESC so the first item returned is the first item to process.

DROP TABLE IF EXISTS edges;
CREATE TABLE edges(from_node int, to_node int);
INSERT INTO edges VALUES ('A','B'),('A','C'),('B','D'),('C','D')
                       , ('D','E'),('D','F'),('E','G'),('F','G')
                       , ('C','F');
with recursive cte as (
      select distinct 0 as from_node, e.from_node as to_node, 1 as lev
      from edges e
      where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
      union all
      select e.from_node, e.to_node, lev + 1
      from cte join
           edges e
           on e.from_node = cte.to_node
     )
select to_node, max(lev) from cte group by to_node order by max(lev) desc
;

Result:

to_node  max(lev)
-------  --------
G        5       
F        4       
E        4       
D        3       
C        2       
B        2       
A        1

Answer 2

I found this question running into similar problem. Since both @Ludovic's and @Gordon's answers didn't fully answered all my particular questions and there's not enough room in comments I decided to summarize my own answer.

Recursive query solution is good

Basically, @Gordon's answer is based on graph traversal of all paths. The cte.lev column actually represents length of path from some start node to cte.to_node.

What about loops?

What's not clear is what to return when multiple paths into particular node are possible (i.e. if the undirected version of DAG had loops). For example in following graph

1
^
|\
2 \
^ /
|/
3

the node 1 is reachable from initial node 3 at distance 1 directly and at distance 2 via node 2. Hence the node 1 is expanded twice with different value of path length.

Let v be the greatest value of the two. The v can generally be defined as length of the longest path from start node to given node. This value corresponds with topological ordering. It essentially splits nodes into chunks so that for any two nodes n1, n2 with values v1, v2 respectively, the node n1 is before n2 when v1<v2 and ordering of n1,n2 is arbitrary when v1=v2. (I have no exact proof but by contradiction if this ordering wouldn't hold there would have to be counter-directed edge or edge within chunk so the value v wouldn't be the length of the longest path.)

Hence the SQL is (original example fiddle, my looped example fiddle)

with cte as (
      select 0 as from_node, e.from_node as to_node, 1 as lev
      from edges e
      where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
      union all
      select e.from_node, e.to_node, lev + 1
      from cte join
           edges e
           on e.from_node = cte.to_node
     )
select to_node, max(lev)
from cte
group by to_node
order by max(lev)

(which is close to @Ludovic's answer but Ludovic relies on ordering by id which IMHO cannot guarantee the proper ordering in general case.

Optimization

The recursive CTE now generates rows with to_node and length of the path to it. If some node was reached by multiple paths of same length, each of that paths expands to new rows at another level of recursion, which generates duplicate rows and for some graphs it can lead to combinatorial explosion. For example in following graph (let the edges be directed from left to right)

  B   E
 / \ / \
A   D   G
 \ / \ /
  C   F

the D node is reached from A via two paths but algorithm does not take it into consideration hence E has two paths as well as F, G has even four paths.

For SQL-based solution in ideal world, adding distinct would suffice, which would eliminate duplicate expansion of D-E and D-F edges:

select distinct 0 as from_node, e.from_node as to_node, 1 as lev
from edges e
where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
union all
select distinct e.from_node, e.to_node, lev + 1
from cte join
     edges e
     on e.from_node = cte.to_node

Unfortunately this doesn't work because of DISTINCT operator is not allowed in the recursive part of a recursive common table expression 'cte'. error in SQLServer. (I actually work with Oracle where the result is analogous - ORA-32486 unsupported operation in recursive branch of recursive WITH clause.) Similarly neither the group by nor some query nesting tricks can be used.

In this point I gave up with SQLServer but for Oracle there exists one more solution based on window functions. In the recursive part of query it is possible to define bunch of duplicate rows as a partition, number rows within that partition and choose only one of potentially many duplicates.

with edges (from_node,to_node) as ( 
select 'A','B' from dual union all 
select 'A','C' from dual union all 
select 'B','D' from dual union all 
select 'C','D' from dual union all 
select 'D','E' from dual union all 
select 'D','F' from dual union all 
select 'E','G' from dual union all 
select 'F','G' from dual
)
, cte (from_node, to_node, lev, dup) as (
  select distinct null as from_node, e.from_node as to_node, 0 as lev, 1 as dup
  from edges e
  where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
  union all
  select e.from_node, e.to_node, cte.lev + 1
    , row_number() over (partition by e.to_node, cte.lev order by null) as dup
  from cte
  join edges e on e.from_node = cte.to_node
  where cte.dup = 1
)
select to_node, lev from cte where dup = 1 order by lev 

The drawback is that the row_number of current level of recursion cannot be filtered in where condition. Hence we must stand that duplicate rows pass and expand into next level of recursion where they are finally pruned. However this heuristics is still useful - I was querying the Oracle dba_dependencies table and the query didn't terminate at all without it.

I didn't found the way to make this small trick work in SQLServer since SQLServer handles window function in recursive queries differently. Sorry for messing question with Oracle issues but I consider this topic interesting for anyone who finds this question.