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?
 A: 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:
$$ \left\{ \left\langle A, B, C \right\rangle \mid \left\langle A, B, C \right\rangle \in \mathbb{R} \land A = x\right\} $$
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 \mathbb{R}.\mathbb{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):
$$
\begin{aligned}
0 &= \lambda q\mathbb{R}.\mathbb{R} \\
1 &= \lambda q\mathbb{R}.q \;\; \mathbb{R} \\
2 &= \lambda q\mathbb{R}.q \;\; \left(q \;\; \mathbb{R} \right) \\
3 &= \lambda q\mathbb{R}.q \;\; \left(q \;\; \left(q \;\; \mathbb{R} \right)\right)
\end{aligned}
$$
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?
