(57)【要約】【課題】  テーブルに対して行われる変更を効率的に識別して格納すること。【解決手段】  基本テーブルは、削除マーカ及び挿入マーカを用いて走査される。削除マーカは、ステートメントを実行する前にトランザクションの一部として基本テーブルにコミットされた最終の変更を識別し、挿入マーカは、ステートメントの実行中にトランザクションの一部として基本テーブルにコミットされた最終の変更を識別する。削除マーカの走査結果は、デルタテーブルに格納されている削除を用いてフィルタリングされ、削除テーブルにはフィルタリングされた行が投入される。挿入マーカの走査結果は、デルタテーブルに格納されている挿入を用いてフィルタリングされ、挿入テーブルにはフィルタリングされた行が投入される。【選択図】  図４
2004348744.tif 000002
【特許請求の範囲】
【請求項１】
トランザクションの一部としてのステートメントによって基本テーブルから削除された行を識別する識別方法であって、
前記ステートメントの実行の前に前記トランザクションの一部として変更された最後の行を識別するステップと、
前記最後の行に対応する削除マーカを設定するステップと、
前記削除マーカを用いて前記基本テーブルを走査するステップと、
前記走査の結果をフィルタリングするステップと
を有することを特徴とする識別方法。
【請求項２】
前記最後の行に対応する削除マーカを設定するステップは、
前記削除マーカのトランザクション識別子を、前記トランザクションの識別子に設定するステップと、
前記削除マーカのシーケンス番号を、前記最後の行に割り当てられたシーケンス番号に設定するステップと
を有することを特徴とする請求項１に記載の識別方法。
【請求項３】
前記削除マーカを用いて前記基本テーブルを走査するステップは、
（ａ）前記行のトランザクション識別子が、前記削除マーカのトランザクション識別子に等しいか否かを判定するステップと、
（ｂ）前記両識別子が等しい場合に、前記行を読み出すステップと、
（ｃ）前記両識別子が等しくない場合に、
前記行のシーケンス番号が、前記削除マーカのシーケンス番号以下であるか否かを判定するステップと、
前記シーケンス番号以下である場合に、前記行を読み出すステップと、
前記シーケンス番号以下でない場合に、
前記行の前のバージョンを取り出すステップと、
前記ステップ（ａ）に戻り、前記行の前のバージョンに対して処理を続けるステップと
を有することを特徴とする請求項１に記載の識別方法。
【請求項４】
前記行の前のバージョンを取り出すステップは、バージョン記憶装置から前記行の前のバージョンを取り出すステップを有し、前記前のバージョンは、前記バージョン記憶装置において、前記行のトランザクション識別子及び前記シーケンス番号によって識別されることを特徴とする請求項３に記載の識別方法。
【請求項５】
前記フィルタリングした結果を削除テーブルに投入するステップを有することを特徴とする請求項１に記載の識別方法。
【請求項６】
トランザクションの一部としてのステートメントによって基本テーブルに挿入された行を識別する識別方法であって、
前記ステートメントの実行の前に前記トランザクションの一部として変更された最後の行を識別するステップと、
前記最後の行に対応する挿入マーカを設定するステップと、
前記挿入マーカを用いて前記基本テーブルを走査するステップと、
前記走査の結果をフィルタリングするステップと
を有することを特徴とする識別方法。
【請求項７】
前記最後の行に対応する挿入マーカを設定するステップは、
前記挿入マーカのトランザクション識別子を、前記トランザクションの識別子に設定するステップと、
前記挿入マーカのシーケンス番号を、前記最後の行に割り当てられたシーケンス番号に設定するステップと
を有することを特徴とする請求項６に記載の識別方法。
【請求項８】
前記挿入マーカを用いて前記基本テーブルを走査するステップは、
（ａ）前記行のトランザクション識別子が、前記挿入マーカのトランザクション識別子に等しいか否かを判定するステップと、
（ｂ）前記両識別子が等しい場合に、前記行を読み出すステップと、
（ｃ）前記両識別子が等しくない場合に、
前記行の前記シーケンス番号が、前記挿入マーカのシーケンス番号以下であるか否かを判定するステップと、
前記シーケンス番号以下である場合に、前記行を読み出すステップと、
前記シーケンス番号以下でない場合に、
前記行の前のバージョンを取り出すステップと、
前記ステップ（ａ）に戻り、前記行の前のバージョンに対して処理を続けるステップと
を有することを特徴とする請求項６に記載の識別方法。
【請求項９】
前記行の前のバージョンを取り出すステップは、バージョン記憶装置から前記行の前のバージョンを取り出すステップを有し、前記前のバージョンは、前記バージョン記憶装置において、前記行のトランザクション識別子及び前記シーケンス番号によって識別されることを特徴とする請求項８に記載の識別方法。
【請求項１０】
前記フィルタリングした結果を挿入テーブルに投入するステップを有することを特徴とする請求項６に記載の識別方法。
【請求項１１】
トランザクションの一部としてのステートメントによって基本テーブルから削除された行を識別する識別システムであって、
前記基本テーブルとバージョン記憶装置とデルタテーブルと削除テーブルとを格納するデータ記憶装置と、
コンピュータ実行可能命令を実行するように動作可能なプロセッサと、
コンピュータ実行可能命令を格納したメモリとを備え、
前記命令は、
前記ステートメントの実行の前に前記トランザクションの一部として変更された最後の行を識別するステップと、
前記最後の行に対応する削除マーカを設定するステップと、
前記削除マーカを用いて前記基本テーブルを走査するステップと、
前記走査の結果をフィルタリングするステップと
を有することを特徴とする識別システム。
【請求項１２】
前記基本テーブルは、行の現在のバージョンを格納するためのものであることを特徴とする請求項１１に記載の識別システム。
【請求項１３】
前記バージョン記憶装置は、行の前のバージョンを格納するためのものであることを特徴とする請求項１１に記載の識別システム。
【請求項１４】
前記デルタテーブルは、前記ステートメントによって削除された行を識別するためのものであることを特徴とする請求項１１に記載の識別システム。
【請求項１５】
前記削除テーブルは、前記ステートメントによって削除された行を格納するためのものであることを特徴とする請求項１１に記載の識別システム。
【請求項１６】
前記最後の行に対応する削除マーカを設定するステップを実施する前記コンピュータ実行可能命令は、
前記削除マーカのトランザクション識別子を、前記トランザクションの識別子に設定するステップと、
前記削除マーカのシーケンス番号を、前記最後の行に割り当てられたシーケンス番号に設定するステップと
を有することを特徴とする請求項１１に記載の識別システム。
【請求項１７】
前記削除マーカを用いて前記基本テーブルを走査するステップを実施する前記コンピュータ実行可能命令は、
（ａ）前記行のトランザクション識別子が、前記削除マーカのトランザクション識別子に等しいか否かを判定するステップと、
（ｂ）前記両識別子が等しい場合に、前記行を読み出すステップと、
（ｃ）前記両識別子が等しくない場合に、
前記行のシーケンス番号が、前記削除マーカのシーケンス番号以下であるか否かを判定するステップと、
前記シーケンス番号以下である場合に、前記行を読み出すステップと、
前記シーケンス番号以下でない場合に、
前記行の前のバージョンを取り出すステップと、
前記ステップ（ａ）に戻り、前記行の前のバージョンに対して処理を続けるステップと
を有することを特徴とする請求項１１に記載の識別システム。
【請求項１８】
前記行の前のバージョンは、前記バージョン記憶装置において、前記行のトランザクション識別子及び前記シーケンス番号によって識別されることを特徴とする請求項１７に記載の識別システム。
【請求項１９】
前記メモリは、前記フィルタリングした結果を前記削除テーブルに投入するコンピュータ実行可能命令を有することを特徴とする請求項１１に記載の識別システム。
【請求項２０】
トランザクションの一部としてのステートメントによって基本テーブルに挿入された行を識別する識別システムであって、
前記基本テーブルとバージョン記憶装置とデルタテーブルと挿入テーブルとを格納するデータ記憶装置と、
コンピュータ実行可能命令を実行するように動作可能なプロセッサと、
コンピュータ実行可能命令を格納したメモリとを備え、
前記命令は、
前記ステートメントの実行の前に前記トランザクションの一部として変更された最後の行を識別するステップと、
前記最後の行に対応する挿入マーカを設定するステップと、
前記挿入マーカを用いて前記基本テーブルを走査するステップと、
前記走査の結果をフィルタリングするステップと
を有することを特徴とする識別システム。
【請求項２１】
前記基本テーブルは、行の現在のバージョンを格納するためのものであることを特徴とする請求項２０に記載の識別システム。
【請求項２２】
前記バージョン記憶装置は、行の前のバージョンを格納するためのものであることを特徴とする請求項２０に記載の識別システム。
【請求項２３】
前記デルタテーブルは、前記ステートメントによって挿入された行を識別するためのものであることを特徴とする請求項２０に記載の識別システム。
【請求項２４】
前記挿入テーブルは、前記ステートメントによって挿入された行を格納するためのものであることを特徴とする請求項２０に記載の識別システム。
【請求項２５】
前記最後の行に対応する挿入マーカを設定するステップを実施する前記コンピュータ実行可能命令は、
前記挿入マーカのトランザクション識別子を、前記トランザクションの識別子に設定するステップと、
前記挿入マーカのシーケンス番号を、前記最後の行に割り当てられたシーケンス番号に設定するステップと
を有することを特徴とする請求項２０に記載の識別システム。
【請求項２６】
前記挿入マーカを用いて前記基本テーブルを走査するステップを実施する前記コンピュータ実行可能命令は、
（ａ）前記行のトランザクション識別子が、前記挿入マーカのトランザクション識別子に等しいか否かを判定するステップと、
（ｂ）前記両識別子が等しい場合に、前記行を読み出すステップと、
（ｃ）前記両識別子が等しくない場合に、
前記行のシーケンス番号が、前記挿入マーカのシーケンス番号以下であるか否かを判定するステップと、
前記シーケンス番号以下である場合に、前記行を読み出すステップと、
前記シーケンス番号以下でない場合に、
前記行の前のバージョンを取り出すステップと、
前記ステップ（ａ）に戻り、前記行の前のバージョンに対して処理を続けるステップと
を有することを特徴とする請求項２０に記載の識別システム。
【請求項２７】
前記行の前のバージョンは、前記バージョン記憶装置において、前記行のトランザクション識別子及び前記シーケンス番号によって識別されることを特徴とする請求項２６に記載の識別システム。
【請求項２８】
前記メモリは、前記フィルタリングした結果を前記挿入テーブルに投入するコンピュータ実行可能命令を有することを特徴とする請求項２０に記載の識別システム。
【請求項２９】
ステートメントの実行の前にトランザクションの一部として変更された最後の行を識別するステップと、
前記最後の行に対応する削除マーカを設定するステップと、
前記削除マーカを用いて基本テーブルを走査するステップと、
前記走査の結果をフィルタリングするステップと
を実施するコンピュータ可読命令を格納していることを特徴とするコンピュータ読取可能な記録媒体。
【請求項３０】
前記最後の行に対応する削除マーカを設定するステップは、
前記削除マーカのトランザクション識別子を、前記トランザクションの識別子に設定するステップと、
前記削除マーカのシーケンス番号を、前記最後の行に割り当てられたシーケンス番号に設定するステップと
を有することを特徴とする請求項２９に記載のコンピュータ読取可能な記録媒体。
【請求項３１】
前記削除マーカを用いて基本テーブルを走査するステップは、
（ａ）前記行のトランザクション識別子が、前記削除マーカのトランザクション識別子に等しいか否かを判定するステップと、
（ｂ）前記両識別子が等しい場合に、前記行を読み出すステップと、
（ｃ）前記両識別子が等しくない場合に、
前記行のシーケンス番号が、前記削除マーカのシーケンス番号以下であるか否かを判定するステップと、
前記シーケンス番号以下である場合に、前記行を読み出すステップと、
前記シーケンス番号以下でない場合に、
前記行の前のバージョンを取り出すステップと、
前記ステップ（ａ）に戻り、前記行の前のバージョンに対して処理を続けるステップと
を有することを特徴とする請求項２９に記載のコンピュータ読取可能な記録媒体。
【請求項３２】
前記行の前のバージョンを取り出すステップは、バージョン記憶装置から前記行の前のバージョンを取り出すステップを有し、前記前のバージョンは、前記バージョン記憶装置において、前記行のトランザクション識別子及び前記シーケンス番号によって識別されることを特徴とする請求項３１に記載のコンピュータ読取可能な記録媒体。
【請求項３３】
前記フィルタリングした結果を前記削除テーブルに投入するコンピュータ可読命令を有することを特徴とする請求項２９に記載のコンピュータ読取可能な記録媒体。
【請求項３４】
ステートメントの実行の前にトランザクションの一部として変更された最後の行を識別するステップと、
前記最後の行に対応する挿入マーカを設定するステップと、
前記挿入マーカを用いて基本テーブルを走査するステップと、
前記走査の結果をフィルタリングするステップと
を実施するコンピュータ可読命令を格納していることを特徴とするコンピュータ読取可能な記録媒体。
【請求項３５】
前記最後の行に対応する挿入マーカを設定するステップは、
前記挿入マーカのトランザクション識別子を、前記トランザクションの識別子に設定するステップと、
前記挿入マーカのシーケンス番号を、前記最後の行に割り当てられたシーケンス番号に設定するステップと
を有することを特徴とする請求項３４に記載のコンピュータ読取可能な記録媒体。
【請求項３６】
前記挿入マーカを用いて基本テーブルを走査するステップは、
（ａ）前記行のトランザクション識別子が、前記挿入マーカのトランザクション識別子に等しいか否かを判定するステップと、
（ｂ）前記両識別子が等しい場合に、前記行を読み出すステップと、
（ｃ）前記両識別子が等しくない場合に、
前記行の前記シーケンス番号が、前記挿入マーカの前記シーケンス番号以下であるか否かを判定するステップと、
前記シーケンス番号以下である場合に、前記行を読み出すステップと、
前記シーケンス番号以下でない場合に、
前記行の前のバージョンを取り出すステップと、
前記ステップ（ａ）に戻り、前記行の前のバージョンに対して処理を続けるステップと
を有することを特徴とする請求項３４に記載のコンピュータ読取可能な記録媒体。
【請求項３７】
前記行の前のバージョンを取り出すステップは、バージョン記憶装置から前記行の前のバージョンを取り出すステップを有し、前記前のバージョンは、前記バージョン記憶装置において、前記行のトランザクション識別子及び前記シーケンス番号によって識別されることを特徴とする請求項３６に記載のコンピュータ読取可能な記録媒体。
【請求項３８】
前記フィルタリングした結果を前記挿入テーブルに投入するコンピュータ可読命令を有することを特徴とする請求項３４に記載のコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース管理の分野を対象とし、テーブルに対して行われる変更を識別する識別方法及びそのシステムに関し、より詳細には、基本テーブルからの削除及び基本テーブルへの挿入される行（ｒｏｗ）の識別を行なう識別方法及びそのシステム並びにこのような変更の格納を行なう記録媒体に関する。
【背景技術】
【０００２】
データベース管理システム（ＤＢＭＳ）では、データの現在のバージョンは、概して「基本」テーブルに格納される。基本テーブル中の各行は、変更することができる。このような変更は、基本テーブル中の行の削除でも、挿入でも、修正でもよい。修正とは、行の前のバージョンの削除及び行の現在のバージョンの挿入である。行が変更されると、その変更は、１組の一時的な、メモリに常駐する「遷移（ｔｒａｎｓｉｔｉｏｎ）」テーブルに格納することができる。このような１組の遷移テーブルは、概して自動的に作成され、ＤＢＭＳによって管理される。遷移テーブルの組は、基本テーブルから削除された行を格納する「削除」テーブルと、基本テーブルに挿入された行を格納する「挿入」テーブルとを含むことができる。行が修正されると、行の前のバージョンは削除テーブルに格納され、行の現在のバージョンは挿入テーブルに格納される。
【０００３】
遷移テーブルにより、ＤＢＭＳは、変更の影響を調べ、トリガ動作の条件を設定することが可能になる。具体的には、遷移テーブルは、テーブル間の参照整合性を拡大し、ある特定のビューの基礎をなす基本テーブル中のデータを変更し、違いを検出し、検出した違いに基づいて動作を起こし、また、変更の前と後でのテーブルの状態の違いを見つけ、違いに基づいて動作を起こす。
【０００４】
従来のＤＢＭＳでは、基本テーブル中の行が変更される前にそのような行を完全にコピーすることによって、遷移テーブルに投入を行うことができる。したがって、例えば、行が削除されると、その行の前のバージョンがコピーされ、このコピーは次いで、削除テーブルに格納される。行をコピーすることの欠点は、特にコピーされた行が、例えば、コードや画像など大規模フィールドのバイナリラージオブジェクト（ＢＬＯＢ）データを含む場合、このようなコピーを生成して格納するのにコストがかかることである。
【０００５】
遷移テーブルに投入を行う他の方法は、ログファイルを走査することである。ただし、このようなログの走査を用いることの欠点は、ＢＬＯＢデータはしばしば、ログの走査の使用を実装するのには複雑すぎることである。さらに、ログの走査は、ディスク入出力（ＩＯ）の使用を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、当該分野において、テーブルに対して行われる変更を効率的に識別して格納するシステム及び方法が必要である。このようなシステム及び方法は、大量のＢＬＯＢデータを含む行を低コストで識別し、適切な遷移テーブルに格納できるようにすることが望ましい。このようなシステム及び方法は、ディスクＩＯを非効率に使用することなく動作することがさらに望ましい。
【０００７】
本発明は、このような問題に鑑みてなされたもので、その目的とするところは、テーブルに対して行われる変更を効率的に識別して格納するようにした識別方法及びそのシステムを提供することにある。
【課題を解決するための手段】
【０００８】
したがって、本発明は、テーブルに対して行われる変更を識別して格納するシステム及びその方法を開示する。データの現在のバージョンは、基本テーブルに格納される。基本テーブル中の各行の前のバージョンは、バージョン記憶装置に格納される。デルタテーブルが、基本テーブルに対して行われた変更の一次キーを識別し、このような変更が挿入であるかまたは削除であるか指定する。１組の遷移テーブルが、基本テーブルに対して行われた各変更を格納する。遷移テーブルの組は、基本テーブルから削除された行を格納する削除テーブルと、基本テーブルに挿入された行を格納する挿入テーブルとを含むことができる。
【０００９】
行が基本テーブルにコミットされると、その行には、好ましくはトランザクション（ｔｒａｎｓａｃｔｉｏｎ）識別子（ＸＩＤ）及びシーケンス番号（ＳＥＱ）が割り当てられる。ＸＩＤは、変更が行われるトランザクションの一義的な識別子である。ＳＥＱは、好ましくはトランザクションにおいて行われる各変更に割り当てられる、単調に増加し続ける値である。バージョン記憶装置内にある行の前のバージョンは、基本テーブル中の行の現在のバージョンのＸＩＤ及びＳＥＱによって識別することができる。
【００１０】
遷移テーブルには、トランザクションの一部としてのステートメント（ｓｔａｔｅｍｅｎｔ）によって変更された行を識別することによって、投入を行うことができる。基本テーブルは、削除マーカ及び挿入マーカを用いて走査される。削除マーカは、ステートメントを実行する前にトランザクションの一部として基本テーブルにコミットされた最終の変更を識別し、挿入マーカは、ステートメントの実行中にトランザクションの一部として基本テーブルにコミットされた最終の変更を識別する。削除マーカの走査の結果は、デルタテーブルに格納されている削除を用いてフィルタリングされ、削除テーブルには、フィルタリングされた行が投入される。挿入走査の結果は、デルタテーブルに格納されている挿入を用いてフィルタリングされ、挿入テーブルには、フィルタリングされた行が投入される。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照して本発明の実施の態様について説明する。
なお、本明細書に示す説明は例示のために過ぎず、本発明の技術的範囲を限定するものではない。また、明細書中、同じ構成要素については、同一の符号を付してある。
【００１２】
＜コンピュータ環境＞
図１は、本発明に係る識別システムの一実施形態を説明するためのブロック図で、実施形態及び／またはその部分を組み込むことができる汎用コンピュータシステムを示すブロック図である。
【００１３】
以下の説明では、本発明及び／またはその一部を実装することができる適切な計算機環境の簡潔かつ全体的な説明を提供することを意図している。また、クライアントワークステーションやサーバなどのコンピュータによって実行されるプログラムモジュールなどのコンピュータ実行可能命令という一般的な状況において本発明を説明する。プログラムモジュールは、特定のタスクを実施し、または特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、構成要素、データ構造などを備えている。さらに、本発明及び／またはその一部は、可搬型装置、マルチプロセッサシステム、マイクロプロセッサベースの家電製品またはプログラム可能な家電製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなど他のコンピュータシステム構成と共に実施できる。本発明は、通信ネットワークを介してリンクされるリモート処理装置によって特定のタスクが実施される分散型計算機環境でも実施することができる。分散型計算機環境では、プログラムモジュールは、ローカル及びリモートメモリ記憶装置の両方に置くことができる。
【００１４】
図１に示すように、例示的な汎用計算機システムは、従来のパーソナルコンピュータ１２０などを備え、このコンピュータ１２０は、処理装置１２１とシステムメモリ１２２とシステムメモリなど様々なシステム構成要素を処理装置１２１に結合するシステムバス１２３とを備えている。システムバス１２３は、様々なバスアーキテクチャのどれをも使用するメモリバスまたはメモリコントローラ、周辺バス、及びローカルバスなどいくつかのタイプのバス構造のいずれでもよい。システムメモリは、読出し専用メモリ（ＲＯＭ）１２４及びランダムアクセスメモリ（ＲＡＭ）１２５を備えている。基本入出力システム１２６（ＢＩＯＳ）は、例えば、起動中にパーソナルコンピュータ１２０内部の要素間の情報の転送を助ける基本ルーチンを備え、ＲＯＭ１２４に格納されている。
【００１５】
パーソナルコンピュータ１２０は、ハードディスク（図示せず）からの読出し及びそこへの書込みを行うハードディスクドライブ１２７と、取外し可能磁気ディスク１２９からの読出しまたはそこへの書込みを行う磁気ディスクドライブ１２８と、例えば、ＣＤ−ＲＯＭや他の光学媒体などの取外し可能光ディスク１３１からの読出しまたはそこへの書込みを行う光ディスクドライブ１３０をさらに備えている。ハードディスクドライブ１２７と磁気ディスクドライブ１２８と光ディスクドライブ１３０は、それぞれハードディスクドライブインターフェース１３２と磁気ディスクドライブインターフェース１３３と光ドライブインターフェース１３４によって、システムバス１２３に接続されている。こうしたドライブ及びそれに関連するコンピュータ読取可能な記録媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、及び他のデータの不揮発性記憶装置をパーソナルコンピュータ１２０に提供する。
【００１６】
本明細書で説明する例示的な環境では、ハードディスクと、取外し可能な磁気ディスク１２９と、取外し可能な光ディスク１３１を使用するが、コンピュータによるアクセスが可能なデータを格納することができる、コンピュータ可読な他のタイプの媒体も、例示的な動作環境において使うことができる。このような他のタイプの媒体には、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）などがある。
【００１７】
オペレーティングシステム１３５と、１つまたは複数のアプリケーションプログラム１３６と、他のプログラムモジュール１３７と、プログラムデータ１３８などいくつかのプログラムモジュールを、ハードディスクと、磁気ディスク１２９と、光ディスク１３１と、ＲＯＭ１２４またはＲＡＭ１２５に格納することができる。ユーザは、キーボード１４０などの入力装置、及びマウスなどの指示装置１４２を介して、コマンド及び情報をパーソナルコンピュータ１２０に入力することができる。他の入力装置（図示せず）には、マイクロホン、ジョイスティック、ゲーム用パッド、衛星パラボラアンテナ、スキャナなどがあり得る。こうした及び他の入力装置は、しばしば、システムバスに結合されたシリアルポートインターフェース１４６を介して処理装置１２１に接続されるが、他のインターフェース、例えば、並列ポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）によって接続することもできる。モニタ１４７または他のタイプの表示装置も、映像アダプタ１４８などのインターフェースを介してシステムバス１２３に接続される。モニタ１４７に加えて、パーソナルコンピュータは通常、他の周辺出力装置（図示せず）、例えば、スピーカ及びプリンタを含む。図１の例示的なシステムは、ホストアダプタ１５５と小型計算機システムインターフェース（ＳＣＳＩ）バス１５６とＳＣＳＩバス１５６に接続された外部記憶装置１６２も備えている。
【００１８】
パーソナルコンピュータ１２０は、リモートコンピュータ１４９など１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク接続された環境において動作することができる。リモートコンピュータ１４９は、他のパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置または他の共通ネットワークノードでよく、通常、パーソナルコンピュータ１２０に関連して上述した要素の多くまたはすべてを含むが、図１にはメモリ記憶装置１５０のみを示した。図１に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１５１及びワイドエリアネットワーク（ＷＡＮ）１５２を含む。このようなネットワーク環境は、会社、企業規模のコンピュータネットワーク、イントラネット及びインターネットにおいてよく見られる。
【００１９】
ＬＡＮネットワーク環境において使われる場合、パーソナルコンピュータ１２０は、ネットワークインターフェースまたはアダプタ１５３を介してＬＡＮ１５１に接続される。ＷＡＮネットワーク環境において使われる場合、パーソナルコンピュータ１２０は、通常、モデム１５４、または、例えば、インターネットなどのワイドエリアネットワーク１５２を介した通信を確立する他の手段を備えている。モデム１５４は、内部にあっても外部にあってもよく、シリアルポートインターフェース１４６を介してシステムバス１２３に接続される。ネットワーク接続された環境では、パーソナルコンピュータ１２０に関連して図示したプログラムモジュールまたはその一部は、リモートメモリ記憶装置に格納することができる。図示したネットワーク接続は例示的なものであり、コンピュータ間の通信リンクを確立する他の手段も使うことができる。
【００２０】
＜本発明の例示的なシステム及び方法＞
データの現在のバージョンは、基本テーブルに格納される。基本テーブル中の各行の前のバージョンは、バージョン記憶装置に格納される。デルタテーブルが、基本テーブルに対して行われた変更の一次キーを識別し、このような変更が挿入であるかまたは削除であるか指定する。１組の遷移テーブルが、基本テーブルに対して行われた各変更を格納する。遷移テーブルの組は、基本テーブルから削除された行を格納する削除テーブルと、基本テーブルに挿入された行を格納する挿入テーブルとを備えている。
【００２１】
図２は、本発明による例示的なデータベース管理システム（ＤＢＭＳ）を示すブロック図である。ＤＢＭＳ２００は、基本テーブル２１０と、バージョン記憶装置２２０と、デルタテーブル２３０と、削除テーブル２４０及び挿入テーブル２４２を含む１組の遷移テーブル２４０，２４２とを備えている。
【００２２】
データの現在のバージョンは、基本テーブル２１０に格納される。ただ１つの基本テーブル２１０を示してあるが、ＤＢＭＳ２００は、任意の数の追加の基本テーブルを備えることができる。基本テーブル２１０は、好ましくは、データ列、トランザクション識別子（ＸＩＤ）列、及びシーケンス番号（ＳＥＱ）列を備えている。データ列は、実質的なデータを格納する。ＸＩＤ列は、各行の現在のバージョンがコミットされたトランザクションの識別子を格納する。ＳＥＱ列は、トランザクションにおいて変更が行われたシーケンスを識別する。ＳＥＱは、好ましくは、ＤＢＭＳ２００によって自動的に維持される、単調に増加し続ける値である。ＤＢＭＳ２００内のすべての基本テーブルがＸＩＤ列及びＳＥＱ列を含む必要があるわけではない。望ましくは、本発明による、識別された変更を格納する基本テーブルが、このようなＸＩＤ列及びＳＥＱ列を含む必要がある。例示的な基本テーブル２１０を、以下の表１に示す。
【００２３】
【表１】
2004348744.tif 000003
【００２４】
表１は、顧客に関する実質的なデータを格納するデータ列「顧客ＩＤ」及び「名前」を備えている。行１０１〜１０５は、トランザクション「３０」の一部としてコミットされた。行１０３は、削除された記録であるゴースト記録である。したがって、行１０３はプレースホルダ（ｐｌａｃｅｈｏｌｄｅｒ）として表１に残っているが、行１０３に対応する「名前」データはない。
【００２５】
バージョン記憶装置２２０は、基本テーブル２１０中の行の前のバージョンを格納する。バージョン記憶装置２２０内にある行は、それと置き換わった行のバージョンのＸＩＤ及びＳＥＱによって指標づけされる。したがって、現在の各行のＸＩＤ値及びＳＥＱ値は、前のバージョンへのポインタとして働く。バージョン記憶装置２２０内の行を示す例示的なテーブルを、以下の表２に示す。
【００２６】
【表２】
2004348744.tif 000004
【００２７】
表２は、各行の変更ＸＩＤ値及び変更ＳＥＱ値を識別する列「変更ＸＩＤ」及び「変更ＳＥＱ」によって指標づけされる。例えば、表１に示す行１０１の現在のバージョンには、ＸＩＤ３０及びＳＥＱ１が割り当てられる。現在のバージョンと置き換わった行１０１の１つ前のバージョンは、表２において、変更ＸＩＤ３０及び変更ＳＥＱ１を有して示される。１つ前のバージョンには、ＸＩＤ２０及びＳＥＱ１が割り当てられており、したがって、トランザクション２０の一部としてコミットされた。１つ前のバージョンと置き換わった行１０１の２つ前のバージョンは、表２において変更ＸＩＤ２０及び変更ＳＥＱ１を有して示される。２つ前のバージョンにはＸＩＤ１０及びＳＥＱ１が割り当てられており、したがって、トランザクション１０の一部としてコミットされた。
【００２８】
図３ａ〜図３ｅは、本発明による例示的な基本テーブル及びバージョン記憶装置を示すブロック図で、基本テーブル２１０及びバージョン記憶装置２２０にある、行の例示的なバージョンのブロック図である。例えば、図３ａに示すように、行１０１の現在のバージョンは、基本テーブル２１０に格納されている。現在のバージョンには、ＸＩＤ３０及びＳＥＱ１が割り当てられ、これは、バージョン記憶装置２２０に格納されている、行の１つ前のバージョンをポイント（ｐｏｉｎｔ）する。行の１つ前のバージョンにはＸＩＤ２０及びＳＥＱ１が割り当てられ、これは、やはりバージョン記憶装置２２０に格納されている、行の２つ前のバージョンをポイントする。
【００２９】
また、図３ｂに示すように、行１０２の現在のバージョンは、基本テーブル２１０に格納される。現在のバージョンには、ＸＩＤ３０及びＳＥＱ２が割り当てられ、これは、バージョン記憶装置２２０に格納されている、行の１つ前のバージョンをポイントする。
【００３０】
また、図３ｃに示すように、ゴースト記録である行１０３の現在のバージョンは、基本テーブル２１０に格納される。ゴースト記録は、実質的なデータを含まない削除された記録のためのプレースホルダである。ゴースト記録には、ＸＩＤ３０及びＳＥＱ３が割り当てられ、これは、バージョン記憶装置２２０に格納されている、行の１つ前のバージョンをポイントする。
【００３１】
図３ｄ及び図３ｅにそれぞれ示すように、行１０４及び１０５の現在のバージョンは、基本テーブル２１０に格納される。このような行は新しく挿入されるので、バージョン記憶装置２２０にはこうした行の前のバージョンがない。他の実施形態では、所定の一義的なＳＥＱ値を有する一義的なマーカを、行が新しく挿入されたことを示すのに使うことができる。このような一義的なマーカは、行の前のバージョンがバージョン記憶装置２２０に格納されていないことを示す。
【００３２】
ＤＢＭＳ２００が破損した後にバージョン記憶装置２２０が存続する必要はない。したがって、バージョン記憶装置２２０は、ＤＢＭＳ２００の一時的なデータベースに格納することができる。行の前のバージョンは、好ましくは、このような行にアクセスするクエリを実行することができる間のみ格納され、したがって、前のバージョンは、バージョン記憶装置２２０から周期的に削除される。
【００３３】
バージョン記憶装置２２０は、例えば、ｂツリーやｂ＋ツリーなどのツリー構造に従って編成することができる。ｂツリーに対するキーは、好ましくは各変更のＸＩＤ及びＳＥＱである。ｂツリーに従って編成された行は、そのＸＩＤ値及びＳＥＱ値に従って行全体を削除することができる。例えば、ＸＩＤ及びＳＥＱの指定された範囲内のＸＩＤ及びＳＥＱを有する変更は、全体を削除することができる。行は、トランザクション中の単一のＤＭＬステートメントに続いて、あるいは完全なトランザクションまたは一群のトランザクションに続いて削除することができる。
【００３４】
あるいは、バージョン記憶装置２２０は、各行の前のバージョンを識別するための、物理行ＩＤまたはディスクアドレスを使って編成することができる。このような行ＩＤ方式では、好ましくはＸＩＤ及びＳＥＱの他に、各行の前のバージョンの行ＩＤが格納される。前のバージョンは好ましくは、「ヒープ（ｈｅａｐ）」と呼ばれる１組のディスクページに格納される。新しいヒープは、指定された期間に生成することができる。例えば、ユーザは、６０秒ごとに新しいヒープを生成するよう要求することができる。ヒープは、ヒープに格納されているバージョンを生成したすべてのトランザクションが完了した後で削除することができる。
【００３５】
バージョン記憶装置２２０の編成に加え、このようなツリー構造及びヒープは、基本テーブル２１０を編成するのに使うことができる。例えば、基本テーブル２１０中の行がバイナリラージオブジェクト（ＢＬＯＢ）データを含む場合、このようなＢＬＯＢデータは、フラグメントに分解し、その行に対応する別個のＢＬＯＢ基本テーブルに格納することができる。このようなＢＬＯＢ基本テーブルは、ＤＢＭＳ２００によって維持されるツリー構造またはヒープに従って編成することができる。
【００３６】
デルタテーブル２３０は、基本テーブル２１０中で行われる変更を識別する。例示的なデルタテーブルは、好ましくは２つの列を有する。すなわち、基本テーブル２１０の一次キーの列、及び対応する変更が挿入であるかまたは削除であるかを示す変更列である。
【００３７】
デルタテーブル２３０は、好ましくは、対応するデータ操作言語（ＤＭＬ）ステートメントによって行われた変更を識別する。例えば、ＤＭＬステートメントが変更｛ＸＩＤ３０、ＳＥＱ２｝から｛ＸＩＤ３０、ＳＥＱ４｝を行った場合、対応するデルタテーブル２３０は、好ましくは以下の表３に示すように生成される。
【００３８】
【表３】
2004348744.tif 000005
【００３９】
表３は、変更｛ＸＩＤ３０、ＳＥＱ２｝から｛ＸＩＤ３０、ＳＥＱ４｝の一次キーの値を備え、対応する変更が挿入であるかまたは削除であるか示す。表３は、行１０２が修正されたことを示し、この修正は、削除及び挿入の両方を含む。表３はまた、行１０３が削除され、行１０４が挿入されたことを示す。
【００４０】
遷移テーブル２４０及び２４２は、基本テーブル２１０に対して行われた変更を格納する。削除テーブル２４０は、基本テーブル２１０から削除された行を格納する。上述した例示的なＤＭＬステートメントによって削除された行を示す例示的な削除テーブル２４０を、以下の表４に示す。
【００４１】
【表４】
2004348744.tif 000006
【００４２】
挿入テーブル２４２は、基本テーブル２１０に挿入された行を格納する。上述した例示的なＤＭＬステートメントによって挿入された行を示す例示的な挿入テーブル２４２を、以下の表５に示す。
【００４３】
【表５】
2004348744.tif 000007
【００４４】
遷移テーブル２４０及び２４２には、トランザクションの一部としてのステートメントによって変更された行を識別することによって、投入が行われる。基本テーブル２１０は、削除マーカ及び挿入マーカを用いて走査される。削除マーカは、ステートメントの実行の前にトランザクションの一部として基本テーブル２１０にコミットされた最終の変更を識別し、挿入マーカは、ステートメントの実行中に基本テーブル２１０にコミットされた最終の変更を識別する。削除マーカによる走査の結果は、デルタテーブル２３０に格納されている削除を用いてフィルタリングされ、削除テーブル２４０には、フィルタリングされた行が投入される。挿入走査の結果は、デルタテーブル２３０に格納されている挿入を用いてフィルタリングされ、挿入テーブル２４２には、フィルタリングされた行が投入される。
【００４５】
図４は、変更を識別して格納する例示的な方法を説明するためのフローチャートを示す図である。まず、ステップ４１０で、削除マーカ及び挿入マーカのＸＩＤが、トランザクションの識別子に設定される。例えば、上述した例示的なステートメントはトランザクション「３０」の一部として実行されており、したがって、削除マーカ及び挿入マーカのＸＩＤは３０に設定される。
【００４６】
次に、ステップ４１２で、削除マーカのＳＥＱが、トランザクションの一部としてコミットされた最終の変更のＳＥＱに設定される。例えば、例示的なステートメントの実行の前にトランザクション「３０」の一部としてコミットされた最終の変更には、ＳＥＱ「１」が割り当てられた。したがって、削除マーカは、｛（ＸＩＤ３０、ＳＥＱ１）｝に設定される。
【００４７】
次に、ステップ４１４で、ＤＢＭＳ２００は、データ操作言語（ＤＭＬ）ステートメントを実行する。このステートメントは、基本テーブル２１０中の行を挿入し、削除し、かつ／または修正するのに使うことができる。例えば、上述した例示的なステートメントは、行１０２を修正し、行１０３を削除し、行１０４を挿入した。
【００４８】
ステートメントがある特定の行を変更すると、その行の現在のバージョンは、バージョン記憶装置２２０に格納されている、行の前のバージョンを伴って、基本テーブル２１０に格納される。行の現在のバージョンは、基本テーブル２１０にコミットされると、行の前のバージョンへのポインタとして働くＸＩＤ値及びＳＥＱ値を割り当てられる。各変更に割り当てられるＸＩＤ値は、ステップ４１０で設定された、トランザクションに対するＸＩＤ値である。ＳＥＱ値は、トランザクションにおいて変更が行われたシーケンスを識別する。ＳＥＱは好ましくは、ＤＢＭＳ２００によって自動的に維持される、単調に増加し続ける値である。例えば、例示的なステートメントによって変更された第１の行、つまり、行１０２に割り当てられたＸＩＤ値及びＳＥＱ値は、上述した表１に示した｛（ＸＩＤ３０、ＳＥＱ２）｝である。次の変更された行、つまり、行１０３には｛（ＸＩＤ３０、ＳＥＱ３）｝が割り当てられる。次の変更された行、つまり、行１０４には｛（ＸＩＤ３０、ＳＥＱ４）｝が割り当てられる。
【００４９】
次に、ステップ４１６で、挿入マーカのＳＥＱが、ステートメントの実行中にトランザクションの一部としてコミットされた最終の変更のＳＥＱに設定される。例えば、ステートメントの実行中にトランザクション「３０」の一部として変更された最後の行は行１０４であり、ＳＥＱ「４」が割り当てられた。したがって、挿入マーカは、｛（ＸＩＤ３０、ＳＥＱ４）｝に設定される。
【００５０】
次に、ステップ４１８で、基本テーブル２１０が、削除マーカを用いて走査される。基本テーブル２１０を走査する例示的な方法は、図５を参照して後で詳しく説明する。このような走査を表１に対して削除マーカ｛（ＸＩＤ３０、ＳＥＱ１）｝を用いて実施した結果を、以下の表６に示す。
【００５１】
【表６】
2004348744.tif 000008
【００５２】
次に、ステップ４２０で、削除走査の結果が、デルタテーブル２３０に格納されている削除を用いてフィルタリングされ、ステップ４２２で、削除テーブル２４０に、フィルタリングされた行が投入される。例えば、表６中の行が、表３に格納されている削除を用いてフィルタリングされると、削除テーブル２４０には、以下の表７に示すように投入が行われる。
【００５３】
【表７】
2004348744.tif 000009
【００５４】
次に、ステップ４２４で、基本テーブル２１０が、挿入マーカを用いて走査される。基本テーブル２１０を走査する例示的な方法は、後で図５を参照して詳しく説明する。このような走査を表１に対して削除マーカ｛（ＸＩＤ３０、ＳＥＱ４）｝を用いて実施した結果を、以下の表８に示す。
【００５５】
【表８】
2004348744.tif 000010
【００５６】
ステップ４２６で、挿入走査の結果が、デルタテーブル２３０に格納されている挿入を用いてフィルタリングされ、ステップ４２８で、挿入テーブル２４２に、フィルタリングされた行が投入される。例えば、表８中の行が、表５に格納されている挿入を用いてフィルタリングされると、挿入テーブル２４２には、以下の表９に示すように投入が行われる。
【００５７】
【表９】
2004348744.tif 000011
【００５８】
したがって、図４に関連して上述した処理は、ＤＭＬステートメントによって行われた変更を識別し、遷移テーブル２４０〜２４２にこのような変更を投入する。この処理は、挿入マーカ及び削除マーカを用いて基本テーブル２１０を走査することによって、このような変更が識別されることを可能にする。
【００５９】
図５は、テーブルを走査する例示的な方法を説明するためのフローチャートを示す図である。走査は、マーカのＳＥＱにおいてまたはその前に起こる、異なるトランザクションの一部として行われた変更、及び同じトランザクションの一部として行われた変更を読み出す。
【００６０】
図５に示すように、ステップ５１０で、行のＸＩＤがマーカのＸＩＤに等しいか否かを判定する。等しくない場合、ステップ５１６で、その行が読み出される。等しい場合、ステップ５１２で、その行のＳＥＱがマーカのＳＥＱ以下であるか否かを判定する。マーカのＳＥＱ以下である場合、ステップ５１６で、その行が読み出される。マーカのＳＥＱ以下でない場合、ステップ５１４で、その行の前のバージョンがバージョン記憶装置２２０から取り出され、方法はステップ５１０に戻る。
【００６１】
図４に関連して上述したように、行は読み出された後、走査結果に追加され、デルタテーブル２３０に格納されている行を用いてフィルタリングされる。削除走査によって読み出された行がデルタテーブル２３０中にも削除として記載されている場合、その行は削除テーブル２４０に格納される。挿入走査によって読み出された行がデルタテーブル２３０中にも挿入として記載されている場合、その行は挿入テーブル２４２に格納される。図４及び図５に関連して上述したテーブルは、例えば、メモリやデータベースなど、どの記憶装置にも格納することができる。
【００６２】
以上、本発明を図面を参照して好ましい実施形態について説明したが、本発明から逸脱することなく、本発明の同じ機能を実施するために、他の類似の実施形態を用いることも、説明した実施形態に修正及び追加を行うこともできる。したがって、本発明は、どの１つの実施形態にも限定されるべきではなく、特許請求の範囲による広さ及び技術的範囲内で解釈されるべきである。
【図面の簡単な説明】
【００６３】
【図１】本発明に係る識別システムの一実施形態を説明するためのブロック図である。
【図２】本発明による例示的なデータベース管理システムを示すブロック図である。
【図３ａ】本発明による例示的な基本テーブル及びバージョン記憶装置を示すブロック図（その１）である。
【図３ｂ】本発明による例示的な基本テーブル及びバージョン記憶装置を示すブロック図（その２）である。
【図３ｃ】本発明による例示的な基本テーブル及びバージョン記憶装置を示すブロック図（その３）である。
【図３ｄ】本発明による例示的な基本テーブル及びバージョン記憶装置を示すブロック図（その４）である。
【図３ｅ】本発明による例示的な基本テーブル及びバージョン記憶装置を示すブロック図（その５）である。
【図４】変更を識別して格納する例示的な方法を説明するためのフローチャートを示す図である。
【図５】テーブルを走査する例示的な方法を説明するためのフローチャートを示す図である。
【符号の説明】
【００６４】
１２０  パーソナルコンピュータ
１２１  処理装置
１２２  システムメモリ
１２３  システムバス
１２４  読出し専用メモリ（ＲＯＭ）
１２５  ランダムアクセスメモリ（ＲＡＭ）
１２６  基本入出力システム（ＢＩＯＳ）
１２７  ハードディスクドライブ
１２８  磁気ディスクドライブ
１２９  磁気ディスク
１３０  光ディスクドライブ
１３１  光ディスク
１３２  ハードディスクドライブインターフェース
１３３  磁気ディスクドライブインターフェース
１３４  光ドライブインターフェース
１３５  オペレーティングシステム
１３６  アプリケーションプログラム
１３７  他のプログラムモジュール
１３８  プログラムデータ
１４０  キーボード
１４２  指示装置
１４６  シリアルポートインターフェース
１４７  モニタ
１４８  映像アダプタ
１４９  リモートコンピュータ
１５０  メモリ記憶装置
１５１  ローカルエリアネットワーク（ＬＡＮ）
１５２  ワイドエリアネットワーク（ＷＡＮ）
１５３  ネットワークインターフェース、ネットワークアダプタ
１５４  モデム
１５５  ホストアダプタ
１５６  小型計算機システムインターフェース（ＳＣＳＩ）バス
１６２  外部記憶装置
２００  データベース管理システム（ＤＢＭＳ）
２１０  基本テーブル
２２０  バージョン記憶装置
２３０  デルタテーブル
２４０  遷移テーブル、削除テーブル
２４２  遷移テーブル、挿入テーブル
【図１】
2004348744.tif 000012
【図２】
2004348744.tif 000013
【図３ａ】
2004348744.tif 000014
【図３ｂ】
2004348744.tif 000015
【図３ｃ】
2004348744.tif 000016
【図３ｄ】
2004348744.tif 000017
【図３ｅ】
2004348744.tif 000018
【図４】
2004348744.tif 000019
【図５】
2004348744.tif 000020