CONSTRAINT-BASED QUERY EVALUATION IN DEDUCTIVE DATABASES

Constraints play an important role in the efficient query evaluation i n deductive databases. In this paper, constraint-based query evaluatio n in deductive databases is investigated, with emphasis on linear recu rsions with function symbols. Constraints are grouped into three class es: rule constraints integrity constraints, and query constraints. Tec hniques are developed for the maximal use of different kinds of constr aints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of lin ear recursions shows the following: 1) Rule constraints should be inte grated with their corresponding deduction rules in the compilation of recursions; 2) integrity constraints, including finiteness constraints and monotonicity constraints, should be used in the analysis of finit e evaluability and termination for specific queries; and 3) query cons traints, which are often useful in search space reduction and terminat ion, should be transformed, when necessary, and should be pushed into the compiled chains as deeply as possible for efficient evaluation. Ou r constraint-based query-processing technique integrates query-indepen dent compilation and chain-based query evaluation methods and demonstr ates its great promise in deductive query evaluation.