JPH0833861B2 - 共通情報比較方法 - Google Patents
共通情報比較方法Info
- Publication number
- JPH0833861B2 JPH0833861B2 JP61251702A JP25170286A JPH0833861B2 JP H0833861 B2 JPH0833861 B2 JP H0833861B2 JP 61251702 A JP61251702 A JP 61251702A JP 25170286 A JP25170286 A JP 25170286A JP H0833861 B2 JPH0833861 B2 JP H0833861B2
- Authority
- JP
- Japan
- Prior art keywords
- common information
- node
- identifier
- identifiers
- processors
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明はLAN、オンラインシステム等に利用される分
散データベースシステムにおいてデイレクトリ情報など
の分散システムの共通情報の不一致を検出する方法に関
するものである。
散データベースシステムにおいてデイレクトリ情報など
の分散システムの共通情報の不一致を検出する方法に関
するものである。
分散システムにおける共通情報の一致性は、従来共通
情報作成者が共通情報に付した作成年月日、バージヨン
番号等により人手で検査していた。
情報作成者が共通情報に付した作成年月日、バージヨン
番号等により人手で検査していた。
分散データベースシステムにおいては、各ノードのア
ドレスリスト、あるいは各ノードの外部参照可能データ
ベースの定義情報などの共通情報を互いに複製として持
つている。従来、人手によつて行つて来たこれら共通情
報の一致性のチエツクは共通情報の量の増大とともに困
難さを増大させてきた。また誤操作によりシステムダウ
ンを引き起こしデータに回復困難なダメージを与える可
能性があつた。例えば、全国ネツトワークを使用するア
プリケーシヨンでは共通情報のメンバ数は100〜1000に
なると推定される。また、比較を自動化した場合でも、
そのまま全数比較を行おうとするとオーバーヘツドが大
となり問題である。
ドレスリスト、あるいは各ノードの外部参照可能データ
ベースの定義情報などの共通情報を互いに複製として持
つている。従来、人手によつて行つて来たこれら共通情
報の一致性のチエツクは共通情報の量の増大とともに困
難さを増大させてきた。また誤操作によりシステムダウ
ンを引き起こしデータに回復困難なダメージを与える可
能性があつた。例えば、全国ネツトワークを使用するア
プリケーシヨンでは共通情報のメンバ数は100〜1000に
なると推定される。また、比較を自動化した場合でも、
そのまま全数比較を行おうとするとオーバーヘツドが大
となり問題である。
本発明は上記の問題解決のため、従来人手で行つてい
た共通情報の一致性のチエツクをソフトウエアで自動的
に行うことにより解決しようとするものである。共通情
報にはメンバ毎に作成時刻と作成者を識別するユニーク
な識別子を設定し、これらの一致をチエツクする。チエ
ツクすべきメンバ数の増大に対処するため、チエツクを
段階的に行う方法を採用した。すなわち、共通情報の全
体、全体をいくつかに分けたサブグループ、サブグルー
プをさらに分けたサブグループ等の階層的な分割を行
い、各分割単位毎に、その中のメンバが一致している場
合のみ一致するような識別子を付加した。この識別子を
共通情報全体に対応するものから始めて順に不一致な場
合にそのサブグループを比較する方法でチエツクして全
ての不一致なメンバを確定する。
た共通情報の一致性のチエツクをソフトウエアで自動的
に行うことにより解決しようとするものである。共通情
報にはメンバ毎に作成時刻と作成者を識別するユニーク
な識別子を設定し、これらの一致をチエツクする。チエ
ツクすべきメンバ数の増大に対処するため、チエツクを
段階的に行う方法を採用した。すなわち、共通情報の全
体、全体をいくつかに分けたサブグループ、サブグルー
プをさらに分けたサブグループ等の階層的な分割を行
い、各分割単位毎に、その中のメンバが一致している場
合のみ一致するような識別子を付加した。この識別子を
共通情報全体に対応するものから始めて順に不一致な場
合にそのサブグループを比較する方法でチエツクして全
ての不一致なメンバを確定する。
各プロセツサは共通情報の更新時には、自己プロセッ
サのタイムスタンプと自己プロセツサ識別子をメンバの
識別子として付加するとともに、その上位のサブグルー
プの識別子も全てこの新しい識別子に変更する。そして
この変更内容を他のプロセツサに連絡して反映させる。
各プロセツサの対応する識別子が以前の内容と一致して
いたならば変更を反映させる。この処理を順次上位のノ
ードに対して行う。共通情報のうちいくつかのメンバは
全プロセツサに存在しなくてもよい。存在しないメンバ
および下位にノードを持たないノードは省略するものと
する。これらのノードが比較の対象となつた場合は他の
プロセツサに対応して存在するノードの識別子とは一致
しないような識別子が付加されているものとして比較を
行う。
サのタイムスタンプと自己プロセツサ識別子をメンバの
識別子として付加するとともに、その上位のサブグルー
プの識別子も全てこの新しい識別子に変更する。そして
この変更内容を他のプロセツサに連絡して反映させる。
各プロセツサの対応する識別子が以前の内容と一致して
いたならば変更を反映させる。この処理を順次上位のノ
ードに対して行う。共通情報のうちいくつかのメンバは
全プロセツサに存在しなくてもよい。存在しないメンバ
および下位にノードを持たないノードは省略するものと
する。これらのノードが比較の対象となつた場合は他の
プロセツサに対応して存在するノードの識別子とは一致
しないような識別子が付加されているものとして比較を
行う。
本発明の作用は共通情報の比較に際して階層的にチエ
ツクを行うことにより、チエツク回数を最少化するとと
もに一致していないメンバのみの検出を可能とした。共
通情報ではあるが、使用の際に伝送し、通常は全プロセ
ツサが保有している必要のないメンバに対しては、識別
子の階層を省略することにより識別子の削減が可能であ
る。
ツクを行うことにより、チエツク回数を最少化するとと
もに一致していないメンバのみの検出を可能とした。共
通情報ではあるが、使用の際に伝送し、通常は全プロセ
ツサが保有している必要のないメンバに対しては、識別
子の階層を省略することにより識別子の削減が可能であ
る。
以下、本発明の一実施例を説明する。第６図に本実施
例における分散データベースシステムの構成を示す。ネ
ツワーク４にプロセツサ4a,プロセツサ4b,プロセツサ4c
が接続されている。分散データベースとして各プロセツ
サは学術論文に関するデータベースを分割して保有して
いる。プロセツサ4aには数学論文データベース5aおよび
共通情報1aが付随している。同様にプロセツサ4b,4cに
は各々物理論文データベース5b電子論文データベース5c
と共通情報1b,1cが付随している。共通情報1a,1b,1c
は、それぞれデータベース5a,5b,5cの定義情報の一部分
を含んでいる。
例における分散データベースシステムの構成を示す。ネ
ツワーク４にプロセツサ4a,プロセツサ4b,プロセツサ4c
が接続されている。分散データベースとして各プロセツ
サは学術論文に関するデータベースを分割して保有して
いる。プロセツサ4aには数学論文データベース5aおよび
共通情報1aが付随している。同様にプロセツサ4b,4cに
は各々物理論文データベース5b電子論文データベース5c
と共通情報1b,1cが付随している。共通情報1a,1b,1c
は、それぞれデータベース5a,5b,5cの定義情報の一部分
を含んでいる。
第１図は分散システムにおいて、各プロセツサが保有
している共通情報を合成した全共通情報の構成を示す。
共通情報１は、データ部２およびインデクス部３より構
成されている。データ部２には共通情報の最少単位であ
るメンバ21,22,23が含まれている。これらは、各々数
学，物理，電子の各論文データベースの定義情報であ
る。インデクス部３には木構造のインデクスを構成する
ノード31,311,312,313,3121,3122,3123が含まれてい
る。ノード31は学術論文全体を表し、この下に文学を表
すノード311,理学を表すノード312,工学を表すノード31
3が接続されている。理学を表すノード312の下には、数
学を表すノード3121,物理を表すノード3122が接続され
ている。これらノードには、対応するデータベースの定
義情報を含むメンバ21,22が接続されている。同様に工
学を表すノード313の下には、電子を表すノード3131が
接続され、その下に電子論文データベースの定義情報を
含むメンバ23が接続されている。各ノードには最終更新
時点を表す識別子を記憶することができる。
している共通情報を合成した全共通情報の構成を示す。
共通情報１は、データ部２およびインデクス部３より構
成されている。データ部２には共通情報の最少単位であ
るメンバ21,22,23が含まれている。これらは、各々数
学，物理，電子の各論文データベースの定義情報であ
る。インデクス部３には木構造のインデクスを構成する
ノード31,311,312,313,3121,3122,3123が含まれてい
る。ノード31は学術論文全体を表し、この下に文学を表
すノード311,理学を表すノード312,工学を表すノード31
3が接続されている。理学を表すノード312の下には、数
学を表すノード3121,物理を表すノード3122が接続され
ている。これらノードには、対応するデータベースの定
義情報を含むメンバ21,22が接続されている。同様に工
学を表すノード313の下には、電子を表すノード3131が
接続され、その下に電子論文データベースの定義情報を
含むメンバ23が接続されている。各ノードには最終更新
時点を表す識別子を記憶することができる。
第２図は二つのプロセツサ4a,4bの保有する共通情報1
a,1bの例である。共通情報1cは、データベース5a,5b,5c
の定義情報をおのおの21a,22a,23aとして含んでいる。
一方、共通情報1bには、データベース5a,5bの定義情報2
1b,22bのみが含まれる。第２図において、各ノードの識
別子はプロセツサのタイムスタンプおよびプロセツサの
識別子より構成される。例えばノード31aでは、タイム
スタンプ「２」と識別子「Ａ」である。
a,1bの例である。共通情報1cは、データベース5a,5b,5c
の定義情報をおのおの21a,22a,23aとして含んでいる。
一方、共通情報1bには、データベース5a,5bの定義情報2
1b,22bのみが含まれる。第２図において、各ノードの識
別子はプロセツサのタイムスタンプおよびプロセツサの
識別子より構成される。例えばノード31aでは、タイム
スタンプ「２」と識別子「Ａ」である。
第３図は、比較処理の流れである。比較処理はプロセ
ツサ4a,プロセツサ4b,あるいは第３のプロセツサ4cのい
ずれでも実行することができる。共通情報1a,1bのイン
デクス部から各ノードを一つずつ取り出して下記のよう
に比較をおこなう。第２図の例では不一致のメンバは、
プロセツサ4aの数学データベースの定義情報21aとプロ
セツサ4bの対応するメンバ21bであることがわかる。ま
た、プロセツサ4aの電子データベースの定義情報に対応
するメンバがプロセツサ4bには存在しないことがわか
る。比較処理はインデクス中のルートノードを指定して
サブトリー比較をコールする。サブトリー比較は発見し
た不一致のメンバのリストをコール元へ戻すので、これ
を不一致のメンバのリストとする。
ツサ4a,プロセツサ4b,あるいは第３のプロセツサ4cのい
ずれでも実行することができる。共通情報1a,1bのイン
デクス部から各ノードを一つずつ取り出して下記のよう
に比較をおこなう。第２図の例では不一致のメンバは、
プロセツサ4aの数学データベースの定義情報21aとプロ
セツサ4bの対応するメンバ21bであることがわかる。ま
た、プロセツサ4aの電子データベースの定義情報に対応
するメンバがプロセツサ4bには存在しないことがわか
る。比較処理はインデクス中のルートノードを指定して
サブトリー比較をコールする。サブトリー比較は発見し
た不一致のメンバのリストをコール元へ戻すので、これ
を不一致のメンバのリストとする。
第４図はサブトリー比較の処理の流れを示す。
42では、両プロセッサからノードｉを得る。43でノー
ドｉの識別子が一致している時、不一致メンバリストＬ
＝空でコール元へリターンする。
ドｉの識別子が一致している時、不一致メンバリストＬ
＝空でコール元へリターンする。
識別子不一致の時、44でノードが子ノードを持たず最
下位ノードならば、対応するメンバを不一致メンバリス
トに入れてリターンする。
下位ノードならば、対応するメンバを不一致メンバリス
トに入れてリターンする。
そうでない時、子ノードのチェックを行なう。まず不
一致メンバリストをクリヤしておく。子ノードのなかで
対応するノードが両プロセッサにあるとき不一致リスト
ＬをスタックにPush downし、子ノードｊについて45で
サブトリー比較を再帰的にコールして子ノードｊに対す
る不一致メンバを求め不一致メンバリストＬ′を得る。
そして不一致リストＬをスタックからPop upし、不一致
メンバリストＬ′を不一致メンバリストＬに加える。
一致メンバリストをクリヤしておく。子ノードのなかで
対応するノードが両プロセッサにあるとき不一致リスト
ＬをスタックにPush downし、子ノードｊについて45で
サブトリー比較を再帰的にコールして子ノードｊに対す
る不一致メンバを求め不一致メンバリストＬ′を得る。
そして不一致リストＬをスタックからPop upし、不一致
メンバリストＬ′を不一致メンバリストＬに加える。
また子ノードに対応するノードがない場合には、この
子ノードの子孫である全てのメンバを入れた不一致メン
バリストＬ′を得る。そして不一致メンバリストＬ′を
不一致メンバリストＬに加える。
子ノードの子孫である全てのメンバを入れた不一致メン
バリストＬ′を得る。そして不一致メンバリストＬ′を
不一致メンバリストＬに加える。
子ノードのサーチが終了していなければ、子ノードｊ
のサーチのステップに戻る。
のサーチのステップに戻る。
子ノードのサーチが終了したときは、処理を終了し、
不一致メンバリストＬを持って元へリターンする。
不一致メンバリストＬを持って元へリターンする。
第５図にメンバ更新の処理の流れを示す。プロセツサ
4aが更新を行う場合を示すが、プロセツサ4bが更新を行
う場合も同様である。まず、自プロセツサ4aのメンバを
更新する。次に、52でノードの識別子として自己プロセ
ツサのタイムスタンプと識別子をあわせたものを作成す
る。53でメンバに対応するノードからルートノードまで
のパス上のノードの識別子を新しい識別子に置き換え
る。このとき、新旧識別子のペアをリストとして作成す
る。54でプロセツサ4bに、メンバの更新データと新旧識
別子のペアのリストを送る。プロセツサ4bでメンバを更
新する。メンバに対応するノードからルートノードに向
かつて当該ノードの識別子と送られて来たペアのリスト
の対応する旧識別子を比較する。57で比較結果が一致し
ている場合は、新識別子をそのノードに記入してさらに
上位のノードの比較に進む。一致しない場合は、比較を
打ち切る。分散システム内にあるプロセツサ4b以外のプ
ロセツサに対しても、プロセツサ4bと同様の処理をおこ
なう。
4aが更新を行う場合を示すが、プロセツサ4bが更新を行
う場合も同様である。まず、自プロセツサ4aのメンバを
更新する。次に、52でノードの識別子として自己プロセ
ツサのタイムスタンプと識別子をあわせたものを作成す
る。53でメンバに対応するノードからルートノードまで
のパス上のノードの識別子を新しい識別子に置き換え
る。このとき、新旧識別子のペアをリストとして作成す
る。54でプロセツサ4bに、メンバの更新データと新旧識
別子のペアのリストを送る。プロセツサ4bでメンバを更
新する。メンバに対応するノードからルートノードに向
かつて当該ノードの識別子と送られて来たペアのリスト
の対応する旧識別子を比較する。57で比較結果が一致し
ている場合は、新識別子をそのノードに記入してさらに
上位のノードの比較に進む。一致しない場合は、比較を
打ち切る。分散システム内にあるプロセツサ4b以外のプ
ロセツサに対しても、プロセツサ4bと同様の処理をおこ
なう。
メンバの追加は、メンバに対応するノードからルート
ノードに至るパス上のノードが省略されている場合にノ
ードを追加すること、および追加ノードの旧識別子とし
てシステム共通初期設定用識別子（タイムスタンプ
「Ｏ」、プロセツサ識別子「Ｘ」）を使用すること以外
は、更新の場合と同様である。また、ノードの削除は削
除により子ノードのなくなつたノードを削除する以外
は、更新の場合と同様である。
ノードに至るパス上のノードが省略されている場合にノ
ードを追加すること、および追加ノードの旧識別子とし
てシステム共通初期設定用識別子（タイムスタンプ
「Ｏ」、プロセツサ識別子「Ｘ」）を使用すること以外
は、更新の場合と同様である。また、ノードの削除は削
除により子ノードのなくなつたノードを削除する以外
は、更新の場合と同様である。
本発明によれば、分散システムにおいて各プロセツサ
の持つ共通情報の比較チエツクを全てのメンバを比較す
ることなく効率的に行うことができ、一致しないメンバ
のリストを少ないオーバーヘツドで得ることができる。
また、メンバの一部分を全プロセツサに配置せず、必要
となつた時点で要求のあつたプロセツサへ送る方法によ
り、識別子の一部を省略することも可能である。
の持つ共通情報の比較チエツクを全てのメンバを比較す
ることなく効率的に行うことができ、一致しないメンバ
のリストを少ないオーバーヘツドで得ることができる。
また、メンバの一部分を全プロセツサに配置せず、必要
となつた時点で要求のあつたプロセツサへ送る方法によ
り、識別子の一部を省略することも可能である。
第１図は共通情報の構成図、第２図は２台のプロセツサ
における共通情報のうちインデクス部の例、第３図は比
較処理の流れ図、第４図はサブトリー比較処理の流れ
図、第５図はメンバ更新処理の流れ図、第６図は分散デ
ータベースシステムの構成図である。 １…共通情報、２…インデクス部、３…データ部。
における共通情報のうちインデクス部の例、第３図は比
較処理の流れ図、第４図はサブトリー比較処理の流れ
図、第５図はメンバ更新処理の流れ図、第６図は分散デ
ータベースシステムの構成図である。 １…共通情報、２…インデクス部、３…データ部。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 緒方 博通 神奈川県横浜市戸塚区戸塚町5030番地 株 式会社日立製作所ソフトウエア工場内 (72)発明者 石川 博道 神奈川県横浜市戸塚区戸塚町5030番地 株 式会社日立製作所ソフトウエア工場内
Claims (3)
- 【請求項１】複数のプロセッサより成り共通情報を各プ
ロセッサが保有する分散システムにおける共通情報比較
方法であって、 各プロセッサの複数のメンバよりなる共通情報に各プロ
セッサで同一構造の木構造のインデクスを設けるととも
に木構造の各ノードにその子孫が同一の時にのみ同一の
値となるような識別子のエリアを設け、二つのプロセッ
サの共通情報を比較する時木構造の根より順次識別子を
比較し、識別子が異なる場合、下位ノードについて同様
の比較を繰り返し最下位レベルで識別子が異なっていた
なら対応するメンバを異なったメンバとすることを特徴
とする共通情報比較方法。 - 【請求項２】特許請求の範囲第１項記載の共通情報比較
方法において、 識別子をプロセッサ固有のタイムスタンプとプロセッサ
識別子の組合せとし、各メンバの更新時はその上位のノ
ードの識別子を全て変更するとともに、変更したノード
の新旧識別子を他の全プロセッサに送り、他プロセッサ
は送られてきた旧識別子と自己共通情報の対応するノー
ドの識別子が両者で一致している場合にのみ送られてき
た新識別子を自己の識別子として設定する共通情報管理
を行なうことを特徴とする共通情報比較方法。 - 【請求項３】特許請求の範囲第２項記載の共通情報比較
方法において、 メンバの削除をする場合、上位ノードのうちの削除によ
り下位ノードのなくなったノードを削除するとともに削
除されなかったノードの識別子を全て変更し、新旧識別
子を他の全てのプロセッサに送り、他プロセッサは前記
共通情報管理を行ない、 メンバの追加をする場合、メンバの追加により省略され
ていたノードが必要となった場合には通常使用すること
のない値を持つシステム共通の初期設定値を識別子とし
て持つノードしてこれを追加し、新旧識別子を他の全て
のプロセッサに送り、他プロセッサは前記共通情報管理
を行なうことを特徴とする共通情報比較方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61251702A JPH0833861B2 (ja) | 1986-10-24 | 1986-10-24 | 共通情報比較方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61251702A JPH0833861B2 (ja) | 1986-10-24 | 1986-10-24 | 共通情報比較方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63106860A JPS63106860A (ja) | 1988-05-11 |
| JPH0833861B2 true JPH0833861B2 (ja) | 1996-03-29 |
Family
ID=17226730
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61251702A Expired - Lifetime JPH0833861B2 (ja) | 1986-10-24 | 1986-10-24 | 共通情報比較方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0833861B2 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3866466B2 (ja) | 1999-12-13 | 2007-01-10 | 株式会社東芝 | データ構造管理装置、データ構造管理システム、データ構造管理方法およびデータ構造管理プログラムを格納する記録媒体 |
| JP2003316783A (ja) * | 2002-04-24 | 2003-11-07 | Nippon Telegr & Teleph Corp <Ntt> | 異種半構造化情報源統合検索装置、方法、プログラム及び該プログラムを記録した記録媒体 |
| JP2008250903A (ja) * | 2007-03-30 | 2008-10-16 | Toshiba Corp | ファイル更新装置、プログラム及び方法 |
-
1986
- 1986-10-24 JP JP61251702A patent/JPH0833861B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63106860A (ja) | 1988-05-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2591217B2 (ja) | オブジェクトクラス定義情報実装装置 | |
| US7827302B2 (en) | Scalable virtual partitioning of resources | |
| CA2139693C (en) | Summary catalogs | |
| US6178425B1 (en) | Method of determining the visibility to a remote database client of a plurality of database transactions using simplified visibility rules | |
| US7162499B2 (en) | Linked value replication | |
| US7430570B1 (en) | Shadow directory structure in a distributed segmented file system | |
| US5761678A (en) | Creation of clone storage area with identification of base storage area and deferred cloning of metadata | |
| US6557012B1 (en) | System and method of refreshing and posting data between versions of a database table | |
| US20030135523A1 (en) | Method of using cache to determine the visibility to a remote database client of a plurality of database transactions | |
| AU2019349429B2 (en) | Translation of tenant identifiers | |
| JPH033258B2 (ja) | ||
| US7117221B2 (en) | Replication of changed information in a multi-master environment | |
| JP2004295870A (ja) | アプリケーション定義のシステムにおける整合性ユニットのレプリケーション | |
| JP2003522344A (ja) | データベース同期化／組織化システムおよび方法 | |
| US8015195B2 (en) | Modifying entry names in directory server | |
| US7281014B2 (en) | Method and apparatus for moving data between storage devices | |
| US20190332500A1 (en) | Method and system for global snapshots of distributed storage | |
| AU2019350694B2 (en) | Identification of records for post-cloning tenant identifier translation | |
| US7593951B2 (en) | Application programming interface for centralized storage of principal data | |
| US6516325B1 (en) | Virtual partition vector for a computer directory system | |
| JPH0833861B2 (ja) | 共通情報比較方法 | |
| CN116821232A (zh) | 一种数据同步方法及相关装置 | |
| JPH07210435A (ja) | データベース管理装置 | |
| JPH08329093A (ja) | 分散ディレクトリシステム及び知識情報変更方法 | |
| Matsushita et al. | Cost evaluation of directory management schemes for distributed database systems |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |