Chain-Split Evaluation in Deductive Databases

Research output: Contribution to journalArticlepeer-review


Many popularly studied recursions in deductive databases can be compiled into one or a set of highly regular chain generating paths, each of which consists of one or a set of connected predicates. Previous studies on chain-based query evaluation in deductive databases take a chain generating path as an inseparable unit in the evaluation. However, some recursions, especially many functional recursions whose compiled chain consists of infinitely evaluable function(s), should be evaluated by chain-split evaluation, which splits a chain generating path into two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. In this paper, the necessity of chain-split evaluation is examined from the points of view of both efficiency and finite evaluation, and three chain-split evaluation techniques: magic sets, buffered evaluation, and partial evaluation are developed. Our study shows that chain-split evaluation is a primitive recursive query evaluation technique for different kinds of recursions, and it can be implemented efficiently in deductive databases by extensions to the existing recursive query evaluation methods.

Original languageEnglish (US)
Pages (from-to)261-273
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number2
StatePublished - Apr 1995
Externally publishedYes


  • deductive database
  • logic programming
  • query analysis
  • query optimization
  • query processing
  • recursive query evaluation

ASJC Scopus subject areas

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


Dive into the research topics of 'Chain-Split Evaluation in Deductive Databases'. Together they form a unique fingerprint.

Cite this