SQLまたはTSQLチューリングが完了しましたか？

Question

これは今日のオフィスで起こった。私はそのようなことをする計画はありませんが、理論的にはSQLでコンパイラを書くことができますか？一見すると、完全にチューリングされているように見えますが、多くのクラスの問題では非常に扱いにくいです。

チューリングが完了していない場合、そのようになる必要がありますか？

注：私はSQLでコンパイラを書くようなことは望んでいません。私はそれが愚かなことであることを知っています。その議論を避けていただければ幸いです。

Answer 1

SQLは、真のプログラミング言語であるように設計されたPL/SQLやPSMのような真の 'スクリプト'拡張がなくても、Turing Completeになることが判明しています。それはちょっと浮気している）。

this set of slides Andrew Gierthは、Turing Completeであることが証明されているcyclic tag systemを構築することで、CTEとWindowing SQLがTuring Completeであることを証明しています。しかし、CTE機能は重要な部分です。それによって、自分自身を参照できる名前付きサブ式を作成し、それによって再帰的に問題を解決することができます。

興味深いことに、CTEは、宣言型クエリ言語をより強力な宣言型クエリ言語に変えるために、SQLをプログラミング言語に変えるために実際には追加されませんでした。 C++のように、メタプログラミング言語を作成しようとはしていないにもかかわらず、テンプレートがTuringであることが判明しました。

ああ、Mandelbrot set in SQL例が同様に、非常に印象的です:)

Answer 2

http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question/

このトピックについての議論です。見積もり：

SQL自体（つまり、SQL92標準）は完全ではありません。しかし、 OracleのPL/SQLや SQL ServerのT-SQLなど、SQLから派生した言語の多くが完成しています。

PL/SQLとT-SQLは、SQL92自体の資格があるかどうかにかかわらず、議論の余地がありません。一部の人々は、コンピュータに何をすべきかをプログラミング言語として認めるコードは何であれ、その定義によって、SQL92は1であるが、そうである。 HTML。定義はむしろあいまいであり、それについて議論するのは無意味です。

Answer 3

厳密に言えば、最新のSQL標準には「永続的ストアドモジュール」（PSM）が含まれているため、SQLは現在チューリング完全言語です。簡単に言えば、PSMはOracleのPL/SQL言語の標準バージョン（および現在のDBMSの他の同様の手続き上の拡張機能）です。これらのPSMを含めて

は、SQLは完全なチューリングなった

Answer 4

アンANSI select文、本来はSQL-86で定義されている、それは常に終了しているため、（再帰CTEのを除くと唯一の実装があれば、完全なチューリングされていません任意の深い再帰をサポートします）。したがって、他のチューリングマシンをシミュレートすることはできません。

Answer 5

TSQLはチューリングComplete.To私はBrainFuckインタプリタを作ったことを証明しています。

BrainFuck interpreter in 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 backward 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