Recursive Queries

Users
12

I found a tiny toy self-contained SQL that can be used with SQLite3. It illustrates the primary requirements for recursion: level (or depth) number, path generation, and cycle detection. Here is the output:

level|parent|node|path      |cyclic_flag
0    |     A|   B|/A/B      |0
1    |     B|   C|/A/B/C    |0
2    |     C|   D|/A/B/C/D  |0
3    |     D|   A|/A/B/C/D/A|1

You can just paste this SQL into SQLite3 to get above output:

with dataset as
(
select 'A' as parent, 'B' as node union all
select 'B' as parent, 'C' as node union all
select 'C' as parent, 'D' as node union all 
select 'D' as parent, 'A' as node
),
hierarchy( level, parent, node, path, cyclic_flag )
as
(
select 0 as level,
dataset.parent,
dataset.node,
'/' || dataset.parent || '/' || dataset.node as path,
0 as cyclic_flag
from dataset
where dataset.parent = 'A'

union all
select
hierarchy.level + 1 as level,
dataset.parent,
dataset.node,
hierarchy.path || '/' || dataset.node as path,
case
when
(length(path||dataset.node) - length(replace(path|| dataset.node,dataset.node,'')))/length(dataset.node) = 1
then 0
else 1
end as cyclic_flag
from hierarchy
inner join dataset
on dataset.parent = hierarchy.node
where (length(path) - length(replace(path,hierarchy.node,'')))/length(hierarchy.node) < 2
)
select *
from hierarchy

order by path
;

Hope to spend some time next on testing this with your tip changes. This toy example can be a functionality test. I’ll work up a larger dataset for a performance test.

Since I don’t know much about DGraph yet, I need to spend some serious time with your tutorials and documentation before I can get far on my own.

Thanks for your responsiveness!
Cecil