Extending the superimposed codeword indexing scheme to handle incomplete information

In order to use Prolog as a basis for database applications, techniques are required for rapid retrieval of clauses from large data sets. Various researchers have contributed to the development of indexing strategies for this purpose. One such strategy is known as superimposed codeword + mask bits (SCW + MB). One extension of Prolog which is useful in the development of deductive databases is the ability to handle incomplete information. A form of incomplete information based on sets has been introduced and used in a deductive database system. In order to provide efficient access to clauses containing incomplete information, existing strategies need to be adapted accordingly. This paper presents an extension to the SCW + MB algorithm to cover incomplete information, and describes how this can be realized in hardware. © 1998 Elsevier Science B.V. All rights reserved.