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?


  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.

  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.

  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?

  4. This blog is so nice to me. I will continue to come here again and again. Visit my link as well. Good luck
    obat aborsi
    cara menggugurkan kandungan
    obat penggugur kandungan
    obat telat datang bulan

  5. SQL is very useful for those students who are learning drawing on windows and want to become web designer.I am a writer of phd dissertation writing services and I write all types of Assignments.

  6. We are amongst the Best Mobile App Development Company in Mumbai that offer IOS, Android Mobile Application Development services that look Great and act Smart.
    Mobile app development company in mumbai

  7. Excellent Post. In fact, I'm making it a sticky so other can find it later. Thanks!
    animal crossing

  8. Nice Information Your first-class knowledge of this great job can become a suitable foundation for these people. I did some research on the subject and found that almost everyone will agree with your blog.
    Cyber Security Course in Bangalore

  9. Writing in style and getting good compliments on the article is hard enough, to be honest, but you did it so calmly and with such a great feeling and got the job done. This item is owned with style and I give it a nice compliment. Better!
    Cyber Security Training in Bangalore

  10. this is really nice to read..informative post is very good to read..thanks a lot!

    seo services in lahore

  11. I just couldn't leave your website before telling you that I truly enjoyed the top quality info you present to your visitors? Will be back again frequently to check up on new posts.

    seo company in lahore

  12. thanks for the tips and information..i really appreciate it..

    digital marketing agency in lahore

  13. It was wondering if I could use this write-up on my other website, I will link it back to your website though.Great Thanks.

    Web App Development Services UAE

  14. Thanks For sharing this Superb article.I use this Article to show my assignment in college.it is useful For me Great Work.
    Software Development Company UAE

  15. Nice to be visiting your blog again, it has been months for me. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, great share.

    Custom Website Development in UAE


Blog Archive

Google Analytics