Apakah SQL atau bahkan TSQL Turing Lengkap?

Ini muncul di kantor hari ini. Saya tidak punya rencana melakukan hal seperti itu, tetapi secara teoritis Anda dapat menulis kompiler dalam SQL? Pada pandangan pertama tampaknya bagi saya turing lengkap, meskipun sangat rumit untuk banyak kelas masalah.

Jika belum selesai, apa yang dibutuhkan untuk menjadi seperti itu?

Catatan: Saya tidak punya keinginan untuk melakukan apa pun seperti menulis kompiler dalam SQL, saya tahu itu akan menjadi hal yang konyol untuk dilakukan, jadi jika kita dapat menghindari diskusi itu saya akan sangat menghargainya.

Ternyata SQL dapat menjadi Turing Lengkap bahkan tanpa ekstensi 'scripting' yang benar seperti PL / SQL atau PSM (yang dirancang untuk menjadi bahasa pemrograman yang benar, jadi itu agak curang).

Dalam rangkaian slide ini, Andrew Gierth membuktikan bahwa dengan CTE dan Windowing SQL adalah Turing Lengkap, dengan membangun sistem tag siklik , yang telah terbukti Turing Lengkap. Namun, fitur CTE adalah bagian yang penting - fitur ini memungkinkan Anda untuk membuat sub-ekspresi bernama yang dapat merujuk pada diri mereka sendiri, dan dengan demikian secara rekursif menyelesaikan masalah.

Yang menarik untuk dicatat adalah bahwa CTE tidak benar-benar ditambahkan untuk mengubah SQL menjadi bahasa pemrograman - hanya untuk mengubah bahasa query deklaratif menjadi bahasa query deklaratif yang lebih kuat. Agak seperti di C ++, yang templatnya ternyata Turing lengkap meskipun tidak dimaksudkan untuk membuat bahasa pemrograman meta.

Oh, Mandelbrot yang diatur dalam contoh SQL sangat mengesankan, juga :)

Bahasa pemrograman yang diberikan dikatakan Turing-complete jika dapat diperlihatkan bahwa secara komputasi setara dengan mesin Turing.

TSQL adalah Turing Lengkap karena kita dapat membuat juru bahasa BrainFuck dalam TSQL.

Interpreter BrainFuck dalam SQL - GitHub

Kode yang disediakan berfungsi di dalam memori dan tidak mengubah database.

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

Apakah diskusi tentang topik ini. Kutipan:

SQL seperti itu (yaitu standar SQL92) tidak turing lengkap. Namun, banyak bahasa yang berasal dari SQL, seperti Oracle's PL / SQL dan SQL Server's T-SQL dan lainnya sudah lengkap.

PL / SQL dan T-SQL tentu memenuhi syarat sebagai bahasa pemrograman, apakah SQL92 sendiri memenuhi syarat terbuka untuk diperdebatkan. Beberapa orang mengklaim bahwa setiap bagian kode yang memberi tahu komputer apa yang harus dilakukan memenuhi syarat sebagai bahasa pemrograman; oleh definisi itu SQL92 adalah satu, tetapi begitu juga misalnya HTML. Definisi ini agak kabur, dan itu tidak ada gunanya untuk diperdebatkan.

Sebenarnya, SQL sekarang menjadi bahasa yang lengkap karena standar SQL terbaru termasuk "Persistent Stored Modules" (PSMs). Singkatnya, PSM adalah versi standar bahasa PL / SQL di Oracle (dan ekstensi prosedural serupa dari DBMS saat ini).

Dengan dimasukkannya PSM ini, SQL menjadi turing lengkap

Pernyataan pilih ANSI, sebagaimana aslinya didefinisikan dalam SQL-86, tidak turing lengkap karena selalu berakhir (kecuali untuk CTE rekursif dan hanya jika implementasi mendukung rekursi mendalam sewenang-wenang). Oleh karena itu tidak mungkin untuk mensimulasikan mesin turing lainnya. Prosedur tersimpan sudah lengkap tapi itu curang ;-)

Oracle's PLSQL dan Microsoft TSQL keduanya sudah selesai. Pernyataan pilih Oracle itu sendiri juga turing lengkap.