Perhaps the Prolog terminology of "queries" and "database" gave you the impression it has something to do with databases that store data. It doesn't. The query is over logical terms, and the database is a collection of Prolog facts.
edge(1, 2).
edge(2, 3).
edge(3, 4).
+——-+——-+
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
+——-+——-+
However, in Prolog you can easily define something like reachability using recursion:
reachable(V, V).
reachable(V, W) :-
edge(V, U),
reachable(U, W).
But the graph in your example is still directed, simply by the virtue of predicate arguments being ordered.
So your example misses two rules to be correct.
reachable(V, W) :- edge(V, W).
reachable(V, W) :- edge(W, V).
reachable(V, W) :-
reachable(V, U),
reachable(U, W).
edge(V, W) :- edge(W, V).In fact fore recent SQL standards have added extensions for these kinds of recursive joins. (And some databases like Oracle, DB2 have had recurse or tclose operators for a long time.)
I don't think they're particularly elegant -- they're awkward like most things in SQL because SQL's syntax sucks -- but the ability is in fact there these days.
I wonder whether you're accurately portraying the structural foundations of either Prolog or SQL.
Now, some people argue you might want a less expressive logic programming language, especially datalog, so this isn’t a knock-down argument, but it’s a pretty big difference.
yes it is
> SQL gets Turing completeness by means of various additions/alterations.
Sigh. No. SQL was a subset of relational until recursive CTEs were included to round it off properly.
Can you double check and/or give references? Because I specifically doubted my memory here, and everything I found online before posting matches what I thought—-standard relational algebra is not Turing-complete (hence relational queries are guaranteed to terminate).