SQL 또는 TSQL 튜링 완료?

이것은 오늘 사무실에 와서. 나는 그런 일을하는 계획이 없지만, 이론적으로 당신은 SQL에서 컴파일러를 쓸 수 있을까? 언뜻 그러나 매우 많은 문제 클래스에 대한 완전한 성가신 튜링로 나에게 나타납니다.

가 완료를 튜링되지 않으면, 그렇게되기 위해 무엇을 필요로?

참고 : 나는 쓰기와 같은 SQL의 컴파일러를 아무것도 할 욕망이 없다, 나는 우리가 그것을 감사하겠습니다 그 논의를 피할 수 그렇다면,이 할 수있는 어리석은 일이 될 것입니다 알고있다.

해결법

==============================
1.그것은 SQL은 (그래서 사실 프로그래밍 언어로 설계의 좀 바람을 피우고 있다고)도 같은 PL / SQL 또는 PSM 등 진정한 '스크립팅'확장자없이 전체 튜링 수있는 것으로 나타났다.

그것은 SQL은 (그래서 사실 프로그래밍 언어로 설계의 좀 바람을 피우고 있다고)도 같은 PL / SQL 또는 PSM 등 진정한 '스크립팅'확장자없이 전체 튜링 수있는 것으로 나타났다.

슬라이드 세트에서 앤드류 Gierth은 CTE와 윈도우 화 SQL 완료 튜링 것으로 판명 된 순환 태그 시스템을 구축하여, 튜링에 있음을 증명한다. 열팽창 계수 기능은 그러나 중요한 부분이다 - 당신이 스스로를 참조하여 반복적으로 문제를 해결할 수라는 이름의 하위 표현식을 만들 수 있습니다.

단지 더 강력한 선언적 쿼리 언어로 선언적 쿼리 언어를 설정하는 - 참고로 흥미로운 점은 CTE 정말 프로그래밍 언어로 SQL을 설정하는 추가되지 않은 것입니다. 정렬의 C처럼 ++, 누구의 템플릿들이 메타 프로그래밍 언어를 생성하도록 구성되지 않은 경우에도 완전한 튜링으로 밝혀졌다.

아, SQL의 예에서 만델 브로트 집합은 매우 인상적뿐만 아니라입니다 :)

==============================

2.우리는 TSQL에서 브레인 퍽 인터프리터를 만들 수 있기 때문에 TSQL은 전체 튜링된다.

우리는 TSQL에서 브레인 퍽 인터프리터를 만들 수 있기 때문에 TSQL은 전체 튜링된다.

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 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

==============================
3.https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question

https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question

이 주제에 대한 논의입니다. 인용 한 :
==============================
4.최신 SQL 표준 "영구 저장 모듈"(된 PSM)가 포함되어 있기 때문에 엄밀히 말하면, SQL은 이제 튜링 완전한 언어입니다. 짧은에, PSM은 오라클 (현재 DBMS의 다른 유사한 절차 확장)의 PL / SQL 언어의 표준 버전입니다.

최신 SQL 표준 "영구 저장 모듈"(된 PSM)가 포함되어 있기 때문에 엄밀히 말하면, SQL은 이제 튜링 완전한 언어입니다. 짧은에, PSM은 오라클 (현재 DBMS의 다른 유사한 절차 확장)의 PL / SQL 언어의 표준 버전입니다.

이들 된 PSM의 포함으로, SQL이 완료 튜링이되었다
==============================
5.같은 원래 SQL-86에 정의 된 ANSI select 문은 전체 튜링되지 않기 때문에 (재귀 CTE를 제외하고 구현 만 지원하는 임의의 깊은 재귀 경우) 항상 종료. 어떤 다른 튜링 기계를 시뮬레이션하는 것이 불가능하다. 저장 프로 시저가 완료 튜링하고 있지만 그게 전부는 부정 행위 ;-)

같은 원래 SQL-86에 정의 된 ANSI select 문은 전체 튜링되지 않기 때문에 (재귀 CTE를 제외하고 구현 만 지원하는 임의의 깊은 재귀 경우) 항상 종료. 어떤 다른 튜링 기계를 시뮬레이션하는 것이 불가능하다. 저장 프로 시저가 완료 튜링하고 있지만 그게 전부는 부정 행위 ;-)
==============================
6.오라클 PL SQL 및 Microsoft SQL 모두 완료 튜링된다. 오라클의 SELECT 문 자체도 완전한 튜링된다.

오라클 PL SQL 및 Microsoft SQL 모두 완료 튜링된다. 오라클의 SELECT 문 자체도 완전한 튜링된다.

from https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete by cc-by-sa and MIT license

'SQL' 카테고리의 다른 글

[SQL] MySQL을 같이 여러 값 (0)	2020.04.13
[SQL] MySQL의에서 기본 키를 제거 (0)	2020.04.13
[SQL] 테이블에 개최되는 잠금 확인하는 방법 (0)	2020.04.13
[SQL] CTE, 하위 쿼리, 임시 테이블 또는 테이블 변수 사이의 성능 차이가 있나요? (0)	2020.04.13
[SQL] 어떻게 MySQL을 텍스트로 BLOB에서 변환합니까? (0)	2020.04.12

복붙노트

[SQL] SQL 또는 TSQL 튜링 완료?

SQL 또는 TSQL 튜링 완료?

해결법

1.그것은 SQL은 (그래서 사실 프로그래밍 언어로 설계의 좀 바람을 피우고 있다고)도 같은 PL / SQL 또는 PSM 등 진정한 '스크립팅'확장자없이 전체 튜링 수있는 것으로 나타났다.

2.우리는 TSQL에서 브레인 퍽 인터프리터를 만들 수 있기 때문에 TSQL은 전체 튜링된다.

3.https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question

4.최신 SQL 표준 "영구 저장 모듈"(된 PSM)가 포함되어 있기 때문에 엄밀히 말하면, SQL은 이제 튜링 완전한 언어입니다. 짧은에, PSM은 오라클 (현재 DBMS의 다른 유사한 절차 확장)의 PL / SQL 언어의 표준 버전입니다.

6.오라클 PL SQL 및 Microsoft SQL 모두 완료 튜링된다. 오라클의 SELECT 문 자체도 완전한 튜링된다.

'SQL' 카테고리의 다른 글

티스토리툴바