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