多変数線形再帰型演繹データベースに対する逆数え上げ評価法

Abstract

We consider to answer a datalog program that is a generalization of the well known same generation problem in the sense that it is defined over Cartesian product of m extensional predicates r_i. Each r_i is in general assumed to be cyclic. We present a method, which is the reverse counting method with a modification of termination test to deal correctly with cyclic predicates r_i, and analyze its three costs of complexity : space-requirement, database-access-time and test-time. When compared with the magic set method, which is also applicable to the same problem, this reverse counting method is inferior in the sense of worst-case bound of test-time but competitive in worst-case costs of other two. Some simulations are also conducted to examine these costs on randomly generated r_i. According to the simulation results, however, the reverse counting method is superior to the magic set method by orders of magnitude in the costs of space-requirement and database-access-time, and is in the same order in the cost of test-time.