論理プログラムの意味論と問合せ処理の最適化技術の研究

点击翻译按钮获取中文摘要

論理プログラムの意味論と,その意味論に対応した問合せ処理の最適化技術について,特に,最適化方法の観点から様々な意味論の違いを明確化することを本研究の目的として,研究を行なった。対象とする論理プログラムとしては,通常の論理プログラムよりも表現力の高い,選言的論理プログラム(disjunctive logic programs)を取り上げた。選言的論理プログラムでは,プログラム節の頭部に論理和を許すため,不確定情報の表現が可能で,近年,仮説推論やアブダクション等の応用とも密接に関連することが分かり注目されてきている。プログラム節の本体に否定リテラルを含まないような選言的論理プログラム(postive disjunctive programs)を対象として,まず最適化方法の最も基本的な操作である展開(unfolding)操作を定義し,その操作が選言的論理プログラムの最小モデルを保存することを示した。この結果は,従来の確定ホーン節プログラムに対する最小エルブランモデルの保存という結果を拡張したものになっている。次に,プログラム節の本体に否定リテラルを含むようなより一般的な選言的論理プログラム(general disjunctive programs)に対して,展開操作が2値安定モデル(2-valued stable model)を保存することを示した。一方,安定モデル以外の意味論的性質について,例えば3値安定モデル(3-valued stable model)や,支持モデル(supported model)は,展開操作によって必ずしも保存されないことが分かった。また,選言的論理プログラムの重要な応用として,仮説推論について考察し,与えられた論理プログラムの持つ情報を利用して仮説推論の探索空間を絞り込む効率的な推論方法を提案した。