SQL甚至TSQL图灵是否完整？

Question

今天在办公室提出了这个问题.我没有计划做这样的事情,但理论上你可以在SQL中编写一个编译器吗？乍一看,在我看来,虽然对于许多类型的问题非常麻烦,但我觉得它是完整的.

如果它没有完成,那么它需要什么呢？

注意:我不想做任何事情,比如在SQL中编写编译器,我知道这样做会很愚蠢,所以如果我们能够避免讨论,我会很感激.

Answer 1

事实证明,即使没有真正的"脚本"扩展,例如PL/SQL或PSM(设计为真正的编程语言,因此有点作弊),SQL也可以是Turing Complete.

在这组幻灯片中, Andrew Gierth证明了CTE和Windowing SQL是Turing Complete,通过构建一个已被证明是Turing Complete 的循环标记系统.然而,CTE功能是重要的部分 - 它允许您创建可以引用自身的命名子表达式,从而递归地解决问题.

有趣的是,CTE并没有真正被添加到将SQL转换为编程语言 - 只是将声明性查询语言转换为更强大的声明性查询语言.类似于C++,其模板结果是图灵完整,即使它们不是为了创建元编程语言.

哦,在SQL示例中设置的Mandelbrot非常令人印象深刻,以及:)

Answer 2

TSQL是Turing Complete.To证明我做了一个BrainFuck解释器.

SQL中的BrainFuck解释器 - 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 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

Answer 3

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也是如此.争论的定义相当模糊,争论是一件毫无意义的事情.

Answer 4

严格来说,SQL现在是一种图灵完整的语言,因为最新的SQL标准包括"持久存储模块"(PSM).简而言之,PSM是Oracle中PL/SQL语言的标准版本(以及当前DBMS的其他类似过程扩展).

随着这些PSM的加入,SQL变得完整

Answer 5

最初在SQL-86中定义的ANSI select语句并不完整,因为它总是终止(除了递归CTE,并且仅当实现支持任意深度递归时).因此不可能模拟任何其他图灵机.存储过程是完整的,但那是作弊;-)