Compilation-based list processing in deductive databases

Research output: Chapter in Book/Report/Conference proceedingConference contribution


List functions occur frequently in deductive database applications. We study efficient evaluation of linear recursions with list functions in deductive databases. Since most linear recursions can be compiled into chain forms, a chain-based query evaluation method is developed, which selects an efficient query evaluation algorithm based on the analysis of compiled forms and finiteness, termination and query constraints. Interesting techniques, such as chain-split, existence checking and constraint-based evaluation, are developed to improve the performance. Moreover, chain-based evaluation can be generalized to the complex recursions compilable to chain forms.

Original languageEnglish (US)
Title of host publicationAdvances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings
EditorsAlain Pirotte, Georg Gottlob, Claude Delobel
Number of pages16
ISBN (Print)9783540552703
StatePublished - 1992
Externally publishedYes
Event3rd International Conference on Extending Database Technology, EDBT 1992 - Vienna, Austria
Duration: Mar 23 1992Mar 27 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume580 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Conference on Extending Database Technology, EDBT 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Compilation-based list processing in deductive databases'. Together they form a unique fingerprint.

Cite this