3 ms·

SQL Turing completeness is generally regarded as a (relatively recent) mistake. MapReduce is only regarded as Turing complete as it is typically programmed usin

SQL Turing completeness is generally regarded as a (relatively recent) mistake. MapReduce is only regarded as Turing complete as it is typically programmed using Turing complete languages. In both cases, the validity of many optimisations would be destroyed by any non-terminating behaviour. You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Perhaps a better example is the humble Regex. If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation.

pron 9y ago
> You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Termination and exponential (or super-exponential) running times are about equally bad. Avoiding either is done on a case-by-case basis. Restricting the language can save you from one and not the other. > If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation. I'm not an expert on regex by any means, but I believe this optimization is exponential (a DFA can be exponential in the size of the regex), and so infeasible in practice. Regardless, as I said, regex is about as far down as we can take computation, and regexps make for a very poor generally useful computational construct.