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

鈴木 晋  茨木 俊秀  岸 政七  

誌名
電子情報通信学会論文誌 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のとき,その最悪時間量がOtonmlognnm-hANS│logn))であることを示す.ここで,toは再帰述語の初期値を与える外延データベースのタプル数,nは線形再帰式中の各外延データベースのグラフ表現における節点数,|ANS|は解のサイズである.拡張HaNa法が,m≧3かつ通常よく生じるデータの場合,マジック集合法およびHaNa法より優れていることを示す.