(57)【要約】１つまたは複数のローカルアプリケーションがソースオブジェクトに対して要求を行う場合の、ローカルオブジェクトおよび１つまたは複数の宛先オブジェクトに関するデータベースレプリケーション機能が開示される。要求ロギング機能は、１つまたは複数のローカルアプリケーションによって送られた要求をメモリログに記録する。更新伝播機能は、サービス情報品質精度要件に基づいて、どのソースオブジェクト状態を１つまたは複数の宛先オブジェクトに伝播しなければならないかを決定する。
2008519372.tif 000002
【特許請求の範囲】
【請求項１】
コンテナオブジェクト構造を有し、１つまたは複数の包含オブジェクトをさらに有するソースオブジェクト（１０８）と、
前記ソースオブジェクト（１０８）と同一のコンテナオブジェクト構造を有する１つまたは複数の宛先オブジェクト（１２０）と、
前記ソースオブジェクト（１０８）に対する要求を作成するように適合された１つまたは複数のローカルアプリケーション（１０４）と、
前記１つまたは複数のアプリケーション（１０４）によって前記ソースオブジェクト（１０８）に送られた要求のシーケンスを記録するように適合された要求ロギング機能（１１０）と、
サービス情報品質精度要件に基づいてどのソースオブジェクト（１０８）状態を前記１つまたは複数の宛先オブジェクト（１２０）に伝播させるかを決定する更新伝播機能（１１４）と
を備えるデータベースシステム。
【請求項２】
前記要求ロギング機能（１１０）が、前記ソースオブジェクトの状態変化を引き起こさない要求をフィルタリングし、前記ソースオブジェクト（１０８）の状態変化を引き起こす、前記１つまたは複数のアプリケーション（１０４）によって前記ソースオブジェクト（１０８）に送られた要求のシーケンスを記録するようにさらに適合される請求項１に記載のデータベースシステム。
【請求項３】
前記更新伝播機能（１１４）が、ソースオブジェクト（１０８）状態の前記包含オブジェクトのうちの１つまたは複数が伝播条件を満たすかどうかを判定することにより、どのソースオブジェクト（１０８）状態を伝播しなければならないかを決定し、
前記サービス情報品質精度要件が、前記包含オブジェクトのうちの１つまたは複数についてのパラメータ（Δｓ，Δｔ）を含み、
ｓｉからｓｊへの前記包含オブジェクト状態変化の大きさがパラメータΔｓ以上であり、かつ状態ｓｊが宛先オブジェクト（１２０）に伝播することなくΔｔ以上の時間にわたって包含オブジェクト上に存在している場合、包含オブジェクトについての伝播条件が満たされ、
ｓｉからｓｊへの前記包含オブジェクト状態変化の大きさが、距離関数を使用して測定される請求項１に記載のデータベースシステム。
【請求項４】
前記更新伝播機能（１１４）が、前記要求ロギング機能（１１０）からの要求のシーケンスに基づいて更新のシーケンスを出力することにより、ソースオブジェクト（１０８）状態を前記宛先オブジェクトに伝播させ、
前記更新伝播機能（１１４）が、コンテナ仕様に基づいて、要求ロギング機能（１１０）からの要求のシーケンスを部分的に配列された要求の組に変換し、
前記更新伝播機能（１１４）が、前記部分的に配列された要求の組を要求の圧縮シーケンスに変換する圧縮アルゴリズムを適用して、更新のシーケンスを生成し、
前記更新伝播機能（１１４）が、前記サービス情報品質タイミング要件を超過しないように選ばれた繰返し周期で周期的に実行される請求項３に記載のデータベースシステム。
【請求項５】
前記１つまたは複数の宛先オブジェクト（１２０）から着信更新を受け取り、前記更新を前記ソースオブジェクト（１０８）に伝播させる更新受信機能（１１６）をさらに備える請求項１に記載のデータベースシステム。
【請求項６】
データベース更新を伝播させる方法であって、
１つまたは複数のアプリケーション（１０４）によってソースオブジェクト（１０８）に対して作成された要求をロギングするステップと、
以前の最後の更新伝播以来のソースオブジェクト（１０８）状態変化の大きさを求めるステップと、
前記ソースオブジェクト（１０８）状態変化の大きさがサービス情報品質精度パラメータΔｓ以上であるかどうかを判定するステップと、
前記宛先オブジェクト（１２０）に伝播することなくサービス情報品質精度パラメータΔｔ以上の時間にわたって現在のソースオブジェクト（１０８）状態が前記ソースオブジェクト（１０８）上に存在しているかどうかを判定するステップと、
前記ソースオブジェクト（１０８）状態変化の大きさがΔｓ以上であり、かつ現在のソースオブジェクト（１０８）状態が前記１つまたは複数の宛先オブジェクト（１２０）に伝播することなくΔｔ以上の時間にわたってソースオブジェクト（１０８）上に存在しているとき、前記ロギングした要求に基づいて、１つまたは複数の宛先オブジェクト（１２０）に更新のシーケンスを伝播させるステップであって、前記ソースオブジェクト（１０８）状態変化の大きさが距離関数によって求められるステップと
を含む方法。
【請求項７】
前記ロギングした要求を要求の圧縮シーケンスに変換する圧縮アルゴリズムを適用して、前記更新のシーケンスを生成するステップをさらに含む請求項６に記載の方法。
【請求項８】
前記ソースオブジェクト（１０８）状態変化の大きさがΔｓ以上となった後に、前記１つまたは複数の宛先オブジェクト（１２０）に前記ソースオブジェクト（１０８）状態を伝播させることがどれほどの期間許容されるかを判定するステップであって、更新のシーケンスを伝播することが、その期間で完了するステップをさらに含む請求項６に記載の方法。
【請求項９】
１つまたは複数の宛先オブジェクト（１２０）から着信更新を受け取るステップと、
着信更新を前記ソースデータベース（１０８）に適用するステップと
をさらに含む請求項６に記載の方法。
【請求項１０】
ソースオブジェクト（１０８）および１つまたは複数の宛先オブジェクト（１２０）に対するデータベースレプリケーション機能（１０６）において、１つまたは複数のローカルアプリケーション（１０４）が前記ソースオブジェクト（１０８）に対する要求を作成するデータベースレプリケーション機能（１０６）であって、
前記１つまたは複数のアプリケーション（１０４）によって前記ソースオブジェクト（１０８）に送られた要求のシーケンスを記録するように適合された要求ロギング機能（１１０）と、
サービス情報品質精度要件に基づいて、どのソースオブジェクト（１０８）状態を前記１つまたは複数の宛先オブジェクト（１２０）に伝播するかを決定する更新伝播機能（１１４）とを有し、
前記要求ロギング機能（１１０）が、前記ソースオブジェクト（１０８）の状態変化を引き起こさない要求をフィルタリングし、前記ソースオブジェクト（１０８）の状態変化を引き起こす、前記１つまたは複数のアプリケーション（１０４）によって前記ソースオブジェクト（１０８）に送られた要求のシーケンスを記録するようにさらに適合され、
前記更新伝播機能（１１４）が、現在のソースオブジェクト（１０８）状態が伝播条件を満たすかどうかを判定することにより、どのソースオブジェクト（１０８）状態が伝播するかを決定し、前記サービス情報品質精度要件がパラメータ（Δｓ，Δｔ）を含み、ｓｉからｓｊへの前記ソースオブジェクト（１０８）状態変化の大きさがパラメータΔｓ以上であり、かつ状態ｓｊが宛先オブジェクト（１２０）に伝播することなくΔｔ以上の時間にわたってソースオブジェクト（１０８）上に存在している場合、前記伝播条件が満たされ、ｓｉからｓｊへの前記ソースオブジェクト（１０８）状態変化の大きさが、距離関数を使用して測定され、
前記更新伝播機能（１１４）が、前記要求ロギング機能（１１０）からの要求のシーケンスに基づいて更新のシーケンスを出力することにより、ソースオブジェクト（１０８）状態を前記宛先オブジェクト（１２０）に伝播させ、前記更新伝播機能（１１４）が、前記要求ロギング機能（１１０）からの要求のシーケンスを要求の圧縮シーケンスに変換する圧縮アルゴリズムを適用して、更新のシーケンスを生成するデータベースレプリケーション機能（１０６）。
【請求項１１】
前記更新伝播機能（１１４）がさらに、サービス情報品質タイミング要件に基づいてソースオブジェクト（１０８）状態を前記宛先オブジェクト（１２０）に伝播し、前記更新伝播機能（１１４）が、前記サービス情報品質タイミング要件を超過しないように選ばれた繰返し周期で周期的に実行される請求項１０に記載のデータベースレプリケーション機能。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にコンピュータデータベースに関し、より詳細には、ネットワーク上の重複データベースの同期に関する。
【背景技術】
【０００２】
典型的なコンピュータネットワークは、通信ネットワークによってリンクされた複数のコンピュータを含む。こうしたコンピュータ上で動作するアプリケーションは、情報を共有する必要がある。１つの解決策は、コンピュータのうちの１つの上にデータベースをホストし、アプリケーションの位置に関わらず、アプリケーションにこのデータベースを読み取らせ、更新させることである。このクライアント−サーバ解決策は、多くの状況で十分に機能するが、ネットワーク帯域幅または可用性が十分ではないとき、サーバがアプリケーションのデータベース・アクセス・ワークロードに対処することができないとき、およびサーバが受け入れられないほど危険な単一障害点であるときに、効果性が低くなる。
【０００３】
こうした問題に対処する代替方法は、コンピュータの一部またはすべての上にデータベースを複製することである。各コンピュータ上で、アプリケーションは、ローカルデータベースに要求を送信することによってローカルデータベースを読み取り、更新し、それが完了すると、データベースは各要求に対する応答を送信する。この構成での問題は、データベースレプリカを互いに整合するように保つことである。この一方式は、要求側アプリケーションに対して完了を確認する前に各更新があらゆるデータベースに伝播および適用されるイーガレプリケーション（ｅａｇａｒ  ｒｅｐｌｉｃａｔｉｏｎ）によって実施することができる。さらに、更新が同じ順序ですべてのデータベースに適用され、データベースが依然として互いに整合していることが保証される。クライアント−サーバ手法と比較して、イーガレプリケーションは、ネットワーク障害およびノード障害に直面しても、照会性能および照会可用性の改善を実現する。しかし、更新性能は実際には低く、ネットワーク障害またはノード障害中は、ノード間の通信リンクが遮断されるので、更新を実施することができない。こうした問題には、クォーラムベースの手法を使用して、照会性能および照会可用性を犠牲にして対処することができる。データベースレプリカを整合するように保つ別の方式は、レイジーレプリケーション（ｌａｚｙ  ｒｅｐｌｉｃａｔｉｏｎ）によるものである。レイジーレプリケーションでは、各アプリケーションがそのローカルデータベースに要求を送信し、要求がローカルに処理されるとすぐに確認応答を受信する。その後で、レプリケーション機能がローカル更新を他のコンピュータに伝播し、ローカル更新をそうしたコンピュータのデータベースに適用する。通信接続性が一時的に遮断された場合、更新伝播が遅延するが、ローカルデータベース要求処理は続行する。
【０００４】
データベースレプリケーションにおける現況技術に伴う１つの問題は、イーガレプリケーション方法も、既存のレイジーレプリケーション方法も、妥当なレベルのデータベース同期を依然として維持すると共に、通信ネットワーク資源コストの削減に十分対処していないことである。
【０００５】
Ｏｒａｃｌｅなどの市販のデータベース管理製品はレイジーレプリケーションを実装する。こうした製品で一般に使用される２つの手法は、データレベルレプリケーションと手続きレベルレプリケーションである。データレベルレプリケーションでは、伝播される要求は、挿入、更新、および削除である。要求再配列および圧縮が使用される。手続きレベルレプリケーションでは、要求は任意の手続きであるが、要求再配列および圧縮は使用されない。どちらの手法も、データベースレプリカ内の情報がデータベースの定義された使命に対する妥当な同期要件を満たすことを依然として保証する一方で、通信ネットワーク資源コストを削減することを試みない。
【０００６】
データ記憶コストを削減するのに通常使用されるデータベース圧縮の一形態は、プロセス・データ・ヒストリアン（ｐｒｏｃｅｓｓ  ｄａｔａ  ｈｉｓｔｏｒｉａｎ）と呼ばれる。プロセス・データ・ヒストリアンは、周囲のサンプルからの補間によって受け入れられる精度で再構築することのできるサンプルをなくす「スインギング・ドア・アルゴリズム（ｓｗｉｎｇｉｎｇ  ｄｏｏｒ  ａｌｇｏｒｉｔｈｍ」と呼ばれる圧縮技法を使用する。しかし、補間は、任意に複雑な状態空間に対して定義されておらず、したがってプロセス制御システムに見られるような単純なスカラデータに応用が限定される。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述の理由と、本明細書を読んで理解するときに当業者には明らかとなる以下で述べるその他の理由のために、妥当に信頼性の高いデータを提供しながら通信ネットワーク資源コストを削減するデータベースレプリケーションが当技術分野で求められている。
【課題を解決するための手段】
【０００８】
本発明の実施形態は、サービス情報品質要件の適用を介するネットワーク資源コストを削減する問題、ならびに以下の明細書を読んで研究することによって理解される他の問題に対処する。
【０００９】
本発明の実施形態は、通信ネットワーク資源コストを削減しながら、データベースの特定の使命を考慮して許容される、データベースレプリカ内に含まれるデータの正確さと、データベースレプリカに更新を伝播させる際の遅延の量（すなわち、データベースレプリカ内の情報の鮮度）とによって定義されるデータベース同期のレベルを実現する。
【００１０】
一実施形態では、ソースオブジェクトおよび１つまたは複数の宛先オブジェクトに対するデータベースレプリケーション機能であって、１つまたは複数のローカルアプリケーションがソースオブジェクトの要求を作成するデータベースレプリケーション機能が開示される。要求ロギング機能が、１つまたは複数のアプリケーションによってソースオブジェクトに送信された要求をメモリログに記録する。更新伝播機能は、サービス情報品質精度要件に基づいてどのソースオブジェクト状態を１つまたは複数の宛先オブジェクトに伝播しなければならないかを判定する。
【００１１】
別の実施形態では、データベースシステムが開示される。データベースシステムは、コンテナオブジェクト構造を有するローカルオブジェクトと、ローカルオブジェクトと同じコンテナオブジェクト構造を有する１つまたは複数の宛先オブジェクトと、ソースオブジェクトに対する要求を作成するように適合された１つまたは複数のローカルアプリケーションとを含む。データベースシステム内の要求ロギング機能は、１つまたは複数のアプリケーションによってソースオブジェクトに送信された要求のシーケンスを記録するように適合される。更新伝播機能は、サービス情報品質精度要件に基づいてどのソースオブジェクト状態を１つまたは複数の宛先オブジェクトに伝播させるかを判定する。
【００１２】
さらに別の実施形態では、データベース更新を伝播させる方法が開示される。この方法は、１つまたは複数のアプリケーションによってソースオブジェクトに対して作成された要求をロギングすることを含む。この方法は、以前の最後の更新伝播以来のソースオブジェクト状態変化の大きさを求めること、およびソースオブジェクト状態変化の大きさがサービス情報品質精度パラメータΔｓ以上であるかどうかを判定することに進む。次いで、この方法は、宛先オブジェクトに伝播することなくサービス情報品質精度パラメータΔｔ以上の時間にわたって現在のソースオブジェクト状態がソースオブジェクト上に存在しているかどうかを判定することに進む。次いで、ソースオブジェクト状態変化の大きさがΔｓ以上であり、かつ現在のソースオブジェクト状態が１つまたは複数の宛先オブジェクトに伝播することなくΔｔ以上の時間にわたってソースオブジェクト上に存在している場合、この方法は、１つまたは複数の宛先データベースに更新を伝播させることに進む。
【００１３】
さらに別の実施形態では、データベース更新を伝播させる別の方法が開示される。この方法は、１つまたは複数のアプリケーションによってソースオブジェクトに対して作成された要求をロギングすること、以前の最後の更新伝播以来のソースオブジェクト状態変化の大きさがサービス情報品質精度パラメータΔｓ以上であるかどうか、および宛先オブジェクトに伝播することなくサービス情報品質精度パラメータΔｔ以上の時間にわたって現在のソースオブジェクト状態がソースオブジェクト上に存在しているかどうかを周期的に判定することを含む。ソースオブジェクト状態変化の大きさがΔｓ以上であり、かつ現在のソースオブジェクト状態が１つまたは複数の宛先オブジェクトに伝播することなくΔｔ以上の時間にわたってソースオブジェクト上に存在しているとき、この方法は、ロギングされた要求を要求の圧縮シーケンスに変換する圧縮アルゴリズムを適用すること、および要求の圧縮シーケンスを１つまたは複数の宛先オブジェクトに伝播させることに進み、ソースオブジェクト状態変化の大きさを周期的に求める繰返し周期が、サービス情報品質タイミング要件を超過しないように選ばれる。
【００１４】
さらに別の実施形態では、データベース更新を伝播させる別の方法が開示される。この方法は、１つまたは複数のアプリケーションによってソースオブジェクトに対して作成された要求をロギングすること、以前の最後の更新伝播以来のソースオブジェクト状態変化の大きさを求めること、およびソースオブジェクト状態変化の大きさがサービス情報品質精度パラメータΔｓ以上であるかどうかを判定することを含む。ソースオブジェクト状態変化の大きさがΔｓ以上であるとき、この方法は、ロギングした要求に基づいて、１つまたは複数の宛先データベースに更新のシーケンスを伝播させることに進む。
【００１５】
さらに別の実施形態では、データベース更新を伝播させる別の方法が開示される。この方法は、１つまたは複数のアプリケーションによってソースオブジェクトに対して作成された要求をロギングすること、以前の最後の更新伝播の時以来のソースオブジェクト状態変化の大きさを求めること、およびソースオブジェクト状態変化の大きさがサービス情報品質精度パラメータΔｓ以上であるかどうかを判定することを含む。ソースオブジェクト状態変化の大きさがΔｓ以上であるとき、この方法は、ロギングした要求を要求の圧縮シーケンスに変換する圧縮アルゴリズムを適用して更新のシーケンスを生成すること、およびロギングされた要求に基づいて、１つまたは複数の宛先データベースに更新のシーケンスを伝播させることに進む。
【００１６】
さらに別の実施形態では、コンピュータ可読媒体内に組み込まれる、データベース更新を伝播させる方法が開示される。この方法は、１つまたは複数のアプリケーションによってソースオブジェクトに対して作成された要求をロギングすることを含む。この方法は、以前の最後の更新伝播以来のソースオブジェクト状態変化の大きさを求めること、およびソースオブジェクト状態変化の大きさがサービス情報品質精度パラメータΔｓ以上であるかどうかを判定することに進む。次に、この方法は、宛先オブジェクトに伝播することなくサービス情報品質精度パラメータΔｔ以上の時間にわたって現在のソースオブジェクト状態がソースオブジェクト上に存在しているかどうかを判定することに進む。次いで、ソースオブジェクト状態変化の大きさがΔｓ以上であり、かつ現在のソースオブジェクト状態が１つまたは複数の宛先オブジェクトに伝播することなくΔｔ以上の時間にわたってソースオブジェクト上に存在している場合、この方法は、１つまたは複数の宛先データベースに更新を伝播させることに進む。
【００１７】
好ましい実施形態説明と以下の図を見て考慮するとき、本発明をより容易に理解することができ、本発明の利点および用途がより明白となる。
一般的慣習に従って、記載の様々な特徴は原寸に比例せず、本発明に関連する特徴を強調するように描かれている。参照文字は図および本文全体にわたって同様の要素を示す。
【発明を実施するための最良の形態】
【００１８】
帯域幅が貴重であり、可用性が断続的であるワイヤレスネットワークなどの環境では、通信コストの削減が重要である。レイジーレプリケーションは、あるオブジェクト（例えばソースデータベース）に適用される更新を他のオブジェクト（例えば宛先データベース）に伝播させることによってデータベースレプリカを同期された状態に保つ。本発明の実施形態は、（許容できる同期時間鮮度要件および精度要件に関する）サービス情報品質要件を考慮に入れ、ネットワーク上のコンピュータ間のデータベース更新を伝播させるためのネットワーク資源関連の通信コストを削減する。
【００１９】
本発明の実施形態は２つの要素を有する。第１の要素は、レプリカを許容できる程度に同期するように依然として保ちながら、ソースデータベース更新のシーケンスをより短い宛先データベース更新のシーケンスに圧縮するものである。第２の要素は、何がデータベースレプリカの許容できる同期を構成するかを、サービス情報品質（ＩＱｏＳ）鮮度および精度要件に関して正確に定義することである。
【００２０】
図１に、本発明の一実施形態のデータベースシステム１０２の構成要素を全体的に１００で示す。データベースレプリケーション機能１０６内では、要求ロギング機能１１０は、ローカルアプリケーション１０４がローカル情報オブジェクト１０８に送信する要求のシーケンスを記録する。一実施形態では、ローカル情報オブジェクト１０８はソースデータベース１０８を含む。レコードロギング機能１１０が、ローカルオブジェクト１０８の状態変化を実際に引き起こさないどんな要求もフィルタリングし、その結果、ロギングされた各要求は、オブジェクト１０８に対する更新を表す。更新伝播機能１１４は、本明細書で開示されるように、データベース管理者または所有者によって選択されたＩＱｏＳ精度要件に基づいてどのオブジェクト状態が伝播するかを決定する。更新伝播機能１１４は、ロギングされた結果を要求の圧縮シーケンスに変換し、要求の圧縮シーケンスは、通信リンク１１８を介してローカルオブジェクト１０８の状態を宛先オブジェクト１２０に伝播させる。一実施形態では、宛先オブジェクト１０８は宛先データベース１０８を含む。更新伝播機能１１４は、ＩＱｏＳ伝播鮮度要件に基づいて、要求の圧縮シーケンスを宛先オブジェクト１２０に対する更新受信機能１２２に送信する。一実施形態では、データベースシステム１０２は、１つまたは複数の他のデータベースシステム１２４から類似の更新を受信し、ローカル情報オブジェクト１０８に更新を適用する更新受信機能１１６をさらに含む。
【００２１】
本明細書はデータベースレプリカに関して本発明の実施形態を議論するが、実施形態で提示される手法は、定義された状態と、アプリケーションがその状態をそれによって読み取り、更新することのできる１組のオペレーションとを有する任意の情報オブジェクトに関して有効である。そのような情報オブジェクトは、限定はしないが、単純離散的変数、ファイルの集合、またはリレーショナル・データベースも含むことができる。
【００２２】
オブジェクトの挙動は、そのタイプＴ＝（Ｓ，ｓ０，Ｑ，Ｒ，！，？）によって完全に定義される。Ｓは、オブジェクトの状態空間、すなわち可能なオブジェクト値の組である。Ｓは、少数の列挙される選択肢の組から、リレーショナルモデル、オブジェクト指向モデル、または類似のモデルによって定義された高度に構造化された非常に多数の組にまで及ぶことができる。この構造は、アプリケーションにとっては、各要求に対するオブジェクト応答により、間接的にしか見ることができない。オブジェクトの初期状態はεである。
【００２３】
アプリケーションは、オブジェクトに要求を送信し、応答を受信することによってオブジェクトを読み取り、または更新する。Ｑは、可能な要求の組であり、Ｒは、可能な応答の組である。ＱおよびＲは、可変内容フィールドを有する要求フォームおよび応答フォームによって定義された、少数から非常に多数のものに及ぶことができる。
【００２４】
オブジェクト挙動は、アプリケーションが要求ｑをローカルオブジェクト１０８に送信するときにはいつでも、要求を実行した後のオブジェクトの応答ｒおよびその状態ｓ’が、要求ｑおよび要求を受信する前のオブジェクト状態ｓによって完全に求められる（すなわちそれらの関数である）という意味で決定性である。応答および状態遷移関数が挿入演算子？および！によって示され、その結果ｒ＝ｓ？ｑおよびｓ’＝ｓ！ｑとなる。オブジェクトに送信された要求は、何らかのシリアル順に、または少なくともシリアル化可能な方式で実行されると仮定され、オブジェクトによって実行される要求のシーケンスをレプリケーションで使用するために記録することができると仮定される。
【００２５】
一例を挙げると、一実施形態では、単純オブジェクトタイプテーブルが、ｎ個の列を有し、その最初のｋがキー列である単一リレーショナルテーブルからなる。データベース内のキー（キー列やキー値など）は通常、個々のレコードを一意に識別するのに使用され、従って２つのレコードは重複キー値を有さない。非キー列値は意味を有し、あるデータベース状態ｓｉから別のデータベース状態ｓｊへの非キー列値に対する変更は通常、何らかの現実世界パラメータの変化を表す（例えば、当座預金残高や、燃料タンク内の残留燃料）。一実施形態では、例示的オブジェクトタイプテーブルは、ｉｎｓｅｒｔ（ｘ１，．．．，ｘｎ）、ｄｅｌｅｔｅ（ｘ１，．．．，ｘｋ）、ｓｅｔ（ｘ１，．．．，ｘｋ，ｉ，ｘｊ）（ただしｋ＜ｉ≦ｎ）、およびｇｅｔ（ｘ１，．．．，ｘｋ，ｉ）（ただしｋ＜ｉ≦ｎ）という４つの種類の要求を受け入れる。
【００２６】
状態は、ｘ１，．．．，ｘｋについて２つの別個の行が同一の値を有さないような（ｘ１，．．．，ｘｎ）という形の行の組である。状態空間Ｓは、そのようなすべての行の組の組である。状態空間Ｓを状態変数によってより正確に定義することができる。状態変数は、状態空間Ｓの識別可能で更新可能な要素である。状態変数は、単にタイプ指定のために使用される。オブジェクトの実装は、異なる方式で状態を記録することができる。一実施形態では、タイプテーブルについて、状態変数は、
ｅｘｉｓｔｓ：｛０，１｝のａｒｒａｙ（Ｄ１，．．．，Ｄｋ）
ｃｏｌｉ：Ｄｉのａｒｒａｙ（Ｄ１，．．．，Ｄｋ）（ｋ＜ｉ≦ｎ）
上式で、Ｄ１，．．．，Ｄｋは、列１，．．．，ｎの領域である。状態変数ｅｘｉｓｔｓ（ｘ１，．．．，ｘｋ）は、キー値ｘ１，．．．，ｘｋを有する行が存在するかどうか（１＝あり、０＝なし）を示し、状態変数ｃｏｌｉ（ｘ１，．．．，ｘｋ）は、キーｘ１，．．．，ｘｋに対する非キー列ｉの値を保持する。厳密に言えば、ｃｏｌｉ（ｘ１，．．．，ｘｋ）は、ｅｘｉｓｔｓ（ｘ１，．．．，ｘｋ）＝０である場合、未定義である可能性がある。初期状態εは、すべての可能なキー値についてｅｘｉｓｔｓ（ｘ１，．．．，ｘｋ）＝０を有する。
【００２７】
要求シーケンス圧縮。ソースデータベース１０８に適用された各更新およびあらゆる更新を適用することなく、宛先データベース１２０を十分新鮮かつ正確に保つことができる。最初に、ソースデータベース１０８と宛先データベース１２２はどちらも、その挙動タイプに従って状態ｓ０を有する。ソースコンピュータ１０２上のアプリケーション１０４は、要求ｑ１，ｑ２，ｑ３，ｑ４，ｑ５，．．．をソースデータベース１０８に送信し、データベース１０８に、時刻ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，．．．で新しい状態ｓ１，ｓ２，ｓ３，ｓ４，ｓ５，．．．を達成させる。一実施形態では、レプリケーション機能１０６は、これらの要求をソースコンピュータ１０２内のログ１１２に記録する。更新伝播機能１１４は、ロギングされた要求を要求の圧縮シーケンス、例えばｑ’１，ｑ’３，ｑ’５，．．．に変換する圧縮アルゴリズムを適用し、これらを宛先データベース１２０に送信する。その結果、宛先データベース１２０は、時刻ｔ’１，ｔ’３，ｔ’５，．．．にソースデータベース１０８の状態のサブシーケンスｓ１，ｓ３，ｓ５，．．．を達成する。ソースデータベースに本来適用される要求のシーケンスよりも低いコストで要求の圧縮シーケンスを通信することができる。
【００２８】
一実施形態では、圧縮アルゴリズムはソースコンピュータのログ１２２に記録された要求のシーケンスで開始し、それ以上の変換が不可能となるまで１組の圧縮変換を反復的に適用する。各圧縮変換は、連続する要求ｑ１，．．．，ｑｎのシーケンスをｑ’１，．．．，ｑ’ｍ（０≦ｍ＜ｎ）で置き換える。ソースデータベース１０８の挙動タイプは、許容される圧縮変換の組を決定する。圧縮変換ｑ１，．．．，ｑｎ→ｑ’１，．．．，ｑ’ｍは、２つの条件を満たす場合に許容される。第１に、変換により、宛先データベース１２０が、要求の圧縮シーケンスを実行した後にソースオブジェクト１０８と同じ状態を達成しなければならない。より正確には、任意の状態ｓについてｓ！ｑ’１！．．．！ｑ’ｍ＝ｓ！ｑ１！．．．！ｑｎである（ｑ’１からｑ’ｍの要求のシーケンスによって操作されるデータベース状態ｓが、ｑ１からｑｎのシーケンスによって操作される状態と同じ状態になると解釈される）。第２に、変換により、ソースデータベース１０８が達成しなかった状態を宛先データベース１２０が達成してはならない。無関係の状態を宛先データベース１２０に導入すると、精度の定義が複雑になる。より正確には、任意の状態ｓについてｓ，ｓ！ｑ’１，ｓ！ｑ’１！ｑ’２，．．．，ｓ！ｑ’１！．．．！ｑ’ｍが、ｓ，ｓ！ｑ１，ｓ！ｑ１！ｑ２，．．．，ｓ！ｑ１！．．．！ｑｎのサブシーケンスでなければならない。一般的な種類の圧縮変換は、オブジェクトの状態を変更しない要求を省略することである。
【００２９】
表１に、本発明の一実施形態のオブジェクトタイプテーブルについての例示的圧縮変換を列挙する。
【００３０】
【表１】
2008519372.tif 000003
【００３１】
一実施形態では、圧縮アルゴリズムは、１つまたは複数の可換要求を再配列する。任意のオブジェクト状態ｓについて、どちらの順序の要求を適用することも同じ最終的オブジェクト状態および要求に対する応答が得られる場合、２つの要求ｑおよびｑ’は可換である。
【００３２】
ｓ！ｑ！ｑ’＝ｓ！ｑ’！ｑ
ｓ！ｑ？ｑ’＝ｓ！ｑ’
ｓ！ｑ’！ｑ＝ｓ！ｑ
要求が可換でない場合、それらは競合すると呼ばれる。異なるキー値ｘ１，．．．，ｘｋを有する要求は可換である。したがって、同じ行の異なる列に対するｓｅｔおよびｇｅｔ要求は可換である。ｇｅｔ操作は、オブジェクト状態に対する効果がなく、したがって同じｇｅｔ要求の２つのインスタンスも可換である。要求の可換性は、圧縮のためのさらなる機会を開くことのできる再配列を可能にする。テーブルオブジェクトに対する要求ロギング機能１１０が、ｇｅｔ要求を省略し、ｉｎｓｅｒｔ／ｓｅｔ／ｄｅｌｅｔｅ要求に失敗したと仮定する。同じｒｏｗ（ｘ１，．．．，ｘｋ）オブジェクトに対する要求が隣接するようにシーケンスを再配列することができる。さらに、同じ列に対するｓｅｔ要求が隣接するように、ｉｎｓｅｒｔ要求とｄｅｌｅｔｅ要求との間のｓｅｔ要求を再配列することができる。この再配列が行われた後、圧縮変換を適用して、宛先オブジェクトに送らなければならない要求の数を激減させることができる。
【００３３】
可換要求を個々に再配列し、圧縮し、および伝播させることができる。より重要な状態変化を直ちに伝播させることができると共に、他の状態変化を保持して、場合によっては伝播させる前にさらに圧縮する。例えば、アプリケーションは、あるオブジェクト列について、他のオブジェクト列よりも高い精度を必要とすることがある。
【００３４】
一実施形態では、ソースデータベース１０８はコンテナオブジェクトである。異なるキー値ｘ１，．．．，ｘｋを伴う要求などの要求が可換であるとき、オブジェクトの状態空間が何らかの構造を有し、要求がオブジェクトの異なる部分に作用することを示唆している。オブジェクトは、オブジェクトをその状態の一部として含むコンテナオブジェクトとして振る舞う。
【００３５】
コンテナオブジェクトの挙動タイプは、オブジェクトの内部状態空間内の構造、ならびに要求と状態空間の特定の部分との関連を明らかにする。こうした特性は、コンテナ仕様内に取り込まれる。
【００３６】
図２に、本発明の一実施形態についての上記の例示的オブジェクトタイプテーブルに関するコンテナ仕様２００を示す。コンテナ仕様２００などのコンテナ仕様は、コンテインメントツリー（ｃｏｎｔａｉｎｍｅｎｔ  ｔｒｅｅ）２０２、ツリー２０８および２１２内のオブジェクト（またはノード）に対する状態変数の割当て、およびオブジェクト２０８および２１２に対する要求の割当てを含む。
【００３７】
第１に、上記の例示的オブジェクトタイプテーブルに関するコンテナ仕様２００は、コンテインメントツリー２０２を含む。ルートオブジェクト２０８はコンテナオブジェクト全体を表す。一実施形態では、ルートオブジェクトは、各キー値（ｘ１，．．．，ｘｋ）についてのｒｏｗ（ｘ１，．．．，ｘｋ）オブジェクト２１０を含むオブジェクトである。ルートオブジェクト２０８は、割り当てられた状態変数または要求を有さない。ルートオブジェクト２０８以外のオブジェクトは、包含オブジェクト２１２を表す。各包含オブジェクト２１２は、名前および０以上の「キー」値によって識別される。
【００３８】
第２に、上記の例示的オブジェクトタイプテーブルに関するコンテナ仕様２００は、コンテインメントツリー２０２内の包含オブジェクト２１２に状態変数を割り当てる。オブジェクト２１２の状態は、そのオブジェクトおよびその子孫に割り当てられた状態変数によって保持される。一実施形態では、各ｒｏｗ（ｘ１，．．．，ｘｋ）オブジェクト２１０に状態変数ｅｘｉｓｔｓ（ｘ１，．．．，ｘｋ）が割り当てられる。一実施形態では、各ｒｏｗ（ｘ１，．．．，ｘｋ）オブジェクト２１０が、１つまたは複数のｃｅｌｌ（ｘ１，．．．，ｘｋ，ｉ）（ｋ＜ｉ≦ｎ）オブジェクト２１４である子孫を含む。各セル（ｘ１，．．．，ｘｋ，ｉ）オブジェクト２１４に状態変数ｃｏｌｉ（ｘ１，．．．，ｘｋ）が割り当てられる。
【００３９】
第３に、例示的オブジェクトタイプテーブルに関するコンテナ仕様２００は、Ｑ内のあらゆる要求ｑをコンテインメントツリー２０２内のオブジェクト２１２に割り当てる。１）任意のコンテナオブジェクト２０８状態ｓについて、新しい状態ｓ！ｑおよび応答ｓ？ｑが、包含オブジェクト２１４−１の状態と、コンテインメントツリー２０２内の包含オブジェクト２１４−１の子孫に割り当てられる状態変数のみの関数であり、かつ２）古い状態ｓと新しい状態ｓ！ｑとの任意の差が、包含オブジェクト２１４−１の状態になければならない場合、要求ｑにオブジェクト（例えばオブジェクト２１４−１）に割り当てることができる。２つの要求ｑおよびｑ’が独立の包含オブジェクト２１２（そのうちのどれもコンテインメントツリー内の他のものの祖先ではない別個の包含オブジェクト）に割り当てられるときはいつでも、それらのうちのどれも、他のものが読み取り、または更新することのできる状態変数を更新することができないので、要求は可換でなければならない。しかし、２つの可換要求を、独立ではないオブジェクトに割り当てることは可能である。図２に示すように、上記の例示的オブジェクトタイプテーブルに関する一実施形態では、各ｒｏｗ（ｘ１，．．．，ｘｋ）オブジェクト２１０に要求ｉｎｓｅｒｔ（ｘ１，．．．，ｘｎ）およびｄｅｌｅｔｅ（ｘ１，．．．，ｘｋ）が割り当てられ、各ｃｅｌｌ（ｘ１，．．．，ｘｋ，ｉ）オブジェクト２１４に要求ｓｅｔ（ｘ１，．．．，ｘｎ，ｉ，ｘｉ）およびｇｅｔ（ｘ１，．．．，ｘｋ，ｉ）が割り当てられる。
【００４０】
一実施形態では、適切なコンテナ仕様２００を使用することによって要求再配列を制御することができる。２つの要求が独立の包含オブジェクト２１２に割り当てられる場合、それらは可換でなければならない。この割当てを行うことにより、システム設計者は、これらの要求の再配置が受け入れられることを示している。あるいは、システム設計者は、同一のオブジェクト、または一方が他方を含む別個のオブジェクトに要求を割り当てることもできる。これは、要求が可換であっても再配列が受け入れられないことを示す。
【００４１】
コンテナ仕様が与えられると、要求のシーケンスを、部分的に配列された要求の組に変換することができる。図３ａでは、本発明の一実施形態についてのコンテナ仕様３００に関する部分的に配列された要求の組が示されている。部分的順序は、データベースシステム設計者によって選択される、要求間の矢印によって示される要求３２０の間の１組の順序付き制約３１０である。
【００４２】
部分的順序は、要求再配列に対するすべての許容される機会を表す、要求間の１組の順序付き制約である。要求３２０は、ログ１１２内の要求の順序を反映する水平位置と、コンテインメントツリー３４０内のオブジェクト３３０−ａから３３０−ｅに対する要求の割当てを反映する垂直位置として配置される。便宜上、特別なノードｓｔａｒｔ３５０およびｎｏｗ３５５が示されている。部分的順序は、コンテイメントツリー３４０内の同じオブジェクト３３０−ａから３３０−ｅに割り当てられ、または一方が他方の祖先である２つのオブジェクト（例えば、オブジェクト３３０−ｂはオブジェクト３３０−ｄおよび３３０−ｅの祖先である）に割り当てられた任意の２つの要求３２０間の順序付き制約３１０（矢印で示す）を配置することにより、更新伝播機能１１４によって構築される。
【００４３】
図３ｂに示すように、オブジェクト状態は、このグラフ内で破線３６０および点線３７０−１、３７０−２、および３７０−３によって表される。破線３６０は、時刻ｔ０での状態ｓ０から時刻ｔｊでの現ソースオブジェクト１０８状態ｓｊまでのソースオブジェクト１０８内のすべてのオブジェクト３３０−ａから３３０−ｅの状態を表す（全体的に３８０で示す）。点線３７０−１、３７０−２、および３７０−３は、宛先オブジェクトに伝播させることのできる他の状態を表す。コンテナオブジェクトを複製するとき、コンテナオブジェクト全体（すなわちオブジェクト３０３−ａおよびその子孫オブジェクト３０３−ｂから３０３−ｅ）の状態またはその包含オブジェクト（すなわちオブジェクト３０３−ｂから３０３−ｅ）のいずれかの状態を伝播させることが可能である。
【００４４】
時刻ｔｉでのソースオブジェクト１０８の任意の状態ｓｉについて、ｓｉｎは、包含オブジェクトｎ（すなわちオブジェクト３０３−ｂから３０３−ｅ）のうちの１つの対応する状態である。例えば、一実施形態では、ｓ１ｂは、時刻ｔ１でのオブジェクト３３０−ｂの状態である。状態ｓｉｎを伝播させるために、更新伝播機能１１４は、要求ｑｋ（要求３２０のうちの１つ）がオブジェクトｎ（すなわちオブジェクト３３０−ａから３３０−ｅのうちの１つ）またはその子孫のうちの１つに割り当てられるような最高のｋ≦ｉを識別する。次いで、更新伝播機能１１４は、宛先オブジェクト１２０にまだ送られていない部分的順序内の要求ｑｋおよびその全ての祖先を伝播させる。図３ｂは、要求３２０を伝播状態ｓｉｄ３７０−１、状態ｓｉｂ３７０−２、およびｓｉａ（＝ｓｉ）３７０−３に送らなければならない一実施形態を示す。この実施形態では、状態ｓｉｂを伝播させるために、要求シーケンスｑｉ−３，ｑｉ−２，ｑｉ−１またはｑｉ−３，ｑｉ−１，ｑｉ−２を送らなければならない。ｑｉ−１がｑｉ−２の前に伝播される場合、宛先オブジェクトは、ソースオブジェクトが決して達成しなかった状態を達成することに留意されたい。
【００４５】
一実施形態では、更新伝播機能１１４は、部分的順序に適合する順序で要求３２０を伝播させる。一実施形態では、更新伝播機能１１４は、部分的順序と適合する要求３２０を、宛先オブジェクト１２０に伝播させる前に圧縮する。
【００４６】
図４では、宛先オブジェクト１２０に対する更新伝播を実施する前に、コンテナオブジェクトであるソースオブジェクト１０８に影響を及ぼす要求４００のシーケンスを圧縮する方法が開示される。コンテナ仕様によって誘発される要求の部分的順序により、要求を再配列することが可能となり、さらなる圧縮が可能となる。一実施形態では、要求がまず、コンテインメントツリー内の同一ノードに割り当てられる要求が互いに隣接するように再配列される（４１０）。同一ノードに割り当てられる要求の相対的順序、および別個であるが独立していないノードに割り当てられる要求を維持しなければならない。次いで、先に説明したように圧縮変換を適用する（４２０）。宛先オブジェクト１２０は、ソースオブジェクト１０８と同じタイプを有さなければならず、したがってコンテナオブジェクトでもなければならない。
【００４７】
サービス情報品質（ＩＱｏＳ）。データベース状態伝播に関するサービス情報品質は、鮮度および精度の点で測定される。鮮度は、更新がソースデータベース１０８から宛先データベース１２０に伝播するのにどれほどかかるかの尺度となる。精度は、宛先データベース１２０の状態がソースデータベース１０８の状態をどれほど密接に追跡するかの尺度となる。システム１００のレプリケーション鮮度および精度要件を明示的に定義することができる場合、レプリケーション機能１０６は、通信ネットワーク１１８資源の使用を最適化するために要件によって与えられる柔軟性を利用することができる。
【００４８】
ＩＱｏＳ精度要件。ＩＱｏＳ精度要件は、どの状態がソースデータベース１０８から宛先データベース１２０に伝播されるかの選択を制御する。以前に伝播された状態からの変化が十分大きく（Δｓ）、状態が十分な時間間隔（Δｔ）だけ持続している場合にのみ、ソースデータベース１０８状態を伝播しなければならない。２つのパラメータ（Δｓ，Δｔ）は精度ＩＱｏＳ要件を構成する。一実施形態では、精度要件（０，Δｔ）により、時間間隔Δｔだけ持続するあらゆる状態が宛先データベース１２０に伝播する。一実施形態では、精度要件（Δｓ，０）により、大きさΔｓ以上の変化を表すあらゆる状態が宛先データベース１２０に伝播する。一実施形態では、精度要件（０，０）により、あらゆる状態が宛先データベース１２０に伝播する。
【００４９】
別の実施形態では、ネットワーク資源コストを削減するように２つの精度パラメータ（Δｓ，Δｔ）が選ばれる。一実施形態では、精度要件パラメータΔｔは関数Δｔ（Δｓ）である。Δｔがこの関数として表されると、少なくともΔｔ（Δｓ）の時間間隔だけ持続する（すなわち、完全に表現される精度要件が（Δｓ，Δｔ（Δｓ）である）場合、大きさΔｓの状態変化が伝播しなければならない。一実施形態では、この関数は単調非増加であり、その結果より大きな変化がより早く伝播するが、より小さい変化は比較的長い期間にわたって伝播する。
【００５０】
一実施形態では、オブジェクト状態変化の大きさが、距離関数を使用して測定される。距離関数ｄ（ｓ，ｓ’）は非負実数を返し、以下の特性を有する。
ｄ（ｓ，ｓ’）＝０  （ｓ＝ｓ’の場合のみ）
ｄ（ｓ，ｓ’）＝ｄ（ｓ’，ｓ）
ｄ（ｓ，ｓ’）＋ｄ（ｓ’，ｓ’’）≧ｄ（ｓ，ｓ’’）
宛先データベース１２０に伝播すべきソースデータベース１０８状態のシーケンスは以下のように求められる。状態ｓ０（ソースデータベース１０８と宛先データベース１２０の両方の初期状態）は、ソースオブジェクトと宛先オブジェクトがどちらも最初はこの状態にあるので、「伝播する」と仮定される。ソースデータベース１０８状態ｓｉが先に宛先データベース１２０に伝播したと仮定し、ｔが現在時刻であると仮定する。ｊが伝播条件
（１）ｄ（ｓｉ，ｓｊ）≧Δｓかつｔ≧ｔｊ＋Δｔ
に合致するｉよりも大きい最小の整数である場合、ソースデータベース１０８状態ｓｊが宛先データベース１２０に伝播する次の状態である。
【００５１】
言い換えれば、ｓｉからｓｊへのソースデータベース１０８状態変化の大きさがパラメータΔｓ以上であり、かつ状態ｓｊが宛先データベース１２０に伝播することなくΔｔ以上の時間にわたってソースデータベース１０８上に存在している場合、伝播条件が満たされる。
【００５２】
一実施形態では、以下の関数が、先に論じた例示的オブジェクトタイプテーブルに関する距離関数を定義する。
【００５３】
【数１】
2008519372.tif 000004
【００５４】
ここで、状態変数ｅｘｉｓｔｓおよびｃｏｌｉは状態ｓを表し、状態変数ｅｘｉｓｔｓ’およびｃｏｌ’ｉは状態ｓ’を表す。この実施形態では、距離関数は、２つの状態ｓとｓ’の両方に存在するすべての列およびすべてのキー値にわたって合計した、ｓまたはｓ’のどちらかに存在するが、両方には存在しないキー値の数と、（よりプリミティブな距離関数ｄｉによって測定された）非キー列値間の距離という２つの項の和として、２つの状態ｓとｓ’の間の差を測定する。他の実施形態では、この距離関数の変形例が、様々な項に対する重みを適用し、そのアプリケーション重要度を表す。
【００５５】
更新伝播機能は、項ｄ（ｓｉ，ｓｊ）中のソースオブジェクトの過去の状態を参照する、上記の伝播条件（１）を評価しなければならない。過去のオブジェクト状態の完全な表現を格納することは常に実際的であるわけではなく、常に必要なわけでもない。多くの場合、格納する必要がある情報はずっと少ない。例えば、上記の距離関数は、各項が単一のテーブル行、場合によっては単一のテーブル列を参照する項の和である。各要求は、単一行または単一列に影響を与え、したがって、距離関数に増分変化を引き起こす。この増分変化を求めるためには、古い値ｘｌを各ｓｅｔ（ｘ１，．．．，ｘｋ，ｉ，ｘ’ｌ）要求と共に記録し、古い非キー値ｘｋ＋１，．．．，ｘｎを各ｄｅｌｅｔｅ（ｘ１，．．．，ｘｋ）要求と共に記録することで十分である。まさにこの情報を使用して、要求ｑｉ＋１，．．．，ｑｊの効果を累積することによって距離ｄ（ｓｉ，ｓｊ）を計算することが可能である。
【００５６】
一実施形態では、ＩＱｏＳ精度要件がコンテナオブジェクトに対して定義される。この実施形態では、ソースオブジェクト１０８が状態ｓｏで開始し、要求ｑ１，ｑ２，．．．に応答して時刻ｔ１，ｔ２，．．．で状態ｓ１，ｓ２，．．．を達成する。ＩＱｏＳ精度要件（Δｓｎ，Δｔｎ）は、コンテナオブジェクト２０８または包含オブジェクト２１２に関する状態伝播を以下のように制御する。ｓｊｎがソースオブジェクト１０８状態であり、ｓｉｎが、レプリケーション機能が宛先オブジェクトに伝播させた最後の以前の状態であり、ｔが現在時刻であると仮定する。状態ｓｊｎが伝播条件
（２）ｄｎ（ｓiｎ，ｓｊｎ）≧Δｓｎかつｔ≧ｔｊｎ＋Δｔｎ
を満たす場合、状態ｓｊｎは伝播しなければならない。
【００５７】
ソースオブジェクト１０８の任意の状態ｓｉについて、ｓｉｎは包含オブジェクトｎの対応する状態であり、ｔｉｎは、包含オブジェクトｎがこの状態を達成したときの時刻である。オブジェクトｎがコンテナオブジェクトを表すとき、この伝播条件（２）は、任意のオブジェクトについて先に述べた伝播条件（１）と同じである。包含オブジェクトについて、ｔｊｎがｔｊよりも早くてよいという点で定義がわずかに異なる。具体的には、ｑｋがオブジェクトｎ（すなわちノード１０８または１１２）またはコンテインメントツリー２０２内のその子孫のうちの１つに割り当てられるように最大のｋ≦ｊを選ぶ。すなわち、ｑｋは、オブジェクトｎの状態を変更した状態ｓｊに反映される最後の要求である。その場合、ｔｊｎ＝ｔｋである。
【００５８】
前述のように、ＩＱｏＳ精度要件は、ソースから宛先オブジェクト１２０に伝播すべき状態の選択を制御する。一実施形態では、コンテナ仕様２００内の各オブジェクト２０８および２１２は、関連するＩＱｏＳ精度要件（Δｓｎ，Δｔｎ）および関連するＩＱｏＳ鮮度要件Ｔｐｎを有し、データベース設計者によって決定されるアプリケーションの必要に従って、そのオブジェクトに関する状態伝播を制御する。別の実施形態では、コンテナ仕様２００内のオブジェクト２０８および２１２のうちの１つまたは複数は、関連するＩＱｏＳ精度要件（Δｓｎ，Δｔｎ）および関連する距離関数ｄｎ（全体的に２２０で示す）を有する。
【００５９】
一実施形態では、以下の距離関数がルートコンテナオブジェクト２０８に割り当てられ、
【００６０】
【数２】
2008519372.tif 000005
【００６１】
別々の距離関数ｄｉ：Ｄｉ×Ｄｉ→Ｒが包含オブジェクト２１２のうちの１つまたは複数に割り当てられる。
一実施形態では、ｎがコンテナオブジェクトを表すとき、各距離関数ｄｎは以下の形式である。
【００６２】
【数３】
2008519372.tif 000006
【００６３】
上式で、νｍは、サブスペースｍに割り当てられた状態変数を表し、ｄｎｍは、サブスペースｍからサブスペースｎの距離関数への寄与である。サブスペースｎの子孫はｎ自体を含む。
【００６４】
ＩＱｏＳ鮮度要件。ＩＱｏＳ鮮度要件は、すべての伝播状態ｓｉについての伝播時間に対して伝播遅延範囲Ｔｐを配置する（すなわちｔ’ｉ≦ｔｉ＋Ｔｐ）。一般には、遅延範囲が広いほど、要求を伝播させるために資源を割り振る際に通信ネットワーク１１８がより高い柔軟性を有し、一時的ネットワーク利用不能に対してレプリケーション機能１０６がより高い弾力性を有する。言い換えれば、より長い期間にわたって更新をローカルオブジェクト１０８から宛先オブジェクト１２０に伝播させることができる場合、所与の時点で更新を伝播させるために必要なネットワーク１１８資源が少なくなる。ＩＱｏＳ鮮度要件Ｔｐは、ｄ（ｓｉ，ｓｊ）≧Δｓとなった後に伝播時間がどれほどの期間許容できるかを定義する。コンテナオブジェクトでは、ＩＱｏＳ鮮度要件Ｔｐｎは、時刻ｔｊｎ＋Ｔｐｎまでにｓｊｎを宛先オブジェクト１２０で実現しなければならないことを述べている。
【００６５】
ＩＱｏＳ鮮度要件によれば、時刻ｔ’ｊ≦ｔｊ＋Ｔｐで、任意の伝播状態ｓｊを宛先オブジェクト１２０で実現しなければならない。伝播条件（すなわちｄ（ｓｉ，ｓｊ）≧Δｓおよびｔ≧ｔｊ＋Δｔ）では、ｔは現在時刻を参照する。したがって、更新伝播機能１１４は、状態ｓｊを伝播すべきかどうかを判定するために、現在時刻ｔがｔｊ＋Δｔと等しくなるまで待機しなければならない。更新伝播機能１１４は、ローカルオブジェクト１０８を更新するローカルアプリケーション１０４に関して非同期式に動作する。単純な手法は、更新伝播機能１１４を周期Ｔｃで周期的に実行することである。データベース設計者は、本明細書で開示されるようにＩＱｏＳ鮮度要件を満たすことができるように周期Ｔｃを選ぶべきである。
【００６６】
Ｔｃに対する制約は以下のようなものである。更新伝播機能１１４が実行を開始した後に、宛先オブジェクト１２０で状態ｓｊを実現するのに必要な時間をＴｒとする。ネットワーキング環境、特にワイヤレスネットワークなどの断続的接続性のネットワーキング環境では、この時間を確実に固定することができない。したがって、特定のシステムおよびアプリケーションに対して十分な確実性で満たすことのできるＴｒに対する値を仮定する。最悪の場合、更新伝播機能１１４は時刻ｔｊ＋Δｔの直前に実行を開始する。伝播条件ｄ（ｓｉ，ｓｊ）≧Δｓおよびｔ≧ｔｊ＋Δｔが満たされないので、更新伝播機能１１４は、状態ｓｊを宛先オブジェクト１２０に伝播させるべきであると判定するために、時刻ｔｊ＋Δｔ＋Ｔｃまで待機する。次いで状態ｓｊが時刻ｔｊ＋Δｔ＋Ｔｃ＋Ｔｒに宛先オブジェクト１２０で実現される。ｔｊ＋Δｔ＋Ｔｃ＋Ｔｒはｔｊ＋Ｔｐを超過すべきではないので、ＴｃはＴｐ−Ｔｒ−Δｔ以下であるべきである。したがって、考慮すべき３つのケースが存在する。第１に、Ｔｒ＞Ｔｐである場合、Ｔｃの選択の如何に関わらずＩＱｏＳ鮮度要件を明白に満たすことができない。第２に、Ｔｒ＜Ｔｐ−Δｔである場合、Ｔｃ＝Ｔｐ−Ｔｒ−Δｔを選ぶことによってＩＱｏＳ鮮度要件が満たされることになる。第３に、Ｔｐ−Δｔ≦Ｔｒ≦Ｔｐである場合、伝播条件によって識別されるものに加えて追加の状態を伝播させることによってのみ、ＩＱｏＳ鮮度要件を満たすことができる。その場合、更新伝播機能１１４は、Ｔｒ＜Ｔｐ−Δｔおよび第２のケースが成り立つように、より小さいΔｔの値を選ぶことができる。
【００６７】
コンテナオブジェクトを有する実施形態では、各ノード２０８および２１２がそれ自体のＩＱｏＳ鮮度要件Ｔｐｎおよび精度要件（Δｓｎ，Δｔｎ）を有することができるので、一実施形態では、上述のように各ノードについてＴｃｎを計算し、Ｔｃを最小値のＴｃｎに等しくすることによってＴｃが求められる。
【００６８】
図５では、本発明の一実施形態のデータベース更新５００を伝播させる方法が示されている。この方法は、１つまたは複数のアプリケーションによるソースオブジェクトに対して行われる要求をロギングすることによって開始する（５１０）。以前の更新伝播の時間以来のソースオブジェクト状態変化の大きさが求められる（５２０）。ソースオブジェクト状態変化の大きさがサービス情報品質精度パラメータΔｓ以上である場合（５３０）、かつ現在のソースオブジェクト状態が宛先オブジェクトに伝播することなくサービス情報品質精度パラメータΔｔ以上の時間にわたって存在している場合（５４０）、この方法は、ロギングされた要求に基づいて、１つまたは複数の宛先データベースに更新のシーケンスを伝播させることに進む（５５０）。ある実施形態では、ソースオブジェクト状態変化の大きさは、距離関数によって求められる。ある実施形態では、この方法は、ロギングされた要求を要求の圧縮シーケンスに変換して更新のシーケンスを生成する圧縮アルゴリズムを適用することをさらに含む。ある実施形態では、この方法は、ソースオブジェクト状態変化の大きさがΔｓ以上となった後に１つまたは複数の宛先オブジェクトにソースオブジェクト状態を伝播させるのにどれほどの期間が許容できるかを判定すること、およびその期間内の更新のシーケンスの伝播を完了することをさらに含む。
【００６９】
図６では、本発明の一実施形態のコンテナオブジェクトについてのデータベース更新６００を伝播させる方法が示されている。この方法は１つまたは複数のアプリケーションによってソースオブジェクトに対して行われるロギング要求によって開始する（６１０）。以前の更新伝播の時以来の１つまたは複数のソースオブジェクトノード状態変化の大きさが求められる（６２０）。１つまたは複数のソースオブジェクトノード状態変化の大きさが１つまたは複数のノードに対して定義されたサービス情報品質精度パラメータΔｓ以上である場合（６３０）、かつ現在のソースオブジェクトノード状態が宛先オブジェクトに伝播することなく（１つまたは複数のノードに対して定義された）サービス情報品質精度パラメータΔｔ以上の時間にわたって存在している場合（６４０）、この方法は同一のノードに割り当てられた要求が隣接するように要求を再配列することに進む（６４５）。次に、圧縮変換が再配列後の要求に適用され（６４８）、更新のシーケンスが、圧縮された要求に基づいて、１つまたは複数のソースオブジェクトノード状態変化の大きさがΔｓ以上となった後の時間Ｔｐｎ内に、１つまたは複数の宛先データベースに伝播する（６５０）。一実施形態では、ソースオブジェクトノード状態変化の大きさが距離関数によって求められる。
【００７０】
本発明のデータベースレプリケーション実施形態を実装するのにいくつかの手段が利用可能である。こうした手段には、限定はしないが、デジタルコンピュータシステム、プログラマブルコントローラ、またはフィールドプログラマブルゲートアレイが含まれる。したがって、本発明の他の実施形態は、そのようなコントローラによって実装されたときにコントローラが本発明の実施形態を実装することを可能にするコンピュータ可読媒体上にあるプログラム命令である。コンピュータ可読媒体は、限定はしないが、磁気ディスクまたはテープ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、または任意の光学式データ記憶システム、フラッシュＲＯＭ、不揮発性ＲＯＭ、またはＲＡＭを含む任意の形態のコンピュータメモリを含む。
【００７１】
本明細書で特定の実施形態を図示および説明したが、図示する特定の実施形態を、同じ目的を達成するように考慮された任意の構成で置き換えることができることを当業者は理解されよう。本願は、本発明の任意の適合または変形を包含するものとする。したがって、本発明が特許請求の範囲およびその均等物のみによって限定されることが明白に意図される。
【図面の簡単な説明】
【００７２】
【図１】本発明の一実施形態のオブジェクトの同期を示す図である。
【図２】本発明の一実施形態のコンテナオブジェクトに関するサービス情報品質定義を示す図である。
【図３ａ】本発明の一実施形態のコンテナオブジェクトの伝播を示す図である。
【図３ｂ】本発明の一実施形態のコンテナオブジェクトの伝播を示す図である。
【図４】本発明の一実施形態のコンテナオブジェクト要求圧縮を示す流れ図である。
【図５】本発明の一実施形態の方法を示す流れ図である。
【図６】本発明の一実施形態の別の方法を示す流れ図である。
【図１】
2008519372.tif 000007
【図２】
2008519372.tif 000008
【図３ａ】
2008519372.tif 000009
【図３ｂ】
2008519372.tif 000010
【図４】
2008519372.tif 000011
【図５】
2008519372.tif 000012
【図６】
2008519372.tif 000013
【国際調査報告】
2008519372.tif 000014
2008519372.tif 000015