4 ms·
> Relational algebra is not Turing complete. yes it is > SQL gets Turing completeness by means of various additions/alterations. Sigh. No. SQL was a subset o
by _a_a_a_ 3y ago
> Relational algebra is not Turing complete.
yes it is
> SQL gets Turing completeness by means of various additions/alterations.
Sigh. No. SQL was a subset of relational until recursive CTEs were included to round it off properly.
- hyperpape 3y ago> yes it is Can you double check and/or give references? Because I specifically doubted my memory here, and everything I found online before posting matches what I thought—-standard relational algebra is not Turing-complete (hence relational queries are guaranteed to terminate).
- _a_a_a_ 3y agoFair Q, I may be confusing relational and predicate calculus. Will check and get back. Apologies in advance if I'm wrong.
- _a_a_a_ 3y agoI need to do some more checking, but you are right. The original relational algebra was a subset of first-order predicate logic. Adding recursion I believe just gave it parity with 1st order PL, so fulsome apologies and thanks for pointing out my error.