3 ms·
Prolog and Datalog example (they are identical in this case) % Facts parent(john, mary). parent(mary, ann). parent(mary, tom). % Rules
by greenavocado 2y ago
Prolog and Datalog example (they are identical in this case)
% Facts
parent(john, mary).
parent(mary, ann).
parent(mary, tom).
% Rules
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).
% Query
?- ancestor(john, X).
The Prolog code looks identical to Datalog but the execution model is different. Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered.
Datalog starts by evaluating all possible combinations of facts and rules. It builds a bottom-up derivation of all possible facts:
a. First, it derives all direct parent relationships.
b. Then, it applies the ancestor rules iteratively until no new facts can be derived.
For the query ancestor(john, X):
It returns all X that satisfy the ancestor relationship with john. This includes mary, ann, and tom. The order of rules doesn't affect the result or termination. Datalog guarantees termination because it operates on a finite set of possible facts.
Prolog uses a top-down, depth-first search strategy with backtracking.
For the query ancestor(john, X):
a. It first tries to satisfy parent(john, X). This succeeds with X = mary.
b. It then backtracks and tries the second rule: It satisfies parent(john, Y) with Y = mary. Then recursively calls ancestor(mary, X).
c. This process continues, exploring the tree depth-first.
Prolog will find solutions in this order: mary, ann, tom.
The order of clauses can affect both the order of results and termination: If the recursive rule were listed first, Prolog could enter an infinite loop. Prolog doesn't guarantee termination, especially with recursive rules.
SQL is more verbose. The equivalent of the Datalog/Prolog example above is:
-- Create and populate the table
CREATE TABLE Parent (
parent VARCHAR(50),
child VARCHAR(50)
);
INSERT INTO Parent VALUES ('john', 'mary');
INSERT INTO Parent VALUES ('mary', 'ann');
INSERT INTO Parent VALUES ('mary', 'tom');
-- Recursive query to find ancestors
WITH RECURSIVE Ancestor AS (
SELECT parent, child
FROM Parent
UNION ALL
SELECT a.parent, p.child
FROM Ancestor a
JOIN Parent p ON a.child = p.parent
)
SELECT DISTINCT parent AS ancestor
FROM Ancestor
WHERE child IN ('ann', 'tom');
This is a more interesting example of how one might use Datalog on a large dataset:
% Define the base relation
friend(Person1, Person2).
% Define friend-of-friend relation
friend_of_friend(X, Z) :- friend(X, Y), friend(Y, Z), X != Z.
% Define potential friend recommendation
% (friend of friend who is not already a friend)
recommend_friend(X, Z) :- friend_of_friend(X, Z), not friend(X, Z).
% Count mutual friends for recommendations
mutual_friend_count(X, Z, Count) :-
recommend_friend(X, Z),
Count = count{Y : friend(X, Y), friend(Y, Z)}.
% Query to get top friend recommendations for a person
top_recommendations(Person, RecommendedFriend, MutualCount) :-
mutual_friend_count(Person, RecommendedFriend, MutualCount),
MutualCount >= 5,
MutualCount = max{C : mutual_friend_count(Person, _, C)}.
The equivalent Postgres example would be:
WITH RECURSIVE
-- Base friend relation
friends AS (
SELECT DISTINCT person1, person2
FROM friendship
UNION
SELECT person2, person1
FROM friendship
),
-- Friend of friend relation
friend_of_friend AS (
SELECT f1.person1 AS person, f2.person2 AS friend_of_friend
FROM friends f1
JOIN friends f2 ON f1.person2 = f2.person1
WHERE f1.person1 <> f2.person2
),
-- Potential friend recommendations
potential_recommendations AS (
SELECT fof.person, fof.friend_of_friend,
COUNT(*) AS mutual_friend_count
FROM friend_of_friend fof
LEFT JOIN friends f ON fof.person = f.person1 AND fof.friend_of_friend = f.person2
WHERE f.person1 IS NULL -- Ensure they're not already friends
GROUP BY fof.person, fof.friend_of_friend
HAVING COUNT(*) >= 5 -- Minimum mutual friends threshold
),
-- Rank recommendations
ranked_recommendations AS (
SELECT person, friend_of_friend, mutual_friend_count,
RANK() OVER (PARTITION BY person ORDER BY mutual_friend_count DESC) as rank
FROM potential_recommendations
)
-- Get top recommendations
SELECT person, friend_of_friend, mutual_friend_count
FROM ranked_recommendations
WHERE rank = 1;
Full example you can run yourself: https://onecompiler.com/postgresql/42khbswat https://onecompiler.com/postgresql/42khbswat
- dmpk2k 2y agoHow does the Datalog approach compare with RETE?
- ted_dunning 2y agoThe big deal about Datalog is that it is equivalent to SQL-with-recursion. Thus, it can compile to database queries.
- dkarl 2y ago> Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered Is this an issue in practice? Most languages can create programs with infinite loops, but it's easy to spot in code reviews. It's been over a decade since I encountered an infinite loop in production in the backend. Just wondering if the same is true for Prolog.
- Normal_gaussian 2y agoYes. It is trivially easy to create loops of rules when describing abstract properties. Concrete properties tend to have "levels" to them, but many human concepts are self-referential. In this way, its possible to spot that there may be an issue now or in the future, because the presence or lack of a loop depends on the specific choice of dependencies of a concept. However spotting the potential for a loop doesn't do a lot to help remove its potential existence, or show that it is there or not there.
- derdi 2y agoThere are classes of infinite loops that are harder to spot for beginners, it takes a while to really understand the execution model. Prolog variables can have two states at runtime: unbound or bound. A bound variable refers to some value, while an unbound variable is a "hole" to be filled in at a later time. It's common to pass an unbound variable into some call and expect the callee to bind it to a value. This can cause problems with infinite recursion where you intend to write a call that binds some variable, but the way you've structured your program, it will not actually bind it. So the callee ends up in the same state as the caller, makes a recursive call hoping its callee will bind the variable, and down the infinite recursion you go. With experience you can definitely spot this in code review. You'll also catch it in testing, if you test properly. But it's different enough from other languages that learners struggle with it at first. Another source of (seeming) nontermination is when you ask Prolog's backtracking search to find an answer to some query in a search space that is too large and may not contain an answer at all, or only an answer that is impracticably far away. This is also sort of Prolog-specific since in other languages you rarely write the same kind of optimistic recursive search. This is harder to spot in code review since it's really application-specific what the search space looks like. But again, you test. And when in doubt, you direct and limit the search appropriately.