Recursion

A Vadalog program or ontology is recursive if the dependency graph implied by the rules is cyclical. 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:

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

Some examples follow.

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").

The expected results are:

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 recursion. For more complex examples, see Recursion patterns and Graph Analytics.

Introduction

Get Started

Platform

Integrations

Examples

Vadalog Reference

Resources