Main ArticleExamples TOC

Takmela: Reverse-same-generation Datalog Example (abridged)

A well-known example program for Datalog, which I found in the book "Foundations of Databases" by Abiteboul, Hull & Viano, presented in chapter 13

This is an abridged version (the difference being a smaller fact set) to make the trace shorter and easier to follow. If you want to see the full example traced (at your own peril) you can find it here.

Program 
// 'up' means 'goes up to'
up("a", "e").
up("j", "o").

// 'goes horizontally toward'
flat("m", "o").
flat("p", "m").

// 'goes down to'
down("l", "f").
down("m", "f").

reverse_same_generation(X, Y):-
    flat(X, Y).

reverse_same_generation(X, Y):-
    up(X, X1),
    reverse_same_generation(Y1, X1),
    down(Y1, Y)
    .
Query 
reverse_same_generation(A, B)

For the sake of reducing graph size, the identifiers 'up' , 'down' , 'flat' and 'reverse_same_generation' will be renamed in the actual trace to 'u' , 'd' , 'f' and 'r' respectively.

Hint: Hovering over a graph expands it

Trace appears confusing? This might help

Call start rule
#0: Called r(?, ?) at the top level (will process)
Processing r(?, ?) codePos r(X, Y)→•f(X,Y)
Calling fact: f(?, ?)
Found fact: f(?, ?) → [m, o]
Found fact: f(?, ?) → [p, m]
Processing r(?, ?) codePos r(X, Y)→•u(X,X1), r(Y1,X1), d(Y1,Y)
Calling fact: u(?, ?)
Found fact: u(?, ?) → [a, e]
Found fact: u(?, ?) → [j, o]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o]
Iteration 0
Worklist - successes
jS u(?, ?) → (a, e)
jS u(?, ?) → (j, o)
jS f(?, ?) → (m, o)
jS f(?, ?) → (p, m)
Worklist - continuations
S⤚ u(?, ?) → r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y)
S⤚ f(?, ?) → r(X, Y)→f(X,Y)•
#1: JoinS: u(?, ?) → [a, e] will resume cont: r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y)
newVars: {X=a, X1=e}
Processing r(?, ?) codePos r(X, Y)→u(X|a,X1|e)•r(Y1,X1|e), d(Y1,Y)
Calling: r(?, e) [will process]
Processing r(?, e) codePos r(X, Y)→•f(X,Y|e)
Calling fact: f(?, e)
Processing r(?, e) codePos r(X, Y)→•u(X,X1), r(Y1,X1), d(Y1,Y|e)
Calling fact: u(?, ?)
Found fact: u(?, ?) → [a, e]
Found fact: u(?, ?) → [j, o]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o]
#2: JoinS: u(?, ?) → [j, o] will resume cont: r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y)
newVars: {X=j, X1=o}
Processing r(?, ?) codePos r(X, Y)→u(X|j,X1|o)•r(Y1,X1|o), d(Y1,Y)
Calling: r(?, o) [will process]
Processing r(?, o) codePos r(X, Y)→•f(X,Y|o)
Calling fact: f(?, o)
Found fact: f(?, o) → [m, o]
Processing r(?, o) codePos r(X, Y)→•u(X,X1), r(Y1,X1), d(Y1,Y|o)
Calling fact: u(?, ?)
Found fact: u(?, ?) → [a, e]
Found fact: u(?, ?) → [j, o]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o]
#3: JoinS: f(?, ?) → [m, o] will resume cont: r(X, Y)→f(X,Y)•
newVars: {X=m, Y=o}
Processing r(?, ?) codePos r(X, Y)→f(X|m,Y|o)•
Reached end of rule, success! r(?, ?) → [m, o]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o]
#4: JoinS: f(?, ?) → [p, m] will resume cont: r(X, Y)→f(X,Y)•
newVars: {X=p, Y=m}
Processing r(?, ?) codePos r(X, Y)→f(X|p,Y|m)•
Reached end of rule, success! r(?, ?) → [p, m]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m]
Iteration 1
Worklist - successes
jS r(?, ?) → (m, o)
jS r(?, ?) → (p, m)
jS f(?, o) → (m, o)
Worklist - continuations
nJ f(?, e) → r(X, Y)→f(X,Y|e)•
nJ r(?, o) → r(X, Y)→u(X|j,X1|o), r(Y1,X1|o)•d(Y1,Y)
jK u(?, ?) → r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y|o)
jK u(?, ?) → r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y|e)
S⤚ f(?, o) → r(X, Y)→f(X,Y|o)•
nJ r(?, e) → r(X, Y)→u(X|a,X1|e), r(Y1,X1|e)•d(Y1,Y)
#5: JoinS: r(?, ?) → [m, o] will resume cont: Root(V0, V1)→r(V0,V1)•
newVars: {V0=m, V1=o}
Processing Root() codePos Root(V0, V1)→r(V0|m,V1|o)•
Reached end of rule, success! Root() → [m, o]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓
#6: JoinS: r(?, ?) → [p, m] will resume cont: Root(V0, V1)→r(V0,V1)•
newVars: {V0=p, V1=m}
Processing Root() codePos Root(V0, V1)→r(V0|p,V1|m)•
Reached end of rule, success! Root() → [p, m]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓
#7: JoinS: f(?, o) → [m, o] will resume cont: r(X, Y)→f(X,Y|o)•
newVars: {X=m}
Processing r(?, o) codePos r(X, Y)→f(X|m,Y|o)•
Reached end of rule, success! r(?, o) → [m, o]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
#8: JoinK: u(?, ?) will use u(?, ?) → [a, e] to resume r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y|o)

