Prolog and Lisp were derived from first principles, SQL was designed to be a language that reads similar to English (i.e. easy to learn for non-programmers).
Prolog and Lisp also has the concept of "atom" which can represent many things, but in parsing it's used for terminal symbols.
Prolog has the advantage over Lisp that you can define custom operators and their precedence, so you can create easy to read domain specific languages without excessive amounts of parentheses.
The built-in backtracking can also be useful for parsing.
Definite Clause Grammer rules are also a standard feature, which is very similar to the Backus-Naur form.
BNF and DCGs get a bit closer to what I'm asking, but even then I'm not sure it really adds anything novel -- what, if any advantages do you get from that over the relational algebra whose set theoretic underpinnings serve as the foundation for SQL? How is backtracking functionally different or more powerful than joining?
Let me give an example by way of another formalism, which is the Church-Turing correspondence that establishes a correspondence between the lambda calculus and Turing machines. Is there any theoretically stronger expressive power one gets from Prolog over SQL, or is it an ergonomics question, similar to using say, Ruby over Java?
I guess this is best illustrated by examples.
In prolog, you can define how people are related using "facts" or data:
person_parent(alfred, benny).
person_parent(benny, carl).
CREATE TABLE persons ( name TEXT NOT NULL, parent TEXT NOT NULL);
Let's say I want to know if "carl" is the grandparent of "alfred", in Prolog I would first write a rule to define what a grandparent is:
grandparent(X, Y):- person_parent(X, Z), person_parent(Z, Y).
grandparent(alfred, carl). --> true
grandparent(X, carl). --> X = alfred (and any other kid)
grandparent(alfred, Y). --> Y = carl (and any other grandparent)
grandparent(X, Y). --> X = alfred, Y = carl (and any other combination).
A more powerful example, is defining the rules of suduko and then asking prolog to finish solving a board for you. I will not even begin to suggest how that would be done in SQL (partly because you simply would not use SQL for that).
Nope. Can be written as a non-predicated recursive CTE. Just add a 'where' at the end to specify what you want.
The practical difference is in the way the search takes place. In SQL you would get the right results but it might take a lot longer because it might (depending on what you're looking for) generate all possibilities and just pick the ones you want. In Prolog I think it's a bit more intelligent in searching.
That depends, of course because it's an implementation detail and predicate pushdown or whatever might regain that efficiency, but from experience I can say It Depends.
(I recently did something like this at work, so it is actually useful)
Edit: see https://www.andrewvillazon.com/recursive-cte-sql-server/ for something similar
Two rather distinct solutions:
https://www.sqlite.org/lang_with.html#outlandish_recursive_q...
http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Sudoku_in_...
If it's just that you can define relations in the database scheme, then pretty any programming language would be considered relational.
They're not "true" relations though because SQL allowed duplicate tuples ("rows") and missing values (null) which the pure relational model does not permit.
It's also considered relational because it uses at least some of the terminology and functionality of relational algebraic operators (join, project, restrict(select), union, cross product, etc.). Though this sometimes leads to confusion (e.g. "select" in the rel-algebra means something different from what a lot of people writing SQL queries think it means -- 'select' in the relational algebra is a restricting/filter operator, but the way it appears in a SQL query implies that it's the thing choosing which attributes (columns) to retrieve... which is another operation entirely (project) in the relational algebra...)
As for the explicitness, that's orthogonal to the question. Relational algebraic expressions are in fact quite explicit. Datalog queries (and Prolog maybe too, to some degree, but not always) can be essentially compiled down to relational algebraic operations (tho they don't have to be.) And so can SQL.
SQL is sort of ... inbetween... the relational algebra and something like a "relational calculus" which figures more out for you and does things more automagically.
Sometimes the explicitness of SQL is in fact a feature. I've found Datalog queries a bit awkward to read at times, with the joins sort of automagically happening, it's sometimes tricky to fully grasp what's happening behind the scenes.
Regardless one of the features of the relational algebra is that various operations can be re-ordered for efficiency without losing the semantic meaning. So behind the scenes SQL query planners restructure things as they need and desire.
But ergonomics of the syntax certainly hinders you ...
Example: Adds nulls (weird trivalue logic, and breaks reordering of some relational algebraic expressions), has duplicate tuples (relations stop being sets of sets).
Unfortunately SQL has done more recently to put people off the relational model than it has to bring them around. Though the majority of people who use it don't actually understand the relational model, so.
Datalog is also built on the relational algebra. Or at least, Datalog works on relations and any Datalog programme can effectively "compiled down" to a relational algebraic expression.
Prolog, OTOH, excels at planning, optimization, constraint solving, etc. Given Prolog was originally designed for old-school grammar/logic-based NLP, it also has excellent built-in support for custom DSLs and recursive-descent parsing using definite clause grammars making use of Prolog's logical variables (with indeterminism / backtracking and retry) and unification (pattern matching on steroids).
Check out Prolog in-browser demos for robotic planning/container logistics and machine learning/bioinformatics (not based on LLMs) at [1]. These aren't problems you'd tackle with SQL ;) but beyond SQL's inappropriateness also require actual language support for debugging, packages, testing, integration, etc.
Another, unrelated aspect: I/O, system calls, all that stuff that would require from you in SQL database to go outside and implement functions that are loaded into your database in some database-specific way.
Parsing. SQL doesn't offer much in terms of working with strings. Writing as much as a parser for arithmetic expressions with just integers would be a huge undertaking. No sane person would write such a parser unless for some bizarre code-golf challenge. It's trivial to do that in Prolog.
CLFD. This isn't part of standard Prolog, but it comes with most implementations. This allows you easily to write queries about numerical facts (eg. find all factors of a given integer).
To continue in the similar spirit as above: modern Prologs come with a bunch of libraries. You can have an HTTP server in Prolog, or an image processing tool etc. Something that in SQL you'd have to implement outside of it, and load as an external function.
Modules. Prolog code is more amenable to reuse and can be better organized because you can put it in boxes, hide things you want to keep private in those boxes etc. This is while SQL operates entirely in some sort of a global namespace.
The list isn't exhaustive, these are just the things I could think in a short time.
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).
Part of the reason I wanted to ask this question because I had a suspicion that there may not necessarily be as large of a gap between SQL and Prolog as there may initially appear. Said another way, I wondered if there was a Prolog (or Datalog) to SQL compiler used in production.
I recently stumbled upon Logica [1], which appears to based on a predecessor (Yeladog) built at Google. I don't have experience using it, so I'm not sure how complete the implementation is nor how efficient it is. I'm curious if anyone has used it before and if so, what their experience was. At first blush, it appears to bring the best of both worlds: the expressive power of Prolog/Datalog, combined with the standard operational tooling of SQL which is a common core dependency in many if not most production software systems. Two questions:
1) How does Datalog compare to Prolog for common problems you might use Prolog for? Any things you can do in Prolog differentially that wouldn't be as easy in Datalog and vice versa? 2) What issues might come up in system that uses a Datalog to SQL transpiler? Given that some of the answers in this thread about the efficiency of using Prolog to do constraint solving, it seems like such an approach might lose some of the efficiency that makes it so powerful in the first place. On the other hand, if it doesn't, it seems like it'd bring a killer app to SQL, which is the ability to do constraint solving in a nearly native fashion inside SQL.
1. Nothing, theoretically (but see 2, 3, 4)
2. They are for different domains/problems
3. Both are based on the same formal background (1st order predicate calculus IIRC)
4. Learn both. It's not hard and they're both useful and it won't be a waste of your time.
https://xmonader.github.io/prolog/2018/12/21/solving-murder-...