Hi David,
Yes, parent and child are integers. I hadn't thought of building a string
path, very clever. After a little testing, I have not found a case where
the queries fail.
On 20 December 2017 at 23:18, David Raymond <david.raym...@tomtom.com>
wrote:
> 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
>
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
