(57)【要約】  データベースに対応するデータが多次元データブロックに編成される多次元データモデルを用いるデータベースを更新するための方法および装置。各データブロックは、当該各データブロックに関連付けられており、かつ、関連付けられたデータブロックの漸進的変化の最新状態に対応する集計情報を有する。データブロック内およびデータブロック間のデータの従属性を識別する従属性情報がデータモデル内に維持される。変更エントリのリストは、データブロックに対して行なわれた変更と、当該変更が行なわれた時間とを識別する。データブロックに変更エントリを適用する要求が受信される。変更エントリはデータブロックに適用され、この適用は、データブロックの従属性リストを生成することを含む。当該従属性リストのデータは、更新されたデータブロックに直接的または間接的に従属する。従属性リスト内のデータブロックは、従属性リスト内のデータブロックを更新するために、従属性更新アルゴリズムに従って処理される。
2008547086.tif 000002
【特許請求の範囲】
【請求項１】
多次元データモデルを用いるデータベース内の多次元データブロックに変更を適用するための変更時アプリケータであって、各データブロックは、複数のデータ要素を含み、前記変更時アプリケータは、
データブロック内の１つ以上のデータ要素を更新する要求を受信するため、
変更情報エントリのリストから変更情報エントリを獲得するため、および、
更新によって影響を受ける前記データ要素に基づき選択される１つ以上の規則に従って、前記データブロック内の前記データ要素を更新するためのコンピュータプログラムコードを含み、前記更新は、前記獲得された変更情報エントリと、前記データブロック内の既存のデータ要素とのみを使用し、それにより、前記変更時アプリケータは、前記更新で利用されるすべてのデータが時間的整合点に存在することを確保する、変更時アプリケータ。
【請求項２】
前記規則は、前記データブロック内の各種類のデータ要素を更新するための表現式を規定する１つ以上の数式を含む、請求項１に記載の変更時アプリケータ。
【請求項３】
前記変更情報エントリは、少なくとも以下の要素、すなわち、前記変更エントリが作成されたときを記述する変更情報エントリ番号と、前記変更情報エントリにより影響を受ける１つ以上のデータ要素の位置と、前記データ要素についての古い値と、前記データ要素についての新規の値とを含む、請求項１または２に記載の変更時アプリケータ。
【請求項４】
前記変更情報エントリは、前記データ要素についての新規の値のベクトルを含み、前記データ要素を更新するための前記コンピュータプログラムコードは、前記ベクトルを用いる１つの演算において前記データブロックのいくつかのデータ要素を更新するためのコンピュータプログラムコードを含む、請求項１から３のいずれかに記載の変更時アプリケータ。
【請求項５】
他の変更時アプリケータにより実施される更新を参照して前記データブロックに前記変更情報エントリをいつ適用すべきかを決定するためのコンピュータプログラムコードをさらに含み、前記決定は、前記データブロック内および前記データブロック間のデータ要素間のデータの従属性を識別する前記データモデル内の従属性構造に関して行なわれる、請求項１から４のいずれかに記載の変更時アプリケータ。
【請求項６】
２つの別個の変更時アプリケータの適用間で前記データブロック内のデータ値をいつ計算すべきかを決定するためのコンピュータプログラムコードをさらに含み、前記決定は、前記データブロック内のデータ要素間のデータの従属性を識別する前記データモデル内の従属性構造と前記変更情報エントリとに関して行なわれる、請求項５に記載の変更時アプリケータ。
【請求項７】
前記データベース内の非多次元データ構造および他のデータブロックからデータを検索するためのコンピュータプログラムコードをさらに含む、請求項１から６のいずれかに記載の変更時アプリケータ。
【請求項８】
１つ以上の変更されていないオペランドについての逆演算を用いる数式を再規定することにより、変更されたオペランドおよび結果に基づき、１つ以上の変更時アプリケータ規則を生成するためのコンピュータプログラムコードをさらに含む、請求項１から７のいずれかに記載の変更時アプリケータ。
【請求項９】
変更情報エントリに格納されるべきデータ値を決定するためのコンピュータプログラム
コードをさらに含み、前記決定は、特定の種類の変更情報エントリについて各変更時アプリケータが必要とするオペランドを識別する前記データモデル内の従属性構造に関して行なわれる、請求項１から８のいずれかに記載の変更時アプリケータ。
【請求項１０】
多次元データモデルを用いるデータベースを更新するためのコンピュータ実施方法であって、前記多次元データモデルにおいて、前記データベースに対応するデータは多次元データブロックに編成されており、各データブロックは、前記各データブロックに関連付けられており、かつ、関連付けられたデータブロックの漸進的変化の最新状態に対応する集計情報を有しており、前記方法は、
前記データモデル内に前記データブロック内および前記データブロック間のデータの従属性を識別する従属性情報を維持することと、
前記データブロックの特定のデータブロックに対して行なわれた変更と、前記変更が行なわれた時間とを識別する変更エントリのリストを維持することと、
データブロックに変更エントリを適用する要求を受信することと、
前記データブロックに前記変更エントリを適用することとを含み、前記適用することは、データブロックの従属性リストを生成することを含み、前記従属性リストのデータは前記更新されたデータブロックに直接的または間接的に従属し、前記方法はさらに、
前記従属性リスト内の前記データブロックを更新するために、従属性更新アルゴリズムに従って前記従属性リスト内の前記データブロックを処理することを含む、コンピュータ実施方法。
【請求項１１】
処理することは、前記データブロックの前記処理が新規の変更エントリを生じる場合に前記従属性リスト内のデータブロックを処理することを含む、請求項１０に記載の方法。
【請求項１２】
各データブロックは１つ以上のデータ要素を含み、処理することは、前記データブロックの前記処理が、疎に集計する特定のデータ要素についての表現式の結果として新規の変更エントリを生成し得る場合に前記従属性リスト内のデータブロックを処理することを含む、請求項１０または１１に記載の方法。
【請求項１３】
各データブロックは１つ以上のデータ要素を含み、処理することは、変更エントリの前記適用が、いずれかの疎に集計する測度についてのいずれかの表現式の評価から外れる新規の変更エントリを生じ得る場合に前記従属性リスト内のデータブロックを処理することを含む、請求項１０または１１に記載の方法。
【請求項１４】
処理することは、前記従属性リスト内の各データブロックを処理することを含む、請求項１０から１３のいずれかに記載の方法。
【請求項１５】
処理することは、前記変更エントリのリストに非一時変更のみを格納することを含む、請求項１０から１４のいずれかに記載の方法。
【請求項１６】
変更情報エントリを維持することは、すべての変更エントリが処理された時点を識別する計算変更リスト番号を維持することを含み、それにより、計算変更リストは、前記従属性リスト内の前記データブロックの最も早い開始点の処理を規定する、請求項１０から１５のいずれかに記載の方法。
【請求項１７】
前記データベースのサブセットに対していくつかの計算変更リスト番号が維持され、サブセットの集合は、前記データモデル上の区画を形成する、請求項１６に記載の方法。
【請求項１８】
適用するステップおよび処理するステップは、同一の演算の一部である、請求項１０から１７のいずれかに記載の方法。
【請求項１９】
処理することは、前記従属性リスト内のデータブロックが照会されるまで、または、変更リストエントリが前記従属性リスト内のデータブロックに適用され得るまで、処理を遅延することを含む、請求項１０から１８のいずれかに記載の方法。
【請求項２０】
処理することは、前記データベース内でユーザの能力により規定されるスコピーング関係に従って前記従属性リスト内の前記データブロックを処理することを含む、請求項１０から１８のいずれかに記載の方法。
【請求項２１】
変更エントリを適用することは、多数の期間にわたって繰返される変更を規定する複合変更エントリを適用することを含む、請求項１０から２０のいずれかに記載の方法。
【請求項２２】
処理することは、前記ブロックを規定する１つ以上の密な次元に沿って多数のデータ要素にわたり繰返される変更を規定する複合変更エントリを適用することを含む、請求項１０から２１のいずれかに記載の方法。
【請求項２３】
変更エントリを適用することは、変更時アプリケータを用いる変更エントリを適用することを含む、請求項１０から２２のいずれかに記載の方法。
【請求項２４】
処理することは、変更時アプリケータを用いる変更エントリを適用することを含む、請求項１０から２２のいずれかに記載の方法。
【請求項２５】
要求を受信することは、導出値を含むように指定されるデータブロックのセルにユーザ入力値を受信することと、
前記ユーザ入力値から生じるどのような制約違反をも、前記制約違反が解消されるまで監視することとを含む、請求項１０から２４のいずれかに記載の方法。
【請求項２６】
処理することは、
前記ユーザ入力値を有する前記セルが１つ以上の他のブロック内に何らかの従属値を有するか否かを判断することと、
前記ユーザ入力値を有する前記セルが別のブロック内に従属値を有するときに、前記１つ以上の他のブロック内の前記従属値を調節する補償導出変更リストエントリを作成することとを含む、請求項２５に記載の方法。
【請求項２７】
処理することは、
前記ユーザ入力値を有する前記セルが、１つ以上の他のブロック内にユーザ入力でありかつ導出される何らかの従属値を有するか否かを判断することと、
データ値が、修正されて両方のユーザ入力導出値に従属するときに、最も内部のユーザ入力導出値にのみ前記補償導出変更リストエントリを割当てることとを含む、請求項２６に記載の方法。
【請求項２８】
処理することは、
前記ユーザ入力値を有する前記セルに従属するすべての値が同一ブロック内に存在するか否かを判断することと、
前記ユーザ入力値を有する前記セルに従属するすべての値が同一ブロック内に存在すると判断されたときに、導出データ値がユーザ入力によって修正されたことを示すために追加のディスク空間を確保することと、
前記ユーザ入力値が導出値により無効にされないことを確保することとを含む、請求項２７に記載の方法。
【請求項２９】
行ソース内の１つ以上のデータ要素とデータブロック内の１つ以上のデータ要素との間にマッピングを行ない、行ソースフォーマットで格納されたデータ要素にアクセスする前記データブロックに計算規則を適用することをさらに含む、請求項１０から２８のいずれかに記載の方法。
【請求項３０】
前記マッピングは、スコピーング、次元マップの指定、および時間的変形の１つ以上を規定する、請求項２９または３０に記載の方法。
【請求項３１】
前記マッピングを用いて、行ソースについての変更リストエントリを、前記行ソースに従属するターゲットキューブについての１つ以上の変更リストエントリに変形することをさらに含み、それにより、前記行ソースに対する変更が前記ターゲットキューブに伝搬され得る、請求項２９に記載の方法。
【請求項３２】
前記マッピングを用いて、行ソース内のデータ値の従属性関係を、キューブ内の従属性関係に変形することをさらに含む、請求項２９から３１のいずれかに記載の方法。
【請求項３３】
第１のキューブ内の１つ以上のデータ要素と第２のキューブ内の１つ以上のデータ要素との間にマッピングを行なうことをさらに含み、前記マッピングは、割振りの演算、変形の演算、および集約の演算の１つ以上を規定する、請求項１０から３２のいずれかに記載の方法。
【請求項３４】
前記マッピングは、スコピーング、次元マップの指定、および時間的変形の１つ以上を規定する、請求項３３に記載の方法。
【請求項３５】
前記マッピングを用いて、前記第１のキューブについての変更リストエントリを、前記第２のキューブについての１つ以上の変更リストエントリに変形することをさらに含み、前記第２のキューブは前記第１のキューブに従属し、それにより、前記第１のキューブ内の前記データ要素に対する変更は、前記第２のキューブ内のデータ要素に伝搬され得る、請求項３３または３４に記載の方法。
【請求項３６】
前記マッピングを用いて、キューブ内のデータ値の従属性関係を、キューブ間のデータ値の従属性関係に変形することをさらに含む、請求項３３または３４に記載の方法。
【請求項３７】
根底に存在するデータベースからのデータを用いる多数のシナリオを稼働させるためのコンピュータ実施方法であって、前記データは、前記データが多次元ブロックに編成される多次元データモデルに従って編成されており、各ブロックは、当該各ブロックに関連付けられており、かつ、関連付けられたブロックの漸進的変化の最新状態に対応する集計情報を有しており、前記データモデルは、前記ブロック内および前記ブロック間のデータの従属性を識別する従属性情報をさらに含み、前記方法は、
第１のシナリオプロセスを稼働させることを含み、前記第１のシナリオプロセスは、前記ブロックのうちの第１のブロックのコピーに対して行なわれた第１の変更と、前記第１の変更が行なわれた時間とを識別する第１の変更情報を維持し、前記第１のシナリオプロセスは、前記第１のブロックの前記コピーの再計算および第１の従属ブロックのコピーを容易にして前記第１の変更を組込み、前記方法はさらに、
前記第１のシナリオプロセスと実質的に同時に第２のシナリオプロセスを稼働させることを含み、前記第２のシナリオプロセスは、前記ブロックのうちの第２のブロックのコピーに対して行なわれた第２の変更と、前記第２の変更が行なわれた時間とを識別する第２の変更情報を維持し、前記第２のシナリオプロセスは、前記第２のブロックの前記コピーの再計算および第２の従属ブロックのコピーを容易にして前記第２の変更を組込み、
前記第１の変更は、前記根底に存在するデータベースにコミットされるまで前記第２の
シナリオプロセスにとって利用可能にならず、前記第２の変更は、前記根底に存在するデータベースにコミットされるまで前記第１のシナリオプロセスにとって利用可能にならず、前記方法はさらに、
前記従属性情報、前記集計情報、および前記第１の変更情報を参照して前記根底に存在するデータベースを更新すること、および、それにより、前記第２のシナリオプロセスにとって前記第１の変更を利用可能にすることを含み、
前記更新することは、前記第２の変更情報を前記第１の変更情報に一致させることを含み、どのような第２のシナリオの変更情報の前にもすべての第１のシナリオの変更情報がデータブロックに適用されたかのように前記第２のシナリオがデータを見ることを確保し、それにより、データの整合性を保持する、コンピュータ実施方法。
【請求項３８】
更新することは、
前記第１の変更および前記第２の変更が前記根底に存在するデータベースにコミットされたシーケンスを求めることと、
前記求められたシーケンスの順序で、
前記データベースに前記変更情報を適用することとを含み、前記適用することは、データ変更の従属性リストを生成することを含み、前記従属性リストのデータは以前に変更されたデータ変更に直接的または間接的に従属しており、前記更新することはさらに、
従属性更新アルゴリズムに従って前記従属性リスト内の前記データ変更を処理して、前記従属性リスト内の前記データ変更を更新することを含む、請求項３７に記載の方法。
【請求項３９】
前記第１および第２のシナリオプロセスは、階層関係に編成されており、前記方法はさらに、
以下の状況、すなわち、子シナリオプロセスが廃棄されるか、もしくは前記データベースにコミットされるときか、変更がシナリオプロセスにコミットされるときか、または、２つのシナリオプロセスの一致が生じるとき、の１つ以上が生じるときに、シナリオプロセスに関連する不要情報ブロックを収集することをさらに含む、請求項３７または３８に記載の方法。
【請求項４０】
子シナリオプロセスは、親シナリオプロセスとの一致が必要とされないときにのみ、前記データベースにコミットされ、
更新することは、前記親シナリオプロセス内のブロックを、前記子シナリオプロセスからの対応するブロックで置換することを含む、請求項３７から３９のいずれかに記載の方法。
【請求項４１】
各シナリオプロセスについて、シナリオプロセスに含まれるブロックに変更が生じるたびに、前記変更により影響を受けないブロックを最新状態まで漸進的に変化させることをさらに含む、請求項３７から４０のいずれかに記載の方法。
【請求項４２】
各ブロックは、ヘッダ部およびデータ部にセグメント化され、漸進的に変化させることは、
前記ブロックの前記データ部が漸進的変化の後も漸進的変化の前と同じままであるか否かを判断することと、
前記データ部が同じままであると判断されたときに、前記ブロックの前記ヘッダ情報のみを最新状態まで漸進的に変化させることとを含む、請求項４１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
この発明は、大きなデータセットを解析するための技術に関し、より特定的には、大きな多次元のデータセットを有する「what if」シナリオを効率よく稼動させるための方法および装置に関する。
【背景技術】
【０００２】
「データ管理ソフトウェア」という用語は、ビジネスデータを操作するための数多くの解決策を包含しており、これらの解決策は、大まかに３つのカテゴリ、すなわち、オンライントランザクション処理（On-Line Transaction Processing（ＯＬＴＰ））、データウェアハウジング、およびオンライン解析処理（On-Line Analytical Processing（ＯＬＡＰ））に編成され得る。これらのカテゴリの各々は、一定の利点および欠点を有しており、これらは上記の出願において論じられている。
【０００３】
手短に説明すると、ＯＬＴＰは一般に、たとえば銀行、航空会社、通信販売、スーパーマーケット、および製造を含む多数の業界におけるデータ入力および検索のトランザクションのためのトランザクション志向のアプリケーションを容易化して管理する一群の解決策に関する。ＯＬＴＰシステムに格納されたデータに即座にアクセスできるようにして高度な応答性を確保することが、当該システムの重要な目標である。また、ロック機構を設けて、たとえば一個人が航空機の座席等のリソースを予約したときに、そのリソースがシステム内の他者によりもはや利用され得ないようにすることを確保することも重要である。したがって、ＯＬＴＰシステムでは、２つ以上の場所にデータを格納することが好まれず、その代わりに、異なるテーブルの共同処理に大いに依存してデータを組合せることを強調している。ＯＬＴＰシステムは、リアルタイムのトランザクション処理には極めて効果的であるが、１ヵ月間に３度以上特定の航空便に搭乗する人をすべて示すこと等の集合クエリを使用する報告機能には、特に適しているわけではない。
【０００４】
データウェアハウジングは、異なるデータスキーマを使用しており、これらのスキーマは、相対的に高度な報告機能をサポートするのに一層適しているが、データの莫大な量の複製が存在し得る。ＯＬＴＰの情況では、この複製が容認され得ない。なぜなら、１つのデータに対する変更が、データウェアハウステーブル内の１つの位置だけではなく、多くの場所において複製されなければならないためである。一方で、データウェアハウジングは報告の観点から有利である。なぜなら、会計四半期ごとの特定の経路に関する乗客量等の特定のビジネスに特に関心が集まり得るクエリに対応する情報を集約する集計テーブルの作成および維持が、データウェアハウジングによって可能になるためである。データウェアハウジングシステムは、静的報告を生成するように高度に最適化されているが、質問が事前に認識されていないデータの解析を効率よくサポートしない。たとえば、販売部長が静的報告を見て、特定の月における特定の製品の全国的販売が予想を下回ることを認識するかもしれない。しかしながら、この報告の静的な特性により、不足の生じた理由が明らかにならないかもしれない。このような状況で、販売部長は、データを掘り下げて、たとえば、説明として作用し得る何らかの識別可能な（たとえば地域的、時間的等の）格差が存在するか否かを判断できればよいと思う。この種の能力は、ＯＬＡＰの分野に含まれる。
【０００５】
ＯＬＡＰシステムは、販売部長が静的報告で識別された格差を説明し得るデータに焦点を絞ることを可能にする、臨機応変な解析といったものを可能にするように、データを編成する。これは、詳細なデータを検索するように高度に最適化されているものの、集計を
出すことが一般には極めて苦手なＯＬＴＰの解決策とは対照的であり得る。ＯＬＡＰの手法は、非実用的な数の集計テーブルを維持してこのような機能性の複製を必要とするデータウェアハウジングの解決策とも対照的であり得る。ＯＬＡＰの解決策に関する重要な問題は、これらの解決策が、（ほぼリアルタイムの更新により特徴づけられるトランザクション処理とは対照的に）バッチ処理に対してのみ、一般に最適化されていることに関連する。ＯＬＡＰシステムの根底に存在するデータ内に極めて相互従属性の高い集計情報が大量に存在しているため、いかなる詳細なデータの更新も、演算上、費用がかさむ傾向にある。なぜなら、一般に、多くの異なるレベルの階層上の多くの異なる集計が無効にされて再計算されなければならないためである。したがって、殆どのＯＬＡＰシステムは一般に、データの対話式更新をサポートするのではなく、バッチ再計算を使用する。少なくとも対話式更新の外観を呈するように、種々の妥協点の獲得を試みるＯＬＡＰの解決策が存在する。たとえば或る解決策は、主メモリに適合するようにデータセットまたは当該データセット上の指標を制限し、その後、検索時にすべてのデータ値を対話式に再計算するものがある。また或る解決策は、スクリプティング技術を使用してバッチ間のデータのサブセットを分離および更新する。残念ながら、これらの手法は、多次元データセットの更新にまつわる効率の悪さを部分的にしか緩和しない。その結果、ＯＬＡＰシステムは、問題の識別および捜出を補助するための、データの臨機応変な照会には効果的であるが、変更を行なうことの影響を理解してこれらの識別された問題に対処するのに必要とされる、臨機応変な更新または「what if」シナリオの解析においては、相対的に効果的ではない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記の特許出願は、多数の技術を記載しており、これらの技術により、大きくかつ複雑なデータセットがより効率よく無効にされて再計算され、変更を反映することができる。大きなデータセットについての集計情報を維持する際に、このようなデータセット内の異なるレベルの階層データについてのデータブロック間の従属性チェックと組合わせて、変更ロギングが使用される。その結果、根底に存在するデータの更新または再計算に必要とされる時間は、殆どのＯＬＡＰの解決策におけるようなデータセットのサイズまたは次元数の関数よりもむしろ、行なわれた変更の数の関数に近づく。さらに、記載するこれらの技術により、根底に存在する同一のデータセットを用いる多数の「what if」シナリオを実質的に同時に稼動させることもできる。異なるユーザがこれらの多数のピアシナリオを並行に稼動させることができる。代替的に、１人のユーザが多数のレベルのシナリオ、すなわち、親シナリオの結果に基づいた子シナリオを有することができる。これらはいずれも、従来のＯＬＡＰの分野では現時点で実行不可能である。ユーザの「what if」シナリオが複雑になるにつれて、従来のＯＬＡＰシステムで可能なものも変更および更新の実施を可能にして深い分析性をサポートする、良く構造化されたシステムの必要性が高まっている。
【課題を解決するための手段】
【０００７】
概要
一般に、一局面において、この発明は、方法およびコンピュータプログラムプロダクトを含む装置を提供し、当該方法および装置は、多次元データモデルを用いるデータベース内の多次元データブロックに変更を適用するための変更時アプリケータを提供するための技術を実現および使用する。各データブロックは、いくつかのデータ要素を含む。変更時アプリケータは、データブロック内の１つ以上のデータ要素を更新する要求を受信するため、変更情報エントリのリストから変更情報エントリを獲得するため、および、更新によって影響を受けるデータ要素に基づき選択される１つ以上の規則に従って、データブロック内のデータ要素を更新するためのコンピュータプログラムコードを含み、当該更新は、獲得された変更情報エントリと、データブロック内の既存のデータ要素とのみを使用し、それにより、変更時アプリケータは、当該更新で利用されるすべてのデータが時間的整合
点に存在することを確保する。
【０００８】
さまざまな実現例は、以下の特徴の１つ以上を含み得る。規則は、データブロック内の各種類のデータ要素を更新するための表現式を規定する１つ以上の数式を含み得る。変更情報エントリは、少なくとも以下の要素、すなわち、変更エントリが作成されたときを記述する変更情報エントリ番号と、当該変更情報エントリにより影響を受ける１つ以上のデータ要素の位置と、当該データ要素についての古い値と、当該データ要素についての新規の値とを含み得る。変更情報エントリは、データ要素についての新規の値のベクトルを含み得、データ要素を更新するためのコンピュータプログラムコードは、当該ベクトルを用いる１つの演算においてデータブロックのいくつかのデータ要素を更新するためのコンピュータプログラムコードを含む。変更時アプリケータは、他の変更時アプリケータにより実施される更新を参照してデータブロックに変更情報エントリをいつ適用すべきかを決定するためのコンピュータプログラムコードを含み得、この決定は、データブロック内およびデータブロック間のデータ要素間のデータの従属性を識別するデータモデル内の従属性構造に関して行なわれる。変更時アプリケータは、２つの別個の変更時アプリケータの適用間でデータブロック内のデータ値をいつ計算すべきかを決定するためのコンピュータプログラムコードを含み得、この決定は、データブロック内のデータ要素間のデータの従属性を識別するデータモデル内の従属性構造と変更情報エントリとに関して行なわれる。変更時アプリケータは、データベース内の非多次元データ構造および他のデータブロックからデータを検索するためのコンピュータプログラムコードを含み得る。変更時アプリケータは、１つ以上の変更されていないオペランドについての逆演算を用いる数式を再規定することにより、変更されたオペランドおよび結果に基づき、１つ以上の変更時アプリケータ規則を生成するためのコンピュータプログラムコードを含み得る。変更時アプリケータは、変更情報エントリに格納されるべきデータ値を決定するためのコンピュータプログラムコードを含み得、この決定は、特定の種類の変更情報エントリについて各変更時アプリケータが必要とするオペランドを識別するデータモデル内の従属性構造に関して行なわれる。
【０００９】
一般に、一局面において、この発明は、方法およびコンピュータプログラムプロダクトを含む装置を提供し、当該方法および装置は、データベースに対応するデータが多次元データブロックに編成される多次元データモデルを用いるデータベースを更新するための技術を実現し、使用する。各データブロックは、当該各データブロックに関連付けられており、かつ、関連付けられたデータブロックの漸進的変化の最新状態に対応する集計情報を有する。従属性情報は、データブロック内およびデータブロック間のデータの従属性を識別するために、データモデル内に維持される。変更エントリのリストが維持され、当該リストは、データブロックの特定のデータブロックに対して行なわれた変更と、当該変更が行なわれた時間とを識別する。データブロックに変更エントリを適用する要求が受信される。変更エントリはデータブロックに適用され、この適用は、データブロックの従属性リストを生成することを含み、この従属性リストのデータは、更新されたデータブロックに直接的または間接的に従属する。この従属性リスト内のデータブロックは、従属性リスト内のデータブロックを更新するために従属性更新アルゴリズムに従って処理される。
【００１０】
さまざまな実現例は、以下の特徴の１つ以上を含み得る。処理は、データブロックの処理が新規の変更エントリを生じる場合に従属性リスト内のデータブロックを処理することを含み得る。各データブロックは１つ以上のデータ要素を含み得、処理は、データブロックの処理が、疎に集計する特定のデータ要素についての表現式の結果として新規の変更エントリを生成し得る場合に従属性リスト内のデータブロックを処理することを含み得る。各データブロックは１つ以上のデータ要素を含み得、処理は、変更エントリの適用が、いずれかの疎に集計する測度についてのいずれかの表現式の評価から外れる新規の変更エントリを生じ得る場合に従属性リスト内のデータブロックを処理することを含み得る。処理
は、従属性リスト内の各データブロックを処理することを含み得る。処理は、変更エントリのリストに非一時変更のみを格納することを含み得る。
【００１１】
変更情報エントリを維持することは、すべての変更エントリが処理された時点を識別する計算変更リスト番号を維持することを含み得、それにより、計算変更リストは、従属性リスト内のデータブロックの最も早い開始点の処理を規定する。データベースのサブセットに対していくつかの計算変更リスト番号が維持され得、サブセットの集合は、データモデル上の区画を形成する。適用および処理は、同一の演算の一部であり得る。処理は、従属性リスト内のデータブロックが照会されるまで、または、変更リストエントリが従属性リスト内のデータブロックに適用され得るまで、処理を遅延することを含み得る。処理は、データベース内でユーザの能力により規定されるスコーピング関係に従って従属性リスト内のデータブロックを処理することを含み得る。変更エントリを適用することは、多数の期間にわたって繰返される変更を規定する複合変更エントリを適用することを含み得る。処理は、ブロックを規定する１つ以上の密な次元に沿って多数のデータ要素にわたり繰返される変更を規定する複合変更エントリを適用することを含み得る。変更エントリの適用は、変更時アプリケータを用いる変更エントリを適用することを含み得る。処理は、変更時アプリケータを用いる変更エントリを適用することを含み得る。
【００１２】
要求の受信は、導出値を含むように指定されるデータブロックのセルにユーザ入力値を受信することと、そのユーザ入力値から生じるどのような制約違反をも、その制約違反が解消されるまで監視することを含み得る。処理は、ユーザ入力値を有するセルが１つ以上の他のブロック内に何らかの従属値を有するか否かを判断することと、ユーザ入力値を有するセルが別のブロック内に従属値を有するときに、１つ以上の他のブロック内の従属値を調節する補償導出変更リストエントリを作成することを含み得る。処理は、ユーザ入力値を有するセルが、１つ以上の他のブロック内にユーザ入力でありかつ導出される何らかの従属値を有するか否かを判断することと、データ値が、修正されて両方のユーザ入力導出値に従属するときに、最も内部のユーザ入力導出値にのみ補償導出変更リストエントリを割当てることを含み得る。処理は、ユーザ入力値を有するセルに従属するすべての値が同一ブロック内に存在するか否かを判断することと、ユーザ入力値を有するセルに従属するすべての値が同一ブロック内に存在すると判断されたときに、導出データ値がユーザ入力によって修正されたことを示すために追加のディスク空間を確保することと、そのユーザ入力値が導出値により無効にされないことを確保することとを含み得る。
【００１３】
マッピングは、行ソースフォーマットで格納されたデータ要素にアクセスして当該データ要素に計算規則を適用するために、行ソース内の１つ以上のデータ要素とデータブロック内の１つ以上のデータ要素との間で行なわれ得る。マッピングは、スコーピング、次元マップの指定、および時間的変形の１つ以上を規定し得る。マッピングは、行ソースについての変更リストエントリを、当該行ソースに従属するターゲットキューブについての１つ以上の変更リストエントリに変形することができ、それにより、行ソースに対する変更がターゲットキューブに伝搬され得る。マッピングは、行ソース内のデータ値の従属性関係を、キューブ内の従属性関係に変形し得る。マッピングは、第１のキューブ内の１つ以上のデータ要素と第２のキューブ内の１つ以上のデータ要素との間で行なわれ得る。マッピングは、割振りの演算、変形の演算、および集約の演算の１つ以上を規定し得る。マッピングは、スコーピング、次元マップの指定、および時間的変形の１つ以上を規定し得る。マッピングは、第１のキューブについての変更リストエントリを、第２のキューブについての１つ以上の変更リストエントリに変形することができ、第２のキューブは第１のキューブに従属し、それにより、第１のキューブ内のデータ要素に対する変更は、第２のキューブ内のデータ要素に伝搬され得る。マッピングは、キューブ内のデータ値の従属性関係を、キューブ間のデータ値の従属性関係に変形することができる。
【００１４】
一般に、一局面において、この発明は、方法およびコンピュータプログラムプロダクトを含む装置を提供し、当該方法および装置は、根底に存在するデータベースからのデータを用いる多数のシナリオを稼動させるための技術を実現し、使用する。データは、当該データが多次元ブロックに編成される多次元データモデルに従って編成される。各ブロックは、当該各ブロックに関連付けられており、かつ、関連付けられたブロックの漸進的変化の最新状態に対応する集計情報を有する。データモデルは、ブロック内およびブロック間のデータの従属性を識別する従属性情報を含む。第１のシナリオプロセスが稼動される。第１のシナリオプロセスは、ブロックのうちの第１のブロックのコピーに対して行なわれた第１の変更と、当該第１の変更が行なわれた時間とを識別する第１の変更情報を維持する。第１のシナリオプロセスは、第１のブロックのコピーの再計算および第１の従属性ブロックのコピーを容易にして第１の変更を組込む。第２のシナリオプロセスは、第１のシナリオプロセスと実質的に同時に稼動される。第２のシナリオプロセスは、ブロックのうちの第２のブロックのコピーに対して行なわれた第２の変更と、当該第２の変更が行なわれた時間とを識別する第２の変更情報を維持する。第２のシナリオプロセスは、第２のブロックのコピーの再計算および第２の従属性ブロックのコピーを容易にして第２の変更を組込む。第１の変更は、根底に存在するデータベースにコミットされるまで第２のシナリオプロセスにとって利用可能にならず、第２の変更は、根底に存在するデータベースにコミットされるまで第１のシナリオプロセスにとって利用可能にならない。根底に存在するデータベースは、従属性情報、集計情報、および第１の変更情報を参照して更新され、それにより、第１の変更は第２のシナリオプロセスにとって利用可能になる。更新は、第２の変更情報を第１の変更情報に一致させることと、どのような第２のシナリオの変更情報の前にもすべての第１のシナリオの変更情報がデータブロックに適用されたかのように第２のシナリオがデータを見ることを確保することと、それにより、データの整合性を保持することとを含む。
【００１５】
さまざまな実現例は、以下の特徴の１つ以上を含み得る。更新することは、第１の変更および第２の変更が根底に存在するデータベースにコミットされるシーケンスを求めることと、求められたシーケンスの順序で、データベースに変更情報を適用することとを含み、この適用は、データ変更の従属性リストを生成することを含み、この従属性リストのデータは以前に変更されたデータ変更に直接的または間接的に従属しており、更新することはさらに、従属性更新アルゴリズムに従って従属性リスト内のデータ変更を処理して、従属性リスト内のデータ変更を更新することを含む。第１および第２のシナリオプロセスは、階層関係に編成され得、以下の状況、すなわち、子シナリオプロセスが廃棄されるか、もしくはデータベースにコミットされるときか、変更がシナリオプロセスにコミットされるときか、または、２つのシナリオプロセスの一致が生じるとき、の１つ以上が生じるときに、シナリオプロセスに関連する不要情報ブロックが収集され得る。子シナリオプロセスは、親シナリオプロセスとの一致が必要とされないときにのみ、データベースにコミットされ得、更新は、親シナリオプロセス内のブロックを、子シナリオプロセスからの対応するブロックで置換することを含み得る。各シナリオプロセスについて、シナリオプロセスに含まれるブロックに変更が生じるたびに、その変更によって影響を受けないブロックは、最新状態まで漸進的に変化させることができる。各ブロックは、ヘッダ部およびデータ部にセグメント化され得、漸進的に変化させることは、ブロックのデータ部が漸進的変化の後も漸進的変化の前と同じままであるか否かを判断することと、データ部が同じままであると判断されたときに、ブロックのヘッダ情報のみを最新状態まで漸進的に変化させることとを含み得る。添付の図面および以下の説明に、この発明の１つ以上の実施例の詳細を明示する。この発明の他の特徴および利点は、説明および図面から、ならびにクレームから明らかになるであろう。
【発明を実施するための最良の形態】
【００１６】
さまざまな図面内の同じ参照符号は、同じ要素を指す。
詳細な説明
次に、発明者らによりこの発明を実施するために企図された最良の態様を含む、この発明の具体的な実施例を詳細に参照する。これらの具体的な実施例の例は、添付の図面に例示される。この発明はこれらの具体的な実施例に関連付けて説明されるが、この説明がこの発明を記載された実施例に限定することが意図されないことを理解されるであろう。その反対に、この説明は、前掲の請求項が規定するこの発明の精神および範囲内に含まれ得る代替例、変更例、および等価例を包含するように意図される。以下の説明では、具体的な詳細を明示して、この発明の完全な理解を図る。この発明は、これらの具体的な詳細の一部またはすべてを用いなくても実施可能である。加えて、この発明を必要以上に不明瞭にすることを避けるため、周知の特徴を詳細に説明しない場合がある。
【００１７】
基本的な概念およびシステムの動作
上記の特許出願は、大きなデータセット内の集計情報の保守において、このようなデータセット内のさまざまなレベルの階層データについてのデータブロック間の従属性チェックと組合わせて変更ロギングを使用するシステムおよび方法について記載している。この手法により、データベース管理システム（ＤＢＭＳ）の解決策が生じ、この解決策では、根底に存在するデータの更新または再計算に必要とされる時間が、殆どのＯＬＡＰの解決策におけるようなデータセットのサイズまたは次元数の関数よりもむしろ、行なわれた変更の数の関数に近いものとなる。この技術は、根底に存在するデータセットがリレーショナルデータモデルに対応するか、または多次元データモデルに対応するかに関わらず、適用可能である。この発明の実施例は、変更および更新を実施するための、良く構造化されたフォーマットを提供し、より複雑な演算の実施を可能にする。その結果、ユーザの中には、この発明のシステムおよび方法により、これまでに可能であったものよりも一層複雑な「what if」シナリオを稼動させることができる者もある。以下の章では、このシステムのいくつかの一般的な特徴およびいくつかの基本的な概念を説明する。これらの特徴のより詳細な説明は、上記の特許出願に見ることができる。
【００１８】
この発明の具体的な一実施例によると、本明細書に記載されるさまざまな技術を容易にするために、多次元キューブにデータを編成する多次元データモデルが使用される。キューブとは、多次元データセットである。キューブ内の各データ要素は、次元化された要素である。次元は、疎にまたは密に読込まれ得、データ要素を参照するために使用される指標の数を規定する。ｎ次元を含むと言われるキューブは、次元化された要素の位置を規定するためにｎ個の指標を使用する。
【００１９】
キューブ内の要素の数は、キューブ内の各次元のカルテシアン（Cartesian）積の基数である。キューブは、当該キューブを規定する次元の数に等しい次元数を有する。各次元はメンバーを含み、次元自体もまたメンバーである。次元内のメンバー（その次元自体も含む）の数は、当該次元の基数を規定する。キューブ内のデータ要素の数は、キューブ内の各次元の基数の積である。疎に読込まれた次元または「キー」次元は、キーとして用いられ、密に読込まれた次元または「ブロック」次元内の値のセットを指標付けする。このようなキューブのサブセットを、本明細では「ブロック」と呼ぶ。この発明の一実施例において、ブロックは、システムの計算単位を形成し、すなわち、共に計算される多次元データセットの最小サブセットを形成する。これらのブロックは、入力／出力（Ｉ／Ｏ）単位も形成する。以下に論じるように、ブロック内のすべてのデータが共に演算されるため、中央値の計算等の複雑な演算がブロック内で実施され得るようになる。ブロックを演算単位として使用する別の興味深い結果とは、ブロック内のデータ値が当該ブロック内に存在する他のデータ値から導出され得る場合、そのデータ値を格納する必要がない点であり、それによってシステムは、より効率よく作動し得る。
【００２０】
上で述べたように、この発明で使用される多次元データモデルは、根底に存在するデー
タセットに直接的または間接的に対応し得る。すなわち、根底に存在するデータセットは、上記のデータモデルに対応する多次元データベースに格納され得る。代替的に、根底に存在するデータセットは、異なる多次元モデルに対応する多次元データベースに格納され得るか、または、さまざまなモデルのいずれかに対応するリレーショナルデータベースとしても格納され得る。このような場合、根底に存在するデータベースは、本明細書に記載する技術を容易にするのに適した多次元データモデルにマッピングされる。これらのマッピングについては、以下の別の章でさらに詳細に説明する。
【００２１】
本明細書に記載するシステムおよび方法は、データセルに対して行なわれた修正の経過をたどるために変更リストを使用する。データセルに対する各修正により、変更リストエントリ（ＣＬＥ）が作成される。したがって、「最初」からのＣＬＥをブロックに適用することにより、そのブロックの最新バージョンを生じる。ディスク上のインスタンス化されたブロックは、そのブロックについての時点を本質的に表わす、関連付けられたＣＬＥを有する。ブロックの最新バージョンを得るために、その時点と現在との間のすべてのＣＬＥが適用される。
【００２２】
変更リストおよびその演算の概念をさらに論じる前に、「サンドボックス」の概念を再導入することが有用であり得る。サンドボックスはシナリオとも呼ばれ、このシナリオにおいて、ユーザは「what if」解析を実施する。サンドボックスの概念は、ブロックの更新と、異なるシナリオ内の同一ブロックに対する更新とに対するサポートを生じ、これらは時として並行に稼動される。一般に、ベースシナリオまたはベースサンドボックスと、当該ベースサンドボックスから分岐する子サンドボックスの階層とが存在する。特定のサンドボックスに対して行なわれる更新は、階層内での他のサンドボックスの関係に依存して、当該他のサンドボックスにおいて反映されることもあれば、反映されないこともある。ブロックおよびサンドボックスを更新するための一般的な規則は、上記の特許出願において広範囲に論じられているため、本明細書では論じない。しかしながら「サンドボックスの分離」に関連するいくつかの特別な場合について、以下に論じる。一般に、サンドボックスの分離は、ユーザが他のユーザにより並行に行なわれている変更から分離された変更を行なうことができるサンドボックスを設ける概念を指し、したがって、各ユーザは、他のユーザが当該他のユーザ自身の別個の「世界」内で根底に存在するデータセットを同時に変更していることが考えられる場合でも、自分自身の「世界」内で作業することができ、かつ、根底に存在するデータセットに自分自身の変更がどのような影響を及ぼすかを調べることができる。
【００２３】
次に、変更リストエントリの概念に戻ると、この発明の具体的な一実施例によれば、ＣＬＥは、影響を受けたセルの座標、サンドボックス識別子（ＩＤ）、変更番号、親のサンドボックスＩＤ、親のサンドボックス変更番号、新規の値、および以前に計算した値からのデルタを含む。最新の変更リスト番号（ＣＬＮ）は、各サンドボックスと共に格納される。ＣＬＮは、単調増加する番号であり、サンドボックス内のブロック内のセルに変更が行なわれるたびにインクリメントされる。各ブロックは、サンドボックスに対して計算されたサンドボックスのＩＤと、そのときのＣＬＮとを含む。サンドボックス内において、変更リストエントリのナンバリングは、シーケンス番号を用いた単純かつインクリメンタルなナンバリングである。本来の根底に存在するデータベースは、サンドボックス０として指定される。
【００２４】
ＣＬＥを作成する際に、最新のサンドボックスＣＬＮがインクリメントされ、この番号に対する新規のエントリが作成され、最新の親サンドボックスＣＬＮがそれに関連付けられる。親ＣＬＮを関連付けることは、あらゆる先祖をトラバースすることと、各親サンドボックスについて、最新のサンドボックスにどのような変更の適用が必要であるかを決定することとを容易にする。代替的に、サンドボックスＣＬＮの各々は、そのブロック自体
に格納され得る。一実施例において、すべてのサンドボックス変更リストは、システム内で生じるすべての活動のリストである「マスター変更リスト」内に配置される。
【００２５】
ＣＬＥが作成されると、新規のデータ値が常に格納される。以前のデータ値からの差異（デルタ値とも呼ばれる）は、それが合計値または集約経路値であるときに格納される。このことは、データ値がブロックの次元に沿ったリーフレベル値であり、かつ、キー次元に沿ったその集合演算子として合計またはカウントを有するときに生じる（しかしながら、集合演算子が合計またはカウントに限定されないことに注意されたい）。ＣＬＥが作成された後、従属するＣＬＥのすべてに対してデルタ値が調節される。このことは、フィルタリングによって行なわれ得る。なぜなら、デルタ値のセットを有する変更リストエントリが、対応するサンドボックスか、またはその子孫のためのものであり、メンバーが、このメンバーを従属物として有するためである。
【００２６】
この発明の実施例により、同一キューブ内のメンバー間、および、異なるキューブ間のメンバー間で従属性が規定され得る。したがって、ブロックがメモリから検索されると、データモデル内で固有の従属性構造を参照して、かつ、変更リストを参照して、別のキューブ内の値の変更がこのブロック内のいずれかの値に影響を及ぼすか否かを判断することができる。加えて、従属性構造および変更リストは、或るキューブから別のキューブへの変更情報の変形を容易にするための必要な情報を提供し、それにより、従属性に応じて変更が適用され得る。変形および変更情報の適用については別の章で以下により詳細に論じる。当該変形および適用は、根底に存在するデータソースがリレーショナルであるか、多次元であるかに関係なく行なわれ得る。
【００２７】
上で論じた概念および演算の殆どは、上記の特許出願に開示されている。しかしながら、これらの概念は、ブロック間の解析演算が合計またはカウント等の集約演算である環境に対し、最も良好に適用される。このような演算は、複雑な要素、たとえば適用の順序、変更されたデータ値以外の他のデータ値もしくはターゲットブロック内の他のデータ値、または、データに従属する条件付き演算に対して注意を払うことを要しない。当業者が認識するように、このような要素は、高度なデータ解析において生じ、このような解析をブロック境界間の演算に拡張する際に価値を有する。このような状況では、変更間でデータの整合性を確保するために、特別な注意を払わなければならない。
【００２８】
このような状況の１つが、加重和の場合のように、多数の引数が含まれる場合である。たとえば、ドルで表わされる製品ラインのコストは、当該製品ライン内の各種類の物品を調べ、特定の種類の物品の数にその種類の物品についての単価を乗算し、すべての乗算が終了したときに個々の結果を加算することにより、計算され得る。物品の数が何らかの所定の物品の種類に関して変更するたびに、または、１つ以上の物品の種類に関して単価が変化するたびに、このことは製品ラインのコストに変更を生じる。したがってシステムは、このような変更に対処する能力を有していなければならない。この発明の一実施例において、この能力は、変更時アプリケータと呼ばれる複数のプログラムコードにより管理される。この変更時アプリケータについては、より詳細に以下に説明する。
【００２９】
変更時アプリケータ
この発明の一実施例において、ブロックに対する変更は、変更時アプリケータにより適用される。この変更時アプリケータは、所定の変更をブロックにどのように適用すべきかについての式を指定する複数のプログラムコードとして特徴付けられ得る。データ値が、他のデータ値を計算するために使用される多くの異なる式におけるオペランドとして出現し得るのと同様に、所定の種類のＣＬＥに関連付けられた多くの変更時アプリケータが存在し得る。変更を適用するために使用するプログラムコードから、ＣＬＥ内に含まれるデータを切り離すことは、ＣＬＥの数および種類を劇的に減らすことと認識され得る。
【００３０】
一般に、変更時アプリケータの目的は、他のブロックからではなく、そのブロック自体に含まれるデータと、処理されているＣＬＥとを用いてブロックに更新を行なうことである。それにより、変更時アプリケータは、利用されるすべてのデータが、当該変更が本来行なわれた時点に存在するものであって、それよりも早い何らかの時点または遅い時点に存在するものではないことを確保する。これにより、一連の計算が、連続する変更の適用により行なわれ得るようにし、ここでは、適用の順序が保存されて、まるですべてのシステムが無効にされ、各変更を用いて再計算されたかのように同じデータ値を生じる。変更アプリケータが他のブロックのデータを直接参照するならば、それらのブロックは、ブロックが修正されている時点から他の時点に存在することが考えられ、順序の不整合を生じる。
【００３１】
変更時の属性を含む多数の例示的なシナリオについて以下に論じる。第１のシナリオは、測度ｘが次元ｓ１に沿って集計する（すなわち、x = sum（children(x)））という単純な場合に関する。以下のような変更時の表現式は、ｘが変化するときに何がなされるべきかを規定する。
【００３２】
【数１】
2008547086.tif 000003
【００３３】
この例は、データソースおよびターゲットを逆参照し、かつ、ログエントリの一部に到達するためのマクロを導入する。上記の例により例示された変更時アプリケータが、このような合計またはカウント等の集約の演算をサポートするために使用され得ることが認識される。
【００３４】
第２のシナリオは、先に述べた加重和の状況を導入する。ここで、需要キューブは、製品ラインに沿って集約され、かつ、物品の需要および単価の積として演算される製品コストを含む。当業者は、物品の需要および単価の両方が経時的に変化し得ること、変更の適用順序が保持されなければならないこと、ならびに、各変更が処理されるのに伴い、変更されないオペランドの値が、変更されたオペランドに変更が行なわれた時間において利用可能にならなければならないことを認識するであろう。式に従い、このことは、以下の表１に示すように表現され得る。
【００３５】
【表１】
2008547086.tif 000004
【００３６】
認識できるように、一般には、１つのオペランドにつき、１つの変更時表現式が必要とされる。
【００３７】
上のシナリオにおいて、ＣＬＥは、変更されているデータについての古い値および新規の値だけではなく、他のオペランドの変更時の値も含んでいなければならない。このことは、システムの初期化の際にメンバーについてのすべての変更時アプリケータを調べることと、変更された値自体とともにＣＬＥ内に格納されるべき値のリストに対し、他のすべての「ソース」オペランドを加算することとにより、行なわれる。このことは、システムを後に修正して式または変更時アプリケータを調節する場合に、変更リストが最初に完全に処理されるか、または、システムがバッチ計算機構を用いて計算されなければならないことをさらに示唆する。上記のアプリケータにより、修正された製品ブロックに直接的または間接的に従属するあらゆる製品グループ化ブロックは、他のデータを何ら参照することなく、その以前の値および変更のみに基づき、直接、漸進的に変化し得る。
【００３８】
上記の例では、単価および物品の数がいずれも同一キューブ内に格納されることが想定される。しかしながら、一実施例では、変更時アプリケータもまた、データ検索と、別個のキューブまたは他の非多次元構造内に位置するデータに対する操作とをサポートする。このような場合、システムは、ＣＬＥの生成とその適用との間に遠隔データが修正されないことを確保する。
【００３９】
第３のシナリオは、外部データを用いる、より複雑な割振りのシナリオである。ここで、需要キューブは、完成品に対する総予測需要量（ｐｄ）を含む。この予測需要量は、製造スケジュールキューブ内の製造場所間で割振られる。この割振りの比率は、行ソース（ｒｓ）として公知の第３の演算ユニットから抽出され、ここでデータは、多次元交差における値としてではなく、リレーショナルタプルとしてモデル化される。式により、このことは、以下の表２に示すように表現され得る。
【００４０】
【表２】
2008547086.tif 000005
【００４１】
必要とされるマッピング論理は、この文書の後の章で説明する。上記のシナリオの興味深い局面とは、変更時適用論理を処理する際に使用される第２の引数が、ブロック内で既に利用可能な他のオペランドおよびＣＬＥを用いて再演算され得る点である。この再演算により、ＣＬＥ内に収集および格納されなければならない内容が減じられ、この再演算は、特定のプログラム論理についての逆演算を識別することにより自動化され得る。上記のシナリオにおいて、たとえば乗算は、除算により反転される。プログラム論理のフラグメントに対して指定されるこのような逆演算により、オペランドは、結果および他のオペランドに関して書換えられ得、それにより、当業者にとって親しみ深いピープホール最適化技術を利用する変更時アプリケータにおいて置換され得る。さらに、測度の定義で利用されるすべての演算が、公知のまたは指定された逆演算を有する場合、変更時アプリケータ自体は、本来の測度の定義式のピープホール最適化書換えの適用により、生成され得る。
【００４２】
一実施例において、変更時プログラムの呼出は、ログエントリ変数により管理され、ア
プリケータはマップに格納され、ソース測度により調整される。ソース測度とアプリケータとの間に１対多関係が存在することに注目されたい。変更アプリケータの呼出の擬似コードを以下の表３に示す。
【００４３】
【表３】
2008547086.tif 000006
【００４４】
アプリケータプログラムは、ターゲット測度によりセグメント化され、これにより、１つのソース測度の関数であるいくつかのターゲット測度をサポートすることが可能になる。プログラムルックアップキーがソース測度でなければならないため、１つのログエントリに対していくつかのアプリケータプログラムが存在し得る。
【００４５】
第４のシナリオは、いくつかのアプリケータプログラムが１つのログエントリに対して存在する、従属変更時変数の順序付けに関連する。ログ変数ｘおよびａを考えられたい。ここでｘは、ａおよびｑの関数であり、すなわち、ｘ＝ｆ（ａ,ｑ）であり、ａはｑの関数であり、ｑは変更時変数であり、すなわち、ａ＝ｆ（ｑ）である。このような状況において、変更時アプリケータプログラムは、適切な順序で適用されなければならない。一実施例において、変更時アプリケータプログラムの適用順序は、従属性構造を参照することによって維持される。具体的には、ａはｘよりも前に評価されなければならない。なぜなら、ｘがｑだけでなく、ａの関数でもあるためである。このような順序付けは、変更時アプリケータの定義の再帰的な走査に基づき、部分的な順序付けを用いる変更時アプリケータを列挙することにより、システムの初期化時に確立され得る。
【００４６】
関連するシナリオは、以下の通り、すなわち、ｘ＝ｆ（ｚ,ｑ）である。ここで、ｚはブロック計算時に演算される式の測度であり、ｑは変更時の測度である。このことは問題を呈する。なぜなら、ブロック計算機が呼出されるまでｚの値が認識されないためである。したがって、この種のシナリオをサポートするために、ブロック計算は、ログ適用のプロセスにスプライシングされる必要がある。
【００４７】
上記のシナリオは、ブロック内のデータにアクセスするか、他のブロック内のデータにアクセスして、更新されている測度にそのデータをマッピングするか、または、リレーショナルデータベース内の行ソース等の外部ソースからデータにアクセスすることにより、ブロックに更新が行なわれるときに変更時アプリケータをどのように使用してブロック内の測度を計算し得るかを示す。変更リストは、異なるブロック、キューブ、または行ソース内に存在し得る、相互に従属するデータ値のための通信機構である。
【００４８】
いくつかのキューブ間の演算において、測度の定義は変更時の属性を含み、この変更時の属性は、集計についての表現式を指定する。これによりキューブは、２つのキューブのサブセットのみが互いにマッピングされなければならない状態で、その階層上の集約構造が異なっていることが可能とされる。このような場合、基本式は、集約に使用されるデータソースを識別し、一方、オペランド式は、オペランドに対する変更が生じるときに取るべき動作を規定する。以下の表４は、変更時の表現式を有する測度がどのように見え得るかを例示し、スケジュールキューブに対する予測需要量（ＰＤ）の測度の定義を示す。
【００４９】
【表４】
2008547086.tif 000007
【００５０】
表４において分かるように、変更時の属性は、１つ以上の次元を指定し得る。多次元の場合、このことは、集計が各次元に沿って同一の態様で評価されることを意味する。さらに、データソース情報が変更時の表現式から推論され得るため、メンバーの定義において従属性の構造を指定する必要がない。このような場合、初期のユーザ変更エントリをシステム生成変更エントリに添付して、集計を行なう次元に沿ってその変更をさらに伝搬させなければならない。
【００５１】
これによる副次的作用の１つが、１つの変更の適用により、連鎖的な変更の生成および適用を生じ得る点である。変更ログがＤＢＭＳ内のデータの整合性についての根拠であるため、これらの連鎖的な変更に従属するいずれかの値が照会され得る前に、カスケードが生じなければならない。タッチリスト（TouchList）は、この整合性を強化するデータ構造であり、さらに詳細に以下に論じる。
【００５２】
タッチリストおよび関連する概念
上で論じたように、１つの変更が、すべて連鎖した変更を生じ得る状況が存在する。たとえば、部品の在庫が時間と共に定期的に変化することを想定されたい。時間Ｔにおける期首在庫は、時間Ｔ−１における期末在庫に等しく、時間Ｔ−１における期首在庫に搬入を加算して需要を差引いたものにも等しい。同様に、時間Ｔ＋１における期首在庫は、時間Ｔにおける期末在庫に等しいか、または、違った表現をすると、時間Ｔにおける期首在庫に搬入を加算して需要を差引いたものに等しい。ここで、たとえば時間Ｔ−１において需要が変化した場合、このことは、時間Ｔ、Ｔ＋１、Ｔ＋２等における今後の期首在庫および期末在庫の値のすべてに影響を及ぼす。仮に、サービス需要にとって不適切である場合に在庫を負で表現することが許されない場合、時間Ｔ＋１７における利用可能な在庫を求めるためには、Ｔ−１からＴ＋１６までのすべての変更を適用しなければならず、どのステップも飛ばすことができない。各時間Ｔについての値が異なる演算ユニットまたはブロックに保持されている場合、変更リストを利用してこれらのブロック間で変更を伝えなければならず、これらの変更は、従属性の順序でカスケードしなければならない。一実施例において、このことを確保する態様が、タッチリストの機構を介した態様である。
【００５３】
ＣＬＥが生成されるときに、変更記録の適用がさらに別の変更エントリの生成を生じる場合、そのエントリについてのブロックキーがタッチリストに追加される。最初のリスト上のエントリが「タッチ」されると、それらのエントリは、変更リストの適用およびブロックの計算により現時点まで計算され、それら自体の変更エントリを生成し、これらの変更エントリが次いで、ブロックキーのタッチリストへの追加を必要とし得る。このプロセスは、エントリが生成されなくなるまで繰返し継続する。
【００５４】
タッチングアルゴリズムは、さまざまな効率度を有する、整合した結果を生じ得る。その範囲の一方端に存在するものが、すべての従属性の経路に沿って各ブロックを訪問する「スレッジハンマーアルゴリズム」の手法であり、他方端に存在するものが、所定の変更が適用されるべき場合に何が変化するかについての知識に基づいて、ブロックのより小さなセットを訪問するアルゴリズムである。この分類の４つの例示的な実現例は以下の通りである（保守的傾向の最も低い手法から保守的傾向の最も高い手法へと並べている）。第１の実現例は、変更エントリの適用が新規の変更エントリを生じる場合にブロックにタッチすることを含む。第２の実現例は、変更エントリの適用が、疎に集計する特定の測度についての表現式の評価から外れる新規の変更エントリを生じ得る場合にブロックにタッチすることを含む。第３の実現例は、変更エントリの適用が、いずれかの疎に集計する測度についてのいずれかの表現式の評価から外れる新規の変更エントリを生じ得る場合にタッチすることを含む。第４の実現例は、従属性の経路に沿ってあらゆるブロックにタッチすることを含む。
【００５５】
ブロックにタッチするという概念は、上記の特許出願に説明されている。簡潔に述べると、この発想は、ブロックＣＬＮがサンドボックスＣＬＮ未満であるか否かをチェックすることである。未満である場合、ブロックに適用されなければならないＣＬＥが存在し得る。すると、適用可能なリストＣＬＥを求めてデータベースが探索され、その後、これらのＣＬＥがブロックに適用される。その後、ブロックＣＬＮをサンドボックスＣＬＮまで進展させる。
【００５６】
当業者が認識するように、大きなデータセットに対しては、多数のタッチリストのエントリが存在し得る。この発明に従ったＤＢＭＳが変更の数に比例する時間内で稼動するため、システム変更の数を減らすことが望ましい。システム変更を減らす１つの方法は、適切なタッチングアルゴリズムを選択することに関して上で説明した。変更の数を減らすための別の技術は、一時変更の概念に関連する。ユーザがブロックの変更を要求し、ＤＢＭＳが当該要求により（直接的または間接的に）影響を受けるすべてのブロックにタッチする場合は、それらの変更を格納する必要がない。なぜなら、その特定の要求により影響を受ける変数のすべてが変更されているためである。
【００５７】
変更の数を減らす別の方法は、計算変更リスト番号（Ｃａｌｃ  ＣＬＮ）をどのように進展させるかに関連する。上記の出願で説明したように、特定のキューブについてのＣａｌｃ  ＣＬＮは、そのサンドボックス内のすべてのブロックに適用されたことが保証される変更リスト番号をいつでも反映する。換言すると、そのサンドボックス内のすべてのブロックは、そのサンドボックスのＣａｌｃ  ＣＬＮまでは少なくとも「最新」である。サンドボックスに固有のＣａｌｃ  ＣＬＮは、さらにセグメント化されて、解析モデル内の各キューブに固有のＣＬＮのセットとなり得る。ブロックに対して後に変更が行なわれ、特定のキューブに関するサンドボックス内のどのようなブロックに対してもさらに別の変更が生じないことをシステムが確認すると、そのキューブに関するそのサンドボックスのＣａｌｃ  ＣＬＮを進展させる。より多くの最新のＣａｌｃ  ＣＬＮを有することにより、より高速のタッチングプロセスを生じる。なぜなら、タッチング中に適用されなければならないＣＬＥが少なくなるためである。
【００５８】
システムの効率を上げるさらに別の方法は、変更の生成を遅らせることである。データの整合性は、すべての変更が生成されてから、これらの変更に従属し得る値が変更リストに問合せることを求める。この問合せは、従属する変更のすべてが、同じユーザの演算の一部としてタッチリストを空にすることによる最初の一組の変更を生成するユーザの演算の一部として生成されることにより、強く制約され得る。この場合、ユーザの演算の後、すべてのエントリが生成されたという保証の下で、いずれかのブロックに照会が行なわれ得る。また、この問合せは、特定のブロックが直接的または間接的に従属する、従属する変更のすべてが生成されてから、そのブロックが計算されることを確保することにより、弱く制約され得る。これは、ブロックに照会する際に、タッチリストに問合せてから変更リストの適用を行なうこと、および、タッチリスト上のエントリと照会されているブロックとの間に従属性関係が存在しなくなるまでリスト上のエントリを処理することによって行なわれ得る。このことは、影響を受けたブロックの一部のみがさらに別の解析の一部として照会されるときに、強い制約よりも効率がよいことが考えられる。強い制約と弱い制約との間のあらゆる条件を適宜使用することができる。
【００５９】
実施例によっては、スコーピングにより、時間の節約をさらに行なうことができる。たとえば、ユーザが在庫の解析を行ない、在庫に関するデータしか見ることができないものと想定されたい。このような状況において、ユーザは、たとえば会計データにアクセスする（または配慮する）ことができない。したがって、システム内のユーザの能力の外側限界が事前に公知であるため、根底に存在するデータセットの更新を、これらの外側限界内に限定して、処理時間を節約することができる。一実施例では、この解析のデータ範囲を規定する「解析の種類」を有する解析に対して使用される、関連付けられたサンドボックスにより、このスコーピングの関係が作成される。
【００６０】
この発明の一実施例は、複合エントリの概念をサポートする。複合エントリは、上記の変化する在庫の例を参照すると最も良く説明できる。論じたように、特定の時間における需要の変更に対する変更は、以降の時間における今後の期首在庫および期末在庫の値すべ
てに影響を及ぼす。加えて、需要の変更は、他のブロックに対する連鎖的な変更を生じ得、たとえば、その部品を使用するサブアセンブリまたは製品、配送時間等が変化し得る。これらの連鎖的な変更のすべては、個々の変更として生じ得る。しかしながら、処理時間が変更の数に比例するため、このことは一般に勧められない。むしろ、この発明のシステムは、複合変更の使用をサポートし、この複合変更の使用は、ベクトル数学に類似する。すなわち、一部に対してのみ従属性が存在するものの、変更が多数の期間にわたって繰返される。その結果、いくつかの変更リストエントリを追加して、それらの各々について従属性の解析を行なわなければならない代わりに、従属性の解析が必要とされる１つのエントリのみが追加される。一実施例において、変更時アプリケータプログラムは、ベクトルをサポートすることができ、それにより、多数の値がブロック間で転送され得るようにし、かつ、１つの演算内のターゲット測度に適用され得るようにする。これにより、変更に従属しない多くのブロックに関する変更リストの、より一層効率のよい処理と、当該変更に従属するブロックに対するより効率のよい適用との両方が生じる。
【００６１】
上位入力
一実施例において、この発明のシステムは、導出値を一般に含むセル、たとえば上位セルにユーザが値を入力することを可能にする。したがって、ユーザは、計算値の値を、その従属物の計算の結果以外のものに設定することができる。このことは、導出値を演算する際に使用する入力値を変更する前に、目標から導出された値を設定することにより、トップダウン割振り等の演算に対するサポートを可能にする。一実施例において、この特徴は、通常は導出されるものの、ユーザの入力値により無効にされ得るセルに対し、何らかの余分なディスク空間を取っておくことにより可能になる。
【００６２】
また、このシステムは、ユーザによる導出値の変更に応答して生じるあらゆる制約違反を監視する。たとえば、企業が１月中に或る製品を１０個、２月に１０個、そして３月に１０個を生産することが期待されているものと想定されたい。したがって、第１四半期における総生産は一般に、各月の生産個数の合計、すなわち３０個に等しい導出値である。ユーザがこの第１四半期に対する総生産量を５０個に変更した場合、２０個の差異が生じ、このことは制約違反を招き、オペランドは合計を行なわない。この変更は、この制約違反と共に維持されなければならない。ユーザがオペランド値の１つを変更し、たとえば、１月の値を１５に変更し、２月の値を１５に変更して第１四半期に対する実際の合計を４０個にすると、この差異は、制約違反を２０個ではなく１０個にする。その後、３月の値が２０に変更されると差異は０となり、制約違反が対処済みとなる。当業者が注目するように、この期間全体において、年間値についての値は、第１四半期の値に対する変更により指定される２０個により調節されるべきであったが、この制約違反が解消されるまでは、以降の演算における１月、２月、または３月に対する変更によってさらに調節される必要がない。
【００６３】
この発明の一実施例は、「純変化」をさらに含む、ユーザが指定したこのような導出値についてのＣＬＥの導出されたカテゴリか、または、ユーザが指定したターゲット値とオペランド内の値との間に残存する誤差をサポートする。以降のＣＬＥが作成されるのに伴い、これらのＣＬＥは、導出されたエントリが当該ＣＬＥに対して従属性を有するか否かを判断するために検査される。従属性を有する場合、補償導出ＣＬＥが作成される。この補償導出ＣＬＥは、上で論じた変更時機構を用いて、根底に存在する計算により影響を受けた量の分だけ純変化を調節し、同じ量だけデルタ量をデクリメントし、それにより、他の従属値が影響を受けないようにする。
【００６４】
多数の導出値の変更を行なうこともでき、これらの導出値の変更の１つは、次の導出値の変更に従属する。たとえば、ユーザが第１四半期に加え、年間値を修正した場合にこのことが生じ得る。この場合、１月の値に対する変更は、第１四半期の変更に対する変更に
よって補償されるべきであるが、年間値に影響を及ぼすべきではない。なぜなら、四半期の数の誤差が、その補償分を吸収するためである。しかしながら、４月の数に対する変更は、年間値に直接影響を及ぼすはずである。この発明の一実施例では、導出されたアクティブなＣＬＥが、従属性の階層に維持される。以降のＣＬＥが作成されて、導出されたＣＬＥに照らして検査されると、当該以降のＣＬＥはまず、階層の根に照らして検査される。従属性が見つかると、これらのＣＬＥはさらに、親から導出されたＣＬＥが従属する導出ＣＬＥに照らして繰返し検査される。従属する子が存在しない、階層内の最下位の要素に対して補償が行なわれる。
【００６５】
これまでに、ブロック内のデータ値が同一ブロック内に存在する他のデータ値から完全に演算される場合に、そのデータ値を格納する必要がないことに注目してきた。一実施例において、この特徴は、通常は導出されるものの、ユーザが指定した値を示すビットマップを利用するユーザ入力値によって無効にされ得、かつ、計算によって無効にされるべきではないセルに対して何らかの余分なディスク空間を取っておくことにより可能になる。加えて、このような値は、導出されたＣＬＥを上記の態様で生成しない。なぜなら、同一ブロック内のその引数から式を再計算し、結果のデータ値と格納されたデータ値とを比較することによって純デルタが常に演算され得るためであり、それによりシステムは、より効率よく作動し得る。
【００６６】
マッピング
上で論じたように、さまざまな理由から、たとえば異なるフォーマット（キューブ、行ソース等）で異なる種類のデータを維持することが有利である。なぜなら、異なるデータは異なる次元数を有するためである。データが多次元のキューブフォーマットよりもリレーショナルフォーマットでより効率よく格納されるとき、または、データが本質的にリレーショナルなものである場合、行ソースに特に関心が集まる。たとえば単価は、一般に、それほど頻繁に変化しないため、上記のように時間の次元に沿って各期間に単価の値を複製すると、効率が悪くなる。
【００６７】
一実施例において、この発明のシステムは、リレーショナルデータベース等の行ソースとキューブとの間にマッピングを設け、それにより、行ソースまたは表データがキューブの計算中に参照され得るようにする。このようなマッピングは、集約、すなわち、次元が壊される場合と、割振り、すなわち、次元が拡張される場合とを含む演算において特に重要である。たとえば、販売データが製品ラインに対してドル単位で、および、地理的領域ごとに格納され、ユーザがその地理的領域に関係なく、製品ラインの各製品についての製品あたりの個数としてデータを見たいと望む状況が存在し得る。この場合、いくつかの変換が行なわれなければならない。まず、製品ラインが製品に変換され、すなわち、割振りの演算が行なわれなければならず、これは、たとえば、製品ラインにおける各製品についての製品比を用いることにより行なわれ得る。この製品比は一般に、キューブ履歴データから得ることができる。次に、ドル単位の貨幣価値を個数に変換しなければならず、これは、たとえば、リレーショナルデータベーステーブル等の行ソース内の平均小売価格（ＡＳＰ）を調べることにより行なわれ得る。これは、変形の演算の一例である。最後に、そのデータが地理的領域へとそれ以上細分されないように、地理的情報を破壊しなければならない。これは、集約の演算の一例である。これらの変換のすべては、以下にさらに詳細に説明するように、キューブ間、またはキューブと行ソースとの間にマッピングを設けることによって実現され得る。
【００６８】
マッピングは、マッピングされているソース領域およびターゲット領域のサブセットを規定しなければならない。たとえば、或るキューブから別のキューブにマッピングする際に、各次元に沿った適用可能性の範囲を指定しなければならない。加えて、その範囲内の各次元のメンバーが、ターゲット内の１つ以上の次元に沿った１つ以上のメンバーにマッ
ピングされなければならない。マッピングが１対１でない場合、割振りまたは集約の情報が指定されなければならない。
【００６９】
マッピングが規定された状態で、異なる次元数を有する多次元要素またはリレーショナルで多次元の要素等の非類似データ間において、従属性の解析が行なわれ得る。マッピングにより従属性の解析および変更の適用を行なうための２つの例示的な実現例は、以下の通りである。第１の実現例は、マッピングを適用してＣＬＥをソースマッピングからターゲット上のエントリの対応するセットに変形すること、次に、１つのキューブモデルの場合と同様に、ターゲットエントリの各々に対し、従属性の解析を適用することを含む。第２の実現例は、ソースの次元からターゲットの次元に従属性の構造を直接生成し、それにより、従属性の解析が、マッピングなしでもＣＬＥに対して直接行なわれ得るようにすること、および、従属性の関係が確立される場合にのみ、変更リストのアプリケータを実行する前にマッピングを行なうことを含む。従属性の関係は、たとえ２つの値がマッピングされた領域の範囲内に存在しない場合でも、たとえば、ターゲット値がマッピングされたターゲット領域内の値から集計されるか、または、ソース値がマッピングされたソース領域内の値に集計される場合でも、従属性の関係が当該２つの値間に存在し得ることに注目されたい。
【００７０】
上記の例は、マッピングが有用な、単なる一例である。当業者が認識するように、マッピングが有用な他の状況が構築され得る。たとえば、マッピングはスコーピングを規定することができ、スコーピングは、どの次元のどのメンバーがキューブ間のマッピングに参加するかを指定する。マッピングは、次元マップの仕様を規定することができ、それにより、製品の次元から製品ラインの次元へのマッピングが存在するときに「親」関数が含まれ、製品ラインの次元から製品の次元へのマッピングが存在するときに「子」関数が含まれるようにする。マッピングは、時間的な変形、たとえば月のデータから週のデータへの変形、または、会計カレンダーから製造カレンダーへの変形を規定し得る。
【００７１】
サンドボックス
これまで、上記のシナリオは、１人のユーザの変更または「what if」シナリオから直接的または間接的に生成された変更に対して主に焦点を合わせてきた。根底に存在する同一のデータセット上で、多数のユーザが代替的な「what if」シナリオを稼動させたいと願う状況がしばしば存在する。しかしながら、タッチリストの章で論じた上記の在庫の例から分かるように、変更の適用にはしばしば、順序付けの従属性が存在する。このことは、サンドボックス内と同様に、サンドボックス間でも問題を生じ得る。たとえば、ユーザＡおよびユーザＢが同じデータセットに対し、異なるサンドボックスを用いて作業している状況を想定されたい。ユーザＡおよびユーザＢはさまざまな別個の「what if」シナリオを稼動させており、これにより、上で論じたように異なる種類のカスケードが行なわれ、異なる結果を生じる。ここで、ユーザＡが根底に存在するデータベースに自分の変更を実行依頼したとすると、データが変化し、ユーザＢにより行なわれたすべてのカスケードが無効になるであろう。このことは容認され得ない。したがって、システムは、このような状況に対処するための組込機構を有していなければならない。特に、整合性はここで、ユーザＡが行なったすべての変更が、ユーザＢが行なったすべての変更の前に生じたかのように見えることを要求する。なぜなら、ユーザＢが自分の変更を実行依頼したとすると、それがシーケンスになるためである。これらの機構のいくつかを次に説明するが、まず、サンドボックスの概念をより詳細に考察する。
【００７２】
上記の出願および上記の内容では、さまざまな局面からサンドボックスの使用について説明してきた。上で説明したシステムの新規の動作および機能の結果として、サンドボックスに対する変更の適用および分離を改良してサンドボックス間で整合性が維持されるように確保すること、および、或るセルの予期せぬ数からランタイムの例外に至る、それ以
外の態様で生じるであろうさまざまな問題を回避することが望ましい。
【００７３】
上で説明したように、サンドボックスは、変更を分離し、それによって異なる変更のシナリオが別個に検討され得るように導入される。サンドボックスはツリー階層を形成することができ、上部のサンドボックスは、ベースサンドボックスまたはベースと呼ばれる。異なるサンドボックス内のキューブが同一のメータデータ、すなわち、キューブの定義を共有することに注目されたい。サンドボックス間の主な差異は、ブロックおよび変更である。ベースは、他のサンドボックスによりコミットされた変更から導出されるセル値を有する、それ自体のブロックのセットを有する。他のサンドボックスはすべて、ベースの子またはベースの子孫のいずれかである。各サンドボックスは、それ自体の別個のブロックのセットを有する。これらのブロックは、適用された子サンドボックスからの変更を有する親サンドボックス内のブロックの「スナップショット」であり、このスナップショットは、特定の時点で作成されたコピーである。スナップショットを取って変更を適用するプロセスもまた、変更の分離および適用と呼ばれる。
【００７４】
一実施例において、サンドボックスは、楽観的ロックを有する長期のトランザクションとして扱われる。変更は、多数の目的のために、変更リストエントリとして格納される。ベースサンドボックスは、決してコミットされ得ない長期のトランザクションとして視認され得る。サンドボックスは、そのすべての子サンドボックスが実行依頼されたかまたは廃棄されたときにのみ、実行依頼され得る（すなわち、トランザクションがコミットされ得る）。
【００７５】
一般に、サンドボックスは、データベースと同様の変更分離規則に従う。２つのサンドボックスが入れ子関係を有さない場合、これらのサンドボックスは、互いの変更を見ることができない。その一方で、子サンドボックスは、以下にさらに詳細に説明するいくつかの制限はあるものの、その親サンドボックスの変更を一般に見ることができる。親サンドボックスは２つ以上の子サンドボックスを有し得る。これらの子サンドボックスは個々に発展する。或るサンドボックスは、或るサンドボックスよりも早期に完了するか、または廃棄され得る。したがって、親サンドボックスと子サンドボックスとの間には、ブロックのスナップショットが形成されて子サンドボックス内で修正されるという楽観的ロックが使用される。整合するブロックのスナップショットを得るために、子サンドボックスは、子に適用された親の最新の変更を参照する。以降の変更のすべては、スナップショットを取るために無視される。これが、変更の分離の別の局面である。このことを図１に概略的に例示する。図１は、ベース、親、および子のサンドボックスの階層を示す。各サンドボックスはそれ自体のＣＬＥを有し、スナップショットが形成されたそのそれぞれの親ＣＬＥへの参照を含む。
【００７６】
一実施例において、この発明に従ったＤＢＭＳは、これまでの楽観的ロックのモデルとは異なる機構を使用する。一致を行なう前にトランザクションの終了まで待つ（すなわち、子サンドボックスを実行依頼する）のではなく、一致を連続して行なうことができる。なぜなら、子サンドボックスの変更がその親サンドボックスの変更よりも優先度が高いという概念に基づき、一致のプロセスが、決定論的なものであるためである。この一致プロセスを、さらに詳細に以下に論じる。
【００７７】
サンドボックスは、スナップショットＣＬＮという属性を有し、この属性は、子サンドボックスが整合する親サンドボックス内の整合点を指定する。換言すると、子サンドボックスは、当該子サンドボックスの変更が親に一致させられるまで、スナップショットＣＬＮの後に生じる親サンドボックスの変更を見ることになっていない。したがって、親サンドボックスまたはベースのブロックの漸進的変化を生じる変更が生じたときに、システムは、その漸進的変化がスナップショットＣＬＮを横切ったか否かをチェックする。漸進的
変化がスナップショットＣＬＮを横切っていない場合、ブロックは上記の通り更新される。しかしながら、漸進的変化がスナップショットＣＬＮを横切った場合、子サンドボックスが親サンドボックスからの「古い」ブロックデータにアクセスするようにブロックがまず複製され、その後、当該ブロックが上記の通り更新される。
【００７８】
ブロックキーは、以下の構成要素、すなわち、サンドボックスｉｄ、疎な座標、およびＣＬＮを有する。ＣＬＮは、ブロックのバージョンを指定し、論理的時間におけるこの時点までブロックを漸進的に変化させることを確保する。違った表現をすると、ログ内の以前の変更はすべて、ＣＬＮまでのブロックに適用される（または、ブロックは変更に従属しない）。以降の変更はいずれも、適用されない（または、ブロックは当該変更に従属しない）。
【００７９】
この発明の一実施例において、サンドボックスに関するブロックを検索するための２つの方法が存在する。第１の方法は、最新のサンドボックスＣＬＮ（ｍａｘ  ＣＬＮ）までの最新のサンドボックスから変更を有するブロックを検索することを含む。サンドボックスＣＬＮが、ログ内の「最新の」時点、すなわち、この特定のサンドボックスに関する最後のログエントリの数を表わすために使用されるＣＬＮであることに注目されたい。他方の方法は、特定のＣＬＮまでの最新のサンドボックスから変更を有するブロックを検索することを含む。当業者が認識するように、第１の方法は、サンドボックスの最新のＣＬＮを使用することにより、第２の方法に減縮され得る。特定のＣＬＮに関するサンドボックスの子についてのブロックを検索するための擬似コードを以下の表４に示す。
【００８０】
【表５】
2008547086.tif 000008
【００８１】
一実施例では、ベース以外のサンドボックス内のすべてのブロックを作成するために、３つの方法が存在する。第１の方法は、部分的に導入された変更の適用によるものである。第２の方法は、解析スプレッドシートの操作、キーメトリクスの表示、および報告等のさまざまなタスクに対するオンデマンドのブロック検索によるものである。第３の方法は、子サンドボックスの実行依頼によるものである。
【００８２】
ブロックＣＬＮにより表わされるブロックのさまざまな改訂版は、さまざまな理由により保持される必要がある。たとえば図２は、子サンドボックスがスナップショットＣＬＮ１によりどのように作成されるかを示す。図２に示し、かつ、上で論じたように、スナップショットＣＬＮ１未満であるか、またはそれに等しいブロックＣＬＮでブロックの改訂版を保持しなければならない。また、異なるスナップショットＣＬＮで作成された異なるサンドボックスも存在することが考えられ、これらの異なるサンドボックスに対しては、異なるブロック改訂版が保持されなければならない。ブロックの改訂版によっては、子サンドボックスが廃棄もしくは実行依頼されるときか、または、新規の改訂版の生成を生じる新規の変更が導入されたときに、不要情報ブロックとなり得るものもある。
【００８３】
一実施例では、効率の理由により、サンドボックス内の不要情報ブロックは、子サンドボックスが廃棄もしくは実行依頼されるときか、変更がサンドボックスに対して実行依頼されるときか、または、一致が生じたときにのみ、収集される。たとえば、すべての子サンドボックスのスナップショットＣＬＮが昇順でｓ１，…，ｓｎであり、ここでｎ≧０であるものと想定されたい。Ｌｏｎｇ．ＭＩＮ，ｓ１，…，ｓｎ，Ｌｏｎｇ．ＭＡＸのシーケンスにおいて、いずれかの２つの隣接するｘおよびｙに関し、ｘとｙとの間（両端を含む）でブロックＣＬＮを有する２つ以上のブロック改訂版が存在する場合、最後のものを除くこのようなブロック改訂版のすべてが不要情報ブロックである。
【００８４】
次に、一致のプロセスについて説明する。一実施例において、一致は、サンドボックスの階層のいずれのレベルにおいても開始され得、サンドボックスＣＬＮがいずれかの子サンドボックスに関するいずれかのスナップショットＣＬＮよりも大きいときにのみ、必要とされる。一致が開始されるサンドボックスでは、以下のステップが実施される。まず、アクティブな子サンドボックスが存在しないとの仮定の下で、すべての不要情報ブロックが削除される。次に、サンドボックスの階層が反復的にトラバースされ、各子孫につき、以下のことが実施される。すなわち、当該子孫を置換するために使用される新規のサンドボックスが作成される。親の最新のサンドボックスＣＬＮは、スナップショットＣＬＮとして取られる。ユーザが開始した変更等の非内部の変更エントリが、古いサンドボックスから抽出され、タッチリストが構築される。上記の通り、次に、タッチプロセスが実施される。最後に、古いサンドボックスが廃棄され、新規のサンドボックスが対応する応答に関連付けられる。ブロック間において順序の独立性が存在するときは、一致が必要とされないことに注目されたい。
【００８５】
変更エントリがリレーショナルデータベースに関連するときは、キューブへのマッピングを行なうために、または、当該キューブについてのデータ値を獲得するために、必要な古い列のすべておよび新しい列のすべてのコピーが保持される。一致が生じるときに、これらの多数のコピーが使用される。ユーザによっては、リレーショナルデータベースの同じ行に配置される、異なる値を変更したことが考えられ、これらの変更は、一致の際にマージされなければならない。たとえば、リレーショナルな発注のデータベースにおいて、第１のユーザが、発注の量に対して変更を行なったことが考えられ、別のユーザが、同じ発注の配送の日付に対して変更を行なったことが考えられる。これらのいずれもが同じ発注に関するため、これらの変更は、マージされるときに、一致するまで別個のコピーとして保持されなければならない。
【００８６】
一実施例において、子サンドボックスは、その親との一致が必要とされないときにのみ実行依頼され得る。このような条件下において、実行依頼は、子サンドボックスの変更を適用することによる親ブロックの漸進的変化を必要としない。むしろ、２つのサンドボックスは、ブロックが子サンドボックス内に存在する親サンドボックス内の各ブロックを削除し、子サンドボックスのブロックをリキーして親サンドボックス内のエントリを表わし
、それらのサンドボックスｉｄを更新し、それらの変更リスト番号の値を調節してマージされたログ内の時点を表わすことにより、マージされ得る。
【００８７】
次に、上記のとおり、不要情報ブロックが除去される。不要情報ブロックの除去の後に、事象の実行依頼が続く。この実行依頼は、子において作成された、すべての破壊された制約のＩＤを得ることと、親において作成されたのと同様に子において作成された、すべての破壊された制約の事象をマークすることと、すべての破壊された制約の当該ＩＤを用いて、子についての新規の記録を作成することとを含む。これらの新規の記録は、その後、閉じたものとして、かつ、固定されたものとして、マークされる。次に、破壊された制約は、同じ座標を有する子の制約を有する親の、破壊された制約のすべてを削除し、子のすべての破壊された制約を親に追加することにより、実行依頼される。次に、Ｃａｌｃ  ＣＬＮが、子サンドボックス内のキューブのＣａｌｃ  ＣＬＮにより、親の各キューブに関して調節される。最後に、子サンドボックスから変更エントリがクローニングされ、それらの変更エントリを親の変更リストの末尾に追加することにより、当該変更エントリが実行依頼される。サンドボックスＣＬＮはそれに応じて変更され、これにより、子サンドボックスの実行依頼が完了する。
【００８８】
上記の議論から分かるように、変更が適用されるときにブロックへの問合せに費やされる時間を最小にするために、ブロックのできるだけ最新のバージョンを保持することが有益である。このため、この発明の一実施例では、ブロックが変化するときだけでなく、当該ブロックに対して変更が何ら適用されていないとシステムが判断したときにも、ブロックを前進させる。しかしながら、ブロックデータが変化しない場合、同一ブロックのデータの多数のコピーを保持しておくことは効率が悪い。したがって、この発明の一実施例において、ブロックはヘッダ部およびデータ部にセグメント化され、ブロックがそのデータを変更することなく漸進的に変化させられるたびに、データ部を変化させず、ヘッダのみを前進させる。
【００８９】
この発明は、デジタル電子回路か、コンピュータハードウェア、ファームウェア、ソフトウェア、またはそれらの組合せにおいて実現され得る。この発明の装置は、プログラム可能プロセッサによる実行のためにマシン読取可能な媒体で具体的に実現されるコンピュータプログラムプロダクトにおいて実現され得る。マシン読取可能な媒体の例は、以下のものに限定されないが、ハードディスク、フロッピー（登録商標）ディスク、磁気テープ等の磁気媒体、ＣＤ−ＲＯＭディスクおよびＤＶＤ等の光学媒体、フロプティカル（登録商標）ディスク等の光磁気媒体、ならびに、プログラム命令を格納および実施するように特に構成されたハードウェア装置、たとえば読出専用記憶装置（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）を含む。この発明はまた、放送波、可視光線、電線等の適切な媒体を通じて伝わる搬送波においても実現され得る。この発明の方法ステップは、プログラム可能プロセッサが、入力データを操作して出力を生成することにより、この発明の機能を実施する命令のプログラムを実行することより実施され得る。
【００９０】
この発明は、有利にも、プログラム可能なシステムにおいて実行可能な１つ以上のコンピュータプログラムにおいて実現され得る。このプログラム可能なシステムは、データ記憶システムに結合されてそこからデータおよび命令を受信し、かつ、データおよび命令をそこに送信する少なくとも１つのプログラム可能プロセッサと、少なくとも１つの入力装置と、少なくとも１つの出力装置とを含む。各コンピュータプログラムは、高レベル手続型もしくはオブジェクト指向のプログラミング言語で、または、所望される場合、アセンブリまたはマシン言語で実現され得、いずれの場合も、言語は、コンパイラ型またはインタープリタ型言語であり得る。適切なプロセッサは、一例として、汎用マイクロプロセッサおよび特殊用途マイクロプロセッサの両方を含む。一般にプロセッサは、読出専用メモリおよび／またはランダムアクセスメモリから命令およびデータを受信する。一般に、コ
ンピュータは、データファイルを格納するために１つ以上の大容量記憶装置を含む。このような装置には、内部ハードディスクおよび取外し可能ディスク等の磁気ディスク、光磁気ディスク、および光ディスクが含まれる。コンピュータプログラム命令およびデータを具体的に実現するのに適した記憶装置は、あらゆる形態の不揮発性メモリを含み、これらの不揮発性メモリには、一例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリ装置等の半導体メモリ装置、内部ハードディスクおよび取外し可能ディスク等の磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスクが含まれる。上述のいずれに対してもＡＳＩＣ（特殊用途向け集積回路）が追加され得、または、上述のいずれもがＡＳＩＣに組込まれ得る。
【００９１】
この発明は、ユーザとの対話を設けるために、ユーザに情報を表示するためのモニタまたはＬＣＤ画面等の表示装置と、キーボードと、マウスまたはトラックボール等のポインティング装置とを有するコンピュータシステム上で実現され得る。当該キーボードおよび当該ポインティング装置により、ユーザはコンピュータシステムに入力を提供することができる。コンピュータシステムは、グラフィカルユーザインターフェイスを設けるようにプログラミングされ得、このグラフィカルユーザインターフェイスを介してコンピュータプログラムはユーザと対話する。
【００９２】
この発明の多数の実現例を説明してきた。しかしながら、この発明の精神および範囲から逸脱することなくさまざまな変更が行なわれ得ることを当業者は理解するであろう。たとえば、この発明は、中央トランザクションに対して行なわれた複雑な解析的演算の結果を表わすリレーショナルデータベース内の集計テーブルまたは事実テーブルを漸進的に変化させるためにも使用され得る。したがって、前掲の請求項の範囲内に他の実施例が存在する。
【図面の簡単な説明】
【００９３】
【図１】この発明に従ったサンドボックスの階層の概略図である。
【図２】この発明に従ってサンドボックスの不要情報の収集がどのように行なわれるかを示す概略図である。
【図１】
2008547086.tif 000009
【図２】
2008547086.tif 000010