How to write recursive query for path generation and cycle detection?

Question

I'm working with hierarchical tree data in DolphinDB and need to solve two specific programming challenges:

• Generate full paths (concatenated IDs and names) for all nodes, including infinite-level leaf nodes.
• Detect cyclic references (e.g., A → B → A).

In MySQL, I've successfully achieved this using recursive CTEs：

with recursive at as(
SELECT id, name,json_array(id) as path_id,json_array(name) as path_name,false as cycle
FROM table1
where pid is null and dir_group = 4
union ALL
SELECT t1.id, t1.name,JSON_MERGE_PRESERVE(at.path_id,json_array(t1.id)) as path_id ,
JSON_MERGE_PRESERVE(at.path_name,json_array(t1.name)) as path_name ,
json_contains(at.path_id,json_array(t1.id)) as cycle
FROM table1 t1 join at on t1.pid=at.id
where t1.pid is not null and not at.cycle)
select * from at

But I'm struggling to find an equivalent approach in DolphinDB. I've tried an iterative approach using loops and temporary tables:

// Sample table structure (adjust columns as needed)
nodes = table(1:0, `id`name`pid, [INT,STRING,INT])

// Initialize result table
result = table(1:0, `id`name`path`isCycle, [INT,STRING,STRING,BOOL])

// Initialize stack (using table)
stack = select id, name, string(id) as path from nodes where pid = NULL

while(size(stack) > 0) {
    // Pop last entry (stack behavior)
    current = select * from stack limit -1
    stack = select * from stack limit size(stack)-1

    // Detect cycles
    pathParts = split(current.path, ",")
    isCycle = sum(pathParts == string(current.id)) > 1

    // Store result
    result.append!(select id, name, path, isCycle from current)

    // Push children (reverse order for DFS)
    children = lj(nodes, current, `pid == `id)
    children = select * from children order by id desc  // Reverse for DFS
    stack.append!(select id, name, path + "," + string(id) from children)
}

The iterative approach works for small datasets but fails with deep hierarchies due to performance issues.

Also, I've explored built-in functions like ploop, each, and accumulate, but they don't natively support recursive state passing.

Are there recommended patterns in DolphinDB for recursive hierarchical queries? Or, does DolphinDB have any built-in functions specifically designed for hierarchical data traversal?

My Enviroment:

• DolphinDB version: 3.00.2
• Dataset size: About 1,000,000 rows

Answer 1

You can use DolphinDB's reduce function to implement recursive logic. The reference script is as follows:

step1: mock some data to test.

// Create an example table t containing nodeID, nodeName, and parentID
t = table(1..7 as nodeID,`a1`a2`a3`a4`a5`a6`a7 as nodeName, 0 1 1 2 2 3 3 as parentID)

step2：use inner join to join parent node and child node. Format the output path string like "nodeID1 -> nodeID2 -> nodeID3..." and "nodeName1 -> nodeName2 -> nodeName3...".

// Define the recursive function getchildnode to fetch child nodes and build paths
// t1 is the origin table and t is one of the parent node starting from root. 
def getchildnode(t1,t): 
    select * from t1 
    union 
    select t.nodeID, t.nodeName, t1.pathid + "->" + string(t.nodeID) as pathid, t1.pathname + "->" + t.nodeName as pathname 
    from ej(t1,t,`nodeID,`parentID)

step3：Find the root node.

// Initialize the root node table t1 by selecting nodes with parentID=0 as starting points
t1 = select nodeID, nodeName, string(nodeID) as pathid, nodeName as pathname from t where parentID=0

step4: Use the reduce function to recursively call getchildnode and traverse all levels.

reduce(getchildnode{,t}, t.size(), t1)