著者

鈴木 晋 茨木 俊秀

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.42, no.1, pp.48-58, 2001-01-15

---

演繹データベースの新しい問題クラスである直積問題クラスを定義する.直積問題クラスは右線形問題や同世代問題を包む,datalog問題クラスの部分クラスである.このクラスを効率的に解くために直積法を提案する.従来の方法が中間データとして基礎アトムを生成するのに対し,直積法は基礎アトムの集合を直積を利用して簡潔に表す式を生成する.これにより,直積法は生成する中間データの数を減らして,問題を効率的に解こうとする.直積問題クラス全体に適用できる従来の方法の中ではマジック集合法が最も効率的であると思われる.そこで,直積法とマジック集合法の効率を比較するために,直積問題の例として同世代問題の再帰ルールを複数にした問題および非線形にした問題を使って,計算機実験を行った.実験の結果,ファクトをランダムに生成した場合,どちらの問題に対しても問題がファクトを密に含むとき,直積法がマジック集合法より効率的であることが分かった.We define a new problem class of deductive databases, called the Cartesian product problem class (abbreviated to the CP class).The CP class is a subclass of the datalog problem class, and includes the right-linear problem, the same generation problem and others.To solve the CP class efficiently, we propose the Cartesian product method (abbreviated to the CP method).Although all the existing methods generate ground atoms as intermediate data, the CP method generates Cartesian products, each of which compactly expresses a set of ground atoms.Thus the CP method tries to reduce the number of generated intermediate data and, consequently, to solve problems efficiently.Among the existing methods applicable to the whole CP class, the magic set method seems most efficient.For performance comparisons of these two methods, we conducted experiments with two types of modified same generation problems, where one had two recursive rules and the other a non-linear recursive rule.The experimental results show that the CP method is more efficient than the magic set method when problems densely contain the facts generated at random.