SQL:2008 is Turing-complete [pdf,485k]

_zhqs · on Sept 2, 2009

This is about PostgreSQL 8.4.

I didn't see a mention of SQL 2008. Or maybe that "SQL:2008" doesn't refer to SQL 2008 at all; but I couldn't find the string "2008" in the slides either, unless Spotlight is having a bad Wednesday.

I suspect the title of the post needs revision.

jsrn · on Sept 2, 2009

You are right. Slide 47 says:

> "With CTE and Windowing, SQL is Turing Complete."

CTE (Common Table Expressions) were introduced in the SQL:1999 standard, window functions were introduced in the SQL:2003 standard. PostgreSQL implemented both CTEs and window functions in PostgreSQL 8.4.

gjm11 · on Sept 3, 2009

The reason why I said "SQL:2008" is that that's the dialect specifically mentioned in this example, which I believe is Fetter's: http://wiki.postgresql.org/wiki/Mandelbrot_set . It may well be that earlier versions of SQL are also Turing-complete; I haven't followed the evolution of SQL anything like closely enough to know.

icey · on Sept 2, 2009

As far as I can recall, ANSI-SQL is Turing complete. That would include SQL Server, Mysql, Postgres, Oracle, etc.

The original title of the paper is much better than this title ("High Performance SQL with PostgreSQL").

loginx · on Sept 2, 2009

Oh boy... the countdown to SQL web-frameworks is on now.

cousin_it · on Sept 2, 2009

My dad's company writes enterprise webapps in PL/SQL. I haven't seen the actual code, but imagine it begins like this:

    SELECT '<html>' ...

They're pretty successful commercially. Apparently the approach is practical because it doesn't have many layers.

teilo · on Sept 2, 2009

Already happened: http://www.sqlonrails.org/screencast

loginx · on Sept 2, 2009

Oh man... I love it!

gjm11 · on Sept 2, 2009

Slides from a talk by David Fetter at OSCON 2009.

Devilboy · on Sept 2, 2009

That's pretty cool but I don't think SQL 2008 is the first Turing-complete SQL Server.

SQL Server 2005 could do the Mandlebrot too: http://thedailywtf.com/Articles/Stupid-Coding-Tricks-The-TSQ...

gjm11 · on Sept 3, 2009

SQL:2008 is a language. MS SQL Server 2005 is an implementation, which includes some extensions to the SQL language (notably "T-SQL", use at that link). To me, at least, it's much more surprising to find that the official SQL language is Turing-complete than that someone's implemented proprietary extensions that make it so. Your mileage may vary.