(57)【要約】【課題】ロックに要するメモリ使用量を減少させつつ、より高速にロックの探索、検索を実行可能とする技術を提供する。【解決手段】データベースの更新要求を送信したユーザを特定するユーザ特定情報と、更新要求にかかる行の範囲を示す情報であるロック対象行範囲とを有するノードで構成される二分木を記憶するデータロック情報記憶部と、ユーザから新たな更新要求を受信すると新たな更新要求にかかる行が二分木中のいずれのノードのロック対象行範囲とも一致しない場合、ユーザを示す情報をユーザ特定情報として有し、新たな更新要求にかかる行をロック対象行範囲として有する新たなノードを二分木に追加し、更新要求を発したユーザを示す情報とユーザ特定情報とが一致するノードであって、且つ新たな更新要求にかかる行が当該ノードのロック対象行範囲に含むノードが二分木に存在する場合、ロック取得可能であると判定するロック制御部とを有する。【選択図】図２
2014134896.tif 000002
【特許請求の範囲】
【請求項１】
データベースの更新要求を送信したユーザを特定するユーザ特定情報と、当該更新要求にかかる行の範囲を示す情報であるロック対象行範囲とを有するノードで構成される二分木を記憶する記憶手段と、
ユーザから新たな更新要求を受信すると、前記二分木を探索し、前記新たな更新要求にかかる行が前記二分木中のいずれのノードのロック対象行範囲とも一致しない場合、前記ユーザを示す情報をユーザ特定情報として有し、前記新たな更新要求にかかる行をロック対象行範囲として有する新たなノードを前記二分木に追加し、
前記更新要求を発したユーザを示す情報と前記ユーザ特定情報とが一致するノードであって、且つ前記新たな更新要求にかかる行が当該ノードのロック対象行範囲に含むノードが前記二分木に存在する場合、前記新たな更新要求にかかる行のロックの取得が可能であると判定する制御手段と
を有するデータベース装置。
【請求項２】
前記新たな更新要求にかかる行が複数あり、且つその複数の行が一つの連続した行範囲となる場合、前記制御手段は前記一つの連続した範囲を更新対象行範囲とし、
前記更新要求を発したユーザを示す情報と前記ユーザ特定情報とが一致するノードのロック対象行範囲と一致しない行範囲が存在する場合、前記ユーザを示す情報をユーザ特定情報として有し前記更新対象行範囲のうち、前記一致しない行範囲をロック対象行範囲として有する新たなノードを、前記ロック二分木に追加する
請求項１に記載のデータベース装置。
【請求項３】
前記記憶手段は、ユーザごとのロックの取得を示す二分木であるユーザ別ロック二分木と、全ユーザのロックの取得を示す全体ロック二分木とを記憶し、
前記制御手段は、ユーザから新たな更新要求を受信すると、当該ユーザに対応するユーザ別ロック二分木を探索して、前記新たな更新要求にかかる行が前記二分木のいずれのノードのロック対象行範囲とも一致しない場合、前記全体ロック二分木を探索し、前記新たな更新要求にかかる行が前記全体二分木のいずれのノードのロック対象行範囲とも一致しない場合、前記ユーザを示す情報をユーザ特定情報として有し前記新たな更新要求にかかる行をロック対象行範囲として有する新たなノードを、前記ユーザ別ロック二分木及び全体ロック二分木に追加する
請求項１に記載のデータベース装置。
【請求項４】
前記ロック制御手段は、
前記ロック二分木のノードの中からいずれか一つのノードを選択ノードとして選択するとともに、前記選択ノード以外の一つのノードを相手ノードとして選択し、
前記選択ノードと前記相手ノードのユーザ特定情報が一致し、且つ前記選択ノードのロック対象行範囲と前記相手ノードのロック対象行範囲が一つの連続した行範囲とすることができる場合、前記選択ノードを削除するとともに前記相手ノードのロック対象範囲が前記一つの連続した行範囲となるようにロック対象範囲を変更する
請求項１から請求項３のいずれかに記載のデータベース装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載の実施の形態は、データベース装置に関する。
【背景技術】
【０００２】
多重処理環境におけるオペレーティングシステム及びデータベース管理システムのロック管理部分は、処理のための資源に対してロックの割り当て及び解放を行う。
【０００３】
一般的なデータベース管理システム、特に、リレーショナル・データベース管理システム（ＲＤＢＭＳ）は、データベース，スキーマ，表，行といったように論理的に階層的な資源で構成される。表と行との間には、物理的に行を格納するための記憶装置である磁気ディスクなどの場合、行を物理的に固定長のブロックあるいはページという単位に格納される。この場合、管理資源は、表と行との間にページが資源として管理されることになる。
【０００４】
データベースにアクセスする場合、ユーザは一般にＳＱＬ(ＩＳＯ９０８５)というデータベース問い合わせ言語を利用して行う。ユーザは、ＳＱＬにおいてアクセスしたい表を指定し、表を構成する複数の列に対して探索条件を指定することによって、検索を行ったり、更新を行ったりすることができる。その場合、ＲＤＢＭＳは指定された表に対して細分性の大きい資源（表）から小さい資源（ページ又は行）に対して階層的にロックを割り当てていく。もし、ある階層の資源に対して排他的なロックが割り当てられていれば、その資源に対する排他的ロックが解放されるまで待たされるか処理が禁止されることになる。
【０００５】
従来、検索のような処理の場合には、ロックのモードは参照が主体であるから共用モードでのロックとなり、同じ他の検索を行う処理とは同時実行性が向上する。但し、同じ表に対するアクセスに検索を行う処理と更新を行う処理とが混在する場合には、表単位でロックを行ってしまうと同時実行性が損なわれることになるので、できるだけ細分性の小さい資源に対してロックを割り当てることによって同時実行性を向上させることが行われている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３７４７４７７号公報
【特許文献２】特許第３８００２２８号公報
【特許文献３】特許第３８００２４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記ロックが大量に取得される場合には、単純に行ごとにロックをするような方法では検索等の処理が遅くなるという問題がある。また、ロックされる行数も大量となるため、これらに割り当てられるメモリ容量も増大してしまい、利用可能なリソースを食われてしまうという問題もあった。
【０００８】
この発明は、データベース管理システムにおいて、ロックに要するメモリ使用量を減少させつつ、より高速にロックの探索、検索を実行可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
以下に説明する実施の形態のデータベース装置は記憶手段と、制御手段を有する。
【００１０】
記憶手段は、データベースの更新要求を送信したユーザを特定するユーザ特定情報と、当該更新要求にかかる行の範囲を示す情報であるロック対象行範囲とを有するノードで構成される二分木を記憶する。
【００１１】
制御手段は、ユーザから新たな更新要求を受信すると、前記二分木を探索し、前記新たな更新要求にかかる行が前記二分木中のいずれのノードのロック対象行範囲とも一致しない場合、前記ユーザを示す情報をユーザ特定情報として有し、前記新たな更新要求にかかる行をロック対象行範囲として有する新たなノードを前記二分木に追加し、前記更新要求を発したユーザを示す情報と前記ユーザ特定情報とが一致するノードであって、且つ前記新たな更新要求にかかる行が当該ノードのロック対象行範囲に含むノードが前記二分木に存在する場合、前記新たな更新要求にかかる行のロックの取得が可能であると判定する。
【００１２】
また、前記新たな更新要求にかかる行が複数あり、且つその複数の行が一つの連続した行範囲となる場合、前記制御手段は前記一つの連続した範囲を更新対象行範囲とし、前記更新要求を発したユーザを示す情報と前記ユーザ特定情報とが一致するノードのロック対象行範囲と一致しない行範囲が存在する場合、前記ユーザを示す情報をユーザ特定情報として有し前記更新対象行範囲のうち、前記一致しない行範囲をロック対象行範囲として有する新たなノードを、前記ロック二分木に追加する構成としても良い。
【００１３】
また、前記記憶手段は、ユーザごとのロックの取得を示す二分木であるユーザ別ロック二分木と、全ユーザのロックの取得を示す全体ロック二分木とを記憶し、前記制御手段は、ユーザから新たな更新要求を受信すると、当該ユーザに対応するユーザ別ロック二分木を探索して、前記新たな更新要求にかかる行が前記二分木のいずれのノードのロック対象行範囲とも一致しない場合、前記全体ロック二分木を探索し、前記新たな更新要求にかかる行が前記全体二分木のいずれのノードのロック対象行範囲とも一致しない場合、前記ユーザを示す情報をユーザ特定情報として有し前記新たな更新要求にかかる行をロック対象行範囲として有する新たなノードを、前記ユーザ別ロック二分木及び全体ロック二分木に追加する構成としても良い。
【００１４】
またさらに、前記ロック制御手段は、前記ロック二分木のノードの中からいずれか一つのノードを選択ノードとして選択するとともに、前記選択ノード以外の一つのノードを相手ノードとして選択し、前記選択ノードと前記相手ノードのユーザ特定情報が一致し、且つ前記選択ノードのロック対象行範囲と前記相手ノードのロック対象行範囲が一つの連続した行範囲とすることができる場合、前記選択ノードを削除するとともに前記相手ノードのロック対象範囲が前記一つの連続した行範囲となるようにロック対象範囲を変更する構成としても良い。
【図面の簡単な説明】
【００１５】
【図１】実施の形態にかかるデータベース管理装置を含むマルチユーザ・データベースシステムの構成例を示すブロック図
【図２】実施の形態にかかるデータベース管理部の構成例を示すブロック図
【図３】データベース管理部１０の主たる動作の一つである、ＳＱＬ文実行処理の一例を示すフローチャート
【図４】ロック二分木のノードに対応するオブジェクトのデータ構成例を示す図
【図５】ロック二分木に新たなノードが書き加えられた状態を示す図
【図６】ロウロックオブジェクト４＿１（ノードＮ＿１）を、従来の技術におけるロウロックオブジェクトで示した場合のデータ構成例を示す図
【図７】図５の状態の後に新たなＳＱＬ文をデータベース管理部が受信した場合のロック二分木１５の例を示す図
【図８】ノードＮ＿１の範囲最大値情報を書き換えるとともに、ノードＮ＿２を削除した状態のロック二分木を示す図
【図９】図８の状態の後に新たなＳＱＬ文をデータベース管理部が受信した場合のロック二分木の例を示す図
【図１０】図９の状態の後に新たなＳＱＬ文をデータベース管理部が受信した場合のロック二分木の例を示す図
【図１１】図１０の状態の後に新たなＳＱＬ文をデータベース管理部が受信した場合のロック二分木の例を示す図
【図１２】ノードＮ＿４の範囲最大値情報を書き換えるとともに、ノードＮ＿５を削除した状態のロック二分木を示す図
【図１３】ノードＮ＿３であるロウロックオブジェクト４＿３の範囲最小値情報を書き換えるとともに、ノードＮ＿４を削除した状態のロック二分木を示す図
【図１４】図１３の状態の後に新たなＳＱＬ文をデータベース管理部が受信した場合のロック二分木の例を示す図
【図１５】ノードＮ＿３であるロウロックオブジェクト４＿３の範囲最小値情報を書き換えるとともに、ノードＮ＿６を削除した状態のロック二分木を示す図
【図１６】ノードＮ＿１であるロウロックオブジェクトの範囲最大値情報を書き換えるとともに、ノードＮ＿３を削除した状態のロック二分木を示す図
【図１７】従来の技術におけるロウロックオブジェクトのデータ構成例を示す図
【図１８】本実施の形態におけるロウロックオブジェクトのデータ構成例を示す図
【図１９】ロック対象行範囲が行番号１１から行番号１３までである場合の、従来の技術におけるロウロックオブジェクトのデータ構成例を示す図
【図２０】本実施の形態におけるロウロックオブジェクトを使用した場合、一つのロウロックオブジェクトのみでロック対象行範囲を行番号１１から行番号１３とすることを記述できることを示す図
【図２１】図１７に示したロック二分木１５に新たにロック対象行の行番号を「１１」とするノード（ロウロックオブジェクト）が追加された状態を示す図
【図２２】図１８に示したロック二分木に新たにロック対象行の行番号を「１１」とするノード（ロウロックオブジェクト）が追加された状態を示す図
【図２３Ａ】図２２に示したノードＮ＿１４（ロウロックオブジェクト４＿１４）とノードＮ＿１１（ロウロックオブジェクト４＿１１）とを集約した状態の例を示す図
【図２３Ｂ】ノード集約処理の一例を示したフローチャート
【図２３Ｃ】ノード集約処理の対象を示すロック二分木の例を示す図
【図２４】ノードを集約する処理を行う前のロック二分木を示す図
【図２５】図２４のロック二分木についてノード集約処理を実行した後に得られるロック二分木を示す図
【図２６】ノード追加処理の一例を示すフローチャート
【図２７】ロック二分木の一例を示す図
【図２８】葉ノードであるノードＮ＿２７＿５と、その親ノードであるノードＮ＿２７＿４との集約が判断されている状態を示す
【図２９】葉ノードであるノードＮ＿２７＿５と、その親ノードであるノードＮ＿２７＿４との集約が完了した状態を示す図
【図３０】葉ノードであるノードＮ＿２７＿５と、その２世代上のノードＮ＿２７＿２との集約が判断されている状態を示す図
【図３１】葉ノードであるノードＮ＿２７＿４と、その２世代上のノードであるノードＮ＿２７＿２との集約が完了した状態を示す図
【図３２】ＳＱＬ文実行処理の一例を示すフローチャート
【図３３】ノード追加処理の例を示すフローチャート
【図３４】ロック二分木の例を示す図
【図３５】別のロック二分木の例を示す図
【図３６】更新要求３５０１＿１に基づいてノード追加処理を行う状態を示す図
【図３７】さらに別のロック二分木１５の例を示す図
【図３８】ノードＮ＿３７＿５が追加されたロック二分木を示す図
【図３９】ノードＮ＿３７＿５が選択ノードとして選択され、ノードＮ＿３７＿４が相手ノードとして選択された状態を示す図
【図４０】ノードＮ＿３７＿４のロック対象行範囲を「１４、１６」と変更した状態のロック二分木を示す図
【図４１】ノードＮ＿３７＿４が選択ノード、ノードＮ＿３７＿３が相手ノードとして選択された状態を示す図
【図４２】ノードＮ＿３７＿４を削除し、ノードＮ＿３７＿３のロック対象行範囲を「１４、１８」と変更した状態のロック二分木１５を示す図
【図４３】ノードＮ＿３７＿６が選択ノード、ノードＮ＿３７＿３が相手ノードとして選択された状態を示す図
【図４４】ノードＮ＿３７＿６を削除し、ノードＮ＿３７＿３のロック対象行範囲を「１４、１９」と変更した状態のロック二分木を示す図
【図４５】ノードＮ＿３７＿３が選択ノード、ノードＮ＿３７＿１が相手ノードとして選択された状態を示す図
【図４６】ノードＮ＿３７＿３が削除され、ノードＮ＿３７＿１のロック対象行範囲が「１４、２１」と変更された状態のロック二分木を示す図
【図４７】第３の実施例にかかるデータベース管理部の構成例を示すブロック図
【図４８】第３の実施例にかかるＳＱＬ文実行処理の一例を示すフローチャート
【図４９】ステップＳ４Ａの処理内容の例を示すフローチャート
【図５０】ロック取得状況を示す図
【図５１】図５０のノード群をロック二分木の形式で示した図
【図５２】ユーザ「ｋ１」についてのユーザ別ロック二分木の例を示す図
【図５３】全体ロック二分木の構成を示す図
【図５４】図５０及び図５１に示すロック取得状態におけるデータロック情報記憶部１４の記憶内容の例を示す図
【図５５】更新要求を受け付けた状態を示す図
【図５６】新たな更新要求を受け付けた状態を示す図
【図５７】さらに新たな更新要求を受け付けた状態を示す図
【図５８】さらに新たな更新要求を受け付けた状態を示す図
【図５９】ロック制御部がノードＮ＿５０＿１６を選択ノードとし、ノードＮ＿５０＿６を新たな相手ノードとした状態を示す図
【図６０】ロック制御部がノードＮ＿５０＿１６を削除し、ノードＮ＿５０＿６のロック対象行範囲を「９、１２」と変更した状態のロック二分木を示す図
【図６１】全体ロック二分木のノードＮ＿５３＿３を選択ノードとし、ノードＮ＿５３＿２を相手ノードとして選択した状態を示す図
【図６２】ロック制御部がノードＮ＿５３＿３を削除し、ノードＮ＿５３＿２のロック対象行範囲を「１、１０」と変更した状態のロック二分木を示す図
【図６３】ロック制御部が全体ロック二分木のノードＮ＿５３＿２を選択ノードとし、ノードＮ＿５３＿１を相手ノードとして選択した状態を示す図
【図６４】ロック制御部がノードＮ＿５３＿２を削除し、ノードＮ＿５３＿１のロック対象行範囲を「１、２１」と変更した状態の全体ロック二分木を示す図
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して、この発明の実施の形態にかかる、データベース管理装置を詳細に説明する。
【００１７】
[０．定義]
「ロック二分木」とは、データベース管理システムが、処理のための資源に対するロックの割り当て及び解放の状態を記録するデータである。
【００１８】
「ノード」は、ロック二分木の節点である。各ノードはロウロックオブジェクトとして生成される。
【００１９】
「ロウロックオブジェクト」は、ロックの割り当ての元となる更新要求を行ったユーザを特定する情報であるユーザ特定情報、ロック対象範囲の最小値を特定する範囲最小値情報、ロック対象範囲の最大値を特定する範囲最大値情報、右子ノードを特定する情報である右子ノード特定情報、左子ノードを特定する情報である左子ノード特定情報を有するデータである。ロウロックオブジェクトは、上記ノードをデータとして見た場合の構成要素である。「ノード」は、対応するロウロックオブジェクトのユーザ特定情報、ロック対象範囲の最小値を特定する範囲最小値情報、ロック対象範囲の最大値を特定する範囲最大値情報、右子ノードを特定する情報である右子ノード特定情報、左子ノードを特定する情報である左子ノード特定情報を有する。
【００２０】
「ロック対象行範囲」は、上記範囲最小値情報及び範囲最大値情報によって規定される行範囲である。この行範囲に含まれる全ての行についてロックが割り当てられていることを意味する。本明細書中、行範囲を「Ａ、Ｂ」（但しＡ＜Ｂ）と表記することがある。これは行番号Ａから行番号Ｂまでの各行を意味する。例えば、行範囲「５、８」は、行番号５、行番号６、行番号７、行番号８の４つの行を意味する。また、行範囲「Ａ、Ａ」と表記される場合は、行番号Ａのみが対象であることを意味する。
【００２１】
[１．データベースシステム等の構成例]
図１は、本実施の形態にかかるデータベース管理装置を含むマルチユーザ・データベースシステムの構成例を示すブロック図である。
【００２２】
マルチユーザ・データベースシステム１は、複数のユーザが同時にデータベースにアクセスするシステムであって、例えば受発注システムや座席予約システムなどである。
【００２３】
マルチユーザ・データベースシステム１は、クライアント５０と、ネットワーク４０を介してクライアント５０と接続可能なアプリケーションサーバ６０と、アプリケーションサーバ６０と接続されたデータベース装置２とを有する。
【００２４】
データベース装置２は、データベース３０を記憶するデータベース記憶部２０と、データベース管理部１０を有する。データベース装置２は、クライアント５０からのリクエストなどに対してデータベース３０の検索、更新などの処理を行い、処理結果を返す。
【００２５】
データベース管理部１０は、コンピュータのデータベースを構築するために必要なデータベース運用、管理のためのシステム、及びそのソフトウェアである。
【００２６】
アプリケーションサーバ６０は、クライアント５０からのHTTPのレスポンス要求を処理するウェブサーバとバックエンドのデータベース管理部１０を中心とするデータベース装置２への橋渡しを担い、データの加工などの処理を行う。
【００２７】
データベース装置２は、例えばコンピュータ、ワークステーションなどの情報処理装置によって実現される装置である。この情報処理装置は、演算処理装置（ＣＰＵ）、主メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、入出力装置（Ｉ／Ｏ）、及び必要な場合にはハードディスク装置等の外部記憶装置を具備している装置である。
【００２８】
クライアント５０は、コンピュータネットワークにおいてサーバの提供する機能やデータを利用するコンピュータ、通信端末装置、携帯通信端末装置などである。クライアント５０は、タッチパネルやキーボードなどの入力部５１と、グラフィカルユーザインターフェイスを提供するＧＵＩ部５２と、入力に応じてメッセージ、コマンドなどを生成してアプリケーションサーバ６０に送信し、アプリケーションサーバ６０から受信したメッセージやデータを処理し、ＧＵＩ部５２を介してユーザに情報を提供させる論理プログラム部５３を有する。
【００２９】
図２に、本実施の形態にかかるデータベース管理部１０の構成例を示す。データベース管理部１０は、ＳＱＬ文解析部１１と、データ制御部１２と、ロック制御部１３と、データロック情報記憶部１４とを有する。
【００３０】
なお、これら構成要素はデータベース装置２の機能を、機能ごとにまとめてブロックとして捉えたものであり、データベース装置２が各構成要素に対応する基板、装置、回路、部品などの物理的構成要素を備えていなければならないことを意味するわけではない。また、「接続されている」とは、データ、情報、命令などの送受信、受け取り、受け渡しなどが可能な状態になっていることをいい、互いに配線で連結されているような物理的な接続に限られる意味ではない。
【００３１】
ＳＱＬ文解析部１１は、受け取ったＳＱＬ文が更新系の命令か否かを判定する機能を有する。命令が更新系の命令であれば、データ制御部１２に更新系の命令を処理させる。
【００３２】
データ制御部１２は、ＳＱＬ文解析部１１から更新系の命令を受け取ると、データベース記憶部２０に記憶されたデータの該当行がデータロックされているか否かを、データロック情報記憶部１４に記憶されたロック二分木１５を参照して判定し、該当行がデータロックされていないと判定した場合は、命令の内容に従ってデータベース記憶部２０に記憶されている該当行の内容を書き換える機能を有する。
【００３３】
ロック制御部１３は、ＳＱＬ文解析部１１が受け取ったＳＱＬ文が更新系の命令である場合には、データベース記憶部２０に記憶されたデータの該当行がデータロックされているか否かを、データロック情報記憶部１４に記憶されたロック二分木１５を参照して判定し、新たにロック取得が可能である場合はロック二分木１５に、取得するロックに対応する新たなノードを追加等する機能を有する。
【００３４】
［動作例］
図２に示すデータベース管理部１０の動作例を説明する。図３はデータベース管理部１０の主たる動作の一つである、ＳＱＬ文実行処理の一例を示すフローチャートである。
【００３５】
ＳＱＬ文実行処理において、データベース管理部１０、より詳しくはＳＱＬ文解析部１１はアプリケーションサーバ６０からＳＱＬ文を受信する（Ｓ１）。
【００３６】
次にデータベース管理部１０、より詳しくはＳＱＬ文解析部１１は、受信したＳＱＬ文を解析して、そのＳＱＬ文により構成される命令が、データベースの更新を伴う更新系命令であるか否かを判定する（Ｓ２）。その命令が更新系命令でないと判定した場合（Ｓ２，Ｎｏ）、ＳＱＬ文解析部１１は、その命令をデータ制御部１２に渡し、データ制御部１２はその命令を実行し、その後ＳＱＬ文実行処理を終了する。一方、その命令が更新系命令であると判定した場合（Ｓ２，Ｙｅｓ）、ＳＱＬ文解析部１１はデータ制御部１２にその命令を渡す。
【００３７】
データ制御部１２はその命令に基づいて、データベース３０における更新対象の行を決定し（Ｓ３）、更新対象の行を特定する情報（例えば、行番号、レコード番号など）をロック制御部１３に渡す。なお、更新対象の行が２以上ある場合には、未処理の行のうち一つの行を選択し、その選択した更新対象の行を特定する情報（例えば、行番号、レコード番号など）をロック制御部１３に渡す。
【００３８】
ロック制御部１３は、受け取った更新対象の行を特定する情報に基づいて、データロック情報記憶部１４に記憶されているロック二分木１５に、更新対象の行に対応するノードを追加して更新対象行のロックを行う（Ｓ４）。その後ロック制御部１３はデータ制御部１２に更新対象の行のロックが行われたことを通知する。
【００３９】
更新対象行のロックが行われたことを通知されたデータ制御部１２は、データベース３０における更新対象の行を前述の更新系命令の内容に基づいて書き換える（更新する）（Ｓ５）。
【００４０】
次に、データ制御部１２は、ステップＳ３において決定された更新対象の行の全てがステップＳ４からステップＳ５で処理されたか否かを判定する（Ｓ６）。全ての更新対象の行がステップＳ４からステップＳ５で処理されていないと判定した場合（Ｓ６、Ｎｏ）、データ制御部１２は更新対象の行のうち、未処理の行を一つ選択して、選択した行を特定する情報をロック制御部１３に渡す。ロック制御部１３は受け取った更新対象の行を特定する情報に基づいて、データロック情報記憶部１４に記憶されているロック二分木１５に、更新対象の行に対応するノードを追加して更新対象行のロックを行う（Ｓ４）。一方、ステップＳ６において、全ての更新対象の行がステップＳ４からステップＳ５で処理されたと判定した場合（Ｓ６、Ｙｅｓ）、データベース管理部１０はＳＱＬ文実行処理を終了する。
【００４１】
［本実施の形態におけるロック二分木へのノードの加入］
次に、更新対象の行を新たにロックするために行う、ロック二分木１５へのノードの追加を行うノード追加処理について説明する。ロック二分木は、通常、表ごとに一つ用意される。ロック二分木は、データベース毎に用意されてもよいし、表の一定数の行ごとに一つ、例えば、１−１０００と１００１−２０００でそれぞれロック二分木が用意されてもよい。ここでは表ごとに用意されているものとして説明している。
【００４２】
図４は、ロック二分木１５のノードに対応するオブジェクト（ロウロックオブジェクト：RowLockObject）のデータ構成例を示す図である。ロウロックオブジェクト４は、その属性情報（プロパティ）として、ロックを行う必要がある更新をデータベース装置に要求したユーザ（あるいはクライアント５０）を特定する情報であるユーザ特定情報（図４中”Locker”と表記する）と、ロック対象行範囲の最小値を特定する情報である範囲最小値情報（図４中”To”と表記する）と、ロック対象行範囲の最大値を特定する情報である範囲最大値情報（図４中”From”と表記する）とを有する。さらに、自分の子ノードを特定する情報である左子ノード特定情報及び右子ノード特定情報を属性として有するのであるが、ここでは左子ノード特定情報及び右子ノード特定情報については省略する。
【００４３】
図５は、ロック二分木１５に新たなノードが書き加えられた状態を示す図である。図５のロック二分木１５は、初期状態においてルートノードＮ＿０のみを有している状態として生成される。その後、ＳＱＬ文解析部１１がＳＱＬ文ＳＱＬ１を受信したとする。このＳＱＬ文ＳＱＬ１は、ユーザ名：Ｕ１であるユーザが行番号３以下の全ての行を更新することを意味している。
【００４４】
このＳＱＬ文ＳＱＬ１に応じて、ロック制御部１３は、ロウロックオブジェクト４＿１を生成し、これをルートノードＮ＿０の右子ノードとしてロック二分木１５に追加する。ロウロックオブジェクト４＿１の「ユーザ特定情報」は、”Ｕ１”であり、範囲最小値情報は”１”であり、範囲最大値情報は”３”に設定されている。このロウロックオブジェクト４＿１は、ロック二分木１５の構成要素として見た場合はノードＮ＿１と見ることができる。
【００４５】
図６に、ロウロックオブジェクト４＿１（ノードＮ＿１）を、従来の技術におけるロウロックオブジェクトで示した場合のデータ構成例を示す。従来の技術におけるロウロックオブジェクトは、ユーザ特定情報と、ロック対象行を特定する情報であるロック対象行情報を有する。
【００４６】
本実施の形態との比較のため、ロウロックオブジェクト４＿１を、従来の技術におけるロウロックオブジェクトで示した場合について図６を参照しながら説明する。従来の技術におけるロウロックオブジェクトを用いた場合、ユーザ特定情報を”Ｕ１"とし、ロック対象行情報を”２”とするロウロックオブジェクト４＿Ｐ１と、ロウロックオブジェクト４＿Ｐ１の左子ノードであって、ユーザ特定情報を”Ｕ１"とし、ロック対象行情報を”１”とするロウロックオブジェクト４＿Ｐ２、及びロウロックオブジェクト４＿Ｐ１の右子ノードであって、ユーザ特定情報を”Ｕ１"とし、ロック対象行情報を”３”とするロウロックオブジェクト４＿Ｐ３との３つのロウロックオブジェクトで構成される。
【００４７】
これをノードとして捉えた場合、ノードＮ＿Ｐ1と、ノードＮ＿Ｐ１の左子ノードであるノードＮ＿Ｐ２と、ノードＮ＿Ｐ１の右子ノードであるノードＮ＿Ｐ３で構成されていると見ることができる。
【００４８】
さて、図７に、図５の状態の後に新たなＳＱＬ文ＳＱＬ２をデータベース管理部１０が受信した場合のロック二分木１５の例を示す。新たなＳＱＬ文ＳＱＬ２の内容は、ユーザ”Ｕ１”が行番号４のレコードを更新するという内容である。
【００４９】
ロック制御部１３は、このＳＱＬ文ＳＱＬ２に応じて、新たなロウロックオブジェクト４＿２を生成し、第１世代の子ノードＮ＿１の右子ノードＮ＿２としてロック二分木１５に追加する。ロウロックオブジェクト４＿２（ノードＮ＿２）の「ユーザ特定情報」は、”Ｕ１”であり、範囲最小値情報は”４”であり、範囲最大値情報は”４”に設定されている。
【００５０】
次に、ロック制御部１３は、２つのノード、ノードＮ＿１とノードＮ＿２を一つのノードに集約できるか否かを判定し、集約できる場合には、一方を削除し他方のみ残す。
【００５１】
本実施の形態において、２つのノードを一つのノードに集約してよい条件は
（１）２つのノードのユーザ特定情報が一致すること、及び
（２）２つのノードのロック対象行範囲を一つの連続したロック対象行範囲とすることができること、
の２つである。例えば、一方のノードのロック対象行範囲が１０から１２、もう一方のノードのロック対象行範囲が７から９である場合は、２つのノードのロック対象行範囲が一つの連続した行範囲である７から１２となるので、この２つのノードは範囲最小値情報を”７”とし、範囲最大値情報を”１２”とする一つのノードに集約することができる。
【００５２】
図７に示す例において、ロック制御部１３は、ノードＮ＿１とノードＮ＿２とを一つに集約することが可能かどうか判定する。
【００５３】
判定は具体的には以下の通りである。
（１）２つのノードのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのノードのロック対象行範囲は、”１から３”と、”４”であり、これらは一つの連続したロック対象行範囲”１から４”とすることができる。
【００５４】
よって、２条件が成立するため、ロック制御部１３は、ノードＮ＿１とノードＮ＿２とを一つに集約すること可能と判定し、ノードＮ＿１の範囲最大値情報を”３”から”４”に書き換えるとともに、ノードＮ＿２は削除する。図８にノードＮ＿１の範囲最大値情報を書き換えるとともに、ノードＮ＿２を削除した状態のロック二分木１５を示す。
【００５５】
次に、図８の状態の後に新たなＳＱＬ文ＳＱＬ３をデータベース管理部１０が受信した場合のロック二分木１５の例を図９に示す。新たに受信したＳＱＬ文ＳＱＬ３の内容は、ユーザ”Ｕ１”が行番号１０のレコードを更新するという内容である。
【００５６】
ロック制御部１３は、このＳＱＬ文ＳＱＬ３に応じて、新たなロウロックオブジェクト４＿３を生成し、これを第１世代の子ノードＮ＿１の右子ノードＮ＿３としてロック二分木１５に追加する。追加されたロウロックオブジェクト４＿３の「ユーザ特定情報」は、”Ｕ１”であり、範囲最小値情報は”１０”であり、範囲最大値情報は”１０”に設定されている。
【００５７】
図９に示すロック二分木１５において、ロック制御部１３は、ノードＮ＿１とノードＮ＿３とを一つに集約することが可能かどうか判定する。
【００５８】
判定は具体的には以下の通りである。
（１）２つのロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのロウロックオブジェクトのロック対象行範囲は、”１から４”と、”１０”であり、これらは一つの連続したロック対象行範囲とはならない。
【００５９】
よって、条件（２）は不成立のため、ロック制御部１３は、ノードＮ＿１とノードＮ＿３とを一つに集約することが不可能と判定する。
【００６０】
次に、上記図９の状態の後に新たなＳＱＬ文ＳＱＬ４をデータベース管理部１０が受信した場合のロック二分木１５の例を図１０に示す。新たに受信したＳＱＬ文ＳＱＬ４の内容は、ユーザ”Ｕ１”が行番号６、７、８それぞれのレコードを更新するという内容である。
【００６１】
ロック制御部１３は、このＳＱＬ文ＳＱＬ４に応じて、新たなロウロックオブジェクト４＿４を生成し、これを第２世代の子ノードＮ＿３の左子ノードＮ＿４としてロック二分木１５に追加する。追加されたノードＮ＿４であるロウロックオブジェクト４＿４の「ユーザ特定情報」は、”Ｕ１”であり、範囲最小値情報は”６”であり、範囲最大値情報は”８”に設定されている。
【００６２】
上記図１０に示すロック二分木１５において、ロック制御部１３は、ノードＮ＿３とノードＮ＿４を一つに集約することが可能かどうか判定する。
【００６３】
判定は具体的には以下の通りである。
（１）２つのロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのロウロックオブジェクトのロック対象範囲は、”１０”と、”６から８”であり、これらは一つの連続したロック対象行範囲とはならない。
【００６４】
よって、条件（２）は不成立のため、ロック制御部１３は、ノードＮ＿３とノードＮ＿４とを一つに集約することが不可能と判定する。
【００６５】
上記図１０に示すロック二分木１５において、ロック制御部１３は、さらにノードＮ＿１とノードＮ＿４とを一つに集約することは可能かどうか判定する。
【００６６】
判定は具体的には以下の通りである。
（１）２つのノードであるロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのノードであるロウロックオブジェクトのロック対象行範囲は、”１から４”と、”６から８”であり、これらは一つの連続したロック対象行範囲とはならない。
【００６７】
よって、条件（２）は不成立のため、ロック制御部１３は、さらにノードＮ＿１とノードＮ＿４とを一つに集約することは不可能と判定し、ロック二分木１５に変更を加えない。
【００６８】
次に、図１０の状態の後に新たなＳＱＬ文ＳＱＬ５をデータベース管理部１０が受信した場合のロック二分木１５の例を図１１に示す。新たに受信したＳＱＬ文ＳＱＬ５の内容は、ユーザ”Ｕ１”が行番号９のレコードを更新するという内容である。
【００６９】
ロック制御部１３は、このＳＱＬ文ＳＱＬ５に応じて、新たなロウロックオブジェクト４＿５を生成し、これを第３世代の子ノードＮ＿４の右子ノードＮ＿５としてロック二分木１５に追加する。追加されたノードＮ＿５であるロウロックオブジェクト４＿５の「ユーザ特定情報」は、”Ｕ１”であり、範囲最小値情報は”９”であり、範囲最大値情報は”９”に設定されている。
【００７０】
上述の図１１に示すロック二分木１５において、ロック制御部１３は、ノードＮ＿５とノードＮ＿４を一つに集約することが可能かどうか判定する。
【００７１】
判定は具体的には以下の通りである。
（１）２つのノードに対応するロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのノードに対応するロウロックオブジェクトのロック対象行範囲は、”６から８”と、”９”であり、これらは一つの連続したロック対象行範囲”６から９”となる。
【００７２】
よって、２条件が成立するので、ロック制御部１３は、ノードＮ＿５とノードＮ＿４とを一つに集約することが可能と判定し、ノードＮ＿４の範囲最大値情報を”８”から”９”に書き換えるとともに、ノードＮ＿５は削除する。図１２にノードＮ＿４の範囲最大値情報を書き換えるとともに、ノードＮ＿５を削除した状態のロック二分木１５を示す。
【００７３】
図１２に示すロック二分木１５において、ロック制御部１３は、ノードＮ＿４とノードＮ＿３とを一つに集約することが可能かどうか判定する。
【００７４】
判定は具体的には以下の通りである。
（１）２つのロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのロウロックオブジェクトのロック対象行範囲は、”６から９”と”１０”であり、これらは一つの連続したロック対象行範囲”６から１０”とすることができる。
【００７５】
よって、２条件が成立するので、ロック制御部１３は、ノードＮ＿４とノードＮ＿３とを一つに集約することが可能と判定し、ノードＮ＿３であるロウロックオブジェクト４＿３の範囲最小値情報を”１０”から”６”に書き換えるとともに、ノードＮ＿４は削除する。図１３に、ノードＮ＿３であるロウロックオブジェクト４＿３の範囲最小値情報を書き換えるとともに、ノードＮ＿４を削除した状態のロック二分木１５を示す。
【００７６】
次に、図１３の状態の後にデータベース管理部１０が新たなＳＱＬ文ＳＱＬ６を受信した場合のロック二分木１５の例を図１４に示す。新たに受信したＳＱＬ文ＳＱＬ６の内容は、ユーザ”Ｕ１”が行番号５のレコードを更新するという内容である。
【００７７】
ロック制御部１３は、このＳＱＬ文ＳＱＬ６に応じて、新たなロウロックオブジェクト４＿６を生成し、これを第３世代の子ノードＮ＿３の右子ノードとしてロック二分木１５に追加する。追加されるノードＮ＿６であるロウロックオブジェクト４＿６の「ユーザ特定情報」は、”Ｕ１”であり、範囲最小値情報は”５”であり、範囲最大値情報は”５”に設定されている。
【００７８】
次に、図１４に示すロック二分木１５において、ロック制御部１３は、ノードＮ＿６とノードＮ＿３とを一つに集約することが可能かどうか判定する。
【００７９】
判定は具体的には以下の通りである。
（１）２つのノードであるロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのノードであるロウロックオブジェクトのロック対象行範囲は、”６から１０”と、”５”であり、これらは一つの連続したロック対象行範囲”５から１０”とすることができる。
【００８０】
よって、２条件が成立するので、ロック制御部１３は、ノードＮ＿６とノードＮ＿３とを一つに集約することが可能と判定し、ノードＮ＿３であるロウロックオブジェクト４＿３の範囲最小値情報を”６”から”５”に書き換えるとともに、ノードＮ＿６は削除する。図１５に、ノードＮ＿３であるロウロックオブジェクト４＿３の範囲最小値情報を書き換えるとともに、ノードＮ＿６を削除した状態のロック二分木１５を示す。
【００８１】
次に、図１５に示すロック二分木１５において、ロック制御部１３は、ノードＮ＿３とノードＮ＿１とを一つに集約することが可能かどうか判定する。
【００８２】
判定は具体的には以下の通りである。
（１）２つのノードであるロウロックオブジェクトのユーザ特定情報は、ともに”Ｕ１”であり一致する
（２）２つのノードであるロウロックオブジェクトのロック対象行範囲は、”１から４”と、”５から１０”であり、これらは一つの連続した行範囲”１から１０”とすることができる。
【００８３】
よって、２条件が成立するので、ロック制御部１３は、ノードＮ＿３とノードＮ＿１とを一つに集約することが可能と判定し、ノードＮ＿１であるロウロックオブジェクト４＿１の範囲最大値情報を”４”から”１０”に書き換えるとともに、ノードＮ＿３は削除する。図１６にノードＮ＿１であるロウロックオブジェクト４＿１の範囲最大値情報を書き換えるとともに、ノードＮ＿３を削除した状態のロック二分木１５を示す。この状態において、ロック二分木１５は、ユーザ”Ｕ１”が行番号１から１０までのレコード(行）について、ロックを取得したことを記録していることになる。
【００８４】
[ロウロックオブジェクトのデータ構成例]
次に、ロウロックオブジェクトの構成例について説明する。
【００８５】
[従来のロウロックオブジェクトのデータ構成例]
図１７に、従来の技術におけるロウロックオブジェクトのデータ構成例を示す。図１７には、ノードＮ＿Ｐ１０に対応し、ロック対象行の行番号「１３」とするロウロックオブジェクト４＿Ｐ１０と、ノードＮ＿Ｐ１０の左子ノードＮ＿Ｐ１１に対応し、ロック対象行の行番号「１０」とするロウロックオブジェクト４＿Ｐ１１と、ノードＮ＿Ｐ１０の右子ノードに対応し、ロック対象行の行番号「１５」とするロウロックオブジェクト４＿Ｐ１２とを示している。
【００８６】
従来の技術では、各ロウロックオブジェクトは、ロック対象行を特定する情報であるロック対象行情報１７０１（図中"Value"とする）と、そのロウロックオブジェクトの左子ノードを特定する情報である、左子ノード特定情報１７０２（図中"pLeft"とする）と、そのロウロックオブジェクトの右子ノードを特定する情報である、右子ノード特定情報１７０３（図中"pRight"とする）とを有している。左子ノード特定情報１７０２、右子ノード特定情報１７０３は、例えば該当するロウロックオブジェクトを示すポインタである。従来技術のロウロックオブジェクトは、ロウロックオブジェクト一つにつき、ロック対象行を一つしか扱えない。
【００８７】
[本実施の形態のロウロックオブジェクトのデータ構成例]
図１８に、本実施の形態におけるロウロックオブジェクトのデータ構成例を示す。図１８には、図１７と同様に、ノードＮ＿１０に対応する、ロック対象行の行番号「１３」とするロウロックオブジェクト４＿１０と、ノードＮ＿１０の左子ノードＮ＿１１であり、ロック対象行の行番号「１０」とするロウロックオブジェクト４＿１１と、ノードＮ＿１０の右子ノードＮ＿１２であり、ロック対象行の行番号「１５」とするロウロックオブジェクト４＿１２とを示している。
【００８８】
本実施の形態では、各ロウロックオブジェクトは、ロック対象行情報に範囲を持たせたことを特徴とする。すなわち、従来の技術ではロック対象行を特定する情報はロック対象行情報１７０１のみであったのに対して、本実施の形態では、ロック対象行範囲の最小値を特定する情報である範囲最小値情報１８００（図中"ＶＬ"とする）と、ロック対象行範囲の最大値を特定する情報である範囲最大値情報１８０１（図中"ＶＲ"とする）とを有する。よって、一つのロウロックオブジェクトで複数のロック対象行を扱えるようになる。なお、本実施の形態にかかるロウロックオブジェクトは、さらにそのロウロックオブジェクトの左子ノードを特定する情報である、左子ノード特定情報１８０２（図中"pLeft"とする）と、そのロウロックオブジェクトの右子ノードを特定する情報である、右子ノード特定情報１８０３（図中"pRight"とする）とを有している。左子ノード特定情報１８０２、右子ノード特定情報１８０３は、例えば該当するロウロックオブジェクトを示すポインタである。これは、従来の技術と同様である。また、本実施の形態にかかるロウロックオブジェクトはユーザ特定情報（図略）をその構成要素として有している。
【００８９】
図１９に、ロック対象行範囲が行番号１１から行番号１３までである場合の、従来の技術におけるロウロックオブジェクト４のデータ構成例を示す。従来の技術においては、ロック対象行の行番号「１２」とするロウロックオブジェクト４＿Ｐ１０と、ロウロックオブジェクト４＿Ｐ１０であるノードＮ＿Ｐ１０の左子ノードＮ＿Ｐ１１となる、ロック対象行を行番号「１１」とするロウロックオブジェクト４＿Ｐ１１と、ロウロックオブジェクト４＿Ｐ１０であるノードＮ＿Ｐ１０の右子ノードＮ＿Ｐ１２であり、ロック対象行を行番号「１３」とするロウロックオブジェクト４＿Ｐ１２との、３つのロウロックオブジェクト４からなる二分木が必要となる。
【００９０】
一方、本実施の形態におけるロウロックオブジェクト４を使用して、ロック対象行の範囲が行番号１１から行番号１３までである場合の、ロウロックオブジェクト４のデータ構成例を示す。図２０に、本実施の形態におけるロウロックオブジェクトを使用した場合、一つのロウロックオブジェクト４＿１３のみでロック対象行範囲を行番号１１から行番号１３（すなわち、行番号１１、行番号１２、行番号１３の３行分）とすることを記述できることを示す。ロウロックオブジェクト４＿１３の範囲最小値情報１８００には、値「１１」が格納され、範囲最大値情報１８０１には、値「１３」が格納されている。これは、ノードＮ＿１３のみで、図１９に示した３つのノード、ノードＮ＿Ｐ１０、Ｎ＿Ｐ１１、Ｎ＿Ｐ１２と同一の内容を記述できることを意味する。
【００９１】
[ノードＮ（ロウロックオブジェクト４）の追加]
次に、ロック二分木へのノードの追加はどのように行われるのかについて述べる。まず、従来の技術におけるノードの追加を説明する。図２１は、図１７に示したロック二分木１５に新たにロック対象行の行番号を「１１」とするノードＮ＿Ｐ１４（ロウロックオブジェクト４＿Ｐ１４）が追加された状態を示す図である。図２１に示す例では、葉ノードであるノードＮ＿Ｐ１１（ロウロックオブジェクト４＿Ｐ１１）及びノードＮ＿Ｐ１２（ロウロックオブジェクト４＿Ｐ１２）のうち、「１１」に近いロック対象行１７０１の値を有するノードＮ＿Ｐ１１（ロウロックオブジェクト４＿Ｐ１１）に新たなノードＮ＿Ｐ１４（ロウロックオブジェクト４＿Ｐ１４）が子ノードとして追加される。親ノードであるノードＮ＿Ｐ１１（ロウロックオブジェクト４＿Ｐ１１）のロック対象行１７０１の値は「１０」であり、追加される新たなノードＮ＿Ｐ１４（ロウロックオブジェクト４＿Ｐ１４）のロック対象行１７０１の値「１１」で、値「１０」より大きいので、親ノードであるノードＮ＿Ｐ１１（ロウロックオブジェクト４＿Ｐ１１）の右子ノードとして追加される。すなわち、親ノードであるノードＮ＿Ｐ１１（ロウロックオブジェクト４＿Ｐ１１）の右子ノード特定情報１７０３に、追加された新たなノードＮ＿Ｐ１４（ロウロックオブジェクト４＿Ｐ１４）を特定する情報が格納される。
【００９２】
次に、本実施の形態におけるロウロックオブジェクトの追加を説明する。図２２は、図１８に示したロック二分木１５に新たにロック対象行の行番号を「１１」とするノードＮ＿１４（ロウロックオブジェクト４＿１４）が追加された状態を示す図である。図２２に示す例では、葉ノードであるノードＮ＿１１（ロウロックオブジェクト４＿１１）及びノードＮ＿１２（ロウロックオブジェクト４＿１２）のうち、「１１」に近いロック対象行範囲、より詳しくは範囲最小値情報１８００の値又は範囲最大値情報１８０１の値を有するノードＮ＿１１（ロウロックオブジェクト４＿１１）に新たなノードＮ＿１４（ロウロックオブジェクト４＿１４）が子ノードとして追加される。すなわち、図２２に示す例では、親ノードとして選択されたノードＮ＿１１（ロウロックオブジェクト４＿１１）の右子ノード特定情報１８０３に、追加された新たなノードＮ＿１４（ロウロックオブジェクト４＿１４）を特定する情報が格納される。
【００９３】
[ノードの集約]
本実施の形態では、異なる２つのノードＮ（ロウロックオブジェクト４）のロック対象行範囲が連続する一つの範囲に結合可能な場合、これら２つのノードＮ（ロウロックオブジェクト４）を一つのノードＮ（ロウロックオブジェクト４）に集約することができる。図２３Ａに、図２２に示したノードＮ＿１４（ロウロックオブジェクト４＿１４）とノードＮ＿１１（ロウロックオブジェクト４＿１１）とを集約した状態の例を示す。集約される前のノードＮ＿１１（ロウロックオブジェクト４＿１１）の範囲最大値情報１８０１は「１０」であり、集約される前のノードＮ＿１４（ロウロックオブジェクト４＿１４）の範囲最小値情報１８００は「１１」であるので、この２つのロウロックオブジェクト４のロック対象行範囲「１０から１１まで」という一つのロック対象行範囲とすることができる。
【００９４】
２つのノードＮ（ロウロックオブジェクト４）を集約する処理であるノード集約処理は、２つのノードＮのうち下位のノードＮは削除し、上位のノードの範囲最小値情報１８００及び／又は範囲最大値情報１８０１を書き換えることにより行われる。図２３の例では、一つのロック対象行範囲「１０から１１まで」を示すように、上位のノードＮ＿１１（ロウロックオブジェクト４＿１１）の範囲最大値情報１８０１の値が「１０」から「１１」に書き換えられ、ノードＮ＿１４（ロウロックオブジェクト４＿１４）は削除される。これで、２つのノードＮ＿１４、Ｎ＿１１を集約する処理が完了する。
【００９５】
図２３Ｂにノード集約処理の一例を示すフローチャートを掲げる。以下、このフローチャートを参照しながら、ノード集約処理の内容を説明する。
【００９６】
ノード集約処理において、データベース装置２、より詳しくはロック制御部１３は、ロック二分木１５に新規登録したノードをＮとする（Ｓ２３Ｂ＿１）。次にデータベース装置２、より詳しくはロック制御部１３は、Ｎの親ノードがロック二分木１５に存在するか否かを判定する（Ｓ２３Ｂ＿２）。親ノードが存在しないと判定した場合（Ｓ２３Ｂ＿２，Ｎｏ）、データベース装置２、より詳しくはロック制御部１３はノード集約処理をそのまま終了する。一方、親ノードが存在すると判定した場合（Ｓ２３Ｂ＿２，Ｙｅｓ）、データベース装置２、より詳しくはロック制御部１３はＮの親ノードをＰとする（Ｓ２３Ｂ＿３）。
【００９７】
次に、データベース装置２、より詳しくはロック制御部１３はＮをＰに集約（マージ）できるか否かを判定する（Ｓ２３Ｂ＿４）。ＮをＰに集約（マージ）できると判定した場合（Ｓ２３Ｂ＿４、Ｙｅｓ）、データベース装置２、より詳しくはロック制御部１３は集約の結果残ったＰを新たなＮとし（Ｓ２３Ｂ＿５）、後述するステップＳ２３Ｂ_６に進む。一方、ＮをＰに集約（マージ）できないと判定した場合（Ｓ２３Ｂ＿４、Ｎｏ）、データベース装置２、より詳しくはロック制御部１３は前述のステップＳ２３Ｂ＿５を行わずに後述するステップＳ２３Ｂ_６に進む。
【００９８】
ステップＳ２３Ｂ＿６において、データベース装置２、より詳しくはロック制御部１３はＰの親ノードがロック二分木１５に存在するか否かを判定する（Ｓ２３Ｂ＿６）。Ｐの親ノードがロック二分木１５に存在しないと判定した場合（Ｓ２３Ｂ＿６、Ｎｏ）、データベース装置２、より詳しくはロック制御部１３はそのままノード集約処理を終了する。一方、Ｐの親ノードがロック二分木１５に存在すると判定した場合（Ｓ２３Ｂ＿６、Ｙｅｓ）、データベース装置２、より詳しくはロック制御部１３はＰの親ノードを新たなＰとし（Ｓ２３Ｂ＿７）、その後前述のステップＳ２３Ｂ_４に戻って、ノード集約処理を続行する。
【００９９】
以上で、ノード集約処理の内容の説明を終了する。
【０１００】
図２３Ｃに、ノード集約処理の対象となるノードの例を示す。図２３Ｃに示したロック二分木は、ノードＡ１と、ノードＡ１の子ノードであるノードＡ２及びノードＡＸ、ノードＡ２の子ノードであるノードＡ３及びノードＡＹ、ノードＡ３の子ノードであるノードＡ４から構成されており、ノードＡ４の子ノードとして、ノードＡ５が新規登録された。
【０１０１】
この例では、新規登録されたＡ５、あるいはＡ５やその後集約の結果残ったノードと集約の相手とされるのは、Ａ４，Ａ３，Ａ２、Ａ１の親子関係を有するノードであって、兄弟関係であるノードＡＸ，ＡＹは集約の対象とはされない。
【０１０２】
本実施の形態のように、２つのノードＮ（ロウロックオブジェクト４）を集約する処理であるノード集約処理を行うことが可能とすると、以下のような利点が得られる。
【０１０３】
図２４は、あるロック二分木１５を示す図である。このロック二分木１５についてノード集約処理を行った結果、図２５に示すロック二分木１５が生成されたものとする。
【０１０４】
ノードを集約する処理を行う前のロック二分木１５(図２４参照)において、新たなノードをロック二分木１５に追加するには、ルートノードＮ＿０から最下層のノードＮ＿Ｂｏｔｔｏｍまで５ノードの探索が必要であるが、ノードを集約する処理を行った後のロック二分木１５(図２５参照)においては、新たなノードを追加するには、ルートノードＮ＿０から最下層のノードＮ＿Ｂｏｔｔｏｍまで２ノード探索すればよい。
【０１０５】
また、ノードを集約する処理を行う前の状態（図２４参照）でロック二分木１５を記憶するには、少なくとも１１ノードＮ（ロウロックオブジェクト４）分の記憶容量が必要となるのに対して、ノードを集約する処理を行った後の状態（図２５参照）では、ロック二分木１５を記憶するには４ノードＮ（ロウロックオブジェクト４）分の記憶容量で足りる。このように、ノードを集約する処理が可能となることで、ノードの追加、探索などの処理量を低減させることが可能となるとともに、ロック二分木１５を記憶するために必要な記憶容量を減少させることも可能となる。
【０１０６】
[第１の実施例]
次に、本実施の形態の第１の実施例について説明する。第１の実施例は、ロック対象行を範囲で管理することを特徴とする。
【０１０７】
第１の実施例にかかるマルチユーザ・データベースシステム１、データベース装置２、データベース管理部１０の構成は、前述の第１の実施の形態と同じ（図１、図２参照）であり、第１の実施例にかかるデータベース管理部１０の動作例も前述の第１の実施の形態と同じ（図３参照）であるので、マルチユーザ・データベースシステム１、データベース装置２、データベース管理部１０の構成及びその動作については、説明を省略する。
【０１０８】
[ロック二分木へのノード追加方法]
ここで、ロック制御部１３が新たなデータをロックする処理（図３、Ｓ４参照）において、更新対象の行に対応するノードＮをロック二分木１５に加える処理であるノード追加処理について述べる。
【０１０９】
図２６は、ノード追加処理の一例を示すフローチャートである。なお、図２６において、「Ｐ」は、現在処理対象としているロック二分木に属するノードＮ（ターゲットノードと呼ぶ；ロウロックオブジェクト４）を示す情報であり、「ｋ」はノードＮ（ロウロックオブジェクト４）に対応するユーザを示す情報であり、「ｖ」は新たにロックを取得したい行番号（以下、「追加ロック対象行番号」という）を示す情報である。
【０１１０】
ノード追加処理を開始すると、ロック制御部１３は現在の処理対象とするノードＮ（ロウロックオブジェクト４）を示す情報Ｐが空か否かを判定する（Ｓ２６０１）。ノードＮ（ロウロックオブジェクト４）を示す情報Ｐが空であると判定した場合（Ｓ２６０１、Ｙｅｓ）、現在の処理対象とするノードＮ（ロウロックオブジェクト４）を示す情報Ｐに、更新対象として更新を要求された行に対応する新たなノードＮ（ロウロックオブジェクト４）を追加し（Ｓ２６０２）、その後ノード追加処理を終了する。
【０１１１】
一方、現在の処理対象とするノードＮ（ロウロックオブジェクト４）が存在する（空でない）と判定した場合（Ｓ２６０１、Ｎｏ）、ロック制御部１３はそのノードＮ（ロウロックオブジェクト４）の範囲最大値情報（１８０１）ｖＲが追加ロック対象行番号ｖより小さいか否かを判定する（Ｓ２６０３）。
【０１１２】
範囲最大値情報ｖＲが追加ロック対象行番号ｖより小さいと判定した場合（Ｓ２６０３、Ｙｅｓ）、ロック制御部１３はそのノードＮ（ロウロックオブジェクト４）の右子ノード特定情報（１８０３）ｐＲが空（ＮＵＬＬ）であるか否かを判定する（Ｓ２６０４）。右子ノード特定情報ｐＲが空（ＮＵＬＬ）であると判定した場合（Ｓ２６０４、Ｙｅｓ）、ロック制御部１３は、現在処理対象のノードの右子ノード特定情報に、更新対象として更新を要求された行に対応する新たなノードＮ（ロウロックオブジェクト４）を追加し（Ｓ２６０９）、その後ノード追加処理を終了する。
【０１１３】
一方、ステップＳ２６０４において右子ノード特定情報ｐＲが空（ＮＵＬＬ）でないと判定した場合（Ｓ２６０４、Ｎｏ）、ターゲットノードを示す変数Ｐに右子ノード特定情報ｐＲを代入する（Ｓ２６０５）。これで、新たなターゲットノードは現在のターゲットノードからその右子ノードに変更される。その後ステップＳ２６０３に戻りノード追加処理が続行される。
【０１１４】
前述のステップＳ２６０３の説明に戻る。ステップＳ２６０３において、範囲最大値情報ｖＲが追加ロック対象行番号ｖより小さくないと判定した場合（Ｓ２６０３、Ｎｏ）、ロック制御部１３は、ターゲットノードＮ（ロウロックオブジェクト４）の範囲最小値情報（１８００）ｖＬが追加ロック対象行番号ｖより大きいか否かを判定する（Ｓ２６０６）。範囲最小値情報ｖＬが追加ロック対象行番号ｖより大きくないと判定した場合（Ｓ２６０６、Ｎｏ）、ロック制御部１３はターゲットノードＮ（ロウロックオブジェクト４）のユーザ特定情報ｋと、ノード追加を要求しているユーザとが一致するか否かを判定する（Ｓ２６１０）、ターゲットノードＮ（ロウロックオブジェクト４）のユーザ特定情報ｋと、ノード追加を要求しているユーザとが一致すると判定した場合（Ｓ２６１０、Ｙｅｓ）、ロック制御部１３はそのユーザｋによる行番号ｖのデータの更新を許可する（Ｓ２６１２）。その後ロック制御部１３はノード追加処理を終了する。一方、ターゲットノードＮ（ロウロックオブジェクト４）のユーザ特定情報ｋと、ノード追加を要求しているユーザとが一致しないと判定した場合（Ｓ２６１０、Ｎｏ）、ロック制御部１３はそのユーザｋによる行番号ｖのデータの更新を許可しない（Ｓ２６１１）。その後ロック制御部１３はノード追加処理を終了する。
【０１１５】
前述のステップＳ２６０６の説明に戻る。ステップＳ２６０６において、範囲最小値情報（１８０２）ｖＬが追加ロック対象行番号ｖより大きいと判定した場合（Ｓ２６０６、Ｙｅｓ）、ロック制御部１３はそのノードＮ（ロウロックオブジェクト４）の左子ノード特定情報ｐＬが空（ＮＵＬＬ）であるか否かを判定する（Ｓ２６０７）。左子ノード特定情報ｐＬが空（ＮＵＬＬ）であると判定した場合（Ｓ２６０７、Ｙｅｓ）、ロック制御部１３は、現在処理対象のノードの左子ノードとして、新たなノードを追加する（Ｓ２６１３）。その後ロック制御部１３はノード追加処理を終了する。
【０１１６】
一方、ステップＳ２６０７において右子ノード特定情報ｐＬが空（ＮＵＬＬ）でないと判定した場合（Ｓ２６０７、Ｎｏ）、ターゲットノードを示す変数Ｐに左子ノード特定情報ｐＬを代入する。これで、新たなターゲットノードは現在のターゲットノードからその左子ノードに変更される。その後ステップＳ２６０３に戻りノード追加処理が続行される。
【０１１７】
[ノード追加処理の具体例]  
ノード追加処理の具体例を示す。図２７は、ロック二分木１５の一例を示す図である。このロック二分木１５は、ノード追加処理が行われる前においてノードＮ＿２７＿１からノードＮ＿２７＿４で構成されているとする。ノードＮ＿２７＿１は、ユーザ特定情報を「ｋ１」とし、範囲最小値情報１８００を「２０」、範囲最大値情報１８０１を「２１」とするロウロックオブジェクト４である。ノードＮ＿２７＿２は、ユーザ特定情報を「ｋ１」とし、範囲最小値情報１８００を「１１」、範囲最大値情報１８０１を「１２」とするロウロックオブジェクト４であり、ノードＮ＿２７＿１の左子ノードである。ノードＮ＿２７＿３は、ユーザ特定情報を「ｋ２」とし、範囲最小値情報１８００を「１６」、範囲最大値情報１８０１を「１８」とするロウロックオブジェクト４であり、ノードＮ＿２７＿２の右子ノードである。ノードＮ＿２７＿４は、ユーザ特定情報を「ｋ１」とし、範囲最小値情報１８００を「１４」、範囲最大値情報１８０１を「１５」とするロウロックオブジェクト４であり、ノードＮ＿２７＿３の左子ノードである。
【０１１８】
ここで、ユーザ「ｋ１」から行番号１３についての新たな更新要求２７０１があり、この更新要求２７０１に応じて行番号１３についてロックを行うためのノード追加処理が行われるものとする。このノード追加処理において、当初のターゲットノードはノードＮ＿２７＿１に設定されるので、処理は前述のステップＳ２６０３に進む（Ｓ２６０１，Ｙｅｓ）。ステップＳ２６０３において、ノードＮ＿２７＿１の範囲最大値情報１８０１ｖＲ（＝２１）は入力値ｖ（＝１３）より小さくないので、ステップＳ２６０６に進む（Ｓ２６０３、Ｎｏ）。ステップＳ２６０６において、ノードＮ＿２７＿１の範囲最小値情報１８００ｖＬ（＝２０）は入力値ｖ（＝１３）より大きいので、ステップＳ２６０７に進む（Ｓ２６０６，Ｙｅｓ）。ステップＳ２６０７において、ノードＮ＿２７＿１の左子ノード特定情報ｐＬ（＝ノードＮ＿２７＿２）は空（ＮＵＬＬ）でないので、ステップＳ２６０８に進む（Ｓ２６０７、Ｎｏ）。ステップＳ２６０８において、ターゲットＰにノードＮ＿２７＿１の左子ノード特定情報ｐＬ（＝ノードＮ＿２７＿２）が代入される。これで新たなターゲットはノードＮ＿２７＿２となる。
【０１１９】
処理は再びステップＳ２６０３に戻る。ステップＳ２６０３において、ノードＮ＿２７＿２の範囲最大値情報１８０１ｖＲ（＝１２）は入力値ｖ（＝１３）より小さいので、ステップＳ２６０４に進む（Ｓ２６０３、Ｙｅｓ）。ステップＳ２６０４において、ノードＮ＿２７＿２の右子ノード特定情報ｐＲ（＝ノードＮ＿２７＿３）は空（ＮＵＬＬ）でないので、ステップＳ２６０５に進む（Ｓ２６０４、Ｎｏ）。ステップＳ２６０５において、ターゲットＰにノードＮ＿２７＿２の右子ノード特定情報ｐＲ（＝ノードＮ＿２７＿３）が代入される。これで新たなターゲットＰはノードＮ＿２７＿３となる。
【０１２０】
処理はまた再びステップＳ２６０３に戻る。ステップＳ２６０３において、ノードＮ＿２７＿３の範囲最大値情報１８０１ｖＲ（＝１８）は入力値ｖ（＝１３）より小さくないので、ステップＳ２６０６に進む（Ｓ２６０３、Ｎｏ）。ステップＳ２６０６において、ノードＮ＿２７＿３の範囲最小値情報１８００ｖＬ（＝１６）は入力値ｖ（＝１３）より大きいので、ステップＳ２６０７に進む（Ｓ２６０６，Ｙｅｓ）。ステップＳ２６０７において、ノードＮ＿２７＿３の左子ノード特定情報ｐＬ（＝ノードＮ＿２７＿４）は空（ＮＵＬＬ）でないので、ステップＳ２６０８に進む（Ｓ２６０７、Ｎｏ）。ステップＳ２６０８において、新たなターゲットＰにノードＮ＿２７＿３の左子ノード特定情報ｐＬ（＝ノードＮ＿２７＿４）が代入される。これで新たなターゲットＰはノードＮ＿２７＿４となる。
【０１２１】
処理は再度ステップＳ２６０３に戻る。ステップＳ２６０３において、ノードＮ＿２７＿４の範囲最大値情報１８０１ｖＲ（＝１５）は入力値ｖ（＝１３）より小さくないので、ステップＳ２６０６に進む（Ｓ２６０３、Ｎｏ）。ステップＳ２６０６において、ノードＮ＿２７＿４の範囲最小値情報１８００ｖＬ（＝１４）は入力値ｖ（＝１３）より大きいので、ステップＳ２６０７に進む（Ｓ２６０６，Ｙｅｓ）。ステップＳ２６０７において、ノードＮ＿２７＿４の左子ノード特定情報ｐＬ（＝ノードＮ＿２７＿４）は空（ＮＵＬＬ）なので、ステップＳ２６０８に進む（Ｓ２６０７、Ｙｅｓ）。ステップＳ２６０９において、ノードＮ＿２７＿４の左子ノード特定情報ｐＬ（＝ノードＮ＿２７＿４）に、ユーザ「ｋ１」による行番号「１３」に関する更新要求に対応するノードＮ＿２７＿５を特定する情報が格納される。これによりノードＮ＿２７＿１からノードＮ＿２７＿４で構成されたロック二分木１５に新たなノードＮ＿２７＿５が追加されたことになる。
【０１２２】
[ノード集約処理の具体例]
ロック制御部１３は、図２６に示したロック二分木１５に含まれるノードＮについて、ノード集約処理を実行する。
【０１２３】
まず、ロック制御部１３は、葉ノードであるノードＮ＿２７＿５と、その親ノードであるノードＮ＿２７＿４とを一つの連続したロック対象行範囲を有するノードに集約できるか否かを判断する。図２８に、葉ノードであるノードＮ＿２７＿５と、その親ノードであるノードＮ＿２７＿４との集約が判断されている状態を示す。
【０１２４】
まず、ノードＮ＿２７＿５のユーザ特定情報は「ｋ１」であり、もう一方のノードＮ＿２７＿４のユーザ特定情報も「ｋ１」であり、両者のユーザ特定情報は一致するので、集約可能条件を満たすとロック制御部１３は判断する。
【０１２５】
次にロック制御部１３は、葉ノードであるノードＮ＿２７＿５のロック対象行範囲は「１３、１３」であり、ノードＮ＿２７＿４のロック対象行範囲は「１４、１５」であることから、この２つのロック対象行範囲は、一つの連続したロック対象行範囲「１３、１５」を構成するので、ロック制御部１３は、下位ノードであるノードＮ＿２７＿５を削除するとともに、ノードＮ＿２７＿４のロック対象行範囲を「１４、１５」から「１３、１５」に書き換えることにより、ノードＮ＿２７＿５とノードＮ＿２７＿４との集約を完了する。図２９に、葉ノードであるノードＮ＿２７＿５と、その親ノードであるノードＮ＿２７＿４との集約が完了した状態を示す。なお、図中点線で示されているノードＮ＿２７＿５は、削除済みであることを意味する。
【０１２６】
ロック制御部１３は、ノードＮ＿２７＿５とノードＮ＿２７＿４との集約が完了したのち、さらにノード集約処理を続行する。ロック制御部１３は、更新されたノードであるノードＮ＿２７＿４と、その親ノードであるノードＮ＿２７＿３とを一つの連続したロック対象行範囲を有するノードに集約できるか否かを判断する。
【０１２７】
ロック制御部１３は、ノードＮ＿２７＿４のユーザ特定情報は「ｋ１」であり、もう一方のノードＮ＿２７＿３のユーザ特定情報ｊは「ｋ２」であり、両者のユーザ特定情報は一致しないので、集約可能条件を満たさないとロック制御部１３は判断する。
【０１２８】
ロック制御部１３は、ノードＮ＿２７＿４とノードＮ＿２７＿３との集約は不可能であると判断したのち、さらにノード集約処理を続行する。
【０１２９】
ロック制御部１３は、葉ノードであるノードＮ＿２７＿４と、その親ノードの親ノードであるノードＮ＿２７＿２とを一つの連続したロック対象行範囲を有するノードに集約できるか否かを判断する。図３０に、葉ノードであるノードＮ＿２７＿５と、その２世代上のノードＮ＿２７＿２との集約が判断されている状態を示す。
【０１３０】
ロック制御部１３は、ノードＮ＿２７＿４のユーザ特定情報は「ｋ１」であり、もう一方のノードＮ＿２７＿２のユーザ特定情報も「ｋ１」であり、両者のユーザ特定情報は一致するので、集約可能条件を満たすとロック制御部１３は判断する。
【０１３１】
次にロック制御部１３は、葉ノードであるノードＮ＿２７＿４のロック対象行範囲は「１３、１５」であり、ノードＮ＿２７＿２のロック対象行範囲は「１１、１２」であることから、この２つのロック対象行範囲は、一つの連続したロック対象行範囲「１１、１５」を構成するので、ロック制御部１３は、下位ノードであるノードＮ＿２７＿４を削除するとともに、ノードＮ＿２７＿２のロック対象行範囲を「１１、１２」から「１１、１５」に書き換えることにより、ノードＮ＿２７＿４とノードＮ＿２７＿２との集約を完了する。図３１に、葉ノードであるノードＮ＿２７＿４と、その２世代上のノードであるノードＮ＿２７＿２との集約が完了した状態を示す。なお、図中点線で示されているノードＮ＿２７＿４は、削除済みであることを意味する。
【０１３２】
ロック制御部１３は、同様に更新されたノードであるノードＮ＿２７＿２と、その親ノードの親ノードであるノードＮ＿２７＿１についても同様にノードの集約を試みるが、集約不可能であり、ロック二分木の頂点まで集約処理を実施したので、ロック制御部１３は、ロック二分木１５についてのノード集約処理を図３１の状態で終了する。
【０１３３】
[第２の実施例]
次に第２の実施例について説明する。第２の実施例の特徴は、ロック対象行を範囲で取り扱うことを可能とする点にある。
【０１３４】
第２の実施例にかかるマルチユーザ・データベースシステム１、データベース装置２、データベース管理部１０の構成は、前述の第１の実施の形態と同じ（図１、図２参照）であるので、構成の詳細な説明は省略する。
【０１３５】
第２の実施例にかかるデータベース管理部１０の動作例を説明する。図３２はデータベース管理部１０の主たる動作の一つである、ＳＱＬ文実行処理の一例を示すフローチャートである。
【０１３６】
ＳＱＬ文実行処理において、データベース管理部１０、より詳しくはＳＱＬ文解析部１１はアプリケーションサーバ６０からＳＱＬ文を受信する（Ｓ３２０１）。
【０１３７】
次にデータベース管理部１０、より詳しくはＳＱＬ文解析部１１は、受信したＳＱＬ文を解析して、そのＳＱＬ文が構成する命令が、データベースの更新を伴う更新系命令であるか否かを判定する（Ｓ３２０２）。その命令が更新系命令でないと判定した場合（Ｓ３２０２，Ｎｏ）、ＳＱＬ文解析部１１は、その命令をデータ制御部１２に渡し、データ制御部１２はその命令を実行し（Ｓ３２０７）、その後ＳＱＬ文実行処理を終了する。一方、その命令が更新系命令であると判定した場合（Ｓ３２０２，Ｙｅｓ）、ＳＱＬ文解析部１１はデータ制御部１２にその命令を渡す。
【０１３８】
データ制御部１２はその命令に基づいて、データベース３０における更新対象の行を決定し（Ｓ３２０３）、さらに更新対象の行が複数である場合に複数の更新対象の行を一つの連続した範囲として集約することが可能か否かを判定し、可能であれば、一つの連続した範囲を決定する。更新対象の行を特定する情報（例えば、行番号又はその範囲、レコード番号又はその範囲など、）をロック制御部１３に渡す。例えば、データ制御部１２はＷｈｅｒｅ条件やＩＮＤＥＸなどを使い、更新対象の行を集約する。例えば、更新対象の行が１から１０までであるとすると、更新対象の行範囲を「１、１０」として扱うようにして良い。この行範囲は範囲最小値情報ｖＬ＝１、範囲最大値情報ｖＲ＝１０とするロウロックオブジェクト４などとして生成される。
【０１３９】
ロック制御部１３は、受け取った更新対象の行範囲を特定する情報に基づいて、データロック情報記憶部１４に記憶されているロック二分木１５に、更新対象の行範囲に対応するノードＮ（ロウロックオブジェクト４）を加えて該当行範囲のロックを行う（Ｓ３２０４）。その後ロック制御部１３はデータ制御部１２に更新対象の行範囲のロックが行われたことを通知する。
【０１４０】
更新対象の行範囲のロックが行われたことを通知されたデータ制御部１２は、データベース３０における更新対象の行範囲のデータを前述の更新系命令の内容に基づいて書き換える（更新する）（Ｓ３２０５）。
【０１４１】
次に、データ制御部１２は、ステップＳ３２０３において決定された更新対象の行が全てステップＳ３２０４からステップＳ３２０５で処理されたか否かを判定する（Ｓ３２０６）。全ての更新対象の行範囲がステップＳ３２０４からステップＳ３２０５で処理されていないと判定した場合（Ｓ３２０６、Ｎｏ）、データ制御部１２は更新対象の行範囲のうち、未処理の行範囲を一つ選択して、選択した行範囲を特定する情報をロック制御部１３に渡す。ロック制御部１３は受け取った更新対象の行範囲を特定する情報に基づいて、データロック情報記憶部１４に記憶されているロック二分木１５に、更新対象の行範囲に対応するノードＮを加えて該当行のロックを行う（Ｓ３２０４）。一方、ステップＳ３２０６において、全ての更新対象の行がステップＳ３２０４からステップＳ３２０５で処理されたと判定した場合（Ｓ３２０６、Ｙｅｓ）、データベース管理部１０はＳＱＬ文実行処理を終了する。
【０１４２】
[ロック二分木へのノード追加処理]
ここで、ロック制御部１３が該当の行をロックする処理（Ｓ３２０４参照）において、更新対象の行に対応するノードＮをロック二分木１５に加える処理であるノード追加処理について述べる。
【０１４３】
図３３は、ノード追加処理の例を示すフローチャートである。なお、図３３において、「Ｐ」は、現在処理対象としているロック二分木に属するノードＮ（ロウロックオブジェクト４）を示す情報であり、「ｋ」はノードＮ（ロウロックオブジェクト４）に対応するユーザを示す情報であり、「ｖＲ」は行範囲中の最大値を示す情報である範囲最大値情報１８０１であり、「ｖＬ」は行範囲中の最小値を示す情報である範囲最小値情報１８００である。また、「ｐＬ」は左子ノード特定情報１８０２であり、「ｐＲ」は右子ノード特定情報１８０３である。
【０１４４】
ノード追加処理を開始すると、ロック制御部１３は現在の処理対象とするノードＮ（ロウロックオブジェクト４）を示す情報Ｐが空か否かを判定する（Ｓ３３０１）。ノードＮ（ロウロックオブジェクト４）を示す情報Ｐが空であると判定した場合（Ｓ３３０１、Ｙｅｓ）、現在の処理対象とするノードＮ（ロウロックオブジェクト４）を示す情報Ｐに、更新対象として更新を要求された行に対応する新たなノードＮ（ロウロックオブジェクト４）を追加し（Ｓ３３０２）、その後ノード追加処理を終了する。
【０１４５】
一方、現在の処理対象とするノード（ロウロックオブジェクト；以下「現在処理対象ノードＮ（ロウロックオブジェクト４）」と呼ぶ）が存在する（空でない）と判定した場合（Ｓ３３０１、Ｎｏ）、ロック制御部１３は現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲが更新対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬより小さいか否かを判定する（Ｓ３３０３）。
【０１４６】
現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲが更新対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬより小さいと判定した場合（Ｓ３３０３、Ｙｅｓ）、ロック制御部１３は現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲの右子ノード特定情報ｐＲが空（ＮＵＬＬ）であるか否かを判定する（Ｓ３３０４）。現在処理対象ノードＮ（ロウロックオブジェクト４）の右子ノード特定情報ｐＲが空（ＮＵＬＬ）であると判定した場合（Ｓ３３０４、Ｙｅｓ）、ロック制御部１３は、現在処理対象ノードＮ（ロウロックオブジェクト４）の右子ノード特定情報ｐＲに、更新対象ノードＮ（ロウロックオブジェクト４）を追加し（Ｓ３３１３）、その後ノード追加処理を終了する。
【０１４７】
一方、ステップＳ３３０４において、現在処理対象ノードＮ（ロウロックオブジェクト４）の右子ノード特定情報ｐＲが空（ＮＵＬＬ）でないと判定した場合（Ｓ３３０４、Ｎｏ）、現在処理対象ノードＮ（ロウロックオブジェクト４）を示す変数Ｐに、現在処理対象ノードＮ（ロウロックオブジェクト４）の右子ノード特定情報ｐＲを代入する（Ｓ３３０５）。これで、新たなターゲットノードは現在のターゲットノードからその右子ノードに変更される。その後ステップＳ３３０３に戻りノード追加処理が続行される。
【０１４８】
前述のステップＳ３３０３の説明に戻る。ステップＳ３３０３において、現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲが更新対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬより小さくないと判定した場合（Ｓ３３０３、Ｎｏ）、ロック制御部１３は、現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬが更新対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲより大きいか否かを判定する（Ｓ３３０６）。現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬが更新対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲより大きくないと判定した場合（Ｓ３３０６、Ｎｏ）、ロック制御部１３は現在処理対象ノードＮ（ロウロックオブジェクト４）のユーザ特定情報ｋと、更新対象ノード追加を要求しているユーザとが一致するか否かを判定する（Ｓ３３１０）、現在処理対象ノードＮ（ロウロックオブジェクト４）のユーザ特定情報ｋと、更新対象ノード追加を要求しているユーザとが一致すると判定した場合（Ｓ３３１０、Ｙｅｓ）、ロック制御部１３は現在処理対象ノードＮ（ロウロックオブジェクト４）を特定する情報Ｐを維持しながら、新たな更新対象ノードを生成するため以下の（１）（２）の処理をそれぞれ行う。
（１）更新対象ノードの範囲最小値情報ｖＬをそのままとし、更新対象ノードの範囲最大値情報ｖＲに現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬから１だけ減算した値を格納する。
（２）更新対象ノードの範囲最小値情報ｖＬに現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲに１だけ加算した値を格納する。更新対象ノードの範囲最大値情報ｖＲはそのままとする。
（１）（２）で生成された新たな更新対象ノードでそれぞれ、現在処理対象ノードＮから処理を再開する。このとき、生成された更新対象ノードのｖＬとｖＲの関係が「ｖＬ＜＝ｖＲ」で無い場合は、すでにロック取得できていると判断できるので処理を行う必要が無い。
ステップＳ３３１２の後ロック制御部１３はノード追加処理を終了する。
【０１４９】
一方、ステップＳ３３１０においてターゲットノードＮ（ロウロックオブジェクト４）のユーザ特定情報ｋと、更新対象ノード追加を要求しているユーザとが一致しないと判定した場合（Ｓ３３１０、Ｎｏ）、ロック制御部１３はそのユーザｋによる行範囲のデータの更新を許可しない（Ｓ３３１１）。その後ロック制御部１３はノード追加処理を終了する。
【０１５０】
前述のステップＳ３３０６の説明に戻る。ステップＳ３３０６において、現在処理対象ノードＮ（ロウロックオブジェクト４）の範囲最小値情報ｖＬが更新対象ノードＮ（ロウロックオブジェクト４）の範囲最大値情報ｖＲより大きいと判定した場合（Ｓ３３０６、Ｙｅｓ）、ロック制御部１３は現在処理対象ノードＮ（ロウロックオブジェクト４）の左子ノード特定情報ｐＬが空（ＮＵＬＬ）であるか否かを判定する（Ｓ３３０７）。左子ノード特定情報ｐＬが空（ＮＵＬＬ）であると判定した場合（Ｓ３３０７、Ｙｅｓ）、ロック制御部１３は、現在処理対象ノードの左子ノードとして、更新対象ノードを追加する（Ｓ３３０９）。その後ロック制御部１３はノード追加処理を終了する。
【０１５１】
一方、ステップＳ３３０７において、現在処理対象ノードＮ（ロウロックオブジェクト４）の右子ノード特定情報ｐＬが空（ＮＵＬＬ）でないと判定した場合（Ｓ３３０７、Ｎｏ）、現在処理対象ノードを特定する情報Ｐに、現在処理対象ノードの左子ノード特定情報ｐＬを代入する（Ｓ３３０８）。これで、新たな現在処理ノードは、現在処理ノードからその左子ノードに変更される。その後ステップＳ３３０３に戻りノード追加処理が続行される。
【０１５２】
[ノード追加処理の具体例]
第２の実施例にかかるデータベース管理部１０ノード追加処理の具体例を示す。
【０１５３】
[具体例１]
図３４に、ロック二分木１５の例を示す。このロック二分木１５は、以下のノードから構成されている。
【０１５４】
ユーザ特定情報を「ｋ１」とし、範囲最小値情報を「２０」とし、範囲最小値情報を「２１」とするノードＮ＿３４＿１と、
ノードＮ＿３４＿１の左子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１１」とし、範囲最小値情報を「１２」とするノードＮ＿３４＿２と、
ノードＮ＿３４＿２の右子ノードであってユーザ特定情報を「ｋ２」とし、範囲最小値情報を「１６」とし、範囲最小値情報を「１８」とするノードＮ＿３４＿３と、
ノードＮ＿３４＿３の左子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１４」とし、範囲最小値情報を「１５」とするノードＮ＿３４＿４と、
を有する。
【０１５５】
このロック二分木１５について、ロック制御部１３が更新要求ユーザを「ｋ１」、更新要求行範囲を「１８、１９」とする更新要求３４０１に基づいてノード追加処理を行う場合を述べる。ロック制御部１３は、ロック二分木１５をノードＮ＿３４＿１から探索していき、更新要求３４０１の更新要求行範囲と重複するロック対象行範囲を有するノードを求める。このロック二分木１５では、ノードＮ＿３４＿３のロック対象行範囲が「１６、１８」で更新要求行範囲「１８、１９」と行番号「１８」について重複する。ここで、ノードＮ＿３４＿３のユーザ情報と更新要求３４０１の更新要求ユーザを比較すると、ノードＮ＿３４＿３のユーザ情報「ｋ２」であり一方更新要求ユーザ「ｋ１」であって一致しないため、ロック制御部１３は更新要求３４０１に基づくロックは取得不可であると判定する。行番号「１８」についてユーザ「ｋ２」がすでにロック取得済みであるためである。
【０１５６】
[具体例２]
別の具体例として、別のロック二分木１５の例について述べる。このロック二分木１５は、以下のノードＮによって構成されている。
【０１５７】
ユーザ特定情報を「ｋ１」とし、範囲最小値情報を「２０」とし、範囲最小値情報を「２１」とするノードＮ＿３５＿１と、
ノードＮ＿３５＿１の左子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１１」とし、範囲最小値情報を「１２」とするノードＮ＿３５＿２と、
ノードＮ＿３５＿２の右子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１７」とし、範囲最小値情報を「１８」とするノードＮ＿３５＿３と、
ノードＮ＿３５＿３の左子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１４」とし、範囲最小値情報を「１５」とするノードＮ＿３５＿４と、
ノードＮ＿３５＿３の右子ノードであってユーザ特定情報を「ｋ２」とし、範囲最小値情報を「１９」とし、範囲最小値情報を「１９」とするノードＮ＿３５＿５と、
である。
【０１５８】
このロック二分木１５について、更新要求ユーザを「ｋ１」、更新要求行範囲を「１８、２１」とする更新要求３５０１に基づいてロック制御部１３がノード追加処理を行う場合を述べる。上記ロック二分木に対して、更新要求３５０１が出された状態を図３５に示す。
ロック制御部１３は、ロック二分木１５をノードＮ＿３５＿１から探索していき、更新要求３５０１の更新要求行範囲と重複するロック対象行範囲を有するノードを求める。このロック二分木１５では、ノードＮ＿３５＿１のロック対象行範囲が「２０、２１」で更新要求行範囲「１８、２１」と行範囲「２０、２１」について重複する。ここでノードＮ＿３５＿１のユーザ情報と更新要求３５０１の更新要求ユーザを比較すると、ともに「ｋ１」で一致しているのでロック制御部１３は行範囲「２０、２１」についてロック可能であると判定する。
【０１５９】
ロック制御部１３は、更新要求３５０１のうち、行範囲「２０、２１」を除いた残りの更新要求範囲「１８、１９」を有する更新要求３５０１＿１に基づいてノード追加処理を続行する（Ｓ３３１２参照）。更新要求３５０１＿１に基づいてノード追加処理を行う状態を図３６に示す。
【０１６０】
ロック制御部１３は、ノードＮ＿３５＿１の子ノードであるノードＮ＿３５＿２から更新要求３５０１＿１の更新要求範囲と重複しているロック対象行範囲を有するノードを求める。
【０１６１】
ノードＮ＿３５＿２のロック対象行範囲は、更新要求３５０１＿１の更新要求範囲と重複しておらず、更新要求３５０１＿１に対応する新たなノードをノードＮ＿３５＿２の左子ノードとすることもできないため、ロック制御部１３は、ノードＮ＿３５＿２の右子ノードであるノードＮ＿３５＿３を次の対象としてノード追加処理を続行する。
【０１６２】
ロック制御部１３は、ノードＮ＿３５＿２の右子ノードであるノードＮ＿３５＿３を対象として、更新要求３５０１＿１の更新要求範囲と重複しているロック対象行範囲を有するノードを求める。ノードＮ＿３５＿３のロック対象行範囲が「１７、１８」で更新要求行範囲「１８、１９」と行範囲「１８」について重複する。ここでノードＮ＿３５＿３のユーザ情報と更新要求３５０１＿１の更新要求ユーザを比較すると、ともに「ｋ１」で一致しているのでロック制御部１３は行範囲「１８」についてロック可能であると判定する。
【０１６３】
ロック制御部１３は、更新要求３５０１＿１のうち、ロック可能と判定した行範囲「１８」を除いた残りの更新要求範囲「１９、１９」を有する更新要求３５０１＿２に基づいてノード追加処理を続行する（Ｓ３３１２参照）。
【０１６４】
ロック制御部１３は、ノードＮ＿３５＿３の右子ノードであるノードＮ＿３５＿５を対象として、更新要求３５０１＿２の更新要求範囲と重複しているロック対象行範囲を有するノードを求める。ノードＮ＿３５＿５のロック対象行範囲が「１９、１９」で更新要求行範囲「１９、１９」と行範囲「１９」について重複する。ここでノードＮ＿３５＿５のユーザ情報と更新要求３５０１＿２の更新要求ユーザを比較すると、ノードＮ＿３５＿５のユーザ情報「ｋ２」であり、一方更新要求３５０１＿２の更新要求ユーザは「ｋ１」であって、両者は一致しないため、ロック制御部１３は更新要求３５０１＿２に基づくロックは取得不可であると判定する。行番号「１９」についてユーザ「ｋ２」がすでにロック取得済みであるためである。
【０１６５】
すなわち、ロック制御部１３は、更新要求３５０１について、更新対象行範囲「１８、２１」のすべてがロック可能で無かったため、最終的な結果としてロックは不可であると判定する。そのため、ロック取得が不可の行が存在した時点で処理を打ち切ることができる。
【０１６６】
[具体例３]
図３７に、さらに別のロック二分木１５の例を示す。このロック二分木１５は、以下のノードを構成要素として有している。
【０１６７】
ユーザ特定情報を「ｋ１」とし、範囲最小値情報を「２０」とし、範囲最小値情報を「２１」とするノードＮ＿３７＿１と、
ノードＮ＿３７＿１の左子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１１」とし、範囲最小値情報を「１２」とするノードＮ＿３７＿２と、
ノードＮ＿３７＿２の右子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１７」とし、範囲最小値情報を「１８」とするノードＮ＿３７＿３と、
ノードＮ＿３７＿３の左子ノードであってユーザ特定情報を「ｋ１」とし、範囲最小値情報を「１４」とし、範囲最小値情報を「１５」とするノードＮ＿３７＿４と、
である。
【０１６８】
このロック二分木１５について、更新要求ユーザを「ｋ１」、更新要求行範囲を「１６、１９」とする更新要求３７０１に基づいてロック制御部１３がノード追加処理を行う場合を述べる。ロック制御部１３はロック二分木１５をノードＮ＿３７＿１から探索していき、更新要求３７０１の更新要求行範囲と重複するロック対象行範囲を有するノードを求める。このロック二分木１５では、ノードＮ＿３７＿３のロック対象行範囲が「１７、１８」であり、更新要求３７０１の更新要求行範囲「１６、１９」と行範囲「１７、１８」について重複する。ここでノードＮ＿３７＿３のユーザ情報と更新要求３７０１の更新要求ユーザを比較すると、ともに「ｋ１」で一致しているのでロック制御部１３は行範囲「１７、１８」についてロック可能であると判定する。
【０１６９】
次に、ロック制御部１３は更新要求３７０１の更新要求行範囲のうち行範囲「１７、１８」を除いた残りの更新要求範囲「１６、１６」を有する更新要求３７０１＿１と、更新要求範囲「１９、１９」を有する更新要求３７０１＿２とを生成し、これらに基づいてノード追加処理を続行する。
【０１７０】
ロック制御部１３は更新要求範囲「１６、１６」を有する更新要求３７０１＿１について、ノード追加処理を続行する。ロック制御部１３はノードＮ＿３７＿３の左子ノードであるノードＮ＿３７＿４について更新要求３７０１＿１を処理する。ノードＮ＿３７＿４のロック対象行範囲「１４、１５」と更新要求３７０１＿１の更新要求行範囲「１６、１６」は重複しておらず、ノードＮ＿３７＿４の範囲最大値「１５」より更新要求３７０１＿１の範囲最小値「１６」は大きく、ノードＮ＿３７＿４は右子ノードを有していないので、ロック制御部１３は更新要求３７０１＿１に対応する新しいノードＮ＿３７＿５を生成し、これをノードＮ＿３７＿４の右子ノードとして記憶させる。ノードＮ＿３７＿５が追加されたロック二分木１５を図３８に示す。
【０１７１】
次にロック制御部１３は更新要求範囲「１９、１９」を有する更新要求３７０１＿２について、ノード追加処理を続行する。ロック制御部１３はノードＮ＿３７＿３について更新要求３７０１＿１を処理する。ノードＮ＿３７＿３のロック対象行範囲「１７、１８」と更新要求３７０１＿２の更新要求行範囲「１９」は重複しておらず、ノードＮ＿３７＿３の範囲最大値「１８」より更新要求３７０１＿２の範囲最小値「１９」は大きく、ノードＮ＿３７＿３は右子ノードを有していないので、ロック制御部１３は更新要求３７０１＿２に対応する新しいノードＮ＿３７＿６を生成し、これをノードＮ＿３７＿３の右子ノードとして記憶させる。ノードＮ＿３７＿６が追加されたロック二分木１５を図３８に示した。
【０１７２】
このノード追加処理の結果、ロック制御部１３は、ユーザｋ１について更新要求範囲「１６、１９」のロックがすべて取得可能であると判定できたので、ロック可能と判定し、判定結果をデータ制御部１２に出力する。
【０１７３】
[ノード集約処理]
ロック制御部１３はノード追加処理の後に、ロック二分木中の２つのノードのロック対象行範囲が一つの連続したロック対象行範囲とできる場合に、その２つのノードを一つのノードにする処理であるノード集約処理を行う。
【０１７４】
図３９から図４６に、図３８に示したロック二分木について、ロック制御部１３がノード集約処理を行った例を示す。
【０１７５】
ノード集約処理において、ロック制御部１３は最も下位のノードＮから他のノードＮと集約することができるかどうかを調べてゆく。図３８に示したロック二分木１５では、最下位のノードであるノードＮ＿３７＿５が最初に選択される。ロック制御部１３は選択したノード（「選択ノード」と呼ぶ）と他のノード（「相手ノード」と呼ぶ）と集約することが可能かどうか調べる。相手ノードは、選択ノードに近いノードから優先して選択される。図３８のロック二分木１５では、ノードＮ＿３７＿４が相手ノードとして選択される。ノードＮ＿３７＿５が選択ノードとして選択され、ノードＮ＿３７＿４が相手ノードとして選択された状態を図３９に示す。
【０１７６】
ロック制御部１３は、選択ノードのロック対象行範囲と、相手ノードのロック対象行範囲が一つの連続したロック対象行範囲となるか否かを調べる。これらが一つの連続したロック対象行範囲となる場合には、選択ノードを削除するともに、相手ノードのロック対象行範囲を、前記一つの連続したロック対象行範囲となるように書き換える。これらが一つの連続したロック対象行範囲とならない場合には、ロック制御部１３は、ロック二分木１５中の他のノードから別のノードを新たな相手ノードとして選択し、集約することが可能な相手ノードが見つかるまで全てのノードを相手ノードとして選択してゆく。
【０１７７】
図３９の例では、選択ノードであるノードＮ＿３７＿５のロック対象行範囲は「１６、１６」であり、相手ノードであるノードＮ＿３７＿４のロック対象行範囲は「１４、１５」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「１４、１６」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿３７＿５を削除するとともに、相手ノードであるノードＮ＿３７＿４のロック対象行範囲を「１４、１５」から「１４、１６」と変更する。ノードＮ＿３７＿５を削除し、ノードＮ＿３７＿４のロック対象行範囲を「１４、１６」と変更した状態のロック二分木１５を図４０に示す。
【０１７８】
続いて、ロック制御部１３は図４０に示すロック二分木１５について、ノード集約処理を続行する。図４０に示したロック二分木１５では、最下位のノードの一つであるノードＮ＿３７＿４が選択ノードとして選択される。また、ロック制御部１３は、相手ノードとして残りのノード中最下位のノードであるノードＮ＿３７＿６を選択するが、ノードＮ＿３７＿６とは一つの行範囲とならないので、次に下位のノードであるノードＮ＿３７＿３を相手ノードとして選択する。ノードＮ＿３７＿４が選択ノード、ノードＮ＿３７＿３が相手ノードとして選択された状態を図４１に示す。
【０１７９】
図４１の例では、選択ノードであるノードＮ＿３７＿４のロック対象行範囲は「１４、１６」であり、相手ノードであるノードＮ＿３７＿３のロック対象行範囲は「１７、１８」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「１４、１８」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿３７＿４を削除するとともに、相手ノードであるノードＮ＿３７＿３のロック対象行範囲を「１４、１８」と変更する。ノードＮ＿３７＿４を削除し、ノードＮ＿３７＿３のロック対象行範囲を「１４、１８」と変更した状態のロック二分木１５を図４２に示す。
【０１８０】
続いて、ロック制御部１３は図４２に示すロック二分木１５について、ノード集約処理を続行する。図４２に示したロック二分木１５では、最下位のノードであるノードＮ＿３７＿６が選択ノードとして選択される。また、ロック制御部１３は、相手ノードとして残りのノード中最下位のノードであるノードＮ＿３７＿３を選択する。ノードＮ＿３７＿６が選択ノード、ノードＮ＿３７＿３が相手ノードとして選択された状態を図４３に示す。
【０１８１】
図４３の例では、選択ノードであるノードＮ＿３７＿６のロック対象行範囲は「１９、１９」であり、相手ノードであるノードＮ＿３７＿３のロック対象行範囲は「１４、１８」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「１４、１９」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿３７＿６を削除するとともに、相手ノードであるノードＮ＿３７＿３のロック対象行範囲を「１４、１９」と変更する。ノードＮ＿３７＿６を削除し、ノードＮ＿３７＿３のロック対象行範囲を「１４、１９」と変更した状態のロック二分木１５を図４４に示す。
【０１８２】
続いて、ロック制御部１３は図４４に示すロック二分木１５について、ノード集約処理を続行する。図４４に示したロック二分木１５では、最下位のノードであるノードＮ＿３７＿３が選択ノードとして選択される。また、ロック制御部１３は、相手ノードとして、選択ノードに近いノードを優先して相手ノードとして選択し、この例ではノードＮ＿３７＿２を選択するが、ノードＮ＿３７＿３とは一つの行範囲とならないので、次に近いノードであるノードＮ＿３７＿１を相手ノードとして選択する。ノードＮ＿３７＿３が選択ノード、ノードＮ＿３７＿１が相手ノードとして選択された状態を図４５に示す。
【０１８３】
図４５の例では、選択ノードであるノードＮ＿３７＿３のロック対象行範囲は「１４、１９」であり、相手ノードであるノードＮ＿３７＿１のロック対象行範囲は「２０、２１」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「１４、２１」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿３７＿３を削除するとともに、相手ノードであるノードＮ＿３７＿１のロック対象行範囲を「２０、２１」から「１４、２１」に変更する。ノードＮ＿３７＿３が削除され、ノードＮ＿３７＿１のロック対象行範囲が「１４、２１」と変更された状態のロック二分木１５を図４６に示す。
【０１８４】
続いて、ロック制御部１３は図４６に示すロック二分木１５について、ノード集約処理を続行する。図４６に示したロック二分木１５では、最下位のノードであるノードＮ＿３７＿２が選択ノードとして選択される。また、ロック制御部１３は、相手ノードとして、選択ノードに近いノードを優先して選択するので、ノードＮ＿３７＿１を選択する。ノードＮ＿３７＿２とノードＮ＿３７＿１それぞれのロック対象行範囲「１１、１２」と「１４、２１」とは一つの連続したロック対象行範囲とならない。また残りの他のノードも存在しないので、ロック制御部１３は、ノード集約処理を終了する。すなわち、図３８に示すロック二分木１５は、ロック制御部１３によるノード集約処理の結果、図４６に示すロック二分木１５に書き換えられるのである。
【０１８５】
ノード集約処理を行うと、ノードの追加、探索などの処理量を低減させることが可能となるとともに、ロック二分木１５に含まれるノード数を減少させることでロック二分木１５を記憶するために必要な記憶容量を減少させることも可能となる。
【０１８６】
[第３の実施例]
次に、本実施の形態の第３の実施例について述べる。第３の実施例は、複数のユーザによってデータベースシステムが使用されることを前提として、ユーザ全体のロック取得状況を記録するロック二分木１５Ａ（以下、「全体ロック二分木」と呼ぶ）と、個々のユーザのロック取得状況を記録するロック二分木１５Ｂ（以下、「ユーザ別ロック二分木」と呼ぶ）と用いてロックの管理を行うことを特徴とする。
【０１８７】
[データベース装置、データベース管理部等の構成]
第３の実施例にかかるマルチユーザ・データベースシステム１、データベース装置２の構成は、前述の第１の実施の形態と同じ（図１、図２参照）であるので、同一の構成要素には同一の参照番号を付して、これら構成要素の詳細な説明は省略する。
【０１８８】
第３の実施例にかかるデータベース管理部１０の構成例を図４７に示す。第３の実施例にかかるデータベース管理部１０は、ＳＱＬ文解析部１１と、データ制御部１２と、ロック制御部１３と、データロック情報記憶部１４とを有する。
【０１８９】
但し、第３の実施例にかかるデータベース管理部１０は、全体ロック二分木１５Ａと、データベースを使用しているユーザそれぞれに対応する、複数のユーザ別ロック二分木１５Ｂをデータロック情報記憶部１４が有している点で、第１の実施の形態と相違している。また、第１の実施の形態ではロック二分木は全ユーザで共有する必要あるが、第３の実施の形態では全体ロック二分木は全ユーザが共有する必要あるが、ユーザ別ロック二分木は他のユーザが参照することは無いので共有する必要はない。ユーザごとに木が分かれているため、ユーザ特定情報を持つ必要が無い。集約において、ユーザ特定情報が常に一致するので、ユーザが同じかどうか判定をする必要はない。
【０１９０】
[データベース管理システムの動作]
次に、第３の実施例にかかるデータベース管理システムの動作について説明する。図４８は、第３の実施例にかかるデータベース管理部１０の主たる動作の一つである、ＳＱＬ文実行処理の一例を示すフローチャートである。第３の実施例にかかるＳＱＬ文実行処理は、前述の第１の実施の形態にかかるＳＱＬ文実行処理（図３参照）と基本的に同じであるので、同一の処理には同一の参照番号を付して、各処理の詳細な説明は省略する。
【０１９１】
但し、図４８に示す第３の実施例におけるステップＳ４Ａは、全体ロック二分木１５Ａ及びユーザ別ロック二分木１５Ｂを扱う点で、第１の実施の形態におけるステップＳ４と、相違している。
【０１９２】
図４９に、ステップＳ４Ａの処理内容の例を示すフローチャートを掲げ、この図を参照しながらステップＳ４Ａの処理内容を説明する。
【０１９３】
ステップＳ４Ａである該当行ロック処理において、ロック制御部１３はまず、更新要求に応じた行範囲のロックが取得可能か否かについて、当該更新要求を行ったユーザに対応するユーザ別ロック二分木１５Ｂを探索し、ロック可能な場合にはそのユーザ別ロック二分木１５Ｂに新たなノードの追加を行う（Ｓ４９０１）。ノードが追加された場合には、ロック制御部１３はそのノードを追加ノードリスト（図示省略）に加える。追加ノードリストは、例えば、追加されたノードごとに一つのレコードを有するデータであって、各レコードは、追加されたノードを特定する情報を格納する。
【０１９４】
更新要求に応じたユーザ別ロック二分木１５Ｂへのノード追加処理が完了すると、ロック制御部１３は、前記追加ノードリストを参照して、新規で追加したノードが存在するか否かを判定する（Ｓ４９０２）。ロック制御部１３は、前記追加ノードリストに、追加されたノードが記載されていれば、新規で追加したロック（ノード）が存在すると判定する。
【０１９５】
ステップＳ４９０２において、新規で追加したノードが存在しないと判定した場合（Ｓ４９０２，Ｎｏ）、ロック制御部１３はそのまま該当行ロック処理を終了する。一方、新規で追加したノードが存在すると判定した場合（Ｓ４９０２，Ｙｅｓ）、ロック制御部１３は追加ノードリストから追加されたノードの情報を一つ読みだす（Ｓ４９０３）。
【０１９６】
次に、ロック制御部１３は全体ロック二分木１５Ａを探索し、ステップＳ４９０３において読みだしたノードに対応する行範囲についてロック取得可能か否かを判定する（Ｓ４９０５）。
【０１９７】
ロック取得可能でないと判定した場合（Ｓ４９０５，Ｎｏ）、ロック制御部１３は当該更新要求に対応するロックの取得は不可であることを示す情報をデータ制御部１２に渡し（Ｓ４９０６）、該当行ロック処理を終了する。一方、ロック取得可能であると判定した場合（Ｓ４９０５，Ｙｅｓ）、ロック制御部１３は、前記追加ノードリスト中の全てのノードについてＳ４９０５の判定を行ったか否かを判定する（Ｓ４９０７）。
【０１９８】
ステップＳ４９０７において、前記追加ノードリスト中の全てのノードについてＳ４９０５の判定を行ったと判定した場合（Ｓ４９０７、Ｙｅｓ）、ロック制御部１３は当該更新要求に対応するロックの取得は可能であることを示す情報をデータ制御部１２に渡し（Ｓ４９０８）、該当行ロック処理を終了する。一方、前記追加ノードリスト中の全てのノードについてＳ４９０５の判定を行っていないと判定した場合（Ｓ４９０７、Ｎｏ）、ロック制御部１３はステップＳ４９０３に戻り、追加ノードリスト中の未処理ノードについてＳ４９０３以降の処理を続行していく。
【０１９９】
以上で該当行ロック処理の説明を終了する。
【０２００】
[具体例]
次に、第３の実施例にかかるデータベース管理部１０の動作について、具体例をあげて説明する。ここで説明する例のロック取得状況を図５０に示す。図５０では、ロック取得状況をロック二分木１５中のノードＮの表示形式で示した。
【０２０１】
ロック二分木１５は、ノードＮ＿５０＿１からノードＮ＿５０＿１２までの１２個のノードＮで構成されている。ノードＮ＿５０＿１は、ユーザ特定情報として「ｋ１」を有し、範囲最小値情報として「１」を有し、範囲最大値情報として「１」を有するノードＮである。ノードＮ＿５０＿２は、ユーザ特定情報として「ｋ８」を有し、範囲最小値情報として「２」を有し、範囲最大値情報として「２」を有するノードＮである。ノードＮ＿５０＿３は、ユーザ特定情報として「ｋ７」を有し、範囲最小値情報として「３」を有し、範囲最大値情報として「３」を有するノードＮである。ノードＮ＿５０＿４は、ユーザ特定情報として「ｋ１」を有し、範囲最小値情報として「４」を有し、範囲最大値情報として「６」を有するノードＮである。ノードＮ＿５０＿５は、ユーザ特定情報として「ｋ６」を有し、範囲最小値情報として「７」を有し、範囲最大値情報として「８」を有するノードＮである。ノードＮ＿５０＿６は、ユーザ特定情報として「ｋ１」を有し、範囲最小値情報として「１１」を有し、範囲最大値情報として「１２」を有するノードＮである。ノードＮ＿５０＿７は、ユーザ特定情報として「ｋ４」を有し、範囲最小値情報として「１３」を有し、範囲最大値情報として「１３」を有するノードＮである。ノードＮ＿５０＿８は、ユーザ特定情報として「ｋ１」を有し、範囲最小値情報として「１４」を有し、範囲最大値情報として「１５」を有するノードＮである。ノードＮ＿５０＿９は、ユーザ特定情報として「ｋ３」を有し、範囲最小値情報として「１６」を有し、範囲最大値情報として「１６」を有するノードＮである。ノードＮ＿５０＿１０は、ユーザ特定情報として「ｋ１」を有し、範囲最小値情報として「１７」を有し、範囲最大値情報として「１８」を有するノードＮである。ノードＮ＿５０＿１１は、ユーザ特定情報として「ｋ２」を有し、範囲最小値情報として「１９」を有し、範囲最大値情報として「１９」を有するノードＮである。ノードＮ＿５０＿１２は、ユーザ特定情報として「ｋ１」を有し、範囲最小値情報として「２０」を有し、範囲最大値情報として「２１」を有するノードＮである。
【０２０２】
図５１に、上記ノードＮ＿５０＿１からノードＮ＿５０＿１２をロック二分木１５の表示形式で示した図を示す。
【０２０３】
このロック二分木１５において、ノードＮ＿５０＿１２は、左子ノードとしてノードＮ＿５０＿６を有する。ノードＮ＿５０＿６は、左子ノードとしてノードＮ＿５０＿４を有し、右子ノードとしてノードＮ＿５０＿１０を有する。ノードＮ＿５０＿４は、左子ノードとしてノードＮ＿５０＿２を有し、右子ノードとしてノードＮ＿５０＿５を有する。ノードＮ＿５０＿２は、左子ノードとしてノードＮ＿５０＿１を有し、右子ノードとしてノードＮ＿５０＿３を有する。ノードＮ＿５０＿１及びノードＮ＿５０＿３はいずれの子ノードも有しない葉ノードである。ノードＮ＿５０＿５もいずれの子ノードも有しない葉ノードである。
【０２０４】
ノードＮ＿５０＿１０は、左子ノードとしてノードＮ＿５０＿８を有し、右子ノードとしてノードＮ＿５０＿１１を有する。ノードＮ＿５０＿８は、左子ノードとしてノードＮ＿５０＿７を有し、右子ノードとしてノードＮ＿５０＿９を有する。ノードＮ＿５０＿７及びノードＮ＿５０＿９はいずれの子ノードも有しない葉ノードである。ノードＮ＿５０＿１１もいずれの子ノードも有しない葉ノードである。
【０２０５】
なお、図中に示したノードＮ＿５０＿１３は、ロック取得されていない行範囲を示すものであり、実際にはロック二分木１５に加えられるものではなく、参考のために表示した。
【０２０６】
次に、図５０及び図５１に示すロック取得状態の場合に、ユーザ別ロック二分木１５Ｂ及び全体ロック二分木１５Ａはどのように構成されるかを説明する。図５２は、ユーザ「ｋ１」についてのユーザ別ロック二分木１５Ｂの例を示す図である。ユーザ「ｋ１」についてのユーザ別ロック二分木１５Ｂは、ユーザ特定情報として「ｋ１」を有するノードＮ＿５０＿１２、ノードＮ＿５０＿６、ノードＮ＿５０＿４、ノードＮ＿５０＿１０、ノードＮ＿５０＿８で構成されている。一方、全体ロック二分木１５Ａの構成を図５３に示す。全体ロック二分木１５Ａは、ノードＮ＿５３＿１と、ノードＮ＿５３＿１の左子ノードのノードＮ＿５３＿２で構成される。ノードＮ＿５３＿１は、ユーザ特定情報として「ｋ０」を有し、範囲最小値情報として「１１」を有し、範囲最大値情報として「２１」を有するノードＮである。ユーザ特定情報として「ｋ０」を有し、範囲最小値情報として「１」を有し、範囲最大値情報として「８」を有するノードＮである。なお、ユーザ特定情報「ｋ０」は、全ユーザを示す。
【０２０７】
第３の実施例にかかるデータロック情報記憶部１４は、ユーザ別ロック二分木１５Ｂをユーザごとに記憶している。図５４に、図５０及び図５１に示すロック取得状態におけるデータロック情報記憶部１４の記憶内容を例示する。データロック情報記憶部１４は、ユーザ「ｋ１」からユーザ「ｋ９」のそれぞれについてユーザ別ロック二分木１５Ｂを有し、各ユーザ別ロック二分木１５Ｂは当該ユーザに対応するノードを含むロック二分木を記憶している。また、データロック情報記憶部１４は全体ロック二分木１５Ａも記憶している。
【０２０８】
第３の実施例にかかるロック制御部１３は、ユーザ「ｋ１」からの更新要求を取得した場合に、まず「ｋ１」についてのユーザ別ロック二分木１５Ｂを探索して、ユーザ別ロック二分木１５Ｂに含まれない行範囲が存在するか否かを判定し、ユーザ別ロック二分木１５Ｂに含まれない行範囲が存在する場合は、その行範囲についてロック取得可能か否かを全体ロック二分木１５Ａを探索して判断する。すでに全体ロック二分木１５Ａにその行範囲が含まれている場合は、ロック取得不可（他のユーザによりロック取得されている）とし、全体ロック二分木１５Ａにその行範囲が含まれていない場合は、ロック取得可能と判断するとともに、全体ロック二分木に当該行範囲に対応する新たなノードを追加する。
【０２０９】
[動作例]
次に、第３の実施例にかかるロック制御部１３の動作例について、上述の図５２に示したユーザ別ロック二分木１５Ｂ、及び図５３に示した全体ロック二分木１５Ａを用いて説明する。
【０２１０】
[ユーザｋ１による行範囲「１４、１４」とする更新要求]
図５２に示したユーザ別ロック二分木１５Ｂ、及び図５３に示した全体ロック二分木１５Ａのロック取得状態で、新たにユーザｋ１による更新対象行範囲を「１４、１４」とする更新要求５５０１をデータベース管理部１０が取得したとする。この更新要求５５０１を受け付けた状態を図５５に示す。
【０２１１】
更新要求５５０１に応じて、ロック制御部１３はユーザｋ１のユーザ別ロック二分木１５Ｂを探索して、更新対象行範囲「１４、１４」（行番号１４のみを更新対象とする）が既存のノードのいずれかに含まれているか否かを調べる。この例では、ノードＮ＿５０＿８が行範囲１４を含んでいるので、更新要求５５０１についてロック取得可能(ロック取得済み）と判定する。なお、全体ロック二分木１５Ａについて探索は行わない。ユーザ別ロック二分木１５Ｂで行範囲１４についてロック取得済みと記録されているので、全体ロック二分木１５Ａにおいても、行範囲１４についてロック取得されていることが反映済みとなっているからである。
【０２１２】
[ユーザｋ１による更新対象行範囲「１３、１３」とする更新要求]
図５５に示したユーザ別ロック二分木１５Ｂ及び全体ロック二分木１５Ａのロック取得状態の後に、さらに新たな更新要求として、ユーザｋ１による更新対象行範囲を「１３、１３」とする更新要求５６０１をデータベース管理部１０が取得したとする。この更新要求５６０１を受け付けた状態を図５６に示す。
【０２１３】
ロック制御部１３はユーザｋ１のユーザ別ロック二分木１５Ｂを探索して、更新対象行範囲「１３、１３」（行番号１３のみ）がユーザ別ロック二分木１５Ｂの既存のノードのいずれかに含まれているか否かを調べる。この例では、いずれのノードも行範囲「１３、１３」を含んでいないので、全体ロック二分木１５Ａに行範囲「１３、１３」をロック取得するためのノードＮ＿５０＿１４が追加可能かどうか判定する。
【０２１４】
ロック制御部１３は全体ロック二分木１５Ａを探索して、ノードＮ＿５０＿１４と同じ行範囲「１３、１３」についてロック取得可能か否かを判定する。この例では、行範囲「１３、１３」は、ロック対象行範囲「１１、２１」を有するノードＮ＿５３＿１のロック対象行範囲に含まれているため、ロック制御部１３は更新要求５６０１についてのロック取得は不可であると判定する。なお、この結果ユーザ別ロック二分木１５ＢへのノードＮ＿５０＿１４の追加は行われない。ノードＮ＿５０＿１４に対応する行範囲のロック取得は不可だからである。
【０２１５】
[ユーザｋ１による更新態様行範囲「３、４」とする更新要求]
図５６に示したユーザ別ロック二分木１５Ｂ及び全体ロック二分木１５Ａのロック取得状態の後に、さらに新たな更新要求として、ユーザｋ１による更新対象行範囲「３、４」とする更新要求５７０１をデータベース管理部１０が取得したとする。この更新要求５７０１を受け付けた状態を図５７に示す。
【０２１６】
ロック制御部１３はユーザｋ１のユーザ別ロック二分木１５Ｂを探索して、行範囲「３、４」がユーザ別ロック二分木１５Ｂの既存のノードのロック対象行範囲いずれかに含まれているか否かを調べる。この例では、ノードＮ＿５０＿４が行番号４を含んでいるが、いずれのノードも行番号３を含んでいないので、全体ロック二分木１５Ａに行範囲「３、３」（行番号３のみ）についてロック取得するためのノードＮ＿５０＿１５が追加可能であるかどうかを判定する。
【０２１７】
次に、ロック制御部１３は全体ロック二分木１５Ａを探索して、ノードＮ＿５０＿１５と同じ行範囲「３、３」についてロック取得可能か否かを判定する。この例では、行範囲「３、３」は、行範囲「１、８」を有するノードＮ＿５３＿２のロック対象行範囲に含まれているため、ロック制御部１３は更新要求５７０１についてのロック取得は不可であると判定する。なお、ロック制御部１３はユーザ別ロック二分木１５ＢへのノードＮ＿５０＿１５の追加は行わない。ノードＮ＿５０＿１５に対応する行範囲のロック取得は他のユーザによりロック取得済みのため、ユーザｋ１によるロック取得は不可だからである。
【０２１８】
[ユーザｋ１による行範囲９から１２とする更新要求]
図５７に示したユーザ別ロック二分木１５Ｂ及び全体ロック二分木１５Ａのロック取得状態の後に、さらに新たな更新要求として、ユーザｋ１による行範囲「９、１２」についての更新要求５８０１をデータベース管理部１０が取得したとする。この更新要求５８０１を受け付けた状態を図５８に示す。
【０２１９】
ロック制御部１３はユーザｋ１のユーザ別ロック二分木１５Ｂを探索して、行範囲「９、１２」がユーザ別ロック二分木１５Ｂの既存のノードのロック対象行範囲のいずれかに含まれているか否かを調べる。この例では、ノードＮ＿５０＿６のロック対象行範囲が行範囲「１１、１２」を含んでいるが、いずれのノードも行範囲「９、１０」を含んでいないので全体ロック二分木１５Ａに行範囲「９、１０」をロック取得するためのノードＮ＿５０＿１６を追加可能かどうか判定する。
【０２２０】
ロック制御部１３は全体ロック二分木１５Ａを探索して、ノードＮ＿５０＿１６の行範囲を含むロック対象行範囲を有するノードが存在するか否か調べる。この例では、ノードＮ＿５３＿１、ノードＮ＿５３＿２のいずれのロック対象行範囲も行範囲「９、１０」を含んでいないので、ロック制御部１３は行範囲「９、１０」をロック取得するためのノードＮ＿５３＿３を全体ロック二分木１５Ａに追加可能であると判定し、その結果、更新要求５８０１に対応するロック取得が可能であると判定する。また、ロック制御部１３はユーザ別ロック二分木１５Ｂに新たなノードＮ＿５０＿１６を追加するとともに、全体ロック二分木１５Ａにも新たなノードＮ＿５３＿３を追加するノード追加処理を行う。
【０２２１】
[ノード集約処理]
ロック制御部１３は、図５８に示すユーザ別ロック二分木１５Ｂと全体ロック二分木１５Ａのそれぞれに対してノード集約処理を実行しても良い。以下に、図５８に示すユーザ別ロック二分木１５Ｂと全体ロック二分木１５Ａのそれぞれに対して、ロック制御部１３がノード集約処理を実行した場合の例について説明する。なお、ノード集約処理の内容は、前述の第２の実施例におけるノード集約処理と同様である。
【０２２２】
[ユーザ別ロック二分木のノード集約処理]
ロック制御部１３はユーザ別ロック二分木１５Ｂについてノード集約処理を行う。ロック制御部１３は新規に登録したノードから他のノードと集約することができるかどうかを調べてゆく。図５８に示したユーザ別ロック二分木１５Ｂでは、新規に登録したノードの一つであるノードＮ＿５０＿１６が最初に選択ノードとして選択される。ロック制御部１３は選択ノードと親ノードである相手ノードとを集約することが可能かどうか調べる。図５８のロック二分木１５では、ロック制御部１３はノードＮ＿５０＿４を相手ノードとして選択する。
【０２２３】
ロック制御部１３は、選択ノードのロック対象行範囲と、相手ノードのロック対象行範囲が一つの連続したロック対象行範囲となるか否かを調べる。これらが一つの連続したロック対象行範囲となる場合には、選択ノードを削除するともに、相手ノードのロック対象行範囲を、前記一つの連続した範囲となるように変更する。これらが一つの連続したロック対象行範囲とならない場合には、なにもしない。ロック制御部１３は、ロック二分木１５中のノードからその親のノードを新たな相手ノードとして選択し、親のノードが存在しなくなるまで二分木をさかのぼりを相手ノードとして選択してゆく。
【０２２４】
図５８の例では、選択ノードであるノードＮ＿５０＿１６のロック対象行範囲は「９、１０」であり、相手ノードであるノードＮ＿５０＿４のロック対象行範囲は「４、６」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲とすることが不可能であるので、ノードＮ＿５０＿４の親ノードであるノードＮ＿５０＿６を新たな相手ノードとして選択する。ロック制御部１３がノードＮ＿５０＿１６を選択ノードとし、ノードＮ＿５０＿６を新たな相手ノードとした状態を図５９に示す。
【０２２５】
選択ノードであるノードＮ＿５０＿１６のロック対象行範囲は「９、１０」であり、新たな相手ノードであるノードＮ＿５０＿６のロック対象行範囲は「１１、１２」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「９、１２」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿５０＿１６を削除するとともに、相手ノードであるノードＮ＿５０＿６のロック対象行範囲を「１１、１２」から「９、１２」と変更する。ロック制御部１３がノードＮ＿５０＿１６を削除し、ノードＮ＿５０＿６のロック対象行範囲を「９、１２」と変更した状態のロック二分木１５を図６０に示す。
【０２２６】
ロック制御部１３は、残りのノードについてもノード集約処理を実行するが、いずれのノードについても集約可能な組み合わせとならないため、図６０の状態で、ユーザ別ロック二分木１５Ｂのノード集約処理は終了する。
【０２２７】
[全体ロック二分木のノード集約処理]
次に、ロック制御部１３は全体ロック二分木１５Ａについてノード集約処理を行う。ロック制御部１３は、全体ロック二分木１５Ａ中の新規に登録したノードから他のノードと集約することができるかどうかを調べてゆく。図６０に示した全体ロック二分木１５Ａでは、新規に登録したノードノードＮ＿５３＿３が最初に選択ノードとして選択される。ロック制御部１３は選択ノードと親ノードである相手ノードとを集約することが可能かどうか調べる。図６０の全体ロック二分木１５Ａでは、ロック制御部１３はまずノードＮ＿５３＿２を相手ノードとして選択する。図６１に、全体ロック二分木１５ＡのノードＮ＿５３＿３を選択ノードとし、ノードＮ＿５３＿２を相手ノードとして選択した状態を示す。
【０２２８】
選択ノードであるノードＮ＿５３＿３のロック対象行範囲は「９、１０」であり、相手ノードであるノードＮ＿５３＿２のロック対象行範囲は「１、８」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「１、１０」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿５３＿３を削除するとともに、相手ノードであるノードＮ＿５３＿２のロック対象行範囲を「１、８」から「１、１０」に変更する。ロック制御部１３がノードＮ＿５３＿３を削除し、ノードＮ＿５３＿２のロック対象行範囲を「１、１０」と変更した状態のロック二分木１５Ａを図６２に示す。
【０２２９】
次に、ロック制御部１３は全体ロック二分木１５Ａについてさらにノード集約処理を続行する。ロック制御部１３は、図６２に示した全体ロック二分木１５Ａでは、最下位のノードであるノードＮ＿５３＿２を新たな選択ノードとして選択する。ロック制御部１３は選択ノードと相手ノードとを集約することが可能かどうか調べる。相手ノードは、選択ノードに近いノードが優先して選択される。図６２の全体ロック二分木１５Ａでは、他のノードはノードＮ＿５３＿１のみであり、ノードＮ＿５３＿１が相手ノードとして選択される。図６３に、ロック制御部１３が全体ロック二分木１５ＡのノードＮ＿５３＿２を選択ノードとし、ノードＮ＿５３＿１を相手ノードとして選択した状態を示す。
【０２３０】
選択ノードであるノードＮ＿５３＿２のロック対象行範囲は「１、１０」であり、相手ノードであるノードＮ＿５３＿１のロック対象行範囲は「１１、２１」である。よってこれらのロック対象行範囲は一つの連続したロック対象行範囲「１、２１」とすることが可能であるので、ロック制御部１３は選択ノードであるノードＮ＿５３＿２を削除するとともに、相手ノードであるノードＮ＿５３＿１のロック対象行範囲を「１１、２１」から「１、２１」に変更する。ロック制御部１３がノードＮ＿５３＿２を削除し、ノードＮ＿５３＿１のロック対象行範囲を「１、２１」と変更した状態の全体ロック二分木１５Ａを図６４に示す。この状態では、全体ロック二分木１５Ａ中のノードはノードＮ＿５３＿１の一つのみになったので、これ以上ノードの集約を行うことはできないため、ロック制御部１３はノード集約処理を終了する。
【０２３１】
[まとめ]
本実施の形態及び各実施例の利点を述べる。
【０２３２】
１．複数の行について一つのノードでまとめてデータロックの記述できるので、ロック二分木中のノードを少なくすることが可能となる。ユーザからの「UPDATE」が空間的局所性があれば、さらに少ないノードでデータロックの記述が可能となる。本実施の形態によれば、ロック二分木へのノードの登録作業自体は高速で省メモリとなる。
【０２３３】
２．本実施の形態及び各実施例は、ノードＮ(ロウロックオブジェクト４)がロック対象行範囲を扱うことにより、複数のロック対象行をまとめて登録することを可能とする。よって、個別にロック対象行をノードとしてロック二分木に登録する従来記述より高速でデータロックの登録が可能となる。これは、ロック二分木１５の探索において、同じ方向なら複数のロック対象行について「相乗り」（同時に探索）できるためである。
【０２３４】
３．また、ノード集約処理を行うことにより、上記の利点をさらに向上させることを可能としている。
【０２３５】
以上、本発明の実施の形態、及び実施例を説明したが、本発明はこれらに限定されるものではなく、発明の趣旨を逸脱しない範囲内において、種々の変更、追加、組み合わせ等が可能である。
【符号の説明】
【０２３６】
１…マルチユーザ・データベースシステム；  ２…データベース装置；  ４…ロウロックオブジェクト；  １０…データベース管理部；  １１…ＳＱＬ文解析部；  １２…データ制御部；  １３…ロック制御部；  １４…データロック情報記憶部；  １５…ロック二分木；  １５Ａ…全体ロック二分木；  １５Ｂ…ユーザ別ロック二分木；  ２０…データベース記憶部；  ３０…データベース；  ４０…ネットワーク；  ５０…クライアント；  ６０…アプリケーションサーバ；  Ｎ…ノード；
【図１】
2014134896.tif 000003
【図２】
2014134896.tif 000004
【図３】
2014134896.tif 000005
【図４】
2014134896.tif 000006
【図５】
2014134896.tif 000007
【図６】
2014134896.tif 000008
【図７】
2014134896.tif 000009
【図８】
2014134896.tif 000010
【図９】
2014134896.tif 000011
【図１０】
2014134896.tif 000012
【図１１】
2014134896.tif 000013
【図１２】
2014134896.tif 000014
【図１３】
2014134896.tif 000015
【図１４】
2014134896.tif 000016
【図１５】
2014134896.tif 000017
【図１６】
2014134896.tif 000018
【図１７】
2014134896.tif 000019
【図１８】
2014134896.tif 000020
【図１９】
2014134896.tif 000021
【図２０】
2014134896.tif 000022
【図２１】
2014134896.tif 000023
【図２２】
2014134896.tif 000024
【図２３Ａ】
2014134896.tif 000025
【図２３Ｂ】
2014134896.tif 000026
【図２３Ｃ】
2014134896.tif 000027
【図２４】
2014134896.tif 000028
【図２５】
2014134896.tif 000029
【図２６】
2014134896.tif 000030
【図２７】
2014134896.tif 000031
【図２８】
2014134896.tif 000032
【図２９】
2014134896.tif 000033
【図３０】
2014134896.tif 000034
【図３１】
2014134896.tif 000035
【図３２】
2014134896.tif 000036
【図３３】
2014134896.tif 000037
【図３４】
2014134896.tif 000038
【図３５】
2014134896.tif 000039
【図３６】
2014134896.tif 000040
【図３７】
2014134896.tif 000041
【図３８】
2014134896.tif 000042
【図３９】
2014134896.tif 000043
【図４０】
2014134896.tif 000044
【図４１】
2014134896.tif 000045
【図４２】
2014134896.tif 000046
【図４３】
2014134896.tif 000047
【図４４】
2014134896.tif 000048
【図４５】
2014134896.tif 000049
【図４６】
2014134896.tif 000050
【図４７】
2014134896.tif 000051
【図４８】
2014134896.tif 000052
【図４９】
2014134896.tif 000053
【図５０】
2014134896.tif 000054
【図５１】
2014134896.tif 000055
【図５２】
2014134896.tif 000056
【図５３】
2014134896.tif 000057
【図５４】
2014134896.tif 000058
【図５５】
2014134896.tif 000059
【図５６】
2014134896.tif 000060
【図５７】
2014134896.tif 000061
【図５８】
2014134896.tif 000062
【図５９】
2014134896.tif 000063
【図６０】
2014134896.tif 000064
【図６１】
2014134896.tif 000065
【図６２】
2014134896.tif 000066
【図６３】
2014134896.tif 000067
【図６４】
2014134896.tif 000068