I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete.

Probably just recursion (something like "MY_QUERY(param) = select * from param UNION MY_QUERY(DO_SOMETHING_WITH(param))"). But I don't see how I could define aggregate functions with this.

Any idea?

  • 1
    $\begingroup$ Why are you asking? What is the context/motivation for your question? What makes you think there exists a unique minimal set of such features? $\endgroup$
    – D.W.
    Sep 30, 2013 at 6:37
  • $\begingroup$ Because it would be nice to have such language. I particularly would implement it in a web scraper application I work on, but I'm sure it could have many other uses. I'm not sure there is a unique minimal but there is a minimal for sure. $\endgroup$
    – Juan
    Sep 30, 2013 at 6:55
  • $\begingroup$ My suggestion would be to identify the requirements for what you need for your web scraper, and ask about that (making sure to motivate those requirements realistically). I think this site does better with questions that are motivated by a real need. As it is, the question feels artificial to me. (For instance, I don't see a clear reason why minimality is of the essence, nor why you care about Turing-completeness rather than "usefulness in practice".) $\endgroup$
    – D.W.
    Sep 30, 2013 at 7:15
  • $\begingroup$ The requirements are really just that. The language should be as simple as possible, so less features are preferred, and the reason why I care about turing completeness is the same reason any programming language cares about it: so that I know users can program the application to do anything they want to do with the data they scrape. I don't see how would this not be useful for many other cases too. $\endgroup$
    – Juan
    Sep 30, 2013 at 7:32
  • 1
    $\begingroup$ This question has produced extensive research, starting in 1979 and continuing to this day. I'm familiar with only a fraction of it, and it's a little difficult for me to summarize. Very briefly: there is no minimal extension, and it's not very obvious which criteria you would want such an extension to meet. For instance, the extension shouldn't be too expressive, if you still want the results of queries to be computable; efficiently, if possible. $\endgroup$ Sep 30, 2013 at 9:24

1 Answer 1


You need just two things: new values and recursion/while.

New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that.

Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE RECURSIVE feature of SQL is one such.

SQL with CTE RECURSIVE is Turing Complete (without stored procedures).

See the Alice book http://webdam.inria.fr/Alice/ for a detailed treatment.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.