Skip to content

Recursion

Recursive predicates compute transitive closures — relationships that span an arbitrary number of hops. This is the kind of query that is impossible to write correctly in plain SQL without engine-specific recursive CTEs.

Typical uses: org charts, referral chains, product taxonomies, bill of materials, dependency graphs.

Transitive closure

Define a base case and a recursive case, and put the @Recursive directive before the rules with an iteration limit:

@Recursive(AllManagers, 20);

# Base case: direct manager
AllManagers(employee_id:, manager_id:) :- Employees(employee_id:, manager_id:);

# Recursive case: manager's managers
AllManagers(employee_id:, manager_id:) :-
  AllManagers(employee_id:, intermediate:),
  Employees(employee_id: intermediate, manager_id:);

Shortest paths

Find shortest paths in weighted graphs by enumerating route costs recursively, then keeping the minimum per destination with a Min= aggregation:

# Enumerate route costs from the origin, hop by hop.
@Recursive(RouteCost, 10);
RouteCost(destination:, cost:) :-
  ShippingRoutes(origin: "warehouse_main", destination:, cost:);
RouteCost(destination:, cost: total) :-
  RouteCost(destination: hub, cost: hub_cost),
  ShippingRoutes(origin: hub, destination:, cost:),
  total == hub_cost + cost;

# Keep the cheapest cost per destination.
@OrderBy(ShippingCost, "destination");
ShippingCost(destination:, total? Min= cost) distinct :- RouteCost(destination:, cost:);

The @Recursive iteration limit bounds the path length, so cyclic route graphs terminate; the final aggregation keeps only the cheapest route per destination.

Cycle detection

The recursive closure of a parent/child edge detects cycles in a hierarchy — a node that is its own ancestor:

@Recursive(AncestorOf, 100);
AncestorOf(ancestor_id:, descendant_id:) :- ParentOf(parent_id: ancestor_id, child_id: descendant_id);
AncestorOf(ancestor_id:, descendant_id:) :-
  AncestorOf(ancestor_id:, intermediate:),
  ParentOf(parent_id: intermediate, child_id: descendant_id);

HierarchyCycle(node_id:) :- AncestorOf(ancestor_id: node_id, descendant_id: node_id);

Safety

The verifier checks recursive programs at compile time: missing base cases, trivial loops, and unbounded recursion without @Recursive are all reported as errors before any SQL is generated.

Complete example

A management chain (transitive closure) and a shortest-path computation. The shortest path is written as a recursive RouteCost enumeration followed by a Min= aggregation per destination:

# run: AllManagers, ShippingCost
@Engine("duckdb");

# Tables
Employees(employee_id: 1, manager_id: null);
Employees(employee_id: 2, manager_id: 1);
Employees(employee_id: 3, manager_id: 2);
Employees(employee_id: 4, manager_id: 2);

ShippingRoutes(origin: "warehouse_main", destination: "rotterdam", cost: 4);
ShippingRoutes(origin: "rotterdam", destination: "oslo", cost: 3);
ShippingRoutes(origin: "warehouse_main", destination: "oslo", cost: 9);
ShippingRoutes(origin: "oslo", destination: "helsinki", cost: 2);

# Rules

## Transitive closure: every manager above an employee, at any depth.
@Recursive(AllManagers, 20);
@OrderBy(AllManagers, "employee_id", "manager_id");
AllManagers(employee_id:, manager_id:) :-
  Employees(employee_id:, manager_id:), manager_id is not null;
AllManagers(employee_id:, manager_id:) :-
  AllManagers(employee_id:, manager_id: intermediate),
  Employees(employee_id: intermediate, manager_id:), manager_id is not null;

## Shortest paths: enumerate route costs recursively...
@Recursive(RouteCost, 10);
RouteCost(destination:, cost:) :-
  ShippingRoutes(origin: "warehouse_main", destination:, cost:);
RouteCost(destination:, cost: total) :-
  RouteCost(destination: hub, cost: hub_cost),
  ShippingRoutes(origin: hub, destination:, cost:),
  total == hub_cost + cost;

## ...then keep the cheapest per destination.
@OrderBy(ShippingCost, "destination");
ShippingCost(destination:, total? Min= cost) distinct :- RouteCost(destination:, cost:);
Generated SQL and execution results 
$ synalog.check('recursion.l')
No errors found.

$ synalog.compile('recursion.l', 'AllManagers')
-- Initializing DuckDB environment.
create schema if not exists logica_home;
-- Empty record, has to have a field by DuckDB syntax.
drop type if exists logicarecord893574736 cascade; create type logicarecord893574736 as struct(nirvana numeric);
create sequence if not exists eternal_logical_sequence;

