Efficient evaluation of functional recursive query programs in deductive databases
Wang Jiang · Summit (Simon Fraser University) · 1991
Functional recursive query programs are recursive query programs expressed in Horn clause logic with function symbols.The functional recursions studied in this thesis are confined to one commonly used class of recursions: linear recursions.We compile a functional linear recursion into a highly regular compiled formula and analyze the safety and the evaluation of the compiled formula with respect to a given query and a set of constraints sgecified over a given database instance.We show that for the functional linear recursions, safety can be viewed as a combination of two properties: frnie evaluability, which guarantees the finiteness of intermediate answers, and termination, which guarantees the finiteness of the evaluation.We present a necessary and sufficient condition guaranteeing the finite evaluability of compiled formulas and a sufficient condition guaranteeing the termination of the evaluation.The algorithms for testing these conditions are developed-Based on the analysis of safety, we present a safe, constraint-based evaluation method for compiled formulas.We classify constraints into three classes: (i) integrity constraints, (ii) rule constraints and (iii) query constraints.We show that integrity constraints should be used to generate safe evaluation plans.Rule constraints can 5e used in compilation to reduce the search space.Query constraints are shown to be useful in the selection of efficient evaluation plans and search space reduction.