Recursion

We say that a Vadalog program or ontology is recursive if the dependency graph implied by the rules is cyclic. The simplest form of recursion is that in which the head of a rule also appears in the body (self-recursive rules).

Recursion is particularly powerful as it allows for inference based on previously inferred results.

In self-recursive rules, in case of bodies with two atoms, we distinguish between:

  1. left recursion, where the recursive atom is the left-most;

  2. right recursion, where the recursive atom is the right-most.

  3. non-linear recursion, where both the atoms are recursive.

Some examples follow.

Example
edge(1,2).
edge(2,3).
edge(1,4).
edge(4,5).
path(X,Y) :- edge(X,Y).
path(X,Z) :- path(Y,Z), edge(X,Y).
@output("path").
Expected result
path(1,3). path(1,2). path(1,5). path(2,3). path(1,4). path(4,5).
Example
edge(1,2).
edge(2,3).
edge(1,4).
edge(4,5).
path(X,Y) :- edge(X,Y).
path(X,Z) :- edge(X,Y),path(Y,Z).
@output("path").
Expected result
path(1,3). path(1,2). path(1,5). path(2,3). path(1,4). path(4,5).
Example
edge(1,2).
edge(2,3).
edge(1,4).
edge(4,5).
path(X,Y) :- edge(X,Y).
path(X,Z) :- path(X,Y),path(Y,Z).
@output("path").
Expected result
path(1,3). path(1,2). path(1,5). path(2,3). path(1,4). path(4,5).

The examples above show reachability in graphs with left, right and non-linear recursion, respectively.