CREATE OR REPLACE TABLE logica_home.AllManagers_ifr0 AS WITH t_1_Employees AS (SELECT * FROM (

    SELECT
      1 AS employee_id,
      null AS manager_id
   UNION ALL

    SELECT
      2 AS employee_id,
      1 AS manager_id
   UNION ALL

    SELECT
      3 AS employee_id,
      2 AS manager_id
   UNION ALL

    SELECT
      4 AS employee_id,
      2 AS manager_id

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      t_0_Employees.employee_id AS employee_id,
      t_0_Employees.manager_id AS manager_id
    FROM
      t_1_Employees AS t_0_Employees
    WHERE
      (t_0_Employees.manager_id IS NOT null)

) AS UNUSED_TABLE_NAME  ORDER BY employee_id, manager_id ;

-- Interacting with table logica_home.AllManagers_ifr0

CREATE OR REPLACE TABLE logica_home.AllManagers_ifr1 AS WITH t_1_Employees AS (SELECT * FROM (

    SELECT
      1 AS employee_id,
      null AS manager_id
   UNION ALL

    SELECT
      2 AS employee_id,
      1 AS manager_id
   UNION ALL

    SELECT
      3 AS employee_id,
      2 AS manager_id
   UNION ALL

    SELECT
      4 AS employee_id,
      2 AS manager_id

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      AllManagers_ifr0.employee_id AS employee_id,
      Employees.manager_id AS manager_id
    FROM
      logica_home.AllManagers_ifr0 AS AllManagers_ifr0, t_1_Employees AS Employees
    WHERE
      (Employees.manager_id IS NOT null) AND
      (Employees.employee_id = AllManagers_ifr0.manager_id)
   UNION ALL

    SELECT
      t_0_Employees.employee_id AS employee_id,
      t_0_Employees.manager_id AS manager_id
    FROM
      t_1_Employees AS t_0_Employees
    WHERE
      (t_0_Employees.manager_id IS NOT null)

) AS UNUSED_TABLE_NAME  ORDER BY employee_id, manager_id ;

-- Interacting with table logica_home.AllManagers_ifr1

CREATE OR REPLACE TABLE logica_home.AllManagers_ifr2 AS WITH t_1_Employees AS (SELECT * FROM (

    SELECT
      1 AS employee_id,
      null AS manager_id
   UNION ALL

    SELECT
      2 AS employee_id,
      1 AS manager_id
   UNION ALL

    SELECT
      3 AS employee_id,
      2 AS manager_id
   UNION ALL

    SELECT
      4 AS employee_id,
      2 AS manager_id

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      AllManagers_ifr1.employee_id AS employee_id,
      Employees.manager_id AS manager_id
    FROM
      logica_home.AllManagers_ifr1 AS AllManagers_ifr1, t_1_Employees AS Employees
    WHERE
      (Employees.manager_id IS NOT null) AND
      (Employees.employee_id = AllManagers_ifr1.manager_id)
   UNION ALL

    SELECT
      t_0_Employees.employee_id AS employee_id,
      t_0_Employees.manager_id AS manager_id
    FROM
      t_1_Employees AS t_0_Employees
    WHERE
      (t_0_Employees.manager_id IS NOT null)

) AS UNUSED_TABLE_NAME  ORDER BY employee_id, manager_id ;

-- Interacting with table logica_home.AllManagers_ifr2

CREATE OR REPLACE TABLE logica_home.AllManagers_ifr1 AS WITH t_1_Employees AS (SELECT * FROM (

    SELECT
      1 AS employee_id,
      null AS manager_id
   UNION ALL

    SELECT
      2 AS employee_id,
      1 AS manager_id
   UNION ALL

    SELECT
      3 AS employee_id,
      2 AS manager_id
   UNION ALL

    SELECT
      4 AS employee_id,
      2 AS manager_id

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      AllManagers_ifr2.employee_id AS employee_id,
      Employees.manager_id AS manager_id
    FROM
      logica_home.AllManagers_ifr2 AS AllManagers_ifr2, t_1_Employees AS Employees
    WHERE
      (Employees.manager_id IS NOT null) AND
      (Employees.employee_id = AllManagers_ifr2.manager_id)
   UNION ALL

    SELECT
      t_0_Employees.employee_id AS employee_id,
      t_0_Employees.manager_id AS manager_id
    FROM
      t_1_Employees AS t_0_Employees
    WHERE
      (t_0_Employees.manager_id IS NOT null)

) AS UNUSED_TABLE_NAME  ORDER BY employee_id, manager_id ;

-- Interacting with table logica_home.AllManagers_ifr1

WITH t_1_Employees AS (SELECT * FROM (

    SELECT
      1 AS employee_id,
      null AS manager_id
   UNION ALL

    SELECT
      2 AS employee_id,
      1 AS manager_id
   UNION ALL

    SELECT
      3 AS employee_id,
      2 AS manager_id
   UNION ALL

    SELECT
      4 AS employee_id,
      2 AS manager_id

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      AllManagers_ifr3.employee_id AS employee_id,
      Employees.manager_id AS manager_id
    FROM
      logica_home.AllManagers_ifr1 AS AllManagers_ifr3, t_1_Employees AS Employees
    WHERE
      (Employees.manager_id IS NOT null) AND
      (Employees.employee_id = AllManagers_ifr3.manager_id)
   UNION ALL

    SELECT
      Employees.employee_id AS employee_id,
      Employees.manager_id AS manager_id
    FROM
      t_1_Employees AS Employees
    WHERE
      (Employees.manager_id IS NOT null)

) AS UNUSED_TABLE_NAME  ORDER BY employee_id, manager_id ;

-- Executed on DuckDB:
| employee_id | manager_id |
|-------------|------------|
| 2           | 1          |
| 3           | 1          |
| 3           | 2          |
| 4           | 1          |
| 4           | 2          |
(5 rows)

$ synalog.compile('recursion.l', 'ShippingCost')
-- Initializing DuckDB environment.
create schema if not exists logica_home;
-- Empty record, has to have a field by DuckDB syntax.
drop type if exists logicarecord893574736 cascade; create type logicarecord893574736 as struct(nirvana numeric);
create sequence if not exists eternal_logical_sequence;

CREATE OR REPLACE TABLE logica_home.RouteCost_ifr0 AS WITH t_0_ShippingRoutes AS (SELECT * FROM (

    SELECT
      E'warehouse_main' AS origin,
      E'rotterdam' AS destination,
      4 AS cost
   UNION ALL

    SELECT
      E'rotterdam' AS origin,
      E'oslo' AS destination,
      3 AS cost
   UNION ALL

    SELECT
      E'warehouse_main' AS origin,
      E'oslo' AS destination,
      9 AS cost
   UNION ALL

    SELECT
      E'oslo' AS origin,
      E'helsinki' AS destination,
      2 AS cost

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      ShippingRoutes.destination AS destination,
      ShippingRoutes.cost AS cost
    FROM
      t_0_ShippingRoutes AS ShippingRoutes
    WHERE
      (ShippingRoutes.origin = E'warehouse_main')

) AS UNUSED_TABLE_NAME  ;

-- Interacting with table logica_home.RouteCost_ifr0

CREATE OR REPLACE TABLE logica_home.RouteCost_ifr1 AS WITH t_0_ShippingRoutes AS (SELECT * FROM (

    SELECT
      E'warehouse_main' AS origin,
      E'rotterdam' AS destination,
      4 AS cost
   UNION ALL

    SELECT
      E'rotterdam' AS origin,
      E'oslo' AS destination,
      3 AS cost
   UNION ALL

    SELECT
      E'warehouse_main' AS origin,
      E'oslo' AS destination,
      9 AS cost
   UNION ALL

    SELECT
      E'oslo' AS origin,
      E'helsinki' AS destination,
      2 AS cost

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      ShippingRoutes.destination AS destination,
      ShippingRoutes.cost AS cost
    FROM
      t_0_ShippingRoutes AS ShippingRoutes
    WHERE
      (ShippingRoutes.origin = E'warehouse_main')
   UNION ALL

    SELECT
      t_0_ShippingRoutes.destination AS destination,
      ((RouteCost_ifr0.cost) + (t_0_ShippingRoutes.cost)) AS cost
    FROM
      logica_home.RouteCost_ifr0 AS RouteCost_ifr0, t_0_ShippingRoutes
    WHERE
      (t_0_ShippingRoutes.origin = RouteCost_ifr0.destination)

) AS UNUSED_TABLE_NAME  ;

-- Interacting with table logica_home.RouteCost_ifr1

CREATE OR REPLACE TABLE logica_home.RouteCost_ifr2 AS WITH t_0_ShippingRoutes AS (SELECT * FROM (

    SELECT
      E'warehouse_main' AS origin,
      E'rotterdam' AS destination,
      4 AS cost
   UNION ALL

    SELECT
      E'rotterdam' AS origin,
      E'oslo' AS destination,
      3 AS cost
   UNION ALL

    SELECT
      E'warehouse_main' AS origin,
      E'oslo' AS destination,
      9 AS cost
   UNION ALL

    SELECT
      E'oslo' AS origin,
      E'helsinki' AS destination,
      2 AS cost

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      ShippingRoutes.destination AS destination,
      ShippingRoutes.cost AS cost
    FROM
      t_0_ShippingRoutes AS ShippingRoutes
    WHERE
      (ShippingRoutes.origin = E'warehouse_main')
   UNION ALL

    SELECT
      t_0_ShippingRoutes.destination AS destination,
      ((RouteCost_ifr1.cost) + (t_0_ShippingRoutes.cost)) AS cost
    FROM
      logica_home.RouteCost_ifr1 AS RouteCost_ifr1, t_0_ShippingRoutes
    WHERE
      (t_0_ShippingRoutes.origin = RouteCost_ifr1.destination)

) AS UNUSED_TABLE_NAME  ;

-- Interacting with table logica_home.RouteCost_ifr2

CREATE OR REPLACE TABLE logica_home.RouteCost_ifr1 AS WITH t_0_ShippingRoutes AS (SELECT * FROM (

    SELECT
      E'warehouse_main' AS origin,
      E'rotterdam' AS destination,
      4 AS cost
   UNION ALL

    SELECT
      E'rotterdam' AS origin,
      E'oslo' AS destination,
      3 AS cost
   UNION ALL

    SELECT
      E'warehouse_main' AS origin,
      E'oslo' AS destination,
      9 AS cost
   UNION ALL

    SELECT
      E'oslo' AS origin,
      E'helsinki' AS destination,
      2 AS cost

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      ShippingRoutes.destination AS destination,
      ShippingRoutes.cost AS cost
    FROM
      t_0_ShippingRoutes AS ShippingRoutes
    WHERE
      (ShippingRoutes.origin = E'warehouse_main')
   UNION ALL

    SELECT
      t_0_ShippingRoutes.destination AS destination,
      ((RouteCost_ifr2.cost) + (t_0_ShippingRoutes.cost)) AS cost
    FROM
      logica_home.RouteCost_ifr2 AS RouteCost_ifr2, t_0_ShippingRoutes
    WHERE
      (t_0_ShippingRoutes.origin = RouteCost_ifr2.destination)

) AS UNUSED_TABLE_NAME  ;

-- Interacting with table logica_home.RouteCost_ifr1

CREATE OR REPLACE TABLE logica_home.RouteCost AS WITH t_0_ShippingRoutes AS (SELECT * FROM (

    SELECT
      E'warehouse_main' AS origin,
      E'rotterdam' AS destination,
      4 AS cost
   UNION ALL

    SELECT
      E'rotterdam' AS origin,
      E'oslo' AS destination,
      3 AS cost
   UNION ALL

    SELECT
      E'warehouse_main' AS origin,
      E'oslo' AS destination,
      9 AS cost
   UNION ALL

    SELECT
      E'oslo' AS origin,
      E'helsinki' AS destination,
      2 AS cost

) AS UNUSED_TABLE_NAME  )
SELECT * FROM (

    SELECT
      ShippingRoutes.destination AS destination,
      ShippingRoutes.cost AS cost
    FROM
      t_0_ShippingRoutes AS ShippingRoutes
    WHERE
      (ShippingRoutes.origin = E'warehouse_main')
   UNION ALL

    SELECT
      t_1_ShippingRoutes.destination AS destination,
      ((RouteCost_ifr3.cost) + (t_1_ShippingRoutes.cost)) AS cost
    FROM
      logica_home.RouteCost_ifr1 AS RouteCost_ifr3, t_0_ShippingRoutes AS t_1_ShippingRoutes
    WHERE
      (t_1_ShippingRoutes.origin = RouteCost_ifr3.destination)

) AS UNUSED_TABLE_NAME  ;

-- Interacting with table logica_home.RouteCost

SELECT
  RouteCost.destination AS destination,
  MIN(RouteCost.cost) AS total
FROM
  logica_home.RouteCost AS RouteCost
GROUP BY RouteCost.destination ORDER BY destination;

-- Executed on DuckDB:
| destination | total |
|-------------|-------|
| helsinki    | 9     |
| oslo        | 7     |
| rotterdam   | 4     |
(3 rows)