3 ms·

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

8 points by gjm11 17y ago

gjm11 17y ago
Slides from a talk by David Fetter at OSCON 2009.
Devilboy 17y ago
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-TSQL-Madlebrot.aspx http://thedailywtf.com/Articles/Stupid-Coding-Tricks-The-TSQ...
- gjm11 17y ago
  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.
joubert 17y ago
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 17y ago
  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.
loginx 17y ago
Oh boy... the countdown to SQL web-frameworks is on now.
- teilo 17y ago
  Already happened: http://www.sqlonrails.org/screencast http://www.sqlonrails.org/screencast
  - loginx 17y ago
    Oh man... I love it!
- cousin_it 17y ago
  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.
icey 17y ago
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").
gjm11 17y ago
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 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.

8 points by gjm11 17y ago

gjm11 17y ago

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-TSQL-Madlebrot.aspx http://thedailywtf.com/Articles/Stupid-Coding-Tricks-The-TSQ...

gjm11 17y ago
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.

joubert 17y ago

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 17y ago
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.

loginx 17y ago

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

teilo 17y ago
Already happened: http://www.sqlonrails.org/screencast http://www.sqlonrails.org/screencast
- loginx 17y ago
  Oh man... I love it!
cousin_it 17y ago
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.

icey 17y ago

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

gjm11 17y ago

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