Is SAP HANA SQL/SQLScript Turing complete?

There was an interesting (aka nerdy) question in the SAP Community Q&A the other day:
Are SQLScript and HANA SQL Turing complete?”

I took a swing at it and the following is my result (a slightly edited version of my original answer).


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 and 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) said, that 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 system). The SQL code is also available in my GitHub repo.

<br />
do begin<br />
declare prods VARCHAR(4) ARRAY;<br />
declare currProd, initWord, currWord VARC&lt;span data-mce-type=&quot;bookmark&quot; style=&quot;display: inline-block; width: 0px; overflow: hidden; line-height: 0;&quot; class=&quot;mce_SELRES_start&quot;&gt;&lt;/span&gt;HAR(300); -- 300 is arbitrary and would be exceeded for more runs<br />
declare currProdNo integer = 0;<br />
declare runs, maxruns bigint = 0;</p>
<p>	initWord :='11001';                   -- the starting/initial 'word'<br />
	maxruns := 100;                       -- a limit to the number of iterations<br />
                                              -- rule 110 is suspected to run indefinitively<br />
    prods = ARRAY ('010', '000', '1111');     -- the three 'producer rules' stored in a string array</p>
<p>    currWord := :initWord;<br />
    runs := 0;<br />
    -- dummy table var to monitor output<br />
    tmp = select :runs as RUNS, :currProd as CURRPROD, :currWord as CURRWORD<br />
    from dummy;</p>
<p>    while (:runs &amp;lt; :maxruns) DO<br />
        runs := :runs+1;</p>
<p>        currProdNo :=  mod(:runs,3)+1;    -- pick rule no. 1,2 or 3 but never 0<br />
                                          -- as SQLScript arrays are 1 based<br />
        currProd := :prods[:currProdNo];</p>
<p>        if (left (:currWord, 1)='1') then  -- add current producer to the 'word'<br />
            currWord := :currWord || :currProd;<br />
        end if;</p>
<p>        currWord := substring (:currWord, 2); -- remove leftmost character</p>
<p>        -- save current state into temp table var<br />
        tmp = select RUNS, CURRPROD, CURRWORD from :tmp<br />
              union all<br />
              select :runs as RUNS, :currProd as CURRPROD, :currWord as CURRWORD<br />
              from dummy;</p>
<p>    end while;</p>
<p>    select * from :tmp;                      -- output the table var<br />
end;<br />

Running this gives the following output:

<br />
/*<br />
Statement 'do begin declare prods VARCHAR(4) ARRAY; declare currProd, initWord, currWord VARCHAR(300); declare ...'<br />
successfully executed in 7&amp;lt;span data-mce-type=&quot;bookmark&quot; style=&quot;display: inline-block; width: 0px; overflow: hidden; line-height: 0;&quot; class=&quot;mce_SELRES_start&quot;&amp;gt;&amp;lt;/span&amp;gt;17 ms 39 µs  (server processing time: 715 ms 590 µs)<br />
Fetched 101 row(s) in 2 ms 517 µs (server processing time: 0 ms 424 µs)</p>
<p>RUNS    CURRPROD    CURRWORD<br />
0       ?           11001<br />
1       000         1001000<br />
2       1111        0010001111<br />
3       010         010001111<br />
4       000         10001111<br />
5       1111        00011111111<br />
6       010         0011111111<br />
7       000         011111111<br />
8       1111        11111111<br />
9       010         1111111010<br />
10      000         111111010000<br />
11      1111        111110100001111<br />
12      010         11110100001111010<br />
13      000         1110100001111010000<br />
14      1111        1101000011110100001111<br />
15      010         101000011110100001111010<br />
16      000         01000011110100001111010000<br />
17      1111        1000011110100001111010000<br />
18      010         000011110100001111010000010<br />
19      000         00011110100001111010000010<br />
20      1111        0011110100001111010000010<br />
21      010         011110100001111010000010<br />
22      000         11110100001111010000010<br />
23      1111        11101000011110100000101111<br />
24      010         1101000011110100000101111010<br />
25      000         101000011110100000101111010000<br />
[...]<br />
*/<br />

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

3 thoughts on “Is SAP HANA SQL/SQLScript Turing complete?”

  1. It matters because it’s means anything you can do in any other turing complete language can be done in Hana sql script.

    1. Thanks for the comment Matthew.
      I see the general point of turing-completeness as a classification mechanism for programming languages.
      It’s just that in my experience, certain problems – while possible to be solved in, say, SQLScript – just tend to be better dealt with in a different language and that the classes of problems for which SQL/SQLScript are good at are widely known.
      Or the other way around: while turing-complete tells me the about whether a language is generally capable of doing something, it does not give me the slightest hint towards whether or not it would be good at doing it. That makes the whole question rather academic – as in “not relevant to the problem at hand”.

      1. I was typing on my phone so I didn’t elaborate, but what I would have added is that while anything your can write in one Turing complete language can be written in a another (and as a corollary, any computer can emulate any other computer), it ain’t necessarily going to be pretty, efficient or easy!

        In the answer I gave here: https://answers.sap.com/questions/545145/migrating-complex-abap-calculation-logic-to-cds.html?childToView=545157#answer-545157

        it was kind of meta-relevant to the problem at hand, in that I used to try to elicit more information from the questioner about what he was wanting to achieve. But I think I just scared him away… 😉

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.