補足マジックセット法における否定の効率的処理

概要

論文の詳細を見る
演繹データベースの分野では,再帰や否定を含むデータベースの効率的評価法の研究が盛んにおこなわわれている.再帰を処理するための効率のよい手法として一般化マジックセット法や,その改良版である補足マジックセット法(Supplementary Magic Set Method)がある.これらの手法は,ボトムアップ評価とルール書き換えとに基づいている.上記手法を,否定を処理できるように拡張した手法がいくつか提案されている.しかし,それらの拡張手法にはむだな処理が含まれている.我々は[STU89]において,一般化マジックセット法を拡張した否定処理に含まれるむだな処理を指摘し,効率を改善するための手法を提案した.我々の手法はインデックス付けと,導出監視ファクトの生成とに基づいている.しかしながら,この手法では,効率改善を実現するために,ボトムアップ処理系とは異なる外付の機構で一部の機能を実現しており,処理系が複雑になっていた.本稿では,補足マジックセット法を拡張した否定処理法に対しても,同様な効率改善が可能であることを示す.本稿の手法は,我々が以前提示した手法よりも,次の2つの点で優れている.第1に,補足マジックセット法を基にすることによって,通常のルールと同じ形式のルールで,我々の手法を実現することが可能になり,処理系が単純化できる.第2に,冗長なルールの発生を防止できる.本稿で使用する,リテラル,ゴール,ルール,ボディ,ヘッドなどの用語の定義は,一般的な論理プログラムの定義に従う.
一般社団法人情報処理学会の論文
1989-10-16

補足マジックセット法における否定の効率的処理

スポンサーリンク

概要

著者

関連論文

スポンサーリンク