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

鈴木　晋  茨木　俊秀  岸　政七  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.10   pp.934-943
発行日: 1992/10/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: データベース
キーワード: 
アルゴリズム,  計算複雑性,  演えきデータベース,  同世代問題,  問合せ処理,  

本文: PDF(629.9KB)>>
論文を購入



あらまし: 
演えきデータベースで扱われる有名な問題である同世代問題を一般化し，再帰述語の変数の数を2から一般のm（≧2）個にした問題を扱う．更に，基礎データを格納するm個の外延データベースはすべて閉路を含んでもよいとする．従来，m＝2の場合については多くの方法が提案されており，最悪時間量においてHaNa法が最も優れる．一般のmの場合についてはあまり研究されていないが，m≧3のとき，マジック集合法または一般のmに適用できるように素直に変形されたHaNa法が，最悪時間量において最も優れていると思われる（どちらの方法が優れているかは，問合せにおいて定数に固定されている変数の数hに依存する）．本論文では，m＝2に対して提案されたHaNa法をm≧3の場合に効率的になるように変形した拡張HaNa法を提案し，m≧3のとき，その最悪時間量がO（to（nmlogn＋nm-h│ANS│logn））であることを示す．ここで，toは再帰述語の初期値を与える外延データベースのタプル数，nは線形再帰式中の各外延データベースのグラフ表現における節点数，|ANS|は解のサイズである．拡張HaNa法が，m≧3かつ通常よく生じるデータの場合，マジック集合法およびHaNa法より優れていることを示す．