A recursive function contains a computation and a decision: whether to terminate or go deeper. Any recursive function/query will fail to terminate if the termination condition is not satisfied.
Here are two similar CTEs. The first terminates, the second does not. WITH RECURSIVE cnt(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM cnt WHERE x<1000000) SELECT x FROM cnt; WITH RECURSIVE cnt(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM cnt WHERE x>0) SELECT x FROM cnt; A recursive query on DAG data will still not terminate if the recursive part of the query keeps returning the same results instead of advancing through the data. Of course that would not be a 'correct query'. Regards David M Bennett FACS Andl - A New Database Language - andl.org -----Original Message----- From: sqlite-users-boun...@mailinglists.sqlite.org [mailto:sqlite-users-bounces at mailinglists.sqlite.org] On Behalf Of James K. Lowden Sent: Wednesday, 17 June 2015 4:45 AM To: General Discussion of SQLite Database Subject: Re: [sqlite] Is recursive CTE fully capable? On Mon, 15 Jun 2015 11:03:17 +1000 <david at andl.org> wrote: > >>>Unless the recursion is circular, I don't see how an SQL query over > >>>a finite database could fail to terminate. > > What does this mean? It is trivial to write a recursive CTE that does > not terminate, and the property of "circularity" is not what makes the > difference. Hmm, for a correctly written recursive query not to terminate, is it not a requirement that the data contain a cycle? I can't prove it, but no counterexample springs to mind. In the positive: a correct recursive query always terminates if the data represent a directed acyclic graph. By "correct" I mean the CTE expresses a recursive relation. If you recurse over with R (a, b) as (select 1 as a, 1 as b) you have no right to expect termination. But you might be able to fry an egg on the processor. --jkl _______________________________________________ sqlite-users mailing list sqlite-users at mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
