Next: Allowing Variables in Up: Using More Than Previous: Depth Oriented (MDN)

### Breadth and Depth Oriented (MN)

The following algorithm (MN-Algorithm) combines the MNB- and MND-Algorithms:

1. For each argument column , create a list where is the longest prefix of column without variables
2. 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 MN-Algorithm recursively to this procedure ( index tree depth)
3. If any clauses are left go to 1 else stop

MN-Algorithm 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 MN-Algorithm 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.uni-kl.de