JPH03123946A

JPH03123946A - データベースの排他制御方法

Info

Publication number: JPH03123946A
Application number: JP1262810A
Authority: JP
Inventors: Ryoji Kataoka; 良治片岡; Tetsuji Sato; 哲司佐藤; Hideaki Takeda; 武田　英昭; Ushio Inoue; 潮井上
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1989-10-07
Filing date: 1989-10-07
Publication date: 1991-05-27

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明はデータベースの排他制御方法に係り、詳しくは
、同一のデータベースを複数のトランザクションから頻
繁にアクセスする業務、特に大址のデータの参照のみを
行うトランザクションと複数のデータ参照してその一部
を更新するトランザクションとが混在して頻繁に発生す
る業務において、トランザクションの一貫性を保ちつつ
、高い同時実行性を実現するデータベースの排他制御方
法に関するものである。

〔従来の技術〕

データベース処理装置の分野において、同一のデータベ
ースを複数のトランザクションで同時に処理しながら、
全てのトランザクションの一貫性を保証する排他制御技
術は、トランザクションの同時実行性を高め、処理能力
の高いデータベース管理機構を実現する上で重要な技術
である。

従来、トランザクションの同時実行性を高める技術とし
て、データの更新履歴（版）をトランザクションからア
クセスできるようにし、異なる１〜ランザクジヨンから
同一のデータを同時に参照、更新可能とする多版同時実
行制御技術が知られている。例えば、Ｂ　ｅｒｎｓｔｅ
ｉｎ、　Ｐ　、　Ａ　、　、　Ｈａｄｚｉｌａｃｏｓ。

Ｖ、、Ｇｏｏｄｍａｎ、　Ｎ、　”Ｃｏｎｃｕｒｒｅｎ
ｃｙ　Ｃｏｎｔｒｏｌ　ａｎｄＲｅｃｏｖｅｒｙ　ｉｎ
　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ”　　第５章（Ａ
ＤＤＩＳＯＮ−ＷＥＳＬＥＹ　　ＰＵＢＬＩＳＩ−（Ｉ
ＮＧ　ＣＯＭＰＡＮＹ、１９８７）には、多収同時実行
制御において、トランザクションの一貫性を二相ロック
で保証する方法と基本タイムスタンプ順序で保証する方
法が示されている。

第３図は、多版同時実行制御技術を用いた従来方式のデ
ータベース処理装置の構成例を示したもので、３１は排
他制御部、３２は排他制御情報表。

３３は版管理表、３４はトランザクション実行部、３５
はデータベース情報表、３６はアドレス変換表、３７は
データベース格納部、３８は端末である。

データベース格納部３７は関係データベースを格納して
いる。排他制御部３１は、排他制御情報表３２と版管理
表３３を用いて、後述する二相ロックあるいは基本タイ
ムスタンプ順序を用いてトランザクションの一貫性を保
証するものである。

排他制御情報表３２は、トランザクションによるデータ
のアクセス状態を表わしたものである。版管理表３３は
、データの更新の度に生成される版を識別するための情
報を格納したものである。トランザクション実行部３４
は、トランザクションを解析して所要のデータベース処
理を実行するもので、通常、複数のトランザクションを
並行して処理している。データベース情報表３５は、関
係データベースの表と該表を構成するデータに関する情
報を格納したものである。アドレス変換表３６は、デー
タの論理識別子からデータベース格納部３７に格納され
た関係データベースの表の該データの格納位置を算出す
るためのものである。端末３８は、トランザクションの
入力と処理結果の出力を行うものである。

端末３８からトランザクションが人力されると、トラン
ザクション実行部３４は、データベース情報表３５から
データベース格納部３７に格納された関係データベース
の表の参照または更新すべきデータを求め、該データの
参照または更新により当該トランザクション実行部３４
で並行処理される全てのトランザクションの一貫性を保
証できるかどうかを排他制御部３１に間合せ、一貫性が
保証できる場合に、該参照または更新処理を実行する。

