SQL Turing Completeness question | Tech Off

Shining Arcanine

Is SQL turing complete with stored procedures? More interestingly, is SQL turing complete without stored procedures? Also, is/should SQL be considered a computer programming language?

I am curious about this as the answer to the last question will determine whether I know 7 computer programming languages or 8. Specifically, I know PHP, SQL, SML, C, C++, Java, Assembly and Fortran. That is approximately the order in which I learned them, although I learned some languages simultaneously and others took longer to learn than others. Also, I am considering both x86 assembly and MIPS assembly to be the same language.

Sven Groot
You can't have everything; after all, where would you put it?

I think you need to rephrase your question a bit. Stored procedures don't really have anything to do with it.

SQL as such (i.e. the SQL92 standard) is not turing complete. However, many of the languages derived from SQL, such as Oracle's PL/SQL and SQL Server's T-SQL and others are turing complete.

PL/SQL and T-SQL certainly qualify as programming languages, whether SQL92 itself qualifies is open for debate. Some people claim that any piece of code that tells a computer what to do qualifies as a programming language; by that definition SQL92 is one, but so is e.g. HTML. The definition is rather vague, and it's imo a pointless thing to argue about.

Fun fact: C++ templates provide a turing complete language, which is executed at compile time, such as the following code which computes the greatest common divisor at compile time (not run time):

template<int x, int y>
struct gcd 
{
    static const int Value = gcd<x, x % y>::Value;
};

template<int x>
struct gcd<x, 0> 
{
    static const int Value = x;
};

evildictaitor
How could you use the adjective "indescribable" truthfully?

In reply to Sven Groot

#Oct 6th @ 10:15 PM

You are a bad bad man, Sven.

Also I would argue that number of languages known is a fairly bad assessment of the quality of the programmer. Number of different paradgms of coding, perhaps, or total years of experience programming; but fluency in one or two computer languages is much more important.

For example, you say MIPS assembly, but if I asked you to write a general matrix multiplier in it, would you be able to?

Shining Arcanine

In reply to evildictaitor

#Oct 7th @ 5:56 AM

I am not sure what is more sad, the fact that I know MIPS assembly or the fact that I can actually do that. I would of course need to know the calling convention and the format of which the matrix is stored. I am taking a class on it right now.

I took Introduction to Linear Alegbra a few years ago and I still remember the general algorithm for the multiplication of matrices. I could write an algorithm for the multiplication of an infinite number of matrices (well practically infinite), provided a pointer to an array of pointers to matrices, the format in which the matrices are stored and the size of the matrices (all matrices must be the same size), plus the calling convention that the function is expected to use. I probably could define these things myself though. For example:

int * matrixMul ( int size, int * a, int * b, ... );

Where a, b and all succeeding matrices are allocations of length size squared that are to be multiplied and the function returns an a pointer to an allocation of length size squared containing the result. Also all values in the allocations would be located as defined by their indices (numbered from i = 0 to size - 1), where i % size gives the row position and i / size gives the column position, with the upper left of the matrice being position (0, 0). A disclaimer would be necessary as a * b != b * a when multiplying matrices.

I would have to pull out of my C book (by Kernighan and Richie) to look up how variable function parameter lists work in C to get an idea of what the calling convention should be, but I assume that would be left for me to define (and me to fix should something else be in use).

By the way, would MySQL 5.0 be considered a programming language, as the specific dialect of SQL I know is MySQL (it went well with PHP)?

Sven Groot
You can't have everything; after all, where would you put it?

In reply to Shining Arcanine

#Oct 7th @ 6:19 AM

By the way, would MySQL 5.0 be considered a programming language

By whom? Like I said, there are about as many definitions of what constitutes a programming language as there are programmers. The distinction is completely meaningless in the real world.

evildictaitor
How could you use the adjective "indescribable" truthfully?

In reply to Shining Arcanine

#Oct 7th @ 6:19 AM

For __cdecl it's

push ebp

mov ebp, esp

add esp (size of stack)

...

pop ebp

ret

where arguments are pushed and cleaned by caller. The 'n'th argument is on [esp + 4*(n+1)] and the 'n'th local is on [esp - 4*n], assuming all locals are sizeof(void*) long. __cdecl also has the restriction that it returns on EAX and does not modify EBX, ESP, EBP, EIP or EFLAGS over the function call. All other registers are saved by the caller if it cares about their value.

