Re: SQL with CTEs Turing Complete?

From: Tegiri Nenashi <>
Date: Tue, 5 May 2009 09:06:18 -0700 (PDT)
Message-ID: <>

On May 4, 5:58 pm, (David Fetter) wrote:
> Tegiri Nenashi <> wrote:
> > On May 4, 1:13 pm, (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
> 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. Received on Tue May 05 2009 - 18:06:18 CEST

Original text of this message