2

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

closed as off-topic by mustaccio, Mr.Brownstone, Md Haidar Ali Khan, Max Vernon, MDCCL Oct 31 '18 at 0:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Too localized - this could be because your code has a typo, basic error, or is not relevant to most of our audience. Consider revising your question so that it appeals to a broader audience. As it stands, the question is unlikely to help other users (regarding typo questions, see this meta question for background)." – mustaccio, Mr.Brownstone, Md Haidar Ali Khan, Max Vernon, MDCCL
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 '12 at 13:13
  • 2
    Related: Is SQL or even TSQL Turing Complete? – GSerg Feb 5 '12 at 14:33
  • 4
    There are also recursive WITH queries (CTE) to implement loops of any kind in pure SQL. – Erwin Brandstetter Feb 5 '12 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 '12 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 '12 at 18:46
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'.

6

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.

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.

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-)

  • 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 '12 at 18:46

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