(57)【要約】【課題】階層型データを複数のトランザクションが並行してアクセスする場合にもトランザクションの分離性を保証することができるトランザクション処理システムを提供すること。【解決手段】各トランザクションの開始時に各トランザクション用の階層型データのコピーを作成する。第１のトランザクションがコピーに対して読み出し又は書き込みを行う場合に、該アクセスと該第２のトランザクションがコピーに対して行った書き込み又は読み出しアクセスとが衝突するか判定し、衝突回避を行う。その後、第１のトランザクションが正常に終了する場合には、それがコピーに行った書き込みアクセスを、階層型データに反映させるとともに、第２のトランザクションが未終了ならば該トランザクション用のコピーにも反映させる。【選択図】    図１
2004234567.tif 000002
【特許請求の範囲】
【請求項１】
階層型データを対象として複数のトランザクションを並列に処理するトランザクション処理システムにおける並行制御方法であって、
各トランザクションが前記階層型データへのアクセスを開始するにあたって、前記階層型データのコピーを作成するコピーステップと、
第１のトランザクションが該第１のトランザクション用の階層型データのコピーに対して読み出し又は書き込みの一方のアクセスを行う場合に、該アクセスと、第２のトランザクションが該第２のトランザクション用の階層型データのコピーに対して行った読み出し又は書き込みの他方のアクセスとの間に衝突が発生するか否かを判定する判定ステップと、
この判定ステップにおいて衝突が発生すると判定された場合に、衝突を回避するための処理を行う処理ステップと、
前記第１のトランザクションが正常に終了する場合に、該第１のトランザクションが該第１のトランザクション用の階層型データのコピーに行った書き込みアクセスを、前記階層型データに反映させるとともに、前記第２のトランザクションが未だ終了していないときは、該書き込みアクセスを、該第２のトランザクション用の階層型データのコピーにも反映させる反映ステップとを有することを特徴とする並行制御方法。
【請求項２】
前記判定ステップでは、前記書き込みアクセスを考慮せずに前記読み出しアクセスを行って参照されるデータと、前記書き込みアクセスを考慮して前記読み出しアクセスを行って参照されるデータとの間の同一性に基づいて、前記衝突が発生するか否かを判定することを特徴とする請求項１に記載の並行制御方法。
【請求項３】
前記判定ステップでは、前記第１のトランザクションが前記階層型データのコピーに対して読み出しアクセスを行う場合には、該第１のトランザクション用の階層型データのコピーに対して該読み出しアクセスを行うときに参照される第１のデータと、該第１のトランザクション用の階層型データのコピーと前記第２のトランザクション用の階層型データのコピーとをマージしたものに対して同じ読み出しアクセスを行うときに参照される第２のデータとの間の同一性を調べ、その結果に基づいて前記衝突が発生するか否かを判定することを特徴とする請求項１に記載の並行制御方法。
【請求項４】
すべての前記第２のトランザクションについて前記第１のデータと前記第２のデータとの間に同一性があると判断された場合に、前記衝突が発生しないと判定し、それ以外の場合に、前記衝突が発生すると判定することを特徴とする請求項３に記載の並行制御方法。
【請求項５】
前記第１のトランザクションが前記階層型データのコピーに対して書き込みアクセスを行う場合に、前記階層型データをアクセスするすべてのトランザクションによる書き込みアクセスを反映させるために前記階層型データをコピーして作成された共有コピーに対しても同じ書き込みアクセスを行うステップを更に有し、
前記判定ステップでは、前記第１のトランザクションが前記階層型データのコピーに対して読み出しアクセスを行う場合には、該読み出しアクセスによって参照される第１のデータと、前記階層型データの共有コピーに対して同じ読み出しアクセスを行うときに参照される第２のデータとの間の同一性を調べ、その結果に基づいて前記衝突が発生するか否かを判定することを特徴とする請求項１に記載の並行制御方法。
【請求項６】
前記第１のデータと前記第２のデータとの間に同一性があると判断された場合に、前記衝突が発生しないと判定し、同一性がないと判断された場合に、前記衝突が発生すると判定することを特徴とする請求項５に記載の並行制御方法。
【請求項７】
前記判定ステップでは、前記第１のトランザクションが前記階層型データのコピーに対して書き込みアクセスを行う場合には、前記階層型データをアクセスするすべての前記第２のトランザクションのすべての読み出しアクセスについて、当該読み出しアクセスを行ったときに参照された第１のデータと、該書き込みアクセスを行った後における前記階層型データの状態に対して当該読み出しアクセスを行った当該第２のトランザクションを実行した場合に、当該読み出しアクセスを行うときに参照する第２のデータとの間の同一性を調べ、その結果に基づいて前記衝突が発生するか否かを判定することを特徴とする請求項１に記載の並行制御方法。
【請求項８】
前記階層型データをアクセスするすべての前記第２のトランザクションのすべての読み出しアクセスについて前記第１のデータと前記第２のデータとの間に同一性があると判断された場合に、前記衝突が発生しないと判定し、それ以外の場合に、前記衝突が発生すると判定することを特徴とする請求項７に記載の並行制御方法。
【請求項９】
前記階層型データをアクセスするすべてのトランザクションについて、各トランザクション毎に、当該トランザクションが前記階層型データのコピーに対して行ったアクセスの系列を記録するステップを更に有し、
前記判定ステップでは、前記アクセスの系列の記録を参照して、前記階層型データをアクセスするすべての前記第２のトランザクションのすべての読み出しアクセスを求めることを特徴とする請求項７または８に記載の並行制御方法。
【請求項１０】
前記読み出しアクセスが行われたときに参照されたデータを記録するステップを更に有し、
前記判定ステップでは、前記参照されたデータの記録を参照して、前記第１のデータを求めることを特徴とする請求項７または８に記載の並行制御方法。
【請求項１１】
前記判定ステップでは、前記読み出しアクセスを行ったトランザクションの開始時における前記階層型データの状態に対して該トランザクションが該読み出しアクセス以前に行った書き込みアクセスを行い、これによって得られる階層型データの状態に対して前記読み出しアクセスを行い、この結果得られるデータを、前記第１のデータとすることを特徴とする請求項７または８に記載の並行制御方法。
【請求項１２】
前記第１のトランザクションが前記階層型データのコピーに対して書き込みアクセスを行う場合に、前記階層型データをアクセスするすべてのトランザクションによる書き込みアクセスを反映させるために前記階層型データをコピーして作成された共有コピーに対しても同じ書き込みアクセスを行うステップと、
前記階層型データをアクセスするいずれかのトランザクションが書き込みアクセスを行った時点における前記共有コピーの状態を保存するステップとを更に有し、
前記判定ステップでは、保存されている前記共有コピーの状態のうちから、前記読み出しアクセスを行った時点における前記階層型データの状態に近いものを選択するとともに、必要に応じて該共有コピーの状態に対して該読み出しアクセスを行ったトランザクションが行った書き込みアクセスを行って、該読み出しアクセスを行った時点における階層型データの状態を再現し、再現された該階層型データの状態に対して該読み出しアクセスを行い、この結果得られるデータを、前記第１のデータとすることを特徴とする請求項７または８に記載の並行制御方法。
【請求項１３】
前記判定ステップでは、前記第１のトランザクション用の階層型データのコピーに対して前記書き込みアクセスを行った後の状態に対して、前記第２のトランザクションが前記読み出しアクセス以前に行った書き込みアクセスを行い、これによって得られる階層型データの状態に対して前記読み出しアクセスを行い、この結果得られるデータを、前記第２のデータとすることを特徴とする請求項７または８に記載の並行制御方法。
【請求項１４】
前記第１のトランザクションが前記階層型データのコピーに対して書き込みアクセスを行う場合に、前記階層型データをアクセスするすべてのトランザクションによる書き込みアクセスを反映させるために前記階層型データをコピーして作成された共有コピーに対しても同じ書き込みアクセスを行うステップと、
前記階層型データをアクセスするいずれかのトランザクションが書き込みアクセスを行った時点における前記共有コピーの状態を保存するステップとを更に有し、
前記判定ステップでは、保存されている前記共有コピーの状態のうちから、前記読み出しアクセスを行いたい時点における前記階層型データの状態に近いものを選択し、該共有コピーの状態に対して、前記書込みアクセスを行ったトランザクションがその時点以降に行った書込みアクセスを行うとともに、必要に応じて該読み出しアクセスを行ったトランザクションが行った書き込みアクセスを行って、該読み出しアクセスを行いたい時点における階層型データの状態を再現し、再現された該階層型データの状態に対して該読み出しアクセスを行い、この結果得られるデータを、前記第２のデータとすることを特徴とする請求項７または８に記載の並行制御方法。
【請求項１５】
前記共有コピーの保存数に上限がある場合には、前記階層型データの各書き込みアクセス時の状態に対応する前記共有コピーのうち、後で読み出しアクセスを行いたい状態を再現するときに利用される可能性の高いものを優先して保存することを特徴とする請求項５、１２または１４に記載の並行制御方法。
【請求項１６】
前記処理ステップでは、前記判定ステップにおいて衝突が発生すると判定された場合に、前記衝突に係るトランザクションのうち、所定の基準で決定されるものを、前記衝突に係る他のトランザクションが終了するまで待機させることを特徴とする請求項１ないし１５のいずれか１項に記載の並行制御方法。
【請求項１７】
階層型データを対象として複数のトランザクションを並列に処理するトランザクション処理システムであって、
各トランザクションが前記階層型データへのアクセスを開始するにあたって、前記階層型データのコピーを作成するコピー手段と、
第１のトランザクションが該第１のトランザクション用の階層型データのコピーに対して読み出し又は書き込みの一方のアクセスを行う場合に、該アクセスと、第２のトランザクションが該第２のトランザクション用の階層型データのコピーに対して行った読み出し又は書き込みの他方のアクセスとの間に衝突が発生するか否かを判定する判定手段と、
この判定手段において衝突が発生すると判定された場合に、衝突を回避するための処理を行う処理手段と、
前記第１のトランザクションが正常に終了する場合に、該第１のトランザクションが該第１のトランザクション用の階層型データのコピーに行った書き込みアクセスを、前記階層型データに反映させるとともに、前記第２のトランザクションが未だ終了していないときは、該書き込みアクセスを、該第２のトランザクション用の階層型データのコピーにも反映させる反映手段とを備えたことを特徴とするトランザクション処理システム。
【請求項１８】
階層型データを対象として複数のトランザクションを並列に処理するトランザクション処理システムとしてコンピュータを機能させるためのプログラムであって、
各トランザクションが前記階層型データへのアクセスを開始するにあたって、前記階層型データのコピーを作成するコピー機能と、
第１のトランザクションが該第１のトランザクション用の階層型データのコピーに対して読み出し又は書き込みの一方のアクセスを行う場合に、該アクセスと、第２のトランザクションが該第２のトランザクション用の階層型データのコピーに対して行った読み出し又は書き込みの他方のアクセスとの間に衝突が発生するか否かを判定する判定機能と、
この判定機能において衝突が発生すると判定された場合に、衝突を回避するための処理を行う処理機能と、
前記第１のトランザクションが正常に終了する場合に、該第１のトランザクションが該第１のトランザクション用の階層型データのコピーに行った書き込みアクセスを、前記階層型データに反映させるとともに、前記第２のトランザクションが未だ終了していないときは、該書き込みアクセスを、該第２のトランザクション用の階層型データのコピーにも反映させる反映機能とをコンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、階層型データモデルに基づくデータベースを対象としたトランザクション処理システム、該トランザクション処理システムにおける並行制御方法及びプログラムに関する。
【０００２】
【従来の技術】
トランザクション処理システムでは、トランザクションと呼ぶ処理の流れを単位として処理の実行を管理する。個々のトランザクションは、実行過程で、データベースのファイルに記録管理するデータにアクセスして、データの参照または更新を行う。
【０００３】
一般にトランザクション処理システムでは、複数のトランザクションを並行に処理することで性能の向上を計る。その際、システムは、複数のトランザクションを並行に処理した場合の実行結果と、個々のトランザクションを１つずつ直列に処理した場合の実行結果とが同じであるように、トランザクションのアクセスを制御する必要がある。このことを、トランザクションの分離性（ｉｓｏｌａｔｉｏｎ）を保証する、あるいは、その実行は直列可能（ｓｅｒｉａｌｉｚａｂｌｅ）であるという。
【０００４】
トランザクションの分離性を保証するためには、並行に処理する複数のトランザクションが同じデータにアクセスすることを回避する必要がある。そのため、分離性の保証において扱いが難しいのは、同時に複数のトランザクションが１つのファイル上のデータにアクセスする場合である。複数のトランザクションが同じファイルにアクセスすることを許さなければこの問題は生じない。しかし、複数のトランザクションを並行に処理してシステムの性能を向上させるためには、１つのファイルの中の異なる部分に記録管理するデータに同時に複数のトランザクションがアクセスできるようにする必要がある。
【０００５】
この問題を解決するために最も一般的に用いられている方式はロックである。ロック方式では、あるトランザクションがアクセスを行ったデータをそのトランザクションが終了するまでロックすることで、並行して処理する他のトランザクションが同じファイル上の同じ部分のデータにアクセスすることを回避し、同じファイル上の異なる部分のデータのみにアクセスすることを可能にする。しかし、トランザクションの分離性を保証するロック方式を実現するためには、ファントム（ｐｈａｎｔｏｍ）と呼ばれる問題を解決しなければならない。
【０００６】
ファントムとは、トランザクションがすでに削除したデータ、あるいは、これから挿入する可能性があるデータを表し、その時点においては存在しないデータである。例えば、あるトランザクションＴ１が条件Ｐを満たすデータを読み出した後に、並行に処理する他のトランザクションＴ２が条件Ｐを満たすようなあるデータを削除あるいは挿入したとする。トランザクションＴ２のアクセスによってデータが更新された後にトランザクションＴ１が条件Ｐを満たすデータの読出しを再度行ったときの結果は、トランザクションＴ２のアクセスの前にトランザクションＴ１が読出しを行ったときの結果と異なる。
【０００７】
トランザクションの分離性を保証するためには、トランザクションＴ２が削除あるいは挿入したデータに対してロックを行い、並行に処理するトランザクションＴ１がファントムにアクセスできないようにする必要がある。しかし、ロックの対象であるデータはファントムであり、すでに削除されているか、あるいは、まだ挿入されていないためにロックの時点においては存在しない。したがって、ファントムはその扱いが困難である。
【０００８】
ファントムの問題を解決する主なロック方式として、インデックスロック（ｉｎｄｅｘ  ｌｏｃｋ）、述語ロック（ｐｒｅｄｉｃａｔｅ  ｌｏｃｋ）、プレシジョンロック（ｐｒｅｃｉｓｉｏｎ  ｌｏｃｋ）の３つの方式が知られている（例えば、非特許文献１参照）。
【０００９】
１つ目のインデックスロックでは、データそのものではなく、データのインデックス（ｉｎｄｅｘ）をロックの対象とする。インデックスはデータの検索を高速にするために用いるデータの値に基づいた索引であり、インデックスの構造としてＢ−Ｔｒｅｅ、ハッシュテーブルなどの種類が知られている。インデックスロックでは、インデックスの構造を利用して、ファントムを参照する可能性があるインデックスの範囲をロックすることによってファントムの問題を解決し、トランザクションの分離性を保証する。
【００１０】
２つ目の述語ロックでは、データそのものではなく、データの集合を特定する述語をロックの対象とすることで、ファントムの問題を解決する。通常、トランザクションが行うデータへのアクセスは、そのデータを特定する述語によって行われる。述語ロックでは、あるトランザクションがアクセスに使用した述語をロックし、他のトランザクションがアクセスに使用する述語とすでにロックした述語を比較することで、トランザクションの分離性が破られないかを検査する。
【００１１】
３つ目のプレシジョンロックは、この述語ロックを改善した方式であり、述語ロックと同様にファントムの問題を解決できる。この方式の特徴は、トランザクションがデータへのアクセスを要求したときに、他のトランザクションがすでに行ったアクセスで使用した述語とそのデータを比較することである。比較の結果、データが述語を充足しなければトランザクションの分離性は維持される。
【００１２】
【非特許文献１】
“Ｔｒａｎｓａｃｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ：  Ｃｏｎｃｅｐｔｓ  ａｎｄ  Ｔｅｃｈｎｉｑｕｅｓ”  （Ｊｉｍ  Ｇｒａｙ，  ＡｎｄｒｅａｓＲｅｕｔｅｒ著，  Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，  １９９３）
【００１３】
【発明が解決しようとする課題】
トランザクション処理の対象となるデータの集合あるいはファイルを管理する方式として、従来はリレーショナルデータモデルに基づく関係データベースが主流であったが、近年では階層型モデルのデータを管理するデータベースの必要性が高まっている。階層型データモデルの例としては、インターネット上で交換するデータの標準フォーマットとして注目されているＸＭＬがある。
【００１４】
ここで、階層型データモデルに基づくデータベースを対象としてトランザクション処理を行う場合について、従来の３つのロック方式、すなわち、インデックスロック、述語ロック、プレシジョンロックのそれぞれが抱える問題点について述べる。
【００１５】
まず、インデックスロックでは、データのファイルから導出するインデックス構造を使用する。リレーショナルデータモデルに対してはＢ−Ｔｒｅｅなどの有効なインデックス構造が知られており、従来のほとんどの関係データベースはインデックスロックに基づく方式を採用している。しかし、階層型データモデルでは、データの親子関係がツリー構造で表現される、あるいは、データの重複が許されるなどといった理由から、有効なインデックス構造を導出できない。この問題を解決するために、階層型データモデルをリレーショナルデータモデルに変換して関係データベースとして管理する方式もある。しかし、そのような方式は、データのファイルが持つ本来の階層構造を効率よく管理できず、かつ、すべての階層型データモデルに対して有効ではないといった問題点がある。そのため、階層型データモデルに基づくデータベースに対してインデックスロックを使用するのは困難である。
【００１６】
述語ロックでは、トランザクションの分離性を検査するために述語同士の比較を行う必要がある。一般に述語の充足性判定はＮＰ完全であることが知られており、述語ロックの実装には大変コストがかかる。
【００１７】
述語ロックを改善した方式であるプレシジョンロックでは、述語同士の比較を行う代わりにデータと述語の比較を行うため、述語ロックに比べてコストが小さい。また、トランザクションがアクセスに使用した述語を予めロックする方法ではなく、アクセスが要求された時点において分離性の検査を行う方法を用いるので、トランザクションの並行処理性に優れている。しかし、インデックスロックと比べるとコストが高いという問題点があり、関係データベースが主流であった従来では、インデックスロックに基づく方式が主に使用されていた。さらに、プレシジョンロックについては、概念のみが知られており、実装方式は提案されていない。プレシジョンロックを階層型データモデルに適用するためには、トランザクションがアクセスして更新しようとする階層型データが、並行に処理する他のトランザクションのアクセス時にすでに使用された述語を充足するか否かの判定をして分離性の検査を行う必要がある。しかし、このような問題を解決する実用的な方式は、まだ提案されていない。
【００１８】
現状では、ＸＭＬデータのような階層型データモデルに基づくデータベースに対してトランザクションの分離性を保証するためには、並行に処理するトランザクションがアクセスするデータファイル全体をロックするといった方式が使用されている。
【００１９】
本発明は、上記事情を考慮してなされたもので、階層型データを複数のトランザクションが並行してアクセスする場合にも、トランザクションの分離性を保証することができる、あるいは、その実行が直列化可能であるように処理の順序を制御することができるトランザクション処理システム、並行制御方法及びプログラムを提供することを目的とする。
【００２０】
【課題を解決するための手段】
本発明は、階層型データを対象として複数のトランザクションを並列に処理するトランザクション処理システムにおける並行制御方法であって、各トランザクションが前記階層型データへのアクセスを開始するにあたって、前記階層型データのコピーを作成するコピーステップと、第１のトランザクションが該第１のトランザクション用の階層型データのコピーに対して読み出し又は書き込みの一方のアクセスを行う場合に、該アクセスと、第２のトランザクションが該第２のトランザクション用の階層型データのコピーに対して行った読み出し又は書き込みの他方のアクセスとの間に衝突が発生するか否かを判定する判定ステップと、この判定ステップにおいて衝突が発生すると判定された場合に、衝突を回避するための処理を行う処理ステップと、前記第１のトランザクションが正常に終了する場合に、該第１のトランザクションが該第１のトランザクション用の階層型データのコピーに行った書き込みアクセスを、前記階層型データに反映させるとともに、前記第２のトランザクションが未だ終了していないときは、該書き込みアクセスを、該第２のトランザクション用の階層型データのコピーにも反映させる反映ステップとを有することを特徴とする。
【００２１】
また、本発明は、階層型データを対象として複数のトランザクションを並列に処理するトランザクション処理システムであって、各トランザクションが前記階層型データへのアクセスを開始するにあたって、前記階層型データのコピーを作成するコピー手段と、第１のトランザクションが該第１のトランザクション用の階層型データのコピーに対して読み出し又は書き込みの一方のアクセスを行う場合に、該アクセスと、第２のトランザクションが該第２のトランザクション用の階層型データのコピーに対して行った読み出し又は書き込みの他方のアクセスとの間に衝突が発生するか否かを判定する判定手段と、この判定手段において衝突が発生すると判定された場合に、衝突を回避するための処理を行う処理手段と、前記第１のトランザクションが正常に終了する場合に、該第１のトランザクションが該第１のトランザクション用の階層型データのコピーに行った書き込みアクセスを、前記階層型データに反映させるとともに、前記第２のトランザクションが未だ終了していないときは、該書き込みアクセスを、該第２のトランザクション用の階層型データのコピーにも反映させる反映手段とを備えたことを特徴とする。
【００２２】
また、本発明は、階層型データを対象として複数のトランザクションを並列に処理するトランザクション処理システムとしてコンピュータを機能させるためのプログラムであって、各トランザクションが前記階層型データへのアクセスを開始するにあたって、前記階層型データのコピーを作成するコピー機能と、第１のトランザクションが該第１のトランザクション用の階層型データのコピーに対して読み出し又は書き込みの一方のアクセスを行う場合に、該アクセスと、第２のトランザクションが該第２のトランザクション用の階層型データのコピーに対して行った読み出し又は書き込みの他方のアクセスとの間に衝突が発生するか否かを判定する判定機能と、この判定機能において衝突が発生すると判定された場合に、衝突を回避するための処理を行う処理機能と、前記第１のトランザクションが正常に終了する場合に、該第１のトランザクションが該第１のトランザクション用の階層型データのコピーに行った書き込みアクセスを、前記階層型データに反映させるとともに、前記第２のトランザクションが未だ終了していないときは、該書き込みアクセスを、該第２のトランザクション用の階層型データのコピーにも反映させる反映機能とをコンピュータに実現させるためのプログラムである。
【００２３】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００２４】
本発明によれば、例えばＸＭＬのような階層型データを複数のトランザクションが並行してアクセスする場合にも、トランザクションの分離性を保証することができる、あるいは、その実行が直列化可能であるように処理の順序を制御することができるようになる。
【００２５】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００２６】
図１に、本発明の一実施形態に係るトランザクション処理システムの構成例を示す。図中、１はトランザクション管理部、１１はトランザクションマネージャ、１２はリソースマネージャ、１１１はトランザクション管理表、３はハードディスク、３１はファイル、５はアプリケーションプログラムをそれぞれ示している。
【００２７】
なお、トランザクション処理システムがハードディスク３を備えてもよいし、他のサーバ等がハードディスク３を備え、トランザクション処理システムが他のサーバ等を介してハードディスク３にアクセス可能であってもよい。また、アプリケーションプログラム５はトランザクション処理システム上で実行するものであってもよいし、アプリケーションプログラム５は他の計算機上で実行されるもので、他の計算機をクライアント、トランザクション処理システムをサーバとする、クライアント・サーバ・システムであってもよい。
【００２８】
図１のハードディスク３には、トランザクションのアクセスの対象となるデータのファイル３１が記録されている。ここでは、階層型データモデルの一例であるＸＭＬ形式のドキュメントとしてデータが記録されているファイルを対象とするトランザクション処理システムを例にとって説明する。ＸＭＬに関しては、“Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＸＭＬ）  １．０”  （Ｗ３Ｃ  Ｒｅｃｏｍｍｅｎｄａｔａｉｏｎ  １０−Ｆｅｂ−１９９８）に開示されている。
【００２９】
ハードディスク３に記録するファイル３１のドキュメント形式は、テキスト形式であってもツリー形式であっても構わない。図２は、テキスト形式のＸＭＬドキュメントの例を示している。実際のＸＭＬドキュメントには＜？ｘｍｌ＞で始まるプロローグ部があるが、ここでは省略する。図３は、図２と同じデータをツリー形式で表現しているドキュメントの例である。
【００３０】
図２のテキスト形式のドキュメントは、＜ｆｌｏｗｅｒｓ＞と＜／ｆｌｏｗｅｒｓ＞のタグで囲まれている。テキスト形式のドキュメントを囲む一番外側のタグは、ツリー形式のドキュメントにおけるツリーの根に相当する。例えば、図３のツリー形式のドキュメントでは、ｆｌｏｗｅｒｓという名前のノードがツリーの根となっている。
【００３１】
データの階層関係は、テキスト形式のドキュメントではタグの入れ子関係によって、ツリー形式のドキュメントではノードの親子関係によって表現される。例えば、図２の＜ｆｌｏｗｅｒｓ＞と＜／ｆｌｏｗｅｒｓ＞のタグの内側には＜ｆｌｏｗｅｒ＞と＜／ｆｌｏｗｅｒ＞の入れ子タグが３つあり、図３のツリーの根ノードの下には名前がｆｌｏｗｅｒである子ノードが３つある。図２のドキュメントのｆｌｏｗｅｒタグの内側にはさらにｎａｍｅ、ｃｏｌｏｒ、ｐｒｉｃｅの３つのタグがあり、例えば、１つ目のｆｌｏｗｅｒタグの内側のｎａｍｅタグで囲まれたデータは“Ｔｕｌｉｐ”となっている。これに対して、図３のドキュメントでは、１つ目のｆｌｏｗｅｒノードの子であるｎａｍｅノードのさらに子であるツリーの葉ノードの名前が“Ｔｕｌｉｐ”となっていてデータの値を表している。
【００３２】
以下では、各ファイルはツリー形式のドキュメントとして記録されている場合を例にとって説明するが、各ファイルがテキスト形式で記録されている場合でも例えばツリー構造への変換を加えることなどによって同様に実施できる。
【００３３】
図１のアプリケーションプログラム５は、ハードディスク３に記録されているファイル３１にアクセスしてデータの操作（読出しあるいは書込み）を行う。そのために、トランザクションを発行し、トランザクション管理部１を介してトランザクションの処理を行う。
【００３４】
本実施形態の並列制御方式が扱う問題は、同じファイルにアクセスする複数のトランザクションの並行処理を、分離性を維持しながら行う問題である。以降の本実施形態の並行制御方式の説明では、トランザクションはその実行過程で１つのファイルのみにアクセスする場合を中心に説明する。通常のトランザクションは複数のファイルにアクセスしてデータの操作することもできるが、トランザクションのアクセスの対象となる個々のファイルごとにその処理を分けて考えることで、１つのトランザクションが複数のファイルにアクセスする場合も同様に実施することができる。
【００３５】
トランザクションのアクセスには、データの参照を行うための読出しアクセスとデータの更新（例えば、挿入、削除、値の変更）を行うための書込みアクセスとがある。本実施形態におけるトランザクションは、１つのファイルに対して行う１つ又は複数の読出しアクセス及び又は書込みアクセスのアクセス系列からなる。
【００３６】
まず、トランザクションの読出しアクセスは、ＲＥＡＤ（ｐａｔｈ）という操作を行う。一般に階層型データモデルでは、パス形式の述語を用いることによって参照するデータ（ツリー形式においてはデータに対応するノード）を指定できる。例えば、ＸＭＬドキュメント上のある部分のデータあるいはデータの集合を指定するためには、ＸＰａｔｈというパス形式の言語がよく用いられる。ＸＰａｔｈに関しては、“ＸＭＬ  Ｐａｔｈ  Ｌａｎｇｕａｇｅ  （ＸＰａｔｈ）  １．０”  （Ｗ３Ｃ  Ｒｅｃｏｍｍｅｎｄａｔａｉｏｎ  １６−Ｎｏｖ−１９９９）に開示されている。ＲＥＡＤ（ｐａｔｈ）におけるｐａｔｈは、例えば、ＸＰａｔｈのようなパス形式の述語である。ＲＥＡＤ（ｐａｔｈ）は、ｐａｔｈによって指定されたドキュメント上のノードあるいはノードの集合を返す操作である。
【００３７】
トランザクションは、ＲＥＡＤ（ｐａｔｈ）の結果として返されるノードから参照したいデータの値を読み出すこととなる。例えば、ｐａｔｈ＝“ｆｌｏｗｅｒ［ｎａｍｅ＝Ｔｕｌｉｐ］／ｃｏｌｏｒ”は、ＸＰａｔｈ言語を用いた一例であり、［ｎａｍｅ＝Ｔｕｌｉｐ］の条件を満たすｆｌｏｗｅｒの子ノードｃｏｌｏｒを指定する述語である。トランザクションが図３のドキュメントに対する読出しアクセスとしてＲＥＡＤ（“ｆｌｏｗｅｒ［ｎａｍｅ＝Ｔｕｌｉｐ］／ｃｏｌｏｒ”）の操作を行うと、その結果として図３のノードｎ５が返される。トランザクションは、ノードｎ５の値（ツリーにおいては子ノードの名前）から“Ｙｅｌｌｏｗ”を読み出すことができる。もう１つの例として、トランザクションが図３のドキュメントに対してＲＥＡＤ（“ｆｌｏｗｅｒ［ｐｒｉｃｅ＜４００］／ｎａｍｅ”）を行うと、この場合は、ノードの集合｛ノードｎ４，ノードｎ１０｝が返される。トランザクションは、それぞれのノードの値からデータ“Ｔｕｌｉｐ”と“Ｌｉｌａｃ”を読み出すことができる。
【００３８】
トランザクションの書込みアクセスでは、ここでは、ＩＮＳＥＲＴ、ＤＥＬＥＴＥ、ＲＥＰＬＡＣＥの３種類の操作を行うことができるものとする。なお、ここでは、トランザクションの書込みアクセスの操作として上記の３つのみを挙げたが、ドキュメントのノードに対して更新を行う他の操作も可能であり、その場合でも本実施形態の並列制御方式を同様に実施することができる。
【００３９】
以下、ＩＮＳＥＲＴ操作、ＤＥＬＥＴＥ操作、ＲＥＰＬＡＣＥ操作についてそれぞれ説明する。
【００４０】
ＩＮＳＥＲＴ（ｎｏｄｅ，ｄａｔａ）は、ｎｏｄｅで指定したノードの値に、ｄａｔａで指定した値を挿入する操作である。例えば、図４のドキュメントに対する書込みアクセスとしてＩＮＳＥＲＴ（ノードｎ５，“Ｙｅｌｌｏｗ”）の操作を行うと、その更新結果を反映したドキュメントは図３のようになる。
【００４１】
ＩＮＳＥＲＴ（ｎｏｄｅ，ｃｈｉｌｄ−ｎｏｄｅ）は、ｎｏｄｅで指定したノードの子ノードとして、ｃｈｉｌｄ−ｎｏｄｅで指定したノードを挿入する操作である。この操作の他にも、例えば、何番目の子ノードとして挿入するかを指定する操作、兄弟ノードとしてｎｏｄｅで指定したノードの前に挿入する操作、兄弟ノードとしてｎｏｄｅで指定したノードの後に挿入する操作など、さまざまなＩＮＳＥＲＴ操作を考えてもよい。
【００４２】
ＤＥＬＥＴＥ（ｎｏｄｅ）は、ｎｏｄｅで指定したノードを削除する操作である。例えば、図３のドキュメントに対する書込みアクセスとしてＤＥＬＥＴＥ（ノードｎ１３）の操作を行うと、その更新結果を反映したドキュメントは図４のようになる。
【００４３】
ＲＥＰＬＡＣＥ（ｎｏｄｅ，ｄａｔａ）は、ｎｏｄｅで指定したノードの値をｄａｔａで指定した値に変更する操作である。例えば、図３のドキュメントに対する書込みアクセスとしてＲＥＰＬＡＣＥ（ノードｎ５，“Ｒｅｄ”）の操作を行うと、その更新結果を反映したドキュメントは図５のようになる。
【００４４】
これらＩＮＳＥＲＴ、ＤＥＬＥＴＥ、ＲＥＰＬＡＣＥとは異なる操作を考慮する場合でも同様に実施することが可能である。例えば、ＸＭＬドキュメントのノードには属性を与えることができる。この場合には、書込みアクセスとして、ＩＮＳＥＲＴ（ｎｏｄｅ，ａｔｔｒ，ｖａｌｕｅ）といったｎｏｄｅで指定したノードのａｔｔｒという名前の属性にｖａｌｕｅで指定した値を挿入する操作を加えてもよい。
【００４５】
ところで、トランザクションがデータの更新を行うときは、読出しアクセスによって更新したいデータを指定した後に、そのデータに対して書込みアクセスの操作を行う必要がある。すなわち、書込みアクセスは、読出しアクセスの後に、その読出しアクセスの結果として返されるノードあるいはノードの集合に対して行われる。例えば、トランザクションが図３のドキュメントでＴｕｌｉｐのｃｏｌｏｒの値を“Ｒｅｄ”に更新する場合には、まず、読出しアクセスのＲＥＡＤ（“ｆｌｏｗｅｒ［ｎａｍｅ＝Ｔｕｌｉｐ］／ｃｏｌｏｒ”）を行った後に、その結果として返されるノードｎ５に対して、書込みアクセスのＲＥＰＬＡＣＥ（ノードｎ５，“Ｒｅｄ”）を行う。
【００４６】
なお、ここでは１つのノードに対して書込みアクセスの操作を行う場合の例を説明したが、ノードの集合を対象とする場合も個々のノードに対する更新を行うことで同様に実施できる。
【００４７】
図１のトランザクション管理部１は、各アプリケーションプログラム５が実行するトランザクションの処理を行う。トランザクション管理部１は、トランザクションマネージャ１１とリソースマネージャ１２とを含んでいる。トランザクションマネージャ１１は、アプリケーションプログラム５から発行されるすべてのトランザクションの管理を行う。他方、リソースマネージャ１２は、データベース上のファイル３１の管理と、そのファイル３１に対して各トランザクションが行うアクセスの処理を行う。
【００４８】
図１では、トランザクション管理部１が複数のリソースマネージャ１２を含んでいる場合を例にとって示している。ここでは、各リソースマネージャ１２は、データベース上の個々のファイル３１を担当しており、担当するファイル３１に対するトランザクションのアクセスを処理するものとしている。もちろん、これに限定されるものではなく、他の構成をとっても構わない。例えば、１つのリソースマネージャ１２がすべてのファイル３１へのトランザクションのアクセスを処理するようにして、１つのトランザクションマネージャ１１と１つのリソースマネージャ１２を含むトランザクション管理部１として実施することもできるし、少なくとも１つのリソースマネージャ１２が複数のファイル３１へのトランザクションのアクセスを処理するようにして、１つのトランザクションマネージャ１１と複数（図１よりは少ない数）のリソースマネージャ１２を含むトランザクション管理部１として実施することもできる。
【００４９】
図１のトランザクションマネージャ１１は、アプリケーションプログラム５が発行するすべてのトランザクションを管理する。また、アプリケーションプログラム５が発行した個々のトランザクションを、そのトランザクションがアクセスするファイル３１を管理しているリソースマネージャ１２に対応付ける。そして、各トランザクションのアクセスの処理を、対応するリソースマネージャ１２に指示する。トランザクションマネージャ１１は、新しいファイル３１の作成および消去に応じて、リソースマネージャ１２の作成および削除を行う。
【００５０】
図１のトランザクション管理表１１１は、どのトランザクションがどのリソースマネージャ１２に対応しているかを管理する。トランザクション管理表１１１には、トランザクションのトランザクション識別子と、そのトランザクションがアクセスするファイル３１を管理しているリソースマネージャ１２の識別子との対応を示す情報が記録されている。例えば、図６のトランザクション管理表の例では、トランザクション識別子Ｔ１，Ｔ３，Ｔ５の３つのトランザクションが、リソースマネージャＲ１が管理しているファイル３１にアクセスしていることを示している。
【００５１】
以降では、各トランザクションは１つのファイル３１に対してアクセスを行い、そのファイル３１を管理している１つのリソースマネージャ１２に対応している場合を例としての処理手順を説明する。本実施形態の並行制御方式は、各ファイル３１に対するトランザクションのアクセスを処理する個々のリソースマネージャによって実施されるので、各トランザクションが複数のリソースマネージャに対応する場合においても同様に実施できる。
【００５２】
以下では、トランザクションマネージャ１１が行う処理手順について、（１）トランザクションが発行されたときの処理手順、（２）トランザクションが読出しアクセスあるいは書込みアクセスを要求したとき処理手順、（３）トランザクションの処理を終了するときの処理手順の順番に説明する。
【００５３】
（１）トランザクションが発行されたときの処理手順
アプリケーションプログラム５が新しいトランザクションの発行と、そのトランザクションがアクセスするファイル３１とを、トランザクションマネージャ１１に知らせると、トランザクションマネージャ１１は、まず、新しいトランザクションにトランザクション識別子を割り付ける。また、そのトランザクションがアクセスするファイル３１を管理しているリソースマネージャ１２を調べ、トランザクション識別子と対応するリソースマネージャ１２識別子の情報をトランザクション管理表１１１に記録する。次に、対応するリソースマネージャ１２に対して、新しいトランザクションの処理開始を指示する。
【００５４】
（２）トランザクションがアクセスを要求したときの処理手順
アプリケーションプログラム５がトランザクションの実行を進めていく過程で読出しアクセスあるいは書込みアクセスを要求すると、トランザクションマネージャ１１は、対応するリソースマネージャ１２に、トランザクション識別子とそのトランザクションのアクセス要求とを知らせる。
【００５５】
（３）トランザクションの処理を終了するときの処理手順
アプリケーションプログラム５がトランザクションの処理を終了すると知らせると、トランザクションマネージャ１１は、トランザクション識別子からそのトランザクションを処理しているリソースマネージャ１２を調べて、対応するリソースマネージャ１２に、トランザクションが行ったデータの更新結果をハードディスク３上のファイル３１に書き込んでコミットするか、または更新結果を破棄してアボートするかを決定し、指示する。なお、コミットするかアボートするかの決定方法は、従来通りで構わない。また、トランザクション管理表１１１から、そのトランザクション識別子のエントリを削除する。
【００５６】
図１のリソースマネージャ１２は、対応するハードディスク３上のファイル３１を管理し、トランザクションマネージャ１１から指示されたときにトランザクションのアクセスを処理する。トランザクションのアクセスを処理する際には、本実施形態の並行制御方式を実施し、トランザクションの分離性を維持するように処理する。
【００５７】
本実施形態の並行制御方式では、あるトランザクションが読出しアクセスあるいは書込みアクセスを要求したときに、そのアクセスが、そのトランザクションと並行に処理中の他のトランザクションが行った読出しアクセスあるいは書込みアクセスと同じファイルの同じ部分のデータに対して行われることで、トランザクションの分離性を破らないかを検査する。
【００５８】
ここで、２つのアクセスが同じファイルの同じ部分のデータにアクセスすることを、２つのアクセスは衝突するという。
【００５９】
読出しアクセスと読出しアクセスとの間の衝突では、同時に同じ部分のデータを読み出しても分離性を破らないので、この検査の必要はない。
【００６０】
他方、読出しアクセスと書込みアクセスとの間の衝突では、同時に同じ部分のデータの読出しと書き込みを行うと分離性を破ってしまうので、この検査を行う必要がある。
【００６１】
同様に、書込みアクセスと書込みアクセスとの衝突も分離性を破る。ただし、あるデータに対する書込みアクセスを行う前にはかならずそのデータに対する読出しアクセスが行われるので、分離性を破る書込みアクセスと書込みアクセスとの衝突は、読出しアクセスと書き込みアクセスとの衝突を検査することで発見できることになり、結局、この検査を行う必要はないことになる。
【００６２】
アクセス衝突の検査の結果、あるトランザクションＴ１が要求したアクセスが、他のトランザクションＴ２がすでに行ったアクセスと衝突を起こして分離性を破る場合は、いずれか一方のトランザクションの処理が終了するまで、他方のトランザクションの処理を中断しなければならない。その際は、いずれのトランザクションの処理を優先するかによって、いずれのトランザクションを中断すべきか決めればよい。例えば、先のトランザクションＴ２を優先し、後からのトランザクションＴ１を中断して、トランザクションＴ２が終了した後にトランザクションＴ１を再開する方法や、予めトランザクションごとに優先度を付与しておいて、衝突を起こしたトランザクションの優先度を比較することによって、いずれのトランザクションの処理を優先するかを決定するようにしてもよいし、その他にも、種々の方法が可能である。
【００６３】
本実施形態では、個々のリソースマネージャが管理しているファイルに対するトランザクションのアクセスを処理する際に、アクセス衝突の検査を行う。本実形態で用いるアクセス衝突の検査方法については後で詳しく説明する。
【００６４】
以下、本実施形態の並行制御を実施するリソースマネージャとして２つの構成例を示す。
【００６５】
（リソースマネージャの第１の構成例）
まず、リソースマネージャの第１の構成例について説明する。
【００６６】
図７に、第１の構成例に係るリソースマネージャの構成例を示す。図中、１２はリソースマネージャ、１２１はドキュメントＤ−ａｌｌ、１２２はトランザクション待ちグラフ、１２３はトランザクションリスト、１２４はトランザクションアクセス系列、１２５はドキュメントＤ（Ｔｉｄ）を、３はハードディスクを、３１はドキュメントＤ−ｓｔ（図１のファイル３１）をそれぞれ示している。
【００６７】
リソースマネージャ１２は、１つのファイルを管理し、そのファイルに対する複数のトランザクションのアクセスを処理する。図７のドキュメントＤ−ｓｔは、リソースマネージャ１２が管理するハードディスク３上のファイル（図１の３１）を指す。以降で説明するドキュメントは、すべてファイルＤ−ｓｔと同じツリー形式のドキュメントである。
【００６８】
図７のドキュメントＤ−ａｌｌ（図中の１２１）は、リソースマネージャ１２が管理するファイル３１に対して、処理中のすべてのトランザクションが現在までに行ったデータの更新結果を反映させた場合の内容を保持させるドキュメントである。リソースマネージャ１２は、初期状態でドキュメントＤ−ｓｔをコピーしてドキュメントＤ−ａｌｌを作成する。以降、リソースマネージャ１２は、処理中のトランザクションが要求する書込みアクセスが分離性を破らないと判断すれば、その書込みアクセスによるデータの更新をドキュメントＤ−ａｌｌに重ねて反映させていく。
【００６９】
図７のトランザクションリスト１２３には、リソースマネージャ１２が処理しているトランザクションのトランザクション識別子のリストが記録管理されている。例えば、図８のトランザクションリストの例では、図６の例における識別子Ｒ１のリソースマネージャ１２が、トランザクション識別子Ｔ１，Ｔ３，Ｔ５の３つのトランザクションの処理を並行に行っていることを示している。リソースマネージャ１２は、処理中の個々のトランザクション識別子Ｔｉｄのトランザクションに対して、トランザクションアクセス系列ＡＳ（Ｔｉｄ）（図中の１２４）とドキュメントＤ（Ｔｉｄ）（図中の１２５）を管理する。
【００７０】
図７のトランザクション待ちグラフ１２２は、リソースマネージャ１２が処理を中断して待機させているトランザクションのトランザクション識別子の情報を記録管理する待ちグラフである。待ちグラフの各点はトランザクションを表し、各辺はトランザクションの実行順序の依存関係を表す。
【００７１】
図９は、トランザクション待ちグラフの例を示している。例えば、図９の辺（Ｔ３→Ｔ１）は、トランザクションＴ３の処理が終了するまでトランザクションＴ１が処理を中断して待機していることを表す。もしトランザクションＴ１のアクセスがトランザクションＴ３のアクセスと衝突するときは、トランザクションＴ３の処理が終了するまでトランザクションＴ１を待機させなければならないので、リソースマネージャ１２は、トランザクション待ちグラフ１２２に辺（Ｔ３→Ｔ１）を追加する。そして、トランザクションＴ３の処理を終了するときに、Ｔ３が始点である辺を削除し、その辺の終点のトランザクションの処理を再開する。
【００７２】
トランザクション待ちグラフ１２２は、デッドロックを解決するためにも広く用いられる。待ちグラフの中にループがあるとデッドロックの状態であることがわかる。
【００７３】
本実施形態では、トランザクションの待ち情報を記録管理するために待ちグラフを使用するが、他の方法を使用して実施することも可能である。
【００７４】
図７のトランザクションアクセス系列ＡＳ（Ｔｉｄ）（図中の１２４）は、個々のトランザクションＴｉｄについて、それが処理の開始から行ってきた読出しアクセスおよび書込みアクセスの系列を、リストとして記録管理している。トランザクションアクセス系列１２４には、各アクセスについて順番に、当該アクセスのアクセス番号と、当該アクセスが読出しアクセス、書込みアクセスのいずれであるかを示す情報と、当該アクセスの操作を示す情報とが記録されている。ＡＳ（Ｔｉｄ）は、トランザクション識別子Ｔｉｄのトランザクションのトランザクションアクセス系列を指す。
【００７５】
図１０は、トランザクションアクセス系列の一例を示している。図１０におけるｒは読出しアクセスであることを、ｗは書込みアクセスであることをそれぞれ表す。図１０の例のトランザクションアクセス系列を持つトランザクションは、最初にアクセス番号１の読出しアクセスＲＥＡＤ（“ｆｌｏｗｅｒ／ｎａｍｅ”）を行い、次にアクセス番号２の読出しアクセスＲＥＡＤ（“ｆｌｏｗｅｒ［ｎａｍｅ＝Ｔｕｌｉｐ］／ｃｏｌｏｒ”）を行い、最後にアクセス番号３の書込みアクセスＲＥＰＬＡＣＥ（ｎｏｄｅ２，“Ｒｅｄ”）を行っている。ここでｎｏｄｅ２はアクセス番号２の読出しアクセスの結果として返されたノードを指す。書込みアクセスを行うときの操作対象のノードとしては、以前に行った読出しアクセスの結果のノードおよびノードの集合、あるいはその一部のノードなどを指定することができる。
【００７６】
図７のドキュメントＤ（Ｔｉｄ）（図中の１２５）は、トランザクション識別子Ｔｉｄのトランザクションが行った書込みアクセスによるデータの更新結果を反映しているドキュメントである。なお、以降の説明では、トランザクション識別子Ｔｉｄを省略して、（当該トランザクションに対応する）ドキュメントＤと呼ぶこともある。ドキュメントＤ−ａｌｌがリソースマネージャ１２の処理するすべてのトランザクションにより行われたデータの更新を反映しているのに対して、このドキュメントＤは対応する１つのトランザクションが行ったデータの更新を反映している。
【００７７】
リソースマネージャ１２は、トランザクションの処理を開始するときに、管理するファイル、すなわち、ドキュメントＤ−ｓｔをコピーして新しいトランザクション用のドキュメントＤを作成する。以降、そのトランザクションが読出しアクセスあるいは書込みアクセスを要求したときには、そのアクセスが分離性を破らないと判断すれば、ハードディスク３上のドキュメントＤ−ｓｔの代わりにドキュメントＤにアクセスしてデータの参照あるいは更新を行う。そして、そのトランザクションをコミットして終了するときに、そのトランザクションに対応するドキュメントＤに対して行った更新を、ドキュメントＤ−ｓｔにマージすることによって、コミットするデータの更新結果をハードディスク３上のファイル３１に反映する。他方、トランザクションをアボートして終了するときには、そのトランザクションによる更新結果を破棄するので、ドキュメントＤを削除すればよい。
【００７８】
リソースマネージャ１２は、トランザクションからアクセスを要求されたとき、そのアクセスが分離性を破らないかを判断しなければならない。トランザクションが読出しアクセスを要求したときは、並行して処理中の他のトランザクションがすでに書込みアクセスを行ったデータと同じ部分にアクセスして衝突を起こさないかを検査する。また、トランザクションが書込みアクセスを要求したときは、並行して処理中の他のトランザクションがすでに読出しアクセスを行ったデータと同じ部分にアクセスして衝突を起こさないかを検査する。以降、読出しアクセスがすでに行われた書込みアクセスと衝突することを「ＲＷアクセス衝突」、書込みアクセスがすでに行われた読出しアクセスと衝突することを「ＷＲアクセス衝突」とそれぞれ呼ぶものとする。
【００７９】
（ＲＷアクセス衝突の検査）
まず、ＲＷアクセス衝突の検査について説明する。
【００８０】
ＲＷアクセス衝突は、あるトランザクションＴ１が要求する読出しアクセスが、並行して処理中の他のトランザクションがすでに行った書込みアクセスに対して衝突を起こすことである。
【００８１】
従来の述語ロックやプレシジョンロックでは、述語と述語の比較や述語とデータの比較によって、この衝突を検出する。しかし、トランザクションＴ１の読出しアクセスＲＥＡＤ（ｐａｔｈ）におけるＸＰａｔｈ式のｐａｔｈを、他のトランザクションがすでに更新したデータが充足するか否かを判定するのは、非常に難しい問題である。
【００８２】
本実施形態の並行制御方式では、データとデータとの比較のみによってアクセス衝突の検査を効率よく実現する。
【００８３】
まず、あるトランザクションＴ１が要求する読出しアクセスが、他のトランザクションＴ２がすでに行った書込みアクセスに対してＲＷアクセス衝突を起こす場合を考える。この場合、トランザクションＴ１の要求する読出しアクセスが、トランザクションＴ２がすでに更新したデータと同じ部分のデータを参照するので、アクセス衝突が起きる。
【００８４】
トランザクションＴ１が読出しアクセスを行うときには、ドキュメントＤ（Ｔ１）に対して読出し操作ＲＥＡＤ（ｐａｔｈ）が行われ、ｐａｔｈによって特定されるドキュメントＤ（Ｔ１）上のノードの集合が、読出しアクセスの結果として返される。ＸＰａｔｈ式を評価して結果のノード集合を特定するためには、ツリー構造であるドキュメントＤ（Ｔ１）上の経路を、ｐａｔｈの記述に従ってたどりながら、該当するノードを探索する必要があり、探索経路の最後のステップにおいて結果のノード集合が得られる。したがって、読出しアクセスは、結果のノード集合に至る経路上のすべてのノードを参照することとなる。トランザクションＴ１の読出しアクセスが参照するこれらのノードの集合をＮ１とする。
【００８５】
トランザクションＴ２がすでに行った書込みアクセスの更新結果は、ドキュメントＤ（Ｔ２）に反映されている。ドキュメントＤ（Ｔ１）にトランザクションＴ２がすでに行った更新結果を反映したドキュメントは、ドキュメントＤ（Ｔ１）とＤ（Ｔ２）とをマージして得られる。ここで、２つのドキュメントＤ（Ｔ１）とＤ（Ｔ２）をマージするということは、トランザクションＴ１とＴ２がそれぞれ行った更新結果の両方がマージしたドキュメントに反映されているということを意味する。マージしたドキュメントに対して同様に読出しアクセスＲＥＡＤ（ｐａｔｈ）を行ったときに参照するノードの集合をＮ２とする。
【００８６】
ＲＷアクセス衝突が起きるとき、マージしたドキュメントにおけるドキュメントＤ（Ｔ１）上のノード集合Ｎ１と同じ部分のデータがトランザクションＴ２によって更新されているので、ノード集合Ｎ１とノード集合Ｎ２とは異なることになる。ここで、異なるドキュメントＤ（Ｔ１）上のノードとＤ（Ｔ２）上のノードとが等価であるということは、そのノードがドキュメントＤ−ｓｔの同じノードからコピーされていることを意味する。例えば、トランザクションＴ２が削除したデータと同じ部分のデータをトランザクションＴ１のＲＥＡＤ（ｐａｔｈ）が参照する場合、参照されるノード集合Ｎ１にあるノードがノード集合Ｎ２の中には存在しない。ノード集合Ｎ１とノード集合Ｎ２とが同じであるとは、そのすべての要素がお互いに等価なノードであるということを意味し、ノード集合Ｎ１とノード集合Ｎ２とは等価であるということとする。
【００８７】
ＲＷアクセス衝突の検査は、ドキュメントＤ（Ｔ１）に対してＲＥＡＤ（ｐａｔｈ）がｐａｔｈの評価時に参照するノード集合と、ドキュメントＤ（Ｔ１）とドキュメントＤ（Ｔ２）とをマージしたドキュメントに対してＲＥＡＤ（ｐａｔｈ）がｐａｔｈの評価時に参照するノード集合とが等価であるか否かの検査に等しい。
【００８８】
次に、異なる２つのドキュメントに対して読出しアクセスＲＥＡＤ（ｐａｔｈ）がｐａｔｈの評価時に参照するノード集合の等価性検査について詳しく説明する。
【００８９】
例えば、図３のドキュメントに対してＲＥＡＤ（“ｆｌｏｗｅｒ／ｃｏｌｏｒ”）を行うとき、まず、名前が“ｆｌｏｗｅｒ”である子ノード｛ノードｎ１，ノードｎ２，ノードｎ３｝（＝ノード集合Ｒ１とする）が探索され、次に、それらのノードを出発点（ＸＰａｔｈの仕様では「コンテキストノード」と呼ばれる）として子ノードで名前が“ｃｏｌｏｒ”である｛ノードｎ５，ノードｎ８，ノードｎ１１｝（＝ノード集合Ｒ２とする）が探索される。この場合、ノード集合Ｒ１→ノード集合Ｒ２の経路をたどって、結果のノード集合Ｒ２が特定されるので、ｐａｔｈの評価においてノード集合Ｒ１とノード集合Ｒ２との両方が参照される。したがって、異なるドキュメントに対して読出しアクセスが参照するノード集合が等価であるかを検査するためには、ｐａｔｈの探索経路上の各ステップにおいて参照されるそれぞれのドキュメント上のノード集合を比較して等価であるか検査すればよい。
【００９０】
ＲＷアクセス衝突検査において２つのドキュメントに対して読出しアクセスの参照するノード集合が等価であるということは、読出しアクセスがｐａｔｈの評価時に参照するすべてのノード集合、言い換えれば、ｐａｔｈの探索経路上のすべてのステップで参照されるノード集合が等価であるということである。
【００９１】
ところで、すべてのステップでのノード集合を比較せずに、ＲＷアクセス衝突検査を効率的に行うように実施することもできる。以下、その方法について説明する。
【００９２】
各ドキュメントにおいて、ツリー上で親ノードが書込みアクセスで更新されていれば、その子ノードも更新されていることになる。ドキュメントに対する書込みアクセスの操作には、大きく３つの操作、すなわち、ＩＮＳＥＲＴ（挿入）、ＤＥＬＥＴＥ（削除）、ＲＥＰＬＡＣＥ（値の変更）の操作がある。例えば、トランザクションＴ２がドキュメントＤ（Ｔ２）に対して挿入の書込み操作を行ったとすると、ドキュメントＤ（Ｔ２）のドキュメントツリーにおいて挿入されたノードを根とする部分木にあるすべてのノードも、トランザクションＴ２によって新たに挿入されたノードである。また、トランザクションＴ２が削除の操作を行ったとすると、削除されたノードおよびそのノードを根とする部分木は、ドキュメントＤ（Ｔ２）のドキュメントツリー上には存在しない。また、データの値はドキュメントツリーの葉ノード（リーフノード）に格納されているので、値を更新するＲＥＰＬＡＣＥ操作は、葉ノードに対してのみ行われる（もしツリーの葉ではないノードの名前を更新するといったＲＥＰＬＡＣＥ操作を考える場合でも、そのノードを根とする部分木も変更されるものと仮定することで同様に考えることができる）。
【００９３】
このように、１つのドキュメントツリー上で親ノードが書込みアクセスで更新されていればその子ノードも更新されているので、ｐａｔｈの探索経路上のあるステップで参照したノード集合が異なければ、次のステップでそれらのノード集合を出発点としてその部分木をたどって探索したノード集合も異なる。
【００９４】
このことから、各ステップがツリーにおいて下向きの探索を続けるかぎり、途中のステップでは、参照したノード集合の比較をして等価性を検査する必要はない。
【００９５】
ただし、ＸＰａｔｈには、指定した条件を満たす子ノードや子孫ノードなどを探す下向きの探索の他に、親ノード、兄弟ノードなどを探す異なる方向の探索がある。そのように探索の方向が変わる前のステップでは、参照したノード集合の比較を行い等価であるかどうかを検査すればよい。例えば、図３のドキュメントに対してＲＥＡＤ（“ｆｌｏｗｅｒ［ｎａｍｅ＝Ｔｕｌｉｐ］／ｃｏｌｏｒ”）を行うとき、結果に至る探索経路は｛ノードｎ４｝（＝ノード集合Ｒ１１）→｛ノードｎ１｝（＝ノード集合Ｒ１２）→｛ノードｎ５｝（＝ノード集合Ｒ１３）であり、ノード集合Ｒ１１からノード集合Ｒ１２への探索は下向きではないので、ノード集合Ｒ１１におけるノードの比較は必要であるが、ノード集合Ｒ１２からノード集合Ｒ１３への探索は下向きであるので、ノード集合Ｒ１２におけるノードの比較は省略できる（ノード集合Ｒ１２での比較でノードが異なればノード集合Ｒ１３での比較でもノードは異なるので、ノード集合Ｒ１３の比較だけで十分である）。この場合は、ノード集合Ｒ１１とノード集合Ｒ１３を参照したステップでノード集合の等価性を検査すればよい。
【００９６】
ＸＰａｔｈ式の評価において探索の方向が変わることから、途中のステップで参照されるノード集合の等価性検査を行わなければならない場合は、大きく３つに分けられる。
【００９７】
１つ目は、１つのＸＰａｔｈ式の中に複数のパスが存在する場合である。この場合には、それぞれのパスを評価して得られたノード集合の等価性を検査する。例えば、ＸＰａｔｈの仕様には、＋、−などを含む様々な演算子や関数などがあり、ｐａｔｈ＝ｐａｔｈ１＋ｐａｔｈ２のような例でｐａｔｈの中に２つのパスｐａｔｈ１とｐａｔｈ２が存在する。したがって、ｐａｔｈ１で参照するノード集合とｐａｔｈ２で参照するノード集合とのそれぞれに対して等価性調査を行う。
【００９８】
２つ目は、前述したように、１つのパスの中でも下向きではない探索方向に変わる場合である。ＸＰａｔｈでは探索の方向について、軸（ａｘｉｓ）を指定することによって設定でき、例えば、コンテキストノードに対する親ノード（ｐａｒｅｎｔ）、子孫ノード（ａｎｃｅｓｔｏｒ）などを探索するように設定することができる。その他に下向きではない方向の探索の軸としては、前の兄弟ノード（ｐｒｅｃｅｄｉｎｇ−ｓｉｂｌｉｎｇ）、後の兄弟ノード（ｆｏｌｌｏｗｉｎｇ−ｓｉｂｌｉｎｇ）などがある。
【００９９】
３つ目は、ＸＰａｔｈが定めたノードの位置情報によって探索を行う場合である。例えば、ｐａｔｈ＝ｆｌｏｗｅｒ［ｐｏｓｉｔｉｏｎ（）＝２］の例のように、２番目のｆｌｏｗｅｒノードを探索する場合は、その位置に影響を及ぼす１番目のノードも参照の対象としてノード集合の等価性検査を行う。
【０１００】
以上のように、トランザクションＴ１の読出しアクセスがトランザクションＴ２の書込みアクセスに対して起こすＲＷアクセス衝突は、ドキュメントＤ（Ｔ１）と、ドキュメントＤ（Ｔ１）及びドキュメントＤ（Ｔ２）をマージしたドキュメントとに対してＲＥＡＤ（ｐａｔｈ）を行って参照されるそれぞれのノード集合が等価であるか否かを検査することによって検出する。
【０１０１】
さて、トランザクションの分離性を保証するためには、並列に処理中の他のすべてのトランザクションに対して、要求された読出しアクセスがＲＷアクセス衝突を起こさないかを検査する必要がある。例えば、トランザクションＴ１が読出しアクセスを要求したときは、トランザクションＴ１以外の処理中のすべてのトランザクションに対してＲＷアクセス衝突の検査を行えばよい。これには、トランザクションＴ１とそれ以外の並列に処理中の１つのトランザクションとのＲＷアクセス衝突の検査を、トランザクションＴ１以外の並列に処理中のすべてのトランザクションを対象として繰り返し行う方法や、ドキュメントＤ（Ｔ１）に対して読出しアクセスが参照するノード集合と、ドキュメントＤ（Ｔ１）及び他のトランザクション用のすべてのドキュメントＤをマージしたドキュメントとに対して読出しアクセスが参照するノード集合の等価性検査を行う方法がある。
【０１０２】
本実施形態では、ドキュメントＤ−ａｌｌを用いることによってＲＷアクセス衝突の検査をさらに効率よく処理できる。すなわち、すべてのトランザクションが行ったデータの更新結果は１つのドキュメントＤ−ａｌｌ上に反映されている。したがって、並列に処理中の他の各トランザクションごとのドキュメントＤを使用せずに、ドキュメントＤ（Ｔ１）に対して読出しアクセスが参照するノードの集合とドキュメントＤ−ａｌｌに対して読出しアクセスが参照するノードの集合とが等価であるかを調べる１回の操作だけで、必要なＲＷアクセス衝突の検査が実施できる。
【０１０３】
（ＷＲアクセス衝突の検査）
次に、ＷＲアクセス衝突の検査について説明する。
【０１０４】
ＷＲアクセス衝突の検査もＲＷアクセス衝突の検査と同様な考え方でノードの集合とノードの集合の比較によって行う。
【０１０５】
ＷＲアクセス衝突は、あるトランザクションＴ１が要求する書込みアクセスが、他のトランザクションＴ２がすでに行った読出しアクセスに対して衝突を起こすことである。この衝突は、トランザクションＴ２がすでに行ったある読出しアクセスで参照したデータと同じ部分のデータに対してトランザクションＴ１が書込みアクセスを要求する場合に起きる．トランザクションＴ１が要求した書込みアクセスの操作をＷとする。Ｗは、ＩＮＳＥＲＴ、ＤＥＬＥＴＥ、ＲＥＰＬＡＣＥのいずれかの操作である。
【０１０６】
まず、以前にトランザクションＴ２がある読出しアクセスＲＥＡＤ（ｐａｔｈ）を行った時点のドキュメントＤ（Ｔ２）の状態をＤ´（Ｔ２）として、ドキュメントＤ´（Ｔ２）に対してＲＥＡＤ（ｐａｔｈ）がｐａｔｈの評価時に参照したノードの集合をＮ１１とする。
【０１０７】
次に、書込みアクセスＷを含むトランザクションＴ１のこれまでの更新結果をドキュメントＤ´（Ｔ２）へ反映させたドキュメントをＤ´´（Ｔ２）として、ドキュメントＤ´´（Ｔ２）に対して同じ読出しアクセスＲＥＡＤ（ｐａｔｈ）を行ったときに参照するノードの集合をＮ１２とする。
【０１０８】
トランザクションＴ１が要求する書込みアクセスＷとトランザクションＴ２が以前に行った読出しアクセスＲＥＡＤ（ｐａｔｈ）が衝突してＷＲアクセス衝突が起きるとき，ドキュメントＤ´´（Ｔ２）においてトランザクションＴ２のＲＥＡＤ（ｐａｔｈ）で参照されるデータと同じ部分のデータがトランザクションＴ１のＷによって更新されているので、２つのドキュメントＤ´（Ｔ２）とＤ´´（Ｔ２）に対して読出しアクセスで参照したノードの集合Ｎ１１とＮ１２とは異なる。
【０１０９】
したがって、ＷＲアクセス衝突の検査は、ドキュメントＤ´（Ｔ２）に対するＲＥＡＤ（ｐａｔｈ）の参照するノード集合と、ドキュメントＤ´´（Ｔ２）に対するＲＥＡＤ（ｐａｔｈ）の参照するノード集合とが等価であるかの検査に等しい。
【０１１０】
トランザクションの分離性を保証するためには、並列して処理中の他のトランザクションがすでに行ったすべての読出しアクセスに対して、要求された書込みアクセスがＷＲアクセス衝突を起こさないかを検査する。例えば、トランザクションＴ１が書込みアクセスを要求したときは、トランザクションリスト１２３にあるトランザクションＴ１以外の各トランザクションＴ２が行ったすべての読出しアクセスに対してＷＲアクセス衝突の検査を行う。
【０１１１】
まず、各読出しアクセスが行われた時点のドキュメントＤ´´（Ｔ２）は、ドキュメントＤ−ｓｔに対してその読出しアクセスの前に行われたすべての書込みアクセスの更新結果を反映したドキュメントであるので、ドキュメントＤ−ｓｔに対してトランザクションＴ２のトランザクションアクセス系列の書込みアクセスを行う方法で再作成できる。各読出しアクセスのＲＥＡＤ（ｐａｔｈ）が参照したノード集合Ｎ１１は、再作成したドキュメントＤ´（Ｔ２）に対してＲＥＡＤ（ｐａｔｈ）が参照するノード集合を求めることによって得られる。
【０１１２】
なお、他の方法として、すべての読出しアクセスに対して参照したノード集合Ｎ１１を保存しておくようにしてもよい。
【０１１３】
次に、書込みアクセスＷの更新を反映したドキュメントＤ（Ｔ１）の状態をＤ´（Ｔ１）とすると、Ｗを含むトランザクションＴ１のこれまでの更新結果をドキュメントＤ´（Ｔ２）に反映したドキュメントＤ´´（Ｔ２）は、ドキュメントＤ´（Ｔ１）とＤ´（Ｔ２）をマージすることによって得られる。
【０１１４】
なお、他の方法として、ドキュメントＤ´（Ｔ１）に対してトランザクションＴ２のトランザクションアクセス系列の書込みアクセスを行うことによってドキュメントＤ´´（Ｔ２）を再作成するようにしてもよい。
【０１１５】
図７の第１の構成例のリソースマネージャ１２では、ＷＲアクセス衝突の検査のときに、ドキュメントＤ−ｓｔに対してトランザクションアクセス系列１２４をトレースしながら、すなわち、トランザクションのトランザクションアクセス系列１２４の読出しアクセスおよび書き込みアクセスを順番に実行させていきながら、すでに行われた読出しアクセス時のドキュメントＤの状態を再作成し、読出しアクセスのＲＥＡＤ（ｐａｔｈ）が参照するノード集合の等価性判定を行う。
【０１１６】
なお、他の方法として、トランザクションの書込みアクセスを行ってドキュメントＤを更新するときに、更新前のドキュメントＤの状態を記録しておくように実施することも可能である。この場合は、ドキュメントＤの再作成を行わなくてもよいが、ドキュメントＤの更新毎にその状態を記録すると使用する記録容量が大きくなるというトレードオフがある。後で説明する第２の構成例のリソースマネージャ１２では、ドキュメントＤの状態を記録するタイミングをスケジュールしながらＷＲアクセス衝突の検査を行う。
【０１１７】
以下では、本構成例のリソースマネージャ１２が行う処理手順について、（１）トランザクションの処理を開始するときの処理手順、（２）トランザクションが読出しアクセスを要求したときの処理手順、（３）トランザクションが書込みアクセスを要求したときの処理手順、（４）トランザクションを中断後に再開するときの処理手順、（５）トランザクションをコミットするときの処理手順、（６）トランザクションをアボートするときの処理手順の順番に説明する。
【０１１８】
（１）トランザクションの処理を開始するときの処理手順
図１１に、トランザクション識別子Ｔｉｄのトランザクションの処理を開始するときの処理手順例を示す。
【０１１９】
まず、トランザクション識別子Ｔｉｄをトランザクションリスト１２３に追加する（ステップＳ１）。また、新しいトランザクションのために、トランザクションアクセス系列ＡＳ（Ｔｉｄ）とドキュメントＤ（Ｔｉｄ）を作成する（ステップＳ２，Ｓ３）。
【０１２０】
なお、トランザクションアクセス系列の初期値は、空リストである。
【０１２１】
また、ドキュメントＤ（Ｔｉｄ）は、ドキュメントＤ−ｓｔをコピーして作成する。なお、コピーの際には、例えば、ドキュメントＤ（Ｔｉｄ）の各ノードからドキュメントＤ−ｓｔの対応する各ノードへポインタをつけるなどの方法を実施すれば、アクセス衝突の検査において等価なノードであるか否かの比較を容易に行うことができる。
【０１２２】
以降のトランザクションＴｉｄのアクセスは、ドキュメントＤ（Ｔｉｄ）に対して行われる。
【０１２３】
（２）トランザクションが読出しアクセスを要求したときの処理手順
図１２に、トランザクション識別子Ｔｉｄのトランザクションが読出しアクセスＲＥＡＤ（ｐａｔｈ）を要求したときの処理手順例を示す。
【０１２４】
Ｅｖａｌ（ドキュメント名１，ドキュメント名２，読出しアクセス）は、ドキュメント名１で指定したドキュメントとドキュメント名２で指定したドキュメントに対して読出しアクセスＲＥＡＤ（ｐａｔｈ）のｐａｔｈを評価して結果のノード集合を返す関数を表す。ｐａｔｈの評価時には、探索の途中で必要に応じて参照するノード集合の等価性調査が行われ、もし等価でなければ探索を中断してアクセス衝突を知らせる「ｃｏｎｆｌｉｃｔ」という結果を返す。そうでなければ、最後まで探索を続け、結果のノード集合を返す。すなわち、Ｅｖａｌは、ＲＷアクセス衝突の検査で説明した、ドキュメント名１のドキュメントとドキュメント名２のドキュメントに対して読出しアクセスが参照するノード集合の等価性比較を実施しながら読出しアクセスの結果を求める関数である。
【０１２５】
まず、Ｅｖａｌ（Ｄ（Ｔｉｄ），Ｄ−ａｌｌ，ＲＥＡＤ（ｐａｔｈ））の結果を求める（ステップＳ１１）。結果が「ｃｏｎｆｌｉｃｔ」であれば、ＲＷアクセス衝突が起きる。そうでなければ、ＲＷアクセス衝突は起きない。
【０１２６】
ＲＷアクセス衝突がない場合は（ステップＳ１２）、読出しアクセスの結果を、トランザクションマネージャ１１を介してアプリケーションプログラム５に返して、処理を続ける（ステップＳ１３）。また、トランザクションアクセス系列ＡＳ（Ｔｉｄ）にＲＥＡＤ（ｐａｔｈ）を記録する（ステップＳ１４）。
【０１２７】
ＲＷアクセス衝突がある場合は（ステップＳ１２）、読出しアクセスがどのトランザクションの書込みアクセスと衝突するかを調べて、そのトランザクションが終了するまで待たなければならない。調査では、トランザクションリスト１２３の中からＥｖａｌ（Ｄ（Ｔｉｄ），Ｄ（Ｔｉｄ´），ＲＥＡＤ（ｐａｔｈ））＝ｃｏｎｆｌｉｃｔであるトランザクション識別子Ｔｉｄ´を見つける（ステップＳ１５）。そして、読出しアクセス処理を中断してトランザクション待ちグラフ１２２に（Ｔｉｄ´→Ｔｉｄ）を加える（ステップＳ１６）。トランザクションＴｉｄは、トランザクションＴｉｄ´の処理が終了まで待機する。
【０１２８】
図１３に、関数Ｅｖａｌの処理手順例を示す。
【０１２９】
まず、ドキュメントＤ１に対してｐａｔｈの最初のステップｓの評価を始めるとともに、ドキュメントＤ２に対してｐａｔｈの最初のステップｓの評価を始める（ステップＳ２１）。
【０１３０】
ドキュメントＤ１に対してステップｓの評価時に参照されたノード集合をＮ１とし、ドキュメントＤ２に対してステップｓの評価時に参照されたノード集合をＮ２とする（ステップＳ２２）。
【０１３１】
ここで、ノード集合Ｎ１とノード集合Ｎ２とが等価でない場合（ステップＳ２３）、Ｅｖａｌ（Ｄ１，Ｄ２，ＲＥＡＤ（ｐａｔｈ））＝ｃｏｎｆｌｉｃｔを返して終了する（ステップＳ２４）。
【０１３２】
ノード集合Ｎ１とノード集合Ｎ２とが等価である場合（ステップＳ２３）、ｓがｐａｔｈの最後のステップでなければ（ステップＳ２５）、ｓ＝ｐａｔｈの次のステップとして（ステップＳ２６）、ステップＳ２２から繰り返し、ｓがｐａｔｈの最後のステップであれば（ステップＳ２５）、Ｅｖａｌ（Ｄ１，Ｄ２，ＲＥＡＤ（ｐａｔｈ））＝結果のノード集合を返して終了する（ステップＳ２７）。
【０１３３】
（３）トランザクションが書込みアクセスを要求したときの処理手順
図１４に、トランザクション識別子Ｔｉｄのトランザクションが書込みアクセスを要求したときの処理手順例を示す。
【０１３４】
ＭＥＲＧＥ（ドキュメント名１，ドキュメント名２）は、ドキュメント名１で指定したドキュメントとドキュメント名２で指定したドキュメントをマージした結果のドキュメントを返す関数を表す。
【０１３５】
ＧｅｔＤｏｃ（ドキュメント名，書込みアクセス）は、ドキュメント名で指定したドキュメントに対して書込みアクセスで指定した操作の更新結果を反映したドキュメント返す関数を表す。
【０１３６】
まず、ＷＲアクセス衝突の検査のために、Ｄ（Ｔｉｄ）に要求された書込みアクセスＷを行って、更新結果を反映したドキュメントＤ−ｃａｎｄ＝ＧｅｔＤｏｃ（Ｄ（Ｔｉｄ），Ｗ）を求める（ステップＳ３１）。Ｗは、ＩＮＳＥＲＴ（ｎｏｄｅ，ｄａｔａ）、ＩＮＳＥＲＴ（ｎｏｄｅ，ｃｈｉｌｄ−ｄａｔａ）、ＤＥＬＥＴＥ（ｎｏｄｅ）、ＲＥＰＬＡＣＥ（ｎｏｄｅ，ｄａｔａ）のいずれかの操作を指す。また、ＴＬ＝トランザクションリスト−Ｔｉｄ−アクセス系列が空であるトランザクション識別子とする（ステップＳ３２）。
【０１３７】
そして、トランザクションリストにある他のトランザクションの中でトランザクションアクセス系列が空ではない個々のトランザクションに対してステップＳ３４〜Ｓ４０で示す処理を行う。
【０１３８】
ＴＬ＝ＮＵＬＬでなければ（ステップＳ３２）、ＴＬの中の最初のトランザクションのトランザクション識別子をｘｉｄとして、トランザクションｘｉｄのために、ドキュメントＤ−ｓｔをコピーしてドキュメントＤｏｃを用意し、トランザクションアクセス系列ＡＳ（ｘｉｄ）の最初のアクセス記録を取り出して、これをａｃｃｅｓｓとする（ステップＳ３４）。
【０１３９】
ａｃｃｅｓｓが読出しアクセスであれば（ステップＳ３５）、Ｒ＝ａｃｃｅｓｓの操作ＲＥＡＤ（ｐａｔｈ）とし、Ｄ´＝ＭＥＲＧＥ（Ｄｏｃ，Ｄ−ｃａｎｄ）として、Ｅｖａｌ（Ｄ´，Ｄｏｃ，Ｒ）を求める（ステップＳ３６）。
【０１４０】
Ｅｖａｌ（Ｄ´，Ｄｏｃ，Ｒ）の結果がｃｏｎｆｌｉｃｔであれば（ステップＳ３７）、ＷＲアクセス衝突があるので、書込みアクセスの処理を中断してトランザクション待ちグラフ１２２に（ｘｉｄ→Ｔｉｄ）を加えて処理を終了する（ステップＳ３８）。トランザクションＴｉｄは、トランザクションｘｉｄの処理が終了するまで待機する。
【０１４１】
Ｅｖａｌ（Ｄ´，Ｄｏｃ，Ｒ）の結果がｃｏｎｆｌｉｃｔでなければ（ステップＳ３７）、ＷＲアクセス衝突はないので、ステップＳ４０に移る。
【０１４２】
他方、ステップＳ３５においてａｃｃｅｓｓアクセスが書込みアクセスであれば、Ｗ＝ａｃｃｅｓｓの書込みアクセスの操作として、Ｄｏｃ＝ＧｅｔＤｏｃ（Ｄｏｃ，Ｗ）を実行して、ドキュメントＤｏｃに取り出した書込みアクセスＷの更新を反映させ（ステップＳ３９）、ステップＳ４０に移る。
【０１４３】
ａｃｃｅｓｓがトランザクションアクセス系列ＡＳ（ｘｉｄ）の最後のアクセスでなければ（ステップＳ４０）、トランザクションアクセス系列ＡＳ（ｘｉｄ）の次のアクセスを取り出し、これをａｃｃｅｓｓとして（ステップＳ４１）、ステップＳ３５に戻る。
【０１４４】
また、ａｃｃｅｓｓがトランザクションアクセス系列ＡＳ（ｘｉｄ）の最後のアクセスであれば（ステップＳ４０）、対応するトランザクションに対する衝突の検査は終了し、次いで、ＴＬ＝ＴＬ−ｘｉｄとして（ステップＳ４２）、ステップＳ３２に戻る。
【０１４５】
そして、ステップＳ３２においてＴＬ＝ＮＵＬＬれあれば、すなわち、対象となったすべてのトランザクションに対するＷＲアクセス衝突の検査をとおして衝突がなければ、Ｄ（ｔｉｄ）＝Ｄ−ｃａｎｄ、Ｄ−ａｌｌ＝ＧｅｔＤｏｃ（Ｄ−ａｌｌ，Ｗ）として、書込みアクセスＷの結果をドキュメントＤ（Ｔｉｄ）とドキュメントＤ−ａｌｌの両方に反映させるとともに、書込みアクセスＷをトランザクションアクセス系列ＡＳ（Ｔｉｄ）に記録する（ステップＳ３３）。
【０１４６】
（４）トランザクションを中断後に再開するときの処理手順
トランザクションを中断後に再開するときには特別な処理は必要ない。中断していたアクセスが読出しアクセスである場合は、上記の（２）のトランザクションが読出しアクセスを要求したときの処理手順の最初に戻って処理を続ける。書込みアクセスである場合は、上記の（３）のトランザクションが書込みアクセスを要求したときの処理手順の最初に戻って処理を続ける。
【０１４７】
（５）トランザクションをコミットするときの処理手順
トランザクションをコミットして終了するときは、そのトランザクションが行ったデータの更新結果をファイルおよび他のトランザクションのドキュメントに反映させる処理ａと、そのトランザクションの終了を待ちながら中断している他のトランザクションを再開させる処理ｂとを行う。
【０１４８】
トランザクション識別子Ｔｉｄのトランザクションをコミットするときは、まず処理ａのために、ドキュメントＤ（Ｔｉｄ）をその時点のファイルのドキュメントＤ−ｓｔにマージして、ハードディスク３上のファイル３１に記録する。また、ドキュメントＤ（Ｔｉｄ）をトランザクションリスト１２３に記録されている各トランザクションに対応するドキュメントＤにマージする。この操作によって、中断しているものを含むすべてトランザクションのドキュメントＤにコミットされた更新結果を反映される。
【０１４９】
ここでは、トランザクションのコミット時にコミットする更新結果を並行に処理している他のトランザクションへ知らせる場合を例にとって説明したが、この処理を省略あるいは後回しにするように実施することもできる。この処理を省略すると個々のトランザクションのドキュメントＤには反映されていないが、すでにコミットしたデータの更新が存在することとなる。したがって、上記の（２）の処理手順においてＲＷアクセス衝突を発見したときに、アクセス衝突の対象がすでにコミットしたトランザクションであれば、その時点でコミットした更新結果をアクセス衝突を起こしたトランザクションのドキュメントＤに反映すればよい。
【０１５０】
次に、処理ｂのために、トランザクション待ちグラフ１２２からトランザクション識別子Ｔｉｄのトランザクションの終了を待っているトランザクションを見つけ出す。そのようなトランザクションがあれば、そのトランザクションの再開を指示する。また、待ちグラフからトランザクションＴｉｄを表す点とその点を始点とする辺をすべて削除する。
【０１５１】
処理ａと処理ｂが終了すれば、最後に、トランザクション識別子Ｔｉｄをトランザクションリスト１２３と待ちグラフからから削除し、トランザクションアクセス系列ＡＳ（Ｔｉｄ）とドキュメントＤ（Ｔｉｄ）も削除する。
【０１５２】
（６）トランザクションをアボートするときの処理手順
トランザクションをアボートして終了するときは、そのトランザクションが行ったデータの更新結果を破棄する。ドキュメントＤ−ａｌｌには処理中のすべてのトランザクションが行った更新結果が反映されているので、アボートするトランザクションが行った更新結果も反映されている。それを破棄するために、ドキュメントＤ−ａｌｌを再作成する処理を行う。また、コミット時と同様に、そのトランザクションの終了を待ちながら待機している他のトランザクションを再開させる処理を行う。
【０１５３】
トランザクション識別子Ｔｉｄのトランザクションをアボートするときは、まず、トランザクション識別子Ｔｉｄをトランザクションリスト１２３から削除し、トランザクションアクセス系列ＡＳ（Ｔｉｄ）とドキュメントＤ（Ｔｉｄ）も削除する。
【０１５４】
次に、待ちグラフからトランザクション識別子Ｔｉｄのトランザクションの終了を待っているトランザクションを見つけ出す。そのようなトランザクションがあれば、そのトランザクションの再開を指示する。また、待ちグラフからトランザクションＴｉｄを表す点とその点を始点とするすべての辺を削除する。
【０１５５】
最後に、その時点のファイルのドキュメントＤ−ｓｔにトランザクションリスト１２３にあるすべてのトランザクションのドキュメントＤを重ねてマージさせることで、ドキュメントＤ−ａｌｌを再作成する。この処理によってドキュメントＤ−ａｌｌは、アボートするトランザクションを除くすべての処理中のトランザクションの更新結果を反映していることとなる。
【０１５６】
（リソースマネージャの第２の構成例）
次に、リソースマネージャの第２の構成例について説明する。
【０１５７】
第２の構成例が第１の構成例と異なる点は、ＷＲアクセス衝突の検査の方法である。第１の構成例では、リソースマネージャ１２は、トランザクションのトランザクションアクセス系列をトレースして以前の読出しアクセス時のドキュメントＤの状態を再作成しながらＷＲアクセス衝突の検査を行う。第２の構成例では、リソースマネージャ１２は、各ドキュメントＤの以前の状態を再作成する方法に代わって、ドキュメントＤ−ａｌｌの以前の状態を用いる方法によってＷＲアクセス衝突の検査を行う。
【０１５８】
（ＷＲアクセス衝突の検査）
以下、ＷＲアクセス衝突の検査について説明する。
【０１５９】
図１５は、あるトランザクションＴｉｄのトランザクションアクセス系列の一例を示している。Ｔｉｄは、トランザクション識別子である。トランザクションは、読出しアクセスと書き込みアクセスからなるアクセス系列を持つ。図１５において、縦線は連続した読出しアクセスの系列（１つの読出しアクセスのみからなる系列である場合を含む）を表し、四角は書込みアクセスを表し、上下に連続した四角は連続した書込みアクセス系列を表す。以降、トランザクションＴｉｄの連続した読出しアクセスの系列をＲＳＴｉｄと表記し、連続した書込みアクセス系列ＷＳＴｉｄと表記する。また、ＷＳＴｉｄ（ｉ）はトランザクション処理の開始以降のｉ番目のＷＳＴｉｄを表し、ＲＳＴｉｄ（ｉ）はＷＳＴｉｄ（ｉ）の後に続くＲＳＴｉｄを表す。最初の書込みアクセス以前の読出しアクセスの系列は、ＲＳＴｉｄ（０）とする。
【０１６０】
ここでは、リソースマネージャ１２が図１６に例示するようなトランザクションアクセス系列を持つ３つのトランザクションＴ１、トランザクションＴ２、トランザクションＴ３を処理しているときに、Ｔｉｍｅ６の時点でトランザクションＴ１が書込みアクセスＷを要求した場合のＷＲアクセス衝突の検査を例にとって説明する。
【０１６１】
リソースマネージャ１２は、この書込みアクセスＷが、並列に処理中の他のトランザクション、すなわち、トランザクションＴ２とトランザクションＴ３とがすでに行った読み込みアクセスと衝突しないかを検査する必要がある。すなわち、トランザクション２のＲＳＴ２（０）とＲＳＴ２（１）とＲＳＴ２（２）のすべての読出しアクセスおよびトランザクションＴ３のＲＳＴ３（０）とＲＳＴ３（１）とＲＳＴ３（２）のすべての読出しアクセスが、ＷＲアクセス衝突検査の対象である。
【０１６２】
トランザクションＴ１がドキュメントＤ（１）に対して書込みアクセスＷを行った更新後のドキュメントをＤ´（１）とする。
【０１６３】
第１の構成例で説明したように、例えば、ＲＳＴ２（１）の読出しアクセスＲとのＷＲアクセス衝突を検査するときは、Ｔｉｍｅ１の時点のドキュメントＤ（２）と、ドキュメントＤ（２）およびドキュメントＤ´（１）をマージしたドキュメントに対する読出しアクセスＲの参照するノード集合を比較する。
【０１６４】
すべての読出しアクセスに対してこの検査を行うので、第１の構成例では、トランザクションＴ１とトランザクションＴ２のトランザクションアクセス系列を順番に実行してＴｉｍｅ１とＴｉｍｅ５の時点のＤ（２）と、Ｔｉｍｅ３とＴｉｍｅ４の時点のＤ（３）を求める。
【０１６５】
これに対して、第２の構成例では、ドキュメントＤ−ａｌｌを用いてＷＲアクセス衝突を検査する。Ｔｉｍｅ１の時点のドキュメントＤ（２）は、ドキュメントＤ−ｓｔに対してＷＳＴ２（１）の書込みアクセスの更新結果を反映したものである。この更新はＴｉｍｅ１の時点のＤ−ａｌｌにも反映されているので、Ｔｉｍｅ１の時点のＤ（２）の代わりに、Ｔｉｍｅ１の時点のＤ−ａｌｌに対して読出しアクセスＲを行っても、その結果は同じである。したがって、アクセス衝突の検査は、Ｔｉｍｅ１の時点のＤ−ａｌｌに対する読出しアクセスＲの参照するノード集合と、Ｄ´（１）とＴｉｍｅ１の時点のＤ−ａｌｌとをマージしたドキュメントに対する読出しアクセスＲの参照するノード集合とが同じであるかを比較することと等価になる。同様に、ＲＳＴ２（０）とＲＳＴ３（０）に対する検査では初期時点のＤ−ａｌｌすなわちドキュメントＤ−ｓｔを、ＲＳＴ２（２）に対する検査ではＴｉｍｅ５の時点のＤ−ａｌｌ、ＲＳＴ３（１），ＲＳＴ３（２）に対する検査ではＴｉｍｅ３，４の時点のＤ−ａｌｌを使用すればよい。第２の構成例では、更新されるドキュメントＤ−ａｌｌの各状態を記録しておいて、以降のＷＲアクセス衝突の検査で使用する。
【０１６６】
ただし、記録容量が十分確保できる場合には、すべての時点においてＤ−ａｌｌの状態を記録しておくができるが、他方、記録容量が限られている場合には、すべての時点においてＤ−ａｌｌの状態を記録しておくことはできないため、どの時点のＤ−ａｌｌを記録するのが効果的であるかを決定しなければならない。
【０１６７】
例えば、ＲＳＴ２（１）の読出しアクセスに対する衝突の検査を行うときは、Ｔｉｍｅ１の時点のＤ−ａｌｌを使用しても、Ｔｉｍｅ３，４の時点のＤ−ａｌｌを使用してもよい。なぜなら、トランザクションＴ２のＷＳＴ２（１）の更新がＤ−ａｌｌに反映されたＴｉｍｅ１以降から、トランザクションＴ２のＷＳＴ２（２）が次の更新ＴをＤ−ａｌｌに反映するＴｉｍｅ５の前であれば、どの時点のＤ−ａｌｌに対する読出しアクセスＲの参照するノード集合も等価であるからである。ドキュメントＤ−ａｌｌにはリソースマネージャ１２が並行に処理しているすべてのトランザクションの更新結果が反映されているが、それらの更新はお互いにアクセス衝突を起こないものである。
【０１６８】
もしＴｉｍｅ１の時点のＤ−ａｌｌに対する読出しアクセスＲの参照するノード集合と、Ｔｉｍｅ２の時点のＤ−ａｌｌに対する読出しアクセスＲの参照するノード集合とが異なれば、Ｔｉｍｅ２の時点でのＤ−ａｌｌを更新したトランザクションＴ１の書込みアクセスがＲと衝突するということである（ただし、Ｔｉｍｅ５でのＤ−ａｌｌの更新は、他のトランザクションではなくトランザクションＴ２の書込みアクセスによって行われるので、Ｔｉｍｅ５でのＤ−ａｌｌに対するトランザクションＴ２の読出しアクセスＲの参照するノード集合は、それ以前の結果と同じではない）。
【０１６９】
このような理由により、この例では、ＲＳＴ２（１）とＲＳＴ３（１）に対するＷＲアクセス衝突の検査で同じＴｉｍｅ３の時点のＤ−ａｌｌを使用できる。第２の構成例では、Ｔｉｍｅ３時点のＤ−ａｌｌのように複数のＲＳに対するＷＲアクセス衝突の検査で利用できるＤ−ａｌｌを選択して記録する。どのタイミングでＤ−ａｌｌの状態を記録するかを決める方法については以降で詳しく説明する。
【０１７０】
図１７に、第２の構成例に係るリソースマネージャの構成例を示す。図中、１２はリソースマネージャ、１２１はドキュメントＤ−ａｌｌ、１２２はトランザクション待ちグラフ、１２３はトランザクションリスト、１２４はトランザクションアクセス系列、１２５はドキュメントＤ（Ｔｉｄ）、１２６は記録数を、１２７はドキュメントＤ−ｓを、１２８はＳ−Ｐｏｉｎｔ管理表を、３はハードディスクを、３１はドキュメントＤ−ｓｔ（図１のファイル３１）をそれぞれ示す。
【０１７１】
以下では、第１の構成例のリソースマネージャ１２と相違する点を中心に説明する。
【０１７２】
図１７のトランザクションアクセス系列１２４は、第１の構成例のリソースマネージャ１２と同様に、個々のトランザクションが処理の開始から行ってきた読出しアクセスおよび書込みアクセスの系列をリストとして記録管理している。ただし、読出しアクセス系列と書込みアクセス系列に加えて、書込みアクセス系列の書込みアクセス数を管理する。以降で説明するが、書込みアクセス数は、どの時点でＤ−ａｌｌの状態を記録するかを決定するために用いられる。
【０１７３】
図１８に、トランザクションアクセス系列の一構成例を示す。この例は、図１５で例示したトランザクションＴｉｄのトランザクションアクセス系列と同じ例である。
【０１７４】
トランザクションアクセス系列ＡＳ（Ｔｉｄ）は、読出しアクセス系列と書込みアクセス系列のリストであり、ＲＳ（ｉ）とＷＳ（ｉ）には、それぞれ、トランザクションＴｉｄのｉ番目の読出しリストＲＳＴｉｄ（ｉ）の読出しアクセス操作のリストと、ｉ番目の書込みアクセスリストＷＳＴｉｄ（ｉ）の書込みアクセス操作のリストが記録されている。
【０１７５】
図１７の記録数Ｈ（図中の１２６）は、ドキュメントＤ−ａｌｌの更新前の状態を何個まで記録できるかを示す数値である。記録数Ｈが大きければ大きいほどＤ−ａｌｌの状態を多く記録できるのでＷＲアクセス衝突検査の効率が上がる。反面、Ｄ−ａｌｌの記録に必要な記憶容量が大きくなるというトレードオフがある。記録数Ｈは、トランザクション処理システムが初期に設定するが、トランザクションの処理中にその値を変更してもよい。
【０１７６】
図１７のドキュメントＤ−ｓ（図中の１２７）は、過去のある時点のドキュメントＤ−ａｌｌの状態を記録している。以降、Ｄ−ａｌｌを記録した時点をＳ−Ｐｏｉｎｔと呼び、ある時点でＤ−ａｌｌを記録すると決定することをＳ−Ｐｏｉｎｔを設定すると呼ぶ。リソースマネージャ１２は、記録数Ｈ個までのＳ−Ｐｏｉｎｔを設定できるので、Ｈ個までのＤ−ｓを記録管理している。ｉ番目に設定されたＳ−Ｐｏｉｎｔで記録されたＤ−ｓをＤ−ｓ（ｉ）と表記する。
【０１７７】
図１７のＳ−Ｐｏｉｎｔ管理表（図中の１２８）には、記録数Ｈ個までのエントリがあり、各エントリーは個々のＳ−Ｐｏｉｎｔに対応する。各エントリーには、対応するＳ−Ｐｏｉｎｔを設定した時点において各トランザクションが何番目の書込みアクセス系列ＷＳまでの更新結果をＤ−ａｌｌに反映しているかを示す情報と、そのＳ−Ｐｏｉｎｔの設定によって得られる効果の大きさを示す情報を記録管理している。
【０１７８】
以下、リソースマネージャ１２がＳ−Ｐｏｉｎｔ管理表１２８に記録している情報を利用してＳ−Ｐｏｉｎｔの設定を決定する方法について説明する。
【０１７９】
図１９は、図１６と同じトランザクションＴ１、トランザクションＴ２、トランザクションＴ３のトランザクションアクセス系列を表している。ただし、Ｔｉｍｅ１からＴｉｍｅ５の各時点が図１６とは異なる例である。
【０１８０】
トランザクションが要求した各書込みアクセスが分離性を破らないと判断されてＤ−ａｌｌを更新することになったときに、Ｓ−Ｐｏｉｎｔを設定するか否か、すなわち、その時点のＤ−ａｌｌの状態をＤ−ｓとして記録しておくか否かを決定する。
【０１８１】
図２０は、図１９のＴｉｍｅ１の時点で１つ目のＳ−Ｐｏｉｎｔが設定され、Ｔｉｍｅ２の時点で２つ目のＳ−Ｐｏｉｎｔが設定されたときのＳ−Ｐｏｉｎｔ管理表１２８を示す。
【０１８２】
Ｓ−Ｐｏｉｎｔ管理表１２８の各エントリーは、１つのＳ−Ｐｏｉｎｔに対応していて、各エントリーのＳ−Ｐｏｉｎｔ番号は、対応するＳ−Ｐｏｉｎｔが何番目のＳ−Ｐｏｉｎｔであるかを示す。
【０１８３】
Ｓ−Ｐｏｉｎｔエントリーには、まず、リソースマネージャ１２が処理中の各トランザクションに対応したそれぞれのＷＳ番号の欄がある。各トランザクションのＷＳ番号の欄には、Ｓ−Ｐｏｉｎｔが設定された時点においてそのトランザクションの最近の書込みアクセスリストが何番目のＷＳであったかを記録している。Ｓ−Ｐｏｉｎｔエントリーの各トランザクションのＷＳ番号から、Ｓ−Ｐｏｉｎｔの時点で記録したＤ−ａｌｌ（すなわち、Ｄ−ｓ）に、そのトランザクションの何番目のＷＳまでの更新結果が反映されているかがわかる。したがって、Ｓ−Ｐｏｉｎｔに対応するＤ−ｓを利用して、そのトランザクションのＷＳ番目の読出しアクセス系列の読出しアクセスに対するＷＲアクセス衝突を検査できるということがわかる。
【０１８４】
例えば、図１９において、１番目のＳ−Ｐｏｉｎｔが設定されたＴｉｍｅ１の時点におけるトランザクションＴ２の最近の書込みアクセスリストＷＳＴ２（１）は、１番目のＷＳである。よって、図２０において、Ｓ−Ｐｏｉｎｔ番号が１のエントリーにおけるトランザクション２のＷＳ番号は１である。他のトランザクションＴ１とＴ３に対しては、最近の書込みアクセスリストがないので、０となっている。同様に、２番目のＳ−Ｐｏｉｎｔが設定されたＴｉｍｅ２の時点におけるトランザクションＴ１の最近の書込みアクセスリストＷＳＴ１（１）は、１番目のＷＳであるので、図２０のＳ−Ｐｏｉｎｔ番号が２のエントリーのトランザクション１のＷＳ番号は１となっている。
【０１８５】
Ｓ−Ｐｏｉｎｔエントリーには、次に、対応するＳ−Ｐｏｉｎｔを設定することによって得られる効果の大きさを表す効果値の欄がある。Ｓ−Ｐｏｉｎｔを設定してＤ−ａｌｌの状態をＤ−ｓとして記録しておくと、以降のＷＲアクセス衝突の検査においてＤ−ｓを利用することができるので、Ｄ−ａｌｌの状態を再現するために必要なコストが削減できる。Ｓ−Ｐｏｉｎｔ設定以降のＷＲアクセス衝突の検査のたびにそのコストを削減できるので、Ｓ−Ｐｏｉｎｔの設定によって得られる効果の大きさは、Ｓ−Ｐｏｉｎｔを設定しなかったときにその時点のＤ−ａｌｌを再現するために必要なコストに比例する。Ｓ−Ｐｏｉｎｔの時点のＤ−ａｌｌを再現するためには、各トランザクションに対するその時点において最近の書込みアクセスリスト（すなわち、ＷＳ番目の書込みアクセスリスト）の書き込みアクセスをもう一度行い、Ｄ−ａｌｌに反映された更新を再現する必要がある。
【０１８６】
したがって、Ｓ−Ｐｏｉｎｔの効果値は、Ｓ−Ｐｏｉｎｔエントリーにおける各トランザクションのＷＳ番目の書込みアクセスリストの書込みアクセス数の和とする。
【０１８７】
ただし、Ｓ−ＰｏｉｎｔエントリーにおいてトランザクションのＷＳ番号が１つ前のＳ−ＰｏｉｎｔエントリーにおけるＷＳ番号と同じである場合は、１つ前のＳ−ＰｏｉｎｔのＤ−ｓにＷＳ番目の書込みアクセスリストの更新結果がすでに反映されているので、そのトランザクションのＷＳ番目の書込みアクセスリストの書込みアクセス数は効果値に足さない。例えば、図２０の１番目のＳ−Ｐｏｉｎｔの効果値は、ＷＳＴ２（１）の書き込みアクセス数から１となっている。２番目のＳ−Ｐｏｉｎｔの効果値は、ＷＳＴ１（１）の書き込みアクセス数から３となっている。２番目のＳ−Ｐｏｉｎｔのエントリーのトランザクション２のＷＳ番号欄が１であるが、１つ前の１番目のＳ−ＰｏｉｎｔエントリーのＷＳ番号欄も同じく１であるのでＷＳＴ２（１）の書き込みアクセス数は２番目のＳ−Ｐｏｉｎｔの効果値に足さない。例えば、図１９のＴｉｍｅ２で１番目のＳ−Ｐｏｉｎｔが設定されたときは、Ｓ−Ｐｏｉｎｔ管理表１２８は図２１のようになり、１番目のＳ−Ｐｏｉｎｔの効果値はＷＳＴ１（１）の書き込みアクセス数にＷＳＴ２（１）の書き込みアクセス数を足して３＋１＝４となる。
【０１８８】
リソースマネージャ１２は、Ｓ−Ｐｏｉｎｔ管理表１２８にある各トランザクションのＷＳ番号を参照することでＷＲアクセス衝突の調査のときにどのＤ−ｓを利用できるかを知る。また、ある時点でＳ−Ｐｏｉｎｔを設定するときの効果値を計算し、その値を基準として新しいＳ−Ｐｏｉｎｔを設定するか否かを決定する。Ｓ−Ｐｏｉｎｔ設定を決定する方法については、以降のトランザクションが書込みアクセスを要求したときのリソースマネージャ１２の処理手順の中で詳しく説明する。
【０１８９】
以下では、リソースマネージャ１２が行う処理手順の一例について、（１）トランザクションの処理を開始するときの処理手順、（２）トランザクションが読出しアクセスを要求したときの処理手順、（３）トランザクションが書込みアクセスを要求したときの処理手順、（４）トランザクションを中断後に再開するときの処理手順、（５）トランザクションをコミットするときの処理手順、（６）トランザクションをアボートするときの処理手順の順番に説明する。
【０１９０】
（１）トランザクションの処理を開始するときの処理手順
トランザクションの処理を開始するときの処理手順例は、図１１で示した第１の構成例のリソースマネージャ１２の処理手順例と同様である。
【０１９１】
（２）トランザクションが読出しアクセスを要求したときの処理手順
トランザクションが読出しアクセスを要求したときの処理手順例は、図１２で示した第１の構成例のリソースマネージャ１２の処理手順例と同様である。ただし、図１２のステップＳ１４でＲＥＡＤ（ｐａｔｈ）をトランザクションアクセスリストＡＳ（Ｔｉｄ）に追加するときは、もしＡＳ（Ｔｉｄ）の最後のアクセスリストが読出しアクセスリストＲＳ（ｉ）であれば、そのリストの最後に追加記録し、書込みアクセスリストＷＳ（ｉ）であれば、新しいＲＳ（ｉ）を作成して、その最初のアクセスとして記録する。もしトランザクションの最初のアクセスであれば、ＲＳ（０）の最初のアクセスとして記録する。
【０１９２】
（３）トランザクションが書込みアクセスを要求したときの処理手順
リソースマネージャ１２は、まず、Ｓ−Ｐｏｉｎｔ管理表１２８を調べて、利用可能なＤ−ｓを参照しながら、ＷＲアクセス衝突の検査を行う。調査の結果、要求された書込みアクセスが衝突を起こさないことがわかれば、次に、その時点でＳ−Ｐｏｉｎｔを設定するか否かを決定して、それから書込みアクセスの結果をＤ−ａｌｌに反映する。
【０１９３】
以下では、Ｓ−Ｐｏｉｎｔ管理表１２８のｈ番目のＳ−Ｐｏｉｎｔエントリーの各トランザクションＴｉｄに対応するＷＳ番号をＭＴｉｄ（ｈ）と表記する。
【０１９４】
まず、ＷＲアクセス衝突の検査について説明する。
【０１９５】
リソースマネージャ１２は、トランザクションＴｉｄの要求した書込みアクセスＷが、トランザクションリストにある他のすべてのトランザクションの読出しアクセスリストに対して衝突を起こさないかを検査する必要がある。Ｓ−Ｐｏｉｎｔ管理表１２８のエントリーのＷＳ番号欄に検査対象となる読出しアクセスリストの番号があれば、対応するＳ−ＰｏｉｎｔのＤ−ｓを利用する。番号がないときは、その時点のＤ−ａｌｌを再作成する必要がある。ただし、各トランザクションの最初の読み込みアクセスリストＲＳ（０）に対して検査を行うときは、Ｄ−ｓｔを利用することができ、最近の読み込みアクセスリストに対して検査を行うときは、Ｄ−ａｌｌを利用することができる。現時点のＤ−ａｌｌには、各トランザクションの最近の書込み、すなわちトランザクションアクセスリストの最後のＷＳの書込みの結果が反映されている。
【０１９６】
ＷＲアクセス衝突の検査では、まず、トランザクションＴｉｄの要求した書込みアクセスＷをドキュメントＤ（Ｔｉｄ）に反映したドキュメントＤ−ｃａｎｄを用意する。また、変数ｈの初期値を最後のＳ−Ｐｏｉｎｔの番号＋１とする。
【０１９７】
ここでは、Ｓ−Ｐｏｉｎｔ管理表１２８の最後のエントリーから最初のエントリーまでを逆順に参照しながら衝突の検査を行う場合を例にとって説明するが、もちろん、どのような順番で行っても実施できる。
【０１９８】
変数ｈが最後のＳ−Ｐｏｉｎｔの番号＋１のときの処理は、各トランザクションの最近の読出しアクセスリストＲＳに対する検査を示す。その時点の各トランザクションの最後の書込みアクセスリストをＷＳ（ｉ）とすると、ＲＳ（ｉ）を対象する検査である。すでに説明したように、この場合は、その時点のＤ−ａｌｌを利用できるので、ＲＳ（ｉ）の各読出しアクセスＲに対してＥｖａｌ（Ｄ−ａｌｌ、ＭＥＲＧＥ（Ｄ−ａｌｌ，Ｄ−ｃａｎｄ），Ｒ）の結果がｃｏｎｆｌｉｃｔではないかを調べる。すべてのトランザクションの各読出しアクセスに対して結果がｃｏｎｆｌｉｃｔでなければ、衝突は起きない。
【０１９９】
変数ｈが０のときの処理は、各トランザクションの最初の読出しアクセスリストＲＳ（０）に対する検査を示す。すでに説明したように、この場合は、Ｄ−ｓｔを利用できるので、ＲＳ（ｉ）の各読出しアクセスＲに対してＥｖａｌ（Ｄ−ｓｔ，ＭＥＲＧＥ（Ｄ−ｓｔ，Ｄ−ｃａｎｄ），Ｒ）の結果がｃｏｎｆｌｉｃｔではないかを調べる。すべてのトランザクションの各読出しアクセスに対して結果がｃｏｎｆｌｉｃｔでなければ、衝突は起きない。
【０２００】
変数ｈがその他の値であるときは、各トランザクションに対して次の処理を行う。トランザクション識別子をｘｉｄとする。Ｓ−Ｐｏｉｎｔ管理表１２８のｈ番目のエントリーからトランザクションｘｉｄのＷＳ番号Ｍｘｉｄ（ｈ）を調べ、そのＷＳ番号をｉとする。なお、ｈ番目のＳ−Ｐｏｉｎｔを設定した時点で記録されたドキュメントＤ−ｓ（ｈ）にはＷＳ（ｉ）の更新結果が反映されているので、ＲＳ（ｉ）に対するアクセス衝突検査でＤ−ｓ（ｈ）を利用できる。ｉ＝Ｍｘｉｄ（ｈ＋１）であれば、ＲＳ（ｉ）に対する検査はすでに行われているので検査の必要はない。そうでなければ、まず、ＲＳ（ｉ）の各読出しアクセスＲに対して、Ｅｖａｌ（Ｄ−ｓ（ｈ），ＭＥＲＧＥ（Ｄ−ｓ（ｈ），Ｄ−ｃａｎｄ），Ｒ）を調べる。次に、ｉ＝ｉ＋１としてＲＳ（ｉ）の次の読出しアクセスリストについて考える。もしｉ＝Ｍｘｉｄ（ｈ＋１）であれば、ＲＳ（ｉ）に対する検査はすでに行われている。もしｉ＜Ｍｘｉｄ（ｈ＋１）であれば、ＲＳ（ｉ）の読出しアクセスが行われた時点のＤ−ａｌｌの状態は記録されていないので、再作成を行う必要がある。Ｄ−ｓ（ｈ）にＷＳ（ｉ）の更新操作を行って得られるドキュメントをＤｏｃとして、ＲＳ（ｉ）に対する検査はＤｏｃを用いて行われる。すなわち、ＲＳ（ｉ）の各読出しアクセスＲに対してＥｖａｌ（Ｄｏｃ，ＭＥＲＧＥ（Ｄｏｃ，Ｄ−ｃａｎｄ），Ｒ）の結果を調べる。この処理は、ＲＳ（ｉ）の次の読出しアクセスリストが最後のＲＳである、あるいは、そのＲＳに対する検査がすでに行われている、という条件を満たすまで繰り返される。
【０２０１】
以上のようにして、すべてのトランザクションの読出しアクセスリストに対してＷＲアクセス衝突の検査が終り衝突がなければ、その時点でＳ−Ｐｏｉｎｔを設定するか否かを決める処理に入る。
【０２０２】
その後に、書込みアクセスＷの結果をドキュメントＤ（Ｔｉｄ）とドキュメントＤ−ａｌｌの両方に反映させる。また、書込みアクセスＷをトランザクションアクセス系列ＡＳ（Ｔｉｄ）に記録する。
【０２０３】
図２２に、トランザクション識別子Ｔｉｄのトランザクションが書込みアクセスＷを要求したときのＷＲアクセス衝突の調査の処理手順の一例を示し。
【０２０４】
ステップＳ５１で、Ｄ−ｃａｎｄ＝ＧｅｔＤｏｃ（Ｄ（Ｔｉｄ），Ｗ）、ｈ＝最後のＳ−Ｐｏｉｎｔの番号＋１とする。
【０２０５】
ステップＳ５２で、ｈ＝最後のＳ−Ｐｏｉｎｔの番号＋１ならば、ステップＳ５３でＤｏｃ＝Ｄ−ａｌｌとし、ｈ＝０ならば、ステップＳ５４でＤｏｃ＝Ｄ−ｓｔとし、それ以外ならば、ステップＳ５５でＤｏｃ＝ＭＥＲＧＥ（Ｄ−ｓ（ｈ），Ｄ−ｃａｎｄ）とした後に、いずれの場合も、ステップＳ５６で、ＴＬ＝トランザクションリスト−Ｔｉｄ−アクセス系列が空でないトランザクション識別子とする。
【０２０６】
ステップＳ５７で、ＴＬ＝ＮＵＬＬの場合、ステップＳ５８でｈ＝０ならば、ステップＳ５９に移って、この処理を終了し、次のＳ−Ｐｏｉｎｔ決定フローチャート（図２３参照）を実行する。他方、ステップＳ５８でｈ＝０でないならば、ステップＳ６０で、ｈ＝ｈ−１として、ステップＳ５２に戻る。
【０２０７】
ステップＳ５７で、ＴＬ＝ＮＵＬＬでない場合、ステップＳ６２で、ＲＳ＝Ｒｘｉｄ（ｉ）、Ｒ＝ＲＳの最初のアクセス、Ｄ´＝ＭＥＲＧＥ（ＤＯＣ，Ｄ−ｃａｎｄ）とする。
【０２０８】
ステップＳ６３で、Ｅｖａｌ（Ｄ´，Ｄｏｃ，Ｒ）＝ｃｏｎｆｌｉｃｔである場合、ステップＳ６４で、待ちグラフに（ｘｉｄ→Ｔｉｄ）を追加する。
【０２０９】
他方、ステップＳ６３で、Ｅｖａｌ（Ｄ´，Ｄｏｃ，Ｒ）＝ｃｏｎｆｌｉｃｔでない場合、ステップＳ６５で、ＲがＲＳの最後のアクセスでなければ、ステップＳ６６で、Ｒ＝ＲＳの次のアクセスとし、ステップＳ６３に戻る。
【０２１０】
ステップＳ６５で、ＲがＲＳの最後のアクセスであれば、ステップＳ６７で、ｈ＝最後のＳ−Ｐｏｉｎｔの番号＋１であるとき、あるいは、そうでなくても、ステップＳ６８で、Ｍｘｉｄ（ｈ）＝Ｍｘｉｄ（ｈ＋１）であるとき、あるいは、そうでなくても、ステップＳ６９で、ｉ＜Ｍｘｉｄ（ｈ＋１）でないときは、ステップＳ７０で、ＴＬ＝ＴＬ−ｘｉｄとして、ステップＳ６２に戻る。
【０２１１】
また。ステップＳ６９で、ｉ＜Ｍｘｉｄ（ｈ＋１）であるときは、ステップＳ７１で、ｉ＝ｉ＋１、Ｄｏｃ＝ＤｏｃにＷＳ（ｉ）の更新結果を反映したドキュメントとして、ステップＳ６２に戻る。
【０２１２】
次に、Ｓ−Ｐｏｉｎｔの設定について説明する。
【０２１３】
この処理は、書込みアクセスＷをトランザクションアクセス系列の新しい書込みアクセスリストＷＳ（ｉ＋１）の最初のアクセスとして記録する前に行う。
【０２１４】
まず、新しいＳ−Ｐｏｉｎｔを設定したときに増える効果値を計算する。すでに説明したように、効果値は、すべてのトランザクションにおける最近の書込みアクセスリストＷＳの書込みアクセス数の和である。ただし、ＷＳの番号が前に設定されたＳ−ＰｏｉｎｔエントリーのＷＳ番号と同じであれば、ＷＳの書込みアクセス数は効果値に足さない。図２３においては、変数ｅが、計算された効果値を表している。
【０２１５】
効果値（ｅ）を計算した後、Ｓ−Ｐｏｉｎｔ管理表１２８にある最後のＳ−Ｐｏｉｎｔ番号を調べる。最後のＳ−Ｐｏｉｎｔ番号は、その時点までに設定されたＳ−Ｐｏｉｎｔの数である。その数をｈ´とする。
【０２１６】
ｈ´が記録数Ｈより小さければ、新しいＳ−Ｐｏｉｎｔを設定する。Ｓ−Ｐｏｉｎｔ管理表１２８に、新たに、ｈ´＋１番目のＳ−Ｐｏｉｎｔのエントリーを作成する。エントリーのＳ−Ｐｏｉｎｔ番号はｈ´＋１であり、効果値はｅである。各トランザクションに対応するＷＳ番号には、トランザクションアクセス系列を調べて各トランザクションの最近の書込みアクセスリストの書き込みアクセス数を記録する。そして、その時点のＤ−ａｌｌを、Ｄ−ｓ（ｈ´＋１）として記録する。
【０２１７】
ｈ´が記録数Ｈと同じであれば、それ以上の数のＳ−Ｐｏｉｎｔは設定できない。したがって、すでに設定したＳ−Ｐｏｉｎｔの中で取り消した場合に減る効果値が一番小さいものを調べ、新しいＳ−Ｐｏｉｎｔを設定して増える効果値と比較する。各Ｓ−Ｐｏｉｎｔの取り消しによって減る効果値は、そのＳ−Ｐｏｉｎｔを削除してもその次のＳ−Ｐｏｉｎｔ（最近のＳ−Ｐｏｉｎｔの場合は、新しく設定するＳ−Ｐｏｉｎｔ）に移動するだけで消滅はしない値を効果値から引いたものである。例えば、あるｈ番目のＳ−Ｐｏｉｎｔの効果値に、あるトランザクションｘｉｄのＷＳ番目の書込みアクセスリストの書込みアクセス数Ｎが加算されているときについて考える。ｈ＋１番目のＳ−Ｐｏｉｎｔ（ｈ＝ｈ´の場合は、新しいＳ−Ｐｏｉｎｔ）においてトランザクションｘｉｄが同じＷＳ番号である場合は、ｈ番目のＳ−Ｐｏｉｎｔを取り消しても、Ｎは次のｈ＋１番目のＳ−Ｐｏｉｎｔ（あるいは新しいＳ−Ｐｏｉｎｔ）の効果値に加算される。そうではない場合は、値Ｎ分の効果値は、ｈ番目のＳ−Ｐｏｉｎｔの取り消しによって消滅する。
【０２１８】
取り消しによって減る効果値が一番小さかったＳ−Ｐｏｉｎｔの番号をｈ−ｍｉｎとする。ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔを削除すると減る効果値と、新しいＳ−Ｐｏｉｎｔを設定すると増える効果値を計算して、後者が大きければ、ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔを取り消して新しいＳ−Ｐｏｉｎｔを設定する。ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔを削除すると減る効果値は、ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔの効果値から変数ｅ１の値を引いたものである。ｅ１の値は、各トランザクションに対して、ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔに対応するＷＳ番号Ｍｘｉｄ（ｈ−ｍｉｎ）と、その次のｈ−ｍｉｎ＋１番目のＳ−Ｐｏｉｎｔに対応するＷＳ番号Ｍｘｉｄ（ｈ−ｍｉｎ＋１）が同じである場合に、ＷＳ番目の書込みアクセスリストの書込みアクセス数を足したものである。Ｍｘｉｄ（ｈ−ｍｉｎ）とＭｘｉｄ（ｈ−ｍｉｎ＋１）とが同じである場合は、ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔを削除してもｈ−ｍｉｎ＋１番目のＳ−ＰｏｉｎｔのドキュメントＤ−ｓ（ｈ＋１）にトランザクションｘｉｄのＷＳ番目の書込みアクセスリストの更新結果が反映されているので、その分の効果値は減らずに、ｈ−ｍｉｎ＋１番目のＳ−Ｐｏｉｎｔの効果値に足される。
【０２１９】
新しいＳ−Ｐｏｉｎｔを設定すると増える効果値ｅがｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔを削除すると減る効果値より大きければ、ｈ−ｍｉｎ番目のＳ−ＰｏｉｎｔのエントリーとＤ−ｓ（ｈ−ｍｉｎ）を削除し、それ以降のＳ−Ｐｏｉｎｔの番号と対応するＤ−ｓの番号を１ずつ減らす。また、新しいｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔの効果値にｅ１を足す。そして、新しいＳ−Ｐｏｉｎｔのエントリーを作成してその時点のＤ−ａｌｌをＤ−ｓ（Ｈ）として記録する。
【０２２０】
図２３に、Ｓ−Ｐｏｉｎｔ設定の処理手順の一例を示す。
【０２２１】
ステップＳ８１で、ｈ´＝最後のＳ−Ｐｏｉｎｔの番号、ＴＬ＝トランザクションリスト、ｘｉｄ＝ＴＬの中の最初のトランザクション識別子とする。
【０２２２】
ステップＳ８２で、ｍ＝ＡＳ（ｘｉｄ）の最後のＷＳの番号とする。
【０２２３】
ステップＳ８３で、ｍ＝Ｍｘｉｄ（ｈ´）でないならば、ステップＳ８４で、ｅ＝ＡＳ（ｘｉｄ）の最後のＷＳの書き込みアクセス数とし、他方、ステップＳ８３で、ｍ＝Ｍｘｉｄ（ｈ´）であるならば、ステップＳ８４は、スキップする。
【０２２４】
ステップＳ８５で、ＴＬ＝ＮＵＬＬでない場合、ステップＳ８６で、ＴＬ＝ＴＬ−ｘｉｄ、ｘｉｄ＝ＴＬの中の最初のトランザクション識別子として、ステップＳ８２に戻る。
【０２２５】
ステップＳ８５で、ＴＬ＝ＮＵＬＬである場合、ステップＳ８７で、ｈ´＜記録数Ｈであるならば、ステップＳ８８に移り、新しいＳ−Ｐｏｉｎｔを設定し、その効果値＝ｅとして、この処理を終了する。
【０２２６】
他方、ステップＳ８７で、ｈ´＜記録数Ｈでないならば、ステップＳ８９に移り、ｈ−ｍｉｎ＝削除によって減る効果が一番小さいＳ−ｐｏｉｎｔの番号、ＴＬ＝トランザクションリスト、ｘｉｄ＝ＴＬの中の最初のトランザクション識別子とする。
【０２２７】
ステップＳ９０で、ｅ１＝０とする。
【０２２８】
ステップＳ９１で、ｈ−ｍｉｎ＝ｈ´である場合、ステップＳ９２で、ｍ＝ＡＳ（ｘｉｄ）の最後のＷＳの番号とし、ステップＳ９３で、ｍ＝Ｍｘｉｄ（ｈ−ｍｉｎ）であるならば、ステップＳ９５で、ｅ１＝ｅ１＋ＡＳ（ｘｉｄ）のＭｘｉｄ（ｈ−ｍｉｎ）番目の書き込みアクセス数とし、ｍ＝Ｍｘｉｄ（ｈ−ｍｉｎ）でないならば、ステップＳ９５をスキップして、ステップＳ９６に移る。
【０２２９】
他方、ステップＳ９１で、ｈ−ｍｉｎ＝ｈ´でない場合、ステップＳ９４で、Ｍｘｉｄ（ｈ−ｍｉｎ）＝Ｍｘｉｄ（ｈ−ｍｉｎ＋１）であるならば、ステップＳ９５で、ｅ１＝ｅ１＋ＡＳ（ｘｉｄ）のＭｘｉｄ（ｈ−ｍｉｎ）番目の書き込みアクセス数とし、Ｍｘｉｄ（ｈ−ｍｉｎ）＝Ｍｘｉｄ（ｈ−ｍｉｎ＋１）でないならば、ステップＳ９５をスキップして、ステップＳ９６に移る。
【０２３０】
ステップＳ９６で、ＴＬ＝ＮＵＬＬでない場合、ステップＳ９７で、ＴＬ＝ＴＬ−ｘｉｄ、ｘｉｄ＝ＴＬの中の最初のトランザクション識別子として、ステップＳ８２に戻る。
【０２３１】
他方、ステップＳ９６で、ＴＬ＝ＮＵＬＬである場合、ステップＳ９８で、ｅ＞ｈ−ｍｉｎのＳ−Ｐｏｉｎｔの効果値−ｅ１であるならば、ステップＳ９９で、ｈ−ｍｉｎ番目のＳ−Ｐｏｉｎｔを設定して、処理を終了する。また、ステップＳ９８で、ｅ＞ｈ−ｍｉｎのＳ−Ｐｏｉｎｔの効果値−ｅ１でないならば、ステップＳ１００で、Ｓ−Ｐｏｉｎｔは設定せずに、処理を終了する。
【０２３２】
一例として、記録数Ｈ＝２の場合に、図１９のＴｉｍｅ２、Ｔｉｍｅ３、Ｔｉｍｅ４、Ｔｉｍｅ５の各時点におけるＳ−Ｐｏｉｎｔ管理表１２８の変化を図２４に示す。
【０２３３】
まず、図２４の（ａ）のＴｉｍｅ２の時点のＳ−Ｐｏｉｎｔは、すでに説明したように、図２０と同じである。
【０２３４】
次に、Ｔｉｍｅ３の時点で、Ｓ−Ｐｏｉｎｔ管理表１２８にある最後のＳ−Ｐｏｉｎｔ番号は２であり、記録数Ｈと同じであるので、新しいＳ−Ｐｏｉｎｔを設定するか否か判断する。新しいＳ−Ｐｏｉｎｔの設定で増える効果値ｅは、トランザクション３のＷＳＴ３（１）の書込みアクセス数の２である。１番目のＳ−Ｐｏｉｎｔを削除すると、トランザクションＴ２のＷＳＴ２（１）の書込みアクセス数は２番目のＳ−Ｐｏｉｎｔの効果値に足されるので、減る効果値は０である（２番目のＳ−Ｐｏｉｎｔを削除すると減る効果値も同様に０である）。したがって、Ｔｉｍｅ１で設定された１番目のＳ−Ｐｏｉｎｔは取り消されて新しいＳ−Ｐｏｉｎｔが設定され、図２４の（ｂ）のＳ−Ｐｏｉｎｔ管理表のように変わる。
【０２３５】
Ｔｉｍｅ４の時点で新しいＳ−Ｐｏｉｎｔの設定で増える効果値ｅは、トランザクションＴ２のＷＳＴ３（２）の書込みアクセス数の１である。１番目のＳ−Ｐｏｉｎｔを削除すると、トランザクションＴ１のＷＳＴ１（１）の書込みアクセス数＋トランザクションＴ１のＷＳＴ２（１）の書込みアクセス数（＝４）は２番目Ｓ−Ｐｏｉｎｔの効果値に足されるので、減る効果値はこの場合も０である（２番目のＳ−Ｐｏｉｎｔを削除すると減る効果値も同様に０である）。したがって、Ｔｉｍｅ３で設定された１番目のＳ−Ｐｏｉｎｔは取り消されて新しいＳ−Ｐｏｉｎｔが設定され、図２４の（ｃ）のＳ−Ｐｏｉｎｔ管理表のように変わる。
【０２３６】
最後に、Ｔｉｍｅ５の時点で新しいＳ−Ｐｏｉｎｔの設定で増える効果値ｅは、トランザクション２のＷＳＴ２（２）の書込みアクセス数の２である。１番目のＳ−Ｐｏｉｎｔを削除すると減る効果値は、トランザクションＴ３のＷＳＴ３（１）の書込みアクセス数（＝２）である。一方、２番目のＳ−Ｐｏｉｎｔを削除すると減る効果値は０である。したがって、Ｔｉｍｅ４で設定された２番目のＳ−Ｐｏｉｎｔは取り消されて新しいＳ−Ｐｏｉｎｔが設定され、図２４の（ｄ）のＳ−Ｐｏｉｎｔ管理表のように変わる。
【０２３７】
（４）トランザクションを中断後に再開するときの処理手順
トランザクションを中断後に再開するときの処理は、第１の構成例のリソースマネージャ１２の処理と同じである。
【０２３８】
（５）トランザクションをコミットするときの処理手順
トランザクションＴｉｄをコミットして終了するときは、第１の構成例のリソースマネージャ１２が行う手順と同様に、そのトランザクションが行ったデータの更新結果をファイルおよび他のトランザクションのドキュメントに反映させるために、Ｄ（Ｔｉｄ）をＤ−ｓｔと他のトランザクションのドキュメントＤにマージする処理と、トランザクション待ちグラフ１２２を調べてそのトランザクションの終了を待ちながら中断している他のトランザクションを再開させる処理とを行う。また、トランザクションリストとトランザクション待ちグラフ１２２からＴｉｄを削除し、トランザクションアクセス系列ＡＳ（Ｔｉｄ）とドキュメントＤ（Ｔｉｄ）も削除する。
【０２３９】
その他に、Ｓ−Ｐｏｉｎｔ管理表１２８からトランザクションＴｉｄのＷＳ欄を削除して、それにともなう効果値の変更を行う。各Ｓ−Ｐｏｉｎｔエントリーにおいて効果値に足されているトランザクションＴｉｄのＷＳ番目の書込みアクセスリストの書込みアクセス数を引けばよい。
【０２４０】
（６）トランザクションをアボートするときの処理手順
トランザクションＴｉｄをアボートして終了するときは、第１の構成例のリソースマネージャ１２が行う手順と同様に、そのトランザクションが行ったデータの更新結果を破棄するためにドキュメントＤ−ａｌｌを再作成する処理とトランザクション待ちグラフ１２２を調べて、そのトランザクションの終了を待ちながら待機している他のトランザクションを再開させる処理を行う。また、トランザクションリストとトランザクション待ちグラフ１２２からからＴｉｄを削除し、トランザクションアクセス系列ＡＳ（Ｔｉｄ）とドキュメントＤ（Ｔｉｄ）も削除する。ドキュメントＤ−ａｌｌを再作成は、ドキュメントＤ−ｓｔにトランザクションリストにあるすべてのトランザクションのドキュメントＤを重ねてマージすることで行う。
【０２４１】
その他に、トランザクションのコミット時と同様に、Ｓ−Ｐｏｉｎｔ管理表１２８の変更として、トランザクションＴｉｄのＷＳ欄の削除とそれにともなう効果値の変更を行う。Ｓ−Ｐｏｉｎｔ管理表１２８は効果値の高いＤ−ａｌｌの状態を記録管理するためのものなので、アボート時に最適なＳ−Ｐｏｉｎｔ設定のスケジュールを決定してそれに従ってＤ−ａｌｌの再作成を行うように実施することもできる。
【０２４２】
なお、以上の各機能は、ソフトウェアとして実現可能である。
また、本実施形態は、コンピュータに所定の手段を実行させるための（あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラムとして実施することもでき、該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０２４３】
なお、この発明の実施の形態で例示した構成は一例であって、それ以外の構成を排除する趣旨のものではなく、例示した構成の一部を他のもので置き換えたり、例示した構成の一部を省いたり、例示した構成に別の機能あるいは要素を付加したり、それらを組み合わせたりすることなどによって得られる別の構成も可能である。また、例示した構成と論理的に等価な別の構成、例示した構成と論理的に等価な部分を含む別の構成、例示した構成の要部と論理的に等価な別の構成なども可能である。また、例示した構成と同一もしくは類似の目的を達成する別の構成、例示した構成と同一もしくは類似の効果を奏する別の構成なども可能である。
また、この発明の実施の形態で例示した各種構成部分についての各種バリエーションは、適宜組み合わせて実施することが可能である。
また、この発明の実施の形態は、個別装置としての発明、関連を持つ２以上の装置についての発明、システム全体としての発明、個別装置内部の構成部分についての発明、またはそれらに対応する方法の発明等、種々の観点、段階、概念またはカテゴリに係る発明を包含・内在するものである。
従って、この発明の実施の形態に開示した内容からは、例示した構成に限定されることなく発明を抽出することができるものである。
【０２４４】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０２４５】
【発明の効果】
本発明によれば、階層型データを複数のトランザクションが並行してアクセスする場合にも、トランザクションの分離性を保証することができる、あるいは、その実行が直列化可能であるように処理の順序を制御することができるようになる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るトランザクション処理システムの構成例を示す図
【図２】ＸＭＬドキュメントの一例を示す図
【図３】ＸＭＬドキュメントの一例を示す図
【図４】ＸＭＬドキュメントの一例を示す図
【図５】ＸＭＬドキュメントの一例を示す図
【図６】トランザクション管理表の一例を示す図
【図７】同実施形態に係るリソースマネージャの構成例を示す図
【図８】トランザクションリストの一例を示す図
【図９】トランザクション待ちグラフの一例を示す図
【図１０】トランザクションアクセス系列の一例を示す図
【図１１】同実施形態におけるトランザクションの処理を開始するときの処理手順の一例を示すフローチャート
【図１２】同実施形態におけるトランザクションが読出しアクセスを要求したときの処理手順の一例を示すフローチャート
【図１３】同実施形態における関数Ｅｖａｌの処理の一例を示すフローチャート
【図１４】同実施形態におけるトランザクションが書込みアクセスを要求したときの処理手順の一例を示すフローチャート
【図１５】トランザクションアクセス系列の一例を示す図
【図１６】並行処理中のトランザクションの一例を示す図
【図１７】同実施形態に係るリソースマネージャの他の構成例を示す図
【図１８】トランザクションアクセス系列の一例を示す図
【図１９】並行処理中のトランザクションの一例を示す図
【図２０】Ｓ−Ｐｏｉｎｔ管理表の一例を示す図
【図２１】Ｓ−Ｐｏｉｎｔ管理表の一例を示す図
【図２２】同実施形態におけるトランザクションが書込みアクセスＷを要求したときのＷＲアクセス衝突の調査の処理手順の一例を示すフローチャート
【図２３】同実施形態におけるＳ−Ｐｏｉｎｔ設定の処理手順の一例を示すフローチャート
【図２４】Ｓ−Ｐｏｉｎｔ管理表の一例を示す図
【符号の説明】
１…トランザクション管理部、１１…トランザクションマネージャ、１１１…トランザクション管理表、１２…リソースマネージャ、３…ハードディスク、３１…ファイル、５…アプリケーションプログラム、１２１，１２５，１２７…ドキュメント、１２２…トランザクション待ちグラフ、１２３…トランザクションリスト、１２４…トランザクションアクセス系列、１２６…記録数、１２８…Ｓ−Ｐｏｉｎｔ管理表
【図１】
2004234567.tif 000003
【図２】
2004234567.tif 000004
【図３】
2004234567.tif 000005
【図４】
2004234567.tif 000006
【図５】
2004234567.tif 000007
【図６】
2004234567.tif 000008
【図７】
2004234567.tif 000009
【図８】
2004234567.tif 000010
【図９】
2004234567.tif 000011
【図１０】
2004234567.tif 000012
【図１１】
2004234567.tif 000013
【図１２】
2004234567.tif 000014
【図１３】
2004234567.tif 000015
【図１４】
2004234567.tif 000016
【図１５】
2004234567.tif 000017
【図１６】
2004234567.tif 000018
【図１７】
2004234567.tif 000019
【図１８】
2004234567.tif 000020
【図１９】
2004234567.tif 000021
【図２０】
2004234567.tif 000022
【図２１】
2004234567.tif 000023
【図２２】
2004234567.tif 000024
【図２３】
2004234567.tif 000025
【図２４】
2004234567.tif 000026