AIT Associated Repository of Academic Resources >
A.研究報告 >
A1 愛知工業大学研究報告 >
3.愛知工業大学研究報告 .B(1976-2007) >
26号 >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11133/867
|
Title: | 多変数線形再帰型演繹データベースに対する逆数え上げ評価法 |
Other Titles: | タヘンスウ センケイ サイキガタ エンエキ データベース ニ タイスル ギャクカゾエアゲ ヒョウカホウ Reverses Counting Method for Linear Recursive Query with Many Cyclic Extensional Predicates |
Authors: | 鈴木, 晋 茨木, 俊秀 岸, 政七 SUZUKI, Susumu IBARAKI, Toshihide KISHI, Masahichi |
Issue Date: | 31-Mar-1991 |
Publisher: | 愛知工業大学 |
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. |
URI: | http://hdl.handle.net/11133/867 |
Appears in Collections: | 26号
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|