Next: Allowing Variables in
Up: Using More Than
Previous: Depth Oriented (MDN)
The following algorithm (MNAlgorithm) combines the MNB and
MNDAlgorithms:
 For each argument column , create a list where
is the longest prefix of column without variables
 If then use the first clause as a
separate partition (without indexing) else
 sort the in descending order (w.r.t. their length)
into the list
 := length of first element in
 := position of last column in with length
with (this means
that in order to enlarge the index tree breadth the partition
size may be reduced, e.g. by at most 30%);
:= length of this column;
first elements of ;
reorder w.r.t. selectivity
 create a partition consisting of the first clauses;
index the argument columns in (
index tree breadth)
 for each constant/functor occurring multiply in one
argument column of this partition do
 form a procedure containing all selected clauses
and the remaining argument columns in
(only columns to the right of the current one)
 apply the MNAlgorithm recursively to this procedure
( index tree depth)
 If any clauses are left go to 1 else stop
MNAlgorithm applied to norm example:


 use clause 1 as first partition





 (
is too short, thus index tree breadth )

 second partition consists of clauses 2  9, indexing
takes place on first argument
 and/2 occurs four times in indexing column:
 form procedure from selected clauses:
 applying MNAlgorithm to this procedure:
 or/2 occurs four times in indexing column; result
analogously to and/2:
Resulting index tree:
Next: Allowing Variables in
Up: Using More Than
Previous: Depth Oriented (MDN)
Michael Sintek  sintek@dfki.unikl.de