Chain-split evaluation in deductive databases

A chain-split evaluation technique for the efficient evaluation of recursions in deductive databases is described. Three chain-split evaluation techniques: magic sets, buffered evaluation, and partial evaluation, are developed. The first one is applicable to the evaluation of function-free recursions. The latter two are applicable to both function-free and functional recursions. Partial evaluation is a further refinement of the buffered evaluation by evaluating the buffered functional predicates as much as possible to reduce the cost of maintaining the sequences of buffered values and facilitates termination judgment and constraint pushing. Chain-split evaluation is an important recursive query processing technique which can be implemented efficiently in deductive databases by extension to the available recursive query evaluation techniques.