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
wrote:
> >>>Unless the recursion is circular, I don't see how an SQL query over
> >&
On Mon, 15 Jun 2015 11:03:17 +1000
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
>>>There are queries that cannot be formulated in first order predicate
logic, and recursion is the single capability of SQL that exceeds FOPL
power.
True, wrt SQLite and its dialect, for which RCTE provides Turing
Completeness. Untrue for dialects of SQL that include PSM.
>>>Unless the
>>>The task is to write some SQL code, including as many
INSERT/UPDATE/DELETEs as you want to make other tables with information
about the program, with a final SELECT which returns TRUE if and only if the
program will halt.
SQL with Recursive CTE is Turing Complete. The above is provably
On 14 Jun 2015, at 4:09pm, James K. Lowden wrote:
> Simon Slavin wrote:
>
>> There are plenty of queries which can be expressed in a SQL database
>> but can't be answered without a computer which can reprogram itself
>
> Are there? Do you mean there are SQL queries like that? Or do you
>
On Fri, 12 Jun 2015 01:45:50 +0100
Simon Slavin wrote:
> There are plenty of queries which can be expressed in a SQL database
> but can't be answered without a computer which can reprogram itself
Are there? Do you mean there are SQL queries like that? Or do you
mean there are such queries
linglists.sqlite.org
[mailto:sqlite-users-bounces at mailinglists.sqlite.org] On Behalf Of Igor
Tandetnik
Sent: Friday, 12 June 2015 1:49 PM
To: sqlite-users at mailinglists.sqlite.org
Subject: Re: [sqlite] Is recursive CTE fully capable?
On 6/11/2015 8:08 PM, david at andl.org wrote:
> The que
] Is recursive CTE fully capable?
On 12 Jun 2015, at 1:08am, david at andl.org wrote:
> The question I'm trying to ask is whether recursive CTE (either as
> defined in the standard or as implemented in SQLite) carries the full
> capability of evaluating recursive queries on appropr
On 12 Jun 2015, at 4:48am, Igor Tandetnik wrote:
> http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf
> "With CTE and Windowing, SQL is Turing Complete."
But SQLite doesn't have Windowing, right ? Or does it ?
Simon.
The question I'm trying to ask is whether recursive CTE (either as defined
in the standard or as implemented in SQLite) carries the full capability of
evaluating recursive queries on appropriate data structures, or are there
queries that are beyond what it can do?
As far as I can see recursive
On 6/12/2015 5:33 AM, Simon Slavin wrote:
>
> On 12 Jun 2015, at 4:48am, Igor Tandetnik wrote:
>
>> http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf
>> "With CTE and Windowing, SQL is Turing Complete."
>
> But SQLite doesn't have Windowing,
On 12 Jun 2015, at 1:08am, david at andl.org wrote:
> The question I'm trying to ask is whether recursive CTE (either as defined
> in the standard or as implemented in SQLite) carries the full capability of
> evaluating recursive queries on appropriate data structures, or are there
> queries
On 6/11/2015 8:08 PM, david at andl.org wrote:
> The question I'm trying to ask is whether recursive CTE (either as defined
> in the standard or as implemented in SQLite) carries the full capability of
> evaluating recursive queries on appropriate data structures, or are there
> queries that are
13 matches
Mail list logo
