Czy SQL, a nawet TSQL Turing jest kompletny?

To wypadło dziś w biurze. Nie mam planów zrobienia czegoś takiego, ale teoretycznie czy mógłbyś napisać kompilator w SQL? Na pierwszy rzut oka wydaje mi się, że jest to kompletne, choć niezwykle uciążliwe dla wielu klas problemów.

Jeśli nie jest kompletny, czego wymagałoby to, aby się takim stać?

Uwaga: nie mam ochoty robić czegoś takiego jak pisanie kompilatora w SQL, wiem, że byłoby to głupie, więc jeśli unikniemy tej dyskusji, będę wdzięczny.

Okazuje się, że SQL może być Turing Complete nawet bez prawdziwego rozszerzenia „skryptowego”, takiego jak PL / SQL lub PSM (które mają być prawdziwymi językami programowania, więc to trochę oszustwo).

W tym zestawie slajdów Andrew Gierth udowadnia, że ​​z CTE i Windowing SQL jest Turing Complete, konstruując cykliczny system tagów , który okazał się być Turing Complete. Funkcja CTE jest jednak ważną częścią - pozwala tworzyć nazwane wyrażenia podrzędne, które mogą odnosić się do siebie, a tym samym rekurencyjnie rozwiązywać problemy.

Warto zauważyć, że CTE nie został tak naprawdę dodany, aby przekształcić SQL w język programowania - tylko po to, aby zamienić deklaratywny język zapytań w potężniejszy deklaratywny język zapytań. Coś jak w C ++, którego szablony okazały się kompletne w Turingu, mimo że nie były przeznaczone do tworzenia meta języka programowania.

Och, zestaw Mandelbrota w przykładzie SQL jest również imponujący :)

O danym języku programowania mówi się, że jest kompletny Turinga, jeśli można wykazać, że jest obliczeniowo równoważny maszynie Turinga.

TSQL jest Turing Complete, ponieważ możemy stworzyć interpreter BrainFuck w TSQL.

BrainFuck interpreter w SQL - GitHub

Podany kod działa w pamięci i nie modyfikuje bazy danych.

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

To dyskusja na ten temat. Cytat:

SQL jako taki (tj. Standard SQL92) nie jest kompletny. Jednak wiele języków wywodzących się z SQL, takich jak Oracle PL / SQL, T-SQL SQL Server i inne, jest w fazie ukończenia.

PL / SQL i T-SQL z pewnością kwalifikują się jako języki programowania, ale kwestia, czy sam SQL92 kwalifikuje się, jest przedmiotem dyskusji. Niektórzy twierdzą, że każdy fragment kodu, który mówi komputerowi, co ma zrobić, kwalifikuje się jako język programowania; z tej definicji SQL92 jest jeden, ale tak jest np. HTML. Definicja jest raczej niejasna i nie ma sensu się o nią kłócić.

Ściśle mówiąc, SQL jest teraz kompletnym językiem, ponieważ najnowszy standard SQL zawiera „Trwałe moduły składowane” (PSM). Krótko mówiąc, PSM to standardowa wersja języka PL / SQL w Oracle (i innych podobnych rozszerzeniach proceduralnych obecnego DBMS).

Wraz z włączeniem tych PSM, SQL stał się kompletny

Instrukcja wyboru ANSI, jak pierwotnie zdefiniowano w SQL-86, nie jest zakończona, ponieważ zawsze się kończy (z wyjątkiem rekurencyjnych CTE i tylko wtedy, gdy implementacja obsługuje dowolnie głęboką rekursję). Dlatego nie jest możliwe symulowanie żadnej innej maszyny Turinga. Procedury składowane są kompletne, ale to oszustwo ;-)

Oracle PLSQL i Microsoft TSQL są na ukończeniu. Samo oświadczenie Oracle o wyborze również jest kompletne.