This came up at the office today. I have no plans of doing such a thing, but theoretically could you write a compiler in SQL? At first glance it appears to me to be turing complete, though extremely cumbersome for many classes of problems.
If it is not turing complete, what would it require to become so?
Note: I have no desire to do anything like write a compiler in SQL, I know it would be a silly thing to do, so if we can avoid that discussion I would appreciate it.
http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question/
Is a discussion of this topic.
A quote:
SQL as such (i.e. the SQL92 standard) is not turing complete. However, many of the languages derived from SQL, such as Oracle's PL/SQL and SQL Server's T-SQL and others are turing complete.
PL/SQL and T-SQL certainly qualify as programming languages, whether SQL92 itself qualifies is open for debate. Some people claim that any piece of code that tells a computer what to do qualifies as a programming language; by that definition SQL92 is one, but so is e.g. HTML. The definition is rather vague, and it's imo a pointless thing to argue about.
Strictly speaking, SQL is now a turing complete language because the latest SQL standard includes the "Persistent Stored Modules" (PSMs). In short, a PSM is the standard version of the PL/SQL language in Oracle (and other similar procedural extensions of current DBMS).
With the inclusion of these PSMs, SQL became turing complete
An ANSI select statement is not turing complete because it always terminates. It is therefore not possible to simulate any other turing machine. Stored procedures are turing complete but thats cheating ;-)