Hello,

I'm curious as to SQL with Common Table Expressions is Turing
Complete. Is there some kind of proof either way?

Thanks in advance for any hints, tips, pointers, etc. on this.

Cheers,
David.
--
David Fetter <david (AT) fetter (DOT) org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter (AT) gmail (DOT) com

There is nothing more difficult to take in hand, more perilous to
conduct, or more uncertain in its success, than to take the lead in
the introduction of a new order of things. Because the innovator has
for enemies all those who have done well under the old conditions, and
lukewarm defenders in those who may do well under the new.
Niccolo Machiavelli
The Prince, 1513

On May 4, 1:13*pm, da... (AT) fetter (DOT) org (David Fetter) wrote:
What allowed in CTE expression is critical. If recursion is linear and
no subqueries are allowed, then showing that basic SQL (select+project
+join+union+CTE) might be tough. Otherwise, one can approach the
problem by simulating a known turing complete cellular automaton (such
as rule 110).

Tegiri Nenashi <TegiriNenashi (AT) gmail (DOT) com> wrote:
As opposed to mutual recursion?

Where would they be disallowed?

Cheers,
David.
--
David Fetter <david (AT) fetter (DOT) org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter (AT) gmail (DOT) com

Men by their constitutions are naturally divided into two parties: 1.
Those who fear and distrust the people, and wish to draw all powers
from them into the hands of the higher classes. 2. Those who identify
themselves with the people, have confidence in them, cherish and
consider them as the most honest and safe, although not the most wise
depository of the public interests.
Thomas Jefferson, letter to Henry Lee
August 10, 1824

On May 4, 5:58*pm, da... (AT) fetter (DOT) org (David Fetter) wrote:

The database system I use doesn't allow:
1. More than one disjunct with union all in the recursive with
definition. (And the only allowed "set" operation to connect the two
disjuncts is "union all").
2. No subqueries in the recursive with definition query block.

Assume we model empty cells in the rule 110 (or any other two
dimensional cellular automaton for that matter) as not existing rows
in the table. The alternative -- having a binary column indicating if
a cell is empty or not -- is not a natural choice, because we would
have to have infinite number of tuples even at the very beginning of
computation. Then, checking if the cell is empty would necessarily
reduce to antijoin within the recursive with definition query block.