Path: news.cambrium.nl!textnews.cambrium.nl!feeder3.cambriumusenet.nl!feed.tweaknews.nl!209.197.12.242.MISMATCH!nx01.iad01.newshosting.com!newshosting.com!69.16.185.21.MISMATCH!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!postnews.google.com!d39g2000pra.googlegroups.com!not-for-mail
From: Tegiri Nenashi <TegiriNenashi@gmail.com>
Newsgroups: comp.databases.theory
Subject: Re: SQL with CTEs Turing Complete?
Date: Tue, 5 May 2009 09:06:18 -0700 (PDT)
Organization: http://groups.google.com
Lines: 31
Message-ID: <a143cd63-fafa-47ec-81e6-d0e3b387c6e4@d39g2000pra.googlegroups.com>
References: <rdydncE0easc0WLUnZ2dnUVZ_tidnZ2d@speakeasy.net> 
 <2ba8df7b-43d6-48e7-83a4-ce2d89550e9c@c18g2000prh.googlegroups.com> 
 <YL6dnSvJz_yoEmLUnZ2dnUVZ_ridnZ2d@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 1241539578 28312 127.0.0.1 (5 May 2009 16:06:18 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Tue, 5 May 2009 16:06:18 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: d39g2000pra.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, 5:58=A0pm, da...@fetter.org (David Fetter) wrote:
> Tegiri Nenashi <TegiriNena...@gmail.com> wrote:
> > 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. =A0If recursion is linear
>
> As opposed to mutual recursion?
>
> > and no subqueries are allowed,
>
> Where would they be disallowed?
>


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.