# Would Relational Calculus be Turing-Complete if it Allowed Unsafe Queries?

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?

-

## migrated from stackoverflow.comFeb 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?

-