Quick links

Benchmarking Multi-Rule Recursion Evaluation Strategies

Report ID:
TR-141-88
Date:
February 1988
Pages:
26
Download Formats:
[PDF]

Abstract:

This paper presents an empirical comparison of the Semi-Naive, Generalized Magic Sets, Generalized Counting, and Separable query evaluation strategies as applied to queries on multi-rule recursions. I used each of the methods to evaluate queries over randomly generated relations. For each query there
is a critical density range. If the base relations are below the density range, Generalized Magic Sets, Generalized Counting, and Separable provide roughly equal performance and are significantly better than Semi-Naive. Above the density range, Generalized Magic Sets degrades to Semi-Naive, Generalized
Counting is much worse that Semi-Naive, while Separable is still significantly better than Semi-Naive. This suggests that special purpose algorithms such as Separable can greatly improve the performance of a recursive query processor.

Follow us: Facebook Twitter Linkedin