My understanding about Codd's concept of "safe queries" was created to ensure that a query would always terminate. One key ability of a Turing machine is that it can work on infinite calculations (and thus isn't guaranteed to terminate). If the safe query restriction were removed, would relational calculus be Turing-complete since that means it doesn't have to terminate?

  • $\begingroup$ A nice question for a database exam. $\endgroup$ – Pavel Shved Mar 27 '10 at 14:59
  • 3
    $\begingroup$ Nice question! BTW: David Fetter of PostgreSQL recently sketched out an embedding of a Cyclic Tag System (which is known to be Turing-complete) in pure SQL:2008, thus proving that it is Turing-complete. (The missing pieces compared to earlier versions were Common Table Expressions and Windowing.) Note: I am well aware of the fact that SQL and the Relational Calculus are very different, but I thought it would be an interesting datapoint. $\endgroup$ – Jörg W Mittag Mar 27 '10 at 15:55
  • 3
    $\begingroup$ Another thing: just because something allows writing non-terminating programs, that doesn't necessarily mean it's Turing-complete. Example: a programming language that has an infinite loop as its only construct. $\endgroup$ – Jörg W Mittag Mar 27 '10 at 15:56
  • 6
    $\begingroup$ First question of MSE! $\endgroup$ – Maximilian Janisch Oct 2 '19 at 21:55

I don't know if this is correct, but I have a hypothesis. If we allowed free variables in the formula, then we could think of queries as functions. For example, consider the following query:

{ <A, B, C> | <A, B, C> \in R and A = x}

If the above query has a result M, we can consider that to be a function of the form lambda x.M. If we allow relations to be free variables, we can define a function of the form lambda R.R. Now, if we allow "higher-order queries", ie queries that can query queries, we can represent the Church numerals (with q being a query):

0 = lambda qR.R
1 = lambda qR.q R
2 = lambda qR.q (q R)
3 = lambda qR.q (q (q R))

Therefore, I think that relational calculus can also be a lambda calculus, and therefore be Turing-complete. Can anyone tell me if I'm on the right path?

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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