Is SQL or even TSQL Turing Complete?

by

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 🙂

More Related Contents:

  1. Convert text to system date format [duplicate]
  2. How to get a particular preceding value of a column in SQL [closed]
  3. to select all the employees who have joined most recently under king
  4. How do I obtain a Query Execution Plan in SQL Server?
  5. What is the meaning of the prefix N in T-SQL statements and when should I use it?
  6. Maximum size for a SQL Server Query? IN clause? Is there a Better Approach [duplicate]
  7. SQL JOIN vs IN performance?
  8. Convert varchar into datetime in SQL Server
  9. TSQL Pivot without aggregate function
  10. How to generate a range of dates in SQL Server
  11. SQL RANK() versus ROW_NUMBER()
  12. Generate SQL Create Scripts for existing tables with Query
  13. How do I delete from multiple tables using INNER JOIN in SQL server
  14. Check if a row exists, otherwise insert
  15. Drop all the tables, stored procedures, triggers, constraints and all the dependencies in one sql statement
  16. Script to kill all connections to a database (More than RESTRICTED_USER ROLLBACK)
  17. CTE error: “Types don’t match between the anchor and the recursive part”
  18. How does this CASE expression reach the ELSE clause?
  19. SQL speed up performance of insert?
  20. How to get N rows starting from row M from sorted table in T-SQL
  21. TransactSQL to run another TransactSQL script
  22. How to Concatenate Numbers and Strings to Format Numbers in T-SQL?
  23. How can I generate a temporary table filled with dates in SQL Server 2000?
  24. How do I remove extended ASCII characters from a string in T-SQL?
  25. SQL Server equivalent to MySQL enum data type?
  26. How to correctly insert newline in nvarchar [duplicate]
  27. Grant SELECT permission on a view, but not on underlying objects
  28. How do you copy a record in a SQL table but swap out the unique id of the new row?
  29. Using IF ELSE statement based on Count to execute different Insert statements
  30. SQL – Call Stored Procedure for each record

Leave a Comment