Takmela: Siblings Datalog Example

Another classic example to showcase Logic Programming.

parent("a", "b").
parent("b", "c").
parent("a", "d").
parent("d", "e").

sibling(X, Y):-
    parent(P, X),
    parent(P, Y),
    X != Y
    .

sibling(X, Y)

Hint: Hovering over a graph expands it

Call start rule
	#0: Called sibling(?, ?) at the top level (will process) Processing sibling(?, ?) codePos sibling(X, Y)→•parent(P,X), parent(P,Y), X<Y Calling fact: parent(?, ?) Found fact: parent(?, ?) → [a, b] Found fact: parent(?, ?) → [b, c] Found fact: parent(?, ?) → [a, d] Found fact: parent(?, ?) → [d, e]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e]
Iteration 0
Worklist - successes jS parent(?, ?) → (a, b) jS parent(?, ?) → (b, c) jS parent(?, ?) → (d, e) jS parent(?, ?) → (a, d) Worklist - continuations S⤚ parent(?, ?) → sibling(X, Y)→parent(P,X)•parent(P,Y), X<Y
	#1: JoinS: parent(?, ?) → [a, b] will resume cont: sibling(X, Y)→parent(P,X)•parent(P,Y), X<Y newVars: {P=a, X=b} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|a,X|b)•parent(P|a,Y), X|b<Y Calling fact: parent(a, ?) Found fact: parent(a, ?) → [a, b] Found fact: parent(a, ?) → [a, d]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
	#2: JoinS: parent(?, ?) → [b, c] will resume cont: sibling(X, Y)→parent(P,X)•parent(P,Y), X<Y newVars: {P=b, X=c} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|b,X|c)•parent(P|b,Y), X|c<Y Calling fact: parent(b, ?) Found fact: parent(b, ?) → [b, c]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c]
	#3: JoinS: parent(?, ?) → [d, e] will resume cont: sibling(X, Y)→parent(P,X)•parent(P,Y), X<Y newVars: {P=d, X=e} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|d,X|e)•parent(P|d,Y), X|e<Y Calling fact: parent(d, ?) Found fact: parent(d, ?) → [d, e]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e]
	#4: JoinS: parent(?, ?) → [a, d] will resume cont: sibling(X, Y)→parent(P,X)•parent(P,Y), X<Y newVars: {P=a, X=d} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|a,X|d)•parent(P|a,Y), X|d<Y Calling fact: parent(a, ?) Found fact: parent(a, ?) → [a, b] Found fact: parent(a, ?) → [a, d]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
Iteration 1
Worklist - successes jS parent(b, ?) → (b, c) jS parent(d, ?) → (d, e) jS parent(a, ?) → (a, b) jS parent(a, ?) → (a, d) Worklist - continuations S⤚ parent(b, ?) → sibling(X, Y)→parent(P|b,X|c), parent(P|b,Y)•X|c<Y S⤚ parent(d, ?) → sibling(X, Y)→parent(P|d,X|e), parent(P|d,Y)•X|e<Y S⤚ parent(a, ?) → sibling(X, Y)→parent(P|a,X|d), parent(P|a,Y)•X|d<Y S⤚ parent(a, ?) → sibling(X, Y)→parent(P|a,X|b), parent(P|a,Y)•X|b<Y
	#5: JoinS: parent(b, ?) → [b, c] will resume cont: sibling(X, Y)→parent(P|b,X|c), parent(P|b,Y)•X|c<Y newVars: {Y=c} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|b,X|c), parent(P|b,Y|c)•X|c<Y|c Testing: X|c < Y|c, Failed
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
	#6: JoinS: parent(d, ?) → [d, e] will resume cont: sibling(X, Y)→parent(P|d,X|e), parent(P|d,Y)•X|e<Y newVars: {Y=e} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|d,X|e), parent(P|d,Y|e)•X|e<Y|e Testing: X|e < Y|e, Failed
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
	#7: JoinS: parent(a, ?) → [a, b] will resume cont: sibling(X, Y)→parent(P|a,X|d), parent(P|a,Y)•X|d<Y newVars: {Y=b} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|a,X|d), parent(P|a,Y|b)•X|d<Y|b Testing: X|d < Y|b, Failed
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
	#8: JoinS: parent(a, ?) → [a, b] will resume cont: sibling(X, Y)→parent(P|a,X|b), parent(P|a,Y)•X|b<Y newVars: {Y=b} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|a,X|b), parent(P|a,Y|b)•X|b<Y|b Testing: X|b < Y|b, Failed
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
	#9: JoinS: parent(a, ?) → [a, d] will resume cont: sibling(X, Y)→parent(P|a,X|d), parent(P|a,Y)•X|d<Y newVars: {Y=d} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|a,X|d), parent(P|a,Y|d)•X|d<Y|d Testing: X|d < Y|d, Failed
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d]
	#10: JoinS: parent(a, ?) → [a, d] will resume cont: sibling(X, Y)→parent(P|a,X|b), parent(P|a,Y)•X|b<Y newVars: {Y=d} Processing sibling(?, ?) codePos sibling(X, Y)→parent(P|a,X|b), parent(P|a,Y|d)•X|b<Y|d Testing: X|b < Y|d, Succeeded Reached end of rule, success! sibling(?, ?) → [b, d]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] sibling(?, ?) → [b, d]
Iteration 2
Worklist - successes jS sibling(?, ?) → (b, d) Worklist - continuations
	#11: JoinS: sibling(?, ?) → [b, d] will resume cont: Root(V0, V1)→sibling(V0,V1)• newVars: {V0=b, V1=d} Processing Root() codePos Root(V0, V1)→sibling(V0|b,V1|d)• Reached end of rule, success! Root() → [b, d]
parent(?, ?) → [a, b] parent(?, ?) → [b, c] parent(?, ?) → [a, d] parent(?, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] parent(b, ?) → [b, c] parent(d, ?) → [d, e] parent(a, ?) → [a, b] parent(a, ?) → [a, d] sibling(?, ?) → [b, d] Root() → [b, d]✓
Iteration 3
Worklist - successes nJ Root() → (b, d) Worklist - continuations
(No new calls or successes that can be further processed)
Iteration 4 [Fixed point reached]