Abstract

With the magic sets techniques having been proposed to improve the efficiency of bottom-up evaluations of Datalog programs by taking advantage of goal structure, we extend these techniques to deductive databases with uncertainty in the context of the parametric framework (PF). In our endeavor, we develop the generalized magic sets and generalized supplementary magic sets techniques, and establish their correctness. We have implemented the proposed techniques and have conducted numerous experiments for the assessment of the evaluation performance. Our experiment results reveal that different programs enjoy different efficiency gain, depending on the potential facts ratio, which measures the capacity to improve efficiency. When this ratio ranges from 1% to 20%, the efficiency observed was approximately 1 to 700 times faster. Our results also indicate that an integration of magic sets techniques and semi-naive evaluation with predicate partitioning yield the best performance.