To wypadło dziś w biurze. Nie mam planów zrobienia czegoś takiego, ale teoretycznie czy mógłbyś napisać kompilator w SQL? Na pierwszy rzut oka wydaje mi się, że jest to kompletne, choć niezwykle uciążliwe dla wielu klas problemów.
Jeśli nie jest kompletny, czego wymagałoby to, aby się takim stać?
Uwaga: nie mam ochoty robić czegoś takiego jak pisanie kompilatora w SQL, wiem, że byłoby to głupie, więc jeśli unikniemy tej dyskusji, będę wdzięczny.
Okazuje się, że SQL może być Turing Complete nawet bez prawdziwego rozszerzenia „skryptowego”, takiego jak PL / SQL lub PSM (które mają być prawdziwymi językami programowania, więc to trochę oszustwo).
W tym zestawie slajdów Andrew Gierth udowadnia, że z CTE i Windowing SQL jest Turing Complete, konstruując cykliczny system tagów , który okazał się być Turing Complete. Funkcja CTE jest jednak ważną częścią - pozwala tworzyć nazwane wyrażenia podrzędne, które mogą odnosić się do siebie, a tym samym rekurencyjnie rozwiązywać problemy.
Warto zauważyć, że CTE nie został tak naprawdę dodany, aby przekształcić SQL w język programowania - tylko po to, aby zamienić deklaratywny język zapytań w potężniejszy deklaratywny język zapytań. Coś jak w C ++, którego szablony okazały się kompletne w Turingu, mimo że nie były przeznaczone do tworzenia meta języka programowania.
> Okazuje się, że SQL Czy nie powinien powiedzieć: Okazuje się, że SQL: 1999? Mówię to tylko dlatego, że CTE zostały dodane w wersji 99 i zbyt wiele osób kojarzy standardowy sql z Sql 92.
Ernesto
1
@JensSchauder, który można uogólnić na „Technologia Oracle $ to $ some_good_feature, chociaż w dość chory sposób”
Podany kod działa w pamięci i nie modyfikuje bazy danych.
-- Brain Fuck interpreter in SQLDECLARE@Code VARCHAR(MAX)=', [>,] < [.<]'DECLARE@Input VARCHAR(MAX)='!dlroW olleH';-- Creates a "BrainFuck" DataBase.-- CREATE DATABASE BrainFuck;-- Creates the Source code tableDECLARE@CodeTable TABLE([Id] INT IDENTITY(1,1)PRIMARYKEYNOTNULL,[Command] CHAR(1)NOTNULL);-- Populate the source code into CodeTableDECLARE@CodeLen INT = LEN(@Code);DECLARE@CodePos INT =0;DECLARE@CodeChar CHAR(1);WHILE@CodePos <@CodeLenBEGINSET@CodePos =@CodePos +1;SET@CodeChar = SUBSTRING(@Code,@CodePos,1);IF@CodeChar IN('+','-','>','<',',','.','[',']')INSERTINTO@CodeTable ([Command])VALUES(@CodeChar)END-- Creates the Input tableDECLARE@InputTable TABLE([Id] INT IDENTITY(1,1)PRIMARYKEYNOTNULL,[Char] CHAR(1)NOTNULL);-- Populate the input text into InputTableDECLARE@InputLen INT = LEN(@Input);DECLARE@InputPos INT =0;WHILE@InputPos <@InputLenBEGINSET@InputPos =@InputPos +1;INSERTINTO@InputTable ([Char])VALUES(SUBSTRING(@Input,@InputPos,1))END-- Creates the Output tableDECLARE@OutputTable TABLE([Id] INT IDENTITY(1,1)PRIMARYKEYNOTNULL,[Char] CHAR(1)NOTNULL);-- Creates the Buffer tableDECLARE@BufferTable TABLE([Id] INT IDENTITY(1,1)PRIMARYKEYNOTNULL,[Memory] INT DEFAULT0NOTNULL);INSERTINTO@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 cycleWHILE@CodeIndex <@CodeLengthBEGIN-- Read the next command.SET@CodeIndex =@CodeIndex +1;SET@Command =(SELECT[Command]FROM@CodeTable WHERE[Id]=@CodeIndex);-- Increment the pointer.IF@Command ='>'BEGINSET@Pointer =@Pointer +1;IF(SELECT[Id]FROM@BufferTable WHERE[Id]=@Pointer)ISNULLINSERTINTO@BufferTable ([Memory])VALUES(0);END-- Decrement the pointer.ELSEIF@Command ='<'SET@Pointer =@Pointer -1;-- Increment the byte at the pointer.ELSEIF@Command ='+'UPDATE@BufferTable SET[Memory]=[Memory]+1WHERE[Id]=@Pointer;-- Decrement the byte at the pointer.ELSEIF@Command ='-'UPDATE@BufferTable SET[Memory]=[Memory]-1WHERE[Id]=@Pointer;-- Output the byte at the pointer.ELSEIF@Command ='.'INSERTINTO@OutputTable ([Char])(SELECT CHAR([Memory])FROM@BufferTable WHERE[Id]=@Pointer);-- Input a byte and store it in the byte at the pointer.ELSEIF@Command =','BEGINSET@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.ELSEIF@Command ='['ANDCOALESCE((SELECT[Memory]FROM@BufferTable WHERE[Id]=@Pointer),0)=0BEGINSET@Depth =1;WHILE@Depth >0BEGINSET@CodeIndex =@CodeIndex +1;SET@Command =(SELECT[Command]FROM@CodeTable WHERE[Id]=@CodeIndex);IF@Command ='['SET@Depth =@Depth +1;ELSEIF@Command =']'SET@Depth =@Depth -1;ENDEND-- Jump backwards to the matching [ unless the byte at the pointer is zero.ELSEIF@Command =']'ANDCOALESCE((SELECT[Memory]FROM@BufferTable WHERE[Id]=@Pointer),0)!=0BEGINSET@Depth =1;WHILE@Depth >0BEGINSET@CodeIndex =@CodeIndex -1;SET@Command =(SELECT[Command]FROM@CodeTable WHERE[Id]=@CodeIndex);IF@Command =']'SET@Depth =@Depth +1;ELSEIF@Command ='['SET@Depth =@Depth -1;ENDENDEND;-- Collects and prints the outputDECLARE@Output VARCHAR(MAX);SELECT@Output =COALESCE(@Output,'')+[Char]FROM@OutputTable;PRINT@Output;
Go
SQL jako taki (tj. Standard SQL92) nie jest kompletny. Jednak wiele języków wywodzących się z SQL, takich jak Oracle PL / SQL, T-SQL SQL Server i inne, jest w fazie ukończenia.
PL / SQL i T-SQL z pewnością kwalifikują się jako języki programowania, ale kwestia, czy sam SQL92 kwalifikuje się, jest przedmiotem dyskusji. Niektórzy twierdzą, że każdy fragment kodu, który mówi komputerowi, co ma zrobić, kwalifikuje się jako język programowania; z tej definicji SQL92 jest jeden, ale tak jest np. HTML. Definicja jest raczej niejasna i nie ma sensu się o nią kłócić.
Ściśle mówiąc, SQL jest teraz kompletnym językiem, ponieważ najnowszy standard SQL zawiera „Trwałe moduły składowane” (PSM). Krótko mówiąc, PSM to standardowa wersja języka PL / SQL w Oracle (i innych podobnych rozszerzeniach proceduralnych obecnego DBMS).
Wraz z włączeniem tych PSM, SQL stał się kompletny
Instrukcja wyboru ANSI, jak pierwotnie zdefiniowano w SQL-86, nie jest zakończona, ponieważ zawsze się kończy (z wyjątkiem rekurencyjnych CTE i tylko wtedy, gdy implementacja obsługuje dowolnie głęboką rekursję). Dlatego nie jest możliwe symulowanie żadnej innej maszyny Turinga. Procedury składowane są kompletne, ale to oszustwo ;-)
TSQL jest Turing Complete, ponieważ możemy stworzyć interpreter BrainFuck w TSQL.
BrainFuck interpreter w SQL - GitHub
Podany kod działa w pamięci i nie modyfikuje bazy danych.
źródło
https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question
To dyskusja na ten temat. Cytat:
źródło
Ściśle mówiąc, SQL jest teraz kompletnym językiem, ponieważ najnowszy standard SQL zawiera „Trwałe moduły składowane” (PSM). Krótko mówiąc, PSM to standardowa wersja języka PL / SQL w Oracle (i innych podobnych rozszerzeniach proceduralnych obecnego DBMS).
Wraz z włączeniem tych PSM, SQL stał się kompletny
źródło
Instrukcja wyboru ANSI, jak pierwotnie zdefiniowano w SQL-86, nie jest zakończona, ponieważ zawsze się kończy (z wyjątkiem rekurencyjnych CTE i tylko wtedy, gdy implementacja obsługuje dowolnie głęboką rekursję). Dlatego nie jest możliwe symulowanie żadnej innej maszyny Turinga. Procedury składowane są kompletne, ale to oszustwo ;-)
źródło
Oracle PLSQL i Microsoft TSQL są na ukończeniu. Samo oświadczenie Oracle o wyborze również jest kompletne.
źródło