Path: news.cambrium.nl!textnews.cambrium.nl!feeder3.cambriumusenet.nl!feed.tweaknews.nl!209.197.12.242.MISMATCH!nx01.iad01.newshosting.com!newshosting.com!198.186.194.249.MISMATCH!news-out.readnews.com!transit3.readnews.com!postnews.google.com!c18g2000prh.googlegroups.com!not-for-mail
From: Tegiri Nenashi <TegiriNenashi@gmail.com>
Newsgroups: comp.databases.theory
Subject: Re: SQL with CTEs Turing Complete?
Date: Mon, 4 May 2009 17:13:23 -0700 (PDT)
Organization: http://groups.google.com
Lines: 11
Message-ID: <2ba8df7b-43d6-48e7-83a4-ce2d89550e9c@c18g2000prh.googlegroups.com>
References: <rdydncE0easc0WLUnZ2dnUVZ_tidnZ2d@speakeasy.net>
NNTP-Posting-Host: 70.137.183.58
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1241482403 1983 127.0.0.1 (5 May 2009 00:13:23 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Tue, 5 May 2009 00:13:23 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: c18g2000prh.googlegroups.com; posting-host=70.137.183.58; 
 posting-account=PBsn8woAAADaWofLEAjNrE17YVrUmBlm
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.4) 
 Gecko/2008102920 Firefox/3.0.4,gzip(gfe),gzip(gfe)
Xref:  news.cambrium.nl

On May 4, 1:13=A0pm, da...@fetter.org (David Fetter) wrote:
> Hello,
>
> I'm curious as to SQL with Common Table Expressions is Turing
> Complete. =A0Is there some kind of proof either way?

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