PostgreSQL Question posted in
The official documentation can be found here.

Postgresql – How to get the complete path with CTE

I have a table like below:

ID NextID
1 5
2 NULL
3 6
4 7
5 8
6 9
7 NULL
8 NULL
9 10
10 NULL

I want to get the ID path:

1 --> 5 --> 8
2
3 --> 6 --> 9 --> 10
4 --> 7

and I tried this:

WITH RECURSIVE path_cte AS (
  SELECT ID, NextID, ID::TEXT AS Path
  FROM t1
  WHERE NextID IS NULL
  UNION ALL
  SELECT t1.ID, t1.NextID, t1.ID || ' --> ' || cte.Path
  FROM t1
  JOIN path_cte cte ON t1.NextID = cte.ID
)
SELECT Path
FROM path_cte
ORDER BY ID;

but I got the output:

1 --> 5 --> 8
2
3 --> 6 --> 9 --> 10
4 --> 7
5 --> 8
6 --> 9 --> 10
7
8
9 --> 10
10

I don’t want to get those incomplete paths, but I don’t know how to achieve that.

The path is based on ID and NextID, if NextID is NULL, the path ends, and this ID is the end of the path, the next is to trace forward to get a complete path.

If an ID has neither a preceding ID nor a subsequent ID, it is also considered a path.

The database I use is compatible with PostgreSQL syntax, so you can also use PostgreSQL to demo, thanks 🙂

Tags:

3

Answers


  1. 0 
    WITH RECURSIVE path_cte AS (
    -- Start with paths that end at NULL (leaves)
    SELECT ID, NextID, ID::TEXT AS Path
    FROM t1
    WHERE NextID IS NULL
  
    UNION ALL

    -- Recursively build the paths
    SELECT t1.ID, t1.NextID, t1.NextID::TEXT || ' --> ' || cte.Path
    FROM t1
    JOIN path_cte cte ON t1.ID = cte.NextID
)
SELECT DISTINCT Path
FROM path_cte
WHERE NOT EXISTS (
    SELECT 1
    FROM t1 t2
    WHERE t2.NextID = path_cte.ID  -- Check if there are children/next IDs
)
ORDER BY MIN(ID);  -- Order by the minimum ID in each path

    I hope it can help you

    Login or Signup to reply.
  2. 0

    Based on your explanation that both columns are unique, meaning another row like for example ID 11 and NextID 6 is not possible, you want to exclude all paths that are part of another part. This can be done using a NOT EXISTS subquery:

    WITH RECURSIVE path_cte AS (
  SELECT ID, NextID, ID::TEXT AS Path
  FROM t1
  WHERE NextID IS NULL
  UNION ALL
  SELECT t1.ID, t1.NextID, t1.ID || ' --> ' || cte.Path
  FROM t1
  JOIN path_cte cte ON t1.NextID = cte.ID
)
SELECT path
FROM path_cte p_main
WHERE 
NOT EXISTS (
   SELECT 1 FROM path_cte p_sub 
   WHERE 
     p_main.id <> p_sub.id AND
     p_sub.path LIKE '%' || p_main.path || '%')
ORDER BY p_main.ID;

    This produces following result:

    path
    1 –> 5 –> 8
    2
    3 –> 6 –> 9 –> 10
    4 –> 7

    See this db<>fiddle with your sample data.

    Login or Signup to reply.
  3. 0

    This can be solved by augmenting the query with FirstID and Lvl. Then select distinct FirstID sorted by the longest path length (Lvl).

    WITH RECURSIVE path_cte AS (
  SELECT ID, ID::TEXT AS Path, ID AS FirstID, 1 as Lvl
  FROM t1
  WHERE NextID IS NULL
  UNION ALL
  SELECT t1.ID, t1.ID || ' --> ' || cte.Path, cte.FirstId, cte.Lvl + 1
  FROM t1
  JOIN path_cte cte ON t1.NextID = cte.ID
)
SELECT Path from (
  SELECT DISTINCT ON (FirstID) *
  FROM path_cte
  ORDER BY FirstID, Lvl Desc
 ) ORDER BY ID
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search