2

I know loops cannot be expressed in standard SQL. What other forms of processing can it not perform?

Improve this question
6
  • 6
    You ask "What computations?" but your example of loops is a programming construct rather than a specific computation. AFAIK cursors are standard SQL and they are just loops. Additionally a cross joined view or CTE with ROW_NUMBER can simulate a finite loop.
    – Martin Smith
    Feb 5, 2012 at 13:13
  • 2
    Related: Is SQL or even TSQL Turing Complete?
    – GSerg
    Feb 5, 2012 at 14:33
  • 4
    There are also recursive WITH queries (CTE) to implement loops of any kind in pure SQL.
    – Erwin Brandstetter
    Feb 5, 2012 at 15:47
  • 1
    Is this purely theoretical? Every SQL implementation has their own "sauce" to consider when looking at what you can/cannot do.
    – atxdba
    Feb 5, 2012 at 17:59
  • 2
    I'm not entirely sure this is a completely objective question. Are you looking for a list of things that can or can not be done in SQL?
    – jcolebrand ♦
    Feb 5, 2012 at 18:46

4 Answers 4

Reset to default
7

I think it's probably appropriate here to note that relational algebra <> SQL. Relational algebra (the theoretical underpinnings of relational databases described in Codd's paper 'A relational data model for large shared data banks') is not Turing complete. The model has the property of Godel completeness, which makes it equivalent in expressive power to first order predicate calculus - ordinary logical expressions to you and me.

However, most SQL dialects have various constructs including recursive CTEs and flow control in stored procedures which make them effectively Turing complete. A Turing complete language can express any computation that can be described algorithmically.

It's worth noting that the strict definition Turing completeness requires infinite storage, which is not physically possible. However, this requirement is often relaxed informally when describing programming languages as Turing Complete.

Improve this answer
6

loops cannot be expressed in standard SQL

That is not the case. The relevant part of the Standard is known as SQL/PSM (Persistent Stored Modules). Its procedural paradigm includes 'loops'.

However, consider that core Standard SQL has been relationally complete (by Codd's definition of that term) since at least SQL-92, allowing for 'computations' of arbitrary complexity. Also that a SQL query is more like a specification than an implementation i.e. states the intent for the DBMS to carry out as it sees fit which may itself involve 'looping'.

Improve this answer
3

If we consider queries in relational algebra which cannot be expressed as SQL queries then there are at least two things SQL cannot do. SQL has no equivalent of the DEE and DUM relations and cannot return those results from any query. Projection over the empty set of attributes is therefore impossible.

There are also other things for which SQL has no direct and general purpose equivalent. You may be able to write equivalents of them for given tables with known keys or columns or known data but SQL has no syntax for a single query that always works for any given table or tables (something which would be possible in relational algebra). E.g.: Relational Division, Relational Comparison, Multiple Assignment.

SQL is therefore much more complex but significantly less powerful than the relational algebra.

Improve this answer
1

Since any processing can be narrowed to simple arithmetic operations, there is no any processing not available to sql.

But if you ask about realtime processing, quantum physics and so on - its nearly impossible in reasonable time and efforts 8-)

Improve this answer
1
  • 2
    I believe you meant to include that SQL is shown to be turing complete, thus any processing that can be reduced to simple arithmetic ops can be done in SQL.
    – jcolebrand ♦
    Feb 5, 2012 at 18:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.