SQL ou même TSQL Turing sont-ils complets?

C'est arrivé au bureau aujourd'hui. Je n'ai pas l'intention de faire une telle chose, mais pourriez-vous théoriquement écrire un compilateur en SQL? À première vue, il me semble être complet, bien qu'extrêmement lourd pour de nombreuses catégories de problèmes.

S'il n'est pas complet, que faudrait-il pour le devenir?

Remarque: je n'ai aucun désir de faire quoi que ce soit comme écrire un compilateur en SQL, je sais que ce serait une chose stupide à faire, donc si nous pouvons éviter cette discussion, je l'apprécierais.

Il s'avère que SQL peut être Turing Complete même sans une véritable extension de «script» telle que PL / SQL ou PSM (qui sont conçus pour être de véritables langages de programmation, donc c'est un peu de la triche).

Dans cette série de diapositives, Andrew Gierth prouve qu'avec CTE et Windowing SQL, Turing est complet, en construisant un système de balises cycliques , qui s'est avéré être Turing Complete. La fonctionnalité CTE est cependant la partie importante - elle vous permet de créer des sous-expressions nommées qui peuvent se référer à elles-mêmes, et ainsi résoudre des problèmes de manière récursive.

La chose intéressante à noter est que CTE n'a pas vraiment été ajouté pour transformer SQL en langage de programmation - juste pour transformer un langage de requête déclaratif en un langage de requête déclaratif plus puissant. Un peu comme dans C ++, dont les modèles se sont avérés être complets même s'ils n'étaient pas destinés à créer un méta-langage de programmation.

Oh, l'exemple de Mandelbrot défini dans SQL est également très impressionnant :)

Un langage de programmation donné est dit Turing-complet s'il peut être démontré qu'il est équivalent en calcul à une machine de Turing.

Le TSQL est complet parce que nous Turing pouvons faire un BrainFuck interprète TSQL.

Interpréteur BrainFuck en SQL - GitHub

Le code fourni fonctionne en mémoire et ne modifie pas une base de données.

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

Est une discussion de ce sujet. Une citation:

SQL en tant que tel (c'est-à-dire le standard SQL92) n'est pas terminé. Cependant, de nombreux langages dérivés de SQL, tels que PL / SQL d'Oracle et T-SQL de SQL Server et d'autres, sont en train d'être terminés.

PL / SQL et T-SQL sont certainement considérés comme des langages de programmation, la question de savoir si SQL92 lui-même est qualifiée est sujette à débat. Certaines personnes prétendent que tout morceau de code indiquant à un ordinateur ce qu'il doit faire est considéré comme un langage de programmation; par cette définition, SQL92 en est un, mais il en est de même, par exemple, HTML. La définition est assez vague et il est inutile de discuter.

À proprement parler, SQL est désormais un langage complet car le dernier standard SQL inclut les «modules stockés persistants» (PSM). En bref, un PSM est la version standard du langage PL / SQL dans Oracle (et d'autres extensions procédurales similaires du SGBD actuel).

Avec l'inclusion de ces PSM, SQL est devenu complet

Une instruction de sélection ANSI, telle que définie à l'origine dans SQL-86, n'est pas complète car elle se termine toujours (sauf pour les CTE récursifs et uniquement si l'implémentation prend en charge une récursivité arbitraire profonde). Il n'est donc pas possible de simuler une autre machine de turing. Les procédures stockées sont terminées mais c'est de la triche ;-)

Le PLSQL d'Oracle et le TSQL de Microsoft sont tous deux terminés. La déclaration de sélection d'Oracle elle-même est également terminée.