(57)【要約】【課題】データベース上のデータを複製して用いるデータ処理装置がデータベースの更新を効率良く検出可能とする。【解決手段】複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置から、一のクラスタに属するデータ要素と、当該一のクラスタのクラスタ更新情報とを取得してキャッシュするキャッシュ部と、２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報をデータ管理装置から取得するクラスタ群更新情報取得部と、２以上のクラスタ更新情報に基づいて、当該クラスタ群についてのクラスタ群更新情報を算出するクラスタ群更新情報算出部と、算出したクラスタ群更新情報が、データ管理装置から取得したクラスタ群更新情報と一致する場合に、当該クラスタ群に属するキャッシュされたデータ要素が最新であると判断する更新判断部とを備えるデータ処理装置を提供する。【選択図】図３
2006185220.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置からデータ要素を取得してデータ処理を行うデータ処理装置であって、
一の前記クラスタに属するデータ要素と、当該一のクラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されるクラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき前記データ管理装置により算出される、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を前記データ管理装置から取得するクラスタ群更新情報取得部と、
キャッシュした前記２以上のクラスタ更新情報に基づいて、前記クラスタ群についての前記クラスタ群更新情報を算出するクラスタ群更新情報算出部と、
クラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ管理装置から取得した前記クラスタ群更新情報と一致する場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部と
を備えるデータ処理装置。
【請求項２】
第１の数の前記クラスタからなる第１の前記クラスタ群について前記クラスタ群更新情報算出部が算出した第１の前記クラスタ群更新情報が、前記第１のクラスタ群について前記データ管理装置から取得した前記第１のクラスタ群更新情報と一致しない場合において、
前記クラスタ群更新情報取得部は、前記第１のクラスタ群に属し、前記第１の数より小さい第２の数の前記クラスタからなる第２の前記クラスタ群について、当該第２のクラスタ群に属する前記第２の数の前記クラスタの前記クラスタ更新情報に基づく第２の前記クラスタ群更新情報を前記データ管理装置から取得し、
前記クラスタ群更新情報算出部は、キャッシュされた前記第２の数の前記クラスタ更新情報に基づいて、前記第２のクラスタ群についての前記第２のクラスタ群更新情報を算出し、
前記更新判断部は、前記クラスタ群更新情報算出部により算出された前記第２のクラスタ群更新情報が、前記データ管理装置から取得した前記第２のクラスタ群更新情報と一致する場合に、前記第２のクラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する
請求項１記載のデータ処理装置。
【請求項３】
前記クラスタ群更新情報算出部により算出された前記第２のクラスタ群更新情報が、前記データ管理装置から取得した前記第２のクラスタ群更新情報と一致しない場合において、
前記クラスタ群更新情報取得部は、前記第２のクラスタ群に属し、前記第２の数より小さい第３の数の前記クラスタからなる第３の前記クラスタ群について、当該第３のクラスタ群に属する前記第３の数の前記クラスタの前記クラスタ更新情報に基づく第３の前記クラスタ群更新情報を前記データ管理装置から取得し、
前記クラスタ群更新情報算出部は、キャッシュされた前記第３の数の前記クラスタ更新情報に基づいて、前記第３のクラスタ群についての前記第３のクラスタ群更新情報を算出し、
前記更新判断部は、前記クラスタ群更新情報算出部により算出された前記第３のクラスタ群更新情報が、前記データ管理装置から取得した前記第３のクラスタ群更新情報と一致する場合に、前記第３のクラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する
請求項２記載のデータ処理装置。
【請求項４】
前記クラスタ群更新情報取得部は、前記第１のクラスタ群に属し、かつ、前記第２のクラスタ群に属しない第４の数の前記クラスタからなる第４の前記クラスタ群について、当該第４のクラスタ群に属する前記第４の数の前記クラスタの前記クラスタ更新情報に基づく第４の前記クラスタ群更新情報を前記データ管理装置から取得し、
前記クラスタ群更新情報算出部は、キャッシュされた前記第４の数の前記クラスタ更新情報に基づいて、前記第４のクラスタ群についての前記第４のクラスタ群更新情報を算出し、
前記更新判断部は、前記クラスタ群更新情報算出部により算出された前記第４のクラスタ群更新情報が、前記データ管理装置から取得した前記第４のクラスタ群更新情報と一致する場合に、前記第４のクラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する
請求項２記載のデータ処理装置。
【請求項５】
前記キャッシュ部は、前記第１のクラスタ群に属し、前記第２のクラスタ群及び前記第４のクラスタ群に属しない全ての前記クラスタからなり、いずれの前記クラスタに属する前記データ要素もキャッシングしていない第５のクラスタ群について、当該第５のクラスタ群に属する全ての前記クラスタの前記クラスタ更新情報に基づく第５の前記クラスタ群更新情報をキャッシュし、
前記クラスタ群更新情報算出部は、前記第２のクラスタ群更新情報と、前記第５のクラスタ群更新情報と、前記第４のクラスタ群更新情報とに基づいて、前記第１のクラスタ群更新情報を算出する
請求項４記載のデータ処理装置。
【請求項６】
前記キャッシュ部は、前記第２のクラスタ群について第１及び第２の前記クラスタのみのデータ要素をキャッシュする場合に、前記第１のクラスタの第１の前記クラスタ更新情報と、前記第２のクラスタの第２の前記クラスタ更新情報と、前記第２のクラスタ群における他の全ての前記クラスタの前記クラスタ更新情報に基づく第６の前記クラスタ群更新情報とを、前記クラスタ群更新情報としてキャッシュし、
前記クラスタ群更新情報算出部は、前記第１のクラスタ更新情報、前記第２のクラスタ更新情報、及び前記第６のクラスタ群更新情報に基づいて、前記第２のクラスタ群更新情報を算出する
請求項５記載のデータ処理装置。
【請求項７】
前記クラスタ群更新情報算出部により算出された前記第１のクラスタ群更新情報が、前記データ管理装置から取得した前記第１のクラスタ群更新情報と一致しない場合において、前記クラスタ群更新情報算出部により算出された前記第２のクラスタ群更新情報及び前記第４のクラスタ群更新情報が、前記データ管理装置から取得した前記第２のクラスタ群更新情報及び前記第４のクラスタ群更新情報とそれぞれ一致した場合に、前記データ管理装置から取得した前記第１のクラスタ群更新情報、前記第２のクラスタ群更新情報、及び、前記第４のクラスタ群更新情報に基づいて、前記第５のクラスタ群更新情報を変更するクラスタ群更新情報変更部
を更に備える請求項６記載のデータ処理装置。
【請求項８】
前記データ管理装置に記憶される前記クラスタ更新情報は、当該クラスタに属する前記データ要素が更新されたことを条件として、元のデータ値をハッシュ関数により変換して得られるデータ値に変更されるものであり、
前記クラスタ群更新情報算出部は、前記第２のクラスタ群、前記第４のクラスタ群、及び前記第５のクラスタ群のそれぞれについて、当該クラスタ群に属する全ての前記クラスタの前記クラスタ更新情報を対応するビット毎に排他的論理和をとったデータ値である前記第２のクラスタ群更新情報、前記第４のクラスタ群更新情報、及び前記第５のクラスタ群更新情報を対応するビット毎に排他的論理和をとることにより、前記第１のクラスタ群更新情報を算出する
請求項５記載のデータ処理装置。
【請求項９】
前記データ管理装置に記憶される前記クラスタ更新情報は、当該クラスタに属する前記データ要素が更新されたことを条件として、元のデータ値をインクリメント又はデクリメントして得られるデータ値に変更されるものであり、
前記クラスタ群更新情報算出部は、前記第２のクラスタ群、前記第４のクラスタ群、及び前記第５のクラスタ群のそれぞれについて、当該クラスタ群に属する全ての前記クラスタの前記クラスタ更新情報を合計したデータ値である前記第２のクラスタ群更新情報、前記第４のクラスタ群更新情報、及び前記第５のクラスタ群更新情報を合計することにより前記第１のクラスタ群更新情報を算出する
請求項５記載のデータ処理装置。
【請求項１０】
それぞれの前記クラスタにはクラスタ番号が割り当てられており、
前記クラスタ群は、クラスタ番号が連続する少なくとも１つの前記クラスタからなり、
前記第１のクラスタ群、前記第２のクラスタ群、及び前記第４のクラスタ群のそれぞれは、当該クラスタ群内において最小のクラスタ番号が割り当てられた前記クラスタ及び最大のクラスタ番号が割り当てられた前記クラスタに属する少なくとも１つの前記データ要素がキャッシュされている
請求項５記載のデータ処理装置。
【請求項１１】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置からデータ要素を取得してデータ処理を行うデータ処理装置であって、
一の前記クラスタに属するデータ要素と、当該一のクラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されるクラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて取得した２以上の前記クラスタ更新情報に基づいて、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を算出するクラスタ群更新情報算出部と、
前記クラスタ群更新情報算出部により算出された前記クラスタ群更新情報を前記データ管理装置へ送信し、前記２以上のクラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき定められる前記クラスタ群更新情報と一致するか否かを問い合わせる更新問合せ部と、
前記クラスタ群更新情報算出部が算出した前記クラスタ群更新情報が、前記データ管理装置に記憶された前記クラスタ更新情報に基づく前記クラスタ群更新情報と一致する旨の応答を受けた場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部と
を備えるデータ処理装置。
【請求項１２】
複数のデータ要素を、複数のクラスタに分類して記憶するデータ記憶部と、
それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、
前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、
前記データ要素を取得してデータ処理を行うデータ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、
２以上の前記クラスタからなるクラスタ群についての前記クラスタ更新情報の参照要求を前記データ処理装置から受けた場合に、当該クラスタ群に属する前記２以上のクラスタの前記クラスタ更新情報に基づくクラスタ群更新情報を算出するクラスタ群更新情報算出部と、
前記クラスタ群更新情報を前記データ処理装置へ送信する更新情報送信部と、
を備えるデータ管理装置。
【請求項１３】
複数のデータ要素を、複数のクラスタに分類して記憶するデータ記憶部と、
それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、
前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、
前記データ要素を取得してデータ処理を行うデータ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、
２以上の前記クラスタからなるクラスタ群について、当該クラスタ群に属する前記クラスタ更新情報に基づき前記データ処理装置が算出したクラスタ群更新情報を受信するクラスタ群更新情報受信部と、
前記２以上のクラスタについて前記クラスタ更新情報記憶部に記憶された前記クラスタ更新情報に基づいて、前記クラスタ群更新情報を算出するクラスタ群更新情報算出部と、
前記クラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ処理装置から受信した前記クラスタ群更新情報と一致する場合に、前記データ処理装置にキャッシュされた、前記クラスタ群に属する前記クラスタの前記データ要素は最新であることを前記データ処理装置へ通知する更新通知部と
を備えるデータ管理装置。
【請求項１４】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置と、
前記データ管理装置からデータを取得してデータ処理を行うデータ処理装置と
を備え、
前記データ管理装置は、
前記複数のデータ要素を、前記複数のクラスタに分類して記憶するデータ記憶部と、
それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、
前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、
前記データ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、
２以上の前記クラスタからなるクラスタ群についての前記クラスタ更新情報の参照要求を前記データ処理装置から受けた場合に、当該クラスタ群に属する前記２以上のクラスタの前記クラスタ更新情報に基づくクラスタ群更新情報を算出する第１のクラスタ群更新情報算出部と、
前記クラスタ群更新情報を前記データ処理装置へ送信する更新情報送信部と
を有し、
前記データ処理装置は、
一の前記クラスタに属するデータ要素と、当該一のクラスタの前記クラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタからなるクラスタ群についての前記参照要求を前記データ管理装置へ送信し、当該クラスタ群についてのクラスタ群更新情報を前記データ管理装置から取得するクラスタ群更新情報取得部と、
キャッシュした前記２以上のクラスタ更新情報に基づいて、前記クラスタ群についての前記クラスタ群更新情報を算出する第２のクラスタ群更新情報算出部と、
前記第２のクラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ管理装置から取得した前記クラスタ群更新情報と一致する場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部と
を有する情報システム。
【請求項１５】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置と、
前記データ管理装置からデータを取得してデータ処理を行うデータ処理装置と
を備え、
前記データ管理装置は、
複数のデータ要素を、複数のクラスタに分類して記憶するデータ記憶部と、
それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、
前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、
前記データ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、
２以上の前記クラスタからなるクラスタ群について、当該クラスタ群に属する前記クラスタ更新情報に基づき前記データ処理装置が算出したクラスタ群更新情報を受信するクラスタ群更新情報受信部と、
前記２以上のクラスタについて前記クラスタ更新情報記憶部に記憶された前記クラスタ更新情報に基づいて、前記クラスタ群更新情報を算出する第１のクラスタ群更新情報算出部と、
前記第１のクラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ処理装置から受信した前記クラスタ群更新情報と一致する場合に、前記データ処理装置にキャッシュされた、前記クラスタ群に属する前記クラスタの前記データ要素は最新であることを前記データ処理装置へ通知する更新通知部と
を有し、
前記データ処理装置は、
一の前記クラスタに属するデータ要素と、当該一のクラスタの前記クラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて取得した２以上の前記クラスタ更新情報に基づいて、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を算出する第２のクラスタ群更新情報算出部と、
前記第２のクラスタ群更新情報算出部により算出された前記クラスタ群更新情報を前記データ管理装置へ送信し、前記２以上のクラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき定められる前記クラスタ群更新情報と一致するか否かを問い合わせる更新問合せ部と、
前記第２のクラスタ群更新情報算出部が算出した前記クラスタ群更新情報が、前記データ管理装置に記憶された前記クラスタ更新情報に基づく前記クラスタ群更新情報と一致する旨の応答を受けた場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部と
を有する情報システム。
【請求項１６】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置からデータ要素を取得してデータ処理を行うデータ処理装置によるデータ処理方法であって、
一の前記クラスタに属するデータ要素と、当該一のクラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されるクラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ段階と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき前記データ管理装置により算出される、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を前記データ管理装置から取得するクラスタ群更新情報取得段階と、
キャッシュした前記２以上のクラスタ更新情報に基づいて、前記クラスタ群についての前記クラスタ群更新情報を算出するクラスタ群更新情報算出段階と、
前記クラスタ群更新情報算出段階により算出された前記クラスタ群更新情報が、前記データ管理装置から取得した前記クラスタ群更新情報と一致する場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断段階と
を備えるデータ処理方法。
【請求項１７】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置からデータ要素を取得してデータ処理を行うデータ処理装置によるデータ処理方法であって、
一の前記クラスタに属するデータ要素と、当該一のクラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されるクラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ段階と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて取得した２以上の前記クラスタ更新情報に基づいて、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を算出するクラスタ群更新情報算出段階と、
前記クラスタ群更新情報算出段階により算出された前記クラスタ群更新情報を前記データ管理装置へ送信し、前記２以上のクラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき定められる前記クラスタ群更新情報と一致するか否かを問い合わせる更新問合せ段階と、
前記クラスタ群更新情報算出段階において算出した前記クラスタ群更新情報が、前記データ管理装置に記憶された前記クラスタ更新情報に基づく前記クラスタ群更新情報と一致する旨の応答を受けた場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断段階と
を備えるデータ処理方法。
【請求項１８】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置からデータ要素を取得してデータ処理を行うデータ処理装置用のデータ処理プログラムであって、
前記データ処理装置を、
一の前記クラスタに属するデータ要素と、当該一のクラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されるクラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき前記データ管理装置により算出される、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を前記データ管理装置から取得するクラスタ群更新情報取得部と、
キャッシュした前記２以上のクラスタ更新情報に基づいて、前記クラスタ群についての前記クラスタ群更新情報を算出するクラスタ群更新情報算出部と、
クラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ管理装置から取得した前記クラスタ群更新情報と一致する場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部と
して機能させるデータ処理プログラム。
【請求項１９】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置からデータ要素を取得してデータ処理を行うデータ処理装置用のデータ処理プログラムであって、
前記データ処理装置を、
一の前記クラスタに属するデータ要素と、当該一のクラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されるクラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、
キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて取得した２以上の前記クラスタ更新情報に基づいて、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を算出するクラスタ群更新情報算出部と、
前記クラスタ群更新情報算出部により算出された前記クラスタ群更新情報を前記データ管理装置へ送信し、前記２以上のクラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき定められる前記クラスタ群更新情報と一致するか否かを問い合わせる更新問合せ部と、
前記クラスタ群更新情報算出部が算出した前記クラスタ群更新情報が、前記データ管理装置に記憶された前記クラスタ更新情報に基づく前記クラスタ群更新情報と一致する旨の応答を受けた場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部と
して機能させるデータ処理プログラム。
【請求項２０】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置用のデータ管理プログラムであって、
前記データ管理装置を、
複数のデータ要素を、複数のクラスタに分類して記憶するデータ記憶部と、
それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、
前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、
前記データ要素を取得してデータ処理を行うデータ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、
２以上の前記クラスタからなるクラスタ群についての前記クラスタ更新情報の参照要求を前記データ処理装置から受けた場合に、当該クラスタ群に属する前記２以上のクラスタの前記クラスタ更新情報に基づくクラスタ群更新情報を算出するクラスタ群更新情報算出部と、
前記クラスタ群更新情報を前記データ処理装置へ送信する更新情報送信部と
して機能させるデータ管理プログラム。
【請求項２１】
複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置用のデータ管理プログラムであって、
前記データ管理装置を、
複数のデータ要素を、複数のクラスタに分類して記憶するデータ記憶部と、
それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、
前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、
前記データ要素を取得してデータ処理を行うデータ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、
２以上の前記クラスタからなるクラスタ群について、当該クラスタ群に属する前記クラスタ更新情報に基づき前記データ処理装置が算出したクラスタ群更新情報を受信するクラスタ群更新情報受信部と、
前記２以上のクラスタについて前記クラスタ更新情報記憶部に記憶された前記クラスタ更新情報に基づいて、前記クラスタ群更新情報を算出するクラスタ群更新情報算出部と、
前記クラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ処理装置から受信した前記クラスタ群更新情報と一致する場合に、前記データ処理装置にキャッシュされた、前記クラスタ群に属する前記クラスタの前記データ要素は最新であることを前記データ処理装置へ通知する更新通知部と
として機能させるデータ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ管理装置、データ処理方法、データ管理方法、データ処理プログラム、データ管理プログラム、及び情報システムに関する。特に本発明は、データ管理装置上のデータベースの内容をデータ処理装置が効率良く複製するためのデータ処理装置、データ管理装置、データ処理方法、データ管理方法、データ処理プログラム、データ管理プログラム、及び情報システムに関する。
【背景技術】
【０００２】
データベースに記憶されたデータを用いてデータ処理を行う情報システムにおいては、複数のデータ処理装置により並列処理を行って、データ処理を高速化している。この形態において、各データ処理装置は、データベース上のデータを複製して用いる。これにより、データを高速にアクセスすることができ、データベースへのアクセス集中を防ぐことができる。
【０００３】
非特許文献１は、このような情報システムのアプリケーションの一例として、製品等に無線タグを付加して製品毎の属性データを管理するＥＰＣ−ＩＳ（Electric Product Code - Information Services）を提案している。このような情報システムにおいては、製品毎に個別に属性データを管理することから、膨大なデータを管理する必要があり、大規模な分散システムが要求される。ＥＰＣ−ＩＳにおいては、製品毎の属性データは、ＰＭＬ（Physical Markup Language）と呼ばれる表現形式で管理される（非特許文献２参照。）。
【０００４】
ＥＰＣ−ＩＳによる属性データ管理においては、属性データの参照が多く、更新は稀であるという特性を有する。したがって、各データ処理装置は、データベース上の属性データを複製することにより、更新が生じない限り効率良く処理を行うことができる。
【０００５】
非特許文献３から６は、データベースへの更新操作を順序化して記憶し、複製されたデータに対してこれらの更新操作を適用する更新処理方法を開示する。また、非特許文献７から９は、データの更新処理方法の他の例として、データベースへの更新結果のみを伝播する更新処理方法を開示する。より具体的には、非特許文献７及び８は、インターネット上で文書が動的に生成される場合におけるデータの分散配置・生成方式を開示する。また、非特許文献９は、分散したデータの一部を複製した場合に、データの更新を反映するか否かを選択し、所定の正確性を保つ方法を開示する。
【０００６】
非特許文献１０から１１、及び、特許文献１から２は、ハッシュ関数を用いてデータの更新管理を行う方法を開示する。
【特許文献１】特開平１１−３０６０６９号公報
【特許文献２】特表２００３−５２４２４３号公報
【非特許文献１】EPCglobal U.S., "The EPCglobal Network(tm)", [online], EPCglobal U.S., ［平成１６年１２月１６日検索］, インターネット＜ＵＲＬ：http://www.epcglobalus.org/Network/Network.html＞
【非特許文献２】Christian Floerkemeier他, "PML Core Specification 1.0", [online], ２００３年９月１５日, EPCglobal Inc., ［平成１６年１２月１６日検索］, ＜ＵＲＬ：http://www.epcglobalinc.org/standards_technology/Secure/v1.0/PML_Core_Specification_v1.0.pdf＞
【非特許文献３】Yair Amir and Ciprian Tutu, "From total order to database replication", ２００２年, In Proc. of ICDCS 2002, p. 494-
【非特許文献４】Haifeng Yu and Amin Vahdat, "Minimal replication cost for availability", ２００２年, In Proc. of PODC 2002, p. 98-107
【非特許文献５】Chi Zhang and Zheng Zhang, "Trading replication consistency for performance and availability: an adaptive approach", ２００３年, In Proc. of ICDCS 2003, p. 687-695
【非特許文献６】Khuzaima Daudjee and Kenneth Salem, "Lazy database replication with ordering guarantees", ２００４年, In Proc. of ICDE 2004, p. 424-435
【非特許文献７】Xueyan Tang and Samuel T. Chanson, "Minimal cost replication of dynamic web contents under flat update delivery",２００４年, In IEEE Trans. Parallel Distrib. Syst. 15(5): 431-439
【非特許文献８】Serge Abiteboul, Angela Bonifati, Gregory Cobena, Ioana Manolescu, and Tova Milo, "Dynamic xml documents with distribution and replication", ２００３年, In Proc. of SIGMOD Conference 2003, p. 527-538
【非特許文献９】Ugur Cetintemel, Peter J. Keleher, and Yanif Ahmad, "Exploiting precision vs. efficiency tradeoffs in symmetric replication environments", ２００２年, In Proc. of PODC 2002, p.128
【非特許文献１０】Yasushi Saito and Marc Shapiro, "Optimistic replication", ２００３年, In HP Technical report MSR-TR-2003-60
【非特許文献１１】Brent ByungHoon Kang, Robert Wilensky, and John Kubiatowicz, "Hash history approach for reconciling mutual inconsistency in optimistic replication", ２００３年、In Proc. of ICDCS'03
【非特許文献１２】EPCglobal Inc., "EPC Tag Data Standards Version 1.1 Rev.1.24", [online], ２００４年４月１日, EPCglobal Inc., ［平成１６年１２月１６日検索］, ＜ＵＲＬ： http:// www.epcglobalinc.org/ standards_technology/EPCTagDataSpecification11rev124.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００７】
非特許文献３から９に示した更新処理方法においては、更新操作又は更新結果を伝播するため、伝播する情報のデータ量が大きいという問題がある。また、非特許文献１０から１１及び特許文献１から２においては、データベース上のデータ要素を分割したクラスタ単位での更新検出を行っており、データベースとデータ処理装置の間で更新のチェックに要する通信量が大きいという問題がある。
【０００８】
そこで本発明は、上記の課題を解決することのできるデータ処理装置、データ管理装置、データ処理方法、データ管理方法、データ処理プログラム、データ管理プログラム、及び情報システムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００９】
本発明の第１の形態によると、複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置と、前記データ管理装置からデータを取得してデータ処理を行うデータ処理装置とを備え、前記データ管理装置は、前記複数のデータ要素を、前記複数のクラスタに分類して記憶するデータ記憶部と、それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、前記データ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、２以上の前記クラスタからなるクラスタ群についての前記クラスタ更新情報の参照要求を前記データ処理装置から受けた場合に、当該クラスタ群に属する前記２以上のクラスタの前記クラスタ更新情報に基づくクラスタ群更新情報を算出する第１のクラスタ群更新情報算出部と、前記クラスタ群更新情報を前記データ処理装置へ送信する更新情報送信部とを有し、前記データ処理装置は、一の前記クラスタに属するデータ要素と、当該一のクラスタの前記クラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、キャッシュした２以上の前記データ要素が属する２以上の前記クラスタからなるクラスタ群についての前記参照要求を前記データ管理装置へ送信し、当該クラスタ群についてのクラスタ群更新情報を前記データ管理装置から取得するクラスタ群更新情報取得部と、キャッシュした前記２以上のクラスタ更新情報に基づいて、前記クラスタ群についての前記クラスタ群更新情報を算出する第２のクラスタ群更新情報算出部と、前記第２のクラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ管理装置から取得した前記クラスタ群更新情報と一致する場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部とを有する情報システム、並びに当該情報システムに関するデータ処理装置、データ管理装置、データ処理方法、データ管理方法、データ処理プログラム、及びデータ管理プログラムを提供する。
【００１０】
本発明の第２の形態によると、複数のデータ要素を複数のクラスタに分類して記憶するデータ管理装置と、前記データ管理装置からデータを取得してデータ処理を行うデータ処理装置とを備え、前記データ管理装置は、複数のデータ要素を、複数のクラスタに分類して記憶するデータ記憶部と、それぞれの前記クラスタに対応付けて、当該クラスタに属する前記データ要素の更新状態を示すクラスタ更新情報を記憶するクラスタ更新情報記憶部と、前記データ要素が更新されたことを条件として、当該データ要素が属する前記クラスタの前記クラスタ更新情報を異なるデータ値に変更するクラスタ更新情報変更部と、前記データ処理装置からの要求に応じて、前記データ要素と、前記データ要素が属する前記クラスタの前記クラスタ更新情報とを前記データ処理装置へ送信するデータ送信部と、２以上の前記クラスタからなるクラスタ群について、当該クラスタ群に属する前記クラスタ更新情報に基づき前記データ処理装置が算出したクラスタ群更新情報を受信するクラスタ群更新情報受信部と、前記２以上のクラスタについて前記クラスタ更新情報記憶部に記憶された前記クラスタ更新情報に基づいて、前記クラスタ群更新情報を算出する第１のクラスタ群更新情報算出部と、前記第１のクラスタ群更新情報算出部により算出された前記クラスタ群更新情報が、前記データ処理装置から受信した前記クラスタ群更新情報と一致する場合に、前記データ処理装置にキャッシュされた、前記クラスタ群に属する前記クラスタの前記データ要素は最新であることを前記データ処理装置へ通知する更新通知部とを有し、前記データ処理装置は、一の前記クラスタに属するデータ要素と、当該一のクラスタの前記クラスタ更新情報とを、前記データ管理装置から取得してキャッシュするキャッシュ部と、キャッシュした２以上の前記データ要素が属する２以上の前記クラスタについて取得した２以上の前記クラスタ更新情報に基づいて、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を算出する第２のクラスタ群更新情報算出部と、前記第２のクラスタ群更新情報算出部により算出された前記クラスタ群更新情報を前記データ管理装置へ送信し、前記２以上のクラスタについて前記データ管理装置に記憶された２以上の前記クラスタ更新情報に基づき定められる前記クラスタ群更新情報と一致するか否かを問い合わせる更新問合せ部と、前記第２のクラスタ群更新情報算出部が算出した前記クラスタ群更新情報が、前記データ管理装置に記憶された前記クラスタ更新情報に基づく前記クラスタ群更新情報と一致する旨の応答を受けた場合に、前記クラスタ群内の前記クラスタに属するキャッシュされた前記データ要素が最新であると判断する更新判断部とを有する情報システム、並びに当該情報システムに関するデータ処理装置、データ管理装置、データ処理方法、データ管理方法、データ処理プログラム、及びデータ管理プログラムを提供する。
【００１１】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１２】
本発明によれば、データベース上のデータを複製して用いるデータ処理装置がデータベースの更新を効率良く検出することができる。
【発明を実施するための最良の形態】
【００１３】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１４】
図１は、本実施形態に係る情報システム１０の構成を示す。情報システム１０は、データ管理装置１００と、１又は複数のデータ処理装置１２０とを備える。データ管理装置１００は、複数のデータ要素を複数のクラスタに分類して、データベース１１０に記憶する。すなわち例えば、データベース１１０は、データベースの各行及び／又は各属性をデータ要素とし、複数の行及び／又は複数の属性をクラスタとして記憶してよい。また、データベース１１０は、データベース内の複数のデータ要素を、任意の形態に分割したクラスタに割り当てて記憶してもよい。
【００１５】
また、データベース１１０は、各クラスタに対応付けて、当該クラスタに属するデータ要素の更新状態を示すクラスタ更新情報を記憶する。このクラスタ更新情報は、当該クラスタに属するいずれかのデータ要素が更新されるとデータ値が変更されることにより、当該クラスタのデータ要素の更新状態を示す。
【００１６】
そして、データベース１１０は、２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を要求された場合に、これらのクラスタのクラスタ更新情報に基づくクラスタ群更新情報を生成し、要求元のデータ処理装置１２０へ返信する。
【００１７】
データ処理装置１２０は、データ管理装置１００からデータ要素を取得して、当該データ要素のクラスタ更新情報と共にキャッシュ部１３０にキャッシュし、キャッシュしたデータを用いてデータ処理を行う。本実施形態に係るデータ処理装置１２０は、キャッシュしたデータ要素が最新であるか否かを検出する場合に、まず、キャッシュしたデータ要素を含む２以上のクラスタについてのクラスタ群更新情報をデータベース１１０から取得する。そして、取得したクラスタ群更新情報が、キャッシュしたクラスタ更新情報に基づくクラスタ群更新情報と一致する場合に、これらのクラスタに属するキャッシュしたデータ要素が最新であると判断する。
【００１８】
以上に示した情報システム１０によれば、データ処理装置１２０は、１つのクラスタ群更新情報を取得することにより複数のクラスタについての更新有無を検出することができる。データ処理装置１２０は、必要に応じて複数のクラスタ群について順次更新検出を行うことで、少ない通信量でデータベース１１０内のデータ要素の更新を効率良く検出することができる。
【００１９】
図２は、本実施形態に係るデータ管理装置１００の構成を示す。データ管理装置１００は、データベース１１０と、データ送信部２２０と、データ受信部２３０と、クラスタ更新情報変更部２４０と、参照要求受信部２５０と、クラスタ群更新情報算出部２６０と、更新情報送信部２７０とを備える。
【００２０】
データベース１１０は、データ記憶部２００と、クラスタ更新情報記憶部２１０とを有する。データ記憶部２００は、複数のデータ要素を、複数のクラスタに分類して記憶する。本実施形態に係るデータ記憶部２００は、一例として、各製品に付加された無線タグに記録された当該製品の識別子（ＩＤ）に対応して、当該製品の製品名及び価格等の属性データを記憶する。クラスタ更新情報記憶部２１０は、それぞれのクラスタに対応付けて、当該クラスタに属するデータ要素の更新状態を示すクラスタ更新情報を記憶する。データ送信部２２０は、データ要素の読出要求をデータ処理装置１２０から受けた場合に、当該データ要素と、当該データ要素が属するクラスタのクラスタ更新情報とを、要求元のデータ処理装置１２０へ送信する。データ受信部２３０は、データ要素の書込要求をデータ処理装置１２０から受信し、受信したデータ要素をデータ記憶部２００に書き込むことによりデータベース１１０を更新する。
【００２１】
クラスタ更新情報変更部２４０は、データ処理装置１２０からの書込要求に応じてデータ要素が更新されたことを条件として、当該データ要素が属するクラスタのクラスタ更新情報を異なるデータ値に変更する。本実施形態に係るクラスタ更新情報変更部２４０は、一例として、あるクラスタに属するデータ要素が更新されたことを条件として、当該クラスタのクラスタ更新情報を、元のデータ値をハッシュ関数により変換して得られるデータ値に変更する。
【００２２】
参照要求受信部２５０は、２以上のクラスタからなるクラスタ群についてのクラスタ更新情報の参照要求をデータ処理装置１２０から受信する。クラスタ群更新情報算出部２６０は、２以上のクラスタからなるクラスタ群についてのクラスタ更新情報の参照要求をデータ処理装置１２０から受けた場合に、当該クラスタ群に属する２以上のクラスタのクラスタ更新情報をクラスタ更新情報記憶部２１０から読み出して、これらのクラスタ更新情報にに基づくクラスタ群更新情報を算出する。
【００２３】
本実施形態に係るクラスタ群更新情報算出部２６０は、一例として、当該クラスタ群に属する全てのクラスタのクラスタ更新情報を、対応するビット毎に排他的論理和をとる。そして、クラスタ群更新情報算出部２６０は、排他的論理和により得られたデータ値を、当該クラスタ群についてのクラスタ群更新情報とする。更新情報送信部２７０は、データ処理装置１２０からの参照要求に応答して、クラスタ群更新情報算出部２６０により算出されたクラスタ群更新情報を当該データ処理装置１２０へ送信する。
【００２４】
以上に示したデータ管理装置１００によれば、２以上のクラスタからなるクラスタ群について、クラスタ更新情報の参照要求を受けた場合に、これらのクラスタのクラスタ更新情報に基づくクラスタ群更新情報をクラスタ群更新情報算出部２６０により算出する。これにより、全てのクラスタ更新情報をデータ処理装置１２０へ送信する場合と比較して、データ処理装置１２０へ送信する更新情報のデータ量を低減することができる。
【００２５】
図３は、本実施形態に係るデータ処理装置１２０の構成を示す。データ処理装置１２０は、データ処理部３００と、キャッシュ部１３０と、クラスタ群更新情報取得部３１０と、クラスタ群更新情報算出部３２０と、更新判断部３３０と、クラスタ群更新情報変更部３４０と、データ受信部３５０と、データ送信部３６０とを備える。
【００２６】
データ処理部３００は、データベース１１０に記憶されたデータ要素を必要に応じてアクセスし、データ処理を行う。例えばデータ処理部３００は、Ｗｅｂアプリケーションサーバであり、端末からの要求に応じ、データベース１１０を参照しつつ無線タグの属性データ管理等のＷｅｂアプリケーションの処理を行ってもよい。
【００２７】
キャッシュ部１３０は、データ処理部３００から一のクラスタに属するデータ要素のアクセスを受けたことに応じて、当該データ要素と、当該一のクラスタのクラスタ更新情報とを、データ管理装置１００からデータ受信部３５０を介して取得する。そして、キャッシュ部１３０は、当該データ要素と、当該クラスタ更新情報とをキャッシュする。これによりデータ処理部３００は、一旦キャッシュされたデータ要素については、データベース１１０に代えてキャッシュ部１３０から当該データ要素を取得することができる。
【００２８】
クラスタ群更新情報取得部３１０は、キャッシュしたデータ要素がデータ管理装置１００上で更新されたか否かを検出する場合に、１又は２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報をデータ管理装置１００から取得する。より具体的には、異なるクラスタに属する２以上のデータ要素をキャッシュしている場合、クラスタ群更新情報取得部３１０は、キャッシュした２以上のデータ要素が属する２以上のクラスタからなるクラスタ群についてのクラスタ更新情報の参照要求をデータ管理装置１００へ送信する。この参照要求を受けると、データ管理装置１００は、当該クラスタ群に属する２以上のクラスタに対応してデータベース１１０に記憶された２以上のクラスタ更新情報に基づいてクラスタ群更新情報を算出し、データ処理装置１２０へ返信する。
【００２９】
クラスタ群更新情報算出部３２０は、キャッシュ部１３０にキャッシュした１又は２以上のクラスタ更新情報に基づいて、参照要求の対象となるクラスタ群についてのクラスタ群更新情報を算出する。更新判断部３３０は、クラスタ群更新情報算出部３２０により算出されたクラスタ群更新情報が、データ管理装置１００から取得したクラスタ群更新情報と一致する場合に、クラスタ群内のクラスタに属するキャッシュされたデータ要素が最新であると判断する。これを受けて、データ処理部３００は、最新の当該データ要素を用いてデータ処理を行うことができる。
【００３０】
一方、更新判断部３３０は、クラスタ群更新情報算出部３２０により算出されたクラスタ群更新情報が、データ管理装置１００から取得したクラスタ群更新情報と一致しない場合に、クラスタ群内のクラスタに属するキャッシュされたデータ要素が最新でないと判断する。この場合、データ処理装置１２０は、当該クラスタに属するキャッシュされた各データ要素の更新チェックを行い、更新されたデータ要素をデータ管理装置１００から再度取得する。この場合、更新判断部３３０は、更新されたデータ要素の読出要求をデータ管理装置１００に対して送信し、最新のデータ要素をデータ受信部３５０により受信させ、キャッシュ部１３０内の古い当該データ要素を最新のデータ値に更新させてもよい。これに代えて、更新判断部３３０は、キャッシュ部１３０に記憶された当該データ要素を無効化し、データ処理部３００に使用させないようにしてもよい。
【００３１】
クラスタ群更新情報変更部３４０は、クラスタ群更新情報取得部３１０によりデータ管理装置１００から取得された１又は複数のクラスタ群更新情報及び／又はクラスタ更新情報に基づいて、キャッシュ部１３０にキャッシュされたクラスタ群更新情報及び／又はクラスタ更新情報を最新の値に変更する。データ受信部３５０は、データ処理部３００が用いるデータ要素がキャッシュ部１３０にキャッシュされていない場合に、当該データ要素及び当該データ要素が属するクラスタのクラスタ更新情報をデータ管理装置１００から受信し、キャッシュ部１３０へ格納する。データ送信部３６０は、データ処理部３００によりキャッシュ部１３０内のデータ要素が更新された場合に、更新されたデータ要素をデータ管理装置１００へ送信する。これを受けてデータ管理装置１００は、データベース１１０内の当該データ要素を更新する。
【００３２】
以上に示したデータ処理装置１２０によれば、データ管理装置１００上のクラスタ更新情報に基づくクラスタ群更新情報と、キャッシュ部１３０内のクラスタ更新情報に基づくクラスタ群更新情報とを比較することにより、キャッシュしたデータ要素が最新であるか否かをデータ処理装置１２０自身が判断することができる。このため、データ管理装置１００は、データ処理装置１２０がいずれのデータ要素をキャッシュしているかを記憶する必要がない。したがって、多数のデータ処理装置１２０をデータ管理装置１００に接続した場合においても、データ管理装置１００におけるキャッシュ状態の管理コストを抑えることができる。
【００３３】
図４は、本実施形態に係るクラスタ群更新情報の一例を示す。以下、情報システム１０におけるクラスタ更新情報の管理方法、キャッシュ方法、更新チェック方法、及び、キャッシュしたクラスタ群更新情報の更新方法を示す。
【００３４】
（１）クラスタ更新情報の管理方法
データ記憶部２００は、複数のデータ要素{r1,…,rn}（=集合R）を、予め複数のクラスタC1, …, Ctにクラスタリングして記憶する。それぞれのクラスタCiにはクラスタ番号ciが割り当てられる。本実施形態において、クラスタの個数tは全データ要素の数nと比較し十分小さく（t＜＜n）、かつ、同一のデータ要素は一のクラスタにのみ属するものとする（i≠j ⇒ Ci∩Cj=Φ）。
【００３５】
クラスタ更新情報記憶部２１０は、クラスタ毎に、当該クラスタCiに属する少なくとも１つのデータ要素xαが更新されたことを示す更新チェックサムとして用いられるクラスタ更新情報hiを記憶する。本実施形態に係るクラスタ更新情報記憶部２１０は、予め定められたハッシュ関数H()を用いて、クラスタ更新情報hiの初期値をH(i || 0)に設定する。そして、クラスタCiの少なくとも１つのデータ要素が更新された場合、クラスタ更新情報変更部２４０は、クラスタ更新情報hiをハッシュ関数Hにより変換し、新たなクラスタ更新情報h'i = H(i || hi)とする。
【００３６】
（２）キャッシュ方法
あるデータ処理装置１２０が、k個のデータ要素{x1,…xk}（=集合X⊂R）をデータベース１１０から複製し、キャッシュする場合について、キャッシュ方法を示す。ただし、キャッシュしたデータ要素の数kは、全データ要素の数nと比較し十分小さい。この場合、データ管理装置１００内のデータ送信部２２０は、複製対象のデータ要素x及び当該データ要素xが属するクラスタの識別子ciのリストL1と、複製対象のデータ要素が属する全てのクラスタについて、当該クラスタCiの識別子ci及び当該クラスタCiのクラスタ更新情報hiのリストL2とをデータ処理装置１２０へ送信する。また、本実施形態において、データ送信部２２０は、当該クラスタCiの識別子ciに対応付けて、データ処理装置１２０が記憶すべきクラスタ群更新情報hi,jをクラスタ群更新情報算出部２６０により算出させ、リストL2に含めてデータ処理装置１２０へ送信する。このクラスタ群更新情報hi,jは、当該クラスタCiの次のクラスタCi+1から、キャッシュすべきデータ要素が属する、当該クラスタCiの次のクラスタCjの直前のクラスタCj-1までの各クラスタのクラスタ更新情報hi+1からhj-1に基づいて算出される。より具体的には、当該クラスタ群更新情報hi,jは、クラスタ更新情報hi+1からhj-1までの排他的論理和により算出される。
【００３７】
一例として図４に、あるデータ処理装置１２０が、クラスタC2、C5、C9、及びC10のそれぞれについて、当該クラスタに属する少なくとも１つのデータ要素をキャッシュする場合を示す。この場合、データ管理装置１００は、読出要求に応じて、識別子c2と、クラスタ更新情報h2と、クラスタC2の次のクラスタC3から、キャッシュすべきデータ要素が属する次のクラスタC5の直前のクラスタC4までのクラスタ群のクラスタ群更新情報h2,5（=h3 xor h4）とを組としてデータ処理装置１２０へ送信する。同様に、データ管理装置１００は、識別子c5と、クラスタ更新情報h5と、クラスタC6からC8までのクラスタ群のクラスタ群更新情報h5,9（=h6 xor h7 xor h8）との組、識別子c9と、クラスタ更新情報h9と、クラスタ群更新情報h9,10（=0）との組、及び、識別子c10と、クラスタ更新情報h10と、クラスタ群更新情報0との組を、データ処理装置１２０へ送信する。
【００３８】
データ処理装置１２０は、以上に示したクラスタ更新情報及びクラスタ群更新情報の組を受信する。これにより、データ処理装置１２０は、キャッシュしたデータ要素が属する全てのクラスタのクラスタ更新情報（例えばh2、h5、h9、及びh10）を、キャッシュ部１３０にキャッシュすることができる。また、データ処理装置１２０は、キャッシュしたデータ要素が属する各クラスタの間に配列された、キャッシュしたデータ要素が属しない１又は２以上のクラスタからなる全てのクラスタ群について、クラスタ群更新情報（例えばh2,5及びh5,9）をキャッシュ部１３０にキャッシュすることができる。
【００３９】
なお、データ処理装置１２０のそれぞれが、各データ要素が属するクラスタを特定可能な場合においては、データ管理装置１００は、データ要素に対応付けてクラスタの識別子を送信しなくてもよい。
【００４０】
（３）更新チェック方法
（３−１）クラスタ群の更新チェック
データ処理装置１２０は、上記（２）で示したクラスタ更新情報及びクラスタ群更新情報の組をキャッシュする。これによりデータ処理装置１２０は、キャッシュしたデータ要素が属する任意の２つのクラスタにより定まる範囲内のクラスタ群について、クラスタ群更新情報を以下の通り算出することができる。
【００４１】
すなわち、データ処理装置１２０は、キャッシュしたデータ要素が属する、隣接する２つのクラスタのクラスタ更新情報と、この２つのクラスタの間に配列される、キャッシュしたデータ要素が属しない１以上のクラスタについてのクラスタ群更新情報とに基づいて、キャッシュしたデータ要素が属する、隣接する２つのクラスタにより定まる範囲のクラスタ群についてのクラスタ群更新情報を算出することができる。例えば、キャッシュ部１３０は、クラスタ群{C2,…,C5}についてクラスタC2及びC5のみのデータ要素をキャッシュする場合に、クラスタC2のクラスタ更新情報h2と、クラスタC5のクラスタ更新情報h5と、クラスタ群{C2,…,C5}における他の全てのクラスタ{C3,C4}のクラスタ更新情報h3,h4に基づくクラスタ群更新情報h2,5とを、クラスタ群更新情報としてそれぞれキャッシュする。このためデータ処理装置１２０は、クラスタ更新情報h2、クラスタ更新情報h5、及びクラスタ群更新情報h2,5を対応するビット毎に排他的論理和をとることにより、これらの情報に基づいてクラスタ群{C2,…,C5}についてのクラスタ群更新情報check(2,5)を算出することができる。なぜなら、排他的論理和は結合則を満たすため、check(2,5) = h2 xor h3 xor h4 xor h5 = h2 xor (h3 xor h4) xor h5 = h2 xor h2,5 xor h5となるからである。
【００４２】
同様に、データ処理装置１２０は、複数のクラスタ群からなるクラスタ群についてのクラスタ群更新情報を、各クラスタ群のクラスタ群更新情報に基づいて算出することができる。例えば、キャッシュ部１３０は、クラスタ群{C2,…,C10}に属し、クラスタ群{C2,…,C5}及び{C9,C10}に属しない全てのクラスタからなり、いずれのクラスタに属するデータ要素もキャッシングしていないクラスタ群{C6,…,C8}についてのクラスタ群更新情報h5,9をデータ管理装置１００から取得してキャッシュしている。このためデータ処理装置１２０は、キャッシュしたデータ要素が属するクラスタを含むクラスタ群{C2,…,C5}及び{C9,C10}についてのクラスタ群更新情報check(2,5)及びcheck(9,10)と、キャッシュしたデータ要素が属しないクラスタからなるクラスタ群{C6, …,C8}についてのクラスタ群更新情報h5,9とに基づいて、クラスタ群{C2,…,C10}のクラスタ群更新情報check(2,10)を算出することができる。より具体的には、データ処理装置１２０は、クラスタ群更新情報check(2,5)及びcheck(9,10)と、クラスタ群更新情報h5,9とを、対応するビット毎に排他的論理和をとることにより、これらのクラスタ群からなるクラスタ群{C2,…,C10}についてのクラスタ群更新情報check(2,10)を算出することができる。
【００４３】
一方、データ管理装置１００は、任意の２つのクラスタにより定まる範囲のクラスタ群についてのクラスタ群更新情報を、当該クラスタ群内の全クラスタについてデータベース１１０に記憶されたクラスタ更新情報に基づいて算出することができる。すなわち例えば、データ管理装置１００は、クラスタ群{C2,…,C10}についてのクラスタ群更新情報check(2,10)を、データベース１１０に記憶されたクラスタ更新情報h2,…,h10を対応するビット毎に排他的論理和をとることにより算出することができる。
【００４４】
データ処理装置１２０は、キャッシュしたデータ要素が属するクラスタを含むクラスタ群についてのクラスタ群更新情報を、キャッシュ部１３０に記憶されたクラスタ更新情報及び／又はクラスタ群更新情報に基づいて算出する。また、データ処理装置１２０は、同一のクラスタ群についてクラスタ更新情報の参照要求をデータ管理装置１００へ送信して、当該クラスタ群についてのクラスタ群更新情報を取得する。そして、データ処理装置１２０は、算出したクラスタ群更新情報を、データ管理装置１００から取得したクラスタ群更新情報と比較する。これにより、データ処理装置１２０は、比較の結果一致した場合に、当該クラスタ群についてキャッシュしたデータ要素は最新であると判断することができる。
【００４５】
なお、以上の処理において、データ管理装置１００は、データ処理装置１２０からの参照要求に応じたクラスタ群のクラスタ群更新情報を算出することができる。このため、データ管理装置１００は、データ処理装置１２０によりキャッシュされたデータ要素及び／又はクラスタについてのキャッシュ管理を行う必要はない。
【００４６】
（３−２）更新されたクラスタの特定
データ処理装置１２０は、上記（３−１）に示したクラスタ群の更新チェック方法を用いて、キャッシュしたデータ要素が属する全てのクラスタを含むクラスタ群の更新有無を検出することができる。そして、クラスタ群内のいずれかのデータ要素が更新されたことを検出すると、データ処理装置１２０は、当該クラスタ群の部分集合となる部分クラスタ群について更新有無をチェックすることにより、更新されたクラスタの範囲を絞り込むことができる。
【００４７】
本実施形態に係るデータ処理装置１２０は、キャッシュしたデータ要素が属する全てのクラスタを含むクラスタ群をルートノードに対応付け、上位ノードにより指定されるクラスタ群に含まれる、キャッシュしたデータ要素が属するクラスタを含むクラスタ群を下位ノードに対応付け、キャッシュしたデータ要素が属するクラスタを末端ノードに対応付けた木構造グラフを用いて、更新されたクラスタを探索する。なお、本実施形態においては、各ノードに対応するクラスタ群は、クラスタ番号が連続する少なくとも１つのクラスタからなり、当該クラスタ群内において最小のクラスタ番号が割り当てられたクラスタ及び最大のクラスタ番号が割り当てられたクラスタに属する少なくとも１つのデータ要素がキャッシュされていることを前提とする。これに代えて、当該クラスタ群は、最小のクラスタ番号が割り当てられたクラスタ及び／又は最大のクラスタ番号が割り当てられたクラスタのデータ要素がキャッシュされていない形態を採ってもよい。
【００４８】
データ処理装置１２０は、第１の数t1個のクラスタからなる第１のクラスタ群（例えば{C2,…,C10}についてクラスタ群更新情報算出部２６０が算出した第１のクラスタ群更新情報（例えばcheck(2,10)）が、第１のクラスタ群についてデータ管理装置１００から取得した第１のクラスタ群更新情報と一致しない場合において、以下の処理を行う。
【００４９】
ｉ）データ処理装置１２０は、第１のクラスタ群に対応するノードのいずれかの下位ノードに対応する第２のクラスタ群（例えば{C2,…,C5}）について、更新有無をチェックする。
【００５０】
より具体的には、クラスタ群更新情報取得部３１０は、第１のクラスタ群に属し、第１の数より小さい第２の数t2個のクラスタからなる第２のクラスタ群について、当該第２のクラスタ群に属するt2個のクラスタのクラスタ更新情報（例えば{h2,…,h5}）に基づく第２のクラスタ群更新情報（例えばcheck(2,5)）をデータ管理装置１００から取得する。
【００５１】
次に、クラスタ群更新情報算出部２６０は、キャッシュされたt2個のクラスタ更新情報に基づいて、第２のクラスタ群についての第２のクラスタ群更新情報を算出する。この場合において、クラスタ群更新情報算出部２６０は、キャッシュされたクラスタ更新情報に基づいて第２のクラスタ群の更に下位のクラスタ群についてのクラスタ群更新情報を算出し、これらのクラスタ群更新情報に基づいて第２のクラスタ群更新情報を算出してよい。
【００５２】
そして、更新判断部３３０は、クラスタ群更新情報算出部２６０により算出された第２のクラスタ群更新情報が、データ管理装置１００から取得した第２のクラスタ群更新情報と一致する場合に、第２のクラスタ群内のクラスタに属するキャッシュされたデータ要素が最新であると判断する。
【００５３】
ｉｉ）第２のクラスタ群が更新されたと判断した場合、データ処理装置１２０は、第２のクラスタ群の更に下位の第３のクラスタ群について、更新有無をチェックする。
【００５４】
より具体的には、更新判断部３３０は、クラスタ群更新情報算出部２６０により算出された第２のクラスタ群更新情報が、データ管理装置１００から取得した第２のクラスタ群更新情報と一致しない場合、第２のクラスタ群が更新されたと判断する。この場合、クラスタ群更新情報取得部３１０は、第２のクラスタ群に属し、第２の数t2個より小さい第３の数t3個のクラスタからなる第３のクラスタ群について、当該第３のクラスタ群に属するt3個のクラスタのクラスタ更新情報に基づく第３のクラスタ群更新情報をデータ管理装置１００から取得する。
【００５５】
次に、クラスタ群更新情報算出部２６０は、キャッシュされたt3個のクラスタ更新情報に基づいて、第３のクラスタ群についての第３のクラスタ群更新情報を算出する。そして、更新判断部３３０は、クラスタ群更新情報算出部２６０により算出された第３のクラスタ群更新情報が、データ管理装置１００から取得した第３のクラスタ群更新情報と一致する場合に、第３のクラスタ群内のクラスタに属するキャッシュされたデータ要素が最新であると判断する。
【００５６】
ｉｉｉ）上記ｉ）において第２のクラスタ群が更新されていないと判断した場合、データ処理装置１２０は、第１のクラスタ群に対応するノードの下位ノードに対応する第４のクラスタ群（例えば{C9,C10}）について、更新有無をチェックする。
【００５７】
より具体的には、クラスタ群更新情報取得部３１０は、第１のクラスタ群に属し、かつ、第２のクラスタ群に属しない第４の数t4個のクラスタからなる第４のクラスタ群について、当該第４のクラスタ群に属するt4個のクラスタのクラスタ更新情報に基づく第４のクラスタ群更新情報（例えばcheck(9,10)）をデータ管理装置１００から取得する。
【００５８】
次に、クラスタ群更新情報算出部２６０は、キャッシュされたt4個のクラスタ更新情報に基づいて、第４のクラスタ群についての第４のクラスタ群更新情報を算出する。そして、更新判断部３３０は、クラスタ群更新情報算出部２６０により算出された第４のクラスタ群更新情報が、データ管理装置１００から取得した第４のクラスタ群更新情報と一致する場合に、第４のクラスタ群内のクラスタに属するキャッシュされたデータ要素が最新であると判断する。
【００５９】
以上に示したｉ）からｉｉｉ）の処理を木構造グラフの上位ノードに対応するクラスタ群から末端ノードに対応するクラスタに至るまで繰り返すことにより、データ処理装置１２０は、更新されたクラスタを特定することができる。
【００６０】
（３−３）更新されたデータ要素の特定
上記（３−２）の処理により、データ処理装置１２０は、更新されたデータ要素を有するクラスタを特定することができる。これを受けて、データ処理装置１２０は、当該クラスタに属するキャッシュされた各データ要素の更新チェックを行い、更新されたデータ要素をデータ管理装置１００から再度取得する。
【００６１】
（４）キャッシュしたクラスタ群更新情報の更新
クラスタ群更新情報算出部２６０により算出された第１のクラスタ群更新情報（例えばcheck(2,10)）が、データ管理装置１００から取得した第１のクラスタ群更新情報と一致しない場合において、クラスタ群更新情報算出部２６０により算出された第２のクラスタ群更新情報（例えばcheck(2,5)）及び第４のクラスタ群更新情報（例えばcheck(9,10)）が、データ管理装置１００から取得した第２のクラスタ群更新情報及び第４のクラスタ群更新情報とそれぞれ一致した場合、更新判断部３３０は、第１のクラスタ群に属し、第２のクラスタ群及び第４のクラスタ群に属しない全てのクラスタからなる第５のクラスタ群（例えば{C6,…,C8}）が更新されたと判断する。この場合、更新判断部３３０は、データ管理装置１００から取得した第１のクラスタ群更新情報check(2,10)、第２のクラスタ群更新情報check(2,5)、及び、第４のクラスタ群更新情報check(9,10)に基づいて、第５のクラスタ群更新情報h5,9を変更する。
【００６２】
より具体的には、更新判断部３３０は、第１のクラスタ群更新情報check(2,10)、第２のクラスタ群更新情報check(2,5)、及び、第４のクラスタ群更新情報check(9,10)を、対応するビット毎に排他的論理和をとったデータ値を求める。このデータ値は、以下の式に示す通り、第５のクラスタ群更新情報h5,9となる。
【００６３】
check(2,10) xor check(2,5) xor check(9,10)
= (check(2,5) xor h5,9 xor check(9,10)) xor check(2,5) xor check(9,10)
= (check(2,5) xor check(2,5)) xor h5,9 xor (check(9,10) xor check(9,10))
= h5,9                                                                  （１）
【００６４】
以上に示した処理により、データ処理装置１２０は、上位のクラスタ群のクラスタ群更新情報と、キャッシュされたデータ要素が属するクラスタを含む下位のクラスタ群のクラスタ群更新情報とに基づいて、キャッシュされたデータ要素が属しない他のクラスタからなる第５のクラスタ群のクラスタ群更新情報を独自に算出することができる。
【００６５】
図５は、本実施形態に係る情報システム１０における、図４に示した木構造グラフに基づいて更新されたクラスタを検出する場合の通信フローを示す。
【００６６】
まず、データ処理装置１２０内のクラスタ群更新情報算出部３２０は、キャッシュされたデータ要素が属する全てのクラスタを含むクラスタ群{C2,…,C10}についてキャッシュ部１３０に記憶されたクラスタ更新情報に基づいて、クラスタ群更新情報check(2,10)を算出する（ステップＳ５００）。次に、クラスタ群更新情報取得部３１０は、当該クラスタ群についてのクラスタ更新情報の参照要求をデータ管理装置１００へ送信する（Ｓ５０５）。
【００６７】
クラスタ群{C2,…,C10}についてのクラスタ更新情報の参照要求を受けると、データ管理装置１００内のクラスタ群更新情報算出部２６０は、当該クラスタ群のクラスタ群更新情報check(2,10)を算出し（Ｓ５１０）、データ送信部２２０を介してデータ処理装置１２０へ返信する（Ｓ５１５）。
【００６８】
次に、更新判断部３３０は、Ｓ５００において算出したクラスタ群更新情報check(2,10)と、Ｓ５１５においてデータ管理装置１００から取得したクラスタ群更新情報check(2,10)との一致／不一致を判定する（Ｓ５２０）。一致した場合、更新判断部３３０は、当該クラスタ群についてキャッシュしたいずれのデータ要素も最新の値であると判断し、データ処理部３００によるデータ処理を継続させる。
【００６９】
一方、Ｓ５２０において不一致であった場合、データ処理装置１２０内のクラスタ群更新情報算出部３２０は、クラスタ群{C2,…,C10}の下位のクラスタ群{C2,…,C5}及び{C9,…,C10}について、クラスタ群更新情報check(2,5)及びcheck(9,10)を算出する（Ｓ５２２）。次に、クラスタ群更新情報取得部３１０は、これらのクラスタ群についてのクラスタ更新情報の参照要求をデータ管理装置１００へ送信する（Ｓ５２５）。
【００７０】
Ｓ５２５の参照要求を受けると、データ管理装置１００内のクラスタ群更新情報算出部２６０は、これらのクラスタ群のクラスタ群更新情報check(2,5)及びcheck(9,10)を算出し（Ｓ５３０）、データ送信部２２０を介してデータ処理装置１２０へ返信する（Ｓ５３５）。
【００７１】
次に、更新判断部３３０は、Ｓ５２２において算出したクラスタ群更新情報check(2,5)及びcheck(9,10)と、Ｓ５３５においてデータ管理装置１００から取得したクラスタ群更新情報check(2,10)との一致／不一致を判定する（Ｓ５４０）。一致した場合、更新判断部３３０は、これらのクラスタ群についてキャッシュしたいずれのデータ要素も最新の値であると判断し、上位のクラスタ群{C2,…,C10}に属し、下位のクラスタ群{C2,…,C5}及び{C9,…,C10}に属しないクラスタからなるクラスタ群{C6,…,C8}のクラスタ群更新情報h5,9を更新する。
【００７２】
一方、Ｓ５４０においてクラスタ群更新情報check(2,5)が不一致であった場合、データ処理装置１２０内のクラスタ群更新情報取得部３１０は、クラスタ群{C2,…,C5}の更に下位のクラスタC2及びC5についてのクラスタ（群）更新情報を参照する参照要求をデータ管理装置１００へ送信する（Ｓ５４５）。これを受けて、データ管理装置１００内のデータ送信部２２０は、これらのクラスタのクラスタ更新情報h2及びh5をデータ処理装置１２０へ返信する（Ｓ５５０）。
【００７３】
次に、更新判断部３３０は、キャッシュ部１３０にキャッシュされたクラスタ更新情報h2及びh5と、データ管理装置１００から取得したクラスタ更新情報h2及びh5との一致／不一致を判定する（Ｓ５５５）。いずれかのクラスタ更新情報が不一致であった場合、キャッシュ部１３０は、対応するクラスタに属するキャッシュされたデータ要素を無効化する。
【００７４】
一方、Ｓ５５５においていずれのクラスタ更新情報についても一致した場合、クラスタ群更新情報変更部３４０は、上位のクラスタ群{C2,…,C5}に属し、クラスタC2及びC5以外のクラスタからなるクラスタ群{C3,C4}についてのクラスタ群更新情報h2,5を変更する。
【００７５】
以上に示した情報システム１０によれば、データ管理装置１００内のデータベース１１０上のデータ要素を複製して用いるデータ処理装置１２０が、データベース１１０内のデータ要素の更新を効率良く検出することができる。
【００７６】
なお、以上に示したハッシュ関数は、更新検出の精度を高めるために、一般化衝突困難性を満たすことが望ましい。ここで、一般化衝突困難性とは、同一の出力メッセージ空間Mを有するn個の関数H1,…,Hnについて、H1(x1) + H2(x2) + … + Hn(xn) = 0を満たす(x1,…,xn)の組であって自明でないものを発見することが困難であるという性質をいう。ここで、n=2かつH1=H2とすると、上記の性質は、通常のハッシュ関数の衝突困難性の定義となる。H1,…,Hnが理想的なハッシュ関数であれば、上記の性質を満たす。
【００７７】
本実施形態においては、衝突困難性を満たすハッシュ関数Hを用い、Hi(x) = H(i || x)とすることにより、各クラスタのクラスタ更新情報を一般化衝突困難性を満たすハッシュ関数により更新することができる。このようなハッシュ関数を用いることにより、クラスタ内のデータ要素の更新に伴ってクラスタ更新情報が更新された場合、当該クラスタを含むクラスタ群のクラスタ群更新情報が変化する。これにより情報システム１０は、データ要素の更新を精度良く検出することができる。
【００７８】
本実施形態に係る情報システム１０は、上記一般化衝突困難性の条件式H1(x1) + H2(x2) + … + Hn(xn) = 0における演算子“+”として、排他的論理和を用いる。そして、本実施形態に係る情報システム１０は、上記ハッシュ関数が一般化衝突困難性を満たすこと、及び、ハッシュ関数の出力メッセージ空間がビット毎の排他的論理和に対してアーベル群となることを利用している。これにより、同一のクラスタ群については、クラスタ更新情報を加算する順序とは無関係に同一のクラスタ群更新情報を得ることができる。したがって、データ要素が更新されていない場合、下位のクラスタ群のクラスタ群更新情報に基づいてデータ処理装置１２０が算出したクラスタ群更新情報と、同一のクラスタ群について異なる演算順序でデータ管理装置１００が算出したクラスタ群更新情報とが一致する。
【００７９】
本実施形態に係る情報システム１０は、排他的論理和に代えて、上記条件を満たすハッシュ関数又は演算子を用いてもよい。例えば、ハッシュ関数を、離散対数問題が解決困難な有限部分群上のべき演算としてもよい。この場合、ある位数qの部分群G（単位元をIとする）の上でn個の元g1,…,gnを選択すると、g1x1g2x2…gnxn=Iを満たす(x1,…,xn)を決定することは、離散対数問題に基づく表現問題と呼ばれ、離散対数問題と等価な困難性を持つ。そこで、情報システム１０は、クラスタCiに対するハッシュ関数H(x)=gixとし、演算子“+”を部分群G上での積としてもよい。
【００８０】
また、情報システム１０は、クラスタ更新情報の更新にハッシュ関数を用いるのに代えて、インクリメント又はデクリメントによりクラスタ更新情報を更新してもよい。すなわち、クラスタ更新情報変更部２４０は、当該クラスタに属するデータ要素が更新されたことを条件として、データ管理装置１００に記憶されたクラスタ更新情報の元のデータ値を、インクリメント又はデクリメントして得られるデータ値に変更する。そして、クラスタ群更新情報算出部２６０は、クラスタ群についてクラスタ更新情報の参照要求を受けた場合に、当該クラスタ群に属する全クラスタのクラスタ更新情報の合計値を算出し、クラスタ群更新情報とする。
【００８１】
一方、データ処理装置１２０内のクラスタ群更新情報算出部３２０は、同一のクラスタ群について、当該クラスタ群に属する全てのクラスタのクラスタ更新情報を合計したデータ値であるクラスタ群更新情報を算出する。この際、クラスタ群更新情報算出部３２０は、下位の１又は複数のクラスタ群のクラスタ群更新情報を合計し、上位のクラスタ群更新情報としてよい。
【００８２】
情報システム１０は、十分なビット数のクラスタ更新情報及びクラスタ群更新情報を用いることにより、インクリメント又はデクリメントによりクラスタ更新情報を更新する形態においても、データ要素の更新を精度良く検出することができる。
【００８３】
図６は、本実施形態の変形例に係るデータ管理装置１００の構成を示す。本変形例に係る情報システム１０は、キャッシュしたクラスタ更新情報に基づき算出したクラスタ群更新情報をデータ処理装置１２０からデータ管理装置１００へ送信し、データ管理装置１００において更新の検出を行う。図６において、図２と同一の符号を付した部材は、図２とほぼ同一の機能及び構成をとるため、以下相違点を除き説明を省略する。
【００８４】
本変形例に係るデータ管理装置１００は、参照要求受信部２５０及び更新情報送信部２７０に代えてクラスタ群更新情報受信部６５０及び更新通知部６７０を備える。クラスタ群更新情報受信部６５０は、２以上のクラスタからなるクラスタ群について、当該クラスタ群に属するクラスタ更新情報に基づきデータ処理装置１２０が算出したクラスタ群更新情報を含む検査要求を受信する。クラスタ群更新情報算出部２６０は、検査要求により指定されたクラスタ群内の２以上のクラスタについてクラスタ更新情報記憶部２１０に記憶されたクラスタ更新情報に基づいて、クラスタ群更新情報を算出する。更新通知部６７０は、クラスタ群更新情報算出部２６０により算出されたクラスタ群更新情報が、データ処理装置１２０から受信したクラスタ群更新情報と一致する場合に、データ処理装置１２０にキャッシュされた、当該クラスタ群に属するクラスタのデータ要素は最新であることをデータ処理装置１２０へ通知する。一方、不一致であった場合、当該クラスタ群に属するクラスタのデータ要素は更新されたことをデータ処理装置１２０へ通知する。この場合、更新通知部６７０は、クラスタ群更新情報算出部２６０により算出されたクラスタ群更新情報をデータ処理装置１２０へ通知する。
【００８５】
図７は、本実施形態の変形例に係るデータ処理装置１２０の構成を示す。図７において、図３と同一の符号を付した部材は、図３とほぼ同一の機能及び構成をとるため、以下相違点を除き説明を省略する。
【００８６】
本変形例に係るデータ処理装置１２０は、クラスタ群更新情報取得部３１０に代えて更新問合せ部７００を備える。クラスタ群更新情報算出部３２０は、キャッシュした２以上のデータ要素が属する２以上のクラスタについて取得した２以上のクラスタ更新情報に基づいて、当該２以上のクラスタからなるクラスタ群についてのクラスタ群更新情報を算出する。更新問合せ部７００は、クラスタ群更新情報算出部３２０により算出されたクラスタ群更新情報を含む検査要求をデータ管理装置１００へ送信し、２以上のクラスタについてデータ管理装置１００に記憶された２以上のクラスタ更新情報に基づき定められるクラスタ群更新情報と一致するか否かを問い合わせる。更新判断部３３０は、クラスタ群更新情報算出部３２０が算出したクラスタ群更新情報が、データ管理装置１００に記憶されたクラスタ更新情報に基づくクラスタ群更新情報と一致する旨の応答を受けた場合に、クラスタ群内のクラスタに属するキャッシュされたデータ要素が最新であると判断する。
【００８７】
図８は、本実施形態の変形例に係る情報システム１０の通信フローを示す。
まず、図５のＳ５００と同様にして、クラスタ群更新情報check(2,10)を算出する（Ｓ５００）。次に、クラスタ群更新情報取得部３１０は、当該クラスタ群についてのクラスタ群更新情報の検査要求をデータ管理装置１００へ送信する（Ｓ８０５）。
【００８８】
クラスタ群{C2,…,C10}についてのクラスタ群更新情報の検査要求を受けると、データ管理装置１００内のクラスタ群更新情報算出部２６０は、当該クラスタ群のクラスタ群更新情報check(2,10)を算出する（Ｓ５１０）。次に、クラスタ群更新情報算出部２６０は、データ処理装置１２０が算出したクラスタ群更新情報が、Ｓ５１０において算出したクラスタ群更新情報と一致するかどうかを判定し（Ｓ８１２）、判定結果をクラスタ群更新情報受信部６５０を介してデータ処理装置１２０へ通知する（Ｓ８１５）。
【００８９】
更新判断部３３０は、一致した旨の通知を受けると、当該クラスタ群についてキャッシュしたいずれのデータ要素も最新の値であると判断し、データ処理部３００によるデータ処理を継続させる。
【００９０】
一方、不一致の通知を受けると、データ処理装置１２０内のクラスタ群更新情報算出部３２０は、図５のＳ５２２と同様にして、クラスタ群更新情報check(2,5)及びcheck(9,10)を算出する（Ｓ５２２）。次に、更新問合せ部７００は、これらのクラスタ群についてのクラスタ群更新情報の検査要求をデータ管理装置１００へ送信する（Ｓ８２５）。
【００９１】
Ｓ８２５の検査要求を受けると、データ管理装置１００内のクラスタ群更新情報算出部２６０は、これらのクラスタ群のクラスタ群更新情報check(2,5)及びcheck(9,10)を算出する（Ｓ５３０）。次に、クラスタ群更新情報算出部２６０は、データ処理装置１２０が算出したクラスタ群更新情報が、Ｓ５３０において算出したクラスタ群更新情報と一致するかどうかを判定し（Ｓ８３２）、判定結果をクラスタ群更新情報受信部６５０を介してデータ処理装置１２０へ通知する（Ｓ８３５）。
【００９２】
次に、一致した旨の通知を受けると、更新判断部３３０は、これらのクラスタ群についてキャッシュしたいずれのデータ要素も最新の値であると判断し、上位のクラスタ群{C2,…,C10}に属し、下位のクラスタ群{C2,…,C5}及び{C9,…,C10}に属しないクラスタからなるクラスタ群{C6,…,C8}のクラスタ群更新情報h5,9を更新する。
【００９３】
一方、Ｓ８３５において不一致の通知を受けると、データ処理装置１２０内のクラスタ群更新情報取得部３１０は、クラスタ群{C2,…,C5}の更に下位のクラスタC2及びC5についてのクラスタ（群）更新情報の検査要求をデータ管理装置１００へ送信する（Ｓ８４５）。これを受けて、データ管理装置１００内のクラスタ群更新情報算出部２６０は、これらのクラスタのクラスタ更新情報h2及びh5が、クラスタ更新情報記憶部２１０に記憶されたクラスタ更新情報h2及びh5と一致するか否かを判定し（Ｓ８４７）、判定結果をクラスタ群更新情報受信部６５０を介してデータ処理装置１２０へ通知する（Ｓ８５０）。
【００９４】
次に、不一致の通知を受けると、キャッシュ部１３０は、対応するクラスタに属するキャッシュされたデータ要素を無効化する。
【００９５】
一方、いずれのクラスタ更新情報についても一致した旨の通知を受けると、クラスタ群更新情報変更部３４０は、不一致の通知と併せて受信したクラスタ更新情報の最新値に基づいて、上位のクラスタ群{C2,…,C5}に属し、クラスタC2及びC5以外のクラスタからなるクラスタ群{C3,C4}についてのクラスタ群更新情報h2,5を変更する。
【００９６】
以上に示した情報システム１０によれば、図２及び図３に示した情報システム１０と同様に、データ管理装置１００内のデータベース１１０上のデータ要素を複製して用いるデータ処理装置１２０が、データベース１１０内のデータ要素の更新を効率良く検出することができる。
【００９７】
図９は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【００９８】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００９９】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【０１００】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラムや、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。
【０１０１】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【０１０２】
コンピュータ１９００にインストールされ、コンピュータ１９００を図２に示したデータ管理装置１００として機能させるデータ管理プログラムは、データ記憶部２００を管理するデータ管理モジュールと、クラスタ更新情報記憶部２１０を管理するクラスタ更新情報管理モジュールと、データ送信モジュールと、データ受信モジュールと、クラスタ更新情報変更モジュールと、参照要求受信モジュールと、クラスタ群更新情報算出モジュールと、更新情報送信モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、データ記憶部２００と、クラスタ更新情報記憶部２１０と、データ送信部２２０と、データ受信部２３０と、クラスタ更新情報変更部２４０と、参照要求受信部２５０と、クラスタ群更新情報算出部２６０と、更新情報送信部２７０としてそれぞれ機能させる。
【０１０３】
コンピュータ１９００にインストールされ、コンピュータ１９００を図３に示したデータ処理装置１２０として機能させるデータ処理プログラムは、データ処理モジュールと、キャッシュ管理モジュールと、クラスタ群更新情報取得モジュールと、クラスタ群更新情報算出モジュールと、更新判断モジュールと、クラスタ群更新情報変更モジュールと、データ受信モジュールと、データ送信モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、データ処理部３００と、キャッシュ部１３０と、クラスタ群更新情報取得部３１０と、クラスタ群更新情報算出部３２０と、更新判断部３３０と、クラスタ群更新情報変更部３４０と、データ受信部３５０と、データ送信部３６０としてそれぞれ機能させる。
【０１０４】
また、コンピュータ１９００にインストールされ、コンピュータ１９００を図６に示したデータ管理装置１００として機能させるデータ管理プログラムは、データ記憶部２００を管理するデータ管理モジュールと、クラスタ更新情報記憶部２１０を管理するクラスタ更新情報管理モジュールと、データ送信モジュールと、データ受信モジュールと、クラスタ更新情報変更モジュールと、クラスタ群更新情報受信モジュールと、クラスタ群更新情報算出モジュールと、更新通知モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、データ記憶部２００と、クラスタ更新情報記憶部２１０と、データ送信部２２０と、データ受信部２３０と、クラスタ更新情報変更部２４０と、クラスタ群更新情報受信部６５０と、クラスタ群更新情報算出部２６０と、更新通知部６７０としてそれぞれ機能させる。
【０１０５】
コンピュータ１９００にインストールされ、コンピュータ１９００を図７に示したデータ処理装置１２０として機能させるデータ処理プログラムは、データ処理モジュールと、キャッシュ管理モジュールと、更新問合せモジュールと、クラスタ群更新情報算出モジュールと、更新判断モジュールと、クラスタ群更新情報変更モジュールと、データ受信モジュールと、データ送信モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、データ処理部３００と、キャッシュ部１３０と、更新問合せ部７００と、クラスタ群更新情報算出部３２０と、更新判断部３３０と、クラスタ群更新情報変更部３４０と、データ受信部３５０と、データ送信部３６０としてそれぞれ機能させる。
【０１０６】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤやＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【０１０７】
以上に示した情報システム１０によれば、データ管理装置１００内のデータベース１１０上のデータ要素を複製して用いるデータ処理装置１２０が、データベース１１０内のデータ要素の更新を、少ない通信量で効率良く検出することができる。より具体的には、クラスタ更新情報及びクラスタ群更新情報のデータ量をm、従来方法において通常のデータ要素の更新検出に用いる更新情報のデータ量をm'、クラスタの総数をt、キャッシュするデータ要素の数をk、キャッシュしたデータ要素が属する全クラスタの数をl、更新されたデータ要素を有するクラスタの数をαとすると、本実施形態に係る情報システム１０における通信量・計算量、及び従来方法における通信量・計算量は以下のように算出できる。
【０１０８】
（１）本実施形態に係る情報システム１０における通信量・計算量
本実施形態に係る情報システム１０においては、木構造により更新されたクラスタを探索するため、データ管理装置１００及びデータ処理装置１２０の通信回数はlog2lとなる。また、変更されたクラスタを特定するために、2m log2lの通信量を要する。そして、特定されたクラスタに属する全データ要素の更新検査を行うダイレクト・チェッキング（Direct Checking）方式を採ると、更新情報を受信するため１回通信を行い、平均m'k/lのデータを転送する。
したがって、本実施形態に係る情報システム１０においては、総通信量はα(2m log2l + m'k/l)となる。kが十分大きい場合、通信回数の増加に対し、総通信量は指数的に減少する。
また、計算量は、データ管理装置１００による3tα個のクラスタ更新情報の排他的論理和、及び、kα/l個のクラスタ更新情報の検証となる。
【０１０９】
（２）従来方法における通信量
全データ要素についてダイレクト・チェッキング方式により更新検査を行う場合、通信回数は１回で、通信量はkm'となる。計算量はk個のクラスタ更新情報の検証となる。
【０１１０】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【０１１１】
例えば、データ管理装置１００は、データ要素が更新される頻度に基づいて、当該データ要素が属するべきクラスタを選択してもよい。すなわち例えば、データ管理装置１００は、頻繁に更新されるデータ要素を、少数のクラスタに集中して割り当てることにより、図４に示した木構造グラフの探索を効率良く行うことができる。
【０１１２】
このようなクラスタの選択方法の一例として、データ管理装置１００は、ＥＰＣ−ＩＳ等のアプリケーションによる製品情報の管理においては、製品名や製造日等の基本的に更新されない属性データを割り当てるクラスタと、製品の所在等の更新の可能性が高い属性データを割り当てるクラスタとを、異なるクラスタとしてよい。また、データ管理装置１００は、要求に応じて順次製品についての情報を記憶するデータベース行を割り当てていき、連続するデータベース行を同一のクラスタに割り当てることにより、比較的古い更新が稀な製品についてのデータ要素と、比較的新しく更新が頻繁な製品についてのデータ要素とを異なるクラスタに割り当てることができる。
【０１１３】
これに代えて、データ管理装置１００は、データベースの属性又は行毎等の更新頻度を計測し、計測結果に基づいてクラスタを再割当してもよい。
【０１１４】
また、情報システム１０は、複数の情報処理装置のそれぞれが処理の結果ログ情報を出力する情報システムにおいて、これらのログ情報をデータ記憶部２００として記憶し、ログ情報の変化をデータ処理装置１２０により検出するシステムとして用いることもできる。このようなログ情報は、変更が少なく読み出しが中心となるため、本実施形態に係る情報システム１０により効率良く処理することができる。このようなシステムの例としては、情報システムのセキュリティ管理における監査や、センサネットワークによるセンス結果の監視等が挙げられる。
【図面の簡単な説明】
【０１１５】
【図１】本発明の実施形態に係る情報システム１０の構成を示す。
【図２】本発明の実施形態に係るデータ管理装置１００の構成を示す。
【図３】本発明の実施形態に係るデータ処理装置１２０の構成を示す。
【図４】本発明の実施形態に係るクラスタ群更新情報の一例を示す。
【図５】本発明の実施形態に係る情報システム１０の通信フローを示す。
【図６】本発明の実施形態の変形例に係るデータ管理装置１００の構成を示す。
【図７】本発明の実施形態の変形例に係るデータ処理装置１２０の構成を示す。
【図８】本発明の実施形態の変形例に係る情報システム１０の通信フローを示す。
【図９】本発明の実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【符号の説明】
【０１１６】
１０  情報システム
１００  データ管理装置
１１０  データベース
１２０  データ処理装置
１３０  キャッシュ部
２００  データ記憶部
２１０  クラスタ更新情報記憶部
２２０  データ送信部
２３０  データ受信部
２４０  クラスタ更新情報変更部
２５０  参照要求受信部
２６０  クラスタ群更新情報算出部
２７０  更新情報送信部
３００  データ処理部
３１０  クラスタ群更新情報取得部
３２０  クラスタ群更新情報算出部
３３０  更新判断部
３４０  クラスタ群更新情報変更部
３５０  データ受信部
３６０  データ送信部
６５０  クラスタ群更新情報受信部
６７０  更新通知部
７００  更新問合せ部
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
2006185220.tif 000003
【図２】
2006185220.tif 000004
【図３】
2006185220.tif 000005
【図４】
2006185220.tif 000006
【図５】
2006185220.tif 000007
【図６】
2006185220.tif 000008
【図７】
2006185220.tif 000009
【図８】
2006185220.tif 000010
【図９】
2006185220.tif 000011