SQL 또는 TSQL 튜링이 완료되었습니까?

SQL 또는 TSQL 튜링이 완료되었습니까?

이것이 오늘 사무실에 올라왔습니다.그런 일을 할 계획은 없지만 이론적으로는 SQL로 컴파일러를 작성해주실 수 있나요?언뜻 보기에 그것은 많은 종류의 문제들에 대해 극도로 번거롭긴 하지만 완전한 것처럼 보입니다.

만약 튜링이 완전하지 않다면, 그렇게 되기 위해서는 무엇이 필요합니까?

참고: 저는 SQL로 컴파일러를 쓰는 것과 같은 일을 하고 싶지 않습니다. 그렇게 하는 것이 어리석은 일이 될 것이라는 것을 알고 있기 때문에 그 논의를 피할 수 있다면 감사하겠습니다.

SQL은 PL/SQL 또는 PSM과 같은 진정한 '스크립트' 확장이 없어도 튜링 컴플리트(Turing Complete)가 될 수 있음이 밝혀졌습니다.

이 슬라이드 세트에서 Andrew Gierth는 CTE 및 Windowing SQL을 사용하여 Turing Complete임을 입증한 순환 태그 시스템을 구성하여 Turing Complete임을 증명합니다.그러나 CTE 기능은 중요한 부분입니다. 이 기능을 사용하면 자신을 참조할 수 있는 명명된 하위 식을 생성하여 문제를 재귀적으로 해결할 수 있습니다.

주목할 점은 CTE가 SQL을 프로그래밍 언어로 바꾸기 위해 실제로 추가된 것이 아니라는 것입니다. 단지 선언적 쿼리 언어를 더 강력한 선언적 쿼리 언어로 바꾸기 위해서입니다.메타 프로그래밍 언어를 만들기 위한 것이 아니었음에도 불구하고 템플릿이 튜링으로 완성된 것으로 밝혀진 C++와 유사합니다.

아, SQL 예제에 있는 만델브로도 매우 인상적입니다 :)

주어진 프로그래밍 언어는 튜링 기계와 계산적으로 동등하다는 것을 보여줄 수 있다면 튜링-완전이라고 합니다.

TSQL에서 BrainFuck 인터프리터를 만들 수 있기 때문에 TSQL은 Turing Complete입니다.

SQL의 BrainFuck 인터프리터 - 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

https://web.archive.org/web/20110807062050/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는 하나이지만 HTML과 마찬가지입니다. 그 정의는 다소 모호하며 논쟁하기에는 무의미한 것입니다.

엄밀하게 말하면 최신 SQL 표준에 PSM(Persistent Storeed Modules)이 포함되어 있기 때문에 SQL은 이제 튜링 완전한 언어가 되었습니다.간단히 말해서, PSM은 Oracle에서 PL/SQL 언어의 표준 버전입니다(그리고 현재 DBMS의 다른 유사한 절차 확장).

이러한 PSM이 포함되면서 SQL은 turing complete가 되었습니다.

원래 SQL-86에서 정의된 ANSI 선택 문은 항상 종료되기 때문에 완전하지 않습니다(재귀적 CTE를 제외하고는 임의로 심층 재귀를 지원하는 경우에만 해당).따라서 다른 튜링 기계를 시뮬레이션할 수 없습니다.저장 프로시저는 튜링 완료이지만 부정행위 ;-)

간단히 다음 쿼리를 실행합니다.

select * 
from (SELECT 0 union SELECT 1) 
JOIN (SELECT 0 union SELECT 1) 
JOIN (SELECT 0 union SELECT 1)  
JOIN (SELECT 0 union SELECT 1)  
JOIN (SELECT 0 union SELECT 1) 
JOIN (SELECT 0 union SELECT 1)  
JOIN (SELECT 0 union SELECT 1) 
JOIN (SELECT 0 union SELECT 1) 

그리고 당신은 8자리 숫자의 처음 256개의 숫자를 생성할 것입니다.이제 SELECT, AND, OR의 조합을 사용하면 모든 8비트 기계를 쓸 수 있습니다.

관련된 테이블이 없는 것처럼 선택, 결합 및 가입만 하면 됩니다.

제가 보기엔 튜링이 완전한 것 같네요

튜링 컴플리트리티가 무엇인지, 튜링 컴플리트 언어를 구성하는 것이 무엇인지에 대해 일반 대중들 사이에 많은 혼란이 남아 있습니다.저는 이러한 오해를 해소하기 위해 블로그에 글을 올렸는데, 즉 초지능 컴퓨터에 관한 TV 프로그램을 봤는데 정말 유용한 비유를 보여주었습니다.