排他制御部３１は、トランザクション実行部３４から該
−貫性の判定を要求されたデータに対して、排他制御情
報３２と版管理表３３に格納された情報を用いて判定を
行い、一貫性が保証できるときは参照または更新す入き
該データの版の識別子を、並行処理されているいずれか
のトランザクションの終了後に一貫性が保証できるとき
は実行待ちを示す信号を、一貫性を保証できないときは
トランザクションの中止を要求する信号をトランザクシ
ョン実行部３４に与える。トランザクション実行部３４
は、排他制御部３１からの版の識別子を与えられたとき
はアドレス変換表３６から参照または更新すべきデータ
の格納位置を求め、データベース格納部３７をアクセス
してトランザクション処理を実行し、排他制御部３１か
ら実行待ちの信号を与えられたときはトランザクション
の処理を一時中断し、並行処理している他のトランザク
ションがあればその実行に移り、排他制御部３１からト
ランザクションの中止の信号を与えられたときは既に行
った処理を全て実行前の状態に回復させる。

第４図は、第３図に示した従来方式のデータベース処理
装置において、トランザクションの一貫性を二相ロック
で保証する多版同時実行制御によるトランザクション処
理の実行例である。図において、４１はデータベース格
納部３７に格納された関係データベースの表の１つであ
り、４２，４３はデータ識別子Ｘで識別されるデータ（
以降、データＸと呼ぶ）に対応する版であり、この例で
は、トランザクションＡがデータＸを更新し、トランザ
クションＢがデータＸを参照する。排他制御情報表３２
に格納する情報は、データがトランザクションにより参
照されていることを示すリードロック、データがトラン
ザクションにより更新されていることを示すライトロッ
ク、及びデータを参照、更新することができないことを
示す保証ロックの３種類からなる。排他制御部３１は、
同一のデータを同時にライトロックできない規則、保証
ロックされているデータをリードロック、ライトロック
できない規則、データのライ１へロックを解除するとき
に該データがリードロックされているならば該ライ１〜
ロツクを保証ロックに変更する規則、及びトランザクシ
ョンに関係データベースの構成要素として有効な最新の
版を参照させる規則により、トランザクションの一貫性
を保証する。

第４図において、トランザクションＡは、時刻ａでデー
タＸをライトロックし、データＸの版４２を基に更新後
の版４３を生成する。トランザクションＢは、時刻すで
データＸをリードロックし、データＸの表４１の構成要
素として有効な最新の版４２を参照する。データＸは、
この時点で異なるトランザクションＡ、Ｂから同時に参
照、更新される。トランザクションＡによるライトロッ
クは、トランザクションＢによるデータＸのリードロッ
クのため、トランザクションＡの終了時刻Ｃで保証ロッ
クに変更される。データＸの更新後の版４３は時刻Ｃで
表４１の構成要素として有効となるが、データＸの更新
前の版４２がトランザクションＢによりまだ参照されて
いるので、該保証ロックにより更新後の版４３のアクセ
スを禁止してトランザクションの一貫性を保証する。デ
ータＸの保証ロックは、トランザクションＢの終了時刻
ｄでトランザクションＢによりデータＸのリードロック
と共に解除される。データＸの更新前の版４２は、時刻
ｄ以降アクセスされなくなるので削除される。

以上の説明でわかるように、二相ロックを用いた多版同
時実行制御では、更新中のデータに更新前の版と更新後
の版の２つを持たせて、異なるトランザクションから同
一データの参照と更新を同時に行わせながらトランザク
ションの同時実行性を高め、更新完了時に保証ロックを
用いてトランザクションの一貫性を保証している。