Also, by the general formula for matrix multiplication don't you just mean A : R[n,r], B : R[r,m] --> (AB) : R[n,m], (AB)[i,j] = Sum[ i : [0, r], A[i,r] * B[r, j] ]?

With regards to whether or not it's a programming language - most people don't use Turing Completeness as a requirement (nessisary _or_ sufficient) for a syntax to be a programming language. The requirement is usually just the slightly subjective question of whether you can perform and automate meaningful tasks via the syntax. Languages for which is theoretically, but not in practise true, such as BrainF*ck and Shakespeare Programming Language are termed "esoteric programming languages", although strictly one ought to refer to them as esoteric syntaxes, since they arn't in practise used for programming. Under such a definition SQL is clearly a programming language.

It is important to remember that being good at two or three languages is much more important than having a brief overview of ten different ones - so if you feel that you know 7 or 8 programming languages, then you should probably be seeking to become really good at one or two of them (preferably in entirely different paradgms, such as learning C, C# and Haskell), rather than learning any more.

Shining Arcanine

In reply to evildictaitor

#Oct 7th @ 5:09 PM

evildictaitor, you asked for the solution in MIPS assembly. That calling convention is for x86 assembly, not MIPS assembly, which isn't very helpful for doing things in MIPS, although I suppose I could make up my own calling convention for MIPS based on it. Also, I am somewhat confused by how the callee is expected to know how many arguments there are.

Anyway, yes, the number of columns in Matrix A must be equal to the number of rows in Matrix B. My linear algebra class mentioned that and then went onto to never actually use that and instead deal with only square matrices, which is what I thought of multiplying when you posed your question. Taking that into account makes things somewhat more complex (as the number of rows and columns must be stored), but it is doable if you were to designate the 0th word of the start of a matrix to contain the number of rows in its upper half word and the number of columns in its lower half word, with the actual matrix data following that, where the first row would be suceeded by the second row, etcetera.

Also, I don't think that a computer programming language must be turing complete to be a language, but I think that turing completeness implies that it is a computer programming language. In set theory, this would be to say tha the set of turing complete languages is a subset of the set of computer programming languages. If I can state that a language is a turing complete language, I can state as a conseqence of modus ponens that it is a computer programming language.

I do not know all of these languages because learning them was fun and interesting (although in the case of C, learning it certainly was). I know them because I had to know them at a given point in time for one thing or another. If I could choose which to use on a day to day basis, I would choose C, which is my favorite programming language. Here is why I know each language:

PHP - I used to maintain a website (it is still online , but it is not maintained) that I made and I wanted to dynamically generate web pages, so I learned PHP, which is my first programming language.
MySQL - I wanted to store relational information, so I learned MySQL, which went very well with PHP
SML - When I started college, I took a course that was required for the Computer Science major and that course (and its follow-up course) required that I know SML to answer questions on the exams, so I learned SML
C - Well, due to the bureaucratic nature of course prerequisities, it was either this or Python, and I thought I needed to know C++ for scientific computing, which had this as a pre-requisite, so I took a class on this. It only took me 8 hours of reading (split between over two separate days that I spread out over two weeks) to learn this language and it is my favorite, so there.
C++ - I thought I needed to know C++ for scientific computing (which is what I want to do down the road), so I learned C++. I later learned that all scientific computer programs are written in Fortran (ugh)
Java - I was forced into knowing this by the Computer Science department. I would have preferred being forced into learning Microsoft's proprietary C# instead of Sun Microsystems' proprietary Java. Apparently, Java has displaced Cobol as the local business language, which is why the Computer Science department forces it upon people. I have sworn that after college, I will never write another program in this language so long as I live.
Fortran - I needed this for undergraduate research. It is nice to know, but when I am in charge of what language is used to write a scientific program, I am jumping ship to C++.
Assembly (x86) - When I was taking a class on C that wasn't required for my major, I was curious if I could be a better compiler than Visual Studio, so I taught myself a bit of x86 to find out. I found that I could only write assembly that was as good as the compiler, rather than better.
Assembly (MIPS) - The university requires that all Computer Science majors learn this