Is SQL or Even Tsql Turing Complete

Is SQL or even TSQL Turing Complete?

It turns out that SQL can be Turing Complete even without a true 'scripting' extension such as PL/SQL or PSM (which are designed to be true programming languages, so that's kinda cheating).

In this set of slides Andrew Gierth proves that with CTE and Windowing SQL is Turing Complete, by constructing a cyclic tag system, which has been proved to be Turing Complete. The CTE feature is the important part however -- it allows you to create named sub-expressions that can refer to themselves, and thereby recursively solve problems.

The interesting thing to note is that CTE was not really added to turn SQL into a programming language -- just to turn a declarative querying language into a more powerful declarative querying language. Sort of like in C++, whose templates turned out to be Turing complete even though they weren't intended to create a meta programming language.

Oh, the Mandelbrot set in SQL example is very impressive, as well :)

T-SQL is Turing complete : What does this mean, exactly?

"Turing Complete" has a technical meaning, but the term is usually used as a shorthand for "you can write code to do arbitrary logic in this" (such as business logic) as opposed to "you can only use this for limited tasks" (like selecting XML nodes with XPath).

No actually existing modern language is truly Turing complete because Turing-completeness requires infinite memory, which modern computers do not have.

As explained in the Wikipedia entry, all that is really needed for a turing-complete language is the ability to store and retrieve variables, and some sort of conditional execution based on retrieved values. Such a language can be exceedingly difficult to use. Joke languages have been created on this basis.

• https://en.wikipedia.org/wiki/Turing_completeness

To summarize: A language is Turing complete if it can compute every function that a Turing machine can. Alternatively, if it can be used to write an emulator of a single-tape Turing machine.

Turing complete graph query languages

I'm not sure about what you include in the etc..
But I think your statement is correct. As you say that you are not looking for edge cases or exotic manipulation of the language.

1. Cypher is not turing complete
2. SQL is not properly t.c.
3. By any practical definition, SPARQL is not t.c.
4. Datalog is not t.c.
5. AQL is more or less as powerful as standard SQL

Yet, we should not look at turing completeness as a must-have feature. The power of declarative query languages is that the hard work is done by the system, while the user just describes what they are looking for. This has the added advantage that the system is able to find optimized plans to get to the right information.

What is Turing Complete?

Here's the briefest explanation:

A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).

So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.

Sometimes it's a joke... a guy wrote a Turing Machine simulator in vi, so it's possible to say that vi is the only computational engine ever needed in the world.

What are the differences between T-SQL, SQL Server and SQL

SQL is the basic ANSI standard for accessing data in a relational database. When you see "MSSQL" it is referring to Microsoft SQL Server, which is the entire database architecture and not a language. T-SQL is the proprietary form of SQL used by Microsoft SQL Server. It includes special functions like cast, convert, date(), etc. that are not part of the ANSI standard.

You will also see things like plSQL, which is Oracle's version of SQL, and there are others as well (mySQL has its own version, for example, and Microsoft Access uses Jet SQL.)

It is important to note the the ANSI standard for SQL has different releases (for example, 92 or 99, representing the year it was released.). Different database engines will advertise themselves as "mostly ANSI-92" compliant or "fully ANSI-99" compliant, etc, and any exceptions will usually be documented.

So although "SQL is SQL", every engine uses its own "flavor" of it, and you do have to do a little reading on the particular platform before you just dive in.

A further note - the SQL extensions, like T-SQL, are generally considered full-fledged programming languages, complete with looping, if/then, case statements, etc. SQL itself is limited to simply querying and updating data and is not considered a true programming language.

Wikipedia has a decent article for an overview here:
http://en.wikipedia.org/wiki/SQL

Which generation of languages does SQL belong to?

SQL tries to be a 5GL, by allowing the user to express their intent at a high level of abstraction while leaving the determination of an algorithm for achieving the intent up to the engine.

Unfortunately, due to various deficiencies in the language, it falls far short of that goal.

How similar are Relational Database Languages and Logic Programming?

Similarities are captured by Datalog query language. Here is motivation and better explanation of connection between logic and databases. This excerpt should address your question:

Nevertheless, coupling Prolog and relational databases show some
dissonances. Facts and rules in Prolog are organized in a total order
and the semantics of a Prolog program depends on this order. In
contrast, relations in a database are considered as unordered sets of
tuples and the result of a query is independent from any physical
order. The processing of Prolog programs is tuple oriented while
relational databases are set oriented. Prolog offers procedural
features like the cut predicate to allow the programmer to control the
inference process. The order of evaluation of a Prolog program is
pre-determined, whereas expressions in relational calculus are purely
declarative and the actual evaluation is left to a query processor
which may rearrange the query for optimization purposes. Optimization
of queries was crucial for the success of relational databases. The
procedural nature of the Prolog engine leaves the burden of
optimization with the programmer.

Can a language be turing complete but incomplete in other ways?

No. or at least if you found one that would be a disproof of the Church Turing Thesis.

However, there are languages that are Turing complete but in which it is a complete pain in the ass to write certain programs, i.e., string processing in FORTRAN, numerical programming in COBOL, integer arithmetic in sed, practically everything in x86 assembler.

And then of course there's brainfuck.

---

Related Topics