(57)【特許請求の範囲】
【請求項１】
データベースに対するユーザからの問合せを解析して対応する実行手順を作成し、当該実行手順にしたがってデータベース処理を行うデータベース処理装置であり、インスタンスの集まりで構成され、個々のインスタンスを添字にて確定することが可能なデータ型を扱うデータベース処理装置において、
問合せ中に前記データ型の列に対する指定を少なくとも二つ含み、かつ前記列に対する条件の指定を含む述語もしくは関数を含む場合、上記述語もしくは関数に指定されている列に対してインデクスが作成されているかどうかを判定し、インデクスが作成されていない場合には、テーブルデータをアクセスし上記述語もしくは関数を評価する様に実行手順を作成する問合せ解析処理部と、
作成した実行手順に従い、テーブルデータを取得し、前記述語に指定された前記データ型の複数列のデータを構成するインスタンスの内、同一添字にて確定されるインスタンスの組みを取得し、そのそれぞれのインスタンスに対し前記述語に指定された条件を用いて評価するテーブルデータ管理部と、
を備えることを特徴とするデータベース処理装置。
【請求項２】
データベースに対するユーザからの問合せを解析して対応する実行手順を作成し、当該実行手順にしたがってデータベース処理を行うデータベース処理装置であり、インスタンスの集まりで構成され、個々のインスタンスを添字にて確定することが可能なデータ型を扱うデータベース処理装置において、
行データの挿入処理、削除処理、または更新処理により挿入、削除、更新される前記データ型の列を少なくとも二つ構成列に持つインデクスに対するメンテナンス処理を行うように実行手順の作成を行う問合せ解析処理部と、
作成した実行手順に従い、行データから上記インデクスを構成する前記データ型の複数列のデータを構成するインスタンスの内、同一添字にて確定されるインスタンスの組みを添字数分取得し、その取得したインスタンスの組みと、そのインスタンスを含む行を識別するための行識別子とで添字数分のインデクスエントリを作成し、その作成されたインデクスエントリを用いて、上記インデクスをメンテナンスするインデクス管理部と、
を備えることを特徴とするデータベース処理装置。
【請求項３】
データベースに対するユーザからの問合せを解析して対応する実行手順を作成し、当該実行手順にしたがってデータベース処理を行うデータベース処理装置であり、インスタンスの集まりで構成され、個々のインスタンスを添字にて確定することが可能なデータ型を扱うデータベース処理装置としてコンピュータを機能させる為のプログラムを記録した媒体において、
問合せ中に前記データ型の列に対する指定を少なくとも二つ含み、かつ前記列に対する条件の指定を含む述語もしくは関数を含む場合、上記述語もしくは関数に指定されている列に対してインデクスが作成されているかどうかを判定し、インデクスが作成されていない場合には、テーブルデータをアクセスし上記述語もしくは関数を評価する様に実行手順を作成する問合せ解析処理部と、
作成した実行手順に従い、テーブルデータを取得し、前記述語に指定された前記データ型の複数列のデータを構成するインスタンスの内、同一添字にて確定されるインスタンスの組みを取得し、そのそれぞれのインスタンスに対し前記述語に指定された条件を用いて評価するテーブルデータ管理部として、
コンピュータを機能させる為のプログラムを記録したことを特徴とする媒体。
【請求項４】
データベースに対するユーザからの問合せを解析して対応する実行手順を作成し、当該実行手順にしたがってデータベース処理を行うデータベース処理装置であり、インスタンスの集まりで構成され、個々のインスタンスを添字にて確定することが可能なデータ型を扱うデータベース処理装置としてコンピュータを機能させる為のプログラムを記録した媒体において、
行データの挿入処理、削除処理、または更新処理により挿入、削除、更新される前記データ型の列を少なくとも二つ構成列に持つインデクスに対するメンテナンス処理を行うように実行手順の作成を行う問合せ解析処理部と、
作成した実行手順に従い、行データから上記インデクスを構成する前記データ型の複数列のデータを構成するインスタンスの内、同一添字にて確定されるインスタンスの組みを添字数分取得し、その取得したインスタンスの組みと、そのインスタンスを含む行を識別するための行識別子とで添字数分のインデクスエントリを作成し、その作成されたインデクスエントリを用いて、上記インデクスをメンテナンスするインデクス管理部として、
コンピュータを機能させる為のプログラムを記録したことを特徴とする媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベース処理方法および装置に適用可能な技術に関するものである。
【０００２】
【従来の技術】
現実世界において多値従属となる情報、すなわちある項目に対して複数の情報を扱う場面は多く存在する。リレーショナルデータベースでは、このような情報を正規形データモデルで扱うのが一般的なアプローチである。すなわち、複数テーブルとその間の関連で実現するアプローチである。
【０００３】
学生の試験の成績に関する情報を成績表２１２、学生のEmailアドレスなどに関する情報を学生名簿表２１１の二つの表に正規化した例を図１に示す。学生名簿表２１１、成績表２１２にそれぞれ学籍番号を有し、それらがキーとなって関連が張られている。この場合、キーとなる情報（学籍番号）が重複するため、その分のデータベース容量が必要となる。
【０００４】
英語の点数が６０以下の成績の学生に英会話教室の案内を電子メールを用いて発送するために対象学生のEmailアドレスを取得したい。その場合、これらの表に対する問合せは次のような複雑なものとなる。また、結合処理を必要とするため処理に時間を要する。
【０００５】
SELECT 学生名簿.Emailアドレス
FROM 学生名簿,成績
WHERE
成績.科目='英語' AND
成績.点数<=60 AND
学生名簿.学籍番号=成績.学籍番号
以上のように正規化データモデルのアプローチでは、社員番号が二つの表に重複するためデータベース容量が大きくなる。また問合せ処理が複雑となり、結合処理を必要とするため処理に時間を要する。
【０００６】
一方、非正規化表にて実現する別のアプローチも存在する。先の２つの表を非正規化して実現したのが図１の成績表２１３である。この場合の問合せ文は以下のように簡単になる。
【０００７】
SELECT DISTINCT Emailアドレス
FROM 成績
WHERE 科目='英語' AND 点数<=60
しかし、科目、点数以外の列（学籍番号、氏名、学部、Emailアドレス）のデータを冗長に持つことになり、データベースが肥大化する。問合せ文は簡単になるが、非正規化表であるため行の件数も多く、結合処理こそは必要とはしないが、DISTINCTを用いて重複排除しなければならず必ずしも高速な検索とはいかない。
【０００８】
データベース問合せ言語ＳＱＬでも、情報の集まりを効率よく扱うためオブジェクト指向拡張の機能の一つとしてコレクション型が導入された。また、公知な技術として 日立：”XDM E2系 プログラム作成の手引き(XDM/RD E2)”,pp27,1997記載の繰り返し列を用いることにより、複数の情報を配列のように１つの列データとして格納することができる。
【０００９】
【発明が解決しようとする課題】
コレクション型も繰り返し列も、列の要素間同士の関連が無いため、前記のような複数条件を有する問合せを行うアプリケーションを構築しようとすると、先に説明した複数の正規化表間の関連によるアプローチもしくは非正規化表によるアプローチのどちらかにならざるを得ない。そして、データベース容量の増大、複雑な問合せ文、検索処理でのパフォーマンスの劣化という問題がある。
【００１０】
本発明の目的は上記問題を解決し、比較可能なインスタンスの集まりを管理するデータベースに対するアクセスを好適に行うことが可能な技術を提供することにある。
【００１１】
【課題を解決するための手段】
本発明のデータベース処理システムでは、インスタンスの集まりで構成され、個々のインスタンスを添字にて確定することが可能なデータ型を扱う。本発明のデータベース処理システムでは、前記データ型の列に対する指定を少なくとも二つ含み、かつ前記列に対する条件の指定を含む述語もしくは関数を含む問合せを受け取り解析し、上記述語もしくは関数に指定されている列に対してインデクスが作成されているかどうかを判定する。
【００１２】
インデクスが作成されている場合には、上記インデクスをアクセスする様に実行手順を決定する。そしてデータベース処理実行時に、実行手順に従いインデクスをアクセスするいことにより、上記述語もしくは関数に指定された条件に合致する同一添字により確定されるインスタンスの組を有するテーブルデータの識別子を取得する。
【００１３】
また、インデクスが作成されていない場合には、テーブルデータをアクセスする様に実行手順を決定する。そしてデータベース処理実行時に、実行手順に従いテーブルデータをアクセスし、そのテーブルデータの前記述語に指定された前記データ型の列のデータを構成するインスタンスの内、同一添字にて確定されるインスタンスの組みを取得し、その取得した少なくとも二つの前記データ型の列から取得したインスタンスの組みのそれぞれのインスタンスに対し前記述語もしくは関数に指定された条件を用いて評価する。
【００１４】
上記インデクスは、インスタンスの集まりで構成され個々のインスタンスを添字にて確定することが可能なデータ型の列を少なくとも二つインデクス構成列に持ち、前記データ型の列のデータを構成するインスタンスの内同一添字にて確定されるインスタンスの組みと、前記データ型の列以外の列データと、行データを識別するための行識別子とから成るインデクスエントリより構成される。そして、テーブルデータの挿入処理、削除処理、更新処理の際、上記インデクスエントリを生成しそれを用いてメンテナンスされる。
【００１５】
以上の様に本発明のデータベース処理システムによれば、ある同じデータ型のインスタンスの集まりを列のデータとして１つの表に格納管理し、複数のその列の要素を組みとして評価するので、表に関するデータベース容量を最小限に抑えることができ、かつ集合を扱う列に対する検索を簡単な問合せ記述によって高速に行うことが可能である。
【００１６】
【発明の実施の形態】
以下に同じデータ型のインスタンスの集まりをデータとして扱うデータベースに対する処理を高速に行う一実施形態のデータベース処理システムについて説明する。
【００１７】
まず、本発明の概念を図３を用いて簡単に説明する。
【００１８】
本実施形態のデータベース管理システムでは、ある同じデータ型のインスタンスの集まりを列データとして管理する。この同じデータ型のインスタンスの集まりからなるデータ型を以降「繰返し型」、「繰返し型」をデータ型とする列を以降「繰返し列」と呼ぶことにする。また、個々のインスタンスを「繰返し列」の要素と呼ぶことにする。
【００１９】
図３の成績表３００において科目列および点数列が繰返し列として定義されており、成績表のイメージを図示している。繰返し列を有する本成績表のテーブルの定義文の一例を以下に示す。
【００２０】
CREATE TABLE 成績（
学籍番号      CHAR(8),
氏名          MVARCHAR(10),
学部          MVARCHAR(10),
Emailアドレス VARCHAR(32),
科目          MVARCHAR(16) ARRAY[32],
点数          INTEGER ARRAY[32])
ここで、繰返し列はARRAYというキーワードで指定されている。科目列は、定義最大長１６バイトのMVARCHAR型データを最大要素数３２個まで格納管理可能であることを示している。同様に点数列は、INTEGER型データを最大要素数３２まで格納可能であることを示している。
【００２１】
繰返し列は、問合せ文において繰返し列名に続く角括弧"["および"]"の間に指定された値により、繰返し列内に格納管理される要素の一つを確定することを可能とする。例えば、科目列の要素の一つの値で「１」により確定する要素の値を射影する問合せ文は以下のようになる。
【００２２】
SELECT 科目[1] FROM 成績
角括弧"["および"]"の間に指定される数値Ｎは、科目列内のＮ番目の要素としての意味を持たせることが多いと考えられる。以降繰返し列名に続く角括弧"["および"]"の間に指定された値を「添字」と呼ぶ。
【００２３】
次のような例を用いて説明する。
【００２４】
英語の点数が６０以下の成績の学生に英会話教室の案内を電子メールを用いて発送するために対象学生のEmailアドレスを取得したい。その場合の成績表に対する問合せを実現するために以下のような問合せ４をデータベース管理システムに対して行う。
【００２５】
SELECT Emailアドレス
FROM 成績
WHERE ARRAY(科目,点数)[ANY](科目='英語' AND 点数<=60)
本実施例では、「英語の点数が６０以下」という評価を実現するためにARRAY述語を用いている。ARRAY述語は、"ARRAY"に続く括弧"(",")"内に指定される複数の繰返し列を添字が同じ要素の組みとして複数項目の繰返しと見なし、そのいずれかの要素が"[ANY]"に続く括弧"(",")"内に指定される条件を満たす場合、真を返す述語である。"ARRAY"に続く括弧"(",")"内の指定繰返し列が複数ではなく一つである場合、ARRAY述語は指定繰返し列のいずれかの要素が"[ANY]"に続く括弧"(",")"内に指定される条件を満たす場合に真を返す。
【００２６】
よって、ARRAY述語を含めた上記問合せ文は、科目列の要素の値が'英語'であり、かつその要素に対応する点数列の要素の値が60以下であるテーブル行のEmailアドレスの値を取得するための問合せである。
【００２７】
上記問い合わせ４をユーザから受け取ったデータベース管理システムは、成績表の各行３０１〜３０５の科目列、点数列に対してARRAY述語を評価する。その結果、英語の点数が５２である要素を有する行３０２および、英語の点数が５９である要素を有する行３０３を条件を満足する検索結果行として選定し、結果５をユーザに返す。
【００２８】
以上により、従来のリレーショナルモデルで複数表の関連にて実現していたインスタンスの集合を、集合を扱える列の値として１つの表に格納でき、データベース容量を最小限に抑えることができる。また、複数の繰返し列の要素を組みとして評価することにより、集合を扱う列に対する検索を簡単な問合せ記述によって実現することができる。その問合せ文は上記１つの表に対するものであり、アクセス領域最小限に抑えられることから、問合せ実行処理も効率的に実現することができる。問合せ実行に関しては、複数の繰返し列の要素の組みをキーとしたインデクスを適用することにより、さらなる高速実行を実現することができる。
【００２９】
次に図４に本実施形態のデータベース管理システムの概略構成を示す。図４に示す様に本実施形態のデータベース管理システム１は、問合せ解析処理部１０、データベース処理実行制御部２０、テーブルデータ管理部３０、インデクス管理部４０、データベース領域アクセス処理部５０、定義処理・ディクショナリ管理部６０を有する。
【００３０】
問合せ解析処理部１０は、ユーザあるいはアプリケーションプログラムからの問合せ要求４を受け付け解析し、データベースに対するアクセスのための適切な実行手順を生成する。また、問合せ解析処理部１０は、データベースアクセスにより取得した問合せ要求４の実行結果データを問合せ元に返す機能も有する。問合せ要求４が、データ格納、削除、更新、検索などのデータ操作処理(ＤＭＬ)要求の場合は、処理制御をデータベース処理実行制御部２０に渡す。テーブル定義やインデクス定義などのデータ定義処理(ＤＤＬ)の場合には、処理制御を定義処理・ディクショナリ管理部６０に渡す。問合せ解析処理部１０は、問合せ要求４を解析する際に、問合せ文中にARRAY述語が含まれている場合、そのARRAY述語を評価するためのインデクスが利用可能であるかを決定する処理１１を行い、その結果を実行手順作成処理１２において実行手順に反映する。
【００３１】
データベース処理実行制御部２０は、問合せ解析処理部１０により生成された実行手順に従ってテーブルデータ管理部３０やインデクス管理部４０などを用いデータベースアクセスの実行制御を行い、アクセスの結果取得したデータを問合せ要求元に返すために問合せ解析処理部１０に渡す。
【００３２】
テーブルデータ管理部３０は、データベース領域２に格納されているテーブルデータ２１を管理する。具体的には、テーブルデータ２１に対しデータの格納、削除、更新、検索処理をデータベース領域アクセス処理部５０を経由し行う。テーブルデータ２１には、図３を用いて説明した繰返し列を有するテーブルデータも含まれている。テーブルデータ管理部３０は、問合せ文中にARRAY述語が含まれ、その評価にインデクスを使用しないと実行手順により指示されている場合、テーブルの行データに対しARRAY述語評価処理３１を行う機能を有している。
【００３３】
インデクス管理部４０は、データベース領域２に格納されているインデクス２２を管理する。具体的には、テーブルデータ２１の更新に伴い、それに関連するインデクス２２に対し更新処理をデータベース領域アクセス処理部５０を経由し行うインデクス更新処理４２の機能を有する。また、インデクス２２をアクセスすることにより、ARRAY述語に対して真であるようなテーブル行の検索を高速に行うためのインデクス検索処理４１の機能を有する。
【００３４】
データベース領域アクセス処理部５０は、前述のようにテーブルデータ管理部３０あるいはインデクス管理部４０からの要求に従い、データベース領域２に格納されているテーブルデータ２１あるいはインデクス２２に対するアクセスを行う。
【００３５】
定義処理・ディクショナリ管理部６０は、ディクショナリ３に格納されているスキーマ情報、テーブル情報などの各種定義情報を管理する。ディクショナリ３に格納されている定義情報にはデータベース領域２に格納されているインデクス２２に関する定義情報であるインデクス３１も含んでいる。定義処理・ディクショナリ管理部６０は、問合せ要求４がデータ定義処理(ＤＤＬ)の場合に、問合せ解析処理部１０の解析結果である定義情報をデクショナリ３に登録する。
【００３６】
データベース管理システム１を問合せ解析処理部１０、データベース処理実行制御部２０、テーブルデータ管理部３０、インデクス管理部４０、データベース領域アクセス処理部５０、定義処理・ディクショナリ管理部６０として機能させる為のプログラムは、それぞれＣＤ−ＲＯＭ等の記録媒体に記録され磁気ディスク等に格納された後、メモリにロードされて実行されるものとする。なお前期プログラムを記録する媒体はＣＤ−ＲＯＭ以外の他の媒体でも良い。また、ネットワーク上の別コンピュータシステムを経由してメモリのロードされて実行されるものでも良い。
【００３７】
図２は本実施形態のコンピュータシステムのハードウエア構成の一例を示す図である。コンピュータシステム２０００は、ＣＰＵ２００２、主記憶装置２００１、磁気ディスク装置等の外部記憶装置２００３及び多数の端末２００４で構成される。主記憶装置２００１上には、図４を用いて先に説明したデータベース管理システム１が置かれ、外部記憶装置２００３上にはデータベース管理システム１が管理するテーブルデータ２１とインデクス２２を含むデータベース領域２が格納される。また、ディクショナリ３も外部記憶装置２００３上に格納される。さらに、データベース管理システム１を実現するプログラムも外部記憶装置２００３上に格納される。
【００３８】
図５はテーブルデータ２１として格納される個々の行データの格納構造の一形態を示す図である。行データは、データレコード５３０という形態にて、入出力の単位であるページ５００の中に格納される。ページ５００はデータベース領域２の構成単位である。１つのページ５００内には、複数のデータレコード５３０が格納可能である。データレコード５３０のページ内の格納位置は、スロット５２０により指示される。スロット５２０の領域には指示するデータレコード５３０が格納されているページ５００の先頭からの格納位置が記憶される。ページ制御情報５１０は、スロットの割当て状況などのスロット管理およびページ内の使用状況などの領域管理を行うためのものである。データレコード５３０は、繰返し列のデータが記憶される繰返し列データフィールド５３２を含む。また、データレコード５３０は、繰返し列とは別のカラムデータフィールド５３３と、データレコード５３０内のこれらデータフィールドを管理するためのレコードヘッダ５３１を有する。
【００３９】
繰返し列データフィールド５３２には、繰返し列のデータを構成する要素が配列構造にて格納されている。よって、要素へのアクセスは添字を用いて容易に可能な形態になっている。本形態では、繰返し列データフィールド５３２は、データレコード５３０内に直接格納されているが、別レコードして実現しデータレコードから論理的にポイントされる形態でもかまわない。また、配列構造である必要はなく、添字により格納位置が確定しさえすればよい。
【００４０】
図６は本実施形態のインデクス２２の構成例を示す図である。図６では、データベース領域２に格納されるインデクス２２の構成の一形態を表している。図６に示す様に、インデクス２２はインデクスエントリ２２１から成る。
【００４１】
インデクスエントリ２２１は、インデクスキー２２２と、その行データの実体であるデータレコード５３０をアクセスするためのレコード識別子２２３により構成される。
【００４２】
インデクスキー２２２は、行データ内のインデクスが定義されている繰返し列のデータの内、ある添字により確定される要素の値により生成される。インデクスを複数の繰返し列に対して定義した場合、その複数の繰返し列のデータの内ある添字により確定される要素の値の組みによってインデクスキー２２２は生成される。
【００４３】
図６の例では、成績表の２つの繰返し列（科目、点数）に対して定義されたインデクスを示している。本例のインデクスキー２２２は、科目列の要素の値＋点数列の要素の値というデータ構造を採っている。
【００４４】
インデクスの定義は、例えば以下のようなＳＱＬに類似した要求文により行われる。
【００４５】
CREATE INDEX ARRAY_IDX1 ON 成績（科目,点数）
ここで、ARRAY_IDX1は定義されたインデクスの対して付けたインデクス名称である。
【００４６】
レコード識別子２２３は、データレコード５３０が格納されるページ５００を一意に識別するためのページ識別子２２４と、ページ内のデータレコード格納位置を特定するためのスロット５２０を示すスロット番号２２５から成る。スロット番号２２５は、ページ格納構造においてページ制御情報５１０側から順次番号付けされる。図６では、「ページ識別子＋スロット番号」という構造を採っているが、「スロット番号＋ページ識別子」でもなんら問題はない。レコード識別子２２３を用いてデータレコードをアクセスする。具体的には、レコード識別子２２３を構成するページ識別子２２４を用いて格納ページをアクセスし、スロット番号２２５に対応するスロットに記録されているデータレコード格納位置を取得することによってデータレコード５３０に対するアクセスは行われる。
【００４７】
１つの行データの繰返し列は複数の要素を有するため、１行データに対し要素数分のインデクスキー２２２すなわちインデクスエントリ２２１が存在する。すなわち、同一レコード識別子２２３が複数のインデクスエントリ２２１内に存在することとなる。図６の例では、{Page25,2},{Page30,4}というレコード識別子が２つのインデクスエントリ２２１に存在している。
【００４８】
インデクスは、複数の繰返し列に対してのみではなく、繰返し型以外の列と繰返し列との組み合わせに対して定義してもかなわない。
【００４９】
図１３、図１４、図１５にインデクスを構成する列のバリエーションを例として示す。
【００５０】
図１３は、一つの繰返し列にインデクスを定義した場合のインデクスエントリ２２１の例を示している。繰返し列Ｃ３に対してインデクス定義された表１３００の行データ１３０１(レコード識別子：row13)に対応したインデクスエントリ２２１を表１３００の右側に図示している。インデクスエントリ２２１内のインデクスキー２２２は繰返し列Ｃ３の要素の値によって生成されている。行データ１３０１において繰返し列Ｃ３に格納される要素数は４であることから、レコード識別子row13を有するインデクスエントリ２２１は４つである。ここで繰返し列の要素の値が重複する場合、１インデクスエントリ２２１内に重複数分のレコード識別子が格納管理されることになる。
【００５１】
図１４は、二つの繰返し列にインデクスを定義した場合のインデクスエントリ２２１の例を示している。繰返し列Ｃ３およびＣ４に対してインデクスが定義された表１４００の行データ１４０１（レコード識別子：row14)に対応したインデクスエントリ２２１を表１４００の右側に図示している。インデクスエントリ２２１内のインデクスキー２２２は繰返し列Ｃ３の要素の値およびその要素の添え字に対応した繰返し列Ｃ４の要素の値によって生成されている。
【００５２】
図１５は、二つの繰返し列および一つの繰返し列以外の列にインデクスを定義した場合のインデクスエントリ２２１の例を示している。繰返し列以外の列Ｃ２、繰返し列Ｃ３およびＣ４に対してインデクスが定義された表１５００の行データ１５０１(レコード識別子：row15)に対応したインデクスエントリ２２１を表１５００の右側に図示している。インデクスエントリ２２１内のインデクスキー２２２は、列Ｃ２の値、繰返し列Ｃ３の要素の値およびその要素の添え字に対応した繰返し列Ｃ４の要素の値の３つによって生成されている。
【００５３】
本インデクス２２は、ARRAY述語に指定されている条件に合致する列値を有するデータレコードのレコード識別子を取得するためのものであり、本構成例のようにインデクスエントリ２２１がテーブル構造のように実装されている必要はなく、図７に示すようなＢ木インデクス等のデータアクセス高速手段として実現することが多い。
【００５４】
図７は本実施形態のインデクス２２のデータ構造をＢ木インデクスとしての実現した場合の例を示す図である。Ｂ木インデクス２２は、ルートノード７０１、中間ノード７０２、リーフノード７０３により構成される。
【００５５】
ルートノード７０１を頂点に木構造を形成している。木構造の末端のリーフノード７０３に、インデクスエントリ２２１が格納管理されている。ルートノード７０１および中間ノード７０２には下位に位置するノードへのポインタを有するエントリが格納管理される。
【００５６】
ルートノード７０１、中間ノード７０２、リーフノード７０３は、入出力の単位であるページにより実現されることが多い。図４を用いて説明したインデクス検索処理４１において、ARRAY述語に指定された条件より生成したキーを用いて、ルートノード７０１より中間ノード７０２を経由しリーフノード７０３まで木構造を辿る。ルートページ７０１および中間ノード７０２はメモリ常駐することによりＩＯ回数を削減することが可能になり高速なアクセスを実現することができる。
【００５７】
図８は本実施形態の問合せ解析処理部１０の処理手順を示すフローチャートである。図８では問合せ解析処理部１０で問合せ４内にARRAY述語が出てきた場合のARRAY述語対応インデクス使用決定処理１１の処理内容を表している。
【００５８】
ユーザからの問合せ４の解析にて、ディクショナリ３に登録してあるインデクス定義情報３１を基に、ARRAY述語評価にインデクスを使用する実行手順を生成するか、インデクスを使用しない実行手順を生成するか決定する。まず、ステップ８０１においてARRAY述語部を解析しARRAY述語に指定されているカラム名を取得する。次にステップ８０２にて取得したカラム名に関連したインデクス定義情報３１を取得する。このインデクス定義情報３１の取得処理は、定義処理・ディクショナリ管理部６０に要求して実現する。ステップ８０３にて関連したインデクス定義情報が取得できた場合、ステップ８０４に進みそのインデクスをARRAY述語評価に使用するように実行手順を生成することを決定し、ステップ８０６にて処理を終了する。
【００５９】
ステップ８０３にて関連したインデクス定義情報が取得できなかった場合、使用可能なインデクスは定義されないと判断し、ステップ８０５にてARRAY述語評価にはインデクスは使用せずデータレコードをアクセスし繰り返し列データを評価するように実行手順を生成することを決定し、ステップ８０６にて処理を終了する。
【００６０】
図９は本実施形態のインデクス管理部４０の処理手順を示すフローチャートである。図９では、問合せ文中にARRAY述語が含まれ、その評価のために利用可能なインデクスが存在し、それを使用することを実行手順により指示されている場合のインデクス検索処理４１の処理内容を表している。
【００６１】
まず、ステップ９０１においてARRAY述語に指定されている条件よりインデクス検索キーの生成を行う。図３の説明で使用した問い合わせ文では、科目='英語'および点数=60を用いてインデクス検索キー{'英語',60}を生成する。次にステップ９０１で生成したインデクス検索キーを用いてインデクスエントリのサーチを行う。ここでは、条件「科目='英語' AND 点数<=60」に合致するインデクスエントリをサーチする。そして、ステップ９０３において条件に合致するインデクスエントリ見つかった場合、ステップ９０４に進みインデクスエントリ内のレコード識別子を取得し、ステップ９０５にて取得レコード識別子をデータベース処理実行制御部３０に対し返却し、ステップ９０７にてインデクス検索処理を終了する。ここで返却されたレコード識別子は、データベース処理実行制御部３０にて、射影処理等のためのデータレコードアクセスに用いられる。
【００６２】
ステップ９０３において条件に合致するインデクスエントリが見つからなかった場合、ステップ９０８において検索結果なしとデータベース処理実行制御部３０に返却し、ステップ９０７にてインデクス検索処理を終了する。
【００６３】
図１０および図１１は本実施形態のインデクス管理部４０の処理手順を示すフローチャートである。図１０および図１１ではインデクスが定義された繰返し列を含むテーブルデータ２１の更新に伴う場合のインデクス更新処理４２の処理内容を表している。
【００６４】
問合せ解析処理部１０で生成した実行手順にて更新対象であると指示されたインデクスに対して更新を行う。まず、ステップ１００１において問合せ解析処理部１０で生成した実行手順を参照し、テーブルデータ２１に施された処理の種別を判定する。判定の結果、テーブルデータに施された処理が挿入処理である場合、ステップ１００２に進む。
【００６５】
ステップ１００２において挿入されたテーブルデータの内更新対象インデクスを構成する列データを取得する。メモリ上に存在する挿入テーブルデータから取得するのが効率的である。繰返し列の場合、要素の一つを挿入データとして取得する。次にステップ１００３においてステップ１００２で取得したデータを用いてインデクスキーの作成を行う。そして、ステップ１００４において先に作成したインデクスキーを用いてインデクス内をサーチしインデクスエントリ更新位置を見つける。ステップ１００５においてサーチ対象インデクスキーに対応するインデクスエントリが見つかったかどうか判定し、インデクスエントリが見つかりすでに存在する場合ステップ１００６に進む。そしてステップ１００６において見つかったインデクスエントリにレコード識別子を追加する。ステップ１００５における判定にてインデクスエントリが見つからなかった場合、ステップ１００７において新規インデクスエントリを作成し、インデクスに追加する。
【００６６】
ステップ１００６およびステップ１００７において１インデクスエントリの更新処理を終了した後、ステップ１００８において追加データがさらに存在するかどうかを判定する。すなわち、繰返し列のさらなる要素が存在するかどうかを判定する。追加データがさらに存在する場合、ステップ１００２に戻りインデクスに対しレコード識別子の追加あるいは新規インデクスエントリの追加を前述のように行う。追加データがすでに無い場合、繰返し列の要素数分の更新処理が完了としてステップ１０２６にてインデクス更新処理を終了する。
【００６７】
戻ってステップ１００１において判定結果が削除処理である場合、ステップ１００９に進む。ステップ１００９では削除されたテーブルデータの内更新対象インデクスを構成する列データを取得する。テーブルデータを削除する際、メモリ上にインデクス更新に必要な列データを保持しておく。繰返し列の場合、要素の一つを削除データとして取得する。次にステップ１０１０においてステップ１００９で取得したデータを用いてインデクスキーの作成を行う。そして、ステップ１０１１において先に作成したインデクスキーを用いてインデクス内をサーチしインデクスエントリ更新位置を見つけ、ステップ１０１２においてインデクスエントリからレコード識別子を削除する。ここでレコード識別子の削除によってインデクスエントリ無いのレコード識別子の数が０個になった場合、インデクスエントリの削除を行ってもよい。その後ステップ１０１３において
削除データがさらに存在するかどうかを判定する。すなわち、繰返し列のさらなる要素が存在するかどうかを判定する。削除データがさらに存在する場合、ステップ１００９に戻りインデクスに対しレコード識別子の削除を前述のように行う。削除データがすでに無い場合、繰返し列の要素数分の更新処理が完了したとしてステップ１０２６にてインデクス更新処理を終了する。
【００６８】
戻ってステップ１００１において判定結果が更新処理である場合、１０１４からステップ１０１５に進む。ステップ１０１５以降は図１１に示してある。ステップ１０１５では更新されたテーブルデータの内インデクスを構成する更新前の列データを取得する。テーブルデータを更新する際、メモリ上にインデクス更新に必要な列データを更新前列データとして保持しておく。繰返し列の場合、要素の一つを更新前データとして取得する。次にステップ１０１６においてステップ１０１５で取得したデータを用いてインデクスキーの作成を行う。そして、ステップ１０１７において先に作成したインデクスキーを用いてインデクス内をサーチしインデクスエントリ更新位置を見つけ、ステップ１０１８においてインデクスエントリからレコード識別子を削除する。ここでレコード識別子の削除によってインデクスエントリ無いのレコード識別子の数が０個になった場合、インデクスエントリの削除を行ってもよい。その後、ステップ１０１９において、更新されたテーブルデータの内インデクスを構成する更新後の列データを取得する。
【００６９】
メモリ上に存在する更新テーブルデータから取得するのが効率的である。繰返し列の場合、要素の一つを更新後データとして取得する。次にステップ１０２０において先に取得したデータを用いてインデクスキーの作成を行う。そして、ステップ１０２１において先に作成したインデクスキーを用いてインデクス内をサーチしインデクスエントリ更新位置を見つける。ステップ１０２２においてサーチ対象インデクスキーに対応するインデクスエントリが見つかったかどうか判定し、インデクスエントリが見つかりすでに存在する場合ステップ１０２３に進む。そして、ステップ１０２３において見つかったインデクスエントリにレコード識別子を追加する。ステップ１０２２における判定にてインデクスエントリが見つからなかった場合、ステップ１０２４において新規インデクスエントリを作成し、インデクスに追加する。
【００７０】
ステップ１０２３およびステップ１０２４において１インデクスエントリの更新処理を終了した後、ステップ１０２５において更新データがさらに存在するかどうかを判定する。すなわち、繰返し列のさらなる要素が存在するかどうかを判定する。更新データがさらに存在する場合、ステップ１０１５に戻る。更新データがすでに無い場合、繰返し列の要素数分の更新処理が完了したとしてステップ１０２６にてインデクス更新処理を終了する。
【００７１】
図１２は本実施形態のテーブルデータ管理部３０の処理手順を示す処理フローである。図１２では問合せ文中にARRAY述語が含まれ、その評価にインデクスを使用しないと実行手順により指示されている場合のテーブルの行データに対するARRAY述語評価処理３１の処理内容を表している。
【００７２】
インデクス等を用いて取得したARRAY評価対象のレコード識別子を用いてデータレコードをアクセスし、指定列データに対しARRAY述語を評価する。まず、ステップ１２０１においてインデクス等を用いて絞り込んだ検索結果候補である行のレコード識別子を取得する。そしてレコード識別子内のページ識別子よりデータレコードが格納されているページをアクセスする。さたにレコード識別子内のスロット番号によりデータレコードをアクセスし、ステップ１２０４において繰返し列データフィールドをアクセスする。そしてステップ１２０５において繰返し列から要素データを１つ取り出し、ステップ１２０８において要素データに対しARRAY述語内の条件の判定を行う。ARRAY述語内の条件の判定結果が真の場合、ステップ１２０８にてARRAY述語評価処理を終了する。その場合、その後射影列データの取り出し処理などを行う。
【００７３】
戻ってステップ１２０８において要素データに対するARRAY述語内の条件の判定結果が偽の場合、さらに次の要素データに対するARRAY述語内の条件の判定を行うためにステップ１２０７に進み、次の要素データが存在するか判定する。次の要素データが存在する場合、ステップ１２０５に戻る。すでに要素データが無い場合、最終的なARRAY述語の判定結果が偽としてARRAY述語評価処理を終了する。その場合、次のデータレコードに対するARRAY述語評価処理を行う。
【００７４】
以上示したフローチャートの処理は、図４で例として示したコンピュータシステムにおけるプログラムとして実行される。しかし、そのプログラムは図２の例の様にコンピュータシステムに物理的に直接接続される外部記憶装置に格納されるものと限定はしない。ハードディスク装置、フロッピーディスク装置等のコンピュータで読み書きできる記憶媒体に格納することができる。また、ネットワークを介して図２のコンピュータシステムとは別のコンピュータシステムに接続される外部記憶装置に格納することもできる。
【００７５】
本実施形態では、繰返し列に対する評価機能をARRAY述語で実現しているが、ARRAY述語である必要はなく他の述語でもよい。さらに、関数であってもかまわない。本実施例では、ARRAY述語を実現する機能において複数の繰返し列の要素の値を組みで扱うようになっているが、必ずしもARRAY述語の機能である必要はない。例えば、表定義文であるCREATE TABLE文におけるオプション指定という実施例も有りうる。
【００７６】
以上説明した様に本実施形態のデータベース処理システムによれば、ある同じデータ型のインスタンスの集まりを繰返し列と呼ぶ列のデータとして１つの表に格納管理するので、表に関するデータベース容量を最小限に抑えることができる。また、複数の繰返し列の要素を組みとして評価することにより、集合を扱う列に対する検索を簡単な問合せ記述にて高速に行うことが可能である。
【００７７】
【発明の効果】
本発明によれば、比較可能なインスタンスの集まりを繰返し列と呼ぶ列のデータとして管理することにより、データベースへのアクセスを好適に行うことが可能となる。
【図面の簡単な説明】
【図１】従来の同じデータ型のインスタンスの集まり扱う場合のテーブルを示す図である。
【図２】本実施形態のコンピュータシステムのハードウエア構成の一例を示す図である。
【図３】本発明の概念図である。
【図４】本実施形態のデータベース処理システムの機能ブロックを示す図である。
【図５】本実施形態のテーブルデータレコード格納ページ構造の一例を示す図である。
【図６】本実施形態のインデクスの構成の一例を示す図である。
【図７】本実施形態のインデクスの構造の一例を示す図である。
【図８】本実施形態の問合せ解析処理部１０の処理手順を示すフローチャートである。
【図９】本実施形態のインデクス管理部４０のインデクス検索処理の処理手順を示すフローチャートである。
【図１０】本実施形態のインデクス管理部４０のインデクス更新処理の処理手順を示すフローチャートである。
【図１１】本実施形態のインデクス管理部４０のインデクス更新処理の続きの処理手順を示すフローチャートである。
【図１２】本実施形態のテーブルデータ管理部３０の処理手順を示すフローチャートである。
【図１３】本実施形態のインデクスキー構成の一例を示す図である。
【図１４】本実施形態のインデクスキー構成の一例を示す図である。
【図１５】本実施形態のインデクスキー構成の一例を示す図である。
【符号の説明】
１…データベース管理システム、２…データベース領域、３…ディクショナリ、４…問合せ、１０…問合せ解析処理部、２０…データベース処理実行制御部、３０…テーブルデータ管理部、４０…インデクス管理部、５０…データベース領域アクセス処理部、６０…定義処理・ディクショナリ管理部、２１…テーブルデータ、２２…インデクス、３１…インデクス定義情報、１１…ARRAY述語対応インデクス使用決定処理、１２…実行手順作成処理、３１…ARRAY述語評価処理、４１…インデクス検索処理、４２…インデクス更新処理、２２２…インデクスキー、２２３…レコード識別子、２２４…ページ識別子、２２５…スロット番号、５３２…繰返し列データフィールド。
【図１】
0003914662.tif 000002
【図２】
0003914662.tif 000003
【図３】
0003914662.tif 000004
【図４】
0003914662.tif 000005
【図５】
0003914662.tif 000006
【図６】
0003914662.tif 000007
【図７】
0003914662.tif 000008
【図８】
0003914662.tif 000009
【図９】
0003914662.tif 000010
【図１０】
0003914662.tif 000011
【図１１】
0003914662.tif 000012
【図１２】
0003914662.tif 000013
【図１３】
0003914662.tif 000014
【図１４】
0003914662.tif 000015
【図１５】
0003914662.tif 000016