第５図は、第３図に示した従来方式のデータベース処理
装置において、トランザクションの一貫性を基本タイム
スタンプ順序で保証する多版同時実行制御によるトラン
ザクション処理の実行例である。図において、５１はデ
ータベース格納部３７に格納された関係データベースの
表の１つであり、５２．５３はデータ識別子Ｙで識別さ
れるデータ（以降、データＹと呼ぶ）に対応する版であ
り、この例では、トランザクションＣがデータＹを更新
し、トランザクションＤがデータＹを参照する。トラン
ザクション実行部３４は、端末３８から入力されるトラ
ンザクションに開始時刻に相当するタイムスタンプを付
加する。排他制御情報表３２に格納する情報は、データ
がトランザクションにより更新されていることを示すラ
イトロックの１種類からなる０版管理表３３に格納する
版の識別情報は、版を生成したトランザクションのタイ
ムスタンプ（以降、ライトスタンプと呼ぶ）と版を現時
点までに参照したトランザクションのタイムスタンプの
最大値（以降、リードスタンプと呼ぶ）を含む。排他制
御部３１は、トランザクションによるデータの参照、更
新時に該トランザクションのタイムスタンプ以下で最大
のライトスタンプを持つ該データの版を選択し、該版が
該データの最新の版であるとき更新を許可する規則、該
版のリードスタンプが該トランザクションのタイムスタ
ンプ以下であるとき更新を許可する規則、及び同一のデ
ータを同時にライトロックできない規則により、トラン
ザクションの一貫性を保証する。

第５図において、トランザクションＣは開始時刻ｇをタ
イムスタンプとして持ち、トランザクションＤは開始時
刻ｆをタイムスタンプとして持ち。

データＹの版５２はｆとｇよりも小さいライトスタンプ
とリードスタンプを持つとする。トランザクションＣは
、時刻りでデータＹの版５２を選択して、データＹをラ
イトロックし、版５２を基に更新後の版５３を生成する
。版５３は、ライトスタンプとしてｇを、リードスタン
プとしてｇより小さい値を与えられる。トランザクショ
ンＤは、時刻ｉでデーＹの版５２を選択して参照する。

版５２のリードスタンプは、ｆに更新される。データＹ
は、この時点で異なるトランザクションがら同時に参照
、更新される。トランザクションＣによるデータＹのラ
イトロックは、トランザクションＣの終了時刻ｊで解除
される。以上の説明でわかるように、基本タイムスタン
プ順序を用いた各版同時実行制御では、データに複数の
版を持たせて、異なるトランザクションから同一データ
の参照と更新を同時に行わせながらトランザクションの
同時実行性を高め１版に付与するライトスタンプとリー
ドスタンプを用いてトランザクションの発生順序に従っ
た一貫性のある１−ランザクジョン処理を行う。

〔発明が解決しようとする課題〕

上記従来技術の二相ロックを用いた各版同時実行制御で
は、データを更新するトランザクションが完了したとき
に、該データを参照中のトランザクションが存在すると
、該参照中のトランザクションが完了するまで、他のト
ランザクションは該データを参照、更新できないので、
関係データベースの表を構成する全てのデータを参照す
るような多くの処理時間を要するトランザクションが長
時間データをリードロックすると、他のトランザクショ
ン処理が長時間遅延されることが多くなり、トランザク
ションの同時実行性が劣下する問題があった。

また、上記従来技術の基本タイムスタンプ順序を用いた
各版同時実行制御では、トランザクションがデータの最
新版を参照で選択したとき、該版が他のトランザクショ
ンによりライトロックされていると参照が遅延され、各
版同時実行制御を用いてもトランザクションの同時実行
性が向上しない問題があった。さらに、トランザクショ
ンがデータの最新版を更新で選択しても、該トランザク
ションより発生時刻の遅いトランザクションが該版を先
行して参照してしまうと該トランザクションを中止しな
ければならず、複数のデータを参照した後その一部を更
新するような、トランザクションの発生からデータの更
新を行うまでの期間の長いトランザクションについて、
各版同時実行制御を用いてもトランザクションの同時実
行性が向上しない問題があった。

本発明の目的は、上記従来技術の問題点を解決し、複数
トランザクションの同時実行性の高い各版同時実行制御
による排他制御方法を提供することにある。

〔課題を解決するための手段〕

本発明は、トランザクションをデータの更新を含む更新
トランザクションとデータの参照のみを行う検索トラン
ザクションに分類し、排他制御部において、更新トラン
ザクションを二相ロックを用いた各版同時実行制御で、
検索トランザクションを基本タイムスタンプ順序で用い
た多収同時実行制御で管理することを特徴とする。

入力されるトランザクションが更新トランザクションで
あるか検索トランザクションであるかは、例えばユーザ
がトランザクションに付加した制御情報を基に判断する
機能をトランザクション実行部に具備しておき、検索ト
ランザクションにはトランザクション実行部での処理開
始時刻に相当するタイムスタンプを割当てる。

