On 14 Jun 2015, at 4:09pm, James K. Lowden <jklowden at schemamania.org> wrote:
> Simon Slavin <slavins at bigfraud.org> wrote: > >> There are plenty of queries which can be expressed in a SQL database >> but can't be answered without a computer which can reprogram itself > > Are there? Do you mean there are SQL queries like that? Or do you > mean there are such queries that could be asked of a relational database > but cannot be expressed in SQL? I was a little loose in my language. There are queries which can be expressed in terms of tables of rows of columns, with numbers and text in them. E.g "Jane is four years old, Derek was twice Jane's age last time there was a Winter Olympics. If Derek's dog is white with black spots how much does Jane's mother earn per year ?" There are some queries where you can figure out a schema to store data to express the situation, but you can't figure out any combination of database massaging commands (INSERT/UPDATE/DELETE) and a final SELECT that will fetch the answer you want. > There are queries that cannot be formulated in first order predicate > logic, and recursion is the single capability of SQL that exceeds > FOPL power. Unless the recursion is circular, I don't see how an SQL > query over a finite database could fail to terminate. The Termination Problem is not about whether a SQL query terminates, but whether a program in another language terminates. Suppose you have a TABLE of lines of a program in your favourite toy programming language: row 1 of the table is line 1 of the program, row 2 of the table is line 2 of the program, etc.. The programming language can be any reasonably complicated one. BASIC, PASCAL, Java, JavaScript, whatever. The task is to write some SQL code, including as many INSERT/UPDATE/DELETEs as you want to make other tables with information about the program, with a final SELECT which returns TRUE if and only if the program will halt. Simon.
