Datalog and Recursive Queries: A Small Language for Data Relationships

Datalog expresses derived relationships as rules over facts. Its syntax is small enough to expose the logic that SQL often hides behind joins, subqueries, and recursion. For data cleaning, that clarity helps separate source facts, derived evidence, and violation rules.

Facts and rules

parent("Ada", "Ben").
parent("Ben", "Chen").

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

Read :- as “is true if.” The first rule is the base case. The second rule says that a parent of an ancestor is also an ancestor.

Evaluation repeatedly applies rules until no new fact can be derived. This is the least fixed point.

round 0: source parent facts
round 1: direct ancestors
round 2: paths of length two
...
stop when the result no longer grows

In plain terms: recursion keeps asking “what new fact follows from everything known so far?” and stops when the answer is “nothing.”

Variables must be safe

Every variable in a rule head or negative condition should be bound by a positive body atom. Otherwise the rule may range over an undefined universe.

has_author(P) :- paper_author(P, A).
missing_author(P) :- paper(P), not has_author(P).

P is grounded by paper(P) before the negative test. Negation is safest when the program is stratified: predicates do not depend negatively on themselves through a cycle.

Integrity constraints as denial rules

A denial states a combination that must never occur:

:- paper_author(P, A), not paper(P).

Operationally, turn the body into a query. Every answer is a witness to the violation. Unlike a vague “invalid relationship” flag, the witness identifies the implicated tuples.

The recursive SQL equivalent

WITH RECURSIVE ancestor(person, descendant) AS (
  SELECT parent, child
  FROM parent

  UNION

  SELECT a.person, p.child
  FROM ancestor AS a
  JOIN parent AS p ON p.parent = a.descendant
)
SELECT * FROM ancestor;

UNION removes duplicates and helps the finite relation reach a fixed point. UNION ALL may be faster, but cycles can produce repeated paths or nontermination unless the query tracks visited state or depth.

Where recursion helps cleaning

• following hierarchical taxonomies;
• finding transitive duplicate links;
• tracing provenance dependencies;
• propagating classifications through a graph;
• detecting cycles in parent-child data.

Recursion does not decide whether an edge is trustworthy. It magnifies whatever base facts and mappings it receives, so validation of the seed relation remains essential.

Review card

• Facts are stored observations; rules derive new relations.
• Recursive evaluation continues to a fixed point.
• A base case anchors recursion.
• Safe variables are bound by positive atoms.
• A denial rule’s answers are violation witnesses.
• Recursive SQL uses the same fixed-point idea, with duplicate and cycle handling made explicit.

parent("Ada", "Ben").
parent("Ben", "Chen").

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

round 0: source parent facts
round 1: direct ancestors
round 2: length-two paths
...
result 不再成長就停止

has_author(P) :- paper_author(P, A).
missing_author(P) :- paper(P), not has_author(P).

:- paper_author(P, A), not paper(P).

WITH RECURSIVE ancestor(person, descendant) AS (
  SELECT parent, child
  FROM parent

  UNION

  SELECT a.person, p.child
  FROM ancestor AS a
  JOIN parent AS p ON p.parent = a.descendant
)
SELECT * FROM ancestor;