マジックセット法を用いた問合せ処理の停止性について

概要

論文の詳細を見る
論理プログラムで表された演えきデータベースの問合せ処理方法はトップダウン法とボトムアップ法に大別される.トップダウン法,ボトムアップ法どちらに対しても,有限時間内にすべての問合せの解を求めることが不可能な場合が存在する.これまで,トップダウン法とボトムアップ法のそれぞれに対して停止性に関する研究がいくつかなされている.また,両者の利点を併せもつマジックセット法という方法も提案されている.トップダウン法,ボトムアップ法のどちらを用いても問合せ処理は停止しないが,term depth abstractionを用いたマジックセット法では停止する場合がある.そこで本論文ではterm depth abstractionを用いたマジックセット法による問合せ処理の停止性の十分条件を提案する.また,この十分条件およびSohnとVan Gelderによるトップダウン法の停止性の十分条件を判定するアルゴリズムを利用し,与えられた論理プログラムと問合せが停止性を満たすかどうかを解析するアルゴリズムを提案する.
社団法人電子情報通信学会の論文
1994-07-25