Compilation-based list processing in deductive databases

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

Abstract

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
PublisherSpringer-Verlag
Pages104-119
Number of pages16
ISBN (Print)9783540552703
DOIs
StatePublished - Jan 1 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

Other

Other3rd International Conference on Extending Database Technology, EDBT 1992
CountryAustria
CityVienna
Period3/23/923/27/92

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this