Magic set computation with differential representation of facts

Takahiko Suzuki, Toshihisa Takagi, Kazuo Ushijima

Research output: Chapter in Book/Report/Conference proceedingChapter


We propose an implementation technique of a bottom-up computation in deductive database systems based on the Magic Set method. This technique improves the performance of generate-and-test type programs which use function symbols. Our technique consists of SIPS that enable set-oriented computation and differential representation of sets. The cost of the set-oriented computation can be reduced by using a differential representation of sets. This technique, for example, is applicable to retrieval of paths between two nodes in a graph. When the two nodes are connected by a single path, the cost of computation using this technique is O(N), while the cost with a naive application of the Magic Set method is O(N2).

Original languageEnglish
Title of host publicationMemoirs of the Kyushu University, Faculty of Engineering
PublisherPubl by Kyushu Univ
Number of pages14
Publication statusPublished - Dec 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Energy(all)
  • Earth and Planetary Sciences(all)
  • Management of Technology and Innovation
  • Atmospheric Science


Dive into the research topics of 'Magic set computation with differential representation of facts'. Together they form a unique fingerprint.

Cite this