TY - JOUR
T1 - Constraint-Based Query Evaluation in Deductive Databases
AU - Han, Jiawei
N1 - Funding Information:
Manuscript received September 18. 1990; revised May 1 I, 1992. and January 8. 1993. This work was supported in part by the National Sciences and Engineering Research Council of Canada under Operating Grant OGP-0037230, and in part by a research grant from the Centre for Systems Science at Simon Fraser University. This paper is a subrtantial revision of "Constraint-Ba\ed Reasoning in Deductive Databases," Proc. 7th /nf. Cot$ Duru En,?.. Kobe. Japan, Apr. 1991. pp. 257-265. The author is with the School of Computing Science, Simon Fraser University. Bumaby VSA 1S6, BC. Canada. IEEE Log Number 92 12680.
PY - 1994/2
Y1 - 1994/2
N2 - Constraints play an important role in the efficient query evaluation in deductive databases. In this paper, constraint-based query evaluation in deductive databases is investigated, with emphasis on linear recursions with function symbols. Constraints are grouped into three classes: rule constraints, integrity constraints, and query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows the following: 1) Rule constraints should be integrated 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 finite evaluability and termination for specific queries; and 3) query constraints, which are often useful in search space reduction and termination, should be transformed, when necessary, and should be pushed into the compiled chains as deeply as possible for efficient evaluation. Our constraint-based query-processing technique integrates query-independent compilation and chain-based query evaluation methods and demonstrates its great promise in deductive query evaluation.
AB - Constraints play an important role in the efficient query evaluation in deductive databases. In this paper, constraint-based query evaluation in deductive databases is investigated, with emphasis on linear recursions with function symbols. Constraints are grouped into three classes: rule constraints, integrity constraints, and query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows the following: 1) Rule constraints should be integrated 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 finite evaluability and termination for specific queries; and 3) query constraints, which are often useful in search space reduction and termination, should be transformed, when necessary, and should be pushed into the compiled chains as deeply as possible for efficient evaluation. Our constraint-based query-processing technique integrates query-independent compilation and chain-based query evaluation methods and demonstrates its great promise in deductive query evaluation.
KW - Deductive databases
KW - compilation techniques
KW - constraint-based query evaluation
KW - functional recursions
KW - linear recursions
KW - query optimization
KW - recursive query processing
UR - http://www.scopus.com/inward/record.url?scp=0028381756&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028381756&partnerID=8YFLogxK
U2 - 10.1109/69.273030
DO - 10.1109/69.273030
M3 - Article
AN - SCOPUS:0028381756
SN - 1041-4347
VL - 6
SP - 96
EP - 107
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 1
ER -