I'm publishing this series ahead of Code BEAM Europe this October, where I'll reveal Bondy, a new declarative language for the BEAM: statically typed, functional, relational and rule-based.

Every codebase has one of these. Who is in Alice's management chain? Which products can substitute for this one, directly or through a chain of substitutes? Which documents can this user reach through the groups they belong to? You write it as a recursive function over a list of pairs:

%% reports: [{Who, Boss}]
manages(Boss, Who, Reports) ->
    lists:member({Who, Boss}, Reports)
    orelse lists:any(
        fun({W, B}) ->
            W =:= Who andalso manages(Boss, B, Reports)
        end, 
        Reports
    ).

It works until the data has a cycle, and then it never returns. So you add a visited set:

manages(Boss, Who, Reports) ->
    manages(Boss, [Who], Reports, sets:new()).

manages(_Boss, [], _Reports, _Seen) ->
    false;
manages(Boss, [W | Rest], Reports, Seen) ->
    case lists:member({W, Boss}, Reports) of
        true -> 
            true;
        false ->
            Next = [
                B ||  {W1, B} <- Reports, W1 =:= W,
                        not sets:is_element(B, Seen)
            ],
            manages(
                Boss, 
                Next ++ Rest, 
                Reports, 
                sets:add_element(W, Seen)
            )
    end.

Now it terminates. It is a depth-first search with an accumulator, written by hand. Yet the question it answers is one sentence long: B manages W if W reports to B, or W reports to someone B manages. The search order, the cycle protection and the accumulator are not part of the question. They are the price of asking it in a language whose only tool for "what follows from these facts" is a function that walks them.

Facts you look up

The second post called this the relation role. A relation holds facts, and you can ask about them in either direction: who Alice reports to, or who reports to Carol. Here it is, and every line compiles:

relation ReportsTo = {who: String, boss: String}

fact ReportsTo(who: "alice", boss: "bob")
fact ReportsTo(who: "bob", boss: "carol")

relation Manages(boss: String, who: String) :-
    ReportsTo(who: who, boss: boss)

relation Manages(boss: String, who: String) :-
    ReportsTo(who: mid, boss: boss), 
    Manages(boss: mid, who: who)

relation ReportsTo = {...} declares what a fact looks like and makes it a relation. A fact declaration is static data written into the module: the facts the relation starts with. The next section shows how facts come and go while the program runs.

The two Manages lines are a derivation rule, the second kind of rule in Bondy. Read :- as "if". Bob manages Alice if Alice reports to Bob. Carol manages Alice if Alice reports to someone Carol manages. Two rules for the same relation mean "either one": Manages holds whenever either rule says so.

Then you ask:

public function team_of(boss: String) ->
    query Manages(boss: boss, who: w) end

public function bosses_of(who: String) ->
    query Manages(boss: b, who: who) end

team_of returns every w the rules can reach. A field with a value is a filter, and a field left as a variable is what you want back. bosses_of asks the same relation the opposite question, everyone above a person, with no second traversal. With the two facts above:

team_of("carol") => [{"alice"}, {"bob"}]
bosses_of("alice") => [{"bob"}, {"carol"}]

Each answer is a tuple with one element per variable you left open.

Where the facts live

A relation says what a fact looks like. It says nothing about where facts are kept. That is the job of a relation store: a supervised process that owns the storage for a set of relations. You declare one as a module implementing the Relation.Store behaviour, with four required callbacks:

module Org.Store implements Relation.Store

import Org.{relation ReportsTo}

public function name() :: Atom -> 
    :org

public function adapter() :: Module -> 
    Relation.Adapter.Table

public function opts() :: Map -> 
    #{}

public function relations() :: List(TypeRef) -> 
    [ReportsTo]

adapter() picks the backend. Relation.Adapter.Table keeps the facts in ETS, in memory. Postgres.Relation.Adapter keeps them in PostgreSQL tables, with options such as the schema to use and whether to create the tables on start:

public function adapter() :: Module -> 
    Postgres.Relation.Adapter

public function opts() :: Map ->
    #{
        :schema => "public", 
        :ddl => :drop_and_create, 
        :on_destroy => :drop
    }

Moving between the two changes the store module and nothing else. The relations, the rules and the queries stay the same, because they never mentioned storage in the first place. You start a store with Relation.Store.start(Org.Store), which runs it under Bondy's own supervisor, or put Relation.Store.start_link/1 in your supervision tree. When it starts, it creates the storage and loads the relation's fact declarations into it.

From then on, facts come and go at runtime. You look up the relation's storage and insert or delete rows, each row built with the relation's constructor:

let Ok(reports) = Relation.Registry.lookup(ReportsTo)

Relation.Adapter.Table.insert(
    reports, 
    ReportsTo(who: "dee", boss: "carol")
)
%% => Ok(:inserted)

Relation.Adapter.Table.delete(
    reports, 
    ReportsTo(who: "alice", boss: "bob")
)
%% => Ok({:deleted, ReportsTo(who: "alice", boss: "bob")})

insert refuses a row of the wrong relation with Error(:wrong_relation), and delete returns Error(:not_found) for a row that is not there. The next query sees the change, derived relations included, because a query evaluates the rules over whatever the store holds at that moment. After the two calls above, team_of("carol") includes Dee, and Alice is no longer anyone's report.

There is no update. A fact is a statement that something is true. When it stops being true you delete it, and when something new becomes true you insert that. Changing Alice's manager is a delete of the old fact and an insert of the new one.

Why it terminates

The recursive Manages has no visited set because it does not need one. The engine evaluates derivation rules in rounds: start with the facts, apply every rule, add whatever is new, and repeat until a round adds nothing. Manages only recombines names that are already in the facts, so the rounds run out. A cycle in the data produces facts that already exist, so it adds nothing. Each round also only looks at what changed in the round before, so the engine doesn't redo work.

A rule that computes a new value in its body, such as n = m + 1, is different: it can add a new fact in every round. The compiler accepts it, and the engine stops it at a round limit with a fixpoint_diverged error.

That is what Seen did in the Erlang version, except you don't have to remember to write it. And the first Erlang version, the one that loops forever, can't be written at all.

Facts plus "if" rules, repeated until nothing new appears, is Datalog. It dates from 1977, and a lot of graph and policy engines run on it.

Negation, and the version the compiler refuses

Sometimes the question is about absence. Who has no manager? Which node has no outgoing edge?

relation Node = {name: String}
relation Edge = {from: String, to: String}

relation Isolated(name: String) :-
    Node(name: name), 
    not Edge(from: name, to: _)

not Edge(...) succeeds when there is no matching fact. This is where "repeat until nothing changes" can go wrong. If A is defined as "not B" and B as "not A", each new A takes away a reason for a B, and the other way round. So the rounds never settle. Datalog handles this with stratification: a relation has to be fully computed before a rule can ask what is not in it. That excludes any relation that depends on its own absence.

I wrote the bad case to see what happens:

relation A(name: String) :- 
    Node(name: name), 
    not B(name: name)

relation B(name: String) :- 
    Node(name: name), 
    not A(name: name)

The compiler rejects it as unstratifiable and names the cycle: ['Bondy.Probe.B','Bondy.Probe.A']. It is the relation-side counterpart of the guard check on rewrite rules from two posts ago: a program that could not have a well-defined answer does not compile.

An example with three relations

Access control is where most people meet this, because some part of the policy is always transitive. Users own resources. Admins can reach everything. A manager can reach what their reports own:

relation User      = {id: String, name: String, role: Atom}
relation Resource  = {id: String, owner: String}
relation ReportsTo = {who: String, boss: String}

relation CanAccess(user: String, resource: String) :-
    Resource(id: resource, owner: user)

relation CanAccess(user: String, resource: String) :-
    User(id: user, role: :admin), 
    Resource(id: resource)

relation Manages(boss: String, who: String) :-
    ReportsTo(who: who, boss: boss)

relation Manages(boss: String, who: String) :-
    ReportsTo(who: mid, boss: boss), 
    Manages(boss: mid, who: who)

relation CanAccess(user: String, resource: String) :-
    Manages(boss: user, who: owner), 
    Resource(id: resource, owner: owner)

Five rules, each one a line from the policy document. The function version would be a can_access/2 with three branches, one calling the manages/3 from the top of this post, and next year a fourth branch for delegated access. Here that is one more rule.

The CanAccess rules also don't say which one to try first, when to stop, or what to cache. The engine decides that.

Two stores, two kinds of rule

We have now seen both kinds of rule, so here they are side by side.

A derivation rule works over relations. It only adds facts, worked out from the ones already there. It never removes anything, so it finishes whenever its rules only recombine values already in the facts (stratification takes care of not). This is Datalog.

A rewrite rule works over constraints, the facts rules act on. It removes and replaces: a Bucket with three tokens becomes a Bucket with two, and the old one is gone. This is CHR. Because it can remove, the compiler has to check what Datalog gets for free, which is what the guard check in the rules post does.

Both match facts the same way. A ReportsTo in a relation and a Bucket in a constraint store are both values of a structural type. A rule matches either one by unification, the operation the third post shows in detail. You call neither kind of rule: both fire on their own. They do live in different stores, on purpose. Facts you look up and facts rules act on behave differently, so keeping them apart lets the compiler check each kind for what can go wrong with it.

That covers the roles that ship, and both kinds of rule. Before the roles that are still in design, one question the series has kept deferring: how does the compiler know a guard is pure? That is the next post.