Constraint-Based Query Evaluation in Deductive Databases

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)96-107
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
StatePublished - Feb 1994
Externally publishedYes


  • Deductive databases
  • compilation techniques
  • constraint-based query evaluation
  • functional recursions
  • linear recursions
  • query optimization
  • recursive query processing

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Constraint-Based Query Evaluation in Deductive Databases'. Together they form a unique fingerprint.

Cite this