Well, if your parent and child are going to be integers, then you can do some
magic with strings. (This is with the assumption that an edge can't go from and
to the same node)
Here's something to get the non-looping paths:
with recursive x (parent, path, child) as (
select parent, cast(parent as text) || ' => ' || cast(child as text), child
from edges
union
select x.parent, x.path || ' => ' || cast(edges.child as text), edges.child
from x
inner join edges on x.child = edges.parent
where x.path not like ('%' || cast(edges.child as text) || ' => %'))
select * from x;
...and after a bit of playing around, the loops...
with recursive x (parent, path, child) as (
select parent, cast(parent as text) || ' => ' || cast(child as text), child
from edges
union
select x.parent, x.path || ' => ' || cast(edges.child as text), edges.child
from x
inner join edges on x.child = edges.parent
where x.path not like ('%' || cast(x.child as text) || ' => %'))
select * from x where parent = child;
Let me know if those work ok for you.
-----Original Message-----
From: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] On
Behalf Of Shane Dev
Sent: Wednesday, December 20, 2017 4:32 PM
To: SQLite mailing list
Subject: [sqlite] How to detect cycles in a hierarchical table?
Hello,
I have an edges table -
sqlite> .sch edges
CREATE TABLE edges(parent, child);
sqlite> select * from edges;
parent child
1 2
1 3
2 4
3 1
4 5
5 2
Here we have two cycles -
1) 1 => 3 => 1 (length 1)
2) 2 => 4 => 5 => 2 (length 3)
Cycles cause recursive common table expression queries to become infinite
loops. Is there a query which can detect all cycles regardless of length?
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
