Next: The 1V-Algorithm Up: Our Approach Previous: Breadth and Depth

Allowing Variables in Index Blocks (1V and MV)

In order to obtain larger and thus more efficient partitions (w.r.t. time), indexed argument columns should be allowed to contain some variables. If, for example, an argument column contains the sequence (1,2,X,2,1), it makes sense to form a single partition from all 5 clauses; if a 1 is presented to this partition, only the clauses 1,3,5 have to be tried. If a constant other than 1 or 2 or any structure or list is presented to this partition, the third clause has to be tried. The standard switch_on_constant and switch_on_structure instructions cannot handle this situation which made it necessary to add the else argument to these instructions.

The algorithms for generating index trees with variables allowed in partitions (1V- and MV-Algorithms) can easily be obtained from the 1N-Algorithm and MN-Algorithm by simply replacing the restriction ``no variables'' by ``at most a number and percentage %of variables''.

is called the block variable size and specifies the maximal number of variables an argument column of a partition is allowed to contain; is the maximal portion (in %) of variables in a partition's argument column.

Michael Sintek -