Clause Indexing

The Jekejeke Prolog system is capable of dynamically creating indexes for multiple argument positions and that might span multiple arguments. Naïvely scanning the full clause set of a defined predicate would be inefficient. Therefore when a defined predicates is invoked an analysis of the arguments of the calling goal is performed:

  1. First Argument Indexing: When the defined predicate is called with a non-variable first argument then the functor of this argument is used in a hash table lookup to find a smaller set of clauses for scanning.
  1. Non-First Argument Indexing: If the first argument is a variable then the calling goal is searched for another argument which is non-variable and the functor of this argument is then picked for a hash table lookup.
  1. Multi-Argument Indexing: The hash table does not only point to clause sets but also to further hash tables so that recursively after a found non-variable argument further non-variable arguments can be searched in the calling goal.

When clauses are consulted or asserted no indexes are maintained by default. Only after a defined predicate has been first invoked and the arguments have been analysed indexes are created. The index that is created is thus dependent on the call history of the predicate. Dynamic clause indexing is both available for static, dynamic and thread local predicates.

In general the resulting indexing structure need not be the same for different hash entries. When clauses are retracted and a clause set reaches zero size, then the corresponding hash entry is removed. The hash table automatically resizes to smaller sizes if necessary. When the hash table points to a trivial clause set of size one then search continues for an alternative indexing argument to further restrict the clause set.

When building the index we also consider constraints in the body of a clause. What we can currently detect are constraints of the form var(X) where X is a variable. If an argument of an indexed clause is a variable it takes a different route into the index depending whether it is guarded by such a constraint or not. When calling the predicate non variable arguments can take the non-guarded route.

The YAP Prolog system [7, section 6] does a similar dynamic clause indexing. But additionally the system considers constraints such as bindings and type checks defined in the body of each clause. Currently we do not incorporate bindings into our index. The Ciao Prolog system [8, section 88] allows declaring multi-argument indexes. In the declaration one can specify the key type. It is possible to index argument either on the functor or on the full term. Currently we do not support indexes based on full terms.

The following Prolog flags for the clause indexing are provided:

sys_clause_index:
Legal values are on and off. The flag indicates whether clause indexing is enabled for the knowledge base. Default value is on. Value can be changed.

Kommentare