In this section we provide an overview of several indexing schemes which is a slightly revised version of section 6 in [Ste92]. They can be distinguished into hardware oriented and software oriented approaches.
The hardware oriented approaches are based on database techniques. A hash-function returns, for a given query, a set of clauses as potential matches. This is done separately from the compilation of the program, so clauses (maybe a very large number of clauses) can be stored separately (e.g. externally).
Most software oriented indexing schemes use a mixed storage of index and clause code, so the whole program must be loaded at run time.