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

http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf

by gjm11 • 17 years ago

8 11 17 years ago

assets.en.oreilly.com

gjm113• 17 years ago

Slides from a talk by David Fetter at OSCON 2009.

Devilboy• 17 years 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-TSQ...

gjm113• 17 years 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• 17 years 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• 17 years 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.

loginx2• 17 years ago

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

teilo• 17 years ago

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

loginx2• 17 years ago

Oh man... I love it!

cousin_it• 17 years 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• 17 years 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").

gjm113• 17 years 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 . 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.

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

Related Stories