Lambda the Ultimate

Yes, OOTP is a great paper and has inspired some projects including m36. https://github.com/agentm/project-m36.
Yes, Rel continues to move along. Worth a catch-up.
No, I don't know much about 'that' Eve. Will look into it.
No, 'K/J' doesn't ring any bells. A link?
Yes, Datalog has many useful ideas.
Daedalus? Solving equations?
Bloom? Disorderly computing?

If succ()+transitive closure gives you Turing Completeness, where would you look for research on that?

With infinite relations, transitive closure, and any simple 'small step' Turing complete model (like cellular automaton), you can query for a future state that meets some criteria (like a halting condition).

K and J are collection oriented programming languages with entries on Wikipedia. K in practice makes heavy use of column structured databases.

For Dedalus, I was referring to the predecessor of Bloom. I actually find it more interesting than Bloom.

Why Transitive Closure, because otherwise relational algebra cannot answer queries like find the least common ancestor (given a table of parent/child relationships). Relational Algebra plus Transitive Closure is computationally complete.

Interestingly logic has equivalent expressive power to relational algebra, and Prolog has recursion, so the pure variant of Prolog is effectively relational algebra plus Transitive Closure. So if you are looking for a declarative query language that is Turing complete and has minimal syntactic overhead then Prolog (or Datalog) is the answer.

If you consider that Prolog only has clause definition as its only syntax, that is pretty amazing expressive power.

Pure Datalog (without negation) is equivalent to relational algebra without set difference and with added recursive queries. In this case all queries terminate (in exponential time), so it is not Turing complete. Adding back in negation (whether stratified, well-founded or stable-model semantics) increases the expressive power considerably to classes like co-NEXPTIME, but not to full Turing completeness. You have to add function symbols to get semidecidability and thus Turing completeness. See e.g. this survey of the computational complexity of various logic programming variants. There is an extensive literature on this for Datalog and also for other logic languages such as description logics.

Don't datalog programs execute in polynomial time? Or are you talking about the complexity as a function of the length of the datalog program?

I was referring to the program complexity (or combined complexity), which is as you say. For data complexity (fixed IDB) it is indeed polynomial time, but it seemed better to quote the more dynamic case where the program can itself be part of the input.

Posted in wrong place.

The above comment about Datalog seems correct (it adds transitive closure to relational algebra, but takes away negation), but then you seem to go wrong in the second part. You don't need anything more than a pure subset of Prolog for Turing Completeness.

http://cs.stackexchange.com/questions/19591/what-makes-prolog-turing-complete

Prolog has function symbols, Datalog doesn't. Your SO answer makes exactly the same point that they are required for Turing completeness in addition to recursion.

You are right, I guess I just haven't made the distinction between Prolog clause heads with single or multiple arguments. This seems to me to be a naming thing. My pure Prolog interpreter just has atoms, structures, clauses and rules, so I did not see a distinction.

Short answer, Prolog or Datalog. For longer answer see above.

Edit: see above, Datalog is not Turing complete, however Prolog is.

Datalog is a declarative logic programming language that is syntactically a subset of Prolog, but in which queries are deterministic.
Modern Datalog implementations include negation and functional symbols, and thereby achieve TC.

So I was right for the wrong reasons :-) I should have just stuck to the original insight, that Prolog (and now Datalog) is what you get when you add what is missing from relational algebra to make it Turing complete.

That Datalog is what you get when you extract a deterministic subset of Prolog that you can use as a query language, solve the negation problem and then add back in just enough to make it computationally complete again.

Perhaps, but Prolog seems to be simpler to define and has that combination of simplicity and elegance that we call expressive power. Stratified negation like Datalog has is interesting, but I don't think it is the solution to the negation problem. I think something like constructive negation is more likely to be the solution to the negation problem.

Edit: I think I should really say "Prolog Like" as I am talking about the pure part of Prolog (no cut or other unsound operations, unification with an occurs check).