(57)【特許請求の範囲】
【請求項１】
コンピュータ環境内でリレーショナル・データベースの参照保全性を維持するために、前記データベースに対して実行される動作を計画的に順序付けるシステムであって、
（ａ）前記データベースの複数の表に対し行われる挿入順序を判定する手段と、
（ｂ）前記データベースの前記複数の表に対し行われる削除順序を判定する手段と、
（ｃ）前記データベースに対し行われる複数の挿入、更新、および削除処理（以下これらの処理を「変更」と総称する）を、当該変更のそれぞれによって実行される動作のタイプ、および当該変更のそれぞれによって主キー値が指定されている前記複数の表の特定の１つに従って、クラスタ化する手段と、
（ｄ）前記クラスタ化された変更を前記データベースに適用する手段とを備え、
当該適用する手段（ｄ）が、
まず、前記挿入順序に従って、前記動作が挿入である前記クラスタ化された変更のすべてを適用する手段と、
次に、前記動作が更新である前記クラスタ化された変更のすべてを適用する手段と、
最後に、前記削除順序に従って、前記動作が削除である前記クラスタ化された変更のすべてを適用する手段とを含み、
前記挿入順序を判定する手段（ａ）が、
（ａ１）前記複数の表のうちのコンピュータによって選択された現行表のそれぞれについて、１つまたは複数の参照関係にある表（以下これを「関係する表」と称する）を識別する手段と、
（ａ２）前記現行表および前記関係する表のそれぞれの間で、挿入優先順位を判定する手段と、
（ａ３）前記現行表が前記関係する表に対して挿入優先順位を有する場合には、前記関係する表の前に前記現行表を順序付け、前記現行表が前記関係する表に対して挿入優先順位を有しない場合には、前記関係する表の後に前記現行表を順序付ける手段とを含み、
前記挿入優先順位を判定する手段（ａ２）が、
前記現行表および前記関係する表の各特定の１つについて、前記現行表の主キーと前記特定の関係する表の外部キーとの間に定義された挿入制約が存在するかどうかを判定する手段と、
前記挿入制約が存在する場合には、前記挿入制約の外部キーが前記特定の関係する表内に配置されているかどうかを判定する手段と、
前記挿入制約が存在しない場合、または前記外部キーが前記特定の関係する表内に配置されていない場合には、前記現行表が前記挿入優先順位を有しないと結論する手段と、
前記外部キーが前記特定の関係する表内に配置されている場合には、前記現行表が前記挿入優先順位を有すると結論する手段とを含み、
前記削除順序を判定する手段（ｂ）が、
（ｂ１）前記複数の表のうちのコンピュータによって選択された現行表のそれぞれについて、１つまたは複数の参照関係にある表（以下これを「関係する表」と称する）を識別する手段と、
（ｂ２）前記現行表および前記関係する表のそれぞれの間で、削除優先順位を判定する手段と、
（ｂ３）前記現行表が前記関係する表に対して削除優先順位を有する場合には、前記関係する表の前に前記現行表を順序付け、前記現行表が前記関係する表に対して削除優先順位を有しない場合には、前記関係する表の後に前記現行表を順序付ける手段とを含み、
前記削除優先順位を判定する手段（ｂ２）が、
前記現行表および前記関係する表の各特定の１つについて、前記現行表の外部キーと前記特定の関係する表の主キーとの間に定義された削除制約が存在するかどうかを判定する手段と、
前記削除制約が存在する場合には、前記削除制約の外部キーが前記現行表内に配置されているかどうかを判定する手段と、
前記削除制約が存在しない場合、または前記外部キーが前記現行表内に配置されていない場合には、前記現行表が前記削除優先順位を有しないと結論する手段と、
前記外部キーが前記現行表内に配置されている場合には、前記現行表が前記削除優先順位を有すると結論する手段とを含むシステム。
【請求項２】
前記動作が更新である前記クラスタ化された変更が、任意の順序で適用される、請求項１に記載のシステム。
【請求項３】
前記挿入順序を判定する手段の動作および前記削除順序を判定する手段の動作が、前記クラスタ化する手段の動作および前記適用する手段の動作の前に実行される、請求項１に記載のシステム。
【請求項４】
前記クラスタ化する手段の動作および前記適用する手段の動作が、後続の複数の変更のそれぞれについて繰り返して実行される、請求項１に記載のシステム。
【請求項５】
リレーショナル・データベースの参照保全性を維持するために、前記データベースに対して実行される動作を計画的に順序付ける方法であって、
（ａ）前記データベースの複数の表に対し行われる挿入順序を判定するステップと、
（ｂ）前記データベースの前記複数の表に対し行われる削除順序を判定するステップと、
（ｃ）前記データベースに対し行われる複数の挿入、更新、および削除処理（以下これらの処理を「変更」と総称する）を、当該変更のそれぞれによって実行される動作のタイプ、および当該変更のそれぞれによって主キー値が指定されている前記複数の表の特定の１つに従って、クラスタ化するステップと、
（ｄ）前記クラスタ化された変更を前記データベースに適用するステップとから成り、
当該適用するステップ（ｄ）が、
まず、前記挿入順序に従って、前記動作が挿入である前記クラスタ化された変更のすべてを適用するステップと、
次に、前記動作が更新である前記クラスタ化された変更のすべてを適用するステップと、
最後に、前記削除順序に従って、前記動作が削除である前記クラスタ化された変更のすべてを適用するステップとを含み、
前記挿入順序を判定するステップ（ａ）が、
（ａ１）前記複数の表のうちのコンピュータによって選択された現行表のそれぞれについて、１つまたは複数の参照関係にある表（以下これを「関係する表」と称する）を識別するステップと、
（ａ２）前記現行表および前記関係する表のそれぞれの間で、挿入優先順位を判定するステップと、
（ａ３）前記現行表が前記関係する表に対して挿入優先順位を有する場合には、前記関係する表の前に前記現行表を順序付け、前記現行表が前記関係する表に対して挿入優先順位を有しない場合には、前記関係する表の後に前記現行表を順序付けるステップとを含み、
前記挿入優先順位を判定するステップ（ａ２）が、
前記現行表および前記関係する表の各特定の１つについて、前記現行表の主キーと前記特定の関係する表の外部キーとの間に定義された挿入制約が存在するかどうかを判定するステップと、
前記挿入制約が存在する場合には、前記挿入制約の外部キーが前記特定の関係する表内に配置されているかどうかを判定するステップと、
前記挿入制約が存在しない場合、または前記外部キーが前記特定の関係する表内に配置されていない場合には、前記現行表が前記挿入優先順位を有しないと結論するステップと、
前記外部キーが前記特定の関係する表内に配置されている場合には、前記現行表が前記挿入優先順位を有すると結論するステップとを含み、
前記削除順序を判定するステップ（ｂ）が、
（ｂ１）前記複数の表のうちのコンピュータによって選択された現行表のそれぞれについて、１つまたは複数の参照関係にある表（以下これを「関係する表」と称する）を識別するステップと、
（ｂ２）前記現行表および前記関係する表のそれぞれの間で、削除優先順位を判定するステップと、
（ｂ３）前記現行表が前記関係する表に対して削除優先順位を有する場合には、前記関係する表の前に前記現行表を順序付け、前記現行表が前記関係する表に対して削除優先順位を有しない場合には、前記関係する表の後に前記現行表を順序付けるステップとを含み、
前記削除優先順位を判定するステップ（ｂ２）が、
前記現行表および前記関係する表の各特定の１つについて、前記現行表の外部キーと前記特定の関係する表の主キーとの間に定義された削除制約が存在するかどうかを判定するステップと、
前記削除制約が存在する場合には、前記削除制約の外部キーが前記現行表内に配置されているかどうかを判定するステップと、
前記削除制約が存在しない場合、または前記外部キーが前記現行表内に配置されていない場合には、前記現行表が前記削除優先順位を有しないと結論するステップと、
前記外部キーが前記現行表内に配置されている場合には、前記現行表が前記削除優先順位を有すると結論するステップとを含む、方法。
【請求項６】
前記動作が更新である前記クラスタ化された変更が、任意の順序で適用される、請求項５に記載の方法。
【請求項７】
前記挿入順序を判定するステップの動作および前記削除順序を判定するステップの動作が、前記クラスタ化するステップの動作および前記適用するステップの動作の前に実行される、請求項５に記載の方法。
【請求項８】
前記クラスタ化するステップの動作および前記適用するステップの動作が、後続の複数の変更のそれぞれについて繰り返して実行される、請求項５に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ・プログラミングの分野に関し、具体的には、影響される表について定義された参照保全性制約に従って、計画的に動作を順序付けることによって、リレーショナル・データベースに対して実行される動作の効率を高める方法およびシステムに関する。
【０００２】
【従来の技術】
「参照保全性（referential integrity）」とは、データベースの表の間の一貫性が維持される、リレーショナル・データベースの特性を指す。具体的に言うと、参照保全性を維持するためには、各表の行の外部キー値のすべてが有効であることが必要である。外部キーが有効であるのは、その値が、（１）ヌルでないか、（２）識別される表のある行に主キーとして現れるかのいずれかの場合である。主キーが含まれる表を、しばしば「親」表と呼び、外部キーが含まれる表を、「従属」表と呼ぶ。特定の表が外部キーを有しない場合があり、この場合には、この表に関して実施される参照保全性制約はなく、そうでない場合には、表が１つまたは複数の外部キーを有する。表が複数の外部キーを有する時には、複数の親表／従属表関係が存在し、そのような関係のそれぞれについて参照保全性制約を実施しなければならない。
【０００３】
参照保全性制約は、表の行の挿入または削除を行う動作がデータベースに対して実行される時と、更新動作が外部キーの値に影響する時に実施されなければならない。挿入制約では、挿入される行の各外部キー値が、必ず対応する親表に主キー値として現れなければならないことが必要である。たとえば、Employee（従業員）表とDepartment（部署）表を有するデータベースがあり、Employee表の各行が、その従業員が働いている部署を識別する列項目を有すると仮定する。この部署列を、外部キーとして定義することができ、その場合には、対応する主キーが、Department表の部署番号になる。この例では、参照保全性を維持するために、ある部署についてEmployee表で従業員を定義する前に、その部署をDepartment表で作成することが必要になる。削除制約では、削除される行の主キーが、従属表の１つまたは複数の行の外部キー値として指定されていないことが必要である。例として同一のEmployee表およびDepartment表を使用すると、部署がDepartment表から削除される場合には、参照保全性を維持するために、その部署の部署番号を参照しているすべてのEmployee行を、まず削除しなければならない（そうしなければ、削除動作を行うことができない）ことが必要である。更新制約では、外部キー値に対する更新が、親表にすでに主キーとして現れている新しい値を使用しなければならない（または、更新によって、外部キー値にヌルがセットされる）ことが必要である。
【０００４】
したがって、リレーショナル・データベースに対して実行される動作の順序が、データベースの参照保全性を維持するのに非常に重要であることがわかる。潜在的な参照保全性制約違反の検出を提供し、不整合データベースにつながる動作を実行できなくする、多くのデータベース・システムが市販されている（たとえば、無効な挿入動作が、まだ主キー値として使用されたことがない外部キー値を含むことを示すエラー・メッセージを生成する可能性がある）。International Business Machines Corporation（ＩＢＭ）社の一般にＤＢ／２（商標）と称するＤＡＴＡＢＡＳＥ２（商標）製品が、この種のデータベース・システムの初期の例である（「ＤＡＴＡＢＡＳＥ２」はＩＢＭ社の商標であり、「ＤＢ／２」はＩＢＭ社の商標である）。
【０００５】
参照保全性制約違反を避けるために動作を実行しなければならない順序は、通常は、アプリケーション・プログラム内でリレーショナル行が作成または削除される順序と一致しない。したがって、行をデータベースに挿入または削除する必要がある順序は、アプリケーションのイベント・フローから推論することができない。さらに、ユーザが、行の作成または削除に関する情報を対話的に供給する場合、参照保全性を維持するための正しい順序で情報を指定するようにユーザに要求することは、（おそらくは複雑な）表の相互関係を理解するという非現実的な重荷をユーザに課し、柔軟性のない非直観的な形で作業することをユーザに要求する。
【０００６】
参照保全性制約違反を避けるために、リレーショナル・データベースに対して実行される動作を計画的に順序付ける技法の１つとして、オブジェクト指向プログラミング・アプリケーションのために、オブジェクトの間のアソシエーションを使用して、オブジェクト・レベルで動作を順序付ける方法が考えられる。
【０００７】
オブジェクト指向でないアプリケーションと共に使用することができるか、変更を生成するアプリケーションの有効範囲の外部で（アプリケーションからの順序付けられない動作の受取時にリレーショナル・データベース・エンジンで、など）使用することができ、これによってアプリケーション自体の変更を回避するか、その両方である、計画的に動作を順序付ける技法を有することが有利であろう。自動的なデータベース動作順序付けがなければ、プログラマが、動作を生成するアプリケーション・プログラムに動作順序付けを手作業でコーディングするか、データベース内の参照保全性規則実施を使用不能にするかのいずれかを行う必要がある。動作順序付けの手作業のコーディングは、時間がかかり、誤りをおかしやすく、簡単に維持不能なコードにつながる。参照保全性規則検査の使用不能化は、不整合データベースにつながる可能性がある。
【０００８】
したがって、リレーショナル・データベースに対して実行される動作を自動的に順序付ける、改良された技法が必要である。
【０００９】
【発明が解決しようとする課題】
本発明の目的は、参照保全性制約違反を避けるために、リレーショナル・データベースに対して実行される動作を計画的に順序付ける技法を提供することである。
【００１０】
本発明のもう１つの目的は、リレーショナル・データベース動作の効率が高まるように、この順序付け技法を提供することである。
【００１１】
本発明のもう１つの目的は、順序付けで、影響される表について定義された参照保全性制約が使用される、この方針に基づく順序付け技法を提供することである。
【００１２】
本発明のもう１つの目的は、バッチ・モード処理を使用可能にし、これによって、複数のリレーショナル・データベース記憶動作を同時に実行でき、これによって、アプリケーションとデータベース・エンジンの間のラウンドトリップの数を減らし、したがって、システム全体の効率を高める、方針に基づく順序付け技法を提供することである。
【００１３】
本発明のもう１つの目的は、オブジェクト指向アプリケーションと共に使用することに制限されない、方針に基づく順序付け技法を提供することである。
【００１４】
本発明のもう１つの目的は、データベース変更動作を生成するアプリケーション・プログラムの有効範囲の外部で使用することができ、これによって、アプリケーション自体を無変更のままにすることを可能にする、方針に基づく順序付け技法を提供することである。
【００１５】
本発明の他の目的および長所は、部分的には以下の説明および図面に示され、部分的には説明から明白になるか、本発明の実践によって習得することができる。
【００１６】
【課題を解決するための手段】
前述の目的を達成するために、本明細書で広く説明する本発明の目的に従い、本発明は、リレーショナル・データベースに対して実行される動作の効率を高めると同時に参照保全性制約違反を回避する方法およびシステムを提供する。これは、実行される動作を計画的に順序付ける技法を使用して達成される。この技法には、データベースの複数の表の間で挿入順序を判定するステップと、この複数の表の間で削除順序を判定するステップと、変更のそれぞれによって実行される動作に従い、変更のそれぞれによって影響を受ける表の特定の１つに従って、データベースに対して行われる複数の変更をクラスタ化するステップと、クラスタ化された変更をデータベースに適用するステップとが含まれる。クラスタ化された変更を適用するステップには、さらに、まず、挿入順序に従って、動作が挿入であるクラスタ化された変更のすべてを適用するステップと、次に、動作が更新であるクラスタ化された変更のすべてを適用するステップと、最後に、削除順序に従って、動作が削除であるクラスタ化された変更のすべてを適用するステップとが含まれる。動作が更新であるクラスタ化された変更は、任意の順序で適用することができる。
【００１７】
挿入順序および削除順序の判定は、変更のクラスタ化および適用の前の時に実行することができる。
【００１９】
変更のクラスタ化および適用は、後続の複数の変更のそれぞれについて、繰り返して実行することができる。変更の適用は、バッチ書込モードで実行することができる。
【００２０】
挿入順序の判定には、さらに、表の選択された１つのそれぞれについて、１つまたは複数の関係する表を識別するステップと、選択された表および関係する表のそれぞれの中から、挿入優先順位を判定するステップと、選択された表がそれに関する挿入優先順位を有する関係する表の前に選択された表を順序付け、選択された表がそれに対する挿入優先順位を有しない関係する表の後に選択された表を順序付けるステップとを含めることができる。
【００２１】
挿入優先順位を判定するステップには、さらに、選択された表および関係する表の各特定の１つについて、選択された表と特定の関係する表との間の関係が制約を有するかどうかを判定するステップと、制約が存在する時に、制約の外部キーが特定の関係する表内に配置されているかどうか判定するステップと、制約が存在しない時、または外部キーが特定の関係する表内に配置されていない時に、選択された表が挿入優先順位を有しないと結論するステップと、外部キーが特定の関係する表内に配置されている時に、選択された表が挿入優先順位を有すると結論するステップとを含めることができる。
【００２２】
削除順序を判定するステップには、さらに、表の選択された１つのそれぞれについて、１つまたは複数の関係する表を識別するステップと、選択された表および関係する表のそれぞれについて、削除優先順位を判定するステップと、選択された表がそれに関する削除優先順位を有する関係する表の前に選択された表を順序付け、選択された表がそれに関する削除優先順位を有しない関係する表の後に選択された表を順序付けるステップとを含めることができる。
【００２３】
削除優先順位を判定するステップには、さらに、選択された表および関係する表の各特定の１つについて、選択された表と特定の関係する表との間の関係が制約を有するかどうかを判定するステップと、制約が存在する時に、制約の外部キーが選択された表内に配置されているかどうかを判定するステップと、制約が存在しない時または外部キーが選択された表内に配置されていない時に、選択された表が削除優先順位を有しないと結論するステップと、外部キーが選択された表内に配置されている時に、選択された表が削除優先順位を有すると結論するステップとを含めることができる。
【００２４】
これから、図面を参照して本発明を説明するが、図では、同様の符号がすべての図を通じて同一の要素を表す。
【００２５】
【発明の実施の形態】
図１に、本発明を実践することができる代表的なワークステーション・ハードウェア環境を示す。図１の環境には、パーソナル・コンピュータなど、関連する周辺装置を含む、代表的な単一ユーザのワークステーション１０が含まれる。ワークステーション１０には、マイクロプロセッサ１２および、既知の技法に従ってマイクロプロセッサ１２とワークステーション１０の構成要素とを接続し、これらの間の通信を可能にするのに使用されるバス１４が含まれる。ワークステーション１０には、通常は、ユーザ・インターフェース・アダプタ１６が含まれ、ユーザ・インターフェース・アダプタ１６は、バス１４を介して、キーボード１８、マウス２０、または、接触感知画面、ディジタル化入力パッドなどのユーザ・インターフェース装置とすることができる他のインターフェース装置２２など、１つまたは複数のインターフェース装置にマイクロプロセッサ１２を接続する。バス１４は、ＬＣＤ画面またはモニタなどのディスプレイ装置２４も、ディスプレイ・アダプタ２６を介してマイクロプロセッサ１２に接続する。バス１４は、マイクロプロセッサ１２を、メモリ２８および、ハード・ドライブ、ディスケット・ドライブ、テープ・ドライブなどを含めることができる長期保管記憶装置３０も接続する。
【００２６】
ワークステーション１０は、たとえば通信チャネルまたはモデム３２を介して、他のコンピュータまたはコンピュータのネットワークと通信することができる。その代わりに、ワークステーション１０は、ＣＤＰＤ（セルラ・ディジタル・パケット・データ）カードなどの、通信チャネルまたはモデム３２にある無線インターフェースを使用して通信することができる。ワークステーション１０は、ＬＡＮまたはＷＡＮでそのような他のコンピュータと関連することができ、また、ワークステーション１０は、別のコンピュータなどとのクライアント／サーバ配置のクライアントとすることができる。これらの構成のすべてならびに適当な通信ハードウェアおよび通信ソフトウェアが、当技術分野で既知である。
【００２７】
図２に、本発明を実践することができるデータ処理ネットワーク４０を示す。データ処理ネットワーク４０には、無線ネットワーク４２およびネットワーク４４などの複数の個々のネットワークを含めることができ、これらのネットワークのそれぞれに、複数の個々のワークステーション１０を含めることができる。さらに、当業者が諒解するように、１つまたは複数のＬＡＮを含めることができ（図示せず）、ＬＡＮには、ホスト・プロセッサに結合された複数のインテリジェント・ワークステーションを含めることができる。
【００２８】
さらに図２を参照すると、無線ネットワーク４２およびネットワーク４４には、ゲートウェイ・コンピュータ４６またはアプリケーション・サーバ４７（データ・リポジトリ４８にアクセスすることができる）などのメインフレーム・コンピュータまたはサーバも含めることができる。ゲートウェイ・コンピュータ４６は、各ネットワーク４４の入口点として働く。ゲートウェイ・コンピュータ４６は、通信リンク５０ａによって別の無線ネットワーク４２に結合できることが好ましい。ゲートウェイ・コンピュータ４６は、通信リンク５０ｂ、５０ｃを使用して１つまたは複数のワークステーション１０に直接に結合することもできる。ゲートウェイ・コンピュータ４６は、ＩＢＭ社から入手可能なEnterprise Systems Architecture/370、Enterprise Systems Architecture/390コンピュータなどを使用して実施することができる。応用分野に応じて、Application System/400（ＡＳ／４００とも称する）などのミッドレンジ・コンピュータを使用することができる（「Enterprise Systems Architecture/370」はＩＢＭ社の商標であり、「Enterprise Systems Architecture/390」、「Application System/400」、および「ＡＳ／４００」はＩＢＭ社の登録商標である）。
【００２９】
ゲートウェイ・コンピュータ４６は、記憶装置（データ・リポジトリ４８など）に結合４９することもできる。さらに、ゲートウェイ・コンピュータ４６は、１つまたは複数のワークステーション１０に直接にまたは間接的に結合することができる。
【００３０】
当業者は、ゲートウェイ・コンピュータ４６を、無線ネットワーク４２から地理的に大きく離れて配置することができ、同様に、ワークステーション１０を、無線ネットワーク４２およびネットワーク４４からかなりの距離に配置することができることを諒解するであろう。たとえば、無線ネットワーク４２を、米国カリフォルニア州に配置し、ゲートウェイ・コンピュータ４６を、米国テキサス州に配置し、１つまたは複数のワークステーション１０を、米国ニューヨーク州に配置することができる。ワークステーション１０を、ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）などのネットワーキング・プロトコルを使用し、セルラ電話、無線ネットワーク、衛星ネットワークなどの多数の代替接続媒体を介して、無線ネットワーク４２に接続することができる。無線ネットワーク４２は、ＩＰ上のＴＣＰまたはＵＤＰ（ユーザ・データグラム・プロトコル）、Ｘ．２５、フレーム・リレー、ＩＳＤＮ（サービス総合ディジタル網）、ＰＳＴＮ（公衆交換電話網）などの通信リンク５０ａを使用してゲートウェイ・コンピュータ４６に接続されることが好ましい。ワークステーション１０は、代替案では、ダイヤル接続による通信リンク５０ｂまたは５０ｃを使用してゲートウェイ・コンピュータ４６に直接に接続することができる。さらに、無線ネットワーク４２およびネットワーク４４は、図２に示されたものに類似の形で、１つまたは複数の他のネットワーク（図示せず）に接続することができる。
【００３１】
本発明を実施するソフトウェア・プログラミング・コードは、通常は、ワークステーション１０またはアプリケーション・サーバ４７のマイクロプロセッサ１２によって、ＣＤ−ＲＯＭドライブまたはハード・ドライブなどのある種類の長期保管記憶装置３０からアクセスされる。ソフトウェア・プログラミング・コードは、ディスケット、ハード・ドライブ、またはＣＤ−ＲＯＭなどのデータ処理システムと共に使用するためのさまざまな既知の媒体のいずれかで実施することができる。このコードは、そのような媒体上で配布することができ、また、あるコンピュータ・システムのメモリまたは記憶装置からある種類のネットワークを介して他のコンピュータ・システムへ、そのような他のコンピュータ・システムのユーザによる使用のためにユーザに配布することができる。その代わりに、プログラミング・コードを、メモリ２８内で実施し、バス１４を使用してマイクロプロセッサ１２によってアクセスすることができる。ソフトウェア・プログラミング・コードをメモリ内または物理媒体上で実施するか、ネットワークを介してソフトウェア・コードを配布するか、その両方を行う技法および方法は、周知であり、本明細書ではこれ以上説明しない。
【００３２】
本発明のユーザは、ワイヤライン（wireline）接続または無線接続を使用して、自分のコンピュータをサーバに接続することができる。ワイヤライン接続とは、ケーブルおよび電話回線などの物理媒体を使用する接続であり、無線接続は、衛星リンク、無線電波、および赤外線波などの媒体を使用する。多数の接続技法を、これらのさまざまな媒体と共に使用することができ、コンピュータのモデムを使用して電話回線を介する接続を確立する、トークン・リングまたはイーサネットなどのＬＡＮカードを使用する、セルラ・モデムを使用して無線接続を確立するなどを行うことができる。ユーザのコンピュータは、ラップトップ・コンピュータ、ハンドヘルド・コンピュータ、またはモバイル・コンピュータ、車載装置、デスクトップ・コンピュータ、メインフレーム・コンピュータなど、処理機能および通信機能を有するすべての種類のコンピュータ・プロセッサとすることができる。同様に、リモート・サーバは、処理機能および通信機能を有する多数の異なるタイプのコンピュータのいずれかとすることができる。これらの技法は、当技術分野で周知であり、それらの使用を可能にするハードウェア・デバイスおよびソフトウェアは、簡単に入手できる。以下では、ユーザのコンピュータを、同等に「ワークステーション」、「装置」、または「コンピュータ」と呼称し、これらの用語のいずれかまたは用語「サーバ」の使用は、上で説明したいずれかの種類の計算装置を指す。
【００３３】
本発明では、行がデータベースに記憶されるか削除される時に、任意の基礎になるリレーショナル・データベースについて定義された参照保全性制約に従って、挿入動作、更新動作、および削除動作を計画的に順序付ける技法が定義される。本明細書では、主キー列対外部キー列対によって記述されるデータベース内の関係する表の間で定義される関係情報およびこれらの列対に関する保全性規則を使用する順序付けアルゴリズムを定義する。
【００３４】
本発明を使用することができる計算環境には、インターネット環境、イントラネット環境、エクストラネット環境、または他のタイプのネットワーク環境を含めることができる。これらの環境は、クライアント・サーバ・アーキテクチャまたは多層アーキテクチャを使用して構成することができる。本発明は、動作の順序付けが、データベース・エンジンが配置されるのと同一の計算機で実行されるか、結果の順序付けされた動作をデータベース・エンジンに送信するためにネットワークに接続する前に動作の順序付けが実行される、切断モード（すなわちスタンドアロン・モード）で使用することもできる。
【００３５】
本発明の好ましい実施形態を、図３ないし１８を参照して説明する。
【００３６】
好ましい実施形態では、本発明は、１つまたは複数のコンピュータ・ソフトウェア・プログラムとして実施される。本発明のソフトウェアの実施形態は、サーバまたはネットワーク内の中間装置で、１つまたは複数のモジュール（コード・サブルーチンまたは、オブジェクト指向プログラミングで「オブジェクト」とも称する）として動作することができる。その代わりに、本明細書で開示される発明的概念から逸脱せずに、ソフトウェアがユーザのワークステーションで動作することができる。本発明を、リレーショナル・データベースにアクセスするすべてのシステムならびにリレーショナル・データベース・エンジンによって使用することができる。
【００３７】
本発明の実施形態は、（ｉ）実行時に排他的に、または（ｉｉ）部分的に実行時の前（たとえば開発時）に実行される前処理ステップとしておよび部分的に実行時に、実行することができる。どちらの場合でも、アプリケーションによって作成される（順序付けられていない）変更の組が、データベースに適用される前に本発明を使用して順序付けられる。順序付けは、データベース・エンジンが常駐するサーバで、クライアント計算機から変更の組を受け取った後に適用することができる。または、順序付けを、クライアント計算機で適用し、順序付けられた変更の組を、データベース・エンジンによる直接適用のためにサーバに送ることができる。場合（ｉ）には、順序付け技法が、アプリケーションが実行を完了した後に実行されて、そのアプリケーションによって生成された変更を順序付け、適用する状況が含まれる。場合（ｉｉ）では、特定のアプリケーションによって使用される表の間の順序付け関係を、アプリケーションを使用して変更を生成する前に、本発明に従って、計画的に判定することができる。
【００３８】
図３ないし７に、従来技術による、リレーショナル・データベース表に記憶されるデータ値の簡単な例を示す。この例を使用して、本発明の動作を示す。たとえば、対象の表は、Company（会社）表３００、Department（部署）表３１０、Employee（従業員）表３２０、Spouse（配偶者）表３３０、およびAddress（住所）表３４０である。Company表３００の各行３０１および３０２には、単一の会社の情報が格納される。Company表３００は、この表にアクセスするための主キーとして働き、したがって各行の一意の要素であるCompany Number（会社番号）３０３によって編成される。この例では、各行が、会社名のフィールド（列として示される）Company Name３０４も有する。Department表３１０は、この表の主キーであるDepartment Number（部署番号）３１５によって編成される。各行３１１、３１２、３１３、および３１４は、部署名のフィールドDepartment Name３１６およびこの部署が存在する会社番号のフィールドCompany Number３１７を有する。Company Number３１７は、この例では外部キーであり、各部署の行を、関連する会社を表すCompany表３００からの行とリンクする。同様に、Employee表３２０は、その主キーとしてEmployee Number（従業員番号）３２５を有し、この表の行をDepartment表３１０およびSpouse表３３０にリンクする外部キー列３２７および３２８を有する。Spouse表３３０は、その主キーとしてSpouse Identifier（配偶者識別子）３３５を有し、外部キーを含まない。Address表３４０は、主キーとしてAddress Identifier（住所識別子）３４５を使用し、外部キー列３４７を含む。この外部キー列３４７の値は、Employee表３２０の行を指し、この住所が定義されている従業員を識別する（図３ないし７で使用される表が、本発明を示すために簡略化されており、実際のアプリケーションに使用される表が、通常は図３ないし７に示されたものよりより多数のフィールドおよび多数の行を有することは、当業者に明白であろう）。
【００３９】
前に述べたように、データベース行に対して実行することができる関係演算には、挿入動作、更新動作、および削除動作の３種類がある。これらの動作タイプの間の依存性は次の通りである。
（１）挿入動作は、他の挿入に依存する（すなわち、挿入される行が、挿入されるもう１つの行を参照する）可能性があるが、他の種類の動作には依存しない。挿入の間の依存性の例として、新しい部署の従業員の従業員情報が、図３ないし７に示されたデータベースに挿入されると仮定する。Employee表３２０は、外部キー列３２７についてDepartment表３１０に依存するので、新しい部署の行が、その部署の新しい従業員の行の前に挿入されなければならない。
（２）更新動作は、他の更新には依存しないが、挿入に依存する（すなわち、ある行が、挿入される行を参照するように更新される）可能性がある。更新と挿入の間の依存性の例として、従業員０００５０（行３２２）が部署Ｅ０１から部署Ｅ１０に異動したので、図３ないし７に示されたデータベースを変更しなければならず、部署Ｅ１０が、挿入される新しい部署であると仮定する。この場合、従業員の行３２２の更新を実行する前に、新しい部署Ｅ１０の行を挿入しなければならない。
（３）削除動作は、他の削除に依存する（すなわち、削除される行が、削除される別の行を参照する）可能性があり、更新に依存する（ある行が、削除される行の参照を解除するように更新される）可能性がある。削除の間の依存性の例として、部署Ｅ０１およびその従業員のすべてを削除すると仮定する。参照保全性を維持するためには、まず従業員の行を削除することが必要であり、その後、部署の行を削除することができる。削除と更新の間の依存性の例として、部署Ｅ０１が削除されるが、その従業員が削除されないと仮定する。この場合、部署の行３１２の削除が発生する前に、この部署のすべての従業員の行（この例では行３２２および３２３）を変更して、その部署の外部キー列３２７の値を変更しなければならない。
【００４０】
特定のデータベースの表に関する異なるデータベース動作の間の優先関係が、複雑な前提条件木を形成する。しかし、動作実行の正しい順序を決定できるようになるために、これらの前提条件を完全に解決する必要はない。その代わりに、挿入動作の間および削除動作の間でのみ前提条件を解決する必要があり、異なる動作タイプの間の高水準で解決する必要はあるが、異なる動作タイプにまたがって個別に解決する必要はない。動作タイプの間での高水準の動作の解決には、動作を３つの相すなわち、まず挿入動作、次に更新動作、最後に削除動作の順で実行することだけが必要である。この順序は、上で説明した動作タイプの間の依存性に合わせて調整されていることがわかる。したがって、おそらく更新される行によって参照される可能性がある行のすべてが、すでにデータベース内にあることになるので、挿入動作を実行した後に更新動作を実行することが安全である。すべての可能な参照解除が更新相中に行われるので、更新動作の後に削除動作を実行することができる。
【００４１】
挿入動作の間の詳細な順序付けを決定するために重要な判断基準が、行が挿入される表と、その行の外部キーによって参照される表である。用語「参照する」行または表は、本明細書では、前者を記述するのに使用され、用語「参照される」行または表は、後者を記述するのに使用される。図３ないし７の例を使用すると、外部キー列３２７（Department Number）を使用して、Employee表３２０内で「従業員Ｘが部署Ｙで働いている」関係を示す場合、Employee表３２０に挿入される行は、参照する表としてEmployee表、参照される表としてDepartment表３１０を有する。したがって、新しい従業員０００１１を、新しい部署Ｅ１１に挿入する（下で詳細に説明する図８に示されている）場合、参照する行は行４１０であり、参照される行は行４２０である。したがって、行４２０は、行４１０が挿入される前にデータベースに挿入されなければならない。
【００４２】
一般に、挿入に関するこの順序付け要件は、「行を挿入する時に、表Ａ内の参照される行を、表Ｂの参照する行の前に挿入しなければならない」と記述される。すべての参照される行が表Ａに挿入されている場合、表Ｂの行によって参照される可能性がある表Ａ内のすべての行が、すでにデータベース内にあるので、表Ｂに参照する行を挿入しても安全である。したがって、挿入動作は、１時に１つの表について実行することができ、まず表Ａにすべての参照される行を挿入し、その後、表Ｂにすべての参照する行を挿入する。したがって、詳細な挿入優先順位は、本発明の技法を使用する時に、個々の行の間ではなく、表の間で解決するだけでよい。
【００４３】
削除に関する順序付け要件は、「行を削除する時に、表Ｂの参照する行を、表Ａの参照される行を削除する前に削除しなければならない」と記述される。表Ｂからすべての参照する行を削除した場合、表Ｂの、おそらく表Ａの行を参照する可能性があるすべての行がデータベースから除去されているので、表Ａの参照される行を削除しても安全である。したがって、削除動作は、１時に１つの表について実行することができ、まず表Ｂからすべての参照する行を削除し、その後、表Ａからすべての参照される行を削除する。したがって、詳細な削除優先順位では、本発明の技法を使用する時に、個々の行の間ではなく、表の間で解決するだけでよい。
【００４４】
本発明によって定義される順序付け技法では、まず、行を挿入する動作および行を削除する動作のそれぞれについて、影響を受ける表の間で順序付け要件を判定する（参照される表および参照する表について上で定義した規則を使用する）。これによって、順序付けされた挿入表リストおよび順序付けされた削除表リスト（それぞれ図１０の要素５１０および５２０によって示される）がもたらされる。影響を受ける行が、その後、変更される表および実行されるデータベース動作のタイプに従ってクラスタ化される。すなわち、挿入動作が、表によってクラスタ化または分離され、更新動作が、（厳密には必要でないが、好ましい実施形態によれば表によって）分離され、削除動作が、表によって分離される。これによって、表ごとに３つのリストすなわち、挿入される行のリスト、更新される行のリスト、および削除される行のリストがもたらされる（明白であるとおり、動作タイプごとの個々の表リストは、３つの総合リストに組み合わせることができ、その結果の挿入リストおよび削除リストは、順序付けされた挿入表リストおよび順序付けされた削除表リストに従って順序付けされる）。
【００４５】
更新動作を有する表は、上で述べたように、動作順序付けを必要としない。挿入動作および削除動作について、好ましい実施形態では、ほぼ理想的なアルゴリズム（図１０および図１４ないし１６に関して下で詳細に説明する）を使用して、表の間の詳細な前提条件を解決する。それぞれの場合で、順序付けアルゴリズムでは、表の２つのリストすなわち、変更が実行される表の元の順序付けられていないリスト（本明細書では、同等に未ソート・リストと称する）および順序付けられた表リスト（本明細書では同等にソート済みリストと称する）を使用する。当初、順序付けられた表リストは空である。順序付けアルゴリズムは、順序付けられていないリスト内の表について反復する。反復される表のそれぞれ（「現行表」と称する）が、まず順序付けられた表リストの末尾に追加される。このアルゴリズムは、その後、現行表が他の表に対して有する関係（すなわち、それらへまたはそれらからの外部キー）について反復する。そのような関係のそれぞれについて、このアルゴリズムは、現行表がその関係で挿入優先順位（挿入順序付けを実行する時）または削除優先順位（削除順序付けを実行する時）を有するかどうかをテストする。現行表が、関係での優先順位を有し、関係する表が、すでに順序付けられたリストに含まれる（現行表の前の位置に）場合には、関係する表のそれぞれおよびその下位の優先順位の関係する表が、再帰的にリストの末尾に移動される。順序付けアルゴリズムの完了時に、順序付けられたリスト内の表の順序は、データベースで定義された参照保全性規則に対応する、すなわち、ソート済み挿入リストが、挿入動作を実行しなければならない順序を規定し、ソート済み削除リストも同様である。
【００４６】
現行表は、関係する表が現行表内の主キー列を参照する外部キー列を有し、この主キー列／外部キー列対に関して定義された制約がある場合に、関係に対する挿入優先順位を有する。現行表は、現行表が関係する表内の主キー列を参照する外部キー列を有し、この主キー列／外部キー列対に関して定義された制約がある場合に、関係に対する削除優先順位を有する。
【００４７】
順序付け相およびクラスタ化相が完了した後に、ソート済み表リスト内の順序に従って、行の挿入、更新、および削除を行うことができる。
【００４８】
この処理の動作を、例に関して説明する。図８に、図３ないし７のサンプル・データに対して実行することができる変更を示し、図９に、本発明による順序付けの後のこれらの変更を示す。図１０に、図３ないし７からの例の表のサブセットと、各表について作成された動作リストを使用する、本発明に従って実行される表順序付けの例を示す。
【００４９】
図８に、図３ないし７の５つの表のデータに対して行うことができる７つの代表的な変更の行４１０ないし４４０を示す。図８および図９で使用される表フォーマットは、例示を目的とし、本発明と共に使用される構造を示す目的のものでないことに留意されたい。さらに、各変更のデータ値のサブセットだけが含まれ、そのサブセットは、本発明によって使用される関連する情報を示すものであることに留意されたい。図８の列４０５からわかるように、通常のアプリケーションによって作成される動作のタイプは、混合されている。本発明による順序付けの後に、動作は、挿入に関する第１の順序付けられたグループ（４２０、４１０、４３５）、次に、更新に関する順序付けられていないグループ（この例では単一の変更の行４１５だけを含む）、最後に、削除に関する順序付けられたグループ（４４０、４３０、４２５）にクラスタ化される。
【００５０】
図８の列４０６では、変更によって影響を受ける表名が識別され、列４０７では、その表の主キー値が指定される。したがって、行４１０では、主キー値０００１１（Employee Number３２５列の）を有する新しい従業員が、Employee表３２０に挿入される。列４０８では、この新しい従業員のために使用される外部キー列３２７の値が指定され、列４０９では、この外部キーが主キーとして定義されている表が識別される（Employee表３２０の追加の外部キー列３２８は、図を単純にするために行４１０から省略されているが、図１３ないし１７の論理に関して詳細に説明するように、外部キー列３２７と同様の形で処理される）。したがって、行４１０の最後の２つの項目は、この新しい従業員が部署Ｅ１１のメンバであることを示す。図４には、この部署番号の行が含まれておらず、したがって、データベースに行４１０を直接に挿入しようと試みると、参照保全性制約に違反することに留意されたい。しかし、図８の行４２０は、Department表３１０にこの部署を作成する挿入動作である。したがって、本発明の順序付け動作は、計画的に、図９の最初の２つの順序付けられた行（４２０、４１０）によって示されるように、行４１０の挿入動作の前に行４２０の挿入動作が行われるようにし、これによって、違反を避ける。行４３５の残りの挿入動作では、従業員番号０００１２を有する新しい従業員が追加されるが、この従業員は、部署Ｅ２１にいるものとして定義されている。この部署番号は、Department表３１０ですでに定義されているので、行４３５の挿入は、制約違反を引き起こさない。この挿入の行４３５は、順序付けられた挿入動作の３番目として図９に示されている。しかし、挿入の間（および削除の間）の正確な順序付けは、必要でないことに留意することが重要である。順序付け要件は、表によるのであって、特定の表に対する個々の変更によるのではない。したがって、行４１０および４３５（およびEmployee表に対する他の更新）の間の順序付けは、重要でない。
【００５１】
行４１５の更新動作は、図９では、本発明に従って、更新が挿入の後、削除の前に実行されることを示すために、行４２０、４１０、および４３５の挿入動作の後に現れる。複数の更新の間の順序付け（複数の更新は例に示されてはいないが）は不要である。
【００５２】
順序付けられた変更の最後のグループが、削除である。図８の未ソート変更リストには、３つの削除の行４２５、４３０、および４４０が含まれる。データベースから行を削除する時には、問題の外部キーが、行を挿入する時と異なる。行を削除するためには、削除される行の主キーを外部キーとして指定している他の表の行が存在することができない。図８では、星印を使用して、この依存性を示す。たとえば、行４２５では、部署番号Ｅ３１を有する部署が、Department表３１０から削除される。図３ないし７の残りの表を検査することによって、Employee表３２０が、外部キー列３２７としてＥ３１を使用する行３２４を有することがわかる。したがって、行４２５の列４０８および４０９は、この削除動作がEmployee表３２０の従業員００３２０の行に依存することを意味する目的のものであり、したがって、削除動作を実行すると、データベースの参照保全性制約に違反することになる。しかし、従業員００３２０の従業員レコードを先に削除する場合、部署Ｅ３１の削除は、この違反をもたらさない。図８の行４３０は、この従業員の削除を指定するものであり、したがって、本発明の方針に基づく順序付け動作によって、これら２つの削除の間の順序が、図９の順序付けられた行４３０、４２５に示されているように変更される。しかし、従業員００３２０の行の削除は、それ自体の制約違反を引き起こすはずである。行４３０の列４０８および４０９に示されているように、この従業員００３２０は、Address表３４０からの行との依存性関係を有する。というのは、行３４１が、（主キー値ＡＤ００１を使用して）その外部キー列３４７からこの従業員を参照しているからである。図８の行４４０は、この住所の行３４１の削除動作である。図３ないし７の表のどの行も、この住所の行３４１に依存しないので、列４０８および４０９は、この削除動作の行４４０に関する前提条件がないことを示すために空白のままにされていた。したがって、３つの削除動作の最終的な順序は、図９に示されているように４４０、４３０、４２５であり、この順序は、Address表、Employee表、およびDepartment表の間の関係に基づいて判定された。
【００５３】
Employee表、Address表、およびDepartment表を、図３ないし７のデータベースの例からのサブセットと見なし（残りの表と外部キーを無視し）て、図１０に、これらの表の間の順序付けが本発明に従ってどのように実行されるかを示す。図８および図９の例の動作に関して述べたように、外部キー列３２７および３４７のゆえに、これらの表の間に依存性関係が存在する。挿入に関する参照する表／参照される表の順序を使用して、本発明は、挿入に関する正しい順序付けが、まずDepartment５１１、次にEmployee５１２、最後にAddress５１３であると判定する。削除に関する参照する表／参照される表の順序を使用すると、これらの表の順序は、Address５２１、Employee５２２、およびDepartment５２３に逆転する。図１０には、表ごとに３つの動作リストが作成されることも示されている。Employee表５０１に対して実行される変更に関して、３つのリストは、挿入される従業員情報のすべてを含むリスト５３１、従業員更新に関するリスト５３２、および削除される従業員に関するリスト５３３である。類似するリスト５４１ないし５４３および５５１ないし５５３が、それぞれAddress表５０２およびDepartment表５０３について作成される。個々のリスト内では、順序付けは不要であり、これによって、本発明の動作が、参照保全性を維持するための非常に効率的な解決策になる。
【００５４】
図１１および図１２に、それぞれ、図３ないし７の例のデータベースの５つの表の組全体およびそれらの図に示された外部キー関係のすべてを使用して実行される挿入順序付けおよび削除順序付けを示す。アプリケーション・プログラムが、これらの図の左欄に示された順序で動作のグループを作成し、Address表に影響する動作（６０１）が最初であり、Employee表に対する動作（６０２）、Department表に対する動作（６０３）、Spouse表に対する動作（６０４）、およびCompany表に対する動作（６０５）が続くと仮定する。矢印６１１ないし６１４は、図３ないし７の例による、これらの表の間の外部キー関係を示す。検査からわかるように、本発明の参照する／参照される規則は、挿入動作を適用する表順序が、Company６２１、Department６２２、Spouse６２３、Employee６２４、およびAddress６２５であることを必要とする。図１２の右欄に示された削除順序では、これらの表が逆の順序で配置される。
【００５５】
本発明の順序付け技法の好ましい実施形態を実施するのに使用することができる論理を、図１３ないし１８と、図１０の例の表に関して詳細に説明する。この説明では、行われる変更（挿入、更新、および削除）を、情報の「タプル」と称する。
【００５６】
図１３に、本発明の順序付け技法の好ましい実施形態の主高水準フローの論理を示す。処理は、ブロック７００で開始され、ここで、挿入に使用される表順序が判定される。この処理を、図１４で詳細に説明する。図１０を参照すると、ブロック７００で、挿入順序付け情報であるDepartment５１１、Employee５１２、およびAddress５１３が作成される。次に、削除に使用される表順序を判定する（ブロック７１０）が、この削除順序付けは、図１４の論理によって説明する。これによって、図１０の削除順序付け情報であるAddress５２１、Employee５２２、およびDepartment５２３が作成される（明白なとおり、ブロック７００およびブロック７１０を実行する順序は、結果を変更せずに逆転することができる）。その後、アプリケーション・プログラムによって作成されたタプルを、表および動作タイプによってクラスタ化する（ブロック７２０）。図１７で、この処理を詳細に説明する。図１０の図を参照すると、ブロック７２０のクラスタ化では、タプルが適当なリスト５３１ないし５３３、５４１ないし５４３、または５５１ないし５５３に置かれる。これらのリストは、リンク・リスト構造を使用して作成されることが好ましい。参照保全性制約に違反しないようにタプルが順序付けられたので、ブロック７３０、７４０、および７５０で、データベースでの行の挿入、更新、および削除の動作を（この特定の順番で）適用する。図１３には、ブロック７２０ないし７５０が１回だけ行われるものとして図示されているが、特定のアプリケーションのための実施形態で、これらのブロックの反復繰り返しを選択することができることに留意されたい。たとえば、対話的に変更を行うユーザによって駆動されるアプリケーションは、そのアプリケーションが終了するまで、制御が図１３のブロック７５０からブロック７２０に返されるようにして、データベースに対する生成された変更を周期的に適用することができる。もう１つの例として、トランザクション指向アプリケーションと共に使用される時に、ブロック７２０ないし７５０の処理を、各トランザクションの完了時に実行して、トランザクションの有効範囲中に生成された変更を適用することができる。図１３を変更してこの代替反復手法を実施する方法は、当業者には明白であろう。
【００５７】
各動作タイプの個々のタプルについて、変更の適用を、従来技術の技法を使用して実行することができ、したがって、ブロック７３０、７４０、および７５０の論理を詳細に説明しなかったことに留意されたい。すなわち、挿入動作が表によって正しく順序付けられた後に、各挿入を、既存の技法を使用して順番に適用することができ、更新および削除についても同様である。本発明の長所は、複数の動作が１回でデータベースに書き込まれるバッチモード記憶動作を実行することができることである。バッチモード書込機能は、従来技術に存在するが、参照保全性制約を有するデータベース表と共に使用されることはほとんどない。というのは、従来技術に、制約に違反しないように表の任意のグループに関して複数の書込動作を順序付ける方法を計画的に決定する技法がないからである（また、表の特定の組に関する順序付けを実施する論理を手作業でコーディングすることが、極端に難しく、誤りをおかしやすいからである）。
【００５８】
図１４の論理は、本発明による、参照保全性制約に違反しない、正しい表順序付けを判定するのに使用される論理の好ましい実施形態を示すものである。図１５に、図１４が図１３のブロック７００から呼び出される時に使用される、挿入動作に関する表の優先順位を判定するアルゴリズムを示す。図１６に、図１４がブロック７１０から呼び出される時に使用される、削除動作に関する表の優先順位を判定するのに使用される同様のアルゴリズムを示す。これらの異なるアルゴリズムは、たとえば図１４の論理が挿入の処理または削除の処理のどちらのために呼び出されたかを示すフラグをセットすることによって、ブロック８３５から選択的に呼び出されることが好ましい（その代わりに、図１４の論理を、挿入と削除について複製することができ、この場合には、図１５および図１６の論理を、適用可能なコピーに組み込むことができる）。
【００５９】
図１４の処理は、変更が適用される入力表の順序付けられていないリストから開始される（この情報は、生成されたタプルまたはデータベース・スキーマの知識から抽出することができる）。図１０の図を参照して、元の未ソート表順序が、Employee表５０１、Address表５０２、およびDepartment表５０３であると仮定する（上で述べたように、挿入に関する結果の順序は、Department５１１、Employee５１２、およびAddress５１３になり、削除に関する結果の順序は、５２１、５２２、および５２３になる）。ブロック８００で、この順序付けられていない入力リストの最初の表を指すように現行表ポインタをセットする。ブロック８０５で、この表の識別子を、図１４の出力として生成される（当初は空である）順序付けされたリストの末尾に追加する。図１０の例では、現行ポインタは、Employee表を指し、順序付けられていないリストには、Address表およびDepartment表だけが含まれ、順序付けされたリストに、Employee表が含まれる。
【００６０】
ブロック８１０で、現行表が関係を有するかどうかを検査する。本明細書で使用する「関係」は、現行表内に存在するものとして定義された外部キーならびに他の表内で定義され、現行表を参照する外部キーを指す。したがって、現行のEmployee表について、２つの関係すなわち、Departmentとの１つの関係およびAddressとの１つの関係があり、したがって、ブロック８１０は、肯定の結果を有する。制御はブロック８３０に移り、ここで、現行データベース・スキーマの表に関する関係リスト（図１４では「ｒ．ｓ．リスト」と称する）から、現行表を含む最初の関係を得る。この関係リストは、順序付けられないものとすることができ、特定のスキーマで表の間の関係を判定するための、当技術分野で既知の技法を使用して得ることができる。図１８に、図１０の表および関係に対応するスキーマを示す。図１８では、第１の関係１２０５、１２０６が、表１２００の列１２０３と表１２２０の列１２２２の間で定義され、第２の関係１２１０、１２１１が、表１２００の列１２０１と表１２３０の列１２３２の間で定義されている。
【００６１】
現行表に関する関係がない時には、評価する必要がある順序付け制約がなく、したがって、制御は、単純にブロック８１０からブロック８１５に移る。これによって、この表の詳細な順序付け論理の動作がバイパスされ、この表は順序付けされた出力リストのこの位置にとどまる。
【００６２】
この例では、Employeeを含む最初の（したがって現行の）関係が、Employee（「現行」表）とDepartment（したがって「関係する」表）の間の関係であると仮定する。その場合、ブロック８３５が、挿入動作と削除動作のどちらを実行するかに応じて図１５または図１６の論理を呼び出して、現行表が現行の関係に対する優先順位を有するかどうかを判定する。
【００６３】
挿入処理が実行される場合には、次に図１５のブロック９００を実行する。ブロック９００では、現行関係が制約を有するかどうかを尋ねる。例のEmployee対Department関係の場合、部署番号に対する制約（外部キー列３２７を使用する）がある。したがって、ブロック９００は肯定の結果を有し、制御はブロック９２０に移る（制約がない時には、ブロック９００は否定の結果を有し、ブロック９１０で、図１４の呼出し元論理に否定の回答を返す）。その後、ブロック９２０で、関係する表が現行関係に関して外部キーを有するかどうかを検査する。この例では、外部キーは、現行表であるEmployee表内にあり、関係するDepartment表内にはなく、その結果、ブロック９２０は否定の結果を有する。結果が否定の時には、ブロック９４０で、ブロック８３５に否定の回答を返す（そうでない場合には、ブロック９３０で肯定の回答を返す）。
【００６４】
比較からわかるように、図１６の削除処理は、図１５の挿入処理とほとんど同一である。削除処理でも、現行関係の制約があるかどうかを検査し（ブロック１０００）、ない場合にはブロック８３５に否定の回答を返す。しかし、ブロック１０２０のテストでは、ブロック９２０で現行関係の外部キーが関係する表内にあるかどうかを尋ねたのに対して、現行関係の外部キーが、現行表内にあるかどうかを尋ねる。したがって、順序付けられていないEmployee表５０１、Address表５０２、およびDepartment表５０３に関する削除処理を実行し、Employee対Department関係を評価する（図１５に関して上で説明した）時には、ブロック１０２０は、この関係によって使用される外部キー列３２７が、現行（Employee）表内に存在するので、肯定の結果を有する。図１６の残りの論理は、図１５の論理と同一である。
【００６５】
ここで図１４のブロック８３５の処理に戻って、図１５（削除を処理する時には図１６）から否定の回答が返される場合には、制御はブロック８４０に移り、現行表のすべての関係をすでに処理したかどうか（すなわち、関係リストの終りに達したかどうか）を検査する。そうでない場合には、制御はブロック８６０に移る。Employee対Department関係では、挿入処理に関して否定の結果が返されるので、この例では、ブロック８３５に制御が戻った後にブロック８４０が実行される。ブロック８４０は、この時点で否定の結果を有する。というのは、現行Employee表を含むもう１つの関係があるからであり、その関係は、Employee表とAddress表の間の関係である。したがって、ブロック８４５で、関係リストからこの関係を得、その後、ブロック８３５で、現行表がこの特定の関係で優先順位を有するかどうかを判定する。挿入処理についてもう一度図１５を参照すると、現行のEmployee対Address関係は制約を有し、したがって、ブロック９００のテストが肯定の結果を有する。この場合、評価される関係で、Address表３４０の外部キー列３４７が使用されている。Address表は、図１５のこの呼出しでの関係する表であり、したがって、ブロック９２０が肯定の結果を有し、ブロック９３０でブロック８３５に肯定の回答が返されることになる。
【００６６】
もう一度ブロック８３５に戻って、この例の第２の関係評価に関して返される肯定の結果が、ブロック８６０への制御の移動を引き起こす。ブロック８６０では、関係する表が、作成中の順序付けられたリストにすでに含まれるかどうかを尋ねる。この例では、この時点で、順序付けられたリストにEmployee表だけが含まれ、関係するAddress表は含まれないので、ブロック８６０は否定の結果を有し、制御はブロック８４０に戻る。ブロック８４０では、関係リストに、まだ評価されていない現行表に関する関係があるかどうかをもう一度検査する。評価すべき関係がない場合、この例ではこの時点でそうなるが、制御はブロック８１５に移り、図１４によって使用されているスタックが空であるかどうかを検査する。まだスタックに何もプッシュしていないので、このテストはこの例では肯定の結果を有し、処理はブロック８２０で継続される。ブロック８２０では、順序付けられていないリストが空であるかどうかを訪ねるが、これは、そのリストが完全に処理された時に真になる。このテストの結果が肯定である場合には、図１４の動作は、それが呼び出された目的である挿入処理または削除処理に関して完了し、制御は図１３の呼出し元論理に戻る。
【００６７】
ブロック８２０が否定の結果を有する時には、順序付けられていない入力リストから処理しなければならない表がまだある。したがって、ブロック８２５で、順序付けられていないリストからの次の表を指すように現行表ポインタをセットし、ブロック８０５で、順序付けられていないリストから、作成中の順序付けられた出力リストの末尾へ表を移動する。この例では、現行表ポインタが、Address表を指し、順序付けられていないリストに、Department表だけが含まれ、順序付けられたリストに、Employee表およびAddress表が含まれる（当業者に明白であるように、本明細書でのあるリストから別のリストへの「表の移動」への言及は、表の識別子の移動、またはこれと同等に、表へのポインタまたは表の識別子の移動の短縮表記を意図するものである）。現行表（Address）は、Employee表に対する単一の関係を有し、したがって、ブロック８１０は、肯定の結果を有する。ブロック８３０、８３５、８４０、８１５、および８２０が、前に説明したように実行され、ブロック８３５での呼出しから図１５のブロック９００、９２０、および９４０が実行され、否定の結果が返される。ブロック８２０は、この例ではやはり否定の結果を有し、ブロック８２５で、順序付けされないリストの次の表（最後の表でもあるDepartment）を指すように現行表ポインタをセットする。その後、ブロック８０５をもう一度実行し、Department表を順序付けされたリストの末尾に移動する。したがって、順序付けされないリストは空になり、順序付けられたリストにはEmployee、Address、およびDepartmentが含まれる。
【００６８】
Department表について、Employeeとの１つの関係とAddressとの１つの関係の２つの関係が存在する。したがって、ブロック８１０は、肯定の結果を有する。Department対Employeeの関係を評価する時に、ブロック８３５は、肯定の結果を有し、処理はブロック８６０に達する。ブロック８６０は、関係する表（Employee）がすでに順序付けられたリストにあるので、やはり肯定の結果を有する。したがって、ブロック８６５で、図１４のために使用されるスタックに現行表（Department）をプッシュし、ブロック８７０で、現行表ポインタを変更し、その結果、現行表ポインタが、関係する（Employee）表を指すようになる。ブロック８０５は、現行（Employee）表を、順序付けられたリスト内のその既存の位置から順序付けられたリストの末尾に移動し、これは、スタックにプッシュされたばかりの表と現行表の間の関係に従ってリストを順序付けるという効果を有する。この例では、この時点で、順序付けられたリストにAddress、Department、およびEmployeeが含まれ、Employeeは、リスト内でDepartmentより後の位置（したがって、挿入に関するより低い優先順位）に移動されている。
【００６９】
その後、ブロック８１０、８３０、および８３５をもう一度実行し、今回は、Employee対Department関係を評価し、図１５から否定の結果が返される。その後、ブロック８４０および８４５を実行し、Employee対Address関係を得る。この関係について、ブロック８３５は、肯定の結果を有し、制御は再びブロック８６０に達する。ブロック８６０では、関係するAddress表がすでに順序付けられたリストにあることが検出され、したがって、ブロック８６５で、現行Employee表がスタックにプッシュされる（スタックには、EmployeeとDepartmentが含まれる）。その後、ブロック８７０および８０５で、Address表が、順序付けられたリストの一番前の既存の位置から移動されて、リストの末尾の最後の項目になる。この例の順序付けられたリストは、図１０のDepartment５１１、Employee５１２、およびAddress５１３に示されているように、挿入に関して正しい順序になっている。
【００７０】
図１４の処理が、この例に関して終了する形を、これから手短に説明する。Address対Employee関係が評価され、ブロック８３５で否定の結果を有する。これはAddressに関する唯一の関係なので、ブロック８４０からブロック８１５に制御が移される。この時点で、スタックには２つの項目があり、したがって、制御はブロック８１５からブロック８５０に移され、ここで、一番上の要素（Employee）をポップし、現行表にする。制御はブロック８４０に戻り、ここで、Employeeに関するすべての関係が、Employeeがスタックにプッシュされた前の処理サイクル中にすでに処理されていることが判定される。しかし、スタックのプッシュ動作が、現行表の最後の関係でない関係のゆえに発生した場合には、ブロック８４０が、否定の結果を有し、制御はブロック８４５に移って、その表の残りの関係の処理を開始する。Employeeについて評価すべき関係がもうないことの検出によって、制御が再びブロック８１５に移り、次にブロック８５０に移り、ここで、Department表が、スタックからポップされ、現行表にされる。Employeeと同様に、Departmentは、その最後の関係の評価中にスタックにプッシュされたので、ブロック８４０は、肯定の結果を有し、制御は再びブロック８１５に達する。スタックはこの時空なので、制御はブロック８２０に移り、順序付けられていないリストが空であることが検出される。その後、制御は図１３のブロック７００に戻り、任意のデータベース・スキーマの表に関する正しい挿入順序が、計画的に決定されている。
【００７１】
図１４に示した順序付けアルゴリズムは、通常はネットワーク構造を形成する、表の間の関係情報をとりあげ、関連する情報のフラット化された順次表現を生成するのに使用することができる手法の１つにすぎないことに留意されたい。テーブルの対の間の、関係全体ではなく制約だけを考慮することによって、このネットワークを木として扱うことができる。したがって、循環が存在することが不可能になる。図１４で説明した手法は、木をフラット化されたリストに変換する比較的単純直裁な技法であり、したがって、好ましい実施形態として使用される。その代わりに、本明細書で開示される発明的概念から逸脱せずに、木をフラット化されたリストに変換する他の手法を使用することができる。たとえば、上で説明したように、２つの表の間の順序付けを実施するために、表を順序付けられたリストの末尾に移動するのではなく、表が、それが依存する表の直後になるように表を移動する、より複雑な手法を使用することができる。
【００７２】
ブロック７００および７１０が完了した後に、挿入順序付けおよび削除順序付けが決定されている。本発明が、前に述べたように部分的に前処理ステップとして使用され、部分的に実行時に使用される時には、前処理に、この順序付けの決定が（まず、前に述べた従来技術の技法を使用して、対象のスキーマの表および関係を判定した後に）含まれる。クラスタ化処理（その次に図１３のブロック７２０から呼び出されるものとして図示）およびデータベースを変更するためにアプリケーション・プログラムによって生成されたタプルを適用するための動作の実行（ブロック７３０ないし７５０）は、実行時に行われる（または、変更のクラスタ化および適用を、アプリケーションがその実行時処理を完了した後に適用することができる）。
【００７３】
図１７に移って、本発明の好ましい実施形態によって、タプルを適当なリスト（図１０の５３１ないし５３３、５４１ないし５４３、または５５１ないし５５３など）に入れるのに使用されるクラスタ化技法を説明する。この処理に入る際に、データベースに対して行われる変更を表すタプルの順序付けられていないリストが、アプリケーション・プログラムによって作成されている。たとえば、トランザクション指向アプリケーションと共に使用される時には、この論理を、各トランザクションの完了時に呼び出して、前に説明したように、トランザクションの有効範囲中に生成された変更を実行することができる。その場合には、タプル・リストが、そのトランザクションに関する変更を表す。または、図１７の論理が、アプリケーションが完了した時に限って呼び出される場合には、タプル・リストに、アプリケーションの全有効範囲中に生成されたすべての変更が含まれる。
【００７４】
ブロック１１００で、タプル・リストから最初の要素を得、ブロック１１１０で、このタプルによって影響される表（すなわち、タプルでその主キー値が指定されている表）を判定する。ブロック１１４０で、タプルが挿入動作に関するものであるかどうかを尋ねる。そうである場合には、ブロック１１５０で、ブロック１１１０で決定された表の挿入リストにタプルを追加する。そうでない場合には、ブロック１１６０で、タプルが削除動作に関するものであるかどうかを尋ねる。この場合、ブロック１１７０で、適当な表の削除リストにタプルを追加し、そうでない場合には、ブロック１１８０で、適当な表の更新リストにタプルを追加する。前に述べたように、本発明の長所は、特定の表についてリスト内の順序付けが不要であり、したがって、図１７のクラスタ化論理が高速かつ効率的であることである。タプルを適当なリストに追加した後に、制御はブロック１１３０に達し、ここで、すべてのタプルを処理したかどうかを調べるために検査する。そうである場合には、図１７の処理が完了し、制御は呼出し元の論理（図１３のブロック７２０）に戻る。そうでない場合には、ブロック１１２０で、タプル・リストから次の要素を得、ブロック１１３０が否定の結果を有するまで、説明した形で各タプルを適当なリストに追加する処理を継続する。
【００７５】
上で示したように、本発明は、任意のリレーショナル・データベースに対して実行される動作を計画的に順序付けると同時に、そのデータベースの表の間の参照保全性を自動的に維持する、効率的な技法を提供する。この技法は、データベース・エンジン自体で使用することができる。アプリケーションは、アプリケーション自体の変更を必要とせずに、方針に基づく順序付け技法を有利に利用することができる。Enterprise JavaBeansと共に使用される時には、この技法によって、コンテナをパーシスタンス機構から独立にすることが可能になり、コンテナがパーシスタンス実現方法の詳細を知る必要がなくなる。さらに、変更タプルが、本発明を使用する時に表によってクラスタ化されるので、特定の表に対して実行されるすべての変更を知ることが可能になる（この「ビッグ・ピクチャ」ビューが使用可能でない従来技術の技法と対照的に）。この技法では、バッチ書込動作の使用も可能になり、従来技術で一般的な手法（すなわち、書込の間の順序を解決するという複雑な問題を避けるためにデータベース・エンジンに各書込動作を別々に送る手法）と比較して、非常に改善された性能がもたらされる。バッチ書込動作を使用する時には、ネットワーク・ラウンドトリップの数を、再悪条件シナリオの（３×表の数）まで減らすことができる。ここで、３は、異なる動作タイプの数を表す（１タイプの動作だけが実行される時には、ラウンドトリップの数を、影響される表の数まで減らすことができる）。
【図面の簡単な説明】
【図１】本発明を実践することができるコンピュータ・ワークステーション環境のブロック図である。
【図２】本発明を実践することができるネットワーク接続されたコンピュータ環境を示す図である。
【図３】従来技術による、リレーショナル・データベース表に記憶されたデータ値の簡単な例を示す図である。
【図４】従来技術による、リレーショナル・データベース表に記憶されたデータ値の簡単な例を示す図である。
【図５】従来技術による、リレーショナル・データベース表に記憶されたデータ値の簡単な例を示す図である。
【図６】従来技術による、リレーショナル・データベース表に記憶されたデータ値の簡単な例を示す図である。
【図７】従来技術による、リレーショナル・データベース表に記憶されたデータ値の簡単な例を示す図である。
【図８】図３ないし７の記憶されたデータに対して行われる変更の簡単な例を示す図である。
【図９】図３ないし７の記憶されたデータに対して行われる変更の簡単な例を示す図である。
【図１０】本発明に従って実行される表順序付けの例を示す図である。
【図１１】本発明に従って実行される表順序付けの例を示す図である。
【図１２】本発明に従って実行される表順序付けの例を示す図である。
【図１３】これによって本発明の好ましい実施形態を実施することができる論理を示す流れ図である。
【図１４】これによって本発明の好ましい実施形態を実施することができる論理を示す流れ図である。
【図１５】これによって本発明の好ましい実施形態を実施することができる論理を示す流れ図である。
【図１６】これによって本発明の好ましい実施形態を実施することができる論理を示す流れ図である。
【図１７】これによって本発明の好ましい実施形態を実施することができる論理を示す流れ図である。
【図１８】従来技術によるデータベース・スキーマのために使用可能な関係情報を示す図である。
【符号の説明】
１２  マイクロプロセッサ
１６  ユーザ・インターフェース・アダプタ
１８  キーボード
２０  マウス
２２  インターフェース装置
２４  ディスプレイ装置
２６  ディスプレイ・アダプタ
２８  メモリ
３０  記憶装置
【図１】
0003670975.tif 000002
【図２】
0003670975.tif 000003
【図３】
0003670975.tif 000004
【図４】
0003670975.tif 000005
【図５】
0003670975.tif 000006
【図６】
0003670975.tif 000007
【図７】
0003670975.tif 000008
【図８】
0003670975.tif 000009
【図９】
0003670975.tif 000010
【図１０】
0003670975.tif 000011
【図１１】
0003670975.tif 000012
【図１２】
0003670975.tif 000013
【図１３】
0003670975.tif 000014
【図１４】
0003670975.tif 000015
【図１５】
0003670975.tif 000016
【図１６】
0003670975.tif 000017
【図１７】
0003670975.tif 000018
【図１８】
0003670975.tif 000019