SQL или даже TSQL Тьюринг завершен?

171

Это подошло сегодня в офисе. У меня нет планов делать такие вещи, но теоретически вы могли бы написать компилятор на SQL? На первый взгляд мне кажется, что он завершен, хотя и чрезвычайно громоздок для многих классов проблем.

Если он не завершен по Тьюрингу, что бы он потребовал, чтобы стать таким?

Примечание: у меня нет желания делать что-то вроде написания компилятора на SQL, я знаю, что это было бы глупо, поэтому, если мы сможем избежать этого обсуждения, я был бы признателен.

Мэтью Вайнс
источник

Ответы:

219

Оказывается, что SQL может быть Turing Complete даже без настоящего расширения «сценариев», такого как PL / SQL или PSM (которые предназначены для настоящих языков программирования, так что это своего рода обман).

В этом наборе слайдов Эндрю Гирт доказывает, что с CTE и Windowing SQL является Turing Complete, создавая систему циклических тегов , которая оказалась Turing Complete. Тем не менее, функция CTE является важной частью - она ​​позволяет создавать именованные подвыражения, которые могут ссылаться на себя и, таким образом, рекурсивно решать проблемы.

Интересно отметить, что CTE на самом деле не был добавлен, чтобы превратить SQL в язык программирования - просто чтобы превратить декларативный язык запросов в более мощный язык декларативных запросов. Вроде как в C ++, чьи шаблоны оказались завершенными по Тьюрингу, хотя они не были предназначены для создания языка мета-программирования.

О, набор Мандельброта в примере с SQL тоже очень впечатляет :)

Ян де Вос
источник
1
Oracle SQL также завершен, хотя и довольно болезненно: blog.schauderhaft.de/2009/06/18/…
Йенс Шаудер
2
> Получается, что SQL не должен сказать: получается, что SQL: 1999? Просто говорю это, потому что CTE были добавлены в версии 99, и слишком много людей связывают стандартный SQL с Sql 92.
Эрнесто
1
@JensSchauder, который можно обобщить на «технология Oracle $ - это $ some_good_feature, хотя и довольно болезненно»
Роб Грант
3
Прошло 9 лет, но это может быть интересно beta.observablehq.com/@pallada-92/sql-3d-engine
Loupax
33

Данный язык программирования называется полным по Тьюрингу, если можно показать, что он вычислительно эквивалентен машине Тьюринга.

TSQL завершен по Тьюрингу, потому что мы можем создать интерпретатор BrainFuck на TSQL.

Интерпретатор BrainFuck в SQL - 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
Мирослав Попов
источник
Это транзакционный SQL, который завершен по Тьюрингу, я понял, что ANSI SQL - это не TC. Но хороших усилий!
alimack
28

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

Это обсуждение этой темы. Цитата:

SQL как таковой (то есть стандарт SQL92) не завершен. Тем не менее, многие языки, полученные из SQL, такие как Oracle PL / SQL и T-SQL SQL Server и другие, полностью завершены.

PL / SQL и T-SQL, безусловно, квалифицируются как языки программирования, вопрос о том, подходит ли сам SQL92, открыт для обсуждения. Некоторые люди утверждают, что любой фрагмент кода, который сообщает компьютеру, что делать, считается языком программирования; по этому определению SQL92 - один, но, например, HTML. Определение довольно расплывчато, и спорить о нем бессмысленно.

Эйден Белл
источник
15

Строго говоря, SQL теперь является полным языком Тьюринга, потому что последний стандарт SQL включает в себя «Persistent Stored Modules» (PSM). Короче говоря, PSM - это стандартная версия языка PL / SQL в Oracle (и других подобных процедурных расширениях современных СУБД).

С включением этих PSM SQL завершился

Джорди Кэбот
источник
13

Оператор выбора ANSI, как первоначально определено в SQL-86, не завершается по тьюрингу, потому что он всегда завершается (за исключением рекурсивных CTE и только в том случае, если реализация поддерживает произвольно глубокую рекурсию). Поэтому невозможно моделировать любую другую машину Тьюринга. Хранимые процедуры завершаются, но это жульничество ;-)

USR
источник
1

Oracle PLSQL и Microsoft TSQL оба завершены. Сам оператор выбора Oracle также завершен.

sahossaini
источник