newVars: {X=a, X1=e}
Processing r(?, o) codePos r(X, Y)→u(X|a,X1|e)•r(Y1,X1|e), d(Y1,Y|o)
Calling: r(?, e) [already processed]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
#9: JoinK: u(?, ?) will use u(?, ?) → [j, o] to resume r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y|o)

newVars: {X=j, X1=o}
Processing r(?, o) codePos r(X, Y)→u(X|j,X1|o)•r(Y1,X1|o), d(Y1,Y|o)
Calling: r(?, o) [already processed]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
#10: JoinK: u(?, ?) will use u(?, ?) → [a, e] to resume r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y|e)

newVars: {X=a, X1=e}
Processing r(?, e) codePos r(X, Y)→u(X|a,X1|e)•r(Y1,X1|e), d(Y1,Y|e)
Calling: r(?, e) [already processed]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
#11: JoinK: u(?, ?) will use u(?, ?) → [j, o] to resume r(X, Y)→u(X,X1)•r(Y1,X1), d(Y1,Y|e)

newVars: {X=j, X1=o}
Processing r(?, e) codePos r(X, Y)→u(X|j,X1|o)•r(Y1,X1|o), d(Y1,Y|e)
Calling: r(?, o) [already processed]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
Iteration 2
Worklist - successes
jS r(?, o) → (m, o)
nJ Root() → (m, o)
nJ Root() → (p, m)
Worklist - continuations
S⤚ r(?, o) → r(X, Y)→u(X|j,X1|o), r(Y1,X1|o)•d(Y1,Y|o)
S⤚ r(?, o) → r(X, Y)→u(X|j,X1|o), r(Y1,X1|o)•d(Y1,Y|e)
nJ r(?, e) → r(X, Y)→u(X|a,X1|e), r(Y1,X1|e)•d(Y1,Y|o)
nJ r(?, e) → r(X, Y)→u(X|a,X1|e), r(Y1,X1|e)•d(Y1,Y|e)
#12: JoinS: r(?, o) → [m, o] will resume cont: r(X, Y)→u(X|j,X1|o), r(Y1,X1|o)•d(Y1,Y|o)
newVars: {Y1=m}
Processing r(?, o) codePos r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o)•d(Y1|m,Y|o)
Calling fact: d(m, o)
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
#13: JoinS: r(?, o) → [m, o] will resume cont: r(X, Y)→u(X|j,X1|o), r(Y1,X1|o)•d(Y1,Y|e)
newVars: {Y1=m}
Processing r(?, e) codePos r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o)•d(Y1|m,Y|e)
Calling fact: d(m, e)
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o]
#14: JoinS: r(?, o) → [m, o] will resume cont: r(X, Y)→u(X|j,X1|o), r(Y1,X1|o)•d(Y1,Y)
newVars: {Y1=m}
Processing r(?, ?) codePos r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o)•d(Y1|m,Y)
Calling fact: d(m, ?)
Found fact: d(m, ?) → [m, f]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o] d(m, ?) → [m, f]
Iteration 3
Worklist - successes
jS d(m, ?) → (m, f)
Worklist - continuations
nJ d(m, o) → r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o), d(Y1|m,Y|o)•
S⤚ d(m, ?) → r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o), d(Y1|m,Y)•
nJ d(m, e) → r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o), d(Y1|m,Y|e)•
#15: JoinS: d(m, ?) → [m, f] will resume cont: r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o), d(Y1|m,Y)•
newVars: {Y=f}
Processing r(?, ?) codePos r(X, Y)→u(X|j,X1|o), r(Y1|m,X1|o), d(Y1|m,Y|f)•
Reached end of rule, success! r(?, ?) → [j, f]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o] d(m, ?) → [m, f] r(?, ?) → [j, f]
Iteration 4
Worklist - successes
jS r(?, ?) → (j, f)
Worklist - continuations
#16: JoinS: r(?, ?) → [j, f] will resume cont: Root(V0, V1)→r(V0,V1)•
newVars: {V0=j, V1=f}
Processing Root() codePos Root(V0, V1)→r(V0|j,V1|f)•
Reached end of rule, success! Root() → [j, f]
f(?, ?) → [m, o] f(?, ?) → [p, m] u(?, ?) → [a, e] u(?, ?) → [j, o] u(?, ?) → [a, e] u(?, ?) → [j, o] f(?, o) → [m, o] u(?, ?) → [a, e] u(?, ?) → [j, o] r(?, ?) → [m, o] r(?, ?) → [p, m] Root() → [m, o]✓ Root() → [p, m]✓ r(?, o) → [m, o] d(m, ?) → [m, f] r(?, ?) → [j, f] Root() → [j, f]✓
Iteration 5
Worklist - successes
nJ Root() → (j, f)
Worklist - continuations
(No new calls or successes that can be further processed)
Iteration 6 [Fixed point reached]