Skip to content

Recursive Computations in Rel


We are excited to announce the latest enhancements to our Relational Knowledge Graph System (RKGS) (opens in a new tab) that substantially improve the performance of certain recursive computations.

As an example, consider the following recursive computation:


When certain algebraic conditions are satisfied, this program is automatically rewritten by our optimizer into the following:


In the rewritten version, we exploited specific algebraic properties of F to define and construct the “addition” and “subtraction” operators shown in the figure above, so that computing F in two steps is faster than computing it in one step in the original formulation.

More specifically, the improvements come from implementing the Generalized SemiNaive Evaluation (GSNE) presented in our paper on the Convergence of Datalog over (Pre-) Semirings (opens in a new tab). We are honored that this research was awarded the Best Paper Award at PODS 2022 (opens in a new tab).

Experimentally, you can see the speedup factors for two computations on a collection of SNAP datasets. Specifically, we show the speedup for computing single-source-shortest-path (SSSP) and all-pairs-shortest-path (APSP).


Note that for the SSSP computation, the ca-GrGc dataset is too small for the speedup to show — the optimization adds some overhead, and the total overhead must be smaller than the promised speedup factor in order to display a result.


Get Started!

Start your journey with RelationalAI today! Sign up to receive our newsletter, invitations to exclusive events, and customer case studies.

The information you provide will be used in accordance with the terms of our Privacy Policy. By submitting this form, you consent to allow RelationalAI to store and process the personal information submitted above to provide you the content requested.