Re: SQL with CTEs Turing Complete?

Tegiri Nenashi <TegiriNenashi_at_gmail.com> wrote:
> On May 4, 1:13 pm, da..._at_fetter.org (David Fetter) wrote:

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

As opposed to mutual recursion?

> and no subqueries are allowed,

Where would they be disallowed?

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

Cheers,
David.

-- 
David Fetter <david_at_fetter.org> http://fetter.org/
Phone: +1 415 235 3778  AIM: dfetter666  Yahoo!: dfetter
Skype: davidfetter      XMPP: david.fetter_at_gmail.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