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.