Cyclic detection in recursive queries

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Cyclic detection in recursive queries

New, Cecil (GE Aviation, US)
The best I have been able to come with is documented at:
http://stackoverflow.com/questions/32640043/cannot-detect-cyclic-data-in-an-sqlite-database/32719216#32719216

But a) it is ugly, b) performance impact of all the length(), replace() functions, c) if values end in similar strings, it probably won't work.

After some thought, I think the minimum that would solve this problem is to enhance the instr() function to either take a starting position to begin the search or to take an occurrence number to search for. Oracle's version of instr() does both of these (see https://docs.oracle.com/cd/B28359_01/olap.111/b28126/dml_functions_1103.htm)

Postgresql has a specific way of detecting loops, which would be even more robust. It is documented here:
https://www.postgresql.org/docs/9.1/static/queries-with.html


_______________________________________________
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: Cyclic detection in recursive queries

Richard Hipp-3
On 7/12/16, New, Cecil (GE Aviation, US) <[hidden email]> wrote:
> The best I have been able to come with is documented at:
> http://stackoverflow.com/questions/32640043/cannot-detect-cyclic-data-in-an-sqlite-database/32719216#32719216\

So you have a graph with loops.  What is your problem, though?  Do you
merely want to detect the loops?  Or are you trying to query the graph
without getting stuck chasing loops around and around?



> Postgresql has a specific way of detecting loops, which would be even more
> robust. It is documented here:
> https://www.postgresql.org/docs/9.1/static/queries-with.html

That's a long document.  Can you be more specific about what loop
detection mechanism of PostgreSQL you have in mind?

--
D. Richard Hipp
[hidden email]
_______________________________________________
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: Cyclic detection in recursive queries

Jean-Luc Hainaut
In reply to this post by New, Cecil (GE Aviation, US)
On 12/07/2016 13:59, New, Cecil (GE Aviation, US) wrote:
> The best I have been able to come with is documented at:
> http://stackoverflow.com/questions/32640043/cannot-detect-cyclic-data-in-an-sqlite-database/32719216#32719216
>
> But a) it is ugly, b) performance impact of all the length(), replace() functions, c) if values end in similar strings, it probably won't work.
>
> After some thought, I think the minimum that would solve this problem is to enhance the instr() function to either take a starting position to begin the search or to take an occurrence number to search for. Oracle's version of instr() does both of these (see https://docs.oracle.com/cd/B28359_01/olap.111/b28126/dml_functions_1103.htm)
>
> Postgresql has a specific way of detecting loops, which would be even more robust. It is documented here:
> https://www.postgresql.org/docs/9.1/static/queries-with.html
Three suggestions to solve this problem are described in Section 24.4 of
the following document:

https://staff.info.unamur.be/dbm/Documents/Tutorials/SQLfast/SQLfast-Tuto24-Recursive-programming.pdf

Recursive triggers can be used as well (see Section 24.7).

J-L Hainaut

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