Indexing PROLOG Procedures into DAGs by Heuristic Classification
This paper first gives an overview of standard PROLOG indexing and
then shows, in a step-by-step manner, how it can be improved by slightly
extending the WAM indexing instruction set to allow indexing on
multiple arguments. Heuristics are described that overcome the
difficulty of computing the indexing WAM code. In order to become
independent from a concrete WAM instruction set, an abstract graphical
representation based on DAGs (called DAXes) is introduced.
The paper includes a COMMON LISP listing of the main
heuristics implemented; the algorithms were developed for RELFUN,
a relational-plus-functional language, but can easily be used in arbitrary
The ideas described in this paper were first presented
at the Workshop
``Sprachen für KI-Anwendungen, Konzepte - Methoden -
Implementierungen'' 1992 in Bad Honnef [SS92].
This paper is part of a collaborative work together with Werner Stein