Dynamically Ordered Semi-Naive Evaluation of Recursive Queries

Abstract

Conventional fixed point evaluation techniques evaluate recursions by applying all rules repeatedly using an initial set of tuples (i.e., a given extensional database instance) until no new tuples are generated, but there is no specific order in which rules are applied. We can speed up the evaluation by applying rules in an appropriate order. In this paper, we propose a new fixed point evaluation technique, called the dynamically ordered semi-naive evaluation (or simply DYN), in which the next rule to be applied is determined at run time dynamically. DYN consists of a semi-naive algorithm and a set of selection strategies, The semi-naive algorithm allows dynamic ordering of rule applications and makes tuples generated by a rule application immediately available in the subsequent rule applications. After each rule application, the selection strategies determine the next rule by considering the syntactic structure of recursion and some information about the intermediate result up to the present. We develop these selection strategies so that the total number of rule applications and joins can be reduced. Through experimental comparisons, we shows that DYN outperforms the previous evaluation techniques in terms of the total number of rule applications and joins.