(57)【要約】【課題】更新前のデータを読み出し可能にすることと、必要な記憶容量を低減することとを両立させる。【解決手段】実施形態の端末装置は、記憶部と、管理部と、検知部と、参照付与部と、参照削除部と、判断部と、張替部と、削除部と、を有し、処理部が読み出したグラフエレメントが自トランザクションの開始以前に更新されていること、を検知して、実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないと判断部が判断したグラフエレメントに対する隣接グラフエレメントからのリンク情報を、アトミックに更新後のグラフエレメントへ張り替え、又は削除し、リンク情報が全て張り替え若しくは削除され、かつ、参照情報が付与されていないグラフエレメントを削除する。【選択図】図３
2014215914.tif 000002
【特許請求の範囲】
【請求項１】
グラフ構造データを構成するノード又はエッジを示すグラフエレメントを記憶する記憶部と、
前記記憶部が記憶するグラフエレメントに対して個別にデータを操作するトランザクションを実行する処理部の生成及び削除を行う管理部と、
前記処理部が読み出したグラフエレメントが、前記処理部が実行中のトランザクションの開始以前に更新されていることを検知する検知部と、
前記検知部が検知したグラフエレメントに参照情報を付与する参照付与部と、
前記参照付与部が参照情報を付与したグラフエレメントに対して操作したトランザクションの終了時に、操作されたグラフエレメントに付与されている参照情報を削除する参照削除部と、
グラフエレメントが、実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないことを判断する判断部と、
実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないと前記判断部が判断したグラフエレメントに対する隣接グラフエレメントからのリンク情報を、他のグラフエレメントへ張り替える、又は、前記リンク情報を削除する張替部と、
参照情報が付与されていないグラフエレメントであって、前記リンク情報が他のグラフエレメントに張り替えられた、又は、前記リンク情報が削除されたグラフエレメントを削除する削除部と、
を有する端末装置。
【請求項２】
前記判断部は、
前記参照削除部が参照情報を削除したことによって参照情報数が０になったときに、当該グラフエレメントに対する判断を行う
請求項１に記載の端末装置。
【請求項３】
前記判断部は、
予め定められた周期で、判断対象のグラフエレメントに対する判断を行う
請求項１に記載の端末装置。
【請求項４】
前記判断対象のグラフエレメントは、
前記処理部が更新確定後に、前記判断部に対して通知する更新前グラフエレメント、前記検知部が検知し前記判断部に対して通知するグラフエレメント、又は、参照付与部もしくは参照削除部が、それぞれ付与時、削除時に、前記判断部に対して通知するグラフエレメント、の少なくともいずれかである
請求項３に記載の端末装置。
【請求項５】
前記リンク情報が、エッジからノードへのリンク情報であり、かつ、ノードへの操作が削除であった場合に、前記張替部は、前記リンク情報を有するエッジを、削除対象として、前記判断部に通知する
請求項１に記載の端末装置。
【請求項６】
グラフ構造データを構成するノード又はエッジを示すグラフエレメントを記憶する記憶部を有する端末装置にデータを記憶させる情報処理方法であって、
前記記憶部が記憶するグラフエレメントに対して個別にデータを操作するトランザクションを実行する処理部の生成及び削除を行う管理する工程と、
前記処理部が読み出したグラフエレメントが、前記処理部が実行中のトランザクションの開始以前に更新されていることを検知する工程と、
検知したグラフエレメントに参照情報を付与する工程と、
参照情報を付与したグラフエレメントに対して操作したトランザクションの終了時に、操作されたグラフエレメントに付与されている参照情報を削除する工程と、
グラフエレメントが、実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないことを判断する工程と、
実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないと前記判断部が判断したグラフエレメントに対する隣接グラフエレメントからのリンク情報を、他のグラフエレメントへ張り替える、又は、前記リンク情報を削除する工程と、
参照情報が付与されていないグラフエレメントであって、前記リンク情報が他のグラフエレメントに張り替えられた、または、前記リンク情報が削除されたグラフエレメントを削除する工程と、
を含む情報処理方法。
【請求項７】
グラフ構造データを構成するノード又はエッジを示すグラフエレメントを記憶する記憶部を有する端末装置にデータを記憶させる情報処理プログラムであって、
前記記憶部が記憶するグラフエレメントに対して個別にデータを操作するトランザクションを実行する処理部の生成及び削除を行う管理するステップと、
前記処理部が読み出したグラフエレメントが、前記処理部が実行中のトランザクションの開始以前に更新されていることを検知するステップと、
検知したグラフエレメントに参照情報を付与するステップと、
参照情報を付与したグラフエレメントに対して操作したトランザクションの終了時に、操作されたグラフエレメントに付与されている参照情報を削除するステップと、
グラフエレメントが、実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないことを判断するステップと、
実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないと前記判断部が判断したグラフエレメントに対する隣接グラフエレメントからのリンク情報を、他のグラフエレメントへ張り替える、又は、前記リンク情報を削除するステップと、
参照情報が付与されていないグラフエレメントであって、前記リンク情報が他のグラフエレメントに張り替えられた、または、前記リンク情報が削除されたグラフエレメントを削除するステップと、
をコンピュータに実行させるための情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、端末装置、情報処理方法及び情報処理プログラムに関する。
【背景技術】
【０００２】
従来、関連情報の高速な探索を目的とするデータベースとして、例えばグラフデータベースが知られている。ここで、書き込みトランザクションによってデータが更新されてもデータ更新前に開始された読み出しトランザクションが更新後のデータを読まないようにするためには、更新前の旧データを保持しておく必要がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Neo  Technology,  “Neo4j  Reference  Manual  Chapter.12  Transaction  Management”,[online],[平成２５年４月１２日検索]、インターネット＜ＵＲＬ：http://docs.neo4j.org/chunked/stable/transactions.html＞
【非特許文献２】HyperGraphDB,  ,[online],[平成２５年４月１２日検索]、インターネット＜ＵＲＬ：http://scalahypergraph.blogspot.de/2012/12/a-shift-of-perspective-hacking.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の方法では、更新前のデータを読み出し可能に保持すると、必要な記憶容量が大きくなってしまうという問題があった。本発明の実施形態が解決しようとする課題は、更新前のデータを読み出し可能にすることと、必要な記憶容量を低減することとを両立させることができる端末装置、情報処理方法及び情報処理プログラムを提供することである。
【課題を解決するための手段】
【０００５】
実施形態の端末装置は、記憶部と、管理部と、検知部と、参照付与部と、参照削除部と、判断部と、張替部と、削除部と、を有する。記憶部は、グラフ構造データを構成するノード又はエッジを示すグラフエレメントを記憶する。管理部は、前記記憶部が記憶するグラフエレメントに対して個別にデータを操作するトランザクションを実行する処理部の生成及び削除を行う。検知部は、前記処理部が読み出したグラフエレメントが、前記処理部が実行中のトランザクションの開始以前に更新されていることを検知する。参照付与部は、前記検知部が検知したグラフエレメントに参照情報を付与する。参照削除部は、前記参照付与部が参照情報を付与したグラフエレメントに対して操作したトランザクションの終了時に、操作されたグラフエレメントに付与されている参照情報を削除する。判断部は、グラフエレメントが、実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないことを判断する。張替部は、実行中の最も古いトランザクションの開始以前に更新されていて、かつ、参照情報が付与されていないと前記判断部が判断したグラフエレメントに対する隣接グラフエレメントからのリンク情報を、他のグラフエレメントへ張り替える、又は、前記リンク情報を削除する。削除部は、参照情報が付与されていないグラフエレメントであって、前記リンク情報が他のグラフエレメントに張り替えられた、または、前記リンク情報が削除されたグラフエレメントを削除する。
【図面の簡単な説明】
【０００６】
【図１】グラフ構造データのノードに対するトランザクション分離レベルを示す図。
【図２】更新前データを保持したために、不要な参照が生じているグラフ構造データを示す図。
【図３】実施形態にかかる端末装置の構成を例示するブロック図。
【図４】操作情報の構造、及びエッジの張り替え前後の状態を示す図。
【図５】端末装置がｗｒｉｔｅトランザクションを実行する場合に行う処理例を示すアクティビティ図。
【図６】端末装置がｒｅａｄトランザクションを実行する場合に行う処理例を示すアクティビティ図。
【図７】端末装置がガベージコレクションを行う場合の処理例を示すアクティビティ図。
【図８】端末装置の動作（処理シーケンス）の具体例を示す図表。
【発明を実施するための形態】
【０００７】
（背景）
まず、実施形態にかかる端末装置を発明するに至った背景について説明する。図１は、グラフ構造データのノードに対するトランザクション分離レベルを示す図である。図１（ａ）は、Ｒｅａｄ  Ｃｏｍｍｉｔｔｅｄを示し、図１（ｂ）はＲｅｐｅａｔａｂｌｅ  Ｒｅａｄを示している。また、図１（ａ），（ｂ）のいずれにおいても、ノードＶ１，Ｖ２，Ｖ３を有するグラフ構造データに対し、書き込みトランザクション（ｗｒｉｔｅＴｘ）により、ノードＶ２がＶ２’に更新され、読み出しトランザクション（ｒｅａｄＴｘ）が実行されている。
【０００８】
図１（ａ）においては、Ｒｅａｄ  Ｃｏｍｍｉｔｔｅｄであるため、読み出しトランザクション（ｒｅａｄＴｘ）では、確定した最新データを常に読み出す。図１（ｂ）においては、Ｒｅｐｅａｔａｂｌｅ  Ｒｅａｄであるため、読み出しトランザクション（ｒｅａｄＴｘ）では、読み出し対象のデータを常に読み出す。
【０００９】
つまり、トランザクション分離レベルにより、待ち時間を減らすためにどれだけデータの一貫性を保つかが変えられる。
【００１０】
図２は、更新前データ（旧データ）を保持したために、不要な参照が生じているグラフ構造データを示す図である。図２においては、Ｒｅｐｅａｔａｂｌｅ  Ｒｅａｄとするために旧データ（Ｖ２）が保持されている。しかし、旧データが保持されていることにより、旧データ（Ｖ２）を経て更新データ（Ｖ２’）を参照してしまうことがある。この場合、読み出しが遅くなり、記憶容量も大きくなってしまう。そこで、更新前のデータを読み出し可能にすることと、必要な記憶容量を低減することとを両立させることが望まれている。
【００１１】
（実施形態）
図３は、実施形態にかかる端末装置１の構成を例示するブロック図である。端末装置１は、例えば、汎用のコンピュータなどによって実現される。即ち、端末装置１は、ＣＰＵ、記憶装置及び通信インターフェイスなどを備えたコンピュータとしての機能を有する。また、端末装置１は、サーバ装置として実現されてもよいし、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）、デジタルテレビ、ハードディスクレコーダ、スレートＰＣ又はスマートフォン等のデジタル機器として実現されてもよい。
【００１２】
図１に示すように、端末装置１は、記憶部１０、管理部１２、判断部１４、張替部１６及び削除部１８を有する。記憶部１０は、例えば単一又は複数のＨＤＤ（Hard  Disk  Drive）などによって構成される。また、記憶部１０は、他の不揮発性の補助記憶装置（ＳＳＤ、フラッシュメモリ、ＭＲＡＭ等）であってもよいし、主記憶装置であってもよい。管理部１２、判断部１４、張替部１６及び削除部１８は、ハードウェア回路、又はＣＰＵで実行するソフトウェアのいずれであってもよい。
【００１３】
記憶部１０は、グラフ構造データを構成するノード又はエッジを示すグラフエレメント（エレメント）を記憶する。また、記憶部１０は、データコンテナを有するデータエレメントを記憶するものであってもよい。例えば、データコンテナは、複数のデータの追加・更新・削除・取得（検索）を提供するデータ管理機構である。
【００１４】
管理部（トランザクション管理部）１２は、後述する処理部（トランザクション処理部）２０の生成及び削除などを行い、処理部２０の管理を行う。管理部１２は、処理部２０を生成する場合に、処理部２０を一意に識別する識別情報（トランザクションＩＤ）を付与する。また、管理部１２は、少なくとも処理部２０が生存する期間中には、付与したトランザクションＩＤと当該処理部２０への参照情報とを対にして保持する。また、管理部１２は、トランザクションＩＤをキーとした問い合わせに対し、該当トランザクションの状態や処理完了時間を返す。さらに、管理部１２は、同時実行されているトランザクションのうち、最も古いものを特定する。
【００１５】
処理部２０は、読出部２００、検知部２０２、参照付与部２０４、終了処理部２０６、操作記録部２０８及び参照削除部２１０を有する。また、処理部２０が実行するトランザクションは、２種類ある。ｗｒｉｔｅトランザクションは、読み出し及び操作（追加・更新・削除）を行うトランザクションである。ｒｅａｄトランザクションは、読み出しのみを行うトランザクションである。
【００１６】
ｗｒｉｔｅトランザクションは、記憶部１０に格納されているグラフ構造データに対する複数の操作（トランザクション）を、一貫性を保って実行する。このために、処理部２０は、実行状態、コミット準備状態、コミット完了状態、アボート状態及び終了状態の５つのいずれかの状態をとる。
【００１７】
実行状態は、ノード、エッジ、ノード・エッジ内のプロパティ、及びノード内の外向き及び内向きエッジに対する操作を行っている状態である。処理部２０は、管理部１２によって生成された時点で、この状態にある。一連の操作はコミットされておらず（確定されておらず）、ロールバックされ得る。処理部２０は、操作対象を取得する処理において、読出部２００、検知部２０２、参照付与部２０４によって削除可能な旧データの存在を検知し、一時的にデータが削除されないように保護する。
【００１８】
コミット準備状態は、一連の操作を終え、操作完了時間を取得した状態である。処理部２０は、操作開始時間から操作完了時間までの期間に行われた他のトランザクションによる変更をチェックし、実際にコミットしてよいか否かを決定する。
【００１９】
コミット完了状態は、チェックの結果がコミット可能な場合に、一連の操作を確定した状態である。ここで、処理部２０は、すべての操作情報４（図４を用いて後述）に操作完了時間を書き込み、削除データを記録する。さらに、処理部２０は、一連の操作のログを不揮発な記憶領域に書き込み、コミットデータの永続性を担保する処理を行ってもよい。処理部２０は、最後に終了する。
【００２０】
アボート状態は、チェックの結果がコミットできない場合、書き込みの競合が起こった場合、上位のアプリケーションなどからキャンセルが実行された場合などに、実行した操作をキャンセルした状態である。処理部２０は、後述する操作記録部２０８によって記録された操作情報４を全て消去し（ロールバックし）、終了する。
【００２１】
終了状態は、コミット完了状態及びアボート状態において操作に係る後処理を完了した状態である。処理部２０は、終了処理部２０６及び参照削除部２１０により、削除可能な旧データに対する保護を解除する。そして、処理部２０は、上記状態情報を保持する。
【００２２】
一方、ｒｅａｄトランザクションは、実行状態及び終了状態の２つのいずれかの状態をとる。
【００２３】
実行状態は、グラフ構造データに対する読み出しを行っている状態である。処理部２０は、読出部２００、検知部２０２、参照付与部２０４によって削除可能な旧データの存在を検知し、一時的にデータが削除されないように保護する。
【００２４】
終了状態は、対象グラフエレメントの読出しを全て終えた状態である。処理部２０は、終了処理部２０６及び参照削除部２１０により、削除可能な旧データに対する保護を解除する。
【００２５】
上述したように、処理部２０は、読出部２００、検知部２０２、参照付与部２０４、終了処理部２０６、操作記録部２０８及び参照削除部２１０を有する。
【００２６】
操作記録部２０８は、ｗｒｉｔｅトランザクションの実行状態において、実質的な操作処理を行う。例えば、操作記録部２０８は、操作箇所に操作情報４（図４参照）を記録し、同時に処理部２０内に操作箇所情報を記録する。まず、操作記録部２０８が行う操作は、基本的には、”追加”、”更新”又は”削除”のいずれかである。ただし、操作記録部２０８は、更新無しの操作を行うものであってもよい。
【００２７】
例えば、記憶部１０が記憶するデータがグラフ構造データである場合、操作記録部２０８は、ノード・エッジのレベルでは追加・削除を行い、ノード・エッジに属するコンテナデータ（プロパティ情報やノードが保持するエッジ情報）のレベルでは追加・更新・削除を行う。
【００２８】
また、操作記録部２０８は、”追加”の操作として、生成のみを行ってもよいし、生成と追記（Append）を行ってもよい。
【００２９】
操作記録部２０８は、実行状態において、後述する操作情報４を操作箇所に記録する。また、操作記録部２０８は、処理部２０内に操作箇所を示す操作箇所情報を記録する。操作箇所情報は、操作情報４を参照するためのポインタであり、例えば更新前データ（旧データ）へのポインタである。
【００３０】
読出部２００は、グラフエレメントを対象がなくなるまで読み出す。ここで、読出部２００は、読出しを行う場合にトランザクション開始時に取得した操作開始時間を用い、未来のデータ、旧データをスキップし、最新データを取得する。
【００３１】
端末装置１は、旧データのスキップ処理を行う場合に、削除対象データであるか否かの検知と必要な保護を行う。具体的には、処理部２０が以下の処理を行う。
【００３２】
読出部２００は、データの操作開始時間が、図４を用いて後述するデータ構造における登録時間と更新時間の間であれば、当該トランザクションにおける最新データとみなして取得する。また、読出部２００は、データの操作開始時間が登録時間よりも小さければ（早い時間であれば）当該トランザクションにとっては未来に生成されたデータとみなし、存在しないものとして扱う。また、読出部２００は、データの操作開始時間が更新時間よりも大きければ（遅い時間であれば）、当該トランザクションにとっては過去に削除された旧データとみなし、後述する検知部２０２に渡す。また、読出部２００は、トランザクションの競合判定を行い、競合が無い場合にはデータを取得し、競合がある場合には当該トランザクションはアボートする。この競合判定は、例えば、図４を用いて後述するエレメントのデータ構造において、第２領域４２にトランザクションＩＤが含まれている場合に、当該トランザクションの状態に応じて判定するものである。具体的には、アボート状態の場合には、読出部２００は、当該データを最新データとみなして取得する。実行状態の場合には、読出部２００は、データの一貫性を損なう原因となり得る競合が有るとみなしアボートする。コミット完了状態の場合には、読出部２００は、更新された（削除された）データとみなし、次データのチェックへ移行する。コミット準備状態の場合には、投機的実行を許すか否かによって読出部２００の挙動が変わる。投機的実行を許す場合は、読出部２００は、コミット完了状態の場合と同様、次データのチェックへ移行する。一方、投機的実行を許さない場合には、読出部２００は、競合が有るとみなしてアボートする。
【００３３】
検知部２０２は、旧データ（更新時間が設定されたデータ）を検知する。具体的には、検知部２０２は、読出部２００が読み出したデータが、データの操作開始時間より以前に更新されていることを検知することで、旧データを検知する。
【００３４】
参照付与部２０４は、検知部２０２が検知した削除対象の旧データに参照情報（図４参照）を付与し、旧データへのポインタを、トランザクション内に記録する。
【００３５】
終了処理部２０６は、参照付与部２０４が記録した旧データへのポインタを辿り、例えば参照削除部２１０が参照情報を、それぞれアトミックに削除すると、処理を終了する。終了処理部２０６は、参照情報の削除によって参照情報数が０になる場合に、後述する判断部１４を駆動し、ガベージコレクションを実行するように構成されてもよい。
【００３６】
判断部１４、張替部１６及び削除部１８は、ガベージコレクション（削除可能な旧データの消去）を行う機能ブロック（ガベージコレクション部）を構成する。
【００３７】
判断部１４は、同時実行中のトランザクションのうち、最も古いトランザクションの開始時間を取得し、削除判断対象の旧データの更新時間（すなわち削除時間）が開始時間よりも古ければ、削除可能と判断し、張替部１６に張替（更新の場合）、又は削除（削除の場合）を依頼する。
【００３８】
張替部１６は、判断部１４からの要求を受けて、旧データに対する隣接グラフエレメントからのリンク情報を、アトミックに更新後のグラフエレメントへ張り替える、又は、リンク情報の削除を行う。グラフエレメント（ノードあるいはエッジ）は、ノードは隣接エッジへの、エッジは隣接ノードへのリンク情報（図４の矢印。実態は、隣接エレメントが格納されたメモリ上又は不揮発記憶上のアドレス。すなわち、実装上は、ポインタや参照、ファイル上のオフセット値等で表現される）をそれぞれ有するが、張替部１６は、旧データが含まれる次データへのリンク情報を辿り、旧データを指している隣接エレメントのリンク情報を、次データへアトミックに変更する。
【００３９】
また、張替部１６は、次データが無い場合（すなわちデータの削除となる場合）、隣接エレメントがエッジ（旧データがノード）であれば、エッジの更新時間に旧データの更新時間を設定し、削除対象の旧データとして記録する。なお、このエッジは、旧データに向かうエッジ（旧データから見ると入力エッジ）であってもよいし、旧データから外に向かうエッジ（出力エッジ）であってもよい。入力エッジを辿る（すなわち逆向きに辿る）処理をサポートしない場合には、出力エッジはノードと一体とみなして同時に削除する方法を採ってもよい。ただし、入力エッジを辿る処理をサポートする場合には、ノードに入力エッジへのリンク情報（入力エッジコンテナ）が存在するので、例えば上述したように段階的に旧データとみなして、ガベージコレクションにエントリする。また、張替部１６は、隣接エレメントがノードの場合（旧データがエッジの場合）、旧データへのリンク情報をアトミックに削除する（具体的には、リンク先がないことを示す情報、例えば”ＮＵＬＬ”を設定するなど）。
【００４０】
削除部１８、張替部１６によって、隣接エレメント情報が全て除かれた旧データを実際に削除する。
【００４１】
次に、操作情報４について詳述する。図４は、操作情報４の構造、及びエッジの張り替え前後の状態を示す図である。図４に示すように、操作情報４は、第１領域４０、第２領域４２、第３領域４４、第４領域４５及び第５領域４６を有する。なお、データ（操作内容：値）は、第３領域４４に書込まれるものとする。また、データが更新される場合は、新たな操作情報４の第３領域４４にデータが書き込まれるものとする（追記型）。そして、データが読み出されることがなくなると、操作情報４は回収されるものとする。
【００４２】
第１領域４０は、例えばデータを第３領域４４に書き込むトランザクションの完了時に、操作記録部２０８が完了時間（登録時間）を書き込む領域である。ただし、第１領域４０は、トランザクションが実行されて完了するまでの間には、実行されているトランザクションを識別する識別情報（トランザクションＩＤ）が書き込まれる。
【００４３】
第２領域４２は、第３領域４４に書き込まれたデータを更新するトランザクションの完了時に、操作記録部２０８が更新時間を書き込む領域である。ただし、第２領域４２は、データを更新するトランザクションが完了するまでは、他の値が書き込まれる。例えば、第３領域４４に書き込まれたデータを更新するトランザクションが実行されていない場合、第２領域４２には、第３領域４４に書き込まれたデータが有効である旨を示す値（例えば”０”）が書き込まれる。また、第３領域４４に書き込まれたデータを更新するトランザクションが実行されて完了するまでの間には、実行されているトランザクションを識別する識別情報（トランザクションＩＤ）が書き込まれる。
【００４４】
第３領域４４は、上述したように、操作されるデータ（値）を操作記録部２０８が書き込む領域である。
【００４５】
第４領域４５は、参照情報へのポインタを操作記録部２０８（又は参照付与部２０４）が書き込む領域である。参照情報は、トランザクションＩＤ４５０及び次データへのポインタ４５２を有する。また、参照情報は、複数になり得るものである。
【００４６】
第５領域４６は、次データ（次に更新されるデータ）へのポインタを操作記録部２０８が書き込む領域である。なお、第５領域４６は、次データがない場合には、次データが無いことを示す情報（例えば”ＮＵＬＬ”）が書き込まれるものとする。
【００４７】
操作情報４は、エレメント等の旧データ及び最新データにおいて同じデータ構造となっている。例えば、操作記録部２０８は、グラフエレメントを追加する場合、グラフエレメントが属する上位コンテナの新規データエントリポイントの開始時間にトランザクションＩＤを記録し、データに新規グラフエレメントを記録する。ここで、操作記録部２０８は、第２領域４２には未更新（有効）を示す情報（例えば”０”）を書き込み、第５領域４６には次データがないことを示す情報（例えば”ＮＵＬＬ”）を初期値として書き込む。
【００４８】
また、操作記録部２０８は、コンテナデータを追加する場合、コンテナデータが属するデータコンテナの新規データエントリポイントの開始時間にトランザクションＩＤを記録し、データに新規コンテナデータを記録する。ここで、操作記録部２０８は、第２領域４２には未更新（有効）を示す情報（例えば”０”）を書き込み、第５領域４６には次データがないことを示す情報（例えば”ＮＵＬＬ”）を初期値として書き込む。
【００４９】
また、操作記録部２０８は、グラフエレメントを更新する場合、旧（更新対象）グラフエレメントの第２領域４２にトランザクションＩＤを記録し、旧（更新対象）グラフエレメントの第５領域４６に更新データエレメントのアドレスを記録する。そして、操作記録部２０８は、更新データエレメントの第１領域４０にトランザクションＩＤを記録し、更新データエレメントの第３領域４４に更新データエレメントを記録する。
【００５０】
また、操作記録部２０８は、コンテナデータを更新する場合、旧（更新対象）コンテナデータの第２領域４２にトランザクションＩＤを記録し、旧（更新対象）コンテナデータの第５領域４６に更新コンテナデータのアドレスを記録する。そして、操作記録部２０８は、更新コンテナデータの第１領域４０にトランザクションＩＤを記録し、更新コンテナデータの第３領域４４に更新コンテナデータを記録する。
【００５１】
また、操作記録部２０８は、グラフエレメントを削除する場合、旧（削除対象）グラフエレメントの第２領域４２にトランザクションＩＤを記録する。
【００５２】
また、操作記録部２０８は、コンテナデータを削除する場合、旧（更新対象）コンテナデータの第２領域４２にトランザクションＩＤを記録する。
【００５３】
なお、上記のトランザクションＩＤは、コミット完了状態になると、操作完了時間に置き換えられる。一方、アボート状態になると、トランザクションＩＤは初期値（ＮＵＬＬ等）に戻される。ここで、トランザクションＩＤが初期値であるものは、操作情報４ではなく、更新対象となり得る最新グラフエレメント、又は最新コンテナデータであるとする。また、操作情報４は、追加・更新・削除の操作種別を残す領域を設けられてもよいし、削除フラグを立てる領域が設けられてもよい。
【００５４】
次に、端末装置１の動作について説明する。図５は、端末装置１がｗｒｉｔｅトランザクションを実行する場合に行う処理例を示すアクティビティ図である。まず、処理部２０は、トランザクションの操作開始時間を取得する（Ｓ１００）。
【００５５】
次に、処理部２０は、トランザクションの操作対象を取得する（Ｓ１０２）。ここで、処理部２０は、旧データをスキップし、最新データを取得するために、Ｓ１００の処理で取得した操作開始時間を用いる。
【００５６】
処理部２０は、操作対象がない場合にはトランザクションをコミット準備状態へ遷移させる（Ｓ１１２）。また、処理部２０は、操作対象がある場合には、競合の有無を検知する（Ｓ１０４）。
【００５７】
処理部２０は、競合があることを検知した場合にはトランザクションをアボート状態へ遷移させる（Ｓ１０６）。
【００５８】
処理部２０は、競合がない場合には操作情報４を操作箇所に記録し（Ｓ１０８）、操作箇所を処理部２０内に記録する（Ｓ１１０）。
【００５９】
次に、処理部２０は、トランザクションの操作完了時間を取得する（Ｓ１１４）。ここで、処理部２０は、トランザクションがコミット準備状態に遷移した時間を操作完了時間とみなす。処理部２０は、操作情報４を取得する（Ｓ１１６）。処理部２０は、操作情報４がない場合にはトランザクションをコミット完了状態へ遷移させ（Ｓ１２４）、操作情報４がある場合には競合の有無を検知する（Ｓ１１８）。
【００６０】
処理部２０は、競合がなく、待機もない場合には、新たに操作情報４を取得する（Ｓ１１６）。また、処理部２０は、競合がなく、待機がある場合には、他トランザクションのコミット完了状態を待機する（Ｓ１２２）。また、処理部２０は、競合がある場合には、トランザクションをアボート状態へ遷移させる（Ｓ１２０）。
【００６１】
処理部２０は、他トランザクションのコミット完了状態を待機している間に、アボートを受信すると、トランザクションをアボート状態へ遷移させる（Ｓ１２０）。また、処理部２０は、他トランザクションのコミット完了状態を待機している間に、コミット完了を受信すると、新たに操作情報４を取得する（Ｓ１１６）。
【００６２】
処理部２０は、コミット完了状態へ遷移（Ｓ１２４）した後、新たな操作情報４を取得する（Ｓ１２６）。以降の処理は、ガベージコレクションのための登録への処理となる。処理部２０は、操作情報４がある場合には操作完了時間の書き込みを行う（Ｓ１２８）。処理部２０は、操作情報４がない場合には終了処理を行う（Ｓ１３２）。
【００６３】
処理部２０は、操作完了時間の書き込みが削除である場合には、削除データを記録する（Ｓ１３０）。なお、処理部２０は、更新時間の書き込みがあり、次データへのポインタが”ＮＵＬＬ”である場合に、削除であるとみなす。処理部２０は、操作完了時間の書き込みが追加・更新である場合には、新たな操作情報４を取得する（Ｓ１２６）。
【００６４】
図６は、端末装置１がｒｅａｄトランザクションを実行する場合に行う処理例を示すアクティビティ図である。まず、処理部２０は、読出開始時間を取得する（Ｓ２００）。次に、読出部２００は、読出しを行う（Ｓ２０２）。読出部２００は、読出し対象がない場合には、終了処理部２０６に対して終了状態へ遷移するように通知を行う。
【００６５】
検知部２０２は、読出し対象があり、旧データがある場合には、旧データの更新時間と、自トランザクションの読出開始時間を比較する。検知部２０２は、読出し対象があり、旧データがない場合には、読出部２００に対して読出しを行うように通知を行う。
【００６６】
また、検知部２０２は、自読出開始時間が旧データの更新時間よりも大きい場合（遅い場合）、参照付与部２０４に対して通知を行う。また、検知部２０２は、自読出開始時間が旧データの更新時間よりも小さい場合、読出部２００に対して読出しを行うように通知を行う。
【００６７】
参照付与部２０４は、検知部２０２から通知を受け取ると、旧データに参照情報を付与する（Ｓ２０６）。また、参照付与部２０４は、旧データへのポインタをトランザクション内に記録する（Ｓ２０８）。
【００６８】
終了処理部２０６は、読出部２００から通知を受け取ると、トランザクションを終了状態へ遷移させる（Ｓ２１０）。また、終了処理部２０６は、旧データへのポインタを取得し（Ｓ２１２）、ポインタがある場合には参照削除部２１０に対して通知を行い、ポインタがない場合には処理を終了する。
【００６９】
参照削除部２１０は、終了処理部２０６が旧データへのポインタを取得した場合、参照付与部２０４が付与した参照情報を削除し（Ｓ２１４）、終了処理部２０６に対して新たに旧データへのポインタを取得するように通知を行う。
【００７０】
なお、図６に示したＳ２００〜Ｓ２０８の処理は、図５に示したＳ１０２（操作対象取得）の処理の詳細を示すものとなっている。また、図６に示したＳ２１０〜Ｓ２１４の処理は、図５に示したＳ１３２（終了処理）の詳細を示すものとなっている。
【００７１】
図７は、端末装置１がガベージコレクションを行う場合の処理例を示すアクティビティ図である。まず、処理部２０は、旧データを取得する（Ｓ３００）。処理部２０は、旧データがない場合には処理を終了する。また、処理部２０は、旧データがある場合には判断部１４に対して通知を行う。
【００７２】
判断部１４は、処理部２０から通知を受け取ると、同時実行中のトランザクションのうち、最も古いトランザクションの開始時間を取得する（Ｓ３０２）。次に、判断部１４は、旧データの更新時間が取得した開始時間以上である場合には、処理部２０に対して旧データを取得するように通知を行う。また、判断部１４は、旧データの更新時間が取得した開始時間未満である場合には、参照情報を取得する（Ｓ３０４）。
【００７３】
判断部１４は、参照情報がある場合には、処理部２０に対して旧データを取得するように通知を行う。また、判断部１４は、参照データがない場合には、張替部１６に対して通知を行う。
【００７４】
張替部１６は、判断部１４から通知を受け取った場合には、参照情報がノード又はエッジのいずれに対するものであるかを判定する。張替部１６は、参照情報がノードに対するものである場合には、当該ノードに接続するエッジの、当該ノードを指すリンク情報をアトミックに張り替え又は削除する（Ｓ３０６）。張替部１６は、残ノードがある場合には判断部１４に対して参照情報を取得するように通知を行い、残ノードがない場合には削除部１８に対して通知を行う。
【００７５】
また、張替部１６は、参照情報がエッジに対するものである場合には、当該エッジに接続するノードの、当該エッジを指すリンク情報をアトミックに張り替え又は削除する（Ｓ３０８）。張替部１６は、残エッジがある場合には、判断部１４に対して参照情報を取得するように通知を行い、残エッジがない場合には削除部１８に対して通知を行う。
【００７６】
削除部１８は、張替部１６から通知を受け取ると、旧データを削除し、新たな旧データを取得するように処理部２０に対して通知を行う（Ｓ３１０）。
【００７７】
次に、端末装置１の動作の具体例について説明する。図８は、端末装置１の動作（処理シーケンス）の具体例を示す図表である。
【００７８】
図８に示すように、まず、００：００：００に完了するｗｒｉｔｅトランザクション１（ｗｒｉｔｅＴｘ（１））によって（Ａ）→（Ｂ）→（Ｃ）というシンプルなグラフデータが生成される。
【００７９】
（Ｂ）は、００：００：０２〜００：００：０５に実行されるｗｒｉｔｅＴｘ（３）により、（Ｂ）’に変更される。
【００８０】
この場合におけるｒｅａｄトランザクション２,４,５,６の動作は以下のとおりである。
【００８１】
ｗｒｉｔｅＴｘ（３）の開始前に実行されたｒｅａｄＴｘ（２）は、（Ｂ）’を読まない。
【００８２】
ｗｒｉｔｅＴｘ（３）の完了前に実行されたｒｅａｄＴｘ（４）も、（Ｂ）’を読まない。
【００８３】
００：００：０５以降には、旧データとなった（Ｂ）は、最低限、ｒｅａｄＴｘ（４）の終了時間００：００：１５までは削除できない。これは、判断部１４が、その時点で実行中のトランザクションの内、最も古いトランザクションの開始時間を取得し（Ｓ３０２）、これ（００：００：０３）が、旧データの更新時間（００：００：０５）よりも小さいので削除対象と判断しないことによって保証される。
【００８４】
００：００：０５以降に開始されたｒｅａｄＴｘ（５）は、（Ｂ）と（Ｂ）’の双方を読むが、このとき、自読出開始時間（００：００：０８）が、旧データの更新時間（００：００：０５）よりも大きいため、（Ｂ）に参照情報を付与する。
【００８５】
ｒｅａｄＴｘ（５）は、終了時（００：００：１８）に参照情報を削除するが、この時間よりも前にｒｅａｄＴｘ（６）が（Ｂ）を読んでいたら、このｒｅａｄＴｘ（６）の付与する参照情報が残っていることになる。したがって、この場合、ｒｅａｄＴｘ（５）は、判断部１４を駆動しない（（Ｂ）の削除を実行しない）。
【００８６】
ｒｅａｄＴｘ（６）が（Ｂ）を読むのが００：００：１８より後になる場合、ｒｅａｄＴｘ（５）の終了時には、（Ｂ）の参照情報が０になるので、ｒｅａｄＴｘ（６）は判断部１４を駆動して、（Ｂ）の削除を実行する。したがって、この場合、ｒｅａｄＴｘ（６）は、（Ａ）→（Ｂ）’→（Ｃ）と読むことになる。
【００８７】
一方、ｒｅａｄＴｘ（６）が、００：００：１８より前に（Ｂ）を読んだ場合、（Ｂ）に参照情報を付与する。このため、ｒｅａｄＴｘ（５）は、終了時に参照情報が残っているので、（Ｂ）の回収処理（判断部１４）を駆動できない。この場合、ｒｅａｄＴｘ（６）の終了時（００：００：２５）に参照情報が０になるので、ｒｅａｄＴｘ（６）は判断部１４を駆動して、（Ｂ）の削除を実行する。
【００８８】
このように、実施形態にかかる端末装置１は、同時実行中の最も古いトランザクションの開始以前に更新されていることを検知して、参照情報が付与されていないグラフエレメントが示すノードに接続されたエッジのリンク情報をアトミックに張り替え、全てのエッジのリンク情報が更新後のノードを指すように変更したうえで、参照情報が付与されていないグラフエレメントを削除するので、更新前のデータを読み出し可能にすることと、必要な記憶容量を低減することとを両立させることができる。すなわち、Ｒｅｐｅａｔａｂｌｅ  ｒｅａｄを担保するために必要なメモリ使用量のオーバーヘッドも削減することが可能である。
【００８９】
なお、上記実施形態において、判断部１４の駆動は、終了処理部によって行われる構成となっているが、判断部１４は、定期的に実行されるように構成されてもよい。例えば、処理部２０が、コミット完了状態において旧データを判断部１４に登録し、この登録されたデータを、判断部１４が定期的に判断するように構成されてもよい。同様に、この検知部２０２が検知したデータを判断部１４に登録するようにしてもよいし、参照付与部２０４や参照削除部２１０が、それぞれ付与や削除をおこなった旧データを登録するようにしてもよい。
【００９０】
本実施形態の端末装置１で実行される情報処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【００９１】
また、本実施形態の端末装置１で実行される情報処理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。
【００９２】
また、本発明のいくつかの実施形態を複数の組み合わせによって説明したが、これらの実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。これら新規の実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９３】
１  端末装置
１０  記憶部
１２  管理部
１４  判断部
１６  張替部
１８  削除部
２０  処理部
２００  読出部
２０２  検知部
２０４  参照付与部
２０６  終了処理部
２０８  操作記録部
２１０  参照削除部
４  操作情報
４０  第１領域
４２  第２領域
４４  第３領域
４５  第４領域
４５０  トランザクションＩＤ
４５２  次データへのポインタ
４６  第５領域
【図１】
2014215914.tif 000003
【図２】
2014215914.tif 000004
【図３】
2014215914.tif 000005
【図４】
2014215914.tif 000006
【図５】
2014215914.tif 000007
【図６】
2014215914.tif 000008
【図７】
2014215914.tif 000009
【図８】
2014215914.tif 000010