Is SQL or even TSQL Turing Complete?

sql tsql programming-languages language-features
Matthew Vines picture Matthew Vines · May 22, 2009 · Viewed 70k times · Source

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.

Answer

Jan de Vos picture Jan de Vos · Sep 28, 2011

It turns out that SQL can be Turing Complete even without a true 'scripting' extension such as PL/SQL or PSM (which are designed to be true programming languages, so that's kinda cheating).

In this set of slides Andrew Gierth proves that with CTE and Windowing SQL is Turing Complete, by constructing a cyclic tag system, which has been proved to be Turing Complete. The CTE feature is the important part however -- it allows you to create named sub-expressions that can refer to themselves, and thereby recursively solve problems.

The interesting thing to note is that CTE was not really added to turn SQL into a programming language -- just to turn a declarative querying language into a more powerful declarative querying language. Sort of like in C++, whose templates turned out to be Turing complete even though they weren't intended to create a meta programming language.

Oh, the Mandelbrot set in SQL example is very impressive, as well :)

Related questions

How do I UPDATE from a SELECT in SQL Server?

In SQL Server, it is possible to insert rows into a table with an INSERT.. SELECT statement: INSERT INTO Table (col1, col2, col3) SELECT col1, col2, col3 FROM other_table WHERE sql = 'cool' Is it also possible to update a …

Read More
How do I perform an IF...THEN in an SQL SELECT?

How do I perform an IF...THEN in an SQL SELECT statement? For example: SELECT IF(Obsolete = 'N' OR InStock = 'Y' ? 1 : 0) AS Saleable, * FROM Product

Read More
OR is not supported with CASE Statement in SQL Server

The OR operator in the WHEN clause of a CASE statement is not supported. How can I do this? CASE ebv.db_no WHEN 22978 OR 23218 OR 23219 THEN 'WECS 9500' ELSE 'WECS 9520' END as wecs_system

Read More