制約データベースに対する制約問合せ処理では,制約問題を解く方法の研究が中心的な課題である.研究開始時点では,制約データベース処理に関係するさまざまな枠組みの制約問題に着目し,調査を行ったが,研究を具体的にすすめるに当たり,(1)文字列制約,(2)ネットワーク制約,(3)空間的制約,(4)計算幾何学的制約,(5)数式表現制約の5つの枠組みに着目した.以下,本研究で得られた成果について述べる.
【文字列制約】文字列(あるいは単語列)が蓄積されているデータベースから頻出部分文字列を抽出するという文字列制約問題を解くために,生命情報科学分野におけるアミノ酸配列や遺伝子配列などの分子配列データベースに着目し,可変長ワイルドカード領域や曖昧文字表現などを含む正規表現の頻出パターンを抽出する方法を明らかにした.また,この可変長頻出バターンを抽出する処理を高速化するために,並列分散処理の方法を明らかにした.【ネットワーク制約】ネットワーク状に接続されている物事の関係が蓄積されているデータベースを理解するというネットワーク制約問題を解くために,ブログユーザ空間に着目し,クラスタリング技術によりブログユーザのコミュニティを抽出する方法を明らかにした.【空間的制約】空間情報を蓄積するデータベースの空間的制約問題を解くために,携帯電話によるwebアクセス履歴などに着目し,2次元空間に広がる空間オブジェクトの点座標データを蓄積するデータベースから頻出な近接属性パターンを高速に抽出する方法を明らかにした.【計算幾何学的制約】二種類の異なる接続関係をもつ木構造データどうしをつなぎ合わせた調停グラフの交差を減少させるという制約を高速に解く方法を明らかにした.【数式表現制約】数式表現制約問題を解くために,何種類かの仕事を何台かの機械で処理する工場における機械スケジューリング問題に着目した.ここでは,PCクラスタ環境で高速に計算する方法を明らかにした.