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.com Feb 7 '12 at 21:45
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:
If the above query has a result M, we can consider that to be a function of the form
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?