(57)【要約】【課題】  リレーショナル・データベースにおいて時間的に一意のインデックス内のギャップを検出するための技術を実装及び使用する、コンピュータ・プログラム製品を含めた、方法及び装置を提供すること【解決手段】  リレーショナル・データベース内に時間的に一意のインデックスが準備される。インデックスは、キーの各々が１つ又は複数の非時間的キー部分と２つの時間的キー部分とを含む、第１のキーの組を含む。変更行についての挿入、更新、及び削除ステートメントの受信に応答して、変更行と同一の非時間的キー部分を有する行が識別される。識別された行の時間的キー部分と変更行の時間的キー部分とが比較され、変更行が時間的に前の行と時間的に後の行に直接隣接しているか否か、変更行と時間的に前の行との間にギャップが検出されるか否か、又は変更行と時間的に後の行との間にギャップが検出されるか否かを判定する。【選択図】      図１
2014038615.tif 000002
【特許請求の範囲】
【請求項１】
リレーショナル・データベースにおいて時間的に一意のインデックス内のギャップを検出するための方法であって、
リレーショナル・データベース内に時間的に一意のインデックスを準備することであって、前記時間的に一意のインデックスは、第１のキーの組を含み、前記第１のキーの組内の各キーは、１つ又は複数の非時間的キー部分と、時間的開始値及び時間的終了値を示す２つの時間的キー部分とを含む、準備することと、
前記リレーショナル・データベース内の変更行に関する挿入ステートメント、更新ステートメント、及び削除ステートメントのうちの１つの受信に応答して、
前記時間的に一意のインデックス内で、前記変更行と同一の非時間的キー部分を有する行を識別することと、
前記識別された行の前記時間的キー部分と前記変更行の前記時間的キー部分とを比較して、前記変更行が時間的に前の行と時間的に後の行の両方に直接隣接している否か、前記変更行と前記時間的に前の行との間にギャップが検出されるか否か、又は前記変更行と前記時間的に後の行との間にギャップが検出されるか否かを判定することと
を含む、方法。
【請求項２】
ギャップの検出に応答して、前記ギャップに関するデータをギャップ・リスト内に格納することをさらに含む、請求項１に記載の方法。
【請求項３】
前記ギャップ・リストを、前記リレーショナル・データベース内の前記時間的に一意のインデックスにアクセスする許可を有するエージェントがアクセス可能なメモリの共有領域内に格納することをさらに含む、請求項２に記載の方法。
【請求項４】
前記ギャップ・リストは、検索可能な木としてメモリ内に維持される、請求項３に記載の方法。
【請求項５】
前記ギャップ・リストは、検出された各ギャップについての以下の要素、すなわち、テーブル識別子、オブジェクト識別子、インデックス識別子、非時間的キー部分、並びに前記ギャップの開始時間及び終了時間のうちの１つ又は複数を含む連結リストである、請求項３に記載の方法。
【請求項６】
前記要素のうちの少なくとも幾つかをハッシュ化して前記メモリ内のスペースを保存することをさらに含む、請求項５に記載の方法。
【請求項７】
前記リレーショナル・データベース内の変更行に関する挿入ステートメント、更新ステートメント、及び削除ステートメントのうちの１つの受信に応答して、前記ギャップ・リストを検索し、前記ステートメントにより実行された操作がギャップを生じさせたか否かを判定することをさらに含む、請求項２に記載の方法。
【請求項８】
前記ギャップ・リストの検索は、遅延一意性インデックスに対して一意性違反チェックを行う時点で実行され、
前記操作がギャップを生じさせたとの判定に応答して、前記ギャップを生じさせた前記操作をロールバックする、請求項７に記載の方法。
【請求項９】
前記ギャップ・リストは、一度に１つのデータベース・ワークユニットによってのみ読み込み可能及び書き込み可能であり、かつ、前記ギャップ・リストは、一度に１つの時間的に一意のインデックスのみについてのギャップ含む、請求項２に記載の方法。
【請求項１０】
新たに識別されたギャップが前記ギャップ・リストに追加されたときに、事前定義された規則の組に従って、１つ又は複数のギャップを組み合わせることにより、又は既知のギャップを除去することにより、前記ギャップ・リストのサイズを小さくすることをさらに含む、請求項２に記載の方法。
【請求項１１】
請求項１〜１０の何れか１項に記載の方法の各ステップをコンピュータに実行させる、コンピュータ・プログラム。
【請求項１２】
請求項１１記載の前記プログラムをコンピュータ可読記録媒体に記録した、記録媒体。
【請求項１３】
リレーショナル・データベースにおいて時間的に一意のインデックス内のギャップを検出するためのシステムであって、
リレーショナル・データベースを格納するように動作可能なデータストアであって、前記リレーショナル・データベースは、第１のキーの組を有する時間的に一意のインデックスを含み、前記第１のキーの組内の各キーは、１つ又は複数の非時間的キー部分と、時間的開始値及び時間的終了値を示す２つの時間的キー部分とを含む、データストアと、
前記リレーショナル・データベースを制御するように動作可能であり、かつ、前記リレーショナル・データベースからのデータに対するユーザのクエリを処理するための方法動作を行うように動作可能なサーバコンピュータと、
を含み、前記方法動作は、
前記リレーショナル・データベース内の変更行に関する挿入ステートメント、更新ステートメント、及び削除ステートメントのうちの１つの受信に応答して、
前記サーバコンピュータによって、前記時間的に一意のインデックス内で、前記変更行と同一の非時間的キー部分を有する行を識別することと、
前記サーバコンピュータによって、前記識別された行の前記時間的キー部分と前記変更行の前記時間的キー部分とを比較して、前記変更行が時間的に前の行と時間的に後の行の両方に直接隣接しているか否か、前記変更行と前記時間的に前の行との間にギャップが検出されるか否か、又は前記変更行と前記時間的に後の行との間にギャップが検出されるか否かを判定することと
を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リレーショナル・データベースに関し、より具体的には、リレーショナル・データベースにおける時間的に一意のインデックス内のギャップ検出に関する。リレーショナル・データベースは、一般に、形式的に記述された、そこからデータに容易にアクセスすることができるテーブルの組として編成されたデータ項目の集積として説明することができる。リレーショナル・データベースにおいて用いられるソフトウェアは、典型的にはリレーショナル・データベース管理システム（ＲＤＢＭＳ）と呼ばれる。ＲＤＢＭＳの一例は、ニューヨーク州、アーモンク所在のインターナショナル・ビジネス・マシーンズ・コーポレーションから入手可能なＤＢ２  Ｕｎｉｖｅｒｓａｌ  Ｄａｔａｂａｓｅ（ＤＢ２  ＵＤＢ）である。
【背景技術】
【０００２】
ＲＤＢＭＳにおいて用いられることが多いテーブルの１つのタイプは、アプリケーション維持テンポラル・テーブル（Ａｐｐｌｉｃａｔｉｏｎ−Ｍａｉｎｔａｉｎｅｄ  Ｔｅｍｐｏｒａｌ  Ｔａｂｌｅｓ）である。テンポラル・テーブルは、所与の持続時間にわたって有効であることが知られたデータを含む。例えば、顧客への貸付の利率は、月又は年ごとに特定の値を有するが、この利率は、貸付の存続期間中に変動することがある。データベース・サーバが、アプリケーション維持テンポラル・テーブルとともに取り扱うことができる２つのタイプの制約、すなわち時間的一意性（Ｔｅｍｐｏｒａｌ  Ｕｎｉｑｕｅｎｅｓｓ）及びギャップ排除（Ｇａｐ  Ｅｌｉｍｉｎａｔｉｏｎ）が存在する。
【０００３】
時間的一意性制約（ＤＢ２  ＵＤＢシステムにおいては「ＷＩＴＨＯＵＴ  ＯＶＥＲＬＡＰＳ」制約とも呼ばれる）は、アプリケーション維持テンポラル・テーブルの各行が離散的な期間を記述すること、すなわち、所与の顧客の貸付に対する利率は、その貸付の存続期間中のいずれの所与の時点についても１つの値のみを有することを保証する。
【０００４】
ギャップ排除制約（本明細書においては「ＷＩＴＨＯＵＴ  ＧＡＰＳ」とも呼ばれる）は、ユーザのデータの持続期間にわたって値の中にギャップが存在しないこと、すなわち、貸付の開始から貸付の終了までに、利率が記録されない時点が存在しないことを保証する。
【０００５】
ＤＢ２  ＵＤＢのような幾つかのＲＤＢＭＳにおいて、ユーザは、ユーザ自身のギャップ排除トリガ又は構造化照会言語（ＳＱＬ）クエリを作成してギャップを検出することができる。しかしながら、ギャップ排除クエリは、インデックス内の「次の」行及び「以前の」行の値を求めるためにオンライン分析処理（ＯＬＡＰ）又は他の分析機能を用いる必要があるという点で、これらのＳＱＬクエリ、すなわち、
ＳＥＬＥＣＴ  ＊  ＦＲＯＭ
（ＳＥＬＥＣＴ  ＳＴＯＣＫ＿ＩＤ，  ＭＡＸ（ＥＮＤ＿ＤＡＴＥ）  ＯＶＥＲ  （ＯＲＤＥＲ  ＢＹ  ＢＥＧＩＮ＿ＤＡＴＥ）  ＧＡＰ＿ＳＴＡＲＴ，
ＬＥＡＤ（ＢＥＧＩＮ＿ＤＡＴＥ）  ＯＶＥＲ  （ＯＲＤＥＲ  ＢＹ  ＢＥＧＩＮ＿ＤＡＴＥ）  ＧＡＰ＿ＥＮＤ  ＦＲＯＭ  Ｔ１）
ＷＨＥＲＥ  ＧＡＰ＿ＳＴＡＲＴ  ＜  ＧＡＰ＿ＥＮＤ
は、時間的一意性よりはるかに複雑である。
【０００６】
さらに、インデックスは、更新／削除／挿入（ＵＤＩ）操作後、上記のＳＱＬステートメントが読まれる前にロックされないので、ＳＱＬベースのギャップ排除スキームを用いるユーザが「フォールスポジティブ」を受け取ってしまうことがあるので、ユーザは、ギャップについて監視したいインデックスに適合するようにクエリを調整することが必要となる。
【０００７】
別の代替的な技術は、ＵＤＩ操作後にテーブルのインデックスのスキャンを実行して、スキャン中に、修正された非時間的キー部分と一致する全てのキーを検索し、現在の行の終了時間が次の行の開始時間と等しくなることを保証することである。しかしながら、スキャンは、データ上のインデックス・ロック及びページ・ロックが解除された後で行われなければならないので、このことは、ロッキング及び同時処理に関する問題をもたらす。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、リレーショナル・データベースにおいて時間的に一意のインデックス内のギャップを検出するための技術を実装及び使用する、コンピュータ・プログラム製品を含めた方法及び装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の種々の実施形態によれば、リレーショナル・データベースにおいて時間的に一意のインデックス内のギャップを検出するための、コンピュータ・プログラム製品を含めた、方法及び装置が提供される。リレーショナル・データベース内に時間的に一意のインデックスが準備される。時間的に一意のインデックスは、第１のキーの組を含む。第１のキーの組内の各キーは、１つ又は複数の非時間的キー部分と、時間的開始値及び時間的終了値を示す２つの時間的キー部分とを含む。リレーショナル・データベース内の変更行に関する挿入ステートメント、更新ステートメント、及び削除ステートメントのうちの１つの受信に応答して、時間的に一意のインデックス内で、変更行と同一の非時間的キー部分を有する行が識別される。識別された行の時間的キー部分が変更行の時間的キー部分と比較され、変更行が時間的に前の行と時間的に後の行の両方に直接隣接しているか否か、変更行と時間的に前の行との間にギャップが検出されるか否か、又は変更行と時間的に後の行との間にギャップが検出されるか否かを判定する。
【００１０】
本発明の１つ又は複数の実施形態の詳細を、添付図面及び以下の説明で述べる。本発明の他の特徴及び利点は、この説明及び図面から、並びに特許請求の範囲から明らかとなろう。
【図面の簡単な説明】
【００１１】
【図１】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図２】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図３】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図４】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図５】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図６】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図７】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【図８】本発明の種々の実施形態による、インデックス及びギャップ・リストが種々のＵＤＩ操作によりどのように影響を受けるかの例を示す。
【発明を実施するための形態】
【００１２】
種々の図面における同様の参照符号は、同様の要素を示す。
【００１３】
「概説」
本明細書に説明される種々の実施形態は、例えば、時間的インデックスに対するＵＤＩ操作中にギャップのリストを維持するために、ＤＢ２  Ｉｎｄｅｘ  ＭａｎａｇｅｒのようなＲＤＢＭＳインデックスマネージャにより用いることができる技術に関する。これらの技術の使用の結果として、ＲＤＢＭＳの性能を改善することができ、時間的インデックスに対する時間的ＵＤＩ操作のために必要とされるアプリケーション開発時間が短くなり、ユーザのために得られる価値が増す。
【００１４】
種々の実施形態によると、ギャップ排除は、以下の情報、すなわち、変更行の開始時間（既知）、変更行の終了時間（既知）、前の行の終了時間（存在する場合）、及び次の行の開始時間（存在する場合）が知られていれば、インデックスの挿入、削除又は更新（更新は、単純には、直後に挿入が続く削除である）の時点でチェックすることができる。
【００１５】
本明細書で用いられる「前の行」及び「次の行」という表現は、インデックス内の他の全ての非時間的キー部分が一致する行を指す。前の値及び次の値を用いて、変更行が両側の２つの行に時間的に直接隣接していたか、又は空のスペース（既存のギャップ）が存在していたかを判定することができる。
【００１６】
ＩＮＳＥＲＴステートメントは、ギャップを生成する場合があり（挿入される行が前の行又は次の行に直接隣接しない場合）、又はギャップを除去することがある（挿入される行が前の行及び次の行の両方に直接隣接する、すなわちＵＰＤＡＴＥステートメントの場合）。
【００１７】
ＤＥＬＥＴＥステートメントは、ギャップを生成する場合があり（削除される行が前の行及び次の行の両方に直接隣接している場合）、又はギャップを除去することがある（削除される行が前の行又は次の行に直接隣接していない、すなわちＵＰＤＡＴＥステートメントの場合）。
【００１８】
時として、ＩＮＳＥＲＴ又はＤＥＬＥＴＥステートメントは、既存のギャップを拡張するか又は分割するか又は切り詰めることもある。以下にさらに詳細に説明される種々の技術は、既知のギャップの最小数を常に把握するギャップ検出アルゴリズムを用いる。同じく以下に説明されるように、このアルゴリズムは、単集合データの普通のＩＮＳＥＲＴ又はＤＥＬＥＴＥ、又はテーブルの完全クリア（すなわち、「ＤＥＬＥＴＥ  ＦＲＯＭ  Ｔ１」）のような共通シナリオに合わせて最適化される。
【００１９】
幾つかのＵＰＤＡＴＥステートメントは、ＵＰＤＡＴＥの終了によって解決される一時的なギャップを生じさせることがあり、すなわち、以下のＵＰＤＡＴＥステートメント
“ＵＰＤＡＴＥ  Ｔ１  ＳＥＴ  ＢＵＳ＿ＳＴＡＲＴ  ＝  ＢＵＳ＿ＳＴＡＲＴ  ＋  １  ＭＯＮＴＨ，  ＢＵＳ＿ＥＮＤ  ＝  ＢＵＳ＿ＥＮＤ  ＋  １  ＭＯＮＴＨ”
は、テーブル内にデータがあると、多くの行において一時的なギャップを生じさせることがあるが、ＵＰＤＡＴＥの最終結果は、常にギャップのないテーブルとなる。なぜなら、ギャップなしインデックスに対する全てのトランザクションは、インデックス内にギャップがない状態で完了するはずであり、そうでない場合にはトランザクションはロールバックすることになるからである。そのようなインデックスに対するいずれのデータベース操作の最終結果も、トランザクションがギャップのないテーブルで開始したならば、常にギャップのないテーブルとなる。
【００２０】
ひとたびギャップが知られると、このギャップは、当該テーブルに触れることができる全てのエージェントによりアクセス可能なメモリの共有領域内に格納された連結リストに追加することができる。連結リストの要素は、テーブルＩＤ、オブジェクトＩＤ、インデックスＩＤ、非時間的キー部分（又はスペースを節約するためにそのハッシュ値）、並びにギャップの開始時間及び終了時間を含む。ＵＤＩ操作が既存のギャップを除去することになる場合、後述のアルゴリズムによりギャップ・リストを検索してその既存のギャップを見いだすことができる。
【００２１】
ひとたび操作が完了し、全ての行がステートメントによって変更されると、操作がギャップを生じさせたかどうかを見つけ出すのは、ギャップ・リストが何らかのメンバを有しているかどうかをチェックするという単
純なことである。このチェックは、遅延（ｄｅｆｆｅｒｅｄ）一意性インデックスに対して一意性違反チェックを行う時点で実行することができる。操作がギャップを生じさせた場合、そのトランザクションは、ロールバックされる。
【００２２】
当業者により認識されるように、本発明の態様は、システム、方法又はコンピュータ・プログラム製品として具体化することができる。従って、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、又はソフトウェアの態様とハードウェアの態様とを組み合わせた実施形態の形をとることができ、これらは全て本明細書において一般的に「回路」、「モジュール」又は「システム」と呼ぶことができる。さらに、本発明の態様は、具体化されたコンピュータ可読プログラム・コードを内部に有する１つ又は複数のコンピュータ可読媒体内に具体化されたコンピュータ・プログラム製品の形をとることができる。
【００２３】
１つ又は複数のコンピュータ可読媒体の任意の組み合わせを利用することができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。コンピュータ可読ストレージ媒体は、これらに限定されるものではないが、例えば、電子的、磁気的、光学的、電磁気的、赤外線、若しくは半導体のシステム、装置、若しくはデバイス、又は上記のものの任意の組み合わせとすることができる。コンピュータ可読ストレージ媒体のより具体的な例（非網羅的なリスト）には、以下のもの、すなわち、１つ又は複数の配線を有する電気的接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能なプログラム可能読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、光記憶装置、磁気記憶装置、又は上記のものの任意の適切な組み合わせを含む。本文書の文脈においては、コンピュータ可読ストレージ媒体は、命令実行システム、装置若しくはデバイスによって、又はそれらとの関連で使用するためのプログラムを収容又は格納することができる任意の有形媒体とすることができる。
【００２４】
コンピュータ可読信号媒体は、コンピュータ可読プログラム・コードが、例えばベースバンド内に又は搬送波の一部として内部に具体化された伝搬データ信号を含むことができる。このような伝搬信号は、これらに限定されるものではないが、電磁気、光、又はそれらの任意の適切な組み合わせを含む種々の形態のいずれかを取ることができる。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、且つ、命令実行システム、装置若しくはデバイスによって、又はこれらとの関連で使用するためのプログラムを通信し、伝搬し、又は搬送することができる、任意のコンピュータ可読媒体とすることができる。
【００２５】
コンピュータ可読媒体上に具体化されたプログラム・コードは、これらに限定されるものではないが、無線、有線、光ファイバ・ケーブル、ＲＦ等、又は上記のもののいずれかの適切な組み合わせを含む、いずれかの適切な媒体を用いて伝送することができる。
【００２６】
本発明の態様の動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のようなオブジェクト指向型プログラミング言語、及び「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語を含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで記述することができる。プログラム・コードは、完全にユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で、独立したソフトウェア・パッケージとして実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は完全に遠隔コンピュータ若しくはサーバ上で実行される場合もある。後者のシナリオにおいては、遠隔コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）若しくは広域ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は、外部コンピュータへの接続がなされる場合もある（例えば、インターネット・サービス・プロバイダを用いるインターネットを通じて）。
【００２７】
本発明の態様は、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して以下で説明される。フローチャート図及び／又はブロック図の各ブロック、並びにフローチャート図及び／又はブロック図内のブロックの組み合わせは、コンピュータ・プログラム命令によって実装することができることが理解されるであろう。これらのコンピュータ・プログラム命令を、汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに与えてマシンを製造し、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサにより実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実装するための手段を生成するようにすることができる。
【００２８】
これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイスに特定の方式で機能させるように指示することができるコンピュータ可読媒体内に格納し、それにより、そのコンピュータ可読媒体内に格納された命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実装する命令を含む製品を製造するようにすることもできる。
【００２９】
コンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上にロードして、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上で、コンピュータ実装プロセスを生成するための一連の動作ステップを実施させて、それにより、コンピュータ又は他のプログラム可能装置上で実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実装するためのプロセスを提供するようにさえることもできる。
【００３０】
「幾つかの例証的な例」
ここで、本発明の種々の実施形態を、ＲＤＢＭＳにおいて実行することができる種々異なるタイプの操作を例として説明する。これらの例のために、キーＫ０，Ｋ１，Ｋ２，．．．，Ｋｎを有するインデックスを仮定する。各キーＫは、非時間的キー部分Ｋｐ０，Ｋｐ１，．．．Ｋｐｎと、時間的開始値及び終了値についての２つの時間的キー部分ＫｐＢ及びＫｐＥとで構成される。時間的開始キー部分ＫｐＢは、ＫｐＥより小さくなければならず、ここでＫｐＢは包含的であり、一方ＫｐＥは排他的である。これらの制限は、時間的キー部分の定義に固有のものである。ＫｐＢが排他的であることが許容されるか又はＫｐＥが包含的であることが許容される時間的実装では、以下で説明する技術をわずかに修正する必要がある。
【００３１】
そのようなテーブルにおける一意性は、３つの異なる方法で定義することができる。
【００３２】
非時間的一意性：これは、全てのキーＫについて、Ｋの全てのキー部分が相異なることを述べる。
【００３３】
重なりのない時間的一意性：これはさらに、全ての相異なるキーの対Ｋ１及びＫ２について、以下の全てが真であることを述べる。
・Ｋ１ｐＢ  ＜＝  Ｋ２ｐＢならば、Ｋ１ｐＥ  ＜  Ｋ２ｐＢ。
・Ｋ１ｐＥ  ＞＝  Ｋ２ｐＥならば、Ｋ１ｐＢ  ＞＝  Ｋ２ｐＥ。
【００３４】
重なりもギャップもない時間的一意性：これはさらに、全ての外部的に等しいキーＫ（以下で定義される）について、Ｋと外部的に等しいがＫより時間的に先行する前のキーＰｒｅｖＫが存在するならば、ＰｒｅｖＫのＫｐＥはＫのＫｐＢと等しく、Ｋと外部的に等しいがＫより時間的に後である次のキーＮｅｘｔＫが存在するならば、ＮｅｘｔＫのＫｐＢはＫのＫｐＥと等しいことを述べる。インデックス内の全てのキーＫがこの要件を満たすならば、そのインデックスは、ギャップがなく時間的に一意であるといわれる。
【００３５】
Ｋｐ０，Ｋｐ１，．．．Ｋｐｎが等価である任意の２つのキーを外部的に等しい（ｅｘｔｅｒｎａｌｌｙ  ｅｑｕａｌ）キーと呼ぶこととするが、それは、データの現行バージョンは、時間的一意性制約を満たすテーブル内でそのようなキーを１つだけ含むことになるためである。例えば、２つのキー（Ｊｏｅ，‘１２３’，０１／０１／１２，０２／０１／１２）及び（Ｊｏｅ，‘１２３’，０２／０１／１２，０３／０１／１２）を有する時間的インデックスがあると仮定すると、これらは外部的に等しい。換言すれば、データベースを照会しているユーザにとっては、（Ｊｏｅ，‘１２３’）という１つの値が存在するのみであり、この値は、１つは１月から２月まで、もう１つは２月から３月までという２つの有効期間を有する。これらのキーの非時間的キー部分は両方とも等しいが、時間的（開始／終了）キー部分は異なっている。これらのインデックスキー自体は、もちろん、データベースの視点からは完全に異なるが、時間的アプリケーションのユーザの視点からは等しい。
【００３６】
「ギャップ・チェックなし」
あるインデックスが、所与のキーＫについてのＰｒｅｖＫ又はＮｅｘｔＫを含まない場合には、その時間的方向における（それより前又はそれより後の）ギャップのチェックは必要ない。
【００３７】
あるインデックスが、そのインデックス内のその他のいずれのキーもそれに対して外部的に等しくないキーＫを含む場合には、そのキーＫはどちらの側にもギャップを有さないと言われる。
【００３８】
キーが全くないインデックスもまた、ギャップなし制限及び時間的重なりなし制限を満たすものと言われる。
【００３９】
幾つかの実施形態において、ギャップなし制限は、ＤＭＬ（データ操作言語）ステートメントの実行の最後においてのみチェックされる。ＳＥＬＥＣＴ操作中は、リーダをブロックするロックがインデックス上に存在する必要はないものと仮定し、ＵＤＩ操作については、ＵＤＩ操作の持続期間にわたって、修正されるキーの外部的に等しいキーがデータベースによって排他的にロックされるものと仮定する。
【００４０】
ギャップなしインデックスの場合、そのインデックスは、一貫した状態、すなわち全てのキーがギャップも重なりもない時間的一意性要件を満たす状態で、いかなるトランザクションも開始するはずである。以下は、インデックスの挿入、更新又は削除ステートメントの過程でインデックス内にギャップを作り出す可能性がある幾つかの事例である。
【００４１】
「キーの追加」
この操作は、ＳＱＬステートメントの一部として、キーをインデックスに追加する。この操作は、新たなキーＫが外部的に等しいＰｒｅｖＫを有し、ここでＫ−＞ＫｐＢがＰｒｅｖＫ−＞ＫｐＥに等しくない場合、又は新たなキーＫが外部的に等しいＮｅｘｔＫを有し、ここでＫ−＞ＫｐＥがＮｅｘｔＫ−＞ＫｐＢに等しくない場合に、インデックス内にギャップを生じさせる可能性がある
【００４２】
ＩＮＳＥＲＴステートメントは、１つ又は複数のキーをインデックスに追加することができる。例えば、１より多くのキーがインデックスに追加されている場合（例えば、ＳＵＢＳＥＬＥＣＴ  ＳＱＬステートメントからのＩＮＳＥＲＴの一部として）、挿入されているキーの順序は未定義である。上述のように、たとえＩＮＳＥＲＴステートメントの最終結果がギャップのないインデックスであるとしても、ＩＮＳＥＲＴステートメントによって一時的なギャップが導入されることもある。この理由のため、全ＩＮＳＥＲＴ操作が完了するまで、「キー追加」操作によりエラーを投げる（ｔｈｒｏｗ）ことはできない。
【００４３】
データベースにおけるＲＯＬＬＢＡＣＫは、ロールバックされるトランザクションの全ての操作を取り消すことによって実行される。ＲＯＬＬＢＡＣＫ操作の一例は、削除操作を取り消すことであり、これはキーをインデックスに追加することと等価である。インデックスはＤＥＬＥＴＥ開始前には一貫したギャップなし状態にあったと仮定すると、ＤＥＬＥＴＥの取り消し中にインデックス内にギャップは生成されないはずである。
【００４４】
空のインデックス内に最初のキーを追加すること、又は所与の非時間的キー部分の組に対して最初の外部的に等しいキーを追加することで、ギャップが生成されることは決してない。これら２つのシナリオを検出することができ、このＩＮＳＥＲＴステートメントの持続期間中はギャップ検出をディスエーブルにすることができる。
【００４５】
「キーの削除」
この操作は、ＳＱＬステートメントの一部として、インデックスからキーを除去する。この操作は、削除されたキーＫが外部的に等しいＰｒｅｖＫを有し、ここでＫ−＞ＫｐＢがＰｒｅｖＫ−＞ＫｐＥと等しく、かつ、削除されたキーＫが外部的に等しいＮｅｘｔＫを有し、ここでＫ−＞ＫｐＥがＮｅｘｔＫ−＞ＫｐＢと等しい場合に、インデックス内にギャップを生じさせる可能性がある。削除されたＫが、インデックス内の直前又は直後に外部的に等しいキーを有さない場合には、ギャップが生成されることはない。キー削除についてのギャップ検出アルゴリズムは、キー挿入についてのギャップ検出アルゴリズムの逆であることに留意されたい。
【００４６】
ＤＥＬＥＴＥステートメントは、１つ又は複数のキーをインデックスから削除することができる。１より多いキーがインデックスから削除されている場合には、削除されているキーの順序は未定義であり、たとえばＤＥＬＥＴＥステートメントの最終結果がギャップのないインデックスであるとしても、ＤＥＬＥＴＥステートメントによって一時的なギャップが導入されることがある。この理由のため、全ＤＥＬＥＴＥ操作が完了するまで、キー削除操作によりエラーを投げることはできない。
【００４７】
インデックスの最後のキーを削除すること、又は、所与の非時間的キー部分の組に対して最後の外部的に等しいキーを削除することで、ギャップが生成されることは決してない。これら２つのシナリオを検出することができ、このＤＥＬＥＴＥステートメントの持続期間中はギャップ検出をディスエーブルにすることができる。
【００４８】
「ＵＰＤＡＴＥ操作」
ＵＰＤＡＴＥステートメントは、キーの削除と、それに続く異なるキーの挿入として扱われる。従って、キーの追加又は削除についての上述の論理がＵＰＤＡＴＥ操作内で生じ、キーの追加又は削除中に検出されるいかなるギャップもギャップ・リストに記録され、ギャップについてのエラーがあればステートメントの最後においてのみ投げられる。
【００４９】
「操作についての一時的ギャップ・リストの維持」
ギャップは、その時間範囲の開始及び終了により記述される。開始値及び終了値は、ＮＵＬＬになることはできず、負の無限又は正の無限となることもできない。ギャップは、現行のＵＤＩステートメントによって削除されなかった２つのキー値の間にのみ存在することができる。幾つかの実施形態において、既知のギャップのリストは、検索可能な木（例えば二分木又はＢ木など）として維持され、各ギャップ・リストは、一度に１つのデータベース・ワークユニットによってのみ読み出し可能及び書き込み可能であり、一度に１つのインデックスについてのギャップ・リストを含むことになる。このことにより、複数のワークユニットが互いのギャップ・チェックを干渉することが回避される。
【００５０】
キーの追加又は削除操作中にギャップが見いだされるたびにいつでも、ギャップ・エントリがギャップ・リストに追加される。ギャップ・エントリは、非時間的キー部分、ギャップ開始時間、及びギャップ終了時間を含む。ギャップ開始時間及び終了時間は、次の又は前の外部的に等しいキーの開始時間又は終了時間と、新たに追加又は削除されたキーの開始時間又は終了時間とにより定められる。
【００５１】
このように、ギャップ・リストは、インデックスのミラーとして機能することになる。インデックス内に存在するいかなる値もギャップ・リスト内には存在せず、ギャップ・リスト内に存在するいかなるギャップもインデックス内には存在しないことになる。従って、これらのギャップ・リストのサイズを最小にするためには、キーの追加及び削除中に見いだされたギャップを、特定の規則に応じて、既知のギャップと組み合わせるか、又は既知のギャップを除去することになる。
【００５２】
このことをさらに例証するために、図面を参照して後述する以下の事例Ａ−Ｅを検討されたい。以下の事例Ａ−Ｅにおける例のために、一貫したインデックス、及び、時間的開始及び終了値をＴ０，Ｔ１，Ｔ２，Ｔ３，Ｔ４及びＴ５として、特定の範囲の時間的キー値が存在するものと仮定する。図１に示されるように、時間的範囲Ｔ１−＞Ｔ２は、インデックスから排除され、ギャップ・リストに追加される。
【００５３】
事例Ａ：既存のギャップに隣接する、新たに追加されたギャップ
新たに追加されたギャップがリスト内の既存のギャップに隣接する（すなわち、新たなギャップのＫｐＥが既存のギャップのＫｐＢと等しい、及び／又は、新たなギャップのＫｐＢが既存のギャップのＫｐＥと等しい）場合には、一方又は両方の側のギャップが、このギャップの追加によって影響を受けることになる。
【００５４】
事例Ａ１：この一例は、時間的範囲Ｔ０−＞Ｔ１がインデックスから削除される場合である。ギャップ・リストは、Ｔ１−＞Ｔ２を含み、この新たなギャップは、既存のギャップに隣接し、かつそれより前であるが、この新たなギャップ自体は、リスト内にそれより前のギャップを有さない。Ｔ１より後にもギャップは存在せず、従って、値Ｔ０−＞Ｔ１を削除すると、必然的にギャップ・リストからギャップＴ１−＞Ｔ２を除去することになり、ギャップ・リストは空になる。最も早い値はＴ２であるので、インデックスは、この時点ではギャップを有さない。ギャップは、無限の開始時間又は終了時間を有することができないので、最も早い値又は最も遅い値が削除されると、これは、隣接する既知のギャップを除去するという影響を有する。更新されたインデックス及びギャップ・リストを図２に示す。
【００５５】
事例Ａ２：ここで、時間的範囲Ｔ２−＞Ｔ３がインデックスから削除される事例を考える。この場合、既存のギャップＴ１−＞Ｔ２が拡張されてＴ１−＞Ｔ３のギャップになる。２つのキー値がインデックスから削除されたが、ギャップ・リストはなお１つの既知のギャップのみを有する。このようにして、最小数のギャップがギャップ・リスト内に記録され、これがインデックス内のキーの数の半分を超えることは決してない。更新されたインデックス及びギャップ・リストを図３に示す。
【００５６】
事例Ａ３：図４（Ａ）に示されるように、ギャップ・リストが２つのギャップＴ１−＞２及びＴ３−＞Ｔ４を含む事例を考える。新たなギャップ、Ｔ２−＞Ｔ３が導入され、これはギャップ・リスト内の両方のギャップに隣接する。前のギャップのＫｐＥは、いまや後のギャップのＫｐＥとなり、後のギャップはリストから除去され、図４（Ｂ）に示されるようにギャップ・リストには単一のギャップＴ１−＞Ｔ４が残ることになる。
【００５７】
事例Ｂ：新たに追加されたギャップが隣接するギャップを有さない
新たに追加されたギャップがリスト内に隣接するギャップを有さないが、前の又は後の外部的に等しいキー値がインデックス内に存在する場合、これは新たなギャップである。例えば、図１に示された元のインデックス及びギャップ・リストから、Ｔ３−＞Ｔ４がインデックスから削除された場合、このギャップは、図５に示されるように、ギャップ・リストに追加されることになり、既存のギャップＴ１−＞Ｔ２と組み合わされることも又はそれを修正することもない。
【００５８】
事例Ｃ：ギャップがギャップ・リストから削除される
ギャップがギャップ・リストから削除され（すなわち、インデックスキーが、同じ作業ユニット内で削除された後でインデックスに戻されて追加される場合）、そのギャップが既知のギャップと厳密に一致する場合には、そのギャップは、ギャップ・リストから除去される。例えば、既存のギャップＴ１−＞Ｔ２が図１に示されるギャップ・リストから削除された場合には、その結果もたらされるインデックス及びギャップ・リストは、図６のインデックス及びギャップ・リストのように見えることになる。
【００５９】
事例Ｄ：新たに削除されるギャップが既存のギャップ内に完全に含まれる
新たに削除されるギャップが既存のギャップ内に完全に含まれる場合には、ギャップを２つに分割しなければならず、早い方の半分のギャップは、削除されたギャップのＫｐＢに等しいＫｐＥを有し、遅い方の半分のギャップは、削除されたギャップのＫｐＥに等しいＫｐＢを有することになる。例えば、ギャップ・リストが図７（Ａ）に示されるようにＴ１−＞Ｔ４を含み、ギャップＴ２−＞Ｔ３が除去された場合には、ギャップ・リストは、図７（Ｂ）に示されるように、Ｔ１−＞Ｔ２及びＴ３−＞Ｔ４を含むことになる。
【００６０】
事例Ｅ：新たに削除されるギャップが既存のギャップ内に部分的に含まれる
新たに削除されるギャップが既存のギャップ内に部分的に含まれる場合、既存のギャップの開始時間又は終了時間は修正されなければならず、事実上、既知のギャップを短縮する。例えば、ギャップ・リストが図８Ａに示されるようにＴ１−＞Ｔ４を含み、ギャップＴ３−＞Ｔ４がリストから除去された場合、既存のギャップは、図８Ｂに示されるようにＴ１−Ｔ３になる。
【００６１】
操作の最後に、ギャップ・リストを見て、何らかの要素が存在するかどうか確認することによりギャップの存在をチェックするのは、ささいなことである。ギャップを作り出すインデックスの操作はロールバックされ、ロールバックは、インデックスを解決（ｒｅｓｏｌｖｅ）して元の一貫した状態に戻すことが保証されているので、このロールバック操作中、全てのギャップ・チェックを一時停止することができる。
【００６２】
図面内のフローチャート及びブロック図は、本発明の種々の実施形態による、システム、方法及びコンピュータ・プログラム製品の可能な実装の、アーキテクチャ、機能及び動作を示す。この点に関して、フローチャート又はブロック図内の各ブロックは、指定された論理機能を実装するための１つ又は複数の実行可能な命令を含む、モジュール、セグメント又はコードの一部を表すことができる。幾つかの代替的な実装において、ブロック内に記載された機能は、図面内に記された順序とは異なる順序で行われる場合があることにも留意すべきである。例えば、連続して図示された２つのブロックが、実際には実質的に同時に実行されることもあり、又はこれらのブロックは、関与する機能に応じて、ときには逆順で実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、並びにブロック図及び／又はフローチャート図内のブロックの組み合わせは、指定された機能又は動作を実行する専用ハードウェア・ベースのシステム、又は専用ハードウェアとコンピュータ命令との組み合わせによって実装することができることにも留意されたい。
【００６３】
本明細書において用いられる用語は、特定の実施形態を説明する目的のためのものにすぎず、本発明を限定することを意図したものではない。本明細書において用いられる場合、単数形「ａ」、「ａｎ」、及び「ｔｈｅ」は、文脈が明らかにそうでないことを示していない限り、複数形も同様に含むことが意図される。「含む（ｃｏｍｐｒｉｓｅｓ）」及び／又は「含んでいる（ｃｏｍｐｒｉｓｉｎｇ）」という用語は、本明細書において用いられる場合、言明された特徴、整数、ステップ、動作、要素、及び／又はコンポーネントの存在を指定するが、１つ又は複数の他の特徴、整数、ステップ、動作、要素、コンポーネント、及び／又はそれらの群の存在又は追加を排除するものではないことが、さらに理解されるであろう。
【００６４】
以下の特許請求の範囲における全ての「手段又はステップと機能との組み合わせ（ミーンズ又はステップ・プラス・ファンクション）要素の対応する構造、材料、動作及び均等物は、その機能を、明確に特許請求されているように他の特許請求された要素と組み合わせて実行するための、いかなる構造、材料又は動作をも含むことが意図される。本発明の種々の説明は、例示及び説明の目的で提示されたものであるが、網羅的であることを意図するものではなく、又は本発明を開示された形態の限定することを意図するものでもない。本発明の範囲及び思想から逸脱することのない多くの変更及び変形が、当業者には明らかであろう。例えば、本明細書で説明される種々の実施形態は、当業者が精通しているように、Ｂ木、又はハッシュテーブル、又は連結リスト、又はＪａｖａコレクション（ＨａｓｈＭａｐ／ＴｒｅｅＭａｐ／等）、又はＸＭＬファイル等としてモデル化されるギャップ・リストにより扱うことができる。規則に従う限り、ギャップ・リスト（又はインデックス又はデータベース）の実装はアルゴリズムによって規定されない。実施形態は、本発明の原理及び実際の適用を最も良く説明するように、かつ、当業者が、企図された特定の使用に適した種々の修正を伴う種々の実施形態について本発明を理解することを可能にするように選択及び説明がなされた。
【図１】
2014038615.tif 000003
【図２】
2014038615.tif 000004
【図３】
2014038615.tif 000005
【図４】
2014038615.tif 000006
【図５】
2014038615.tif 000007
【図６】
2014038615.tif 000008
【図７】
2014038615.tif 000009
【図８】
2014038615.tif 000010