ユーザの要求に基づくファイル配置問題の計算複雑さ

菊野　亨  吉田　典可  杉原　一夫  角田　良明 

誌名
電子情報通信学会論文誌 D  Vol.J65-D  No.4  pp.458-463
発行日: 1982/04/20
Online ISSN: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(449.4KB)

あらまし: 
分散形データベースシステムにおけるファイル配置問題は，ネットワーク上の各サイトからのファイルに対する問合せ及び更新の頻度がパラメータとして与えられ，必要となる通信コスト，蓄積コストなどをシステム全体で最小にする問題で，これまでにも多くの報告がある．しかし，システム設計の初期段階では，通常，これらのパラメータの正確な値は得られない．本論文ではこの点に注目して，各ファイルに対する問合せと更新を一括してアクセスとして扱うものとし，各サイトからのファイルへのアクセス要求の有無だけが与えられるという立場にたって“ユーザの要求に基づくファイル配置問題（FIP）”を新たに定式化した．FIPでは，複数種類のファイルのコピーの配置を条件“各ファイルのコピーの総数，及び，各サイトのメモリ容量には上限がある”の下に，システム全体の通信コストを最小にするように決める．この問題の時間計算量に関し得られた主な結果は次の通りである．（1）FIPは一般にNP−困難である（従って，効率良い解法は存在しそうにない）．（2）FIPに制限をおくことにより定義できる幾つかの部分問題が多項式時間で解ける．