排他制御部は、トランザクション実行部から更新トラン
ザクションによるデータの参照、更新について一貫性保
証の判定を要求されると、排他制御情報表を探索して二
相ロックを用いた多収同時実行制御の規則で該判定を行
い、データの参照が可能なとき、関係データベースの表
の構成要素として有効な該データの最新版を版管理表を
基に選択し、該データのリードロックを排他制御情報表
に登録し、トランザクション実行部に該版の参照を許可
し、データが更新が可能なときは、関係データベースの
表の構成要素として有効な該データの最新版を版管理表
を基に選択し、該データのライトロックを排他制御情報
表に登録し、更新により生成される版に関する情報を版
管理表に登録し、トランザクション実行部に該版の複製
に対する更新を許可する。

また、排他制御部は、トランザクション実行部から更新
トランザクションの終了を通知されると、該トランザク
ションがデータの更新により生成した版にトランザクシ
ョン終了時刻に相当するタイムスタンプを割当て、版管
理表に登録されている該版に関する情報に該タイムスタ
ンプを追加し、該トランザクションによるリードロック
の解除とライトロックの解除または保証ロックへの変更
を排他制御情報表上で行う。

更に、排他制御部は、トランザクション実行部から検索
トランザクションによるデータの参照について一貫性保
証の判定を要求されると、前記更新トランザクション終
了時に版に割当てたタイムスタンプをライトスタンプと
考え、版管理表を探索しながら基本タイムスタンプ順序
を用いた多収同時実行制御の規則で参照すべき版を選択
し、トランザクション実行部に該版の参照を許可する。

〔作　用〕

本発明では、二相ロックを用いた多収同時実行制御で版
にライトスタンプを付与し、該ライトスタンプを基に基
本タイムスタンプ順序を用いた多収同時実行制御で版の
選択を行うことにより、２つの異なる各版同時制御を１
つの制御に協調させている。これにより、関係データベ
ースの表を構成する全てのデータを参照するような多く
の処理時間を要する検索トランザクションを基本タイム
スタンプ順序を用いた多収同時実行制御で管理して、デ
ータをリードロックせずに参照することが可能になり、
従来の二相ロックを用いた多収同時実行制御におけるト
ランザクション同時実行性を低下させる要因であるデー
タが長時間リードロックされる状態の発生を軽減できる
。

また、版へのライトスタンプの付与を更新トランザクシ
ョンが完了した時点で行い、基本タイムスタンプ順序を
用いた多収同時実行制御によるデータの参照で関係デー
タベースの表の構成要素として有効となっていない版を
選択しないようにすること、および、関係データベース
の表を構成するいくつかのデータを参照した後にその一
部を更新するようなトランザクションを二相ロックを用
いた多収同時実行制御で管理することで、従来の基本タ
イムスタンプ順序を用いた各版実行制御のトランザクシ
ョンの同時実行性を低下させる要因を解消し、従来方法
よりトランザクションの同時実行性の高い多収同時実行
制御を実現している。

〔実施例〕

以下、本発明の実施例を図面を用いて詳細に説明する。

第１図は、本発明を用いたデータベース処理装置の一実
施例を示す図である。図において、１１〜１８は、第３
図の３１〜３８に各々対応する。

版管理表１３はデータベースレコードリスト１１０と、
版リスト１１１よりなる。排他制御情報表１２はロック
レコードリスト１１２とロックトランザクションリスト
１１３よりなる。１９はタイムスタンプレジスタであり
、検索トランザクションに付与するライトスタンプと更
新トランザクションの完了時に該更新トランザクション
により生成された版に付与するライトスタンプとして用
いる値を格納するための手段である。このタイムスタン
プレジスタ１９の初期値はＯとする。データベースレコ
ードリスト１１０は、関係データベースを構成するレコ
ードのレコード識別子と該１ノコード識別子に対応する
版リスト１１１のポインタを格納する。版リスト１１１
は、各レコードを構成する版の識別番号（版番号）と版
に付与するライトスタンプを格納する。ここでは、版番
号は各レコード毎に版の生成順序に従ってＯから昇順に
整数を割当てることとする。また、初期値に対応する版
のライトスタンプは０とする。ロックレコードリスト１
１２は、現時点で更新トランザクションによりロックさ
れているレコードのレコード識別子と該レコード識別子
に対応するロックトランザクションリスト１１３のポイ
ンタを格納する。

