多変数同世代問題に対する問い合わせ評価法

Abstract

We consider a generalization of the same generation problem, which is well known in the deductive database theory, in the sense that the arity of a recursive predicate is generally m and that each extensional database may be cyclic. For the case of m≥3,among developed methods, the magic set method or the HaNa method appears most efficient in worst-case time complexity. We propose here a modification of the HaNa method and analyze its worst-case performance. When m≥3 and some usual conditions are satisfied, the modified HaNa method is superior to the magic set method and to the HaNa method.