Are SQLScript and HANA SQL turing complete?

[patricksteffens]

In a forum, I read that SQL92 is not turing complete, however languages like T-SQL and PL/SQL are (unfortunately there is no evidence given).

So I was wondering: is SQLScript also turing complete? Intuitively, I would argue for yes. However, I haven't found any evidence or formal proof for that.

Another thought is, that SQLScript extends HANA SQL, so if HANA SQL was turing complete, I'd assume that SQLScript is, too.

Can anyone confirm of reject this with a good explanation and (if possible) an evidence?

[lbreddemann · Accepted solution]

Alright, let's do this! (even though I don't have an idea why it would matter at all...)

So, I'm not a computer scientist, and only a third through " The Annotated Turing" (which seems to be a great book, btw). This means what follows is the layman's approach on this.

First off, I had to understand, what is meant by "turing complete" and how to show that a language has that characteristic.

For that, there are a couple of Wikipedia entries and SO discussions available and I leave that for everyone to read (e,g, here, here). One of those discussions linked to a presentation that claimed to prove that PostgreSQL-SQL with recursive common table expressions (CTS) is turing complete. In order to prove this, the author of the presentation ( here btw) said, it's enough to prove that a language can emulate another language that has already been shown to be turing complete. Fair call.
The author's choice was a "cyclic tag system" with a specific rule set ( Rule 110) which apparently has been shown to be turing complete.
Then the author goes on and implements this cyclic tag system with a recursive common table expression and thereby proves the claim.

Yippie.

So, what does that mean for SAP HANA SQL? SAP HANA SQL/SQLScript does not support recursive common table expressions (much to the distaste of everyone who tries to handle hierarchies and does not know about SAP HANA's special hierarchy views and functions (look there) and it also does not support recursive procedure calls.

Bummer, one might think.
Fortunately, every recursion can be expressed as an iteration (compare here), so I thought, let's try this cyclic tag system in SQLScript. This is the result (HANA 1, rev.122.15, on my NUC):

do begin
declare prods VARCHAR(4) ARRAY;
declare currProd, initWord, currWord VARCHAR(300);
declare runs, maxruns bigint = 0;
declare currProdNo integer = 0;
    initWord :='11001';
    maxruns := 100;
    runs := 0;
    prods = ARRAY ('010', '000', '1111');
    currWord := :initWord;
    
    -- dummy table var to monitor output
    tmp = select :runs as RUNS, :currProd as CURRPROD, :currWord as CURRWORD 
    from dummy;

    while (:runs < :maxruns) DO
        runs := :runs +1;
        
        currProdNo :=  mod(:runs, 3)+1;
        currProd := :prods[:currProdNo];

        if (left (:currWord, 1) = '1') then 
             -- add current producer   
            currWord := :currWord || :currProd;
        end if;
        
        -- remove leftmost character
        currWord := substring (:currWord, 2); 

        -- save current state into temp table var
        tmp = select RUNS, CURRPROD, CURRWORD from :tmp
              union all 
              select :runs as RUNS, :currProd as CURRPROD, :currWord as CURRWORD 
              from dummy;
    end while;
    -- output the table var
    select * from :tmp;
end;

Running this gives the following output:

RUNS CURRPROD CURRWORD                     
0   ?       11001
1   000     1001000
2   1111    0010001111                   
3   010     010001111                     
4   000     10001111                     
5   1111    00011111111                   
6   010     0011111111                   
7   000     011111111                     
8   1111    11111111                     
9   010     1111111010                   
10  000     111111010000                 
11  1111    111110100001111               
12  010     11110100001111010             
13  000     1110100001111010000           
14  1111    1101000011110100001111       
15  010     101000011110100001111010     
16  000     01000011110100001111010000   
17  1111    1000011110100001111010000     
18  010     000011110100001111010000010   
19  000     00011110100001111010000010   
20  1111    0011110100001111010000010     
21  010     011110100001111010000010     
22  000     11110100001111010000010       
23  1111    11101000011110100000101111   
24  010     1101000011110100000101111010 
25  000     101000011110100000101111010000
...

That looks suspiciously like the output from the Wikipedia link (above) and does not seem to stop (except for the super-clever "maxruns" variable 🙂 ).

With that, I'd say, it's possible to create a cyclic tag system rule 110 with SQLScript. The tag system is turing complete, therefore SQLScript must be turing complete.

Still, I have no idea why this would matter at all and that's really all I can say/write about this.

Cheers,

Lars

[patricksteffens · Accepted solution]

Thanks for that stunning answer 🙂 Actually, I'm writing my Master's thesis and came across a point where I needed to reason about the computability of SQLScript code fragments.

In turn, this question came into my mind and I thought, it would be placed best on this platform. Turned out, I was right 😛