Homomorphism module

Download this module

This module provides several implementations of the Homomorphism interface family.

Backtrack based homomorphisms

The implementations called BacktrackHomomorphism, BacktrackHomomorphismPattern and BacktrackHomomorphismWithNegation are based on a backtracking search over variables. Optimizations are inspired by constraint satisfaction algorithms, see in particular Jean-François Baget's PhD Thesis (Chapter 5, in French), or Backtracking Through Biconnected Components of a Constraint Graph by J.-F. Baget, Y. Tognetti, IJCAI 2001.

This homomorphism algorithm is configurable with :

a Scheduler
defines the order in which variables are assigned.
a Bootstrapper
computes the initial domain of a variable when it is not already restricted by the forward checking approach.
a ForwardChecking approach
after assignation of a variable, restricts the domain of neighboring variables.
a BackJumping approach
allows the backtrack to jump over some variables.

Others

This module also provides other homomorphisms for particular cases such as homomorphism for a union of conjunctive queries (DefaultUCQHomomorphism ), for atomic queries (AtomicQueryHomomorphism ) or for a small set of facts (PureHomomorphism ).

Smart one

If you do not know which homomorphism you should use, you can use the class SmartHomomorphism which will make a choice for you. This choice is made thanks to implementations of HomomorphismChecker associated with each homomorphism implementation. Each HomomorphismChecker implementation allows to check if the associated homomorphism is applicable and it defines a priority for it.

You can allow SmartHomomorphism to take your own homomorphism implementation into account by loading an associated HomomorphismChecker with the addChecker method.

RuleCompilation based Homomorphism

Each homomorphism implementation described above is able to take into account a preorder associated with compiled rules: RulesCompilation . See the following paper for the theoretical foundations of rule compilation: Query Rewriting for Existential Rules with Compiled Preorder by M. König, M. Leclère, and M.-L. Mugnier, IJCAI 2015.