ロックトランザクションリスト１１３は、レコードをロ
ックしているトランザクションのトランザクション識別
子とロック種類を格納する。

第１図の状態は、データベース格納部１７に格納されて
いる関係データベースの表を構成するレコードを単位と
して排他制御を行う場合のものとし、レコード＃１〜＃
４で構成される表Ａに対して、レコード＃２を更新する
トランザクションとレコード＃３を更新するトランザク
ションが既に処理を完了し、レコード＃１とレコード＃
２を参照した後、レコード＃２を更新するトランザクシ
ョンＴ１が処理を継続中である状態を示している。

トランザクションの実行を開始するまでの手順は以下の
通りである。１−ランザクジョン実行部１４は、端末１
８から久方されたトランザクションを更新トランザクシ
ョンと検索トランザクションに分類し、検索トランザク
ションにタイムスタンプレジスタ１９の値をタイムスタ
ンプとして割当てる。次に、トランザクション実行部１
４は、データベース情報表１５からトランザクション処
理に使用するレコードのレコード識別子を求め、該レコ
ードの参照または更新によりトランザクション実行部１
４で並行処理される全てのトランザクションの一貫性を
保証できるかうかを排他制御部１１へ間合わせる。これ
に対して、排他制御部１１は、排他制御情報表１２を構
成するロックレコードリスト１１２とロックトランザク
ション１１３、及び１版管理表１３を構成するデータベ
ースレコードリスト１１０と版リスト１１１を用いて。

後述する第２図に示す処理の流れでトランザクションの
一貫性保証について判定を行う。排他制御部１１は、ト
ランザクションの一貫性を保証するレコードの参照また
は更新が直ちに回前なときは参照または更新すべき該レ
コードの版の版番号を、並行処理される他のトランザク
ションの終了後に可能なときは実行待ちを示す信号を、
いずれも不可能なときはトランザクションの中止を要求
する信号を、トランザクション実行部１４に与える。

トランザクション実行部１４は、排他制御部１１から版
番号を与えられたときは、レコード識別子と該版番号を
基にアドレス変換表１６から参照または更新すべきデー
タの物理アドレスを求め、データベース格納部１７をア
クセスしてトランザクション処理を実行する。一方、ト
ランザクション実行部１４は、排他制御部１１がら実行
待ちの信号を与えられたときは、並行処理している他の
トランザクションの実行に移る。また、トランザクショ
ン実行部１４は、排他制御部１１がらトランザクション
の中止の信号を与えられたときは、端末３８に該トラン
ザクション処理を中止したことを示す信号を与える。

第２図は第１図における排他制御部１１の処理の流れを
示したものである。

第２図（ａ）は、排他制御部１１がトランザクション実
行部１４から更新トランザクションによるレコードの更
新について一貫性保証の判定を要求されたときの処理の
流れである。排他制御部１１は、二相ロックを用いた釜
飯同時実行制御の規則でレコードをライトロックできる
とき、トランザクションの一貫性を保証しながら該レコ
ードの更新を可能と判定する。排他制御部１１は、排他
制御情報表１２から判定の対象レコードのロック状態を
求め、該レコードが判定を要求しているトランザクショ
ン以外のトランザクションにより保証ロックもライトロ
ックもされていないとき、該レコードをライトロックし
、更新に用いる該レコードの版の版番号を版管理表１３
から求めてトランザクション実行部１４に与え、該レコ
ードが判定を要求しているトランザクション以外のトラ
ンザクションにより保証ロックまたはライトロックされ
ているとき、判定を要求しているトランザクションを実
行待ちとすることでデッドロックが発生するならば該ト
ランザクションの中止を要求する信号を、デッドロック
が発生しないならば該トランザクションの実行待ちを示
す信号をトランザクション実行部１４に与える。更新に
用いる版の版番号は、版管理表１３の更新するレコード
に対応する版リスト１１１中の版番号の最大値とする。

