e.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
wrote:
> >>>Unless the recursion is circular, I don't see how an SQL query o
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 not
>>>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 recursi
>>>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 impossib
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
> me
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 that
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 questi
sqlite] 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 que
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 CTE
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, ri
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 that
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 be
13 matches
Mail list logo