SQL 甚至 TSQL 图灵完备吗? [英] Is SQL or even TSQL Turing Complete?
问题描述
今天在办公室遇到了这个问题.我没有做这种事情的计划，但理论上你可以用SQL编写一个编译器吗?乍一看，它在我看来是图灵完备的，尽管对于许多类别的问题来说都非常麻烦.
如果它不是图灵完备的，那么它需要什么才能成为图灵完备的?
注意:我不想做任何事情，比如用 SQL 编写编译器，我知道这样做很愚蠢，所以如果我们能避免这种讨论，我将不胜感激.
事实证明，即使没有真正的脚本"扩展，如 PL/SQL 或 PSM(它们被设计为真正的编程语言)，SQL 也可以是图灵完备的，所以这有点作弊).
在这组幻灯片 Andrew Gierth 通过构建循环标签系统，已被证明是图灵完备的.然而，CTE 功能是重要的部分——它允许您创建可以引用自身的命名子表达式，从而递归地解决问题.
有趣的是，CTE 并没有真正被添加到将 SQL 变成一种编程语言——只是为了将一种声明式查询语言变成一种更强大的声明式查询语言.有点像在 C++ 中，它的模板被证明是图灵完备的，即使它们不是为了创建元编程语言.
哦，SQL 中的 Mandelbrot 集 示例也非常令人印象深刻:)
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.
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 :)
这篇关于SQL 甚至 TSQL 图灵完备吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
