Classification and compilation of linear recursive rule cluster

Compilation and interpretation are two fundamental methods used in the query process in deductive database systems. The compilation approach is superior when recursive queries are present, since it allows a database management system to precompile query forms and thus eliminates repetitive computations during the query execution phase. Although there are a few methods for compiling single linear recursive rule clusters, new technique is needed to systematically compile complex recursive rule clusters and their queries.;This dissertation presents a novel approach to compile linear recursive rule clusters, including those complicated recursive rule clusters involving mutual recursions. A graph model which shows relationship among the rules in a recursive rule cluster is used to study the behaviors of these rules. Based on such a graph model, all the linear recursive rule clusters can be classified into four disjoint classes. The recursive rule clusters in each class have the same characteristics in compilation and query evaluation processes. And the sets of successful paths for the recursive rule clusters in one class share the same pattern. By studying the recursive rule clusters of each class, a successful path based compilation algorithm is developed for each class. And a general compiled formula has been derived for each of the first three classes. These formulas include new recursive forms which have never been compiled before. A class detection algorithm is also presented for determining which class a linear recursive rule cluster belongs to. The compiled formula of any linear recursive rule cluster can then be generated by applying one of the compilation algorithms depending on the classification.;The query evaluation phase has also been discussed. A uniform multi-level counting technique is proposed to process queries of linear recursive rule clusters by utilizing their corresponding compiled formulas.