4 ms·
Relational algebra is not Turing complete. SQL gets Turing completeness by means of various additions/alterations (sometimes pretty weird ones about that). So t
by hyperpape 3y ago
Relational algebra is not Turing complete. SQL gets Turing completeness by means of various additions/alterations (sometimes pretty weird ones about that). So the foundations are pretty different, and I think this is obvious if you tried to start writing typical programs in SQL/Prolog.
Now, some people argue you might want a less expressive logic programming language, especially datalog, so this isn’t a knock-down argument, but it’s a pretty big difference.
- _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.