SQL 甚至 TSQL 图灵完备吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/900055/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is SQL or even TSQL Turing Complete?
提问by Matthew Vines
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.
这是今天在办公室出现的。我没有做这种事情的计划，但理论上你可以用SQL编写一个编译器吗？乍一看，它在我看来是图灵完备的，尽管对于许多类别的问题来说都非常麻烦。
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.
注意：我不想做任何事情，比如用 SQL 编写编译器，我知道这样做很愚蠢，所以如果我们能避免这种讨论，我将不胜感激。
回答by Jan de Vos
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).
事实证明，即使没有真正的“脚本”扩展，如 PL/SQL 或 PSM（它们被设计为真正的编程语言，所以这有点作弊），SQL 也可以是图灵完备的。
In this set of slidesAndrew 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.
在这组幻灯片中，Andrew Gierth 证明了使用 CTE 和 Windowing SQL 是图灵完备的，通过构造一个循环标签系统，该系统已被证明是图灵完备的。然而，CTE 特性是重要的部分——它允许您创建可以引用自身的命名子表达式，从而递归地解决问题。
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.
有趣的是，CTE 并没有真正被添加到将 SQL 变成一种编程语言——只是为了将一种声明式查询语言变成一种更强大的声明式查询语言。有点像在 C++ 中，它的模板被证明是图灵完备的，即使它们不是为了创建元编程语言。
Oh, the Mandelbrot set in SQLexample is very impressive, as well :)
哦，SQL示例中的Mandelbrot 设置也非常令人印象深刻:)
回答by Miroslav Popov
A given programming language is said to be Turing-complete if it can be shown that it is computationally equivalent to a Turing machine.
如果可以证明给定的编程语言在计算上等同于图灵机，则称其为图灵完备的。
The TSQL is Turing Complete because we can make a Brainfworinterpreter in TSQL.
TSQL 是图灵完备的，因为我们可以在 TSQL 中制作一个Brainfwor解释器。
Brainfwor interpreter in SQL - GitHub
The provided code works in-memory and doesn't modify a database.
提供的代码在内存中工作，不会修改数据库。
-- Brain fwor interpreter in SQL
DECLARE @Code VARCHAR(MAX) = ', [>,] < [.<]'
DECLARE @Input VARCHAR(MAX) = '!dlroW olleH';
-- Creates a "Brainfwor" DataBase.
-- CREATE DATABASE Brainfwor;
-- Creates the Source code table
DECLARE @CodeTable TABLE (
[Id] INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Command] CHAR(1) NOT NULL
);
-- Populate the source code into CodeTable
DECLARE @CodeLen INT = LEN(@Code);
DECLARE @CodePos INT = 0;
DECLARE @CodeChar CHAR(1);
WHILE @CodePos < @CodeLen
BEGIN
SET @CodePos = @CodePos + 1;
SET @CodeChar = SUBSTRING(@Code, @CodePos, 1);
IF @CodeChar IN ('+', '-', '>', '<', ',', '.', '[', ']')
INSERT INTO @CodeTable ([Command]) VALUES (@CodeChar)
END
-- Creates the Input table
DECLARE @InputTable TABLE (
[Id] INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Char] CHAR(1) NOT NULL
);
-- Populate the input text into InputTable
DECLARE @InputLen INT = LEN(@Input);
DECLARE @InputPos INT = 0;
WHILE @InputPos < @InputLen
BEGIN
SET @InputPos = @InputPos + 1;
INSERT INTO @InputTable ([Char])
VALUES (SUBSTRING(@Input, @InputPos, 1))
END
-- Creates the Output table
DECLARE @OutputTable TABLE (
[Id] INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Char] CHAR(1) NOT NULL
);
-- Creates the Buffer table
DECLARE @BufferTable TABLE (
[Id] INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Memory] INT DEFAULT 0 NOT NULL
);
INSERT INTO @BufferTable ([Memory])
VALUES (0);
-- Initialization of temporary variables
DECLARE @CodeLength INT = (SELECT COUNT(*) FROM @CodeTable);
DECLARE @CodeIndex INT = 0;
DECLARE @Pointer INT = 1;
DECLARE @InputIndex INT = 0;
DECLARE @Command CHAR(1);
DECLARE @Depth INT;
-- Main calculation cycle
WHILE @CodeIndex < @CodeLength
BEGIN
-- Read the next command.
SET @CodeIndex = @CodeIndex + 1;
SET @Command = (SELECT [Command] FROM @CodeTable WHERE [Id] = @CodeIndex);
-- Increment the pointer.
IF @Command = '>'
BEGIN
SET @Pointer = @Pointer + 1;
IF (SELECT [Id] FROM @BufferTable WHERE [Id] = @Pointer) IS NULL
INSERT INTO @BufferTable ([Memory]) VALUES (0);
END
-- Decrement the pointer.
ELSE IF @Command = '<'
SET @Pointer = @Pointer - 1;
-- Increment the byte at the pointer.
ELSE IF @Command = '+'
UPDATE @BufferTable SET [Memory] = [Memory] + 1 WHERE [Id] = @Pointer;
-- Decrement the byte at the pointer.
ELSE IF @Command = '-'
UPDATE @BufferTable SET [Memory] = [Memory] - 1 WHERE [Id] = @Pointer;
-- Output the byte at the pointer.
ELSE IF @Command = '.'
INSERT INTO @OutputTable ([Char]) (SELECT CHAR([Memory]) FROM @BufferTable WHERE [Id] = @Pointer);
-- Input a byte and store it in the byte at the pointer.
ELSE IF @Command = ','
BEGIN
SET @InputIndex = @InputIndex + 1;
UPDATE @BufferTable SET [Memory] = COALESCE((SELECT ASCII([Char]) FROM @InputTable WHERE [Id] = @InputIndex), 0) WHERE [Id] = @Pointer;
END
-- Jump forward past the matching ] if the byte at the pointer is zero.
ELSE IF @Command = '[' AND COALESCE((SELECT [Memory] FROM @BufferTable WHERE [Id] = @Pointer), 0) = 0
BEGIN
SET @Depth = 1;
WHILE @Depth > 0
BEGIN
SET @CodeIndex = @CodeIndex + 1;
SET @Command = (SELECT [Command] FROM @CodeTable WHERE [Id] = @CodeIndex);
IF @Command = '[' SET @Depth = @Depth + 1;
ELSE IF @Command = ']' SET @Depth = @Depth - 1;
END
END
-- Jump backwards to the matching [ unless the byte at the pointer is zero.
ELSE IF @Command = ']' AND COALESCE((SELECT [Memory] FROM @BufferTable WHERE [Id] = @Pointer), 0) != 0
BEGIN
SET @Depth = 1;
WHILE @Depth > 0
BEGIN
SET @CodeIndex = @CodeIndex - 1;
SET @Command = (SELECT [Command] FROM @CodeTable WHERE [Id] = @CodeIndex);
IF @Command = ']' SET @Depth = @Depth + 1;
ELSE IF @Command = '[' SET @Depth = @Depth - 1;
END
END
END;
-- Collects and prints the output
DECLARE @Output VARCHAR(MAX);
SELECT @Output = COALESCE(@Output, '') + [Char]
FROM @OutputTable;
PRINT @Output;
Go
回答by Aiden Bell
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.
SQL 本身（即 SQL92 标准）不是图灵完备的。但是，许多源自 SQL 的语言，例如 Oracle 的 PL/SQL 和 SQL Server 的 T-SQL 等，图灵完备。
PL/SQL 和 T-SQL 当然有资格作为编程语言，SQL92 本身是否有资格是有争议的。有些人声称，任何告诉计算机该做什么的代码都是一种编程语言；根据该定义，SQL92 是其中之一，但例如 HTML 也是如此。这个定义相当模糊，我认为这是毫无意义的争论。
回答by Jordi Cabot
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).
严格来说，SQL 现在是一种图灵完备的语言，因为最新的 SQL 标准包括“持久存储模块”（PSM）。简而言之，PSM 是 Oracle 中 PL/SQL 语言的标准版本（以及当前 DBMS 的其他类似过程扩展）。
With the inclusion of these PSMs, SQL became turing complete
通过包含这些 PSM，SQL 变得图灵完备
回答by usr
An ANSI select statement, as originally defined in SQL-86, is not turing complete because it always terminates (except for recursive CTEs and only if the implementation supports arbitrarily deep recursion). It is therefore not possible to simulate any other turing machine. Stored procedures are turing complete but thats cheating ;-)
最初在 SQL-86 中定义的 ANSI select 语句不是图灵完备的，因为它总是终止（递归 CTE 除外，并且仅当实现支持任意深度递归时）。因此不可能模拟任何其他图灵机。存储过程图灵完备，但那是作弊；-)
回答by sahossaini
Oracle's PLSQL and Microsoft's TSQL both are turing complete. Oracle's select statement itself is also turing complete.
Oracle 的 PLSQL 和 Microsoft 的 TSQL 都在图灵完备。Oracle 的 select 语句本身也是图灵完备的。
