35
$\begingroup$

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?

  • 0
    A nice question for a database exam.2010-03-27
  • 3
    Nice question! BTW: David Fetter of PostgreSQL recently sketched out an embedding of a Cyclic Tag System (which is known to be Turing-complete) in pure SQL:2008, thus proving that it is Turing-complete. (The missing pieces compared to earlier versions were Common Table Expressions and Windowing.) Note: I am well aware of the fact that SQL and the Relational Calculus are very different, but I thought it would be an interesting datapoint.2010-03-27
  • 3
    Another thing: just because something allows writing non-terminating programs, that doesn't necessarily mean it's Turing-complete. Example: a programming language that has an infinite loop as its only construct.2010-03-27

1 Answers 1