¿SQL o incluso TSQL Turing completo?

Esto ocurrió en la oficina hoy. No tengo planes de hacer tal cosa, pero en teoría ¿podrías escribir un compilador en SQL? A primera vista, me parece estar completa, aunque extremadamente engorrosa para muchas clases de problemas.

Si no está completo, ¿qué requeriría para ser así?

Nota: No deseo hacer nada como escribir un compilador en SQL, sé que sería una tontería, así que si podemos evitar esa discusión, lo agradecería.

Resulta que SQL puede ser Turing completo incluso sin una verdadera extensión de 'scripting' como PL / SQL o PSM (que están diseñados para ser verdaderos lenguajes de programación, por lo que es un poco engañoso).

En este conjunto de diapositivas, Andrew Gierth demuestra que con CTE y Windowing SQL se está completando Turing, mediante la construcción de un sistema de etiquetas cíclicas , que ha demostrado ser Turing completo. Sin embargo, la función CTE es la parte importante: le permite crear subexpresiones con nombre que pueden referirse a sí mismas y, por lo tanto, resolver problemas de forma recursiva.

Lo interesante a tener en cuenta es que CTE realmente no se agregó para convertir SQL en un lenguaje de programación, solo para convertir un lenguaje de consulta declarativa en un lenguaje de consulta declarativa más potente. Algo así como en C ++, cuyas plantillas resultaron ser completas de Turing a pesar de que no estaban destinadas a crear un lenguaje de meta programación.

Ah, el conjunto de Mandelbrot en el ejemplo de SQL también es muy impresionante :)

Se dice que un lenguaje de programación dado es completo de Turing si se puede demostrar que es computacionalmente equivalente a una máquina de Turing.

El TSQL está Turing completo porque podemos hacer un intérprete BrainFuck en TSQL.

BrainFuck intérprete en SQL - GitHub

El código proporcionado funciona en la memoria y no modifica una base de datos.

-- 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

https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question

Es una discusión de este tema. Una cita:

SQL como tal (es decir, el estándar SQL92) no está completo. Sin embargo, muchos de los lenguajes derivados de SQL, como PL / SQL de Oracle y T-SQL de SQL Server, entre otros, están completos.

PL / SQL y T-SQL ciertamente califican como lenguajes de programación, ya sea que SQL92 califique está abierto a debate. Algunas personas afirman que cualquier código que le dice a una computadora qué hacer califica como lenguaje de programación; según esa definición, SQL92 es uno, pero también lo es, por ejemplo, HTML. La definición es bastante vaga, y no es algo inútil discutir.

Estrictamente hablando, SQL ahora es un lenguaje completo de turing porque el último estándar de SQL incluye los "Módulos almacenados persistentes" (PSM). En resumen, un PSM es la versión estándar del lenguaje PL / SQL en Oracle (y otras extensiones procesales similares del DBMS actual).

Con la inclusión de estos PSM, SQL se volvió completamente completo

Una instrucción de selección ANSI, como se definió originalmente en SQL-86, no está completa porque siempre termina (excepto para los CTE recursivos y solo si la implementación admite una recursión arbitrariamente profunda). Por lo tanto, no es posible simular ninguna otra máquina de turing. Los procedimientos almacenados se están completando, pero eso es trampa ;-)

El PLSQL de Oracle y el TSQL de Microsoft están completos. La declaración select de Oracle en sí misma también se está completando.