Lesson 10.2: 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.

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

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.

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.

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.

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.

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.

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:

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

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.