How to detect cycles in a hierarchical table?

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

How to detect cycles in a hierarchical table?

Shane Dev
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
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

David Raymond
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:[hidden email]] 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
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

Shane Dev
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 <[hidden email]>
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:[hidden email]]
> 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
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] How to detect cycles in a hierarchical table?

Hick Gunter
In reply to this post by Shane Dev
The most useles answer would be: Yes; run a recursive CTE query and if it does not terminate, then there are loops ;)

-----Urspr√ľngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Shane Dev
Gesendet: Mittwoch, 20. Dezember 2017 22:32
An: SQLite mailing list <[hidden email]>
Betreff: [EXTERNAL] [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
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

Lifepillar
In reply to this post by Shane Dev
On 20/12/2017 22:31, Shane Dev wrote:

> 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.
Maybe you could show an example of such queries? This:

   with recursive Visit(node) as (
     select parent from Edges where parent = 1
     union
     select child from Edges join Visit on parent = node
   )
   select node from Visit;

returns a finite result (note that use of 'union' rather than 'union
all').

Life.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

Lifepillar
In reply to this post by Shane Dev
On 20/12/2017 22:31, Shane Dev wrote:
> Is there a query which can detect all cycles regardless of length?

Not.. cough... particularly efficient, but simple:

with recursive Paths(s,t) as (
   select parent, child from Edges
   union
   select parent, t from Edges join Paths on child = s
)
select count(*) > 0 from Paths where s = t;

This finds all pairs of nodes reachable from each other,
then checks whether there are nodes reachable from themselves.
It returns 1 if there are cycles, 0 otherwise.

A better way would probably be to write a function that performs a
dfs.

Life.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

E.Pasma
In reply to this post by Lifepillar
Lifepillar wrote:

> On 20/12/2017 22:31, Shane Dev wrote:
>> 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.
> Maybe you could show an example of such queries? This:
>
>  with recursive Visit(node) as (
>    select parent from Edges where parent = 1
>    union
>    select child from Edges join Visit on parent = node
>  )
>  select node from Visit;
>
> returns a finite result (note that use of 'union' rather than 'union
> all').
>
> Life.

Brilliant. Now I see the difference between UNION and UNION ALL in  
recursion. It is documented as below. Although it needs careful  
reading to understand that UNION effectively eliminates loops.

https://www.sqlite.org/lang_with.html#recursivecte
If a UNION operator connects the initial-select with the recursive-
select, then only add rows to the queue if no identical row has been  
previously added to the queue. Repeated rows are discarded before  
being added to the queue even if the repeated rows have already been  
extracted from the queue by the recursion step. If the operator is  
UNION ALL, then all rows generated by both the initial-select and the  
recursive-select are always added to the queue even if they are  
repeats. When determining if a row is repeated, NULL values compare  
equal to one another and not equal to any other value.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

Shane Dev
In reply to this post by Lifepillar
I always followed the advice on https://sqlite.org/lang_with.html and use
UNION ALL in the compound select statement. This is why cycles trigger
infinite looping. In the case of my edges table, it does not make sense to
have cycles so my goal is to develop INSERT and UPDATE triggers that
prevent this possibility.

On 21 December 2017 at 12:11, Lifepillar <[hidden email]> wrote:

> On 20/12/2017 22:31, Shane Dev wrote:
>
>> 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.
>>
> Maybe you could show an example of such queries? This:
>
>   with recursive Visit(node) as (
>     select parent from Edges where parent = 1
>     union
>     select child from Edges join Visit on parent = node
>   )
>   select node from Visit;
>
> returns a finite result (note that use of 'union' rather than 'union
> all').
>
> Life.
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to detect cycles in a hierarchical table?

Lifepillar
In reply to this post by E.Pasma
On 21/12/2017 17:13, E.Pasma wrote:
> Now I see the difference between UNION and UNION ALL in
> recursion. It is documented as below. Although it needs careful reading
> to understand that UNION effectively eliminates loops.

Having a PostgreSQL background, I cannot recommend its SQL documentation
enough. The section on CTE explains how they are evaluated very well.
While it contains a few PostgreSQL-specific stuff (such as arrays), it
may be inspiring for users of other SQL products as well:

    https://www.postgresql.org/docs/current/static/queries-with.html

There are, in particular, specific examples on how to deal with cycles.

Life.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users