SQL o anche TSQL Turing completo?

Question

Questo è venuto in ufficio oggi. Non ho intenzione di fare una cosa del genere, ma in teoria potresti scrivere un compilatore in SQL? A prima vista mi sembra di essere completo, anche se estremamente ingombrante per molte classi di problemi.

Se non è completo, cosa richiederebbe di farlo?

Nota: non ho voglia di fare qualcosa come scrivere un compilatore in SQL, so che sarebbe una cosa sciocca da fare, quindi se potessimo evitare quella discussione lo apprezzerei.

Answer 1

Si scopre che SQL può essere completato da Turing anche senza una vera estensione "di scripting" come PL/SQL o PSM (progettati per essere veri linguaggi di programmazione, quindi questo è un pasticcio).

In this set of slides Andrew Gierth dimostra che con CTE e Windowing SQL è completato Turing, costruendo un cyclic tag system, che è stato dimostrato essere Turing completo. La funzione CTE è tuttavia la parte importante: consente di creare sottoespressioni denominate che possono fare riferimento a se stesse e risolvere in modo ricorsivo i problemi.

La cosa interessante da notare è che il CTE non è stato realmente aggiunto per trasformare l'SQL in un linguaggio di programmazione - solo per trasformare un linguaggio di interrogazione dichiarativo in un linguaggio di interrogazione dichiarativo più potente. Un po 'come in C++, i cui modelli si sono rivelati completi di Turing anche se non erano destinati a creare un linguaggio di meta-programmazione.

Oh, l'esempio Mandelbrot set in SQL è molto impressionante, così :)

Answer 2

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

È una discussione su questo argomento. Un preventivo:

SQL come tale (ad esempio lo standard SQL92) non è completo. Tuttavia, molti dei linguaggi derivati ​​da SQL, come PL/SQL di Oracle e T-SQL di SQL Server e altri sono completi.

PL/SQL e T-SQL certamente si qualificano come linguaggi di programmazione, indipendentemente dal fatto che SQL92 stesso sia disponibile per il dibattito. Alcune persone sostengono che qualsiasi parte di codice che dice al computer cosa fare si qualifica come linguaggio di programmazione; da quella definizione SQL92 è uno, ma lo è anche per es. HTML. La definizione è piuttosto vaga, ed è una cosa inutile da discutere.

Answer 3

A rigor di termini, SQL è ora un linguaggio completo Turing, perché il più recente standard SQL include i "Moduli memorizzati persistenti" (PSM). In breve, un PSM è la versione standard del linguaggio PL/SQL in Oracle (e altre estensioni procedurali simili dell'attuale DBMS).

Con l'inclusione di questi PSM, SQL divenne Turing completa

Answer 4

Un ANSI select, come originariamente definito in SQL-86, non è turing completa perché termina sempre (tranne che per le CTE ricorsive e solo se l'attuazione supporta una ricorsione arbitrariamente profonda). Non è quindi possibile simulare alcuna altra macchina di turing. Le stored procedure sono complete ma questo è il cheating ;-)

Answer 5

Il TSQL è Turing Complete.To dimostrarlo ho fatto un interprete 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