Dies kam heute im Büro auf. Ich habe nicht vor, so etwas zu tun, aber könnten Sie theoretisch einen Compiler in SQL schreiben? Auf den ersten Blick scheint es mir vollständig zu sein, obwohl es für viele Problemklassen äußerst umständlich ist.
Was würde es erfordern, wenn es nicht vollständig ist?
Hinweis: Ich habe keine Lust, einen Compiler in SQL zu schreiben. Ich weiß, dass dies eine dumme Sache wäre. Wenn wir diese Diskussion vermeiden können, würde ich es begrüßen.
Es stellt sich heraus, dass SQL auch ohne eine echte "Scripting" -Erweiterung wie PL / SQL oder PSM (die als echte Programmiersprachen konzipiert sind, also ein bisschen betrügen kann) Turing Complete sein kann.
In diesem Foliensatz beweist Andrew Gierth, dass mit CTE und Windowing SQL Turing Complete ist, indem er ein zyklisches Tag-System erstellt , das sich als Turing Complete erwiesen hat. Die CTE-Funktion ist jedoch der wichtige Teil - Sie können benannte Unterausdrücke erstellen, die auf sich selbst verweisen können, und so Probleme rekursiv lösen.
Das Interessante ist, dass CTE nicht wirklich hinzugefügt wurde, um SQL in eine Programmiersprache umzuwandeln - nur um eine deklarative Abfragesprache in eine leistungsfähigere deklarative Abfragesprache umzuwandeln. Ähnlich wie in C ++, dessen Vorlagen sich als vollständig herausstellten, obwohl sie nicht dazu gedacht waren, eine Meta-Programmiersprache zu erstellen.
> Es stellt sich heraus, dass SQL Sollte es nicht heißen: Es stellt sich heraus, dass SQL: 1999? Ich sage das nur, weil CTEs in Version 99 hinzugefügt wurden und viel zu viele Leute Standard-SQL mit SQL 92 assoziieren.
Ernesto
1
@JensSchauder, der verallgemeinert werden kann auf "Oracle $ -Technologie ist $ some_good_feature, wenn auch ziemlich krank"
Eine gegebene Programmiersprache wird als Turing-vollständig bezeichnet, wenn gezeigt werden kann, dass sie einer Turing-Maschine rechnerisch äquivalent ist.
Die TSQL ist Turing Complete, weil wir in TSQL einen BrainFuck- Interpreter erstellen können.
Der bereitgestellte Code arbeitet im Arbeitsspeicher und ändert keine Datenbank.
-- 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 <@CodeLen
BEGINSET@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 <@InputLen
BEGINSET@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 <@CodeLength
BEGIN-- 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 als solches (dh der SQL92-Standard) ist nicht vollständig. Viele der von SQL abgeleiteten Sprachen, wie z. B. PL / SQL von Oracle und T-SQL von SQL Server und andere, sind jedoch vollständig.
PL / SQL und T-SQL qualifizieren sich sicherlich als Programmiersprachen. Ob sich SQL92 selbst qualifiziert, steht zur Debatte. Einige Leute behaupten, dass jeder Code, der einem Computer sagt, was zu tun ist, als Programmiersprache qualifiziert ist. Nach dieser Definition ist SQL92 eins, aber zB auch HTML. Die Definition ist ziemlich vage und es ist sinnlos, darüber zu streiten.
Genau genommen ist SQL jetzt eine vollständige Sprache, da der neueste SQL-Standard die "Persistent Stored Modules" (PSMs) enthält. Kurz gesagt, ein PSM ist die Standardversion der PL / SQL-Sprache in Oracle (und anderen ähnlichen prozeduralen Erweiterungen des aktuellen DBMS).
Mit der Einbeziehung dieser PSMs wurde SQL vollständig
Eine ANSI-Select-Anweisung, wie sie ursprünglich in SQL-86 definiert wurde, ist nicht vollständig, da sie immer beendet wird (mit Ausnahme von rekursiven CTEs und nur, wenn die Implementierung eine beliebig tiefe Rekursion unterstützt). Es ist daher nicht möglich, eine andere Turingmaschine zu simulieren. Gespeicherte Prozeduren sind vollständig, aber das ist Betrug ;-)
Die TSQL ist Turing Complete, weil wir in TSQL einen BrainFuck- Interpreter erstellen können.
BrainFuck-Interpreter in SQL - GitHub
Der bereitgestellte Code arbeitet im Arbeitsspeicher und ändert keine Datenbank.
quelle
https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question
Ist eine Diskussion zu diesem Thema. Ein Zitat:
quelle
Genau genommen ist SQL jetzt eine vollständige Sprache, da der neueste SQL-Standard die "Persistent Stored Modules" (PSMs) enthält. Kurz gesagt, ein PSM ist die Standardversion der PL / SQL-Sprache in Oracle (und anderen ähnlichen prozeduralen Erweiterungen des aktuellen DBMS).
Mit der Einbeziehung dieser PSMs wurde SQL vollständig
quelle
Eine ANSI-Select-Anweisung, wie sie ursprünglich in SQL-86 definiert wurde, ist nicht vollständig, da sie immer beendet wird (mit Ausnahme von rekursiven CTEs und nur, wenn die Implementierung eine beliebig tiefe Rekursion unterstützt). Es ist daher nicht möglich, eine andere Turingmaschine zu simulieren. Gespeicherte Prozeduren sind vollständig, aber das ist Betrug ;-)
quelle
Oracle PLSQL und Microsoft TSQL sind beide vollständig. Die select-Anweisung von Oracle selbst ist ebenfalls vollständig.
quelle