トランザクション実行部１４は、これにより該レコード
の最新版の複製を作成して更新を行うことになる。但し
、排他制御部１１は、判定を要求しているトランザクシ
ョンが既にレコードをライトロックしているとき、複製
を作成せずに最新版を直接更新するようにトランザクシ
ョン実行部１４に指示する。尚、排他制御部１１は、更
新可能と判定したとき、更新により生成される版に関す
る情帽のライトスタンプをライトスタンプに用いられな
い値、例えば−１として版管理表１３に登録することで
、該版が関係データベースの表の一部としてまだ有効と
なっていないことを示す。デッドロックは、保証ロック
されているレコードをリードロックしているトランザク
ションまたはレコードをライトロックしているトランザ
クションが判定を要求しているトランザクションの完了
を待っているときに発生する。尚、排他制御部１１は、
デッドロックを判定するとき、一貫性の判定を要求して
いるトランザクションが既にレコードをリードロックし
ているならば、該トランザクションが最新版を更新でき
ないので、トランザクション実行部１４に該トランザク
ションの中止を要求する。

第２図（ｂ）は、排他制御部１１がトランザクション実
行部１４から更新トランザクションによるレコードの参
照について一貫性保証の判定を要求されたときの処理の
流れである。排他制御部１１は、二相ロックを用いた釜
飯同時実行制御の規則でレコードリードロックできると
き、トランザクションの一貫性を保証しながらレコード
の参照が可能と判定する。排他制御部１１は、排他制御
柱情報表１２から判定の対象レコードのロック状態を求
め、該レコードが保証ロックされていないとき、該レコ
ードをリードロックして、参照に用いる該レコードの版
の版番号を版管理表１３から求めてトランザクション実
行部１４に与え、該レコードが保証ロックされていると
き、判定を要求しているトランザクションを実行待ちと
することでデッドロックが発生するならば該トランザク
ションの実行の中止を要求する信号を、デッドロックが
発生しないならば該トランザクションの実行待ちを示す
信号をトランザクション実行部１４に与える。但し、排
他制御部１１は、レコードが保証ロックされているとき
、判定を要求しているトランザクションが既に該レコー
ドをリードロックしているならば、一貫性を保証可能と
判定する。

参照に用いる版の版番号は、版管理表１３の参照するレ
コードに対応する版リスト１１１中のラストスタンプの
最大値に対応するものとする。トランザクション実行部
１４は、これにより関係データベースの表の構成要素と
して有効な最新の該レコードの版を参照することになる
。但し、排他制御部１１は１判定を要求しているトラン
ザクションが既にレコードをライトロックしているなら
ば、該トランザクションの更新で生成した版を参照させ
るため、参照するレコードに対応する版リスト１１１の
版番号の最大値をトランザクション実行部１４に与える
。また、排他制御部１１は、判定を要求しているトラン
ザクションが保証ロックされているレコードを既にリー
ドロックしているならば、該トランザクションに常に同
一の版を参照させるため、参照するレコードに対応する
版リスト１１１中で２番目に大きいライトスタンプに対
応する版番号をトランザクション実行部１４に与える。

デッドロックは、保証ロックされているレコードをリー
ドロックしているトランザクションが判定を要求してい
るトランザクションの完了を待っているときに発生する
。

第２図（Ｑ）は、排他制御部１１がトランザクション実
行部１４から更新トランザクションの完了処理を要求さ
れたときの処理の流れである。排他制御部１１は、タイ
ムスタンプレジスタ１９の値をインクリメントし、版管
理表１３の版リスト１１１中の該更新トランザクション
により生成された版に関する情報のライトスタンプを−
１からタイムスタンプレジスタ１９の値に変更すること
で該版を関係データベースの表の構成要素として有効化
する。また、排他制御部１１は、該更新トランザクショ
ンに関する全てのロック情報を排他制御情報表１２から
削除する。但し、排他制御部１１は、該更新トランザク
ションによりライトロックされているレコードの内、少
なくとも１つのレコードが他のトランザクションにより
リードロックされているならば、該ライトロックを保証
ロックに変更する。排他制御部１１は、ライトロックを
保証ロックに変更したとき、該ライトロックの解除を待
っていたトランザクションがリードロックの解除を新た
に待つことになるので、該リードロックの解除を待つこ
とになったトランザクションについてデッドロックの判
定を行い、デッドロックが発生するとき、該リードロッ
ク待つことになったトランザクションの中止を示す信号
をトランザクション実行部１４に与える。また、排他制
御部１１は、該更新トランザクションによるリードロッ
クの解除で保証ロックされているレコードの全てのリー
ドロックが解除されたならば、該保証ロックを同時に解
除する。排他制御部１１は、ライトロックと保証ロック
を解除したレコードのレコード識別子をトランザクショ
ン実行部１４に与える。トランザクション実行部１４は
、該レコード識別子を基に実行待ちトランザクションを
再開する。

第２図（ｄ）は、排他制御部１１がトランザクション実
行部１４から更新トランザクションの中止処理を要求さ
れたときの処理の流れである。排他制御部１１は、更新
トランザクションが生成した版に関する情報を版管理表
１３から削除し、該更新トランザクションに関する全て
のロック情報を排他制御情報表１２から削除する。更新
トランザクションが生成した版は、更新トランザクショ
ンがライトロックしているレコードを構成する版の内、
ライトスタンプが−１のものである。排他制御部１１は
、該更新トランザクションによるリードロックの解除で
保証ロックされているレコードの全てのリードロックが
解除されたとき、該保証ロックも同時に解除する。排他
制御部１１は、ライトロックと保証ロックを解除したレ
コードのレコード識別子をトランザクション実行部１４
に与える。トランザクション実行部１４は、該レコード
識別子を基に実行待ちトランザクションを再開する。

第２図（ａ）は、排他制御部１１がトランザクション実
行部１４から検索トランザクションによるレコードの参
照について一貫性保証を要求されたときの処理の流れで
ある。排他制御部１１は、基本タイムスタンプ順序を用
いた多板同時実行制御の規則、つまり版管理表１３の参
照するレコードに対応する版リスト１１１中の版番号か
ら検索トランザクションのタイムスタンプ以下で最大の
ライトスタンプを持つものを選択してトランザクション
実行部１４に与える。

第６図は、第１図のデータベース処理装置で、トランザ
クション処理を実行した例を示す。第６図において、６
１はデータベース格納部１７に格納された関係データベ
ースの表の１つであり、６２．６３．６４はレコード識
別子Ｚで識別されるレコード（以降、レコードＺと呼ぶ
）に対応する版である。

更新トランザクションＥ、Ｇはレコード２を更新し、検
索トランザクションＦはレコードＺを参照するものとす
る。更新トランザクションＥは時刻ｎでレコードＺをラ
イトロックし、レコードＺの版６２を基に更新後の版６
３を生成する。版６３のライトスタンプは、このとき−
１に設定される。検索トランザクションＦは、開始時の
タイムスタンプレジスタ１９の値Ｏをタイムスタンプと
して与えられているので、時刻０でレコード２の版６２
を選択して参照する。レコードＺの版６３のライトスタ
ンプは、時刻ｑで更新トランザクションＥが終了すると
き、タイムスタンプレジスタ１９をインクリメントした
値１に設定される。また、トランザクションＥによるレ
コードＺのライトロックは１時刻ｑで更新トランザクシ
ョンＥが終了するとき、レコードＺが他のトランザクシ
ョンによりリードロックされていないので解除される。

トランザクションＧは、時刻ｒでレコードＺの版６３を
基に更新後の版６４を生成する１版６４のライトスタン
プは、このとき−１に設定される。レコードＺの版６４
のライトスタンプは、時刻ｔて更新トランザクションＧ
が終了するとき、タイムスタンプレジスタ１９をインク
リメントした値２に設定される。また、トランザクショ
ンＧによるレコードＺのライトロックは、時刻ｔで更新
トランザクションＥが終了するとき、レコードＺが他の
トランザクションによりリードロックされていないので
解除される。

上記実施例では、参照、更新、追加を行うデータの大き
さとしてレコードを単位としているが、レコード以外の
１例えばページ等を用いても、同様の方法により同時実
行性の高いデータベース処理装置を実現することができ
る。

〔発明の効果〕

以上説明したように、本発明では、トランザクションを
検索トランザクションと更新トランザクションに分け、
検索トランザクションを基本タイムスタンプ順序を用い
た多版同時実行制御で、更新トランザクションを二相ロ
ックを用いた多版同時実行制御で管理する。このことに
より、検索トランザクションは、更新中のデータの参照
で関係データベースの表の構成要素としてまだ有効でな
い版を選択しないため、実行待ちとなることなく常に処
理を行える。また、更新トランザクションは、検索トラ
ンザクションによるデータの参照でデータがリードロッ
クされないため、データが保証ロックされる期間が短く
なり、実行待ちの少ない処理が行える。従って、トラン
ザクションの同時実行性が従来の方法に比べて増加し、
トランザクションの同時実行性の高いデータベース処理
装置を実現できる。特に、従来の二相ロックを用いた多
版同時実行制御でトランザクションの同時実行性を劣下
させる原因となっていた大量のデータを参照する検索ト
ランザクションと、従来の基本タイムスタンプ順序を用
いた多版同時実行制御で実行が中止され易かった複数の
データを参照した後その一部を更新するような更新トラ
ンザクションが同時処理される業務において効果が高く
なる。

【図面の簡単な説明】

第１図は本発明を用いたデータベース処理装置の一実施
例を示す図、第２図は第１図における排他制御部の処理
の流れを示す図、第３図は一般的なデータベース処理装
置の構成例を示す図、第４図は二相ロックを用いた多版
同時実行制御によるトランザクション処理の例を示す図
、第５図は基本タイムスタンプ順序を用いた多版同時実
行制御によるトランザクション処理の例を示す図、第６
図は本発明を用いたトランザクション処理の例を示す図
である。１１・・・排他制御部、　　１２・・・排他制御情報表
、１３・・・版管理表、１４・・・トランザクション実行部、１５・・・データベース情報表。１６・・・アドレス変換表。１７・・・データベース格納部、　　１８・・・端末、
１９・・・タイムスタンプレジスタ、１１０・・・データベースレコードリスト、１１１・・
・版リスト、１１２・・・ロックレコードリスト、１１３・・・ロックトランザクションリスト。第２図（し）第２図ＣすＧ亦り第２図（０）

Claims

【特許請求の範囲】

（１）関係データベースを格納するデータベース格納部
と、関係データベースの表を構成するデータに対して、
該データの参照のみを行う検索トランザクションと、該
データの更新を新たな版の生成により実行する更新トラ
ンザクションとを混在して実行するトランザクション実
行部と、該トランザクション実行部で複数の検索トラン
ザクションと複数の更新トランザクションを同時に実行
する際のトランザクションの一貫性を保証する排他制御
部とからなるデータベース処理装置において、前記更新トランザクションによるデータのアクセス状態
を示す排他制御情報を登録する排他制御情報表と、デー
タを構成する版が前記関係データベースの表の構成要素
として有効となった時刻を示すタイムスタンプを登録す
る版管理表を設け、前記排他制御部は、前記トランザクション実行部で更新トランザクションに
よるデータの参照と更新を実行するときは、該更新トラ
ンザクションの一貫性を前記排他制御情報に登録された
該データに関する排他制御情報を基に保証し、データの
更新の際は前記管理表から該データの最新の版を選択し
て前記トランザクション実行部に該版を基に新たな版の
生成を行わせ、前記トランザクション実行部で更新トランザクションが
完了するときは、該更新トランザクションによるデータ
の更新で生成した版に該更新トランザクションの完了時
刻に相当するタイムスタンプを割当て、前記版管理表に
登録し、前記トランザクシヨン実行部で検索トランザク
ションによるデータの参照を実行するときは、該検索ト
ランザクションの一貫性を前記トランザクション実行部
により該検索トランザクションに割当てられた該検索ト
ランザクションの開始時刻に相当するタイムスタンプと
前記版管理表に登録された該データの版のタイムスタン
プとの比較により保証し、異なるトランザクションから同一のデータを同時に参照
、更新しながら、トランザクションの一貫性を保証する
ことを特徴とするデータベースの排他制御方法。