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