[sqlite] Is recursive CTE fully capable?

[da...@andl.org]

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<100)
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
 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

[sqlite] Is recursive CTE fully capable?

[James K. Lowden]

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 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] Is recursive CTE fully capable?

[da...@andl.org]

>>>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 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.

Regards
David M Bennett FACS

Andl - A New Database Language - andl.org

[sqlite] Is recursive CTE fully capable?

[da...@andl.org]

>>>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 impossible.
But then you already knew that.

Regards
David M Bennett FACS

Andl - A New Database Language - andl.org

[sqlite] Is recursive CTE fully capable?

[Simon Slavin]

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
> mean there are such queries that could be asked of a relational database
> but cannot be expressed in SQL?

I was a little loose in my language.  There are queries which can be expressed 
in terms of tables of rows of columns, with numbers and text in them.  E.g

"Jane is four years old, Derek was twice Jane's age last time there was a 
Winter Olympics.  If Derek's dog is white with black spots how much does Jane's 
mother earn per year ?"

There are some queries where you can figure out a schema to store data to 
express the situation, but you can't figure out any combination of database 
massaging commands (INSERT/UPDATE/DELETE) and a final SELECT that will fetch 
the answer you want.

> There are queries that cannot be formulated in first order predicate
> logic, and recursion is the single capability of SQL that exceeds
> FOPL power.  Unless the recursion is circular, I don't see how an SQL
> query over a finite database could fail to terminate.

The Termination Problem is not about whether a SQL query terminates, but 
whether a program in another language terminates.  Suppose you have a TABLE of 
lines of a program in your favourite toy programming language: row 1 of the 
table is line 1 of the program, row 2 of the table is line 2 of the program, 
etc..  The programming language can be any reasonably complicated one.  BASIC, 
PASCAL, Java, JavaScript, whatever.

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.

Simon.

[sqlite] Is recursive CTE fully capable?

[James K. Lowden]

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 could be asked of a relational database
but cannot be expressed in SQL?  

There are queries that cannot be formulated in first order predicate
logic, and recursion is the single capability of SQL that exceeds
FOPL power.  Unless the recursion is circular, I don't see how an SQL
query over a finite database could fail to terminate.  

--jkl

[sqlite] Is recursive CTE fully capable?

[da...@andl.org]

Interesting.

SQL has been Turing complete since PSM was added to the 1992 standard. (Not
SQLite). I guess they mean "Turing complete with respect to the relation
datatype".

Andl already supports windowing (but not on SQLite). The Andl implementation
of recursion queries is nearly done.

I read the paper. It should provide a good source of sample queries for
Andl. However, I was not impressed by the "proof". Maybe you had to be
there.

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 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 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?

http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20Po
stgreSQL%20Presentation.pdf
"With CTE and Windowing, SQL is Turing Complete."

--
Igor Tandetnik

___
sqlite-users mailing list
sqlite-users at mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Is recursive CTE fully capable?

[da...@andl.org]

Appropriate just means: set up the data structures any way you like in order
to capture the right info and support suitable queries.

I'm not trying to find a shortcut to solving NP complete problems. If I did,
I probably wouldn't post it here.

The question is: are there problems for which:
a) a recursive description and/or recursive data structure are a good match
b) interesting and/or useful queries can be formulated
c) those queries can be solved by general recursive solutions in other
programming languages
d) cannot be solved by the recursion provided by SQL CTE, because of
inherent limitations in the model/algorithm it supports?

There are lots of interesting things you can do with graphs (including
trees, lists, DAGs etc) including creating them, navigating them, modifying
them and measuring them. How far does this particular tool get you?

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 Simon
Slavin
Sent: Friday, 12 June 2015 10:46 AM
To: General Discussion of SQLite Database
Subject: Re: [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 queries on appropriate data 
> structures, or are there queries that are beyond what it can do?

I think your question can only be answered with "What you mean by
"appropriate" ?".  CTE is part of the 1999 SQL standard and as good a way as
any to implement directed graphs in SQL.

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, e.g. The
Halting Problem

<http://en.wikipedia.org/wiki/Halting_problem>

or without a ridiculously long processing time, e.g. The Travelling Salesman
Problem

<http://en.wikipedia.org/wiki/Travelling_salesman_problem>

.  CTE is only one type of meta-programming and is not all-powerful.

Simon.
___
sqlite-users mailing list
sqlite-users at mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Is recursive CTE fully capable?

[Simon Slavin]

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.

[sqlite] Is recursive CTE fully capable?

[da...@andl.org]

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 is very similar in capability (and
algorithm) to tail recursion. It's generally possible to code any loop and
most ordinary recursive functions in terms of tail recursion, which results
in highly efficient implementation. I'm interested to know where the limits
are, and what queries (if any) are beyond using this method.

If there is an academic paper or other reference that provides the answer
I'm happy to be pointed to that.

Regards
David M Bennett FACS

Andl - A New Database Language - andl.org

[sqlite] Is recursive CTE fully capable?

[Igor Tandetnik]

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, right ?  Or does it ?

Not to my knowledge.
-- 
Igor Tandetnik

[sqlite] Is recursive CTE fully capable?

[Simon Slavin]

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 are beyond what it can do?

I think your question can only be answered with "What you mean by "appropriate" 
?".  CTE is part of the 1999 SQL standard and as good a way as any to implement 
directed graphs in SQL.

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, e.g. The Halting 
Problem



or without a ridiculously long processing time, e.g. The Travelling Salesman 
Problem



.  CTE is only one type of meta-programming and is not all-powerful.

Simon.

[sqlite] Is recursive CTE fully capable?

[Igor Tandetnik]

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 beyond what it can do?

http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf
"With CTE and Windowing, SQL is Turing Complete."

-- 
Igor Tandetnik