Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

migrated from Feb 7 '12 at 21:45

This question came from our site for professional and enthusiast programmers.

A nice question for a database exam. – Pavel Shved Mar 27 '10 at 14:59
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. – Jörg W Mittag Mar 27 '10 at 15:55
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. – Jörg W Mittag Mar 27 '10 at 15:56

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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