Motivation for Extensions of the Standard PROLOG Indexing

The standard indexing method is only useful for procedures with a database-like structure, i.e. the first argument is a key (or at least a quasi-key: practically all constants are different, there a hardly any variables):

  p(c1, ...) :- ... .
  p(c2, ...) :- ... .
        ...
  p(cn, ...) :- ... .

Thus the standard indexing method does not work in the following cases:

1. the quasi-key is not the first argument of the procedure
2. the procedure can be split into several blocks each having another argument as a quasi-key
3. the quasi-key is spread over several arguments
4. there is more than one argument (group) that could serve as a quasi-key (this is important if the argument that is best suited for indexing is rarely instantiated in calls)
5. some combinations of cases 1-3 with case 4