Re: SQL with CTEs Turing Complete?
From: Tegiri Nenashi <TegiriNenashi_at_gmail.com>
Date: Mon, 4 May 2009 17:13:23 -0700 (PDT)
Message-ID: <2ba8df7b-43d6-48e7-83a4-ce2d89550e9c_at_c18g2000prh.googlegroups.com>
Date: Mon, 4 May 2009 17:13:23 -0700 (PDT)
Message-ID: <2ba8df7b-43d6-48e7-83a4-ce2d89550e9c_at_c18g2000prh.googlegroups.com>
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?
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). Received on Tue May 05 2009 - 02:13:23 CEST