Constraint-based reasoning in deductive databases

Constraint-based reasoning in deductive databases is studied, with the focus on set-oriented, constraint-based processing of functional linear recursions. A technique is developed which compiles a functional linear recursion into chain or bounded forms and analyzes efficient processing of the compiled chains based on different kinds of constraints. It is shown that rule constraints should be compiled together with the rectified recursions; finiteness constraints and monotonicity constraints should be used in the analysis of finite evaluability and termination; and query constraints should be pushed into the compiled chains, when possible, for efficient set-oriented evaluation. Constraint-based processing can be enhanced by dynamic constraint enforcement in query evaluation. The method is illustrated using a typical traversal recursion problem. It is concluded that the principles developed are useful for a large set of deductive database application problems.