| Did you know ... | Search Documentation: |
| Indexing databases |
The indexing capabilities of SWI-Prolog are described in section 2.17. Summarizing, SWI-Prolog creates indexes for any applicable argument, pairs of arguments and indexes on the arguments of compound terms when applicable. Extended JIT indexing is not widely supported among Prolog implementations. Programs that aim at portability should consider using term_hash/2 and term_hash/4 to design their database such that indexing on constant or functor (name/arity reference) on the first argument is sufficient. In some cases, using the predicates below to add one or more additional columns (arguments) to a database predicate may improve performance. The overall design of code using these predicates is given below. Note that as term_hash/2 leaves the hash unbound if Term is not ground. This causes the lookup to be fast if Term is ground and correct (but slow) otherwise.
:- dynamic
x/2.
assert_x(Term) :-
term_hash(Term, Hash),
assertz(x(Hash, Term)).
x(Term) :-
term_hash(Term, Hash),
x(Hash, Term).
This predicate may be used to build hash tables as well as to exploit argument indexing to find complex terms more quickly.
The hash key does not rely on temporary information like addresses of
atoms and may be assumed constant over different invocations and
versions of SWI-Prolog.91Last
change: version 10.1.20 Numbers are hashed by their value,
so the hash does not depend on how a number is represented. The term_hash/2
predicate is cycle-safe.bugAll
arguments that (indirectly) lead to a cycle have the same hash key.
Hashes are the same on all platforms (byte order, word size and size of wchar_t).
HashKey is in the range [0 ...Range-1]. Range must be in the range [1 ... 2147483647].
This predicate raises an exception when trying to compute the hash on an attributed term. Attributed terms are not handled because subsumes_chk/2 is not considered well defined for attributed terms.
Cyclic terms are supported. The hash is taken over a canonical form of the term graph, so that terms denoting the same infinite tree hash alike however many cells they were written with. That is, given A=[a|A] and B=[a,a|B], A and B produce the same hash. Note that the hash of a cyclic term is not the hash of any acyclic term, as a cyclic term is never =@=/2 to one.
This hash was developed for lookup of solutions to a goal stored in a table. By using a cryptographic hash, heuristic algorithms can often ignore the possibility of hash collisions and thus avoid storing the goal term itself as well as testing using =@=/2.