SQL:2008 is Turing-complete [pdf,485k] | Hacker News Reader

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

assets.en.oreilly.com

8 pointsgjm1111 comments

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.

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.

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.

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

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

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.

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

Oh man... I love it!

Slides from a talk by David Fetter at OSCON 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...

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.

Reply on news.ycombinator.com