Substitution-based compilation of extended rules in deductive databases

Sang Ho Lee, Lawrence Joseph Henschen

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

1 Scopus citations


Query compilation in a deductive database refers to the process of continually replacing defined literals in rule bodies by their definitions until rules with references only to stored relations are obtained. The compiled forms generate the same tuples for the head literal in a database as do the original sets of rules. Previously, the rules were assumed to be function free. However, the use of universal quantifiers (corresponding to the division operator in a database) adds a new degree of flexibility in defining views. We propose a new inference rule, the substitution rule, to replace resolution in the compilation process. The substitution rule handles the embedded universal quantifiers correctly so that the compiled forms again derive all proper instances of the head literals.

Original languageEnglish (US)
Title of host publication10th International Conference on Automated Deduction, Proceedings
EditorsMark E. Stickel
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540528852
StatePublished - 1990
Event10th International Conference on Automated Deduction, CADE 1990 - Kaiserslautern, Germany
Duration: Jul 24 1990Jul 27 1990

Publication series

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


Other10th International Conference on Automated Deduction, CADE 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Substitution-based compilation of extended rules in deductive databases'. Together they form a unique fingerprint.

Cite this