Next: Future Extensions
Up: Allowing Variables in
Previous: The 1V-Algorithm
- For each argument column , create a list where
is the longest prefix of column with at most a number and
percentage %of 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 ;
:= 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 MV-Algorithm recursively to this procedure
( index tree depth)
- If any clauses are left go to 1 else stop
Result of using the MV-Algorithm on our norm example:
In the above DAX, some sub-DAXes were pruned in order to reduce memory
consumption. This pruning is performed by the pruning algorithm
explained in [Ste92].
The benchmarks in appendix C give you an impression of
the efficiency gains of the MV-Algorithm.
Next: Future Extensions
Up: Allowing Variables in
Previous: The 1V-Algorithm