(57)【特許請求の範囲】
【請求項１】
トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムであって、
入力された複数のトランザクションに対してトランザクションの実行順を決定するトランザクション実行順決定手段と、
前記複数のトランザクションが同一のデータ項目に対して処理を行う場合、そのデータ項目に対する枝を作成し、先に処理を行うトランザクションの接点から次に処理を行うトランザクションの接点にその枝を入力して、前記トランザクションの実行順にデータを更新することを示した先行グラフを作成する先行グラフ作成手段と、
前記複数のトランザクションに含まれる部分処理をタスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記トランザクションの実行順に、前記データベースのアクセス領域ごとにグループ分けするグループ分け手段と、
前記グループ分けして作成したグループを用いて合成トランザクションを作成する合成トランザクション作成手段と、
前記合成トランザクションに含まれる個々のグループに対してマルチオペレーション・プロセッシングを用いて処理を行うマルチオペレーション・プロセッシング手段と
を備え、
前記マルチオペレーション・プロセッシング手段は、グループ分けされたタスクがアクセスするアクセス領域内のブロックを調べ、グループ内のタスクが並んでいる順に該ブロックへのアクセス順を決定し、決定したアクセス順に該ブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出し、ブロック内のデータ項目に対して、グループ内のタスクが並んでいる順にタスク処理を順次行い、グループ分けされたタスクの処理が終了し、グループ分けされたタスクを包含するトランザクションの処理が終了すると、その時点で終了したトランザクションをコミットするかどうかを、前記先行グラフの終了したトランザクションの接点に入力枝が存在するかどうかで決定し、該トランザクションの接点に入力枝が存在しない場合は、該トランザクションをコミットし、該トランザクションの接点とその接点から出ているすべての枝を削除し、
ブロック内のデータ項目に対して、グループ内のタスクが並んでいる順にタスク処理を順次行っていくということは、ブロック内のデータ項目が前記先行グラフに存在する場合、そのデータ項目に対して前記先行グラフに示したトランザクションの実行順にトランザクションの部分処理であるタスクの処理を順次行っていくことであり、
複数のタスクがそのデータ項目に対して更新処理を行う場合、そのデータ項目に対して最初のタスクの更新処理を行い、更新されたデータ項目に対して次のタスクの更新処理を行い、このような更新処理を繰り返し、最後のタスクの更新処理が行われると、最後に更新された更新結果だけをデータベースに書き込む
ことを特徴とするトランザクション処理システム。
【請求項２】
請求項１に記載のトランザクション処理システムにおいて、
２相ロック・プロトコル又はタイムスタンプ・プロトコルを用いて複数の合成トランザクションの処理を同時に並行して実行することを特徴とするトランザクション処理システム。
【請求項３】
請求項１又は２に記載のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項４】
請求項１又は２に記載のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースのトランザクション同時実行制御に関し、特に、複数のトランザクションが同時に同一のアクセス領域に対して更新処理を行う場合に関するものである。
【背景技術】
【０００２】
データベース・マネージメント・システムは、複数のユーザーからネットワークを経由して入力される数多くのトランザクションの処理を同時に並行して実行している。しかし、複数のトランザクションが同時に、同一のデータ項目に対して処理を行うと、データの矛盾が発生する場合があるため、データベース・マネージメント・システムは、データの矛盾が起こらないようにするために、トランザクションの同時実行制御を用いて、複数のトランザクションの処理を行っている。
【０００３】
＜直列可能スケジュール＞
複数のトランザクションをデータの矛盾が起こることなく処理するにあたって、最も簡単な手法は、トランザクションを１つずつ順番に処理していくことである。この手法は直列スケジュール(serial schedule)と呼び、１つのトランザクション処理が完全に終了してからでないと、次のトランザクションの処理を始めない手法である。しかし、この手法は、複数のトランザクションの処理を同時に平行して行うことができないため、１つのトランザクションがディスクへのＩ／Ｏ処理を完了するまで待っている間、ＣＰＵ処理を他のトランザクションに切り替えることができないなど、重要なＣＰＵ処理時間を無駄にすることになる。
そのため、複数のトランザクションを、データの矛盾が起こることなく、同時に平行して実行するには、直列可能スケジュール（serializable schedule）という手法が用いられる。
【０００４】
直列可能スケジュールを行うには、各トランザクションが処理を行うデータ項目に対してロックをかける手法が用いられる。ロックには、共有ロックと専有ロックがある。共有ロックは、トランザクションがデータを読み取るためだけにかけるロックである。１つのトランザクションがあるデータ項目を読み取るために共有ロックをかけると、他のトランザクションは、そのデータ項目を読み取ることはできるが、更新や削除することは、その共有ロックが解除されるまでできない。専有ロックは、データを更新するときにかけるロックである。１つのトランザクションがあるデータ項目を更新するために専有ロックをかけると、他のトランザクションは、その専有ロックが解除されるまで、そのデータ項目を更新、削除、及び読み取ることはできない。
ただし、ロックを用いただけでは、ロックをかける順番によっては、複数のトランザクション間でデータの矛盾が発生する場合がある。そのため、複数のトランザクションが同一のデータ項目に対してロックをかける場合、ロックをかけた順番に、それらのトランザクションに対して従属グラフを作成する手法が用いられる。従属グラフにサイクルが存在する場合は、複数のトランザクション間でデータの矛盾が発生したことになり、すべてのトランザクションの処理を中断し、中断したトランザクションの処理を再度始めから行うことになる。なお、従属グラフにサイクルが存在しない場合は、すべてのトランザクションの処理が矛盾なく実行されたことになる。
しかし、この手法だと、従属グラフにサイクルが発生する度に、トランザクションの処理が繰り返して中断されるため効率的ではない。また、何度もトランザクションの処理を繰り返しても直列可能スケジュールで行われない場合もある。そのため、直列可能スケジュールを保障するプロトコルとして、二相ロック・プロトコル、楽観的ロック・プロトコル、タイムスタンプ・プロトコル、マルチバージョン・プロトコルなどが用いられる。
【０００５】
(1)二相ロック・プロトコル
二相ロック・プロトコルは、各トランザクションの中のロック操作を、ロックをかける操作だけからなる成長相(growing phase)と、ロックをはずす操作だけからなる縮退相(shrinking phase)の２つの部分に分離して行う。したがって、ロックを解除した後に、再びロックをかけることは許されない。また、成長相ではロックをかける操作以外にロックのアップグレードが許され、縮退相ではロックを解く操作以外にロックのダウングレードが許される。直列可能スケジュールを行うには、すべてのトランザクションが二相ロック・プロトコルに従う必要がある。
【０００６】
二相ロック・プロトコルは、複数のトランザクションがお互いに必要なロックをかけて、どのトランザクションも処理できなくなると、デッドロックが発生することがある。デッドロックをはずすには、ロックをかけているトランザクションの１つを中断してロールバックし、中断したトランザクションをトランザクション同時処理ステムに再提出する。また、中断したトランザクションが書き込んだデータを別のトランザクションが使用していた場合、その別のトランザクションも中断してロールバックすることになる。このように、１つのトランザクションが中断することによって、いくつものトランザクションが連鎖的にロールバックすることを連鎖的ロールバック(cascading rollback)と呼ぶ。連鎖的ロールバックが起こらないようにするには、厳格な二相ロック・プロトコルという手法を用いる。この手法は、二相ロック・プロトコルの縮退相における最初のロックをはずす操作はトランザクションがコミットまたは中断(abort)した後であるという条件をさらに付け加えたものである。この手法を用いると、連鎖的ロールバックは起こらなくなるが、個々のトランザクションがロックをかけておく時間が長くなる。
【０００７】
<二相ロックの問題点>
二相ロック・プロトコルは、同時に処理するトランザクションの数が増えると、複数のトランザクションの間でロックをかけるために競合が起こり、デッドロックが起こりやすくなる。その結果、デットロックをはずすために数多くのトランザクションが中断してロールバックすることになり、トランザクションの処理速度を低下させることになる。
二相ロック・プロトコルは、複数のトランザクションが同時に、同じデータ項目に対して処理を行う必要がある場合、個々のトランザクションごとに、そのデータ項目に対して何度も繰り返してロックをかけることになる。そして１つのトランザクションがあるデータ項目に対してロックをかけている間、そのデータ項目に対して処理を行う他のトランザクションは、そのロックが解除されるまで待たされることになる。
【０００８】
二相ロック・プロトコルは、個々のトランザクションに対して、オペレーティング・システムのプロセスを用いて処理を行っている。１つのトランザクションが、あるデータ項目に対してロックをかけた状態で、オペレーティング・システムによるプロセスの切り替えが起こると、ロックされたそのデータ項目に対して処理を行う他のトランザクションは、CPU（マイクロプロセッサ)で処理される時間を得ても、そのデータ項目に対してロックをかけることができないため、何も処理を行うことができないまま、再びプロセスの切り替えが起こる。同時に処理するトランザクションの数が増えると、このような状態が繰り返して起こるようになり、トランザクションの処理速度を著しく低下させることになる。
【０００９】
(2) 楽観的ロック・プロトコル
楽観的ロック(optimistic locking protocol)は、トランザクションを実行するのに競合がないものと仮定して処理を行い、トランザクションが終了するときに、競合があったかどうかを確認し、競合があったならば、トランザクションを中断してロールバックする。競合がなかったならば、その時点でデータを書き込むデータ項目に対してロックをかけ、書き込み処理を実行し、トランザクションをコミットする。この手法はトランザクションの処理が行われている間、ロックをかけたままの状態にしておく必要がなく、ロックをかけておく時間はトランザクションがコミットする前の短い時間だけですむ。
【００１０】
<楽観的ロック・プロトコルの問題点>
楽観的ロック・プロトコルも二相ロック・プロトコルと同様に、同時に処理するトランザクションの数が増えると、データを更新するために競合するトランザクションの数が増え、中断してロールバックするトランザクションの数も増えるといった問題点がある。
【００１１】
(3) タイムスタンプ・プロトコル
タイムスタンプ・プロトコルは、複数のトランザクションを同時に並行して処理するにあたって、個々のトランザクションにタイムスタンプ（到着時間)を与え、タイムスタンプの小さい(到着時間の早い)トランザクションからタイムスタンプの大きい(到着時間の遅い)トランザクションへと順番に実行していく手法である。そのためには、トランザクションが処理を行う個々のデータ項目に対して、読み込みタイムスタンプと書き込みタイムスタンプを与えて、次の規約に従ってトランザクション処理を行う。
【００１２】
当面のトランザクションが、あるデータ項目に対して読み込む処理を行うとき、当面のトランザクションのタイムスタンプとそのデータ項目の書き込みタイムスタンプを比べ、当面のトランザクションのタイムスタンプの方が小さければ、当面のトランザクションが読み込むべきデータ項目の値がすでに失われているので、当面のトランザクションを中断する。それ以外のときは、当面のトランザクションの処理を実行し、そのデータ項目の読み込みタイムスタンプに、当面のトランザクションのタイムスタンプを与える。
【００１３】
当面のトランザクションが、あるデータ項目に対して書き込み処理を行うとき、当面のトランザクションのタイムスタンプとそのデータ項目の読み込みタイムスタンプを比べ、当面のトランザクションのタイムスタンプの方が小さければ、当面のトランザクションが書き込み処理を行ったあとのデータ項目の値を読み取るべきトランザクションが、先にそのデータ項目を読み取ってしまっているので、当面のトランザクションを中断する。また、当面のトランザクションが、そのデータ項目の読み込みタイムスタンプよりも大きく、そのデータ項目の書き込みタイムスタンプよりも小さければ、当面のトランザクションは、書き込み処理の時機を逸しているので中断する。それ以外のときは、当面のトランザクションを実行し、当面のトランザクションのタイムスタンプの方がそのデータ項目の書き込みタイムスタンプよりも大きければ、そのデータ項目の書き込みタイムスタンプに、当面のトランザクションのタイムスタンプを与える。
なお、中断したトランザクションは、ロールバックし、トランザクション処理システムに再提出し、新たなタイムスタンプが与えられることになる。
【００１４】
タイムスタンプ・プロトコルは、中断されるトランザクションの数を減らすために、トーマスの書き込みルール(Thomas's write rule)という手法を用いることができる。この手法は、トランザクションがあるデータ項目に書き込み処理を行うとき、当面のトランザクションのタイムスタンプが、そのデータ項目の読み込みタイムスタンプよりも大きく、そのデータ項目の書き込みスタンプよりも小さければ、当面のトランザクションは、書き込み処理の時機を逸してしまっているが、そのことによるデータベース及び他のトランザクションへの影響はないので、当面のトランザクションはこの書き込み処理を無視して処理を続ける手法である。
【００１５】
<タイムスタンプ・プロトコルの問題点>
タイムスタンプ・プロトコルはロックを使用しないため、デッドロックが起こることはない。しかし、同時に処理するトランザクションの数が増えると、個々のデータ項目に対して、正しい順番でトランザクションの処理が行われなくなり、数多くのトランザクションが中断してロールバックし、トランザクション処理システムに再提出されることになる。このような処理が繰り返されると、いつまでたってもトランザクションの処理が完了しなくなるといった問題が起こる。
【００１６】
(4) マルチバージョンを用いた手法
マルチバージョンを用いた手法は、当面のトランザクションがあるデータ項目に対して、データを書き込む際に、そのデータ項目の前の値を維持し、１つのデータ項目に対して複数の値を管理する手法である。そして、複数のトランザクションが、同じデータ項目に対して処理を行う場合、個々のトランザクションに対して、適切なバージョンのデータ項目を与えることによって、中断されるトランザクションの数を減らしている。マルチバージョンを用いた手法は、二相ロック・プロトコルにマルチバージョンを適用させた手法と、タイムスタンプ・プロトコルにマルチバージョンを適用させた手法などがある。
【００１７】
<マルチバージョンの問題点＞
マルチバージョンの問題点は、個々のデータ項目に対して複数のバージョンを維持するために余分な記憶スペースが必要になることである。
【００１８】
【特許文献１】特開平０７−０８４８６４号公報
【特許文献２】特開平０７−２００３７２号公報
【特許文献３】特開平１０−３２０２５８号公報
【特許文献４】特開２００２−３２２４９号公報
【特許文献５】United States Patent  5,280,619   January 18, 1994  System for accessing shared data using a serialization graph constructed from a history file showing completed locking dependencies between transactions
【非特許文献１】北川博之 HIROYUKI KITAGAWA, データベースシステム Database System, pp.147-173, 昭晃堂 情報系教科書シリーズ  第１４巻, １９９６年７月１０日  初版１刷発行 1997
【非特許文献２】Ramez Elmasri, Shamkant B. Navathe, Fundamentals of Database Systems Second Edition, pp.527-575, Addison-Wesley Publishing Company, 1994
【非特許文献３】金弘和實 KAZUIMI KANEHIRO, ベテランが丁寧に教えてくれるデータベースの知識と実務, pp.88-105, 株式会社翔泳社, 2007
【発明の開示】
【発明が解決しようとする課題】
【００１９】
従来のトランザクション処理システムは、以上に述べた問題点があるため必ずしも効率的な手法ではない。従来の手法は、個々のトランザクションを別々に処理するため、同時に処理するトランザクションの数が増えると、個々のトランザクションごとに、同じデータ項目を何度も繰り返して読み出し、そして書き込むことになり、複数のトランザクションが競合し、中断してロールバックするトランザクションが増えて、トランザクションの処理速度が低下することになる。
【００２０】
本発明では、入力された複数のトランザクションを別々に処理するのではなく、入力された複数のトランザクションが処理を行うデータ項目に対して、そのデータ項目を一度だけ検索し、検索したデータ項目に対して、複数のトランザクションの更新処理を順次メインメモリ内で行い、最後に更新した結果だけをデータベースに一度だけ書き込むことを用いる。
【課題を解決するための手段】
【００２１】
上述の目的を達成するために、本発明は、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムであって、入力された複数のトランザクションに対してトランザクションの実行順を決定するトランザクション実行順決定手段と、前記複数のトランザクションが同一のデータ項目に対して処理を行う場合、そのデータ項目に対する枝を作成し、先に処理を行うトランザクションの接点から次に処理を行うトランザクションの接点にその枝を入力して、前記トランザクションの実行順にデータを更新することを示した先行グラフを作成する先行グラフ作成手段と、前記複数のトランザクションに含まれる部分処理をタスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記トランザクションの実行順に、前記データベースのアクセス領域ごとにグループ分けするグループ分け手段と、前記グループ分けして作成したグループを用いて合成トランザクションを作成する合成トランザクション作成手段と、前記合成トランザクションに含まれる個々のグループに対してマルチオペレーション・プロセッシングを用いて処理を行うマルチオペレーション・プロセッシング手段とを備え、前記マルチオペレーション・プロセッシング手段は、グループ分けされたタスクがアクセスするアクセス領域内のブロックを調べ、グループ内のタスクが並んでいる順に該ブロックへのアクセス順を決定し、決定したアクセス順に該ブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出し、ブロック内のデータ項目に対して、グループ内のタスクが並んでいる順にタスク処理を順次行い、グループ分けされたタスクの処理が終了し、グループ分けされたタスクを包含するトランザクションの処理が終了すると、その時点で終了したトランザクションをコミットするかどうかを、前記先行グラフの終了したトランザクションの接点に入力枝が存在するかどうかで決定し、該トランザクションの接点に入力枝が存在しない場合は、該トランザクションをコミットし、該トランザクションの接点とその接点から出ているすべての枝を削除し、ブロック内のデータ項目に対して、グループ内のタスクが並んでいる順にタスク処理を順次行っていくということは、ブロック内のデータ項目が前記先行グラフに存在する場合、そのデータ項目に対して前記先行グラフに示したトランザクションの実行順にトランザクションの部分処理であるタスクの処理を順次行っていくことであり、複数のタスクがそのデータ項目に対して更新処理を行う場合、そのデータ項目に対して最初のタスクの更新処理を行い、更新されたデータ項目に対して次のタスクの更新処理を行い、このような更新処理を繰り返し、最後のタスクの更新処理が行われると、最後に更新された更新結果だけをデータベースに書き込むことを特徴とする。
【００２２】
また、２相ロック・プロトコル又はタイムスタンプ・プロトコルを用いて複数の合成トランザクションの処理を同時に並行して実行するとよい。
さらに、データベースのトランザクション処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムや、このプログラムを記録した記録媒体も本発明である。
【発明の効果】
【００２３】
本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いることによって、従来のトランザクションの処理のように、入力された複数のトランザクションに対して、トランザクションごとに同じデータ項目を何度も繰り返して検索し、検索したデータ項目に対して更新処理を別々に行い、更新された結果を何度も繰り返してデータベースに書き込む必要がなくなった。
本発明のシステムでは、複数のトランザクションが処理を行うデータ項目に対して、そのデータ項目を一度だけ検索し、検索したデータ項目に対して、複数のトランザクションの更新処理を順次メインメモリ内で行い、最後に更新した結果だけをデータベースに一度だけ書き込めばよいのでトランザクションの処理速度が向上した。
また、マルチオペレーション・プロセッシングを用いるので、トランザクションの処理を行う個々のデータ項目が格納してあるブロックをディスクから一度だけしか読み出す必要がなくなった。
【００２４】
本発明のシステムは、入力された複数のトランザクションに対して１つの合成トランザクションを作成し、合成トランザクションに含まれる個々のグループの処理は、異なるリレーションに対して行うため、それらのグループの処理を同時に行っても、複数のグループ間で同一のデータ項目がアクセスされることはない。また、グループに集められたタスクの処理は、メインメモリに読み込まれたブロック内のデータ項目に対して、先行グラフに示したトランザクションの実行順に順次行っていく。その結果、合成トランザクションに合成された複数のトランザクションの間でロックなどをかける必要はなく、トランザクションを待たせたり、トランザクションを中断したりするといったことがなくなった。
【００２５】
本発明のシステムは、入力された複数のトランザクションに対して１つの合成トランザクションを作成し、合成トランザクションの処理を行っていくことができ、１つの合成トランザクションの処理が終了した段階で、新たに複数のトランザクションが入力されると、それらのトランザクションに対して別の合成トランザクションを作成し、その合成トランザクションの処理を行っていくことができるので、合成トランザクションの処理を１つずつ実行していく場合には、ロックを用いる必要はなくなる。また、デッドロックなどを発生することもなく、合成トランザクションに含まれる複数のグループの処理を同時に並行して実行していくことができるようになった。
【００２６】
このように合成トランザクションの処理を１つずつ実行していくことによって、複数のトランザクションの処理速度を向上させることができるが、複数の合成トランザクションの処理を同時に並行して実行することが必要となるような場合には、複数の合成トランザクションに二相ロックやタイムスタンプを用いたマルチオペレーション・プロセッシングを使用することによって、CPUやディスクなどのハードウェア資源を効率よく利用することができるようになった。また従来の二相ロック・プロトコルのように、個々のトランザクションがそれぞれロックをかけるのではなく、数多くのトランザクションから作成された合成トランザクションがロックをかけることになるので、オペレーティング・システムのプロセスやロックなどの資源利用の回数を減少させることができるようになった。
【発明を実施するための最良の形態】
【００２７】
本発明は、数多くのトランザクションを効率よく同時に処理するために、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムを提案する。さらに、本発明は、複数の合成トランザクションの処理を同時に並行して実行するために、トランザクションの同時実行制御を備えたマルチオペレーションに、二相ロックを用いたマルチオペレーション・プロセッシングと、タイムスタンプを用いたマルチオペレーション・プロセッシングを提案する。
【００２８】
本発明者は、以前クエリーの処理だけを扱った「マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システム」について提案した（特許４１０９３０５号参照）。
本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングが上記のクエリーの処理だけを扱ったマルチオペレーション・プロセッシングと異なる点は、検索処理しか行わないトランザクション（クエリー）の処理以外に、更新処理を行うトランザクションの処理を行うことができるようになったことである。
【００２９】
<データベース・マネージメント・システムの構成>
図１は、本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムのアーキテクチャを示す図である。このアーキテクチャは、マイクロプロセッサ（ＣＰＵ）、主記憶装置（メインメモリ）、２次記憶装置（ディスク）を備えたコンピュータ・システム105において、トランザクション処理システム100、キュー103、マルチオペレーション・プロセッサ102などのソフトウェアのモジュールから構成されている。
【００３０】
最初に、複数のユーザーからSQLなどの言語で記述された複数のトランザクションT1,T2,…,T8がトランザクション処理システム100に入力されると、トランザクション処理システムは、入力されたトランザクションに対して、トランザクションの部分処理を求めてトランザクションの実行順を決定し、トランザクションの実行順にデータを更新することを示した先行グラフを作成し、トランザクションに含まれる部分処理をタスクとして取り出し、取り出したタスクをデータベースのリレーション(アクセス領域)ごとにグループG1,G2に分けて、グループG1,G2を作成し(トランザクションT1,T2,…,T8が合計２つのリレーションに対して処理を行う必要がある場合)、作成したグループG1,G2を用いて合成トランザクションTG1,G2を作成し、合成トランザクションTG1,G2をキュー103に加える。
【００３１】
キュー103に合成トランザクションTG1,G2が加えられると、マルチオペレーション・プロセッサ102は、キュー103から合成トランザクションTG1,G2を取り出し、オペレーティング・システムのプロセス(104)が５つほどをトランザクション処理システムのために用意されていた場合、プロセス１がTG1,G2に含まれるグループG1に対してマルチオペレーション・プロセッシングを用いて処理を行い、プロセス２がTG1,G2に含まれるグループG2に対してマルチオペレーション・プロセッシングを用いて処理を行うことになる。
【００３２】
次に、合成トランザクションTG1,G2がキューから取り出された後に、新たにトランザクションT9,T10,T11がトランザクション処理システム100に入力されると、トランザクションT9,T10,T11に対しても同様に、トランザクション処理システム100は、入力されたトランザクションに対して、トランザクションの部分処理を求めてトランザクションの実行順を決定し、トランザクションの実行順にデータを更新することを示した先行グラフを作成し、トランザクションに含まれる部分処理をタスクとして取り出し、取り出したタスクをデータベースのリレーションごとにグループG3,G4,G5に分けて、グループG3,G4,G5を作成し(トランザクションT9,T10,T11が合計３つのリレーションに対して処理を行う必要がある場合)、作成したグループG3,G4,G5を用いて合成トランザクションTG3,G4,G5を作成し、合成トランザクションTG3,G4,G5をキュー103に加える。
【００３３】
マルチオペレーション・プロセッサ102は、現在プロセス１とプロセス２を用いて合成トランザクションTG1,G2の処理を行っていたとすると、残ったプロセス３とプロセス４とプロセス５を用いて合成トランザクションTG3,G4,G5のグループG3,G4,G5の処理を行うことになる。
【００３４】
＜マルチオペレーション・プロセッシングを用いたトランザクション処理システムのフローチャート＞
図２−１，図２−２は、図１で説明したトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムにおいて、トランザクションを処理する一連の流れの概略を説明するためのフローチャートである。
【００３５】
最初に、図２−１において、複数のユーザーからSQL(構造化問い合わせ言語)などのリレーショナル・データベースの言語で記述された複数のトランザクションT1,T2,T3,….,Tsがデータベース・サーバーのトランザクション処理システム１００に入力される(S200)。
トランザクション処理システム１００は、入力されたトランザクションに対して、実行可能なオペレーションに変換してトランザクションの部分処理を作成する(S201)。トランザクションの部分処理を作成すると、トランザクションの実行順を決定する(S202)。
【００３６】
トランザクションの実行順を決定すると、トランザクションT1,T2,….,Tsを接点とした先行グラフを作成する(S203)。先行グラフを作成するにあたって、トランザクションT1,T2,…,Tsの中で複数のトランザクションが同一のデータ項目に対して処理を行う場合、そのデータ項目に対して矢印を持った枝を作成し、先に処理を行うトランザクションの接点から次に処理を行うトランザクションの接点へとその枝を入力させて、そのデータ項目に対するトランザクションの実行順を明確にする。
先行グラフを作成すると、トランザクションに含まれる部分処理をタスクとして取り出し、取り出したタスクをデータベースのリレーション（アクセス領域）ごとにグループ分けして、グループG1,G2,…,Gnを作成する(S204)。
作成されたグループG1,G2,…,Gnを用いて合成トランザクションTG1,G2,…,Gnを作成する(S205)。
【００３７】
合成トランザクションTG1,G2,…,Gnに含まれる個々のグループGi(i=1,2,..,n)に対して、マルチオペレーション・プロセッサ１０２を用いてグループの処理を開始する(S206)。
マルチオペレーション・プロセッッサ１０２は、グループ内のタスクがアクセスするブロックを調べてブロック集合に集める(S207)。
ブロック集合にブロックを集めると、グループ内のタスクが並んだ順にブロックへのアクセス順を決定する(S208)。
決定したブロックのアクセス順にブロックを読み出し、読み出したブロックにアクセスするタスクをグループから抽出し、ブロック内のデータ項目に対して、グループ内のタスクが並んだ順にタスク処理を順次行っていく(S209)。
ブロックでタスクの処理が終了すると(図２−２：S210)、終了したタスクを包含するトランザクションの処理が終了したかどうかを調べる(S211)。トランザクションの処理が終了したかどうかは、トランザクションに含まれるすべてのタスクの処理が終了したかどうかで調べることになる。トランザクションの処理が終了しない場合は、ブロックのアクセス順に示したすべてのブロックをアクセスしたがどうかを確認する(S217)。
【００３８】
トランザクションの処理が終了した場合は、先行グラフをもとにして、この時点でトランザクションをコミットすることができるかどうかを決定する(S212)。トランザクションをコミットすることができるかどうかは、先行グラフにおいて、終了したトランザクションの接点に入力枝が存在するかどうかで調べることになる。
終了したトランザクションの接点に入力枝が存在し、この時点でトランザクションをコミットできない場合は、そのトランザクションをコミット待ちのトランザクションとして置いておく（S216）。
【００３９】
入力枝が存在しないで、トランザクションをコミットすることができる場合は、トランザクションをコミットし(S213)、そのトランザクションの接点とその接点から出ているすべての枝を先行グラフから削除する(S214)。また、枝を削除することによって、別のコミット待ちのトランザクションの接点に入力している枝がすべて無くなる場合は(S215)、そのトランザクションもコミットし、連鎖的にトランザクションのコミットを繰り返していく(S213)。
アクセスしたブロックでの処理が終了すると、ブロックのアクセス順に示したすべてのブロックをアクセスし終えたかどうかを確認する(S217)。
まだ、アクセスしてないブロックが残っているならば、ブロックのアクセス順に、次にアクセスするブロックをディスクから読み出し、読み出したブロックにアクセスするタスクをグループから抽出し、読み出したブロック内のデータ項目に対して、トランザクションの実行順にトランザクションの部分処理であるタスク処理を繰り返して行っていく(S209)。
【００４０】
ブロックのアクセス順に示したすべてのブロックをアクセスし終えると、グループの処理が終了する(S218)。グループの処理が終了すると合成トランザクションに含まれるすべてのグループの処理が終了したかどうかを確認する(S219)。
まだ、グループが残っている場合は、次に処理するグループを合成トランザクションから取り出し、取り出したグループに対して、マルチオペレーション・プロセッシングを用いて処理を行い、このようにしてグループの処理を繰り返して行っていく(S206)。
合成トランザクションに含まれるすべてのグループ処理を終えると、合成トランザクションの処理が完了し、入力されたすべてのトランザクションT1,T2,T3,…,Tsの処理が終了してコミットしたことになる(S220)。
【００４１】
図１，図２−１，図２−２において、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの概略を説明した。
以下の章において、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムについて詳しく説明していくことにする。
第１章では、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたトランザクション処理の手順、及び具体例を示している。第２章では、複数の合成トランザクションを同時に並行して実行するために、二相ロックを用いたマルチオペレーション・プロセッシングとタイムスタンプを用いたマルチオペレーション・プロセッシングを提案し、それぞれの手法を用いた複数の合成トランザクションの処理を並行して行うための手順、及び具体例を示している。第３章では、結合演算の処理を行うクエリーなど、複雑で高度なクエリーがトランザクションに含まれている場合のマルチオペレーション・プロセッシングを具体例をもとに説明している。
第４章では、従来のトランザクションの処理である二相ロック・プロトコルと、本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングとの処理速度を比較するために、独自に開発したデータベース・マネージメント・システムのソフトウェアMOP-DBを用いて、それぞれの処理を用いた実験結果を示している。
【００４２】
[1. トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシング]
[1.1トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの手順]
[(1) トランザクションの部分処理の作成（S201）]
データベース・マネージメント・システムに、複数のトランザクションT1,T2,T3,…,Tsが入力される（S200)と、個々のトランザクションに対して、トランザクションが行うレコードrの読み取り処理をread_item(r)とし、レコードrの書き込み処理をwrite_item(r)として表わしたトランザクションの部分処理を作成する（S201）。
【００４３】
[(2) トランザクションの実行順の決定（S202）]
トランザクションの部分処理を求めると、入力された複数のトランザクションT1,T2,T3,…,Tsに対して、トランザクションの実行順を決定する（S202）。トランザクションの実行順を決定するには、トランザクションの部分処理をもとにしてトランザクションの処理コストを求め、処理コストの小さいトランザクションから処理コストの大きいトランザクションへとトランザクションを並べてトランザクションの実行順を決定する。
なお、トランザクションの処理コストよりも、トランザクションの到着時間の方が重要である場合は、トランザクションの到着順をトランザクションの実行順にしてもよい。
【００４４】
[(3)  先行グラフの作成（S203）]
トランザクションの実行順を決定すると、トランザクションT1,T2,T3,…,Tsを接点とした先行グラフを作成する（S203）。先行グラフを作成するにあたって、トランザクションT1,T2,T3,…,Tsの中で、複数のトランザクションが同一のデータ項目に対して処理を行う場合、そのデータ項目に対して矢印を持った枝を作成し、トランザクションの実行順に、先に処理を行うトランザクションの接点から、次に処理を行うトランザクションの接点へと、その枝を入力する。
トランザクションの実行順が、トランザクションの処理コストの小さい順で並べられている場合は、処理コストの小さいトランザクションの接点から処理コストの大きいトランザクションの接点へと、枝を入力することになる。また、トランザクションの実行順が、トランザクションの到着順で並べられている場合は、先に到着したトランザクションの接点から次に到着したトランザクションの接点へと枝を入力することになる。
【００４５】
[(4) タスクのグループ分け（S204）]
トランザクションT1,T2,T3,…,Tsに含まれる個々の更新処理、及び検索処理などの部分処理をタスクtij(i=トランザクションの番号、j=トランザクション内の処理番号)として取り出し、取り出したタスクを、トランザクションの実行順にデータベースのリレーション(アクセス領域)ごとにグループG1,G2,…,Gnとしてグループに分けていく（S204）。リレーションはデータベースのアクセス領域である。
【００４６】
[(5) 合成トランザクションの作成（S205）]
タスクがリレーションごとにグループ分けされると、作成されたグループG1,G2,…Gnを用いて合成トランザクショTG1,G2,…Gnを作成する（S205）。合成トランザクションTG1,G2,…Gnの処理を行うには、マルチオペレーション・プロセッシングを用いて合成トランザクションTG1,G2,…Gnに含まれる個々のグループ処理を順次行っていくことになる。
【００４７】
[(6) マルチオペレーション・プロセッシングによるグループ処理]
最初に、合成トランザクションTG1,G2,…GnからグループG1を取り出し、マルチオペレーション・プロセッシングを用いてグループG1の処理を開始する（S206）。
【００４８】
[(7) タスクのアクセス領域の検出]
グループG1内のタスクt1, t2, t3,…,tpがアクセスするリレーションに存在するインデックスを用いて、グループG1内のタスクt1, t2, t3,…,tpが、リレーション内のブロックb1,b2,b3,…bmのうちアクセスする必要のあるブロック(ブロックの格納位置)を調べて、アクセスする必要のあるブロックを集めた集合を見出し、それらの集合をそれぞれブロック集合B1,B2,B3,…Bpとする（S207）。言い換えると、タスクti(i=1,2,3,…p) に対して、それに対応するブロック集合として、Bi={ブロックb1,b2,b3,…,bmの中でタスクtiがアクセスする必要があるブロック集合}{i=1,2,3,…,p}となるブロック集合を見出す。ここでブロック集合を見出すにあたっては、インデックスによるブロックの格納位置を調べるだけであって、リレーション内のブロックをディスクにアクセスしてブロックの格納位置を調べることではない。
【００４９】
[(8) ブロックのアクセス順位の決定（S208）]
グループG1内のタスクt1, t2, t3,…,tpに対応するブロック集合B1,B2,B3,…Bpを見出すと、ブロック集合B1,B2,B3,…,Bpの和集合を求めていく。最初に、タスクt1とタスクt2に対応するブロック集合との和集合を求め、その和集合とタスクt3に対応するブロック集合との和集合を求めるということを順次行い、最後にタスクtpに対応するブロック集合との和集合を求める。この際、順次和集合に加わるブロックは和集合中のブロックの後に加えるものとする。最後に求めた和集合の結果から、トランザクションの実行順に、トランザクションの部分処理であるタスク処理を行っていくにあたって、最初にリレーション内のどのブロックからアクセスを始めて、最後にどのブロックでアクセスを終えるかのブロックのアクセス順位を決定することができる（S208）。また、このようにして和集合を求めることは、グループ内のタスクを処理するにあたって、リレーション内のブロックを何度もディスクにアクセスして読み出すことなしに、一度だけブロックにアクセスすれば済むようにするためである。
【００５０】
[(9) 各ブロックでのタスク処理（S209)]
[ブロック bjでのタスク処理]
決定されたブロックのアクセス順位に従って、リレーションにアクセスする最初のブロックをbj(1≦j≦m)としたときに、グループG1内のタスクt1,t2,t3,…,tpをこのブロックで処理を行う必要があるかどうかを調べるためにブロックbjを集合{bj}として表わし、この{bj}とタスクt1,t2,t3,…,tpに対応するブロック集合B1,B2,B3,…,Bpとの間で積集合(∩)を求める。その積集合が{bj}となったブロック集合に対応するタスクはすべてブロックbjで処理を行うことになり、積集合が空集合({})となったブロック集合に対応するタスクはブロックbjで処理を行わないことになる。なお、複数のタスクがブロックbj内の同一のデータ項目に対して処理を行う場合は、先行グラフに示したトランザクションの実行順に、それらのトランザクションの部分処理であるタスク処理を順次行っていく。
ブロックbjで処理を行う必要のあるグループG1のすべてのタスクの処理が終了すると、このブロックbjを再びアクセスする必要がなくなるので、積集合{bj}となったブロック集合と集合{bj}との差集合を求めて、差集合によって得られたブロック集合をBi(1)(i=1,2,…,p)としたときに、その差集合Bi(1)が空集合({})となったブロック集合に対応するタスクは処理が終了（S210)したことになり、その差集合が空集合でないブロック集合に対応するタスクはまだ処理が終了していないことになる。
【００５１】
[トランザクションの終了、及びコミット]
ブロックbjでのタスクの処理が終了すると、終了したタスクを包含するトランザクションの処理が終了したかどうかを確認する（S211)。トランザクションに含まれるすべてのタスクの処理が終了する（S211：YES)と、トランザクションの処理が終了することになる。トランザクションの処理が終了すると、この時点で終了したトランザクションをコミットすることができるかどうかを、先行グラフをもとにして決定する（S212）。
終了したトランザクションの接点に入力している枝が存在する場合（S212：NO）は、そのトランザクションをコミットしないで、コミット待ちのトランザクションとして置いておく（S216）。終了したトランザクションの接点に入力している枝が１つも存在しない場合（S212：YES）は、そのトランザクションをコミットする（S213）。トランザクションをコミットすると、先行グラフからそのトランザクションの接点と、その接点から出ているすべての枝を削除する（S214）。
【００５２】
その際、削除した枝がコミット待ちのトランザクションの接点に入力している枝であり、その枝を削除することによって、コミット待ちのトランザクションの接点に入力している枝が１つもなくなる場合（S215：YES）は、そのコミット待ちのトランザクションもコミットすることになる（S213）。その理由は、接点に入力している枝がなくなるということは、同じデータ項目に対して先に書き込み処理を行ったトランザクションがコミットしたため、その書き込まれたデータ項目を読み込んだ別のトランザクションもコミットすることができるからである。
【００５３】
[ブロック bkでのタスク処理]
さて、すべてのブロックをアクセスしていない場合（S217:NO)、S209に戻り、ブロックのアクセス順位に従って、次のブロックbk(1≦k≦m)を読み出し、ブロックbkを集合{bk}として表わし、この集合{bk}と、すでに処理が終了したタスク以外のグループ内にタスクに対応するブロック集合の間で積集合を求める。その積集合が{bk}となったブロック集合に対応するタスクはすべてブロックbkで処理を行うことになる。ブロックbkで処理を行う必要のあるグループG1内のすべてのタスクの処理が終了すると、ブロックbkを再びアクセスすることがなくなるので、積集合が{bk}となったブロック集合Bi(1)(ブロックbjで処理終了後に差集合によって得られたブロック集合)と集合{bk}との差集合を求める。この差集合が空集合({})となったブロック集合に対応するタスクは処理が終了したことになり、差集合が空集合ではないブロック集合に対応するタスクは、まだ処理が完全に終了していないことになる。ここで、差集合によって得られたブロック集合をBi(2)(i=1,2,…,n)とする。
【００５４】
[トランザクションの終了、及びコミット]
ブロックbkにおいて、タスクの処理が終了する（Ｓ210)と、そのタスクを包含するトランザクションの処理が終了したかどうかを確認する（S211)。トランザクションに含まれるすべてのタスクの処理が終了すると、トランザクションの処理が終了したことになる。トランザクションの処理が終了すると、先行グラフをもとにして、終了したトランザクションをこの時点でコミットすることができるかどうかを決定する（Ｓ212)。
終了したトランザクションの接点に入力している枝が存在する場合（S212：NO）は、そのトランザクションをコミットしないでコミット待ちのトランザクションとして置いておく（S216）。終了したトランザクションの接点に入力している枝が１つも存在しない場合（S212：YES）は、トランザクションをコミットする（S213）。トランザクションをコミットすると、そのトランザクションの接点と、その接点から出ているすべての枝を先行グラフから削除する。
【００５５】
以上の処理を繰り返して行って、ブロックのアクセス順位にしたがってブロックをアクセスし、アクセスしたブロックでグループ内のタスクの処理を行うと、グループG1内のすべてのタスクの処理を終了する（S217：YES）。
【００５６】
[(10) マルチオペレーション・プロセッシングによるグループG2,…,Gnの処理]
グループG1の処理が終了する（S218）と、合成トランザクションTG1,G2,…,GnからグループG2,…,グループGnを順次取り出し、グループG1と同じ手順を用いてグループ処理を繰り返して行っていく（S219：NO）。
すべてのグループ処理を終える（S219：YES）と、合成トランザクションTG1,G2,…,Gnの処理が完了し、入力されたすべてのトランザクションT1,T2,T3,…,Tsの処理が終了してコミットしたことになる（S220)。
【００５７】
[1.2. トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの具体例]
１．１章で示したトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの手順を具体的な例を用いて詳細に説明する。図３−１は、固定長レコード(fixed length record)を使用して作成したデータベースのリレーションDEPARTMENT(300)である。リレーションDEPARTMENT(300)には25件のレコードが5つのブロックに格納してあり、各ブロックに5つのレコードが存在する。各レコードには、DNUMBER（部門番号），DNAME（部門名），MGRSSN（部門長従業員番号），BUDGET(予算), DPHONE（部門電話番号）のデータが格納されている。各ブロックは、次のブロックに対してブロックポインタを持っている。主キーDNUMBERには、主インデックス(310)が存在し、主インデックス(310)は、各ブロックに対してインデックスのポインタを持っている。また属性DPHONEには２次インデックス(321,322)が存在し、２次インデックス(321,322)は、各レコードに対してインデックスのポインタを持っている。
【００５８】
図３−２は、固定長レコードを使用して作成したデータベースのリレーションEMPLOYEE（従業員）である。EMPLOYEE(400)には20件のレコードが5つのブロックに格納してあり、それぞれのブロックに4つのレコードが存在する。各レコードには、SSN（従業員番号），FNAME（名），MINIT（ミドルネームの頭文字），LNAME（姓），BDATE（生年月日）， DNUM（部門番号）， PHONE（電話番号）のデータが格納されている。各ブロックは、次のブロックに対してブロックポインタを持っている。主キーSSNには、主インデックス(410)が存在し、主インデックス(410)は、各ブロックに対してインデックスポインタを持っている。また属性PHONEには２次インデックス(420)が存在し、２次インデックス(420)は、各レコードに対してインデックスのポインタを持っている。
【００５９】
なお、図３−１のリレーションDEPARTMENT(300)と図３−２のリレーションEMPLOYEE(400)以外に、図では示していない１つのリレーションPROJECTがデータベースに存在するものとする。
リレーションDEPARTMENT(300), EMPLOYEE(400), PROJECTは、リレーショナル・データベース・システムのアクセス領域であり、リレーション内のブロックはデータベースのデータが格納してあるディスク上のアクセス単位である。
【００６０】
次に、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたトランザクション処理を説明するために、これらのリレーションに対して、下記に示すようなトランザクションT1, T2, T3, T4, T5, T6, T7, T8の処理を取り上げることにする。以下において、各トランザクションは、BEGINで開始し、COMMITで完了することにする。
【００６１】
(T1):BEGIN WORK;
-- T1の更新処理１
UPDATE DEPARTMENT
SET BUDGET = BUDGET + 10000
WHERE DNUMBER = 7;
-- T1の更新処理２
UPDATE DEPARTMENT
SET BUDGET = BUDGET + 20000
WHERE DNUMBER = 9;
-- T1の更新処理３
UPDATE EMPLOYEE
SET DNUM = 4
WHERE SSN = 2411111133;
COMMIT WORK;
【００６２】
(T2):BEGIN WORK;
-- T2の更新処理１
UPDATE DEPARTMENT
SET BUDGET = BUDGET + 22000
WHERE DPHONE = 23-3728;
-- T2の更新処理２
UPDATE DEPARTMENT
SET BUDGET = BUDGET + 30000
WHERE DNUMBER > 6 AND DNUMBER < 9;
COMMIT WORK;
【００６３】
(T3):BEGIN WORK;
-- T3の更新処理１
UPDATE DEPARTMENT
SET MGRSSN = 470124116
WHERE DNUMBER = 6 OR DNUMBER = 19;
-- T3の検索処理２
SELECT DNUMBER, DNAME
FROM DEPARTMENT
WHERE DNUMBER = 19;
COMMIT WORK; 
【００６４】
(T4):BEGIN WORK;
-- T4の更新処理１
DATE DEPARTMENT  
SET DPHONE = 23-3736
WHERE DNUMBER = 3;
-- T4の更新処理２
UPDATE DEPARTMENT  
SET DPHONE = 23-3737
WHERE DNUMBER = 19;
-- T4の更新処理３
UPDATE EMPLOYEE
SET BDATE = 'DEC-27-1971'
WHERE SSN = 2066567788;    
COMMIT WORK;
【００６５】
(T5):BEGIN WORK;
-- T5の更新処理１
UPDATE DEPARTMENT  
SET BUDGET = BUDGET - 24000
WHERE DNUMBER = 7 OR DNUMBER = 8;
-- T5の更新処理２
UPDATE DEPARTMENT  
SET BUDGET = BUDGET - 11000
WHERE DNUMBER = 14;
COMMIT WORK;
【００６６】
(T6):BEGIN WORK;
-- T6の更新処理１
UPDATE DEPARTMENT  
SET BUDGET = BUDGET  15000
WHERE DNUMBER = 3 OR DNUMBER = 14;
-- T6の更新処理２
UPDATE DEPARTMENT  
SET MGRSSN = 433424659
WHERE DNUMBER = 22;
-- T6の検索処理３
SELECT *  
FROM DEPARTMENT
WHERE DNUMBER = 23;
COMMIT WORK;
【００６７】
(T7):BEGIN WORK;
-- T7の更新処理1
UPDATE EMPLOYEE  
SET BDATE = 'DEC-27-1971'
WHERE SSN = 1645455566;
COMMIT WORK;
【００６８】
(T8):BEGIN WORK;
-- T8の更新処理１
UPDATE EMPLOYEE  
SET DNUM = 7
WHERE PHONE = 21-3728 OR SSN = 2066567788;
COMMIT WORK;
【００６９】
[(1) トランザクションの部分処理の作成（S201）]
入力されたトランザクションT1, T2, T3, T4, T5, T6, T7, T8に対して、個々のトランザクションが行うレコードrの読み取り処理をread_item(r)として表わし、レコードrの書き込み処理をwrite_item(r)として表わし、個々のトランザクションの部分処理を作成すると次のようになる。リレーションDEPARTMENT内のレコードは、D.ri(i=1,2,3,…,25)で表わし、リレーションEMPLOYEE内のレコードは、E.ri(i=1,2,3,…,20)で表わし、個々のレコードの格納位置は、リレーションに存在するインデックスを用いて調べることにする。
各トランザクションに含まれる個々の更新処理、及び検索処理などの部分処理は、タスクtij(i=トランザクションの番号、j=トランザクション内の処理番号)として表わすことにする。
【００７０】
(T1):        
(t11):read_item(D.r7);
D.r7.BUDGET := D.r7.BUDGET + 10000;
write_item(D.r7);
(t12):read_item(D.r9);
D.r9.BUDGET := D.r9.BUDGET + 20000;
write_item(D.r9);
(t13):read_item(E.r14);
E.r14.DNUM := 4;
write_item(E.r14);
【００７１】
(T2):        
(t21):read_item(D.r7);
D.r7.BUDGET := D.r7.BUDGET + 22000;
write_item(D.r7);
(t22):read_item(D.r7);
D.r7.BUDGET := D.r7.BUDGET + 30000;
write_item(D.r7);
read_item(D.r8);
D.r8.BUDGET := D.r8.BUDGET + 30000;
write_item(D.r8);
【００７２】
(T3):        
(t31):read_item(D.r6);
D.r6.MGRSSN := 470124116;
write_item(D.r6);
read_item(D.r19);
D.r19.MGRSSN := 470124116;
write_item(D.r19);
(t32):read_item(D.r19);
【００７３】
(T4):        
(t41):read_item(D.r3);
D.r3.DPHONE := 23-3736;
write_item(D.r3);
(t42):read_item(D.r19);
D.r19.DPHONE := 23-3737;
write_item(D.r19);
(t43):read_item(E.r10);
E.r10.BDATE := 'DEC-27-1971';
write_item(E.r10);
【００７４】
(T5):        
(t51):read_item(D.r7);
D.r7.BUDGET := D.r7.BUDGET  24000;
write_item(D.r7);
read_item(D.r8);
D.r8.BUDGET := D.r8.BUDGET  24000;
write_item(D.r8);
(t52):read_item(D.r14);
D.r14.BUDGET := D.r14.BUDGET  11000;
write_item(D.r14);
【００７５】
(T6):        
(t61):read_item(D.r3);
D.r3.BUDGET := D.r3.BUDGET  15000;
write_item(D.r3);
read_item(D.r14);
D.r14.BUDGET := D.r14.BUDGET  15000;
write_item(D.r14);
(t62):read_item(D.r22);
D.r22.MGRSSN := 433424659;
write_item(D.r22);
(t63):read_item(D.r23);
【００７６】
(T7):        
(t71):read_item(E.r6);
E.r6.BDATE := 'DEC-27-1971';
write_item(E.r6);
【００７７】
(T8):
(t81):read_item(E.r6);
E.r6.DNUM := 7;
write_item(E.r6);
read_item(E.r10);
E.r10.DNUM := 7;
write_item(E.r10);
【００７８】
[(3) トランザクションの実行順の決定（S202）]
トランザクションの部分処理を求めると、トランザクションT1, T2, T3, T4, T5, T6, T7, T8に対して、トランザクションの実行順を決定することになる。
トランザクションの実行順を決定するには、トランザクションに含まれる部分処理をもとにしてトランザクションの処理コストを求め、トランザクションの処理コストの小さい順にトランザクションを並べてトランザクションの実行順を決定するとよい。そのため、トランザクションの部分処理をもとにしてトランザクションの処理コストをもとめると次のようになる。
【００７９】
【表１】
0004261609.tif 000002
【００８０】
トランザクションの処理コストは、トランザクションの処理に必要とされるブロックのアクセス回数である。例えば、トランザクションT1はリレーションDEPARTMENTのブロックb2に格納してあるレコードr7とr9と、リレーションEMPLOYEEのブロックb4に格納してあるレコードr14と、２つのブロックをアクセスする必要があるので、処理コストを２とする。
トランザクションの処理コストを求めると、次のようにして処理コストの小さい順にトランザクションを並べてトランザクションの実行順をT2, T7, T3, T1, T5, T8, T4, T6と決定することができる。ここで、sortは処理コストの小さい順に並べ換えることを表わしている。
sort(T1, T2, T3, T4, T5, T6, T7, T8)⇒ (T2, T7, T1, T3, T5, T8, T4, T6)
【００８１】
[(4) 先行グラフの作成（S203)]
トランザクションの実行順を決定すると、トランザクションT2, T7, T1, T3, T5, T8, T4, T6を接点とした図４（ａ）に示す先行グラフを作成する。先行グラフを作成するにあたって、トランザクションT2, T7, T3, T1, T5, T8, T4, T6の中で複数のトランザクションが同一のデータ項目に対して処理を行う場合、そのデータ項目に対して矢印を持った枝を作成し、トランザクションの実行順に先に処理を行うトランザクションの接点から次に処理を行うトランザクションの接点へとその枝を入力させて、同一のデータ項目に対するトランザクションの実行順を示しておく。なお、１つのトランザクションだけで処理されるデータ項目は先行グラフに枝を記入しないことにする。
【００８２】
トランザクションT4, T6は、リレーションDEPARTMENT内の同一のレコードD.r3に対して更新処理を行うため、トランザクションの実行順に、接点T4から接点T6へと枝を入力させる。  
トランザクションT2,T1,T5は、リレーションDEPARTMENT内の同一のレコードD.r7に対して更新処理を行うため、トランザクションの実行順に、接点T2から接点T1へと枝を入力させ、接点T1から接点T5へと枝を入力させる。
トランザクションT2,T5は、リレーションDEPARTMENT内の同一のレコードD.r8に対して更新処理を行うため、トランザクションの実行順に、接点T2から接点T5へと枝を入力させる。
トランザクションT5,T6は、リレーションDEPARTMENT内の同一のレコードD.r14に対して更新処理を行うため、トランザクションの実行順に、接点T5から接点T6へと枝を入力させる。
【００８３】
トランザクションT3,T4は、リレーションDEPARTMENT内の同一のレコードD.r19に対して更新処理を行うため、トランザクションの実行順に、接点T3から接点T4へと枝を入力させる。
トランザクションT7,T8は、リレーションEMPLOYEE内の同一のレコードE.r6に対して更新処理を行うため、トランザクションの実行順に、接点T7から接点T8へと枝を入力させる。
トランザクションT8,T4は、リレーションEMPLOYEE内の同一のレコードE.r10に対して更新処理を行うため、トランザクションの実行順に、接点T8から接点T4へと枝を入力させる。
なお、図４（ａ）に示す先行グラフは、トランザクションの実行順にもとづいて作成されるため、サイクルを含んでおらず、この先行グラフをもとにして行われるトランザクションのスケジュールは、直列可能スケジュールである。
【００８４】
[(5) タスクのグループ化（Ｓ204)]
トランザクションT2, T7, T1, T3, T5, T8, T4, T6から、トランザクションの部分処理であるタスクt21,t22,t71,t11,t12,t13,t31,t32,t51,t52,t81,t41,t42,t43,t61,t62,t63を取り出し、取り出したタスクをデータベースのリレーションをもとにしてグループに分け、グループ分けされたタスクをトランザクションの実行順に並べると次のようになる。
DEPARTMENT:  グループ  G1 = {t21, t22, t11, t12, t31, t32, t51, t52, t41, t42, t61, t62, t63}
EMPLOYEE:       グループ  G2 = {t71, t13, t81, t43}
グループG1にはリレーションDEPARTMENTに対して処理を行うタスクを集め、グループG2にはリレーションEMPLOYEEに対して処理を行うタスクを集めることになる。
【００８５】
[(6) 合成トランザクションTG1,G2の作成(S205)及び処理(S206)]
タスクをグループ分けして、グループG1,G2を作成すると、グループG1,G2を用いて合成トランザクションTG1,G2を作成する。合成トランザクションTG1,G2の処理を行うには、合成トランザクションTG1,G2に含まれるグループG1, G2に対して、それぞれマルチオペレーション・プロセッシングを用いて処理することになる。
【００８６】
[(6-1) グループG1の処理]
[(a) タスクがアクセスするブロックの集合(S207)]
図３のリレーションDEPARTMENT(300)の主インデックス(310)及び二次インデックス(321,322)を用いて、グループG1内のタスクt21, t22, t11, t12, t31, t32, t51, t52, t41, t42, t61, t62, t63を処理するために読み出す必要のあるリレーションDEPARTMENT(300)内のブロックを調べて、個々のタスクに対応するブロック集合B21, B22, B11, B12, B31, B32, B51, B52, B41, B42, B61, B62, B63に集めると次のようになる。ここでブロック集合を見出すにあたっては、インデックスによるブロックの格納位置を調べるだけであって、リレーション内のブロックをディスクにアクセスしてブロックの格納位置を調べることではない。
【００８７】
タスクt21に対して、B21 = {b2}
タスクt22に対して、B22 = {b2}
タスクt11に対して、B11 = {b2}
タスクt12に対して、B12 = {b2}
タスクt31に対して、B31 = {b2,b4}
タスクt32に対して、B32 = {b4}
タスクt51に対して、B51 = {b2}
タスクt52に対して、B52 = {b3}
タスクt41に対して、B41 = {b1}
タスクt42に対して、B42 = {b4}
タスクt61に対して、B61 = {b1,b3}
タスクt62に対して、B62 = {b5}
タスクt63に対して、B63 = {b5}
【００８８】
[(b) ブロックのアクセス順位の決定（Ｓ208)]
グループ内の個々のタスクに対応するブロック集合を見出すと、グループにタスクが並べられた順に、すなわちt21, t22, t11, t12, t31, t32, t51, t52, t41, t42, t61, t62, t63の順に、各タスクに対応するブロック集合の和集合を求めていく。最初に、TB0={}(空集合)を用意し、TB0とタスクt21に対応するブロック集合B21との和集合TB21を求める。次に、このTB21とタスクt22に対応するブロック集合B22との和集合TB22を求める。同様にして、タスクt11, t12, t31, t32, t51, t52, t41, t42, t61, t62, t63に対応するブロック集合B11, B12, B31, B32, B51, B52, B41, B42, B61, B62, B63に対しても和集合TB11, TB12, TB31, TB32, TB51, TB52, TB41, TB42, TB61, TB62, TB63を順次求めると次のようになる。この場合、順次和集合に加わるブロックは和集合中のブロックの後に加えていくものとする。
【００８９】
TB0 ← ｛｝(空集合)
ブロック集合B21との和集合:  TB21 ← TB0 U B21,   TB21 = {b2}
ブロック集合B22との和集合:  TB22 ← TB21 U B22,  TB22 = {b2}
ブロック集合B11との和集合:  TB11 ← TB22 U B11,  TB11 = {b2}
ブロック集合B12との和集合:  TB12 ← TB11 U B12,  TB12 = {b2}
ブロック集合B31との和集合:  TB31 ← TB12 U B31,  TB31 = {b2, b4}
ブロック集合B32との和集合:  TB32 ← TB31 U B32,  TB32 = {b2, b4}
ブロック集合B51との和集合:  TB51 ← TB32 U B51,  TB51 = {b2, b4}
ブロック集合B52との和集合:  TB52 ← TB51 U B52,  TB52 = {b2, b4, b3}
ブロック集合B41との和集合:  TB41 ← TB52 U B41,  TB41 = {b2, b4, b3, b1}
ブロック集合B42との和集合:  TB42 ← TB41 U B42,  TB42 = {b2, b4, b3, b1}
ブロック集合B61との和集合:  TB61 ← TB42 U B61,  TB61 = {b2, b4, b3, b1}
ブロック集合B62との和集合:  TB62 ← TB61 U B62,  TB62 = {b2, b4, b3, b1, b5}
ブロック集合B63との和集合:  TB63 ← TB62 U B63,  TB63 = {b2, b4, b3, b1, b5}
【００９０】
以上のように、各タスクに対応するブロック集合に対して、タスクが並べられた順に、順次和集合を求めていくと、最後の和集合TB63から、ブロックb2からブロックのアクセスを開始し、ブロックb5でアクセスを終了すればよいことになり、リレーションDEPARTMENT(300)内のブロックへのアクセス順は(b2, b4, b3, b1, b5)となる。このような手法で和集合を求めることによって、リレーションDEPARTMENT(300)内のブロックへのアクセス順を決定することができ、この順にブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出して実行していくことになる。
【００９１】
[(c) 各ブロックでのタスク処理(S209)]
[(c-1) ブロックb2にアクセス]
最初に、リレーションDEAPARTMENT内のブロックの格納位置が256であるブロックb2内のデータをディスクからメインメモリに読み込み、グループG1内のタスクt21, t22, t11, t12, t31, t32, t51, t52, t41, t42, t61, t62, t63がブロックb2で処理を行う必要があるかどうかを調べるため、ブロックb2を集合{b2}として表し、{b2}とブロック集合B21,B22, B11, B12, B31, B32, B51, B52, B41, B42, B61, B62, B63との間でそれぞれ積集合(∩) を求めると次のようになる。
【００９２】
タスクt21に対して:  B21 ∩ {b2} = {b2}
タスクt22に対して:  B22 ∩ {b2} = {b2}
タスクt11に対して:  B11 ∩ {b2} = {b2}
タスクt12に対して:  B12 ∩ {b2} = {b2}
タスクt31に対して:  B31 ∩ {b2} = {b2}
タスクt32に対して:  B32 ∩ {b2} = {}
タスクt51に対して:  B51 ∩ {b2} = {b2}
タスクt52に対して:  B52 ∩ {b2} = {}
タスクt41に対して:  B41 ∩ {b2} = {}
タスクt42に対して:  B42 ∩ {b2} = {}
タスクt61に対して:  B61 ∩ {b2} = {}
タスクt62に対して:  B62 ∩ {b2} = {}
タスクt63に対して:  B63 ∩ {b2} = {}
【００９３】
タスクt21, t22, t11, t12, t31, t51に対して積集合が{b2}となり、ブロックb2で処理が可能となり、メインメモリに読み込んだブロックb2でタスクt21, t22, t11, t12, t31, t51の処理を行っていく。  
タスクt21, t22, t11, t12, t31, t51の処理を行うにあたっては、ブロック内のレコード順位が小さいレコードから順番に処理していき、個々のレコードに対しては、タスクt21, t22, t11, t12, t31, t51の順番でタスク処理を行っていくことになり、それらの処理は次のような順番になる。
【００９４】
【表２】
0004261609.tif 000003
【００９５】
レコードD.r6に関しては、タスクt31がレコードD.r6に対して更新処理を行う。
レコードD.r7に関しては、図４（ａ）に示す先行グラフに示すトランザクションのT2,T1,T5の実行順に、それらのトランザクションの部分処理であるタスクt21, t22, t11, t51の更新処理を順次行っていく。タスクt21は、データベースから読み込んだレコードD.r7に対して更新処理を行う。タスクt22は、タスクt21が更新したレコードD.r7に対して更新処理を行う。タスクt11は、タスクt22が更新したレコードD.r7に対して更新処理を行う。タスクt51は、タスクt11が更新したレコードD.r7に対して更新処理を行う。このようにタスクt21,t22,t11,t51による更新処理をメインメモリ内で順次行い、タスクt51による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
レコードD.r8に関しては、先行グラフ400に示すトランザクションのT2,T5の実行順に、それらのトランザクションの部分処理であるタスクt22, t51の更新処理を順次行っていく。タスクt22は、データベースから読み込んだレコードD.r8に対して更新処理を行う。タスクt51は、タスクt22が更新したレコードD.r8に対して更新処理を行う。タスクt22, t51による更新処理はメインメモリ内で順次行い、タスクt51による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
【００９６】
レコードD.r9に関しては、タスクt12がレコードD.r9に対して更新処理を行う。
ブロックb2でのタスクt21, t22, t11, t12, t31, t51の処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、ブロック集合B21, B22, B11, B12, B31, B51と集合{b2}との差集合を求めて、得られた差集合をB21(1), B22(1), B11(1), B12(1), B31(1), B51(1)とすると、次のようになる。
タスクt21に対して:   B21(1) ← B21 - {b2}, B21(1) = {}
タスクt22に対して:   B22(1) ← B22 - {b2}, B22(1) = {}
タスクt11に対して:   B11(1) ← B11 - {b2}, B11(1) = {}
タスクt12に対して:   B12(1) ← B12 - {b2}, B12(1) = {}
タスクt31に対して:   B31(1) ← B31 - {b2}, B31(1) = {b4}
タスクt51に対して:   B51(1) ← B51 - {b2}, B51(1) = {}
【００９７】
この結果、ブロック集合B21(1), B22(1), B11(1), B12(1), B51 (1) が空集合({})になり、タスクt21, t22, t11, t12,t51の処理が終了する。すると、トランザクションT2内のすべてのタスクの処理が終了するので、この時点でトランザクションT2をコミットできるかどうかを、図４（ａ）の先行グラフをもとにして決定する。接点T2には、他のどの接点からも入力している枝がないので、トランザクションT2をコミットすることになる。T2をコミットすると、図４（ａ）の先行グラフから接点T2と接点T2から出力しているすべての枝を削除し、その結果を図４（ｂ）の先行グラフとして表わすことができる。
また、トランザクションT1,T5によるレコードD.r7に対する更新処理は終了したけれども、T1,T5はまだコミットしていないため、図４（ｂ）の先行グラフ内の接点T1から接点T5へと入力しているD.r7の枝を点線の枝として残しておくことにする。
【００９８】
[(c-2) ブロックb4にアクセス]
次に、リレーションDEPARTMENT内のブロックの格納位置が768であるブロックb4内のデータをディスクからメインメモリに読み込み、すでに処理が終了したタスクt21, t22, t11, t12, t51以外のグループ内のタスクt31, t32, t52, t41, t42, t61, t62, t63がブロックb4で処理を行う必要があるかどうかを調べるため、ブロックb4を集合{b4}として表し、{b4}とブロック集合B31(1), B32, B52, B41, B42, B61, B62, B63との間でそれぞれ積集合(∩)を求めると次のようになる。
【００９９】
タスクt31に対して:   B31(1) ∩ {b4} = {b4}
タスクt32に対して:   B32 ∩ {b4} = {b4}
タスクt52に対して:   B52 ∩ {b4} = {}
タスクt41に対して:   B41 ∩ {b4} = {}
タスクt42に対して:   B42 ∩ {b4} = {b4}
タスクt61に対して:   B61 ∩ {b4} = {}
タスクt62に対して:   B62 ∩ {b4} = {}
タスクt63に対して:   B63 ∩ {b4} = {}
【０１００】
タスクt31, t32, t42に対して積集合が{b4}となり、ブロックb4で処理が可能となり、メインメモリに読み込んだブロックb4でタスクt31, t32, t42の処理を行うと次のようになる。
【０１０１】
【表３】
0004261609.tif 000004
レコードD.r19に関しては、図４（ｂ）の先行グラフに示すトランザクションT3, T4の実行順に、それらのトランザクションの部分処理であるタスクt31, t42の更新処理を順次行っていく。
【０１０２】
タスクt31は、データベースから読み込んだレコードD.r19に対して更新処理を行い、タスクt42は、タスクt31が更新したレコードD.r19に対して更新処理を行うことになる。このようにタスクt31, t42による更新処理をメインメモリ内で順次行い、タスクt42による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
タスクt32の検索処理は、レコードD.r19を検索することである。そのためメインメモリに読み込まれたレコードD.r19に対して、タスクt32と同じトランザクションT3に含まれるタスクt31の更新処理が先に行われると、タスクt42の更新処理が行われる前に、タスクt31によるレコードD.r19の更新結果を、タスクt32の検索結果として取り出すことになる。
【０１０３】
ブロックb4でのタスクt31, t32, t42の処理が終了すると、ブロックb4を再びアクセスする必要がなくなるので、集合B31(1), B32, B42と集合{b4}との差集合を求めて、得られた差集合をB31(2), B32(1), B42(1)とすると、次のようになる。
タスクt31に対して:   B31(2) ← B31(1) - {b4},  B31(2) = {}
タスクt32に対して:   B32(1) ← B32 - {b4},  B32(1) = {}
タスクt42に対して:   B42(1) ← B42 - {b4}, B42(1) = {}
この結果、ブロック集合B31(2), B32(1), B42(1)が空集合({})になり、タスクt31, t32, t42の処理が終了し、トランザクションT3に含まれるすべてのタスクの処理が終了することになり、トランザクションT3が終了すると、この時点でトランザクションT3をコミットできるかどうかを、図４（ｂ）の先行グラフをもとにして決定する。接点T3には、他のどの接点からも入力枝がないので、トランザクションT3をコミットする。T3をコミットすると、接点T3と接点T3から出力している枝を図４（ｂ）の先行グラフから削除し、その結果を図４（ｃ）の先行グラフとして表わすことができる。
【０１０４】
[(c-3) ブロックb3の読み込み]
次に、リレーションDEPARTMENT内のブロックの格納位置が512であるブロックb3内のデータをディスクからメインメモリに読み込み、すでに処理が終了したタスクt21, t22, t11, t12,t31,t32, t51, t42 以外のグループ内のタスクt52, t41, t61, t62, t63がブロックb3で処理を行う必要があるかどうかを調べるため、ブロックb3を集合{b3}として表し、この{b3}とブロック集合B52, B41, B61, B62, B63との間でそれぞれ積集合(∩) を求めると次のようになる。
【０１０５】
タスクt52に対して:  B52 ∩ {b3} = {b3}
タスクt41に対して:  B41 ∩ {b3} = {}
タスクt61に対して:  B61 ∩ {b3} = {b3}
タスクt62に対して:  B62 ∩ {b3} = {}
タスクt63に対して:  B63 ∩ {b3} = {}
【０１０６】
タスクt52, t61に対して積集合が{b3}となり、ブロックb3で処理が可能となり、メインメモリに読み込んだブロックb3でタスクt52, t61の処理を行うと次のようになる。
【０１０７】
【表４】
0004261609.tif 000005
【０１０８】
レコードD.r14に関しては、図４（ｃ）の先行グラフに示すトランザクションT5, T6の実行順に、それらのトランザクションの部分処理であるタスクt52, t61の更新処理を順次行っていく。
タスクt52は、データベースから読み込んだレコードD.r14に対して更新処理を行い、タスクt61は、タスクt52が更新したレコードD.r14に対して更新処理を行うことになる。このようにタスクt52,t61による更新処理をメインメモリ内で順次行い、タスクt61による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
ブロックb3でのタスク t52,t61の処理が終了すると、ブロックb3を再びアクセスする必要がなくなるので、ブロック集合 B52, B61と集合{b3}との差集合を求めて、得られた差集合をB52(1),B61(1)とすると、次のようになる。
タスクt52に対して:   B52(1) ← B52 - {b3},  B52(1) = {}
タスクt61に対して:   B61(1) ← B61 - {b3},  B61(1) = {b1}
この結果、ブロック集合B52(1)が空集合({})になり、タスクt52の処理が終了する。
【０１０９】
タスクt52の処理が終了すると、トランザクションT5に含まれるすべてのタスクの処理が終了することになり、この時点でトランザクションT5をコミットできるかどうかを、図４（ｃ）の先行グラフをもとにして決定する。トランザクションT5は、トランザクションT1が先に処理を行ったレコードD.r7に対して処理を行っていて、トランザクションT1はまだコミットしていないため、トランザクションT5をコミットすることはできない。そのためT5をコミット待ちのトランザクションとして置いておくことになる。図４（ｄ）の先行グラフは、トランザクションT5の処理は終了したけれども、コミットできない状態を点線の接点T5として表わしている。
また、トランザクションT5,T6によるレコードD.r14に対する更新処理は終了したけれども、T5,T6はまだコミットしていないため、図４（ｄ）の先行グラフ内の接点T5から接点T6へと入力しているD.r14の枝を点線の枝として残しておくことにする。
【０１１０】
[(c-4) ブロックb1にアクセス]
次に、リレーションDEPARTMENT内のブロックの格納位置が0であるブロックb1内のデータをディスクからメインメモリに読み込み、すでに処理が終了したタスクt21, t22, t11, t12,t31,t32, t51, t52,t42以外のグループ内のタスクt41, t61, t62, t63 がブロックb1で処理を行う必要があるかどうかを調べるため、ブロックb1を集合{b1}として表し、この{b1}とブロック集合B41, B61(1), B62, B63との間でそれぞれ積集合(∩) を求めると次のようになる。
タスクt41に対して:   B41  ∩ {b1} = {b1}
タスクt61に対して:   B61(1)  ∩ {b1} = {b1}
タスクt62に対して:   B62  ∩ {b1} = {}
タスクt63に対して:   B63  ∩ {b1} = {}
【０１１１】
タスクt41, t61に対して積集合が{b1}となり、ブロックb1で処理が可能となり、メインメモリに読み込んだブロックb1でタスクt41, t61の処理を行うと次のようになる。
【０１１２】
【表５】
0004261609.tif 000006
レコードD.r3に関しては、図４（ｄ）の先行グラフに示すように、トランザクションT4,T6の実行順に、それらのトランザクションの部分処理であるタスクt41,t61の更新処理を順次行っていく。タスクt41は、データベースから読み込んだレコードD.r3に対して更新処理を行い、タスクt61は、タスクt41が更新したレコードD.r3に対して更新処理を行うことになる。このようにタスクt41,t61による更新処理をメインメモリ内で順次行い、タスクt61による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
【０１１３】
ブロックb1でのタスクt41,t61の処理が終了すると、ブロックb1を再びアクセスする必要がなくなるので、ブロック集合B41, B61(1)と集合{b1}との差集合を求めて、得られた差集合をB41(1), B61(2)とすると、次のようになる。
t41に対して:   B41(1) ← B41  - {b1},  B41(1) = {}
t61に対して:   B61(2) ← B61(1) - {b1}, B61(2) = {}
この結果、ブロック集合B41(1),B61(2)が空集合({})になり、タスクt41, t61の処理が終了する。図４（ｅ）の先行グラフは、トランザクションT4,T6によるレコードD.r3に対する更新処理が終了したけれども、トランザクションT4,T6の処理がまだ終了していないので、接点T4から接点T6へと入力しているD.r3の枝を点線の枝として残していることを表わしている。
【０１１４】
[(c-5) ブロックb5の読み込み]
最後に、リレーションDEPARTMENT内のブロックの格納位置が1024であるブロックb5内のデータをディスクからメインメモリに読み込み、ブロックb5でグループG1内の最後のタスクt62,t63の処理を行うと次のようになる。
【０１１５】
【表６】
0004261609.tif 000007
タスクt62は、データベースから読み込んだレコードD.r22に対して更新処理を行う。
タスクt63は、データベースから読み込んだレコードD.r23を取り出して検索することになる。
【０１１６】
タスクt62, t63の処理が終了すると、トランザクションT6内のすべてのタスクの処理が終了するので、この時点でトランザクションT6をコミットできるかどうかを、図４（ｅ）の先行グラフをもとにして決定する。トランザクションT6は、トランザクションT5が先に処理を行ったレコードD.r14に対して処理を行い、トランザクションT4が先に処理を行ったレコードD.r3に対して処理を行っているが、トランザクションT5,T4はまだコミットしていないので、トランザクションT6をコミットすることはできない。したがって、トランザクションT6はコミット待ちのトランザクションとして置いておくことになる。図４（f）の先行グラフは、トランザクションT6の処理は終了したけれども、コミットできない状態を点線の接点T6として表わしている。
タスクt62, t63の処理が終了すると、グループG1内のすべてのタスクの処理が終了することになる。グループG1の処理が終了すると、合成トランザクションに含まれるグループG2の処理を開始することになる。
【０１１７】
[(6-2) グループG2の処理]
リレーションEMPLOYEEに対するグループG2の処理は、グループG1の処理と同様に、グループG2内のタスクに対してマルチオペレーション・プロセッシングを用いて処理することになる。
【０１１８】
[(a) タスクがアクセスするブロックの集合]
図３−２のリレーションEMPLOYEE(400)の主インデックス（410)及び二次インデックス(420)を用いて、グループG2内のタスクt71, t13, t81, t43を処理するために読み出す必要のあるリレーションEMPLOYEE内のすべてのブロックを調べて、個々のタスクに対応するブロック集合B71, B13,B81, B43に集めると次のようになる。
タスクt71に対して、B71 = {b2}      
タスクt13に対して、B13 = {b4}    
タスクt81に対して、B81 = {b2, b3}  
タスクt43に対して、B43 = {b3}          
【０１１９】
[(b) ブロックのアクセス順位の決定]
ブロック集合を見出すと、グループ内のタスクが並べられた順に、すなわちt71, t13, t81, t43の順番で各タスク対応するブロック集合の和集合を求めていくと次のようになる。
TB0 ← {} (空集合)
ブロック集合B71との和集合:  TB71 ← TB0 U B71,  TB71 = {b2}
ブロック集合B13との和集合:  TB13 ← TB71 U B13,  TB13 = {b2, b4}
ブロック集合B81との和集合:  TB81 ← TB13 U B81,  TB81 = {b2, b4, b3}
ブロック集合B43との和集合:  TB43 ← TB81 U B43,  TB43 = {b2, b4, b3}
以上のようにして順次和集合を求めていくと、最後の和集合TB43から、リレーションEMPLOYEEに対して、ブロックb2からブロックのアクセスを開始し、ブロックb3でアクセスを終了すればよいことになり、ブロックのアクセス順は(b2, b4, b3)となる。
【０１２０】
[(c) 各ブロックでのタスク処理]
[(c-1) ブロックb2にアクセス]
最初に、リレーションEMPLOYEE(400)内のブロックの格納位置が256であるブロックb2内のデータをディスクからメインメモリに読み込み、グループ内のタスクt71, t13, t81, t43がブロックb2で処理を行う必要があるかどうかを調べるため、ブロックb2を集合{b2}として表し、{b2}とブロック集合B71, B13, B81, B43との間でそれぞれ積集合(∩) を求めると次のようになる。
タスクt71に対して:  B71 ∩ {b2} = {b2}
タスクt13に対して:  B13 ∩ {b2} = {} 
タスクt81に対して:  B81 ∩ {b2} = {b2}
タスクt43に対して:  B43 ∩ {b2} = {}
【０１２１】
タスクt71, t81に対して積集合が{b2}となり、ブロックb2で処理が可能となり、メインメモリに読み込んだブロックb2でタスクt71, t81の処理を行うと次のようになる。
【０１２２】
【表７】
0004261609.tif 000008
レコードE.r6に関しては、図４（f）の先行グラフに示すように、レコードE.r6に対して、トランザクションT7,T8の実行順に、それらのトランザクションの部分処理であるタスクt71,t81の更新処理を順次行っていく。タスクt71は、データベースから読み込んだレコードE.r6に対して更新処理を行い、タスクt81は、タスクt71が更新したレコードE.r6に対して更新処理を行うことになる。このようにタスクt71,t81による更新処理をメインメモリ内で順次行い、タスクt81による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
【０１２３】
ブロックb2でのタスクt71, t81の処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、ブロック集合B71, B81と集合{b2}との差集合を求めて、得られた差集合をB71(1), B81(1)とすると、次のようになる。
タスクt71に対して:   B71(1) ← B71 - {b2}, B71(1) = {}
タスクt81に対して:   B81(1) ← B81 - {b2}, B81(1) = {b3}
この結果、ブロック集合B71(1)が空集合({})になり、タスクt71の処理が終了する。タスクt71の処理が終了するとトランザクションT7内のすべてのタスクの処理が終了することになり、図４（f）の先行グラフをもとにして、この時点でトランザクションT7をコミットすることができるかどうかを決定する。接点T7には、他のどの接点からも入力枝がないので、トランザクションT7をコミットする。T7をコミットすると、図４（f）の先行グラフから接点T7と接点T7から出ているすべての枝を削除し、その結果を図４（g）の先行グラフとして表わすことができる。
【０１２４】
[(c-2) ブロックb4の読み込み]
次に、リレーションEMPLOYEE(400)内のブロックの格納位置が768であるブロックb4内のデータをディスクからメインメモリに読み込み、すでに処理が終了したタスクt71以外のグループ内のタスクt81, t13, t43がブロックb4で処理を行う必要があるかどうかを調べるため、ブロックb4を集合{b4}として表し、この{b4}とブロック集合B81(1), B13, B43との間でそれぞれ積集合(∩) を求めると次のようになる。
タスクt81に対して:  B81(1) ∩ {b4} = {}
タスクt13に対して:  B13 ∩ {b4} = {b4} 
タスクt43に対して:  B43 ∩ {b4} = {}
タスクt13に対して積集合が{b4}となり、ブロックb4で処理が可能となり、メインメモリに読み込んだブロックb4でタスクt13の更新処理を行うと次のようになる。
【０１２５】
【表８】
0004261609.tif 000009
【０１２６】
ブロックb4でのタスクt13の処理が終了すると、ブロックb4を再びアクセスする必要がなくなるので、ブロック集合B13と集合{b4}との差集合を求めて、得られた差集合をB13(1)とすると、次のようになる。
タスクt13に対して:   B13(1) ← B13 - {b4}, B13(1) = {}
この結果、ブロック集合B13(1)が空集合({})になり、タスクt13の処理が終了する。タスクt13の処理が終了すると、トランザクションT1内のすべてのタスクの処理が終了するため、この時点でトランザクションT1がコミットできるかどうかを、図４（g）の先行グラフをもとにして決定する。接点T1には、他のどの接点からも入力枝がないので、トランザクションT1をコミットする。トランザクションT1をコミットすると、接点T1と接点T1から出力しているすべての枝も削除される。T1が削除されると、接点T1から接点T5へと入力している枝が削除され、接点T5の入力枝がすべてなくなるため、トランザクションT5もコミットすることになる。トランザクションT1, T5がコミットした結果は、図４（h）の先行グラフとして表わすことができる。
【０１２７】
[(c-3) ブロックb3にアクセス]
最後に、リレーションEMPLOYEE内のブロックの格納位置が512であるブロックb3内のデータをディスクからメインメモリに読み込み、ブロックb3でグループG2内に残ったタスクt81,t43の処理を行うと次のようになる。
【０１２８】
【表９】
0004261609.tif 000010
レコードE.r10に関しては、図４（h）の先行グラフに示すように、レコードE.r10に対して、トランザクションT8,T4の実行順に、それらのトランザクションの部分処理であるタスクt81,t43の更新処理を順次行っていく。タスクt81は、データベースから読み込んだレコードE.r10に対して更新処理を行い、タスクt43は、タスクt81が更新したレコードE.r10に対して更新処理を行うことになる。このようにタスクt81,t43による更新処理はメインメモリ内で順次行い、タスクt43による最後の更新結果のみをデータベースに一度だけ書き込むことになる。
【０１２９】
タスクt81,t43の処理が終了すると、トランザクションT8,T4のすべてのタスクが終了し、この時点で入力枝のないトランザクションT8をコミットすることができ、さらにトランザクションT4もコミットすることができので、図４（h）の先行グラフから接点T8, T4を削除する。そうすると、接点T4から接点T6へと伸びる枝も削除され、接点T6の入力枝がすべてなくなる（図４（i）参照）ため、トランザクションT6もコミットすることになる。その結果、入力されたすべてのトランザクションがT2, T3, T7, T1, T5, T8, T4, T6の順番でコミットしたことになる。
【０１３０】
以上のことをまとめると表１０のようになる。グループG1の処理を行うには、リレーションDEPARMENT(300)に対して、ブロックb2でタスクt21, t22, t11, t12, t31, t51の処理を行ってトランザクションT2の処理が終了してコミットし、ブロックb4でタスクt31, t32, t42の処理を行ってトランザクションT3の処理が終了してコミットし、ブロックb3でタスクt52, t61の処理を行ってトランザクションT5の処理が終了し、ブロックb1ではタスクt41,t61の処理を行い、ブロックb5でタスクt62,t63の処理を行ってトランザクションT6の処理が終了する。
グループG2の処理を行うには、リレーションEMPLOYEE（400)に対して、ブロックb2でタスクt71, t81の処理を行ってトランザクションT7が終了してコミットし、ブロックb4でタスクt13の処理を行ってトランザクションT1が終了してトランザクションT1,T5がコミットし、ブロックb3でタスクt81, t43の処理を行ってトランザクションT8,T4の処理が終了してトランザクションT8, T4, T6がコミットする。
【０１３１】
【表１０】
0004261609.tif 000011
このようにして、入力された複数のトランザクションの処理が同時に行われ、T2, T3, T7, T1, T5, T8, T4, T6の順にトランザクションが終了してコミットすることになる。トランザクションがコミットした順は、最初に決定したトランザクションの実行順と若干異なるけれども、どちらの順もサイクルを含んでいない図４（ａ）の先行グラフをトポロジカルソートして得ることができる順なので、この手法は、トランザクションの実行順と競合等価な直列可能スケジュールである。
【０１３２】
以上のように、同時に処理することのできる複数のトランザクションに対して、トランザクションの実行順を決定し、決定した順にデータを更新することを示した先行グラフを作成し、トランザクションに含まれる部分処理をタスクとして取り出し、取り出したタスクを、トランザクションの実行順に、データベースのリレーションごとにグループ分けし、グループ分けして作成したグループを用いて合成トランザクションを作成し、合成トランザクションに含まれる個々のグループに対してマルチオペレーション・プロセッシングを用いて処理を行っていくのがトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングによるデータベースのトランザクション処理システムである。
【０１３３】
上記の具体例では、複数のトランザクションによって処理されるレコードをデータ項目として扱って説明した。レコードをデータ項目として扱うと、数多くのレコードが処理される場合、個々のレコードの格納位置を調べて、膨大な先行グラフを作成することになる。そのため、レコードが格納してあるブロックの格納位置だけを調べて、ブロックをデータ項目として扱い、ブロックに対して先行グラフを作成してもよい。その場合、アクセスしたブロックが先行グラフに存在するときに、そのブロックに対して、グループ内のタスク処理を順次行っていくことになる。
また、上記の具体例では、readとwriteを基本とするトランザクションの更新処理を扱った。実際の更新処理には、データの挿入や削除も行われる。マルチオペレーション・プロセッシングを用いてデータの挿入を行うには、データを挿入するブロックの格納位置を調べて、そのブロックに十分なスペースがある場合は、ブロックのアクセス順にしたがってそのブロックをアクセスした際に、データを挿入することになる。また、マルチオペレーション・プロセッシングを用いてデータの削除を行うには、データを削除するブロックの格納位置を調べて、ブロックのアクセス順にしたがってそのブロックをアクセスした際に、データを削除することになる。
【０１３４】
合成トランザクションに含まれる個々のグループの処理は、異なるリレーションに対して行われるため、それらのグループの処理を同時に行っても、グループ間で同一のデータ項目がアクセスされることはない。また、グループに集められたトランザクションの部分処理であるタスクの処理は、メインメモリに読み込まれたブロック内のデータ項目に対して、先行グラフに示したトランザクションの実行順に順次実行していくので、合成トランザクションに合成された個々のトランザクションの間でロックをかける必要はない。したがってトランザクションが待たされたり、トランザクションが中断されたりするといった問題は起こらない。
【０１３５】
本発明のトランザクション同時実行制御を備えたマルチオペレーション・プロセッシングにおいては、数多くのトランザクションが入力されると、1.1節で述べた手順にしたがって合成トランザクションを作成し、合成トランザクションの処理を行っていくことができ、１つの合成トランザクションの処理が終了した段階で、新たに数多くのトランザクションが入力されると、同様な手順を用いて別の合成トランザクションを作成し、その合成トランザクションの処理を行っていくことができるので、合成トランザクションの処理を順次１つずつ実行していく場合には、ロックを用いる必要性はなくなる。また、デッドロックなどを発生することもなく、合成トランザクションに含まれる複数のグループの処理を同時に並行して実行していくことができる。
【０１３６】
このような処理で複数のトランザクションの処理速度を十分に向上させることができるが、図１のオペレーティング・システムのプロセス(104) によるCPUとディスクの資源(105)を効率よく利用するには、複数の合成トランザクションを同時に処理したほうが、効率がいい場合があるので、第２章では複数の合成トランザクションの処理を同時に実行していくためのシステムを提案する。
【０１３７】
[2. 複数の合成トランザクションの処理]    
合成トランザクションの処理を行っている間に、新たに別のトランザクションがいくつか到着すると、到着した複数のトランザクションに対して合成トランザクションが作成され、現在処理が行われている合成トランザクションと一緒に処理が行われると、複数の合成トランザクションの間でデータの矛盾が起こる可能性が出てくる。
例えば、合成トランザクションTG1,G2の処理を行っている間に、図１のトランザクション処理システム（100）に、新たにトランザクションT9,T10,T11が到着すると、トランザクションT9,T10,T11に対して合成トランザクションTG3,G4,G5を作成したとする。マルチオペレーション・プロセッサ（102）は、現在プロセス１とプロセス２を用いて合成トランザクションTG1,G2の処理を行っていたとすると、残ったプロセス３とプロセス４とプロセス５を用いて合成トランザクションTG3,G4,G5の処理を行うことになる。合成トランザクションTG1,G2と合成トランザクションTG3,G4,G5が同一のデータ項目に対して処理を行う必要がある場合、同時にデータが更新されてデータの矛盾が起こる可能性が出てくる。
複数の合成トランザクションの処理が競合してデータの矛盾が起こるといった問題を解決するために、二相ロックを用いたマルチオペレーション・プロセッシングとタイムスタンプを用いたマルチオペレーション・プロセッシングを提案する。
【０１３８】
<二相ロックを用いたマルチオペレーション・プロセッシング>
二相ロックを用いたマルチオペレーション・プロセッシングは、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングに、二相ロックを加えたものである。二相ロックを用いたマルチオペレーション・プロセッシングは、合成トランザクションが処理を行う個々のデータ項目に対してロックをかけて処理を行う手法である。ロックの操作は、ロックをかける操作だけからなる成長相とロックをはずす操作だけからなる縮退相と分離して行う。そのため一度ロックをはずした後に、再びロックをかけることはない。なお、ロックをかけるにあたって、検索処理しか行わないデータ項目に対しては、共有ロックをかけ、更新処理を行うデータ項目に対しては、専有ロックをかけることになる。複数の合成トランザクションの間でデータの矛盾が起こらないようにするには、個々の合成トランザクションは、二相ロックを用いたマルチオペレーション・プロセッシングを使用して処理を行うことになる。
【０１３９】
二相ロックを用いたマルチオペレーション・プロセッシングが、従来の二相ロック・プロトコルと異なる点は、従来のように複数のトランザクションの間でロックをかけるのではなく、マルチオペレーション・プロセッシングの処理を行う複数の合成トランザクションの間でロックをかける点である。また、合成トランザクション自体がコミットするのではなく、合成トランザクションに含まれる個々のトランザクションが順次コミットしていくことである。
また、複数の合成トランザクションの間でデッドロックが生じた場合の対処は、従来のデッドロックの対処と異なる。複数の合成トランザクションの間でデッドロックが生じた場合、デッドロックの関係にある合成トランザクションの１つを中断することになり、中断する合成トランザクションは、合成トランザクションに含まれるトランザクションの中で、コミットしたトランザクションの数が最も少ない合成トランザクションを中断することになる。合成トランザクションの処理を中断するには、合成トランザクションに含まれるトランザクションの中で、すでにコミットしたトランザクションはそのままにしておき、まだコミットしていないトランザクションのみを中断してロールバックし、中断したトランザクションは、トランザクション処理システム(100)に再提出することになる。
【０１４０】
<二相ロックを用いたマルチオペレーション・プロセッシングの具体例>
図５−１，図５−２は、二相ロックを用いたマルチオペレーション・プロセッシングを使用して２つの合成トランザクションT G1,G2, TG3,G4,G5の処理を同時に並行して実行しているものを表わしている。合成トランザクションT G1,G2は1.2章の具体列で用いた合計２つのリレーションDEPARTMENT(300), EMPLOYEE(400)に対して処理を行う合成トランザクションであり、合成トランザクションTG3,G4,G5は、図１のトランザクション処理システム(100)に新たに到着したトランザクションT9,T10,T11から作成された合計３つのリレーションPROJECT,EMPLOYEE,DEPARTEMTに対して処理を行う合成トランザクションである。
図５−１，図５−２において、レコードrに対して共有ロックをかける操作をread_lock(r)として表わし、レコードrに対して専有ロックをかける操作をwrite_lock(r)として表わし、レコードrに対してロックをはずす操作をunlock(r)として表わしている。また、リレーションDEPARTMENT(300)内のレコードは、D.riとして表わし、リレーションEMPLOYEE(400)内のレコードはE.riとして表わし、リレーションPROJECT(図示せず)内のレコードはP.riと表わすことにする。
【０１４１】
図５−１及び図５−２では、合成トランザクションTG1,G2は、時間経過とともに、レコードD.r6,D.r7,D.r8,D.r9,D.19,D.r14,D.r3,D.22,D.23,E.r6,E.r14, E.r10の順にロックをかけて、すべてのロックをかけた後に、マルチオペレーション・プロセッシングによるレコードの処理が終了したレコードから順番にロックをはずしていることが示されている。
合成トランザクションTG3,G4,G5の処理も同様に、時間経過とともに、レコードP.r9,P.r18,E.r11,E.r21,D.r13,D.r14,D.r15,D.r19の順番にロックをかけ、すべてのロックをかけた後に、マルチオペレーション・プロセッシングによるレコードの処理が終了したレコードから順番にロックをはずしている。合成トランザクションTG1,G2と合成トランザクションTG3,G4,G5に含まれるトランザクションは、T2, T9, T3, T11,T10,T7,T1,T5,T8,T4,T6の順番でコミットしている。
【０１４２】
二相ロックを用いたマルチオペレーション・プロセッシングは、ロックをかける実行順によってはデッドロックを生じる場合がある。例えば、図６の合成トランザクションT G1,G2は、レコードD.r14に対してロックをかけようとし、合成トランザクションTG3,G4,G5は、レコードD.r19に対してロックをかけようとしているけれども、お互いに必要なレコードを先にロックし合っているためデッドロックの関係にある。
このデッドロックを解除するには、合成トランザクションTG1,G2,又は合成トランザクションTG3,G4,G5のどちらかを中断することになるが、合成トランザクションTG1,G2は、１つのトランザクションT2をすでにコミットしていて、合成トランザクションTG3,G4,G5は２つのトランザクションT11,T9をすでにコミットしているため、コミットしたトランザクションの数が少ない方の合成トランザクションTG1,G2の処理を中断することになる。合成トランザクションTG1,G2の処理を中断するには、すでにコミットしたトランザクションT2はそのままにしておき、まだコミットしていないトランザクションT7,T3,T1,T5,T8,T4,T6だけを中断してロックバックし、中断したトランザクションをトランザクション処理システム(100)に再提出することになる。
このようにして、個々の合成トランザクションに対して、二相ロックを用いたマルチオペレーション・プロセッシングを用いて処理を行うことによって、複数の合成トランザクションが同時に同一のデータ項目に対して更新処理を行うことがなくなり、データの矛盾が起こることはなくなる。
【０１４３】
<タイムスタンプを用いたマルチオペレーション・プロセッシング>
タイムスタンプを用いたマルチオペレーション・プロセッシングは、複数の合成トランザクションの処理を同時に実行するにあたって、個々の合成トランザクションにタイムスタンプを与え、タイムスタンプの小さい合成トランザクションから順番に処理していく。タイムスタンプを用いたマルチオペレーション・プロセッシングが、従来のタイムスタンプ・プロトコルと異なる点は、従来のように個々のトランザクションに対してタイムスタンプを与えるのではなく、個々の合成トランザクションに対してタイプスタンプを与えることであり、また、個々のトランザクションが処理を行うデータ項目に対してタイムスタンプを与えるのではなく、個々の合成トランザクションが処理を行うデータ項目に対してタイムスタンプを与えることである。なお、複数の合成トランザクションの間でデータの矛盾が起こった場合は、データの矛盾が起こった合成トランザクションの処理を中断することになる。合成トランザクションの処理を中断するには、合成トランザクションに含まれるトランザクションの中ですでにコミットしたトランザクションはそのままにしておき、まだコミットしていないトランザクションだけを中断してロールバックして、トランザクション処理システムに再提出することになる。
【０１４４】
<タイムスタンプを用いたマルチオペレーション・プロセッシングの手順>
タイムスタンプを用いたマルチオペレーション・プロセッシングは、複数の合成トランザクションが処理を行うデータ項目Xに対して、読み込みタイムスタンプread_TS(X)と書き込みのタイムスタンプwrite_TS(X)を与える。
read_TS(X)は、データ項目Xを読み込むことに成功したいくつかの合成トランザクションの中で、最もタイムスタンプの大きい合成トランザクションのタイムスタンプである。
write_TS(X)は、データ項目Xを書き込むことに成功したいくつかの合成トランザクションの中で、最もタイムスタンプの大きい合成トランザクションのタイムスタンプである。
合成トランザクションのタイムスタンプは、TS(TG1,G2,…Gn)として表わし、合成トランザクションに含まれる個々のトランザクションに対してタイムスタンプ(到着時間)を与え、タイムスタンプを与えられたトランザクションの中で、最もタイムスタンプの大きいトランザクションのタイムスタンプを合成トランザクションのタイムスタンプとする。
合成トランザクションTG1,G2,…Gnがデータ項目Xに対して書き込み処理write_item(X)、読み込み処理read_item(X)を行う場合は、次の規約に従って実行していくことになる。
【０１４５】
ケース１ 項目Ｘに対する書き込み処理：
合成トランザクションTG1,G2,…Gnがデータ項目Xに対しての書き込み処理write_item(X)を要求した場合
ａ．read_TS(X) > TS(TG1,G2,…Gn)、又はwrite_TS(X) > TS(TG1,G2,…Gn)であるならば、合成トランザクションTG1,G2,…Gnの処理を中断し、合成トランザクションTG1,G2,…Gnに含まれるトランザクションの中で、まだコミットしていないトランザクションの処理を中断する。中断したトランザクションはロールバックし、トランザクション処理システムに再提出する。
ｂ．aの条件を満たさない場合は、合成トランザクションTG1,G2,…Gnのwrite_item(X)を実行し、write_TS(X)の値をTS(TG1,G2,…Gn)とする。
【０１４６】
ケース２ 項目Ｘに対する読み込み処理：
合成トランザクションTG1,G2,…Gnがデータ項目Xに対して読み込み処理read_item(X)を要求した場合
ａ．write_TS(X) > TS(TG1,G2,…Gn)であるならば、合成トランザクションTG1,G2,…Gnの処理を中断し、TG1,G2,…Gnに含まれるトランザクションの中でまだコミットされていないトランザクションの処理を中断する。中断したトランザクションはロールバックし、トランザクション処理システムに再提出する。
ｂ．write_TS(X) ≦ TS(TG1,G2,…Gn)であるならば、TG1,G2,…Gnのread_item(X)を実行し、TS(TG1,G2,…Gn)の値がread_TS(X)よりも大きければ、read_TS(X)の値をTS(TG1,G2,…Gn)とする。
次に、タイムスタンプを用いたマルチオペレーション・プロセッシングの手順を用いて、合成トランザクションTG1,G2と合成トランザクションTG3,G4,G5の処理を同時に行った場合について説明することにする。
【０１４７】
<タイムスタンプを用いたマルチオペレーション・プロセッシングの具体例>
図７は、タイムスタンプを用いたマルチオペレーション・プロセッシングを使用して合成トランザクションTG1,G2と合成トランザクションTG3,G4,G5の処理を同時に実行しているのを表わしている。
合成トランザクションTG3,G4,G5は、レコードD.r19に対して更新処理を行うにあたって、合成トランザクションTG1,G2がレコードD.r19を読み出した（S704)後に、レコードD.r19を読み出している(S706)けれども、合成トランザクションTG1,G2よりも先にレコードD.r19を書き込んでいる(S708)。そのため、その後に、合成トランザクションTG1,G2がレコードD.r19を書き込む(S709)と、合成トランザクションTG3,G4,G5が書き込んだr19に対する値が上書きされるため、合成トランザクションTG1,G2の処理を中断することになる。タイムスタンプを用いたマルチオペレーション・プロセッシングがどのようにして、このデータの矛盾を見つけるかは次に述べるとおりである。
【０１４８】
合成トランザクションTG1,G2のタイムスタンプを8(合成トランザクションTG1,G2に含まれるトランザクションの中で最もタイムスタンプの大きいトランザクションT8のタイムスタンプを8とした場合)とし（S701）、合成トランザクションTG3,G4,G5のタイムスタンプを11(合成トランザクションTG3,G4,G5に含まれるトランザクションの中で最もタイムスタンプの大きいトランザクションT11のタイムスタンプを11とした場合)とした（S702）とする。
【０１４９】
最初に、合成トランザクションTG1,G2がレコードD.r19を読み出すときに、write_TS(D.r19)の値が0（初期の値）であったとすると、ケース２のbの条件write_TS(D.r19) ≦ TS(TG1,G2)を満たすため、read_item(D.r19)を実行し（S703)、read_TS(D.r19) の値を8とする（S704）。
次に、合成トランザクションTG3,G4,G5がレコードD.r19を読み出す(S705)ときに、write_TS(D.r19)の値が0であったとすると、TS(TG3,G4,G5)の値は11であり、ケース２のbの条件write_TS(D.r19) ≦ TS(TG5)を満たすために、read_item(D.r19)を実行し(S705)、read_TS(D.r19)の値を8から11にする（S706)。
【０１５０】
次に、合成トランザクションTG3,G4,G5がレコードD.r19に書き込み処理write_item(D.r19)を要求する場合（S707)、ケース１のaのread_TS(D.r19) > TS(TG3,G4,G5), 又はwrite_TS(D.r19) > TS(TG3,G4,G5)の条件を満たすかどうかを確認する。read_TS(D.r19)の値は11、write_TS(D.r19)の値は0、TS(TG3,G4,G5)の値は11であり、ケース１のaの条件を満たさないので、ケース１のbのwrite_item(D.r19) を実行し（S707)、write_TS(D.r19)の値を11とする（S708)。
【０１５１】
次に、合成トランザクションTG1,G2がデータ項目D.r19の書き込み処理write_item(D.r19)を要求する場合（S709)、ケース１のaのread_TS(D.r19) > TS(TG1,G2), 又はwrite_TS(D.r19) > TS(TG1,G2)の条件を満たすかどうかを確認する。read_TS(D.r19)の値は11、write_TS(D.r19)の値は11、TS(TG1,G2)の値は8であり、ケース１のaの条件を満たしているので、合成トランザクションTG1,G2の処理を中断することになる。
合成トランザクションTG1,G2を中断するには、合成トランザクションTG1,G2に含まれるトランザクションの中ですでにコミットしたトランザクションT2はそのままにしておき、まだコミットしていないトランザクションT7, T3, T1, T5, T8, T4, T6の処理を中断し、ロールバックすることになる。中断されたトランザクションT7, T3, T1, T5, T8, T4, T6は、トランザクション処理システムに再提出する。
このようにして、タイムスタンプを用いて複数の合成トランザクションの処理を行うのがタイムスタンプを用いたマルチオペレーション・プロセッシングである。
【０１５２】
[３．高度なクエリーがトランザクションに含まれている場合のトランザクション処理]
結合演算の処理を行うクエリーなど、複雑で高度なクエリーがトランザクションに含まれている場合、どのようにしてトランザクションを処理するかを、具体例を用いて説明する。図３−１のリレーションDEPARTMENT(300)と図３−２のリレーションEMPLOYEE(400)に対して、下記に示すような処理を行う３つのトランザクションT12,T13,T14がトランザクション処理システムに入力されたとする。
【０１５３】
(T12):BEGIN WORK;
-- T12の更新処理１
UPDATE DEPARTMENT
SET BUDGET = BUDGET + 9000
WHERE DNUMBER = 7;
-- T12の更新処理２
UPDATE EMPLOYEE
SET MGRSSN = 470191111
WHERE SSN > 1876767888 AND SSN < 2111111124;
-- T12のクエリー１
SELECT *
FROM DEPARTMENT, EMPLOYEE
WHERE DNUMBER = 7 AND
SSN > 2111111124 AND SSN < 2411111133 AND
DNUMBER = DNUM;
COMMIT WORK;
【０１５４】
(T13):BEGIN WORK;
-- T13の更新処理１
UPDATE EMPLOYEE
SET DNUM = 8
WHERE SSN = 2311111132;
COMMIT WORK;
-- T13のクエリー１
SELECT *
FROM DEPARTMENT, EMPLOYEE
WHERE DPHONE = '23-3711' AND 
SSN > 2834567894 AND DNUM = DNUMBER;
-- T13の更新処理２
UPDATE DEPARTMENT  -- T2の更新処理１
SET DNAME = 'SHIPPING'
WHERE DNUMBER = 7;
COMMIT WORK;
【０１５５】
(T14):BEGIN WORK;
-- T14の更新処理1
UPDATE EMPLOYEE
SET PHONE = '23-5600'
WHERE SSN = 2311111132;
-- T14の更新処理２
UPDATE DEPARTMENT
SET BUDGET = BUDGET + 4000
WHERE DNUMBER > 6 AND DNUMBER < 9;
COMMIT WORK;
【０１５６】
入力されたトランザクションの処理を行うにあたって、トランザクションに含まれる結合演算の処理を行うクエリーに対しては、処理ツリーを作成する必要がある。トランザクションT12,T13には、それぞれ結合演算の処理を行うクエリー含まれているので、トランザクション処理システムは、クエリーの最適化を用いて、それらのクエリーに対して、図８に示す処理ツリー(a),(b)を作成する。処理ツリー内の結合演算は|X|で表わし、選択演算はσで表わすことにする。
処理ツリーを作成すると、トランザクション処理システムは、トランザクションT12,T13,T14に対して、トランザクションに含まれる部分処理をタスクとして表わし、トランザクションの部分処理を作成すると次のようになる。
【０１５７】
(T12):
(t121):read_item(D.r7);
D.r7.BUDGET := D.r7. BUDGET + 9000;
write_item(D.r7);
(t122):read_item(E.r9);
E.r9.MGRSSN := 470191111;
write_item(E.r9);
read_item(E.r10);
E.r10.MGRSSN := 470191111;
write_item(E.r10);
(t123):read_item(D.r7);
(t124):read_item(E.r12);
read_item(E.r13);
(t125):TEMP_T12_3 |X|DNUMBER=DNUMTEMP_T12_4;
【０１５８】
(T13):        
(t131):read_item(E.r13);
E.r13.DNUM = 8;
write_item(E.r13);
(t132):read_item(D.r6);
(t133):read_item(E.r19);
read_item(E.r20);
(t134):TEMP_T13_2 |X|DNUMBER=DNUMTEMP_T13_3;
(t135):read_item(D.r7); 
D.r7.DNAME := 'SHIPPING';
write_item(D.r7);
【０１５９】
(T14):        
(t141):read_item(E.r13);
E.r13.PHONE := '23-5600';
write_item(E.r13);
(t142):read_item(D.r7);
D.r7.BUDGET := D.r7.BUDGET + 4000;
write_item(D.r7);
read_item(D.r8);
D.r8.BUDGET := D.r8.BUDGET + 4000;
write_item(D.r8);
【０１６０】
上記のタスクt123は、図８(a)の処理ツリー内の選択演算σDNUMBER=7DEPARTMENTを処理するためのタスクである。
上記のタスクt124は、図８(a)の処理ツリー内の選択演算σSSN>2111111124 AND SSN<2411111133 EMPLOYEEを処理するためのタスクである。
上記のタスクt132は、図８(b)の処理ツリー内の選択演算σDPHONE = '23-3711'DEPARTMENTを処理するためのタスクである。
上記のタスクt133は、図８(b)の処理ツリー内の選択演算σSSN > 2834567894EMPLOYEEを処理するためのタスクである。
【０１６１】
上記のタスクt125は、図８(a)の処理ツリー内の結合演算であり、トランザクションの部分処理ではTEMP_T12_3|X|DNUMBER=DNUMTEMP_T12_4としておく。TEMP_T12_3は、タスクt123の選択処理を行ったときに作成される一時表であり、TEMP_T12_4はタスクt124の選択処理を行ったときに作成される一時表である。タスクt125の結合処理は一時表TEMP_T12_3,TEMP_T12_4ができたときに、実行されることになる。
上記のタスクt134は、図８(b)の処理ツリー内の結合演算であり、トランザクションの部分処理ではTEMP_T13_2 |X|DNUMBER=DNUMTEMP_T13_3としておく。TEMP_T13_2は、タスクt132の選択処理を行ったときに作成される一時表であり、TEMP_T13_3はタスクt133の選択処理を行ったときに作成される一時表である。タスクt125の結合処理は一時表TEMP_T13_2,TEMP_T13_3ができたときに、実行されることになる。
【０１６２】
トランザクションの部分処理を作成すると、トランザクションの実行順を決定する。トランザクションの実行順を決定するには、トランザクションに含まれる部分処理をもとにして、トランザクションの処理コストを求め、トランザクションの処理コストの小さい順にトランザクションを並べてトランザクションの実行順を決定することにする。
トランザクションT12の処理コストを6とし、トランザクションT13の処理コストを5とし、トランザクションT14の処理コストを2とした場合、トランザクションの実行順をT14,T13,T12と決定することができる。
【０１６３】
トランザクションの実行順を決定すると、トランザクションの実行順にデータを更新することを示した図８(c)の先行グラフに作成する。
トランザクションT13,T12は同一のレコードD.r7,E.r13に対して処理を行うため、トランザクションの実行順に接点T13から接点T12へと枝を入力する。
トランザクションT14,T13は同一のレコードD.r7,E.r13に対して処理を行うため、トランザクションの実行順に接点T14から接点T13へと枝を入力する。
トランザクションT14,T12は同一のレコードE.r13に対して処理を行うため、トランザクションの実行順に接点T14から接点T12へと枝を入力する。
【０１６４】
先行グラフを作成すると、トランザクションの実行順にトランザクションT14,T13,T12に含まれる部分処理をタスクとして取り出し、取り出したタスクを、トランザクションの実行順に、データベースのリレーションごとにグループ分けすると次のようになる。
DEPARTMENT:  グループ  G6  =  {t142, t132, t135, t121, t123}
EMPLOYEE:    グループ  G7  =  {t141, t131, t133, t122, t124}
TEMP_T13_3:  グループ  G8  =  {t134}
TEMP_T12_4:  グループ  G9  =  {t125}
【０１６５】
結合演算のタスクをグループ分けするには、結合演算の検索元に使用する一時表をリレーションとみなしてグループ分けすることになり、一時表TEMP_T13_3を結合演算の検索元に使用するタスクt134をグループG8集め、一時表TEMP_T12_4を結合演算の検索元に使用するタスクt125をグループG9に集めることにする。
タスクがグループ分けされて、グループG6,G7,G8,G9が作成されると、グループG6,G7,G8,G9を用いて合成トランザクションTG6,G7,G8,G9を作成し、合成トランザクションTG6,G7,G8,G9に含まれる個々のグループに対して、第一章で述べたマルチオペレーション・プロセッシングを用いて処理することになる。
【０１６６】
グループの処理を行うにあたって、グループG8内のタスクt134の結合処理は、グループG6内のタスクt132の選択処理とグループG7内のタスクt133の選択処理が終了してから始めることなる。
また、グループG9内のタスクt125の結合処理はグループG6内のタスクt123の選択処理とグループG7内のタスクt124の選択処理が終了してから始めることになる。
最初にグループG6とグループG7の処理が終了すると、トランザクションT14内のすべてのタスクの処理が終了することになるので、トランザクションT14の処理が終了してコミットすることになる。トランザクションT14がコミットすると、図13(c)の先行グラフから接点T14とその接点から出ているすべての枝を削除する。その結果は、図13(d)の先行グラフとして表わすことができる。
【０１６７】
次にグループG8の結合処理が終了してタスクt134の処理が終了すると、トランザクションT13内のすべてのタスクの処理が終了するので、トランザクションT13が終了してコミットすることになる。トランザクションT13がコミットすると、図13(d)の先行グラフから接点T13とその接点から出ているすべての枝を削除する。その結果は図13（e)先行グラフとして表わすことができる。
最後にグループG9の結合処理が終了してタスクt125の処理が終了すると、トランザクションT12内のすべてのタスクが終了するので、トランザクションT12の処理が終了してコミットすることになる。その結果、合成トランザクションTG6,G7,G8,G9の処理が完了し、入力されたトランザクションT12,T13,T14の処理がすべて終了し、コミットしたことになる。
【０１６８】
以上に述べたように、本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングは、高度なクエリー処理がトランザクションに含んでいる場合にも対応することができる。
【０１６９】
[４. 実験結果]
本章では、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングによるトランザクション処理の評価のために行った実験とその結果について考察する。実験では、第１章で述べた本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングによるトランザクションの処理時間と、トランザクションの処理を別々に行う従来の二相ロック・プロトコルによるトランザクションの処理時間を測定し、両者の処理時間を比較した。
【０１７０】
トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの処理は、トランザクション処理システムに入力された複数のトランザクションに対して1.1節で述べた手順にしたがって合成トランザクションを作成し、合成トランザクションの処理を行い、１つの合成トランザクションの処理が終了した段階で、新たに数多くのトランザクションが入力されると、同様な手順を用いて別の合成トランザクションを作成し、その合成トランザクションの処理を行っていき、合成トランザクションの処理を順次１つずつ実行した。また、合成トランザクションに含まれる複数のグループの処理は、オペレーティング・システムの複数のプロセスを用いて同時に並行して実行した。
【０１７１】
実験を行うには、Windows XP Professional(登録商標)を搭載したパーソナルコンピューター(1つのCeleron CPU 1.73GHzプロセッサ、1GBメインメモリ、1つの145GBディスク)をデータベース・サーバーとして使用した。データベース・サーバーには、独自に開発したデータベース・マネージメント・システムのソフトウェアMOP-DBをインストールし、このソフトウェアを用いて、6つのリレーションから構成されるデータベースを作成し、個々のリレーション対して、主インデックス、2次インデックスなどのインデックスを加えた。MOP-DBのソフトウェアは、従来の二相ロック・プロトコルによるトランザクションの処理と、本発明のトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングによるトランザクションの処理の両方ができるように開発しておいた。
次に、独自のクライアントプログラムを作成し、クライアントプログラムからSQLで記述された数多くのトランザクションをデータベース・サーバーに入力し、データベース・サーバーによってすべてのトランザクションが処理されてコミットするまでの時間を測定して、それぞれの手法によるトランザクションの処理時間を求めた。
【０１７２】
＜実験１: トランザクションの数の影響＞
各リレーションに100万件ずつレコードを格納し、6つのリレーションに対して合計600万件ほどのレコードをデータベースに加え、データベースに同時に問い合わせるトランザクションの数を1000件から10000件まで変化させたときの処理時間を図９(a).(b)の表とグラフに示した。トランザクションの処理時間が速くなることは処理速度が速くなることであると考えると、トランザクションの数が1000件から10000件までの件数において、全体的にトランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの処理速度のほうが従来の二相ロック・プロトコルの処理速度よりも速いことがわかる。トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングは、トランザクションの数が1000件から5000件までは、図９(a)の表から、従来の二相ロック・プロトコルの処理速度よりも平均して18.36倍の処理速度が得られ、トランザクションの数が6000件から10000件までは、従来の二相ロック・プロトコルの処理速度よりも平均して19.98倍の処理速度が得られた。
【０１７３】
トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングは、トランザクションの数が増えるにつれて処理速度も速くなっていく傾向がある。
図9(b)のグラフに示すように、従来の二相ロック・プロトコルは、トランザクションの数が増えると、数多くのトランザクションが同一のデータ項目を何度も繰り返して読み出し、読み出したレコードに対して更新処理を別々に行い、更新された結果を何度も繰り返してデータベースに書き込むため、トランザクションの処理速度が低下することになった。
一方、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングは、同時に処理するトランザクションの数が増加すると、複数のトランザクションが処理を行う同一のデータ項目を一度だけ読み出し、読み出したレコードに対して複数のトランザクションの更新処理を順次メインメモリ内で行い、最後に更新された結果だけをデータベースに一度だけしか書き込まないので、トランザクションの処理速度が向上した。
【０１７４】
＜実験２: データベースサイズの影響＞
データベースの6つのリレーションに格納されるレコード数を60万件から600万件へと変化させ、それぞれのサイズのデータベースに10000件のトランザクションの処理を一度に要求したときの処理時間を図10(a).(b)の表とグラフに示した。
図10(a).(b)の表とグラフに示すように、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングは、レコード数が60万件から300万件までは、従来の二相ロック・プロトコルの処理速度よりも平均して8.04倍の処理速度が得られ、レコード数が360万件から600万件までは、従来の二相ロック・プロトコルの処理速度よりも平均して15.59倍の処理速度が得られ、データベースのサイズが大きくなるにつれて、処理速度が向上していく傾向がある。従来の二相ロック・プロトコルは、データベースのサイズが大きくなるにつれ、個々のトランザクションの処理に時間がかかるようになった。一方、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングは、データベースのサイズに関係なく効率よく個々の合成トランザクションの処理を実行することができた。
【０１７５】
[５. おわりに]
トランザクション処理システムに入力された複数のトランザクションを処理するにあたって、個々のトランザクションを別々に処理することによって発生する従来の問題を解決するために、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを提案した。
このシステムは、トランザクション処理システムに複数のトランザクションが入力されると、入力されたトランザクションに対して、トランザクションの部分処理を求め、トランザクションの実行順を決定し、決定した順にデータを更新することを示した先行グラフを作成し、トランザクションに含まれる個々の部分処理をタスクとして取り出し、取り出したタスクを、トランザクションの実行順にデータベースのリレーションごとにグループ分けし、グループ分けして作成したグループを用いて合成トランザクションを作成し、合成トランザクションに含まれる個々のグループに対してマルチオペレーション・プロセッシングを用いて処理を行っていくシステムである。
【０１７６】
マルチオペレーション・プロセッシングは、グループにタスクが並んだ順にブロックへのアクセス順を決定し、決定したアクセス順にブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出し、ブロック内のデータ項目に対して、グループ内のタスクが並んだ順にタスク処理を順次行っていく。
ブロック内のデータ項目に対して、グループ内のタスクが並んだ順にタスク処理を順次行っていくということは、ブロック内のデータ項目が先行グラフに存在する場合、そのデータ項目に対して先行グラフに示したトランザクションの実行順にトランザクションの部分処理であるタスク処理を順次行っていくことであり、複数のタスクがそのデータ項目に対して更新処理を行う場合、そのデータ項目に対して最初のタスクの更新処理を行い、更新されたデータ項目に対して次のタスクの更新処理を行い、このような更新処理を繰り返し、最後のタスクの更新処理が行われると、最後に更新された更新結果だけをデータベースに書き込んでいくことである。
【０１７７】
このシステムを用いることによって、従来のトランザクションの処理のように、入力された複数のトランザクションに対して、トランザクションごとに同じデータ項目を何度も繰り返して検索し、検索したデータ項目に対して更新処理を別々に行い、更新された結果を何度も繰り返してデータベースに書き込む必要がなくなった。
本発明のシステムは、複数のトランザクションが処理を行うデータ項目に対して、そのデータ項目を一度だけ検索し、検索したデータ項目に対して、複数のトランザクションの更新処理を順次メインメモリ内で行い、最後に更新した結果だけをデータベースに一度だけ書き込めばよいので、極めて効率的に複数のトランザクションの処理を行うことができるようになった。
本発明は、入力された複数のトランザクションに対して、サイクルを含んでいない先行グラフを作成し、複数のトランザクションによって処理されるデータ項目に対して、先行グラフに示したトランザクションの実行順にトランザクションの処理を順次行っていくので、入力された複数のトランザクションは直列可能スケジュール(serializable schedule)で処理される。
【０１７８】
合成トランザクションに含まれる個々のグループの処理は、異なるリレーションに対して行うため、それらのグループの処理を同時に行っても、複数のグループ間で同一のデータ項目がアクセスされることはない。グループに集められたタスクの処理は、メインメモリに読み込まれたブロック内のデータ項目に対して、先行グラフに示したトランザクションの実行順に順次行っていくので、入力された複数のトランザクションの間でロックをかけたり、トランザクションを待たせたり、トランザクションを中断したりするといった必要がなくなった。
本発明は、入力された複数のトランザクションに対して１つの合成トランザクションを作成し、合成トランザクションの処理を行っていくことができ、１つの合成トランザクションの処理が終了した段階で、新たに複数のトランザクションが入力されると、それらのトランザクションに対して別の合成トランザクションを作成し、その合成トランザクションの処理を行っていくことができるので、合成トランザクションの処理を１つずつ実行していく場合には、ロックを用いる必要はなくなる。また、デッドロックなどを発生することもなく、合成トランザクションに含まれる複数のグループの処理を同時に並行して実行していくことができるようになった。
合成トランザクションを１つずつ実行していくことで十分にトランザクションの処理速度を向上させることができるが、CPUやディスクなどハードウェア資源を効率よく利用することを考慮する場合には、複数の合成トランザクションを同時に並行して実行することを取り上げ、これらの複数の合成トランザクションの処理を同時に並行して実行するために、二相ロックを用いたマルチオペレーション・プロセッシングとタイムスタンプを用いたマルチオペレーション・プロセッシングを提案した。
【図面の簡単な説明】
【０１７９】
【図１】トランザクション処理システムのアーキテクチャの構成を示す図である。
【図２−１】トランザクション処理システムのフローチャートを示す図である。
【図２−２】トランザクション処理システムのフローチャートを示す図である。
【図３−１】データベースのリレーションの例を示す図である。
【図３−２】データベースのリレーションの例を示す図である。
【図４】複数のトランザクションによるデータの更新順を表わした先行グラフの例を示す図である。
【図５−１】二相ロックを用いたマルチオペレーション・プロセッシングの例を示す図である。
【図５−２】二相ロックを用いたマルチオペレーション・プロセッシングの例を示す図である。
【図６】複数の合成トランザクション間でのデッドロックの例を示す図である。
【図７】タイムスタンプを用いたマルチオペレーション・プロセッシングの例を示す図である。
【図８】処理ツリーと先行グラフの例を示す図である。
【図９】トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの実験結果を示す（ａ）表，（ｂ）グラフである。
【図１０】トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングの実験結果を示す（ａ）表，（ｂ）グラフである。
【要約】
【課題】
数多くのトランザクションを効率よく同時に処理するために、トランザクションの同時実行制御を備えたマルチオペレーション・プロセッシングを用いたデータベースのトランザクション処理システムを提案する。
【解決手段】
入力された複数のトランザクションを別々に処理するのではなく、入力された複数のトランザクションが処理を行うデータ項目に対して、そのデータ項目を一度だけ検索し、検索したデータ項目に対して、複数のトランザクションの更新処理を順次メインメモリ内で行い、最後に更新した結果だけをデータベースに一度だけ書き込むことを用いる。
複数の合成トランザクションの処理を同時に並行して実行するために、トランザクションの同時実行制御を備えたマルチオペレーションに、二相ロックを用いたマルチオペレーション・プロセッシングと、タイムスタンプを用いたマルチオペレーション・プロセッシングを用いている。
【選択図】図１【図１】
0004261609.tif 000012
【図２−１】
0004261609.tif 000013
【図２−２】
0004261609.tif 000014
【図３−１】
0004261609.tif 000015
【図３−２】
0004261609.tif 000016
【図４】
0004261609.tif 000017
【図５−１】
0004261609.tif 000018
【図５−２】
0004261609.tif 000019
【図６】
0004261609.tif 000020
【図７】
0004261609.tif 000021
【図８】
0004261609.tif 000022
【図９】
0004261609.tif 000023
【図１０】
0004261609.tif 000024