https://github.com/ubuvoid/writings/blob/main/miller/miller_is_sql.md

이번 답변에서는 SQL의 경우에 대해 자세히 설명하겠습니다.

SQL이 튜링-컴플리트(Turing-Complete)인지 판단하기 위해 한 눈에 필기 후에 우리는 사실 충분한 정보를 가지고 있습니다.

분기 선택("CASE IF THEN")을 위한 어포던스가 있기 때문이며, 재귀를 제한하는 SQL 방언에서도 출력을 테이블에 기록하고 메모리 레지스터인 것처럼 후속 쿼리에서 다시 읽는 것은 사소한 일이기 때문입니다.따라서 SQL에서 어셈블리 언어에 대한 인터프리터를 별도의 고민 없이 구현할 수 있습니다.최소한의 노동력으로 이를 입증하려면 'subleq'와 같은 연산을 가진 단일 명령어 세트 컴퓨터를 구현합니다(https://en.wikipedia.org/wiki/One-instruction_set_computer 참조).

일부 구현이 SQL 쿼리에 대한 샌드박스 실행을 시도한다는 사실은 언어의 핵심 기능을 변경하는 것이 아니라 선의의 "편리함" 기능이 칼처럼 잘라버리는 경향이 있다는 문제에 대해 반창고를 붙일 뿐입니다.

시연을 위해 다음을 고려합니다.

• 제한된 실행 "비-튜링 컴플리트 SQL 인터프리터"가 있다고 가정해 보겠습니다. 이 인터프리터는 단일 쿼리 또는 업데이트 작업만 한 번에 실행할 수 있고 해당 쿼리에 제한을 가하는 종류입니다.
• 자, 쉘에서 그 통역사를 호출할 수 있다고 하세요.
• 마지막으로 셸에서 이 SQL 인터프리터를 실행하기 위해 명령 위에 "while true:"라는 단어를 입력한다고 가정합니다.이제 튜링을 완벽하게 실행할 수 있습니다.

이것이 의미있는 구별입니까?만약 당신의 언어와 튜링 완전성 사이의 유일한 차이점이 while loop이 없다는 사실이라면, 튜링 완전성을 해석하는 당신의 틀은 특별히 유용하지 않다고 주장하고 싶습니다.

Non-Turing Complete 언어가 널리 사용되고 있으며, 데이터 아티팩트를 "비활성화"하는 경향이 있으며 분기 경로 또는 명시적 프로시저 호출에 대한 어포던스가 부족합니다.간단히 말해, 언어에 "동사"가 없거나 "만약 그 외의 경우"와 동등한 언어가 없으면 "Non-Turing Complete"임을 확인할 수 있습니다.예를 들어 인터페이스 정의 언어(DIANA IDL, CORBA, Proto, Srift, JSON Typedef, Coral, Ion 등), 마크업 언어(XML, HTML, Markdown), 데이터 표현 언어(JSON, 텍스트 형식 프로토콜 버퍼, asci DIANA 표현) 등이 있습니다.

관심사 분리를 달성하기 위해 소프트웨어 아키텍처의 전략적 부분에서 튜링-완전 실행에 제한을 가하는 것이 종종 유용하며, 비TC 언어는 그러한 보장을 위한 간단하고 강력한 수단을 제공합니다.

대표적인 예로 HTTP 또는 RPC 요청/응답에서 JSON 페이로드 또는 기타 데이터 아티팩트의 스키마를 검증하는 것을 들 수 있는데, 이는 IDL 및 코드 템플릿을 사용하여 자동화할 수 있는 노동 집약적이고 오류가 발생하기 쉬운 작업입니다.

인공물을 계속 순환시켜요.

(편집 2022/04/08: 재미있는 사실.아마존은 위에 언급된 IDL 중 하나가 아니라 두 개의 IDL을 발명한 것과 동시에 페이스북에서 발명된 세 번째 IDL을 사용했다는 의심스러운 특징을 가지고 있습니다.인터페이스 정의 언어의 주된 목적은 인터페이스를 정의하는 것이므로 하나의 IDL을 다른 IDL로 변환하기 위한 IDL이 있으면 좋겠습니다.한 동료는 아마존의 소프트웨어 인프라를 파리 하수구와 비교했습니다.)

오라클의 PLSQL과 마이크로소프트의 TSQL이 모두 완성되었습니다.오라클의 셀렉트 스테이트먼트 자체도 튜링 완료입니다.

언급URL : https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete