Forward-chaining (chase) module

This module provides several implementations of the forward chaining mechanism, aka chase:

The BreadthFirstChase is the most basic one. At each step, it computes all the homomorphisms from the rule bodies to the current set of facts then perform the corresponding rule applications. At each step after the first one, rules are checked based on the presence of a predicate of their body in the head of a rule applied in the previous step. Furthermore, for optimization reasons, linear rules (with a single atom in the body) are applied over a set of atoms restricted to the atoms generated at the previous step which have the same predicate as the body rule atom.
The ChaseWithGRD improves the preceding basic chase by triggering rules according to the graph of rule dependencies (ie the rules checked at each step after the first one are the successors in the GRD of the rules actually applied at the previous step).
The SccChase applies rules following the layers of the Graph of Strongly Connected Components (SCCG) of the Graph Of Rule Dependencies. It saturates the facts with the rules in a layer before going to the next layer. Differently from the preceding ones, this chase is not breadth-first.

Different kinds of Chase

Several chase variants exist in the litterature that differ on the conditions of applicability of a rule (roughly, more or less redundancies can be avoided). Graal implements the restricted chase (aka standard chase) and the frontier-restricted chase (aka semi-oblivious, and equivalent to skolem chase). Both are available for all previous forward chaining algorithms. The chase behavior can be selected by specifying a RuleApplier to the Chase constructor. A RuleApplier defines the conditions of rule application.

The main implementation called DefaultRuleApplier generates a query from the rule's body, then evaluates it with the SmartHomomorphism . Finally for each found substitution of the query, it calls a ChaseHaltingCondition to generate new data with respect to the kind of chase. The FrontierRestrictedChaseHaltingCondition applies a rule according to a homomorphism from its body to the data if it has not already been applied with another homomorphism that maps the rule's frontier in the same way. The RestrictedChaseHaltingCondition applies a rule to a fact base F according to a homomorphism h if h cannot be extended to a homomorphism from B ∪ H to F where B is the rule body and H its head.

The RestrictedChaseRuleApplier is an optimized implementation of the restricted chase. It generates a ConjunctiveQueryWithNegatedParts of the form B ∧ ¬H where B is the rule body and H the rule head (which must not be found, hence the negation).