今天在办公室出现了。我没有计划做这样的事情,但理论上你可以在SQL中编写一个编译器吗?初看起来,我认为这是彻底的,尽管对于很多类别的问题都非常麻烦。是SQL甚至TSQL图灵完成?
如果它不是完整的,它会变成什么样子?
注意:我不想做任何事情,比如在SQL中编写一个编译器,我知道这将是一件愚蠢的事情,所以如果我们可以避免这种讨论,我将不胜感激。
今天在办公室出现了。我没有计划做这样的事情,但理论上你可以在SQL中编写一个编译器吗?初看起来,我认为这是彻底的,尽管对于很多类别的问题都非常麻烦。是SQL甚至TSQL图灵完成?
如果它不是完整的,它会变成什么样子?
注意:我不想做任何事情,比如在SQL中编写一个编译器,我知道这将是一件愚蠢的事情,所以如果我们可以避免这种讨论,我将不胜感激。
事实证明,即使没有真正的'脚本'扩展,如PL/SQL或PSM(它们被设计成真正的编程语言,SQL也可以是图灵完整的这有点欺骗)。
this set of slides Andrew Gierth通过构建一个cyclic tag system证明了CTE和窗口化SQL是Turing Complete,它已被证明是Turing Complete。然而,CTE功能是重要的部分 - 它允许您创建可以引用自己的命名子表达式,从而递归地解决问题。
有趣的是,CTE并没有真正添加到将SQL转换为编程语言 - 只是将声明式查询语言转变为更强大的声明式查询语言。有点像C++,尽管它们并不打算创建元编程语言,但其模板竟然是图灵完备的。
呵呵,Mandelbrot set in SQL例子是非常可观的,以及:)
http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question/
是这个话题的讨论。一个报价:
SQL本身(即SQL92标准)不是完整的。但是,许多从SQL派生的语言,例如Oracle的PL/SQL和SQL Server的T-SQL等等都是完整的。
PL/SQL和T-SQL肯定有资格作为编程语言,SQL92本身是否具备资格是有争议的。有些人声称任何告诉计算机做什么的代码都可以用作编程语言;根据该定义,SQL92是一个,但也是如此HTML。这个定义相当模糊,而且这是一个毫无意义的争论点。
严格地说,SQL现在是一种完全图灵化的语言,因为最新的SQL标准包含了“持久存储模块”(PSMs)。简而言之,PSM是Oracle中的PL/SQL语言的标准版本(以及当前DBMS的其他类似程序扩展)。
连同这些的PSM的,SQL成为图灵完备
的ANSI SELECT语句,如最初在SQL-86定义的,不是图灵完成,因为它总是终止只有在执行(除递归的CTE和支持任意深度递归)。因此不可能模拟任何其他图灵机。存储过程完成,但那是作弊;-)
的TSQL是图灵Complete.To证明这一点我做了一个BrainFuck解释。
BrainFuck interpreter in SQL - GitHub
-- Brain Fuck interpreter in SQL
DECLARE @Code VARCHAR(MAX) = ', [>,] < [.<]'
DECLARE @Input VARCHAR(MAX) = '!dlroW olleH';
-- Creates a "BrainFuck" DataBase.
-- CREATE DATABASE BrainFuck;
-- 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 backward 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
的Oracle SQL也图灵完备,但在一个相当病态的方式:http://blog.schauderhaft.de/2009/06/18/building-a-turing-engine-in -oracle-sql-using-the-model-clause/ – 2014-08-19 05:38:31
>事实证明,SQL 不应该这样说:事实证明SQL:1999?只是这样说,因为CTE是在版本99中添加的,太多人将标准sql与Sql 92关联起来。 – Ernesto 2014-11-13 14:22:03