I've learned. I'll share.

August 26, 2009

SQL is now turing complete!

David Fetter at Oscon 2009 just made a stunning claim: With CTE and Windowing, SQL is Turing Complete. He even offers a proof and an amazing example (although I'm not sure if the example requires turing completeness, it's still amazing).

This could be a big deal. Why? It means that you can do anything in an SQL query. While drawing the mandlebrot set is a nice demo, the first "killer app" will be tree traversal. Lots of relational tables end up looking like trees and are a royal pain to deal with in normal SQL. After that, only our imagination (and performance) is the limit. You can theoretically create any data view that runs in the DB all in one shot, without any of the troubles of stored procedures.

I see a similarity between turing-complete SQL in the DB and JavaScript on the browser. For years, we used JavaScript to do silly stuff, but then a few bright minds created amazing tools like gmail and google maps and our view of JavaScript was forever changed. Now JavaScript is everywhere and there's a race to make the best development framework and engines fastest engines.

Might the same thing happen with turning-complete SQL? is the race on to be the first programming language to compile down to turing-complete SQL?.

Honestly, if I were a betting man, I'd say it won't come to anything significant. But I'll also guess that the lure of compiling down to SQL will eventually capture someone, somewhere. It's only a matter of time. In fact, if you're a programming language geek, the sirens are probably calling to you right now :). When it does happen, I expect the first language to be a functional one, especially one with a small core, like a variant of lisp. Once we get clojure in clojure, maybe it will be a candidate. Or maybe C# will end up with LINQ-to-turning-complete-SQL (SQLINQ?).

What do you think?

3 comments:

  1. Is the resultant SQL still truly declarative? It will take someone cleverer than me to answer that question - but if it is - then this is a very interesting thing indeed.

    ReplyDelete
  2. From what I read on the netz the following two statements are equal: "This programming language is declarative","There is a DEFINED one-to-one correspondence between written code and produced machine instructions", so in that case since the compiler is not yet written i doubt it's standardized, and hence the language is declarative.

    ReplyDelete
  3. what do I think? reminds me of what Prolog had already accomplished. Then came SQL that didn't nest non-deterministically deep. Then came SPARQL that I guess tried to again take a page from Prolog to add that aspect back in. What's wrong with Prolog? Why do we have to call it other things?

    ReplyDelete

Blog Archive

Google Analytics