New ACM paper, free-tier cloud, and open-source license

Lesson 10.2: Rule chaining

Simple rule chaining

Much like views in a relational database, which can be generated from other views, rules in TypeDB can leverage data generated by other rules. In fact, we’ve already seen an example of this in the previous lesson with the following rules.

rule review-verified-by-purchase:
    when {
        ($review, $product) isa rating;
        ($order, $product) isa order-line;
        ($user, $review) isa action-execution, has timestamp $review-time;
        ($user, $order) isa action-execution, has timestamp $order-time;
        $review-time > $order-time;
    } then {
        $review has verified true;
    };
rule review-unverified:
    when {
        $review isa review;
        not { $review has verified true; };
    } then {
        $review has verified false;
    };

Here, the second rule, review-unverified, has the following statement in its condition.

$review has verified true;

But this statement is also the conclusion of the first rule! This allows the rules to form a chain of logic. TypeDB resolves rules by backward chaining, which we’ll now explore an example of. Let’s say we issue the following query, which lists the IDs of unverified reviews.

match
$review isa review, has verified false;
fetch
$review: id;

When executing this query, TypeDB divides the pattern into individual constraints and attempts to search for each of them. Where there are dependencies between constraints, as described in Lesson 7.6, these constraints are resolved in the most efficient order as determined by the query planner. At some point, TypeDB will attempt to resolve the following constraint.

$review has verified false;

In addition to searching for data that meets this constraint on disk, TypeDB will also check rules in the schema to see if any of their conclusions match the constraint. In doing so, it will identify that the rule review-unverified concludes this constraint. As the condition of a rule implies its conclusion, TypeDB searches for data that matches this rule’s condition, as any match will satisfy the target constraint by the logic of the rule.

TypeDB treats the condition of this rule in the same way as the query pattern. First, it divides the condition into individual constraints. Then it attempts to search for each of them in some planned order, both on disk and in rule conclusions. As a result, TypeDB will eventually attempt to resolve the negated constraint.

$review has verified true;

The rule review-verified-by-purchase is identified as being able to satisfy it, and this process repeats itself, with TypeDB now searching for data matching its condition. This is the basic sequential mechanism of backward chaining. The inference engine works backward from the target constraint in the query, triggering rules sequentially along the way to form a chain. If the rule at the head of the chain is successfully resolved, then all the rules back up the chain are also resolved, and the target constraint is satisfied.

This pair of rules is just one example of rules that can form a chain, and rule chaining is a powerful method for encoding complex domain logic. As long as the condition of one rule contains the conclusion of another, the rules can chain into each other, and there is no limit to the permitted depth of a rule chain.

Recursive rule chaining

If the conclusion of a rule occurs in its own condition, it can form a chain with itself, leading to recursive behaviour. We have encountered the following rule several times since it was first introduced in Lesson 3.3, but now we will spend some time examining it.

rule transitive-location:
    when {
        (location: $parent-place, located: $child-place) isa locating;
        (location: $child-place, located: $x) isa locating;
    } then {
        (location: $parent-place, located: $x) isa locating;
    };

This rule is a recursive rule. If we compare the conclusion, it actually matches both statements in the condition. This means that when we infer $x to be located in $parent place, the facts that $x is located in $child-place and that $child-place is located in $parent place could both themselves be inferred.

Our data contains the following information encoded in locating relations:

  • The user with ID "u0003" is located in Newark.

  • Newark is located in New Jersey.

  • New Jersey is located in the United States.

When we run the following query, we get the following result.

match
$user isa user, has id "u0003";
(located: $user, location: $place) isa locating;
fetch
$place: name;
{
    "place": {
        "name": [ { "value": "Newark", "value_type": "string", "type": { "label": "name", "root": "attribute" } } ],
        "type": { "label": "city", "root": "entity" }
    }
}
{
    "place": {
        "name": [ { "value": "New Jersey", "value_type": "string", "type": { "label": "name", "root": "attribute" } } ],
        "type": { "label": "state", "root": "entity" }
    }
}
{
    "place": {
        "name": [ { "value": "United States", "value_type": "string", "type": { "label": "name", "root": "attribute" } } ],
        "type": { "label": "country", "root": "entity" }
    }
}

To retrieve the first result (Newark), we do not need to use the rule at all, because the fact the user is located there is written to disk. To retrieve the second result (New Jersey), we need to apply the rule once. To retrieve the third result (United States) we need to apply the rule twice. Similarly, if we had another level in our location hierarchy (perhaps North America), we would need to apply the rule three times to retrieve the result.

While the rule transitive-location is the easiest to understand of the rules in the bookstore schema, it is also the one with the most complex behaviour. Generating transitive relations is not the only use case for rule recursion, but it is by far the most common. Depending on the depth of recursion and the size of the dataset, recursive rules can be computationally intensive to resolve, so they should be used with caution. We will explore optimisation strategies for rules, including recursive ones, in Lesson 16 (coming soon).

Provide Feedback