CODEWITHSUNDEEP
recursiondatalog
xunmiw
xunmiw

Reputation: 21

What is the execution order of recursive datalog?

Q(a, b) :- Edge(a, b).
Q(a, b) :- Q(a, x),
            Edge(x, b).

The function of this code is to search all pair of nodes which are reachable. How is that recursive?

Upvotes: 0

Views: 145

Answers (1)

David Tonhofer
David Tonhofer

Reputation: 15328

This is recursive because the predicate calls itself:

q(A, B) :- q(A, X),edge(X, B).

What the actual execution order is depends on the implementation. It may be "bottom up":

  • From any edge(A,B) derive q(A,B)
  • Apply q(A, B) :- q(A, X),edge(X, B). until a fixpoint has been reached (i.e. not further q(A,B) can be deduced).

owever, you should be able to rearrange the code without being at risk of generating non-termination search, unlike in Prolog.

This should work too:

q(A, B) :- q(A, X),edge(X, B).
q(A, B) :- edge(A, B).

Upvotes: 2

Related Questions