(57)【要約】【課題】ディスク・アクセス回数を減少し、クエリーを効率よく高速に処理する。【解決手段】  クエリー・オプティマイザ５００は問い合わせのあったクエリーの最適化を行って関係代数で構成された処理ツリー５０２を作成する。クエリー・オプティマイザ５００によって作成された処理ツリー５０２からトポロジカル・ソートの順番で直接的に処理できるタスクを見出し、これらのタスクをそれぞれのタスクがアクセスするデータベースのリレーションをもとにグループ分けを行い、共通のリレーションに対して処理を行うタスクを集めたグループをグループ列（キュー）５０５に挿入する。マルチオペレーション・プロセッサ５０４は利用できるオペレーティングシステムのプロセスの数に応じてグループ列５０５からグループを取り出して、それぞれのプロセス５０６にマルチオペレーション法を用いたグループの処理を行わせる。【選択図】図１
2008165622.tif 000002
【特許請求の範囲】
【請求項１】
マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースへのアクセス領域ごとにグループ分けするクループ分け手段と、
前記グループ分けされたタスクごとに、マルチオペレーション・プロセッシングを行う
マルチオペレーション・プロセッシング手段と
を備えることを特徴とするクエリー処理システム。
【請求項２】
請求項１に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクの処理コストを計算し、処理コストの小さい順にタスクの処理を行い、タスクの処理で読み出したアクセス部分に対するグループ内の他のタスクの処理部分の処理も行うことを特徴とするクエリー処理システム。
【請求項３】
請求項２に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段は、タスクの処理後、アクセスした部分の格納位置をメインメモリ上に残し、各タスクの処理の内、処理が完了した部分を示すことを特徴とするクエリー処理システム。
【請求項４】
請求項３に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段は、タスクの処理の際、グループ内のこれから処理を行う他のタスクの、インデックスによりアクセスする部分の最初及び／又は最後の格納位置をメインメモリ上に残し、該タスクのアクセスする部分を示すことを特徴とするクエリー処理システム。
【請求項５】
請求項１に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクのアクセス部分の格納位置を調べ、前記グループ分けされたタスクの処理コストを計算し、処理コストの小さいタスク順に調べた格納位置を並べ、この順にアクセス部分を読み出し、読み出したアクセス部分にアクセスするタスクをグループ内から抽出して実行することを特徴とするクエリー処理システム。
【請求項６】
請求項１〜５のいずれかに記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項７】
請求項１〜５のいずれかに記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースのクエリー処理システムに関し、特に、複数のクエリー(検索の問い合わせ)が同時に共通のリレーション(Relation)に対して処理を行う場合に関するものである。
【背景技術】
【０００２】
従来は、ユーザからデータベース・マネージメント・システム（ＤＢＭＳ）に対して、いくつかの問い合わせがあると、データベース・マネージメント・システムは、トランザクションの同時処理制御機能を使用してそれぞれの問い合わせの処理を行っている。
検索のみのトランザクションは、クエリー(問い合わせ)と呼び、クエリーの処理を行うクエリー・プロセッサは、各クエリーに対してクエリーの最適化を行って、ＳＱＬなどの問い合わせ言語で記述されたクエリーを、関係代数を接点とするタスクで構成された処理ツリーに変換して、処理ツリーの処理を行っている。クエリー・プロセッサは、作成したいくつもの処理ツリーを複数のオペレーティングシステムのプロセスを用いて同時に処理を行うことになるが、各プロセスに個々の処理ツリーの処理を行わせるため、それぞれの処理ツリーの処理は独立している。処理ツリーの処理とは、処理ツリー内の関係代数を接点とするいくつものタスク処理を順番に行っていくことである。
【０００３】
関係代数とは、データベースのリレーションに対して、直接的に処理を行う演算であり、選択演算(σ)、射影演算(π) 、結合演算(|X|)などがある。複数のプロセスによっていくつかの処理ツリーの処理が同時に行われると、これらの処理ツリー内のタスク処理のためにデータベースのリレーション内のブロックがアクセスされ、数多くのタスクが共通のリレーションに対して処理を行うときは、リレーション内の同じブロックが何度もディスクからアクセスされるといった問題が起こる。
また、１つのタスク処理がディスクからブロックをアクセスしている間、同じブロックで処理を行う必要のある他のタスク処理は、前のタスク処理がブロックをアクセスし終わるまで待たなければならなくなるといった問題も起こってくる。
【０００４】
このように従来のクエリーの処理方法では、クエリーの処理を行うために、ディスク上のブロックが何度もアクセスされ、アクセスするたびにブロック内のデータが繰り返してメインメモリに読み込まれて処理が行われるので効率的ではなく処理速度が低下することになる。その結果、ユーザから問い合わせられる数多くのクエリー処理にすばやく対応することができなくなる。例えば、インターネットを経由して、データベース・サーバに数多くの問い合わせが集中すると、「サーバーにアクセスが集中しているのでしばらくお待ちください」、「しばらくしてからもう一度アクセスしてください」などといったメッセージが表示され、ユーザは、問い合わせを要求することができなくなる。このような問題点を解決するために、ディスクをアクセスする回数を減らしてクエリーの処理速度を向上させるために次に述べる方法が用いられる。
【０００５】
ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させるには、問い合わせの多いクエリーとクエリーの処理結果、クエリーに含まれる演算（選択演算、射影演算、結合演算などの関係代数）と演算の処理結果(クエリーの中間結果)を一時的にディスクに保存(キャッシング)しておく方法がよく用いられる（非特許文献１〜５参照）。
ユーザからクエリーの問い合わせがあると、データベース・マネージメント・システムは、問い合わせのあったクエリーと同じクエリーの処理結果がディスクに保存されているかどうかを調べて、保存されているならば、そのクエリーの処理を行わずに、保存されているクエリーの処理結果をそのままユーザに返すことになる。また、クエリーは異なるけれども、クエリーに含まれる演算と同じ演算の処理結果がディスクに保存されているならば、データベース・マネージメント・システムは、その演算の処理を行わずに、すでに存在する演算の処理結果を利用してクエリーの処理を行うことになる。
この方法は、保存するクエリーの処理結果、演算の処理結果を増やすことで、同じクエリーや演算の処理を繰り返して行うことなしに、クエリーの処理速度を向上させることを目的としている。しかし、この方法は、問い合わせのあったクエリーやクエリーに含まれる演算がディスクに保存されているものと同じでなければならないため、クエリーや演算が異なる場合は、保存されている処理結果を利用することはできない。また、この方法は、データベースに新たなレコードが加えられるなどしてデータベースが更新されると、保存されている処理結果は古くなるので、データベース・マネージメント・システムは、古くなった処理結果を破棄しなければならない。そのためデータベースの更新がたびたび行われると効率的ではなくなる。
マイクロソフト社のSQLサーバーなどのデータベース・マネージメント・システムは、クエリーの処理速度を維持するために、古くなったクエリーの処理結果をすぐには破棄せずに、しばらく古い処理結果をユーザに返すようにしている。
【０００６】
ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させるその他の方法は、クエリーを処理するためによくアクセスされるディスク上のブロックの複製をメインメモリに一時的に保存(キャッシング)しておく方法が用いられる（非特許文献６〜１０参照）。
この方法は、ユーザからクエリーの問い合せがあると、データベース・マネージメント・システムは、クエリーを処理するためにディスクからアクセスするブロックの複製がメインメモリに保存されているかどうかを調べて、保存されているならば、メインメモリ内の複製を利用する。この方法は、メインメモリ内で保存するブロックの容量を増やしておくことで、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることを目的としている。
【０００７】
しかし、この方法は、ディスク上のブロックとメインメモリ上の複製が同じでなければならないため、ブロック内のデータを変更するときには、ディスク上のブロックとメインメモリ上の複製の両方を更新しておかなければならない。
また、クエリーを処理するために数ギガバイトもあるようなデータベースのリレーションを線形探索(スキャン)するような場合は、メインメモリ内で保存されているブロック以外のほとんどのブロックをディスクからアクセスすることになるので有効ではない。
また、オペレーティングシステム自体もこのようなメモリ管理を行っているため、データベース・マネージメント・システムがメインメモリに保存するブロックの容量を増やすと、メインメモリに保存したはずのブロックがオペレーティングシステムによって仮想メモリ(ディスク)に移動されるなどして、逆にクエリーの処理速度が低下するといった問題が起こる。
【０００８】
以上に述べたようなキャッシングを用いた方法は、オラクルデータベース、MySQL、マイクロソフトSQLサーバーなど数多くのデータベース・マネージメント・システム(ＤＢＭＳ)において幅広く採用されている。しかしこれらの方法は、以上に述べたような問題点があるため必ずしも効率的な方法ではない。
【０００９】
【非特許文献１】Finkelstein, S. Common Expression Analysis in Database Applications. In Proceedings of the International Conference of the Management of Data(SIGMOD'82, Orland, Florida, June 2-4), 1982
【非特許文献２】Yigal Arens and Craig A. Knoblock. Intelligent Cashing: Selecting, Representing and Reusing Data in an Information Server. ACM Press, Proceedings of the third international conference on Information and knowledge management, November 1994
【非特許文献３】Hyunchul Kang, Seungchul Han, Younghyum Kim. Schemes of Storing XML Query Cache. Proceedings of the sixteenth Australasian database conference, Volume 39 ADC 2005
【非特許文献４】Bhushan Mandhani, Dan Suciu, Query Caching and View Selection for XML Databases, Proceedings of the 31st international conference on Very large data bases,VLDB 2005
【非特許文献５】Michael J. Carey, Michael J. Franklin, Miron Livny, and Eugene J. Shekita. Data caching tradeoffs in client-server DBMS architectures. In Proceedings of the ACM SIGMOD, pages 357-366, 1991
【非特許文献６】Giovanni Mario Sacco and Mario Schkolnick. Buffer Management in Relational Database Systems. ACM Transactions on Database Systems, Volume 11, no. 4, pp. 473-498, December 1986
【非特許文献７】Chou, H. And DeWitt, D. An Evaluation of Buffer Management Strategies for Relational Database Systems. Proceedings of VLDB, 1985
【非特許文献８】O'Neil EJ, O'Neil PE, Weikum G. The LRU-K Page Replacement Algorithm For Database Disk Buffering. In ACM SIGMOD Conf., 1993, Washington, D.C., pp 297-306
【非特許文献９】Zhifeng Chen, Yan Zhang, Yuanyuan Zhou. Empirical Evaluation of Multi-level Buffer Cache Collaboration for Storage systems. ACM SIGMETRICS international conference on Measurement and modeling of computer systems SIGMETRICS 2005, Volume 33 Issue 1
【非特許文献１０】Michael Stonebraker. Operating System Support for Database Management.  Communications of The ACM, 24(7):412-18, July 1981
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明では、キャッシングを用いた方法ではなく、別の方法でディスクをアクセスする回数を減少させて、実際には一度だけディスクのブロックをアクセスすることで、ユーザから問い合わせられる数多くのクエリーを効率よく高速に処理していく手法を提案する。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明は、マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースへのアクセス領域ごとにグループ分けするクループ分け手段と、前記グループ分けされたタスクごとに、マルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段とを備えることを特徴とする。
前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクの処理コストを計算し、処理コストの小さい順にタスクの処理を行い、タスクの処理で読み出したアクセス部分に対するグループ内の他のタスクの処理部分の処理も行うとよい。前記マルチオペレーション・プロセッシング手段は、さらに、タスクの処理後、アクセスした部分の格納位置をメインメモリ上に残し、各タスクの処理の内、処理が完了した部分を示すことが望ましい。
前記マルチオペレーション・プロセッシング手段は、タスクの処理の際、グループ内のこれから処理を行う他のタスクの、インデックスによりアクセスする部分の最初及び／又は最後の格納位置をメインメモリ上に残し、該タスクのアクセスする部分を示すことで、さらにディスクへのアクセスを減少することができる。
前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクのアクセス部分の格納位置を調べ、前記グループ分けされたタスクの処理コストを計算し、処理コストの小さいタスク順に調べた格納位置を並べ、この順にアクセス部分を読み出し、読み出したアクセス部分にアクセスするタスクをグループ内から抽出して実行してもよい。
上述のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやそのプログラムを記録した記録媒体も本発明である。
【発明の効果】
【００１２】
ＳＱＬなどの問い合わせ言語で記述されたクエリーを、関係代数を接点とするタスクで構成された処理ツリーに変換して、処理ツリーの処理を行う。本発明では、このクエリーの処理ツリー内のいくつかのタスクが共通のリレーションに対して処理を要求する場合、共通のリレーションをアクセスするタスクをグループに集めて、マルチオペレーション・プロセッシングを使用してグループ処理を行うものである。
グループ内の各タスクのアクセスプランから処理コストを求めて、処理コストの小さいタスクから処理コストの大きいタスクへと順番に処理が終了するようにブロックをアクセスする。タスクの処理コストとは、タスクの処理を行うためにリレーション内のブロックをディスクからアクセスする回数であり、ブロックをアクセスする回数が少ないタスクほど処理コストが小さいことになる。
また、グループに集められた各タスクに対してアクセスプランを作成し、アクセスプランをもとに、各タスクから共通のブロックへのアクセスを見つけ、共通ブロックをアクセスし、共通ブロック上でグループ内のタスク処理を一度に行って、共通リレーションの同じブロックを何度もアクセスすることなしに、ブロックをアクセスすることが一度だけで済むようにしている。
処理コストの小さい処理ツリーから順番に処理が終了していくことになり、その結果、その処理ツリーに対応するクエリー(問い合わせ)に対してすばやく処理結果を出すことが可能になる。
【発明を実施するための最良の形態】
【００１３】
本発明では、１つのリレーションに対していくつかのタスク処理を行う場合に、処理速度の向上をはかる方法として、それらのタスク処理を一度に行うマルチオペレーション・プロセッシングを提案する。
その方法は、クエリーの処理ツリー内のいくつかのタスクが共通のリレーションに対して処理を要求する場合、共通のリレーションをアクセスするタスクをグループに集めて、マルチオペレーション・プロセッシングを使用してグループ処理を行うものである。
【００１４】
マルチオペレーション・プロセッシングでは、グループに集められた各タスクに対してアクセスプランを作成し、アクセスプランをもとに、各タスクから共通のブロックのアクセスを見つけ、共通ブロックをアクセスし、共通ブロック上でグループ内のタスク処理を一度に行って、共通リレーションの同じブロックを何度もアクセスすることなしに、一度のブロック・アクセスで済むようにする。また、マルチオペレーション・プロセッシングは、グループ内の各タスクのアクセスプランから処理コストを求めて、処理コストの小さいタスクから処理コストの大きいタスクへと順番に処理が終了するようにブロックをアクセスするものである。タスクの処理コストとは、タスクの処理を行うためにリレーション内のブロックをディスクからアクセスする回数であり、ブロックをアクセスする回数が少ないタスクほど処理コストが小さいことになる。
【００１５】
処理コストの小さいタスクから順番にタスク処理が終了していくと、クエリー・プロセッサは、マルチオペレーション・プロセッシングによるグループ内のすべてのタスク処理が終了するのを待たずして、すでに終了したタスク処理によって見出される処理ツリー内の次のタスク処理を見出していくことになり、効率的に次々とタスク処理を行うことができるようになる。
このようにして処理コストの小さいタスクから処理コストの大きいタスクへと順番にタスク処理を行うことによって、処理コストの小さい処理ツリー(処理ツリーの処理コストは、処理ツリー内のすべてのタスクの処理コストを合計したものである)から順番に処理が終了していくことになり、その結果、その処理ツリーに対応するクエリー(問い合わせ)に対してすばやく処理結果を出すことが可能になる。
【００１６】
以上のことを考慮したマルチオペレーション・プロセッシングの処理を行うために、ダイナミック・マルチオペレーション・プロセッシング(Dynamic Multi-Operation Processing)とスタティック・マルチオペレーション・プロセッシング(Static Multi-Operation Processing)とよぶ２つの処理方法を提案する。
【００１７】
＜ダイナミック・マルチオペレーション・プロセッシングの概要＞
ダイナミック・マルチオペレーション・プロセッシングは、グループに集められた各タスクに対して、それぞれアクセスプランを作成し、このアクセスプランにしたがって各タスクの処理コストを求め、求められた処理コストを参照して、処理コストの一番小さいタスクから処理コストの一番大きいタスクへと順番に、グループの各タスクの処理を行うものである。処理コストの一番小さいタスクから順番に処理を行うに当たって、処理コストの一番小さいタスクの処理を行うために必要な(ディスク内の)ブロックにアクセスし、ブロック内のデータをメインメモリに読み込むことにする。このブロックは当面のタスクだけではなく、グループ内の他のタスクの処理を行うためにも必要となるときは、このブロックは共通ブロックとなり、この共通ブロックで一度にいくつかのタスク(この共通ブロックを必要とするタスク)処理を行うことにする。次に、２番目に処理コストの小さいタスク処理を行う場合も同様に、そのタスクが必要とする(ディスク内の)ブロック(すでにアクセスしたブロックは除く)へアクセスし、メインメモリに読み込むことにする。このブロックが当面のタスクだけではなく、グループ内の他のタスク処理にも必要になるときには、このブロックは共通ブロックとなり、この共通ブロックで一度にタスク処理を行うことができる。このようにして、処理コストの小さいタスクから処理コストの大きいタスクへと順番に共通ブロックを見出し、この共通ブロックで一度にタスク処理を行っていく方法である。
【００１８】
＜スタティック・マルチオペレーション・プロセッシングの概要＞
スタティック・マルチオペレーション・プロセッシングは、グループ内の各タスクからアクセスプランを作成し、アクセスプランから各タスクの処理コストを求め、求めた処理コストを参照して、処理コストの一番小さいタスクから処理コストの一番大きいタスクへと順番にグループ内の各タスクを並べることにする。ここまでは、ダイナミック・マルチオペレーション・プロセッシングと同じ手順である。
次にデータベースのインデックスを使用して、グループ内の各タスクが、共通のリレーション内のファイルブロックからタスク処理を行うためにアクセスする必要のあるブロック(ブロックの番号とアドレス)を調べて、各タスクに対応するブロック集合に集める。そして、前に求めた処理コストの小さいタスクから処理コストの大きいタスクまでの順番にしたがって、各タスクに対応するブロック集合の和集合を求めていくことによって、アクセスするブロックの順位を決定する。その順位にしたがって共通のリレーション内のブロックをディスクからアクセスし、このブロックを共通ブロックとして、このブロック上で処理を行う必要のあるグループ内のタスク処理を一度に処理していくことになる。
アクセスした共通ブロック上で、グループ内の各タスクが処理を行う必要があるかどうかを調べるには、共通ブロックがグループ内の各タスクに対応するブロック集合に含まれているかどうかで判断することになる。
【００１９】
＜マルチオペレーション・プロセッシングのグループ処理の利点＞
上述のように、ダイナミック・マルチオペレーション・プロセッシング及びスタティック・マルチオペレーション・プロセッシングによるグループ処理を行うことによって、一つのグループにおいて、グループ内の一つのタスクの処理のためにディスク内のリレーションのブロックをアクセスすると、そのブロック(共通ブロック)を必要とするグループ内の他のタスクの処理にもそのブロックを使用することができ、一度アクセスしたブロックを何度もアクセスする必要がなくなり、一度だけのブロック・アクセスで済むようにすることができる。
【００２０】
＜データベース・マネージメント・システムの構成＞
ダイナミック・マルチオペレーション・プロセッシング及びスタティック・マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理を行うために、独自のデータベース・マネージメント・システムのアーキテクチャを提案している。提案するデータベース・マネージメント・システムのアーキテクチャは、クエリー・オプティマイザ（クエリーの最適化）、クエリー・プロセッサ、マルチオペレーション・プロセッサなどのソフトウェアから構成されている。
【００２１】
図１は、ここで提案するマルチオペレーション法を用いたデータベースのクエリー（問い合わせ）処理を行うために開発したデータベース・マネージメント・システム（ＤＢＭＳ）の構成を示す図である。開発したデータベース・マネージメント・システムのアーキテクチャ（ＤＢＭＳ）は、プロセッサ（ＣＰＵ）、メインメモリ、２次記憶装置（ディスク）を備えたコンピュータ・システムにおいて、クエリー・オプティマイザ５００、クエリー・プロセッサ５０１、マルチオペレーション・プロセッサ５０４などのソフトウェアから構成されている。クエリー・プロセッサ５０１は、全体の制御を行っている。
【００２２】
図１において、クエリー・オプティマイザ５００は、問い合わせのあったクエリーの最適化を行って関係代数で構成された処理ツリー５０２を作成する。クエリー・プロセッサ５０１はクエリーの一連の処理を行うために、クエリー・オプティマイザ５００とマルチオペレーション・プロセッサ５０４を制御し、クエリー・オプティマイザ５００によって作成された処理ツリー５０２からトポロジカル・ソートの順番で直接的に処理できるタスクを見出し、これらのタスクをそれぞれのタスクがアクセスするデータベースのリレーションをもとにグループ分けを行い、共通のリレーションに対して処理を行うタスクを集めたグループをグループ列(キュー)５０５に挿入する。マルチオペレーション・プロセッサ５０４は利用できるオペレーティングシステムのプロセスの数に応じてグループ列５０５からグループを取り出して、それぞれのプロセス５０６にマルチオペレーション法を用いたグループの処理を行わせる。なお、図１では、同時に生成されるプロセスを最大４個としている。
【００２３】
開発したデータベース・マネージメント・システムのアーキテクチャが従来のデータベース・マネージメント・システムのアーキテクチャと異なっている点は、本発明のダイナミック・マルチオペレーション・プロセッシング及びスタティック・マルチオペレーション・プロセッシングを用いたグループ処理を行うマルチオペレーション・プロセッサ５０４を新たに加えたこと、マルチオペレーション・プロセッサが効率よくグループ処理を行うことができるように新たにグループ列５０５を用いたこと、クエリー・プロセッサがマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理に対応できるようにしたことなどである。
【００２４】
上述のデータベース・マネージメント・システムの動作を具体例で示す。ユーザからクエリーＱ1,Ｑ2,…の問い合わせがあると、クエリー・オプティマイザ５００はこれらのクエリーの最適化を行って、それぞれ関係代数で構成された処理ツリー５０２  Ｐ1,Ｐ2，…に変換する。次に、クエリー・オプティマイザ５００とマルチオペレーション・プロセッサ５０４を制御し、クエリーの一連の処理を行うクエリー・プロセッサ５０１は、処理ツリーＰ1,Ｐ2,…からトポロジカル・ソートの順番で、他のタスクから依存がなく直接的に処理できるタスクを見つけ、これらのタスクを、それぞれのタスクｔij(iは処理ツリー番号、jはそれぞれの処理ツリー内の処理タスクの番号）がアクセスするデータベースのリレーションをもとに、グループＧ1,Ｇ2,…に分けていく。クエリー・プロセッサ５０１はタスクがグループに集められると、これらのグループＧ1,Ｇ2,…をグループ列（キュー）５０５に挿入する。
【００２５】
グループの処理を行うマルチオペレーション・プロセッサ５０４は、利用できるプロセスの数５０６に応じて、グループ列（キュー）５０５からグループＧ1,Ｇ2,…を取り出して、用意しているそれぞれのプロセスでマルチオペレーション法を用いたグループ処理を行わせる。ここではプロセス１がグループＧ1の処理を行い、プロセス２がグループＧ2の処理を行うことになる。そして、これらのプロセスにおけるグループ処理は、オペレーティングシステム（ＯＳ）のプロセスのスケジューリングによって同時に処理されることになる。その際、マルチオペレーション・プロセッサ５０４が複数のプロセッサ(ＣＰＵ)５０７を利用できるならば、それぞれのプロセスによるグループの処理は、別々のマイクロプロセッサによって並列に処理されることになる。
【００２６】
プロセス１は前述したようにグループＧ1内のタスク処理を処理コストの小さいタスクからの順番で行う。グループＧ1内のタスクの処理が終了すると、マルチオペレーション・プロセッサはグループＧ1内のタスクの処理が終了したことをクエリー・プロセッサ５０１に知らせる。クエリー・プロセッサ５０１はタスクの処理が終了したことによって、処理ツリーからトポロジカル・ソートの順番で新たに処理できるタスクを見つける。
グループＧ1からグループＧ2までのグループがグループ列５０５から取り出されると、クエリー・プロセッサ５０１は新たにグループＧ3を作成して、グループＧ3にタスクを加えて、グループＧ3をグループ列５０５に挿入する。すると、現在グループの処理を行っていないプロセス３がグループ列５０５からグループＧ3を取り出してグループＧ3の処理を始めることになる。
このようにして、プロセス１〜４がグループ列５０５からグループを取り出して、グループ処理を行っていくことによって、処理ツリーＰ1,Ｐ2,…内のタスク処理が次々と終了していくことになり、処理ツリーＰ1,Ｐ2,…内のすべてのタスク処理が終了すると、与えられたクエリーＱ1,Ｑ2,…の処理は完了したことになる。
【００２７】
グループ内のタスク処理は、処理コストの小さいタスクから順番にタスク処理が終了していくので、クエリー・プロセッサ５０１は、マルチオペレーション・プロセッシングによるグループ内のすべてのタスク処理が終了するのを待たずして、すでに終了したタスク処理によって見出される次のタスク処理を処理ツリー５０２から検索する。そのため同時に処理を行っているプロセス１〜４から次々とタスクが終了していき、それに応じて、クエリー・プロセッサ５０１は、効率的に次々と新たに処理することのできるタスクを見出し、それらのタスクのグループ分けを行っていくことになる。
【００２８】
マルチオペレーション・プロセッサ５０４は、グループ列５０５にグループが存在しているときは、グループ列５０５から次々とグループを取り出して処理を行っていくものであり、グループ列５０５内のグループが空になると、グループ列５０５にグループが挿入されるまで待ちの状態になる。そして、クエリー・プロセッサ５０１がグループ列に新たなグループを挿入すると、マルチオペレーション・プロセッサ５０４は、マルチオペレーション・プロセッシングの処理を再開することになる。
【００２９】
クエリー・プロセッサ５０１が現在クエリーの処理（図示しているＱ1からＱ5までのクエリー）を行っている最中に、ユーザからの新たな問い合わせのクエリーＱ6があった場合には、クエリー・プロセッサ５０１は、クエリー・オプティマイザ５００を用いて新しいクエリーＱ6に対する最適化を行って処理ツリーＰ6を作成し、処理ツリーＰ6からトポロジカル・ソートの順番で、処理できるタスクを見出し、それらのタスクと同様に共通のリレーションをアクセスするタスクを集めたグループがグループ列５０５に存在するかどうかを調べる。そのようなグループが既存のグループの中に存在するならば、そのグループにそれらのタスクを加えることになり、既存のグループに存在しない場合には、新たにグループを作成してそのグループにそれらのタスクを加えることにする。さらに、問い合わせのクエリー数が増えると、マルチオペレーション・プロセッサ５０４はグループの処理で忙しくなるので、グループ列５０５にいくつかのグループが待たされるようになり、その間にグループに数多くのタスクが集められることになり、マルチオペレーション・プロセッサ５０４はグループに集められた数多くのタスクの処理を一度に行うことができるようになる。
【００３０】
以上に述べたデータベース・マネージメント・システムのアーキテクチャにおいて、ダイナミック・マルチオペレーション・プロセッシング及びスタティック・マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理を行うことによって、ユーザから問い合わせられる数多くのクエリーを効率よく少ないディスクアクセスで処理していくことが可能になる。
【００３１】
＜マルチオペレーション・プロセッシングを用いたクエリー・プロセッサのフローチャート＞
図２は、マルチオペレーション・プロセッシングを適用し、クエリー・プロセッサ５０１を使用して、クエリーを処理する一連の流れを説明するためのフローチャートである。
図２のフローチャートにおいて、ＳＱＬ（構造化問い合わせ言語）などのリレーショナル・データベースの言語を使用して、ユーザからデータベース・サーバにクエリーの問い合わせがクエリー・プロセッサ５０１に入力される（Ｓ６０２)。
【００３２】
問い合わせ(例えばＳＱＬ)は、クエリー・オプティマイザ(クエリーの最適化)５００によって関係演算で構成された処理ツリーに変換される(Ｓ６０４)。
クエリー・プロセッサ５０１は、トポロジカル・ソートの順番で、直接的に処理することのできるタスクを見つける(Ｓ６０６)。そして、見つけた、直接的に処理することのできるタスクに対して、アクセスするリレーションと共通のリレーションをアクセスするタスクが集められたグループが、グループ列(キュー)５０５に存在するかどうかを調べる（Ｓ６０８）。共通のリレーションをアクセスするタスクが集められたグループがグループ列５０５に存在するならば(Ｓ６０８でＹＥＳ)、そのグループにタスクを加える(Ｓ６１２)。存在していない場合(Ｓ６０８でＮＯ)は、タスクのために新たなグループを作成し、そのグループにタスクを加えて、そのグループをグループ列に挿入する(Ｓ６１０)。
【００３３】
マルチオペレーション・プロセッサ５０４は、利用できるプロセスの数のグループをグループ列から取り出して、マルチオペレーション・プロセッシングを用いてグループの処理を行う(Ｓ６１４)。
グループ内のタスクの処理が終了すると、処理ツリー内のすべてのタスクが終了したかどうかを調べる(Ｓ６１６)。まだ、処理ツリー内にタスクが残っている場合(Ｓ６１６でＮＯ)は、繰り返して、次に処理できるタスクを処理ツリーから見つけて(Ｓ６０６)、アクセスするリレーションをもとにタスクをグループに分けていく(Ｓ６０８)。
処理ツリー内のすべてのタスクの処理が終了する(Ｓ６１６でＹＥＳ)と、その処理ツリーに対応したクエリーの処理が終了する。
【００３４】
マルチオペレーション・プロセッシングとして、ダイナミック・マルチオペレーション・プロセッシングとスタティック・マルチオペレーション・プロセッシングを本発明では提案している。以下で、まず、ダイナミック・マルチオペレーション・プロセッシングを詳しく説明する。
【００３５】
［１．ダイナミック・マルチオペレーション・プロセッシング］
ダイナミック・マルチオペレーション・プロセッシングは、次に示すような手順にもとづいて、共通のリレーションに対して処理を行うタスクの処理を一度に行う方法である。
最初に、１つの共通のリレーションＲに対して処理を行ういくつかのタスクt1,t2,t3,…,tnをグループに集める。グループにタスクを集めると、グループ内の各タスクに対してアクセスプランを作成し、アクセスプランをもとに各タスクの処理コストを計算し、求められた処理コストをもとにグループ内の処理コストの一番小さいタスクから処理コストの一番大きいタスクへと順番に並び替える。
【００３６】
次に、処理コストの一番小さいタスクから順番に処理を行い、当面のタスクの処理を行うためにアクセスしたブロック(共通ブロックと呼ぶことにする)において、グループ内の他のタスクもそれぞれの処理を行う必要がある場合は一度に処理を行う。アクセスしたブロックは、再びアクセスする必要がなくなるが、このブロックで処理が行われたことを示しておくために、アクセスしたブロックの番号ｂi，ブロックのアドレスとブロックがリンクしている次のブロックのアドレスの情報をｂi[ブロックのアドレス，次のブロックのアドレス]として記録しておく。カッコ内のブロックのアドレスとは、リレーションのデータファイルに、ブロックｂiが格納されている相対アドレスであり、データファイルの最初の相対アドレスをゼロとしたときに、そこから何バイト移動したところにブロックｂiが格納してあるかを表したものである。また、カッコ内の次のブロックのアドレスとは、ブロックｂiがブロックポインターを使用してリンクしている次のブロックｂi+1の相対アドレスであり、データファイルの最初の相対アドレスから何バイト移動したところにブロックｂi+1が格納してあるかを表したものである。
【００３７】
当面のタスクを処理するためにアクセスしたブロックを用いて、グループ内の他のタスクも処理を行うときには、それらのタスクは、すでにアクセスしたブロックから処理が始まることになるので、アクセスしたブロックから処理が始まるタスクは、そのブロックが最初のブロックであるということを記録しておくようにする。そのように記録することによって、その後にそのタスクの処理の続きを行うときに、インデックスを使用して最初にアクセスするブロックを検索する手間を省くことができる。また、アクセスしたブロックで処理が終わるタスクは、そのブロックが最後のブロックであるということを記録しておき、そのブロックをアクセスすることなくタスクの処理を終えることができるようになる。当面のタスクの処理が終わると、その次に処理コストの小さいタスクの処理を行い、そのとき、すでにアクセスしたブロックを除いた残りのブロックの中から処理を行っていくことにする。
【００３８】
［１．１  ダイナミック・マルチオペレーション・プロセッシングを用いた例］
［１．１．１  クエリーの問い合わせ］
以上の手順を、図面図３〜図６に示した具体的な例を用いて詳細に記述することにする。図３，図４は、以下の具体的な例で使用するリレーションの例を示している。
図３は、固定長レコード(fixed length record)を使用して作成したデータベースのリレーションの例であり、リレーションDEPARTMENTを示している。
リレーションDEPARTMENT（部門）には、２５件のレコードが5つのファイルブロック(以下ブロック)に格納してあり、それぞれのブロックに５つのレコードが存在する。各レコードには、DNUMBER（部門番号），DNAME（部門名），MGRSSN（部門長従業員番号），DPHONE（部門電話番号）のデータが格納されている。
各ブロックは、次のブロック対してブロックポインターを持っている。
主キーDNUMBERには、主インデックス（１００）が存在し、主インデックスは、各ブロックに対してインデックスのポインターを持っている。また属性DPHONEには２次インデックス（１０１）が存在し、２次インデックスは、各レコードに対してインデックスのポインターを持っている。
【００３９】
図４は、固定長レコードを使用して作成したデータベースのリレーションEMPLOYEE（従業員）である。EMPLOYEEには２０件のレコードが５つのブロックに格納してあり、それぞれのブロックに４つのレコードが存在する。各レコードには、SSN（従業員番号），FNAME（名），MINIT（ミドルネームの頭文字），LNAME（姓），BDATE（生年月日），ADDRESS（住所），SEX（性），SUPERSSN（上司の従業員番号），DNUM（部門番号）のデータが格納されている。
各ブロックは、次のブロックに対してブロックポインターを持っている。
主キーSSNには、主インデックス（２００）が存在し、主インデックスは、各ブロックに対してインデックスポインターを持っている。
【００４０】
以上をまとめると次のような表になる。
【表１】
2008165622.tif 000003
【００４１】
次に、図３,４のデータベースをもとにしてダイナミック・マルチオペレーション・プロセッシングを用いたクエリーを説明するために、下記に示すようなクエリーＱ1,Ｑ2, Ｑ3,Ｑ4,Ｑ5処理を取り上げることにする。図３，４のデータベースに対して次のような５つのクエリーＱ1,Ｑ2,Ｑ3,Ｑ4,Ｑ5の問い合わせがあったとする。
【００４２】
（Ｑ1）
SELECT        SSN, FNAME, LNAME, DNUMBER, MGRSSN
FROM          DEPARTMENT, EMPLOYEE
WHERE        SSN = 453432334 AND DNUMBER = DNUM;
【００４３】
（Ｑ2）         
SELECT         SSN, FNAME, LNAME, DNUMBER, DNAME 
FROM           DEPARTMENT, EMPLOYEE
WHERE        SSN > 531111113 AND DNUMBER = 8 AND DNUMBER = DNUM;
【００４４】
（Ｑ3）
SELECT         FNAME, LNAME, BDATE, DNUMBER, DNAME 
FROM          DEPARTMENT, EMPLOYEE
WHERE        DNUMBER≧7 AND DNUMBER≦18 AND BDATE > 'JAN-1-1971' AND
DNUMBER = DNUM;
【００４５】
（Ｑ4）
SELECT        *
FROM          DEPARTMENT, EMPLOYEE
WHERE        SSN = MGRSSN;  
【００４６】
（Ｑ5）    
SELECT        SSN, FNAME, LNAME, DNUMBER, DNAME, DPHONE
FROM          DEPARTMENT, EMPLOYEE
WHERE        DPHONE = 23-3721 AND SSN = 441111111 AND DNUMBER = DNUM;
【００４７】
［１．１．２  処理プランの作成］
クエリー・プロセッサ５０１は、問い合わせのあった各クエリーＱ1,Ｑ2,Ｑ3,Ｑ4,Ｑ5に対して、クエリーの最適化を行い、各クエリーを処理していくための最良な処理方法である下記の処理プランを作成していくことになる。
クエリー・プロセッサ５０１は、クエリーＱ1に対して処理プランＰ1を作成し、クエリーＱ2に対して処理プランＰ2を作成し、クエリーＱ3に対して処理プランＰ3を作成し、クエリーＱ4に対して処理プランＰ4を作成し、クエリーＱ5に対して処理プランＰ5を作成する。
【００４８】
作成した処理プランを処理ツリーで表すと、図５-１，５-２に示したようにＰ1〜Ｐ5となる。処理ツリーＰi内のタスクtij（ｉは処理ツリーの番号、ｊはそれぞれの処理ツリー内の処理タスクの番号を表わしている）は、以下に示すように、
（ｔij）：  処理結果  ←  関係代数  
として表し、処理結果は関係代数を処理した結果を表すものとする。なお、処理結果は、特定の記憶領域に格納されている。
【００４９】
処理結果名がTEMP_Tj_iの場合は、処理ツリーＰi内のタスクｔijの中間の処理結果を表し、処理結果がRESULT_Qiの場合は、処理ツリーＰi内のタスクｔijの最終の処理結果であることを表している。関係代数は、データベースのリレーションに対して、直接的に処理を行う演算であり、選択演算(σ)、射影演算(π) 、結合演算(|X|)などの演算である。
【００５０】
処理プランＰ１ 
（t11）:  TEMP_T1_1  ← πDNUMBER,MGRSSNDEPARTMENT
（t12）:  TEMP_T2_1  ← σSSN=453432334EMPLOYEE
（t13）:  TEMP_T3_1  ← πSSN,FNAME,LNAME,DNUMTEMP_T2_1
（t14）:  TEMP_T4_1  ← TEMP_T1_1 |X|DNUMBER = DNUM TEMP_T3_1
（t15）:  TEMP_T5_1  ← πSSN,FNAME,LNAME,DNUMBER,MGRSSNTEMP_T4_1
【００５１】
処理プランＰ２ 
（t21）:  TEMP_T1_2  ← σDNUMBER=8DEPARTMENT
（t22）:  TEMP_T2_2  ← πDNUMBER,DNAMETEMP_T1_2
（t23）:  TEMP_T3_2  ← σSSN>531111113EMPLOYEE
（t24）:  TEMP_T4_2  ← πSSN,FNAME,LNAME,DNUMTEMP_T3_2
（t25）:  TEMP_T5_2  ← TEMP_T2_2 |X|DNUMBER=DNUMTEMP_T4_2
（t26）:  RESULT_Q2  ← πSSN,FNAME,LNAME,DNUMBER,DNAME TEMP_T5_2
【００５２】
処理プランＰ３ 
（t31）:  TEMP_T1_3  ← σDNUMBER≧7 AND DNUMBER≦18 DEPARTMENT
（t32）:  TEMP_T2_3  ← π±,DNAME TEMP_T1_3
（t33）:  TEMP_T3_3  ← σBDATE>'JAN-1-1971'EMPLOYEE
（t34）:  TEMP_T4_3  ← πFNAME,LNAME,BDATE,DNUMTEMP_T3_3
（t35）:  TEMP_T5_3  ← TEMP_T2_3 |X|DNUMBER=DNUMTEMP_T4_3
（t36）:  RESULT_Q3  ← πFNAME,LNAME,BDATE,DNUMBER,DNAMETEMP_T5_3
【００５３】
処理プランＰ４ 
（t41）:  RESULT_Q4  ← EMPLOYEE |X|SSN=MGRSSN DEPARTMENT
【００５４】
処理プランＰ５ 
（t51）:  TEMP_T1_5  ← σDPHONE=23-3721 DEPARTMENT
（t52）:  TEMP_T2_5  ← πDNUMBER,DNAME,DPHONE TEMP_T1_5
（t53）:  TEMP_T3_5  ← σSSN=441111111 EMPLOYEE
（t54）:  TEMP_T4_5  ← πSSN,FNAME,LNAME,DNUM TEMP_T3_5
（t55）:  TEMP_T5_5  ← TEMP_T2_5 |X|DNUMBER=DNUM TEMP_T4_5
（t56）:  RESULT_Q3  ← πSSN,FNAME,LNAME,DNUMBER,DNAME,DPHONE TEMP_T5_5
【００５５】
［１．１．３  タスクのグループ化］
ダイナミック・マルチオペレーション・プロセッシングを用いたクエリー処理を行うにあたって、図５-１，図５-２に示した、処理プランＰ1,Ｐ2,Ｐ3,Ｐ4,Ｐ5にもとづいて作成された処理ツリーから、トポロジカル・ソートの順番で、他のタスクから依存がなく直接的に処理できるタスクt11,t12,t21,t23,t31,t33,t41,t51,t53を見つける。
【００５６】
次に、これらのタスクを各タスクがアクセスするデータベースのリレーションをもとにグループに分けていくと、次のようにグループ分けすることになる。なお、２つのリレーションをアクセスする結合演算のタスクなどの場合は、検索先のリレーションではなく検索元のリレーションをもとにしてグループ分けを行う。
DEPARTMENT:    グループ  Ｇ１＝｛t11,t21,t31,t41,t51｝
EMPLOYEE:    グループ  Ｇ２＝｛t12,t23,t33,t53｝
グループＧ1には、リレーションDEPARTMENTに対して処理を行うアクセスするタスクが集められ、グループＧ2には、リレーションEMPLOYEEに対して処理を行うタスクが集められてグループ分けが行われる。
【００５７】
［１．１．４  ダイナミック・マルチオペレーション・プロセッシングによるグループ内のタスク処理］
ダイナミック・マルチオペレーション・プロセッシングを使用して、グループＧ1に集められたタスクt11,t21,t31,t41,t51の処理を行っていく場合について記述する。前述したように、これらのタスク処理は次のように表わされる。
【００５８】
タスクt11：  TEMP_T1_1  ←  πDNUMBER, MGRSSN DEPARTMENT 
タスクt21：  TEMP_T1_2  ←  σDNUMBER=8 DEPARTMENT 
タスクt31：  TEMP_T1_3  ←  σDNUMBER≧7 AND DNUMBER≦18 DEPARTMENT
タスクt41：  RESULT_Q4  ←  EMPLOYEE |X|SSN=MGRSSN DEPARTMENT
タスクt51：  TEMP_T1_5  ←  σDPHONE=23-3721 DEPARTMENT
ここで、πは射影演算、σは選択演算、|X| は結合演算を表している。
これらのタスクは、図３のリレーションDEPARTMENTに対して処理を行うタスクであり、グループＧ1に集められたタスクである。
【００５９】
グループＧ１内の各タスクt11,t21,t31,t41,t51に対して、次のようなアクセスプラン plan(ti1)(i=1,2,…,5）を作成する。
plan(t11)：  DEPARTMENTをスキャンして射影処理を行う。
plan(t21)：  DEPARTMENTの主インデックスを使用して１つのレコードを検索する。
plan(t31)：  DEPARTMENTの主インデックスを使用して複数のレコードを検索する。
plan(t41)：  DEPARTMENTをスキャンしてEMPLOYEEの主インデックスを使用して結合処理を行う。
plan(t51)：  DEPARTMENTの２次インデックスを使用して１つのレコードを検索する。
【００６０】
各タスクに対してアクセスプランを作成すると、アクセスプランをもとに各タスクの処理コストを計算する。処理コストとは、タスクの処理を行うためにディスクをアクセスする回数である。ここではタスクの処理を行うためにディスクをアクセスする回数を減らすのが目的なので、メインメモリで計算する時間、処理結果をディスクに保存するコストは省略する。各タスクｔi1(i=1,2,…,5)の処理コストをcost(ｔi1) で表すと、上記のアクセスプランの処理コストは、次のように表すことができる。
cost(t11) = ｂD = 5 (ｂD:リレーションDEPARTMENTのブロック数）
cost(t21) = xD1 + 1 = 2 (xD1:リレーションDEPARTMENTの主インデックスのレベル）
cost(t31) = xD1 + [ｂD/2] = 4  
cost(t41) = ｂD + (|DEPARTMENT| * (xE+１)) = 5 + 25 * 2) = 55 
(xE:リレーションEMPLOYEEの主インデックスのレベル）
cost(t51) = xD2 + 1 = 3 
(xD2:リレーションDEPARTMENTの二次インデックスのレベル）
【００６１】
タスクt11の処理コストは、リレーションをスキャンして射影演算の処理を行うために、リレーションの中のすべてのブロックをアクセスするコストなので、ｂD=５である。
タスクｔ21の処理コストは、主インデックスを使用して１つのレコードを検索する処理コストである。xD1＋１は、インデックス法に用いられるＢ＋ツリーインデックスなど目的のデータを見つけるためにアクセスする複数のインデックスのレベルxD1と当面のブロックをアクセスする処理コストである。図３のリレーションDEPARTMENTの主インデックス１００のレベルは１であるので（xD1=１となり）、タスクt21の処理コストはxD1+１=２である。
【００６２】
タスクt31の処理コストは、主インデックス１００を使用して最初のレコードを検索し（xD1=１）、続けてファイル内の約半分のブロックをアクセスする処理コストであるのでxD1 + [ｂD/２] = ４である。
タスクt41の処理コストは、リレーションDEPARTMENTをスキャンする処理コストｂDとDEPARTMENT内の各レコードに対してリレーションEMPLOYEEの主インデックス２００を使用して結合できるレコードを検索するコスト|DEPARTMENT| * (xE + １) を合計した処理コストである。xEは、EMPLOYEEの主インデックスのレベルであり、図４のリレーションEMPLOYEEの主インデックス２００のレベルは１であるので、タスクｔ41の処理コストはｂD+ (|DEPARTMENT| * (xE + １)）= 5 + (25 * (1 + 1)) = 55である。
タスクt51の処理コストは、２次インデックス１０１を使用して１つのレコードを検索する処理コストである。これは、２次インデックスのレベルxD2とブロックをアクセスする処理コストであり、図３のリレーションDEPARTMENTの２次インデックス１０１のレベルxD2は２であるので、処理コストはxD2 + 1 = 3である。
【００６３】
以上のように処理コストを計算すると、処理コストをもとにグループ内のタスクを処理コストの小さい順番から並べ替えると次のようになる。
sort(t11,t21,t31,t41,t51）⇒（t21,t51,t31,t11,t41）
sort(…）は、処理コストの小さいタスクから並べ替えを表すものとする。
グループＧ１内のタスクを処理コストの小さい順番で並び替えると、処理コストの小さいタスクからt21,t51,t31,t11,t41の順番で処理を行っていくことになる。
【００６４】
図６は、ダイナミック・マルチオペレーション・プロセッシングを使用して、リレーションDEPARTMENTに対するタスクt11,t21,t31,t41,t51の処理を処理コストの小さいタスクからアクセスしていく状態（スキャン１からスキャン５にわたって）と処理結果をファイル（TEMP_T1_1からTEMP_T1_5まで）に書き込んだ結果を表わした図である。
【００６５】
一連のタスクの処理を行うプロセス４０１は、ディスク内のブロックを図６に示すようにブロックｂ2,ｂ4,ｂ3,ｂ1,ｂ5の順番でアクセスし、各ブロックにおいて、そのブロックで処理を行う必要のあるグループ内のタスクの処理を一度に行い、処理結果をファイルTEMP_T1_1，TEMP_T1_2，TEMP_T1_3，RESULT_Q4，TEMP_T1_5に書き込み、すべてのブロックでのタスク処理が終了すると、ダイナミック・マルチオペレーション・プロセッシングによる一連のタスク処理は終了したことになる。
【００６６】
［（ａ）タスクt21の処理］
最初に、処理コストの小さいタスクt21の処理を行うために、アクセスプランplan(t21)にもとづいて、リレーションDEPARTMENTの主インデックスを使用して”DNUMBER=8”の条件を満たすレコードを検索する。そのため、ディスク内のブロックｂ2をアクセスしてブロックｂ2内のデータをメインメモリに読み込む。ブロックｂ2内のデータをメインメモリに読み込むと、タスクt21の処理を行うと同時にグループ内の他のタスクt51，t31，t11，t41が共通ブロックとしてのブロックｂ2で処理を行う必要があるかどうかを調べる。
【００６７】
タスクt51は、選択演算条件”DPHONE=23-3721”を満たすレコードが必要である。リレーションDEPARTMENT内のレコードは、主属性DNUMBERの順番で格納してあり、属性DPHONEの順番で格納されていないため、ブロックｂ2内の最初と最後のレコードの値だけからでは、タスクt51の条件を満たすレコードが存在するかどうかわからないが、それでも、ブロックｂ2で検索処理を行うことにする(ただし、この場合、タスクt51はブロックｂ2では処理は行われない)。タスクt31は、”DNUMBER≧7 AND DNUMBER≦18”の条件を満たすレコードが必要である。リレーションDEPARTMENT内のレコードは、主属性DNUMBERの順番で格納されていて、ブロックｂ2には、DNUMBERの値が６から１０までのレコードが格納されていて、タスクt31の処理のために必要なレコードの一部が存在しているので、ブロックｂ2(共通ブロック)で検索処理を行うことになる。
【００６８】
タスクt11とt41は、リレーションDEPARTMENTをスキャンしてリレーション内のすべてのブロックをアクセスするタスクなので、ブロックｂ2で処理を行うことになる。このようにブロックｂ2(共通ブロック）において、タスクt21の他にタスクt51,t31,t41,t11の処理を行うことになり、これらのタスクの処理を行うには、ディスク内のブロックｂ２に対してではなく、メインメモリに読み込みこんだブロックｂ2内の各レコードに対してタスク t21,t51,t31,t11,t41の処理を一度に行い、その処理結果を図６に示した処理結果ファイルTEMP_T1_2, TEMP_T1_5, TEMP_T1_3, TEMP_T1_1, RESULT_Q4に書き込んでいくことになる。このブロックｂ2はタスクt21以外に、グループ内の他のタスクt51,t31,t11,t41にも使用されるので、ブロックｂ2を共通ブロック(Common Block)と呼ぶことにする。
【００６９】
ブロックｂ2上において、タスクt21の処理が終了し、他のタスクt51,t31,t11,t41の一部の処理も終了すると、グループ内の次のタスクの処理（処理コストの小さい順番でいうと、タスクt51）を始める前に、ブロックｂ2を再びアクセスすることがないように、次の表２に示した内容をメインメモリに記録しておくことにする。
【００７０】
【表２】
2008165622.tif 000004
【００７１】
ブロックｂ2[256,512]のアドレス256は、リレーションDEPARTMENTのデータファイルにブロックｂ2が格納してある相対アドレスで、データファイルの最初の相対アドレスから256バイト移動したところにブロックｂ2が格納してあることを表したものであり、アドレス512は、ブロックｂ2がブロックポインターを使用してリンクしているブロックｂ3の相対アドレスで、リレーションDEPARTMENTのデータファイルの最初の相対アドレスから512バイト移動したところにブロックｂ3が格納してあることを表したものである。
【００７２】
また、ブロックｂ2上でタスクt31の処理を行った際に、タスクt31の選択条件”DNUMBER≧7 AND DNUMBER≦18”を満たすレコードがブロックｂ2から始まっていて、ブロックｂ2内のDNUMBERの値が7から10までのレコードの処理はすでに終了しているが、DNUMBERの値が11以降のレコードは、引き続きブロックｂ3以降のブロックで処理する必要がある。ブロックｂ2がタスクt31の選択条件を満たす「最初のブロック」であるということを記録しておき、後でタスクt31の処理を引き続き行うときに、インデックスを用いて、最初のブロックｂ2を検索する必要をなくし、記録しておいた最初のブロックｂ2の情報ｂ2[256，512]をもとにして、アドレス512に格納してあるブロックｂ3からタスクt31の処理の続きを始めることができるようにしておく。
【００７３】
［（ｂ）タスクt51の処理］
次に、２番目に処理コストの小さいタスクt51の処理をアクセスプランplan(t51）にもとづいて行う。アクセスプランplan(t51）は、リレーションDEPARTMENTの２次インデックス１０１を使用して選択条件"DPHONE=23-3721"を満たすレコードを検索するためにディスク内のブロックｂ4をアクセスし、ブロックｂ4内のデータをメインメモリに読み込み、タスクt51の処理を行う。ブロックｂ4内のデータをメインメモリに読み込むと、すでにタスクの処理を終了したタスクt21を除くグループ内の他のタスクt31,t11,t41が、ブロックｂ4(共通ブロック)において処理を行う必要があるかどうかを調べる。タスクｔ31は、選択条件”DNUMBER≧7 AND DNUMBER≦18”を満たすレコードが必要であり、ブロックｂ4には、属性DNUMBERの値が16から20までのレコードが格納されていて、タスクt31の処理のために必要なレコードが存在するので、ブロックｂ4で処理を行うことになる。タスクt11とt41は、リレーションをスキャンしてリレーション内のすべてのブロックをアクセスするので、ブロックｂ4で処理を行うことになる。このようにブロックｂ4(共通ブロック)において、これらのタスクの処理を行うには、メインメモリに読み込みこんだブロックｂ4内の各レコードに対してタスクt51,t31,t11,t41の処理を行い、各タスクの処理結果を図６に示した処理結果ファイルTEMP_T1_5, TEMP_T1_3, TEMP_T1_1, RESULT_Q4に書き込んでいくことにする。
【００７４】
ブロックｂ4でのタスク処理が終了すると、メインメモリ上に再びブロックｂ4をアクセスする必要がなくなるが、ブロックｂ4で処理が行われたことを示しておくために、ブロックｂ4が格納してあるアドレスを含んだブロックｂ4の情報ｂ4[768,1024]をメインメモリに記録しておく。またブロックｂ4でグループ内の他のタスクの処理が終了した後に、タスクt31は、選択条件”DNUMBER≧7 AND DNUMBER≦18”を満たすレコードを検索するに当たって、ブロックｂ4には属性DNUMBERの値が16から20までのレコードが格納されていて、タスクt31はそれらのレコードの検索処理をブロックｂ4で終了しているので、ブロックｂ4はタスクt31の条件を満たす「最後のブロック」であるということを記録しておく。このように記録しておくと、後でタスクt31の処理の続きを行うとき、ブロックｂ3をアクセスした後、再度ディスク内のブロックｂ4をアクセスすることなしにタスクt31の処理を終了することができる。
【００７５】
以上のことをまとめると、次の表３に示すような結果となる。
【表３】
2008165622.tif 000005
上記の表３において、タスクt31のｂ2は「最初のブロック」であり、タスクt31のｂ4は、「最後のブロック」であることを示している。
【００７６】
[（ｃ）タスクt31の処理］
次に３番目に処理コストの小さいタスクt31の処理をアクセスプランplan(t31)にもとづいて行う。上記の表３の情報によると、タスクt31の処理はブロックｂ2から始まることになる。ブロックｂ2はすでにアクセスされていて、ブロックｂ2での処理は終わっているので、ブロックｂ2の情報b2[256,512］をもとに、アドレス512に格納してあるブロックｂ3をディスクからアクセスすればよく、ブロックｂ3内のデータをメインメモリに読み込む。ブロックｂ3内のデータをメインメモリに読み込むと、タスクt31の処理を行うと同時に、すでにタスクの処理が終了したタスクt21,t51を除くグループ内の他のタスクt11,t41がブロックｂ3(共通ブロック）で処理を行う必要があるかどうかを調べる。タスクt11とt41は、リレーションをスキャンしてリレーション内のすべてのブロックをアクセスするので、ブロックｂ3で処理を行う必要がある。
【００７７】
このように、ブロックｂ3において、これらのタスクの処理を行うには、メインメモリに読み込んだブロックｂ3内の各レコードに対してタスクt31,t11,t41の処理を行い、各タスクの処理結果を図６に示したファイルTEMP_T1_3, TEMP_T1_1, RESULT_Q4に書き込んでいくことにする。タスクt31の処理のために、ブロックｂ3をアクセスした後、次のブロックｂ4もアクセスする必要があるが、ブロックｂ4はタスクt51の処理のときにすでにアクセスされていて、上記の表３の結果によると、ブロックｂ4はタスクt31の処理を行う「最後のブロック」となっていて、ブロックｂ4での処理はすでに終了しているので、タスクt31の処理がブロックｂ3で終了すると、タスクt31の全体の処理は終了したことになる。ブロックｂ3での処理が終了すると、メインメモリ上で再びブロックｂ3をアクセスする必要がなくなるが、ブロックｂ3を使用したことを示すために、ブロックｂ3が格納してあるアドレスを含んだブロックｂ3の情報ｂ3[512,768]をメインメモリに記録しておく。
【００７８】
以上のことをまとめると、次の表４に示すような結果となる。
【表４】
2008165622.tif 000006
【００７９】
［（ｄ）タスクt11，t41の処理］
次に、４番目に処理コストの小さいタスクt11の処理をアクセスプランplan(t11)にもとづいて行う。タスクt11はリレーションDEPARTMENTをスキャンするために、ディスク内の最初のブロックｂ1をアクセスしてブロックｂ1内のデータをメインメモリに読み込む。ブロックｂ１内のデータをメインメモリに読み込むと、タスクt11のブロックｂ1内での処理を行うと同時に、すでにタスクの処理が終了したタスクt21,t51,t31を除くグループ内の他のタスクt41がブロックｂ1（共通ブロック）で処理を行う必要があるかを調べる。タスクt41は、リレーションをスキャンしてリレーション内のすべてのブロックをアクセスするので、ブロックｂ1で処理を行う必要がある。このようにブロックｂ1において、タスクt11,t41の処理を行うには、メインメモリに読み込んだブロックｂ1内の各レコードに対してタスクt11,t41の処理を行い、各タスクの処理結果を図６に示したファイルTEMP_T1_1，RESULT_Q4に書き込んでいくことにする。タスクt11,t41のブロックｂ1での処理が終了すると、メインメモリ上で再びブロックｂ1をアクセスする必要がなくなるが、ブロックｂ1を使用したことを示すために、ブロックｂ1が格納してあるアドレスを含んだブロックｂ1の情報ｂ1[0,256]をメインメモリに記録しておく。
【００８０】
以上のことをまとめると、次の表５に示すような結果となる。
【表５】
2008165622.tif 000007
【００８１】
タスクt11の処理のためにブロックb1をアクセスした後、続けてリレーションをスキャンするために次のブロックをアクセスするとき、ブロックｂ2,ｂ3,ｂ4はすでにアクセスされていて、これらのブロックでの処理は終了しているので、これらのブロックをディスクにアクセスする必要はなくなり、メインメモリ上のブロックｂ4の情報ｂ4[768,1024］をもとにしてアドレス1024に格納してあるブロックｂ5をアクセスして、ブロックb5内のデータをメインメモリに読み込む。ブロックｂ5内のデータをメインメモリに読み込むと、タスクt11のブロックｂ5内での処理を行うと同時に、すでにタスクの処理が終了したタスクt21,t51,t31を除くグループ内の他のタスクt41がブロックｂ5(共通ブロック）で処理を行う必要があるかどうかを調べる。タスクt41（処理コストの一番大きいタスク）は、リレーションをスキャンしてリレーション内のすべてのブロックをアクセスするので、ブロックｂ5で処理を行う必要がある。このようにブロックｂ5において、タスクt11,t41の処理を行うには、メインメモリに読み込んだブロックｂ5内の各レコードに対してタスクt11,t41の処理を行い、各タスクの処理結果を図６に示したファイルTEMP_T1_1,RESULT_Q4に書き込んでいく。ブロックｂ5での処理を終えるとリレーションDEPARTMENT内のすべてのブロックをアクセスしたことになるので、タスクt11の処理と同時にタスクt41の処理も終了し、グループ内すべてのタスクの処理が終了する。
【００８２】
以上のことをまとめると、次の表６に示すような結果となる。
【表６】
2008165622.tif 000008
【００８３】
このように共通ブロックを利用して、ディスク内のリレーションのブロックを何度もアクセスすることなしに、グループ内のタスクの処理を一度に行い、処理コストの小さいタスクから順番に次々と処理を行っていき、最後のタスク処理ですべてのタスク処理を終了させることができる。
グループＧ１内のタスクがt21,t51,t31,t11,t41の順番で終了すると、図５-１，図５-２の処理ツリーからトポロジカル・ソートの順番で新たにタスクt22,t52,t32の処理を直接的に行うことができるようになり、これらのタスクを各タスクがアクセスするデータベースのリレーションをもとにしてグループ分けすることになる。また、タスクt41の処理が終了したことによって、クエリーＱ4の処理結果RESULT_Q4を得ることができたので、クエリーＱ4を問い合わせたユーザに処理結果RESULT_Q4を返すことになる。グループＧ1の処理が終了すると次はグループＧ2の処理を行うことになる。グループＧ2の処理はグループＧ1の処理と同じようにして行っていくことになるのでグループＧ2の処理はここでは省略することにする。
【００８４】
［２．スタティック・マルチオペレーション・プロセッシング（Static Multi-Operation Processing）］
［２．１  スタティック・マルチオペレーション・プロセッシングの手順］
［（ａ）アクセスすべきブロック（共通ブロック）の順位の決定］
スタティックマルチオペレーション・プロセッシングは、共通のリレーションに対して処理を行う必要のあるグループ内の各タスクに対してアクセスプランを作成し、アクセスプランをもとに各タスクの処理コストを計算し、処理コストをもとにグループ内のタスクを処理コストの小さい順番で並べ替える。ここまでは、ダイナミック・マルチオペレーション・プロセッシングと同じ手順である。
【００８５】
次に、データベースのインデックスを使用して、グループ内の各タスクt1,t２,…,tｎが、共通のリレーションのファイル内のすべてのブロックｂ1,ｂ2,…,ｂmのうちアクセスする必要のあるブロックを調べて、アクセスする必要のあるブロック（格納位置）を集めた集合を見出し、それらの集合をそれぞれブロック集合Ｂ1,Ｂ2,…,Ｂnとする。言い換えると、タスクｔi(i=1,2,…,n)に対して、それに対応するブロック集合として、Ｂi=｛ブロックｂ1,ｂ2,…,ｂmの中でタスクtiがアクセスする必要があるブロックの集合｝(i=1,2,…,n)となる集合を見出すことになる。
ブロック集合Ｂ1,Ｂ2,…,Ｂnを見出すと、前に求めた処理コストの小さいタスクから処理コストの大きいタスクまでの順番にしたがって、それらのタスクに対応する集合として、このように見出された集合Ｂ1,Ｂ2,…,Ｂnを並べ変えることにする。
【００８６】
最初に、処理コストの一番小さいタスクに対応する集合と処理コストの２番目に小さいタスクに対応する集合との和集合（Union）を求め、その和集合と処理コストの３番目に小さいタスクに対応する集合との和集合を求めるということを次々と行い、最後に処理コストの一番大きいタスクに対応する集合との和集合を求めることにする。この際、和集合を求めるに当たっては、新たに加わる集合は和集合の中で最後の項に加えていくことにする。このように和集合を求めることは、グループ内のタスク処理を行うに当たって、ディスク内のリレーションのブロックを何度もアクセスすることなしに、一度だけアクセスすれば済むようにするためである。最後に得られた和集合の結果から、処理コストの一番小さいタスクから処理コストの一番大きいタスクまで順番にタスク処理を行うに当たって、最初にディスク内のどのブロックからアクセスが始まって、最後にどのブロックでアクセスが終わるかというアクセスの順番を明確にするブロックの集合を見出すことができる。これらのブロックを「共通のブロック」と呼ぶことにすると、この共通ブロックを用いて、グループ内のタスクを一度に処理することができる。
【００８７】
［（ｂ）各タスクの共通ブロックの処理］
最初にディスク内のどのブロックからアクセスし、最後にどのブロックでアクセスが終わるかというブロックへのアクセスの順番が決定したときに、最初にアクセスするブロックｂj（１≦ｊ≦ｍ）において、グループ内の各タスクt1,t2,…,tnが処理を行う必要があるかどうかを調べるためには、次のようにして行う。
【００８８】
まず、ブロックｂjを集合{ｂj}として表わし、この{ｂj}とブロック集合Ｂ1,Ｂ2,…, Ｂnとの間で積集合（Intersection）を求める。その積集合が{ｂj}となったブロック集合に対応するタスクはすべて、ブロックｂｊで処理を行うことが必要となり、ブロックｂjは共通ブロックとなり、この共通ブロックｂjで各タスクの処理を行うことになる。その積集合が空集合({})となったブロック集合に対応するタスクはブロックｂjでは処理が行われないことになる。共通ブロックｂｊにおいて各タスクの処理が終了すると、このブロックｂｊを再びアクセスすることがなくなるので、積集合が{ｂj}となったブロック集合と集合{ｂj}との差集合を求めることにする。この差集合が空集合({})となったブロック集合に対応するタスクは終了したことになり、差集合が空集合でないブロック集合に対応するタスクはまだ処理が完全に終了していないことになる。ここで、差集合によって得られたブロック集合をＢi(1)(i=1,2,…,nの中から空集合になったブロック集合は取り除く）とする。
【００８９】
次に、アクセスするブロックｂk(１≦ｋ≦ｍ)で処理する場合に対しても、ブロックｂｊと同様に、各タスク（終了したタスクは除く）がブロックｂkで処理を行う必要があるかどうかを調べるために、ブロックｂkを集合{ｂk}として表わし、この{ｂk}とブロック集合の間で積集合を求める。その積集合が{ｂk}となったブロック集合に対応するタスクはすべてブロックｂkで処理を行うことが必要となり、ブロックｂkは共通ブロックとなり、この共通ブロックｂkで各タスクの処理を行うことになる。共通ブロックｂkにおいて各タスクの処理が終了すると、ブロックｂkを再びアクセスすることがなくなるので、積集合が{ｂk}となったブロック集合Ｂi(1)(ブロックｂjで処理終了後に差集合によって得られたブロック集合)と集合{ｂk}との差集合を求める。この差集合が空集合({})となったブロック集合に対応するタスクは終了したことになり、差集合が空集合ではないブロック集合に対応するタスクは、まだ処理が完全に終了していないことになる。ここで、差集合によって得られたブロック集合をＢi(2)(i=1,2,…,nの中から空集合となったブロック集合は除く)とする。
【００９０】
以上のことを繰り返して、アクセスすべきブロックの順番にしたがって、それぞれのブロックに対して、同様に、積集合を求め、タスク処理を行い、差集合を求めていく。最後にアクセスすべきブロックに対して同様のことを行ったときに、各タスクに対応するブロック集合がすべて空集合({})となると、すべてのタスクの処理は終了したことになる。
【００９１】
［２．２  スタティック・マルチオペレーション・プロセッシングを用いた例］
以上のスタティック・マルチオペレーション・プロセッシングの手順を具体的な例を用いて記述するために、ダイナミック・マルチオペレーション・プロセッシングで使用した図３のリレーションDEPARTMENTと図４のリレーションEMPLOYEEに対するタスクの処理としてグループＧ１に集められたタスクt11,t21,t31,t41,t51の処理を取り上げて説明することにする。
【００９２】
[（ａ）各タスクのアクセスプランの作成］
ダイナミック・マルチオペレーション・プロセッシングと同じように、グループＧ１内の各タスクt11,t21,t31,t41,t51に対してアクセスプランを作成する。
【００９３】
［（ｂ）各タスクの処理コスト］
各タスクのアクセスプランを作成した後、アクセスプランをもとに各タスクの処理コストを計算する。さらに、グループ内のタスクを処理コストの小さい順番で並べ替える。ここまでは、ダイナミック・マルチオペレーション・プロセッシングと同じ手順である。処理コストの小さいタスクから処理コストの大きいタスクへと順番に並べ替えると、ダイナミック・マルチオペレーション・プロセッシングの例で示したように(t21,t51,t31,t11, t41）となる。
【００９４】
［（ｃ）各タスクに対応するブロック集合］
図３の主インデックス１００、及び２次インデックス１０１を用いて、各タスクt11，t21，t31，t41，t51の処理を行うためにアクセスする必要のあるすべてのブロックを事前に調べて、それぞれ集合Ｂ11，Ｂ21，Ｂ31，Ｂ41，Ｂ51に集めると、次のようになり、各タスクに対応するブロック集合が得られる。
タスクt11 に対して、Ｂ11＝{ｂ1,ｂ2,ｂ3,ｂ4,ｂ5｝    
タスクt21 に対して、Ｂ21＝{ｂ2｝            
タスクt31 に対して、Ｂ31＝{ｂ2,ｂ3,ｂ4｝ 
タスクt41 に対して、Ｂ41＝{ｂ1,ｂ2,ｂ3,ｂ4,ｂ5｝
タスクt51 に対して、Ｂ51＝{ｂ4｝            
このように、各タスクt11,t21,t31,t41,t51に対応するブロック集合Ｂ11,Ｂ21,Ｂ31,Ｂ41,Ｂ51を見出すことができるのは、以下に示すような理由にもとづくからである。
【００９５】
タスクt11は、射影演算の処理を行うために、リレーションDEPARTMENT内の最初のブロックｂ1から最後のブロックｂ5までのブロックをアクセスすることが必要となるので、タスクt11の処理を行うためにアクセスする必要のあるブロックの集合は{ｂ1,ｂ2,ｂ3,ｂ4, ｂ5｝となる。
【００９６】
タスクｔ21は、選択条件”DNUMBER=8”を満たすレコードが必要である。リレーションDEPARTMENTの主インデックスを使用すると、属性DNUMBERの値が８であるレコードは、ブロックの相対アドレスが256であるブロックｂ2に格納してあることがわかる。そして、ブロックｂ2だけをアクセスすればよいことになると、タスクt21の処理を行うためにアクセスする必要のあるブロックの集合は{ｂ2}となる。
【００９７】
タスクt31は、選択条件”DNUMBER≧7 AND DNUMBER≦18”を満たすレコードが必要である。リレーションDEPARTMENTの主インデックス１００を使用すると、属性DNUMBERの値が７であるレコードはブロックの相対アドレスが256であるブロックｂ2に格納してあり、次にDNUMBERの値が１８であるレコードはブロックの相対アドレスが768であるブロックｂ4に格納してあり、タスクt31の処理を行うためにアクセスする必要のあるブロックは、ブロックｂ2からブロックｂ4までのブロックとなり、ブロックの集合は{ｂ2,ｂ3,ｂ4}となる。
タスクt41は、結合演算の処理を行うために、リレーションDEPARTMENTの最初のブロックｂ1から最後のブロックｂ5までのブロックをアクセスすることが必要となるので、タスクt41の処理を行うためにアクセスする必要のあるブロックの集合は{ｂ1,ｂ2,ｂ3,ｂ4，ｂ5}となる。
【００９８】
タスクｔ51は、選択条件”DPHONE=23-3721”を満たすレコードが必要である。リレーションDEPARTMENTの２次インデックス１０１を使用すると、属性DPHONEの値が23-3721であるレコードはブロックの相対アドレスが768であるブロックｂ4に格納してあることがわかり、タスクt51の処理を行うためにアクセスする必要のあるブロックの集合は{ｂ4}となる。
【００９９】
[（ｄ）アクセスすべきブロック（共通ブロック）の順位の決定］
以上のように、各タスクに対応するブロック集合を見出した後に、処理コストの小さいタスクから処理コストの大きいタスクへと順番に（ダイナミック・マルチオペレーション・プロセッシングの例で求められた順番に）、すなわちタスクt21,t51,t31,t11,t41の順番に各タスクに対応するブロック集合の和集合を求めていくことにする。
ＴＢ０= {}(空集合)を用意し、これとタスクに対応するブロック集合との和集合を求めていく。
【０１００】
まず、ＴＢ０とタスクt21に対応するブロック集合Ｂ21との和集合ＴＢ21を求める。次に、このＴＢ21とタスクt51に対応するブロック集合Ｂ51の和集合ＴＢ51を求める。さらに、このＴＢ51とタスクt31に対応するブロック集合Ｂ31との和集合ＴＢ31を求める。同様にして、タスクt11，t41に対応するブロック集合Ｂ11，Ｂ41に対しても和集合ＴＢ11，ＴＢ41を求めると次のようになる。この場合、和集合Ｕを求めるに当たっては、新たに加わる集合のブロックは和集合の中で最後に加えていくものとする。
【０１０１】
ＴＢ0  = {} (空集合)                 
タスクt21に対応するブロック集合Ｂ21との和集合：
ＴＢ21= ＴＢ0ＵＢ21  = {ｂ2} 
タスクt51に対応するブロック集合Ｂ51との和集合：
ＴＢ51 = ＴＢ21ＵＢ51 = {ｂ2,ｂ4}
タスクt31に対応するブロック集合Ｂ31との和集合：
ＴＢ31 = ＴＢ51 Ｕ Ｂ31 = {ｂ2,ｂ4,ｂ3｝
タスクt11に対応するブロック集合Ｂ11との和集合：
ＴＢ11 = ＴＢ31 Ｕ Ｂ11 =｛ｂ2,ｂ4,ｂ3,ｂ1,ｂ5｝
タスクt41に対応するブロック集合Ｂ41との和集合：
ＴＢ41 =  ＴＢ11 Ｕ Ｂ41 =｛ｂ2,ｂ4,ｂ3,ｂ1,ｂ5｝
【０１０２】
以上のように、処理コストの小さいタスクに対応するブロック集合から処理コストの大きいタスクに対応するブロック集合へと順番に和集合を求めていくと、最後のタスクt41（処理コストの一番大きいタスク）に対応するブロック集合との和集合ＴＢ41の結果から、ディスクのブロックｂ2からアクセスを開始し、ブロックｂ5でアクセスを終了すればよいことになり、ディスクにおけるリレーションDEPARTMENT内のブロックへのアクセスの順番を（ｂ2,ｂ4,ｂ3,ｂ1,ｂ5）のように決定することができる。このような方法で和集合を求めることは、処理コストの小さいタスクから順番に処理を行うに当たって、ディスク内のブロックをどのような順番でアクセスすればよいか、その順番を決定するためである。
このようにして得られたブロックｂ2,ｂ4,ｂ3,ｂ1,ｂ5は、タスク t21,t51,t31,t11,t41を順番に処理していくときに共用され得るので、これらのブロックを共通ブロックと呼ぶことにする。
【０１０３】
前述したブロック集合Ｂ11,Ｂ21,Ｂ31,Ｂ41,Ｂ51の中に含まれているブロックを見ると、ブロックｂ2は、タスクｔ21，ｔ31，ｔ11，ｔ41を処理するために使用され、ブロック ｂ4はタスクt51,t31,t11,t41を処理するために使用され、ブロックｂ3はタスクt31,t11,t41を処理するために使用され、ブロックb１はタスクt11，t41を処理するために使用され、ブロック ｂ5はタスクt11,t41を処理するために使用されていることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。
【０１０４】
以上のことをまとめると次のような表になる。
【表７】
2008165622.tif 000009
【０１０５】
[（ｅ）共通ブロックでのタスクの処理］
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、それぞれのタスクｔi1(ｉ=1,2,…,5)に対して作成されたブロック集合Ｂi1(i=1,2,…,5)の情報にもとづいて、次に記述するような手順を用いればよい。
【０１０６】
［（ｅ−１）ブロックｂ2の読み込み］
最初にブロックの相対アドレスが256であるブロックｂ2をディスクにアクセスして、ブロックｂ2内のデータをメインメモリに読み込み、グループ内のタスクt21,t51,t31,t11, t41がブロックｂ2で処理を行う必要があるかどうかを調べるため、ブロックｂ2を集合｛ｂ2｝として表し、この｛ｂ2｝とブロックの集合Ｂ21,Ｂ51,Ｂ31,Ｂ11,Ｂ41との間でそれぞれ積集合（Intersection）∩を求めると次のようになる。
【０１０７】
タスクｔ2１に対して：Ｂ2１∩｛ｂ2｝＝｛ｂ2｝
タスクｔ5１に対して：Ｂ5１∩｛ｂ2｝＝ {}
タスクｔ3１に対して：Ｂ3１∩｛ｂ2｝＝｛ｂ2｝
タスクｔ1１に対して：Ｂ1１∩｛ｂ2｝＝｛ｂ2｝
タスクｔ4１に対して：Ｂ4１∩｛ｂ2｝＝｛ｂ2｝
【０１０８】
タスクｔ5１を除くタスクｔ2１,ｔ3１,ｔ1１,ｔ4１に対して積集合が{ｂ2｝となり、タスクｔ21,ｔ31,ｔ11,ｔ4１がメインメモリに読み込んだブロックｂ2で処理を行う必要があることが明らかになり、ブロックｂ2は共通ブロックとなり、共通ブロックｂ2で各タスクの処理を行うことになる。共通ブロックであるブロックｂ2でのタスクの処理が終了すると、ブロックｂ2を再びアクセスする必要がなくなるので、ブロックｂ2を取り除くために、集合Ｂ21,Ｂ31,Ｂ11,Ｂ41と集合｛ｂ2｝との差集合（Difference）を求める。得られた差集合をＢ21(1),Ｂ31(1),Ｂ11(1),Ｂ41(1)とすると、次のようになる。
【０１０９】
タスクt2１に対して：  Ｂ2１-｛ｂ2｝= {} = Ｂ21(1)
タスクt3１に対して：  Ｂ3１-｛ｂ2｝=｛ｂ3，ｂ4｝= Ｂ31(1)
タスクt1１に対して：  Ｂ1１-｛ｂ2｝=｛ｂ1，ｂ3，ｂ4，ｂ5｝= Ｂ11(1)
タスクt4１に対して：  Ｂ4１-｛ｂ2｝=｛ｂ1，ｂ3，ｂ4，ｂ5｝= Ｂ41(1) 
この結果、集合Ｂ21(1)が空集合({})になり、タスクｔ21の処理が終了したことがわかる。
【０１１０】
[（ｅ−２）ブロックｂ4の読み込み]
次に、ブロックの相対アドレスが768であるブロックｂ4をディスクにアクセスして、ブロックｂ４内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21を除くグループ内のタスクｔ51,ｔ31,ｔ11,ｔ41がブロックｂ4で処理を行う必要があるかどうかを調べるために、ブロックｂ4を集合｛ｂ4｝として表し、{ｂ4}とブロックの集合Ｂ51，Ｂ31(1)，Ｂ11(1)，Ｂ41(1)との間でそれぞれ積集合を求めると次のようになる。
タスクt51に対して：  Ｂ51 ∩｛ｂ4｝=｛ｂ4｝
タスクt31に対して：  Ｂ31(1) ∩｛ｂ4｝=｛ｂ4｝
タスクt11に対して：  Ｂ11(1) ∩｛ｂ4｝=｛ｂ4｝
タスクt41に対して：  Ｂ41(1) ∩｛ｂ4｝=｛ｂ4｝
【０１１１】
タスクt51，t31，t11，t41対して積集合が｛ｂ4｝となり、タスクt51，t31，t11，t41が、メインメモリに読み込んだブロックｂ4で処理を行うことが必要である。ブロックｂ４は共通ブロックであり、共通ブロックｂ4で各タスクの処理を行うことになる。共通ブロックであるブロックｂ4でのタスクの処理が終了すると、ブロックｂ4を再びアクセスする必要がなくなるので、ブロックｂ4を取り除くために、集合Ｂ51,Ｂ31(1),Ｂ11(1),Ｂ41(1)と集合｛ｂ4｝との差集合を求める。得られた差集合をＢ51(1),Ｂ31(2),Ｂ11(2),Ｂ41(2)とすると、次のようになる。
【０１１２】
タスクt51に対して：  Ｂ51 -｛ｂ4｝= {} = Ｂ51(1)
タスクt31に対して：  Ｂ31(1) -｛ｂ4｝=｛ｂ3｝=Ｂ31(2)
タスクt11に対して：  Ｂ11(1) -｛ｂ4｝=｛ｂ1,ｂ3,ｂ5｝= Ｂ11(2) 
タスクt41に対して：  Ｂ41(1) -｛ｂ4｝=｛ｂ1,ｂ3,ｂ5｝= Ｂ41(2)
この結果、集合Ｂ51(1)が空集合({})になり、タスクｔ51の処理が終了したことがわかる。
【０１１３】
[（ｅ−３）ブロックｂ3の読み込み］
次に、ブロックの相対アドレスが512であるブロックｂ3をディスクにアクセスして、ブロックｂ3内のデータをメインメモリに読み込み、すでに処理が済んだタスクt21,t51を除くグループ内のタスクt31,t11,t41がブロックｂ3で処理を行う必要があるかどうかを調べるために、ブロックｂ3を集合{ｂ3}として表わし、{ｂ3}とブロックの集合Ｂ31(2),    Ｂ11(2),Ｂ41(2)との間でそれぞれ積集合を求めると次のようになる。
タスクt31に対して：  Ｂ31(2)  ∩｛ｂ3｝=｛ｂ3｝
タスクt11に対して：  Ｂ11(2)  ∩｛ｂ3｝=｛ｂ3｝
タスクt41に対して：  Ｂ41(2)  ∩｛ｂ3｝=｛ｂ3｝
【０１１４】
タスクt31,t11,t41に対して積集合が｛ｂ3｝となり、タスクt31,t11,t41がメインメモリに読み込んだブロックｂ3で処理を行うことが必要となり、ブロックｂ3は共通ブロックとなり、共通ブロックｂ3でタスクt31,t11,t41の処理を行うことになる。共通ブロックであるブロックｂ3のタスクの処理が終了すると、ブロックｂ３を再びアクセスする必要がなくなるので、ブロックｂ3を取り除くために、ブロックの集合Ｂ31(2),Ｂ11(2),Ｂ41(2)と集合  {ｂ3｝との差集合を求める。得られた差集合をＢ31(3),Ｂ11(3),Ｂ41(3)とすると次のようになる。
【０１１５】
タスクt31に対して：  Ｂ31(2) -｛ｂ3｝= {} = Ｂ31(3) 
タスクt11に対して：  Ｂ11(2) -｛ｂ3｝=｛ｂ1,ｂ5｝= Ｂ11(3) 
タスクt41に対して：  Ｂ41(2) -｛ｂ3｝=｛ｂ1,ｂ5｝= Ｂ41(3) 
この結果、集合Ｂ31(3)が空集合({})になり、タスクt31の処理が終了したことがわかる。
【０１１６】
[（ｅ−４）ブロックｂ１の読み込み］
次に、ブロックの相対アドレスが０であるブロックｂ1をディスクからアクセスして、ブロックｂ1内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21,t51,t31を除くグループ内のタスクt11,t41がブロックｂ1で処理を行う必要があるかどうかを調べるため、ブロックｂ1を集合｛ｂ1｝として表し、{ｂ1}と集合Ｂ11(3),Ｂ41(3)との積集合を求めると次のようになる。
タスクt１１に対して：  Ｂ11(3)  ∩｛ｂ1｝=｛ｂ1｝
タスクt４１に対して：  Ｂ41(3)  ∩｛ｂ1｝=｛ｂ1｝
【０１１７】
タスクt11,t41に対して積集合の値が{ｂ1}となり、タスクt11,t41がメインメモリに読み込んだブロックｂ1で処理を行うことが必要である。ブロックｂ1は共通ブロックであり、共通ブロックｂ1でタスクt11,t41の処理を行うことになる。共通ブロックであるブロックｂ1でのタスクの処理が終了すると、ブロックｂ1を再びアクセスする必要がなくなるので、ブロックｂ1を取り除くために、ブロックの集合Ｂ11(3),Ｂ41(3)と集合{ｂ1}との差集合(difference)を求める。得られた差集合をＢ11(4),Ｂ41(4)とすると、次のようになる。
タスクt11に対して：Ｂ11(3) -｛ｂ1｝=｛ｂ5｝=Ｂ11(4)
タスクt41に対して：Ｂ41(3) -｛ｂ1｝=｛ｂ5｝=Ｂ41(4)
【０１１８】
[（ｅ−５）ブロックｂ5の読み込み］
最後に、ブロックの相対アドレスが1024であるブロックｂ5をディスクからアクセスして、ブロックｂ５内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21，t51，t31を除くグループ内のタスクt11,t41がブロックｂ5で処理を行う必要があるかどうかを調べるために、ブロックｂ5を集合{ｂ5}として表わし、{ｂ5}とブロックの集合Ｂ11(4)，Ｂ41(4)との間で積集合を求めると次のようになる。
タスクt11に対して：  Ｂ11(4) ∩｛ｂ5｝=｛ｂ5｝
タスクt41に対して：  Ｂ41(4) ∩｛ｂ5｝=｛ｂ5｝
タスクt11，t41に対して積集合が{ｂ5}となり、タスクt11，t41がメインメモリに読み込んだブロックｂ5で処理を行うことが必要であり、ブロックｂ5は共通ブロックである。共通ブロックであるブロックｂ5上でのタスクの処理が終了すると、ブロックｂ5を再びアクセスする必要がなくなるので、ブロックｂ5を取り除くために、ブロックの集合Ｂ11(4),   Ｂ41(4)と集合{ｂ5}との差集合を求める。得られた差集合の値をＢ11(5),Ｂ41(5)とすると、次のようになる。
タスクt11に対して：  Ｂ11(4)- ｛ｂ5｝= {} = Ｂ11(5) 
タスクt41に対して：  Ｂ41(4)- ｛ｂ5｝= {} = Ｂ41(5) 
この結果、集合Ｂ11(5)，Ｂ41(5)が空集合({})になり、タスクt11,t41の処理が終了したことがわかり、これによってグループ内のすべてのタスクの処理が終了したことになる。
【０１１９】
以上のように、リレーション内のブロックへのアクセスの順番を決定し、その順番にしたがって、アクセスしたブロックを共通ブロックとして利用して、同じブロックを何度もディスクにアクセスすることなしに、一度だけのブロック・アクセスによって処理コストの小さいタスクから順番に処理を行っていく方法がスタティック・マルチオペレーション・プロセッシングである。スタティック・マルチオペレーション・プロセッシングは、最初にインデックスを用いて、グループに集められたタスク処理を行うためにアクセスする必要のあるブロックを調べるため、ダイナミック・マルチオペレーション・プロセッシングよりもインデックスファイルをアクセスする回数が、わずかほど多くなるが、簡潔にかつ論理的に処理を行うことができる。
【０１２０】
スタティック・マルチオペレーション・プロセッシングを用いたタスク処理は、図６のダイナミック・マルチオペレーション・プロセッシングと同じように、リレーションDEPARTMENT内のブロックをｂ2,ｂ4,ｂ3,ｂ1,ｂ5の順番でディスクからアクセスし、各ブロックにおいて、そのブロックで処理を行う必要のあるグループ内のタスクの処理を一度に行い、処理結果をファイルTEMP_T1_1, TEMP_T1_2, TEMP_T1_3, RESULT_Q4, TEMP_T1_5に書き込んでいくことになる。
【０１２１】
＜ＭＯＰ-ＤＢの実験結果＞
ダイナミック・マルチオペレーション・プロセッシングを適用したクエリー・プロセッサとスタティック・マルチオペレーション・プロセッシングを適用したクエリー・プロセッサが、従来のクエリー・プロセッサ（ＭｙＳＱＬ  Ｖｅｒ．３）よりも数多くのクエリーを早く処理することを証明するために、ダイナミック・マルチオペレーション・プロセッシングとスタティック・マルチオペレーション・プロセッシングの処理を行うことが可能な本発明のデータベース・マネージメント・システムＭＯＰ-ＤＢ(Multi-Operation Processing Database)を開発した。
【０１２２】
ＭＯＰ-ＤＢは、ＭｙＳＱＬなど市場で幅広く使われているデータベース・マネージメント・システムよりも数多くのクエリーを高速に処理することを目的とし、ＳＱＬのインタープリタ、クエリーの最適化、トランザクションの同時処理、データを格納するストレージシステムなどデータベース・マネージメント・システム（ＤＢＭＳ）に必要な十分な機能を備えたソフトウェアである。ＭＯＰ-ＤＢは、ダイナミック・マルチオペレーション・プロセッシングを適用したクエリー・プロセッシング及びスタティック・マルチオペレーション・プロセッシングを適用したクエリー・プロセッシングの処理ができると同時に、これらのクエリー・プロセッサを自由に選択して処理を行うことが可能である。
【０１２３】
開発したＭＯＰ-ＤＢを使用して、ダイナミック・マルチオペレーション・プロセッシングによるクエリー・プロセッシング、スタティック・マルチオペレーション・プロセッシングによるクエリー・プロセッシングを用いたクエリーの処理を行い、それぞれのクエリー・プロセッシングの処理速度を調べた。さらに市場で幅広く使用されているＭｙＳＱＬバージョン３と比較するために、共通のクエリーの処理を行ってＭＯＰ-ＤＢとＭｙＳＱＬの処理速度を調べた。  
【０１２４】
ＭＯＰ-ＤＢでクエリーの処理テストを行うには、数多くのレコードを格納した十分に大きいデータベースが必要なため、Windows XP Professional（登録商標）を搭載した一般のエントリーレベルのパーソナル・コンピュータ（１つのCeleron CPU ２．５３ＧＨｚプロセッサ、５１２ＭＢのメインメモリ、１つの１４５ＧＢディスク）上に、図７-１, 図７-２のリレーションEMPLOYEE,  DEPARTMENT，WORKS_ON，PROJECTと４つのリレーションから構成されるデータベースを作成し、それぞれのリレーションに１０万件ずつレコードを格納し、合計４０万件ほどのレコードをデータベースに加えた。クエリーを効率よく高速に処理するには、リレーションにインデックスが必要であるため、リレーションEMPLOYEE７０１の主属性SSNに対して主インデックス７００を作成し、２次属性PHONEに対して２次インデックス７０２を作成した。リレーションDEPARTMENT７０５では、主属性DNUMBERに対して主インデックス７０４を作成し、２次属性DPHONEに対して２次インデックス７０６を作成した。リレーションPROJECT７０８では、主属性PNUMBERに対して主インデックス７０７を作成した。リレーションWORKS_ON７０３に対しては、インデックスを用いないことにした。同様に、ＭｙＳＱＬバージョン３を用いた場合にも、４個のリレーションから構成される共通のデータベースを作成し、ＭＯＰ-ＤＢと同様に、データベース内のリレーションに対してインデックスを加えた。
【０１２５】
次にデータベース・サーバに問い合わせるクエリーは、それぞれのクエリー・プロセッサの処理能力を最大限に利用するために、複雑な検索処理を必要とする数多くの異なるクエリーをＳＱＬで記述した。それらのクエリーは次のような条件や特性を持つものである。
１）  問い合わせるクエリーには、同じクエリーが１つとして含まれないようにするため、すべてのクエリーの検索条件は異なるものにした。また、各クエリーには、演算、属性、変数からなる条件式をブール演算のＡＮＤ，ＯＲを組み合わせて、さらに複雑な条件式を持たせて絞込み検索を行うようにした。
【０１２６】
２）  クエリー・プロセッサによって十分な結合演算処理が行われるように、各クエリーには２つ以上の結合演算を含むようにした。また、クエリー・プロセッサによって必ず検索結果が得られるように、各クエリーには検索条件がゼロにならない検索条件を与えた。
３）  クエリー・プロセッサによってあらゆる種類の処理結果が得られるように、１０００件以下の処理結果が得られるクエリー、１０００件から１万件の処理結果が得られるクエリー、１万件から５万件の処理結果が得られるクエリー、５万件から１０万件の処理結果が得られるクエリーをそれぞれ十分な数ほど（それぞれ２５パーセントずつ）データベースに問い合わせた。
【０１２７】
４）  クエリー・プロセッサによってインデックスを用いた検索が行われるように、検索条件に主インデックスを利用するクエリー、２次インデックスを利用するクエリー、主インデックスと２次インデックスの両方を利用するクエリーを与えた。また、インデックスを利用しないクエリーがインデックスを利用するクエリーとまじわって処理されるように、選択条件に主インデックスと２次インデックスの両方を利用しないクエリーも与えた。
【０１２８】
ＭＯＰ-ＤＢのダイナミック・マルチオペレーション・プロセッシングを適用したクエリー・プロセッシング、スタティック・マルチオペレーション・プロセッシングを適用したクエリー・プロセッシング、及びＭｙＳＱＬバージョン３の処理速度を調べるために、データベース・サーバに検索処理を要求するクライアントプログラムを用意し、クライアントプログラムから数多くのＳＱＬで記述されたクエリーをデータベース・サーバに問い合わせて、データベース・サーバ上のクエリー・プロセッサによってすべてのクエリーが処理されて、検索結果がクライアントプログラムに返されるまでの時間を測定する方法を用いた。クライアントコンピューターとデータベース・サーバとの間の通信速度の影響を避けるために、直接、データベース・サーバ上でクライアントプログラムを起動させて、検索処理結果が得られるようにした。データベースに問い合わせるために作成したクエリーの数は、１００件、２００件、３００件、４００件、５００件、６００件、７００件、８００件、９００件、１０００件となるように、徐々に件数を増加させてクエリーの処理速度を測定した。同様に、ＭｙＳＱＬバージョン３に対しても、上述した件数と同数のクエリー数を用いて、ＭｙＳＱＬのクエリーの処理速度を測定して、ＭｙＳＱＬの処理速度とＭＯＰ-ＤＢを用いたダイナミック・マルチオペレーション・プロセッシング、スタティック・マルチオペレーション・プロセッシングと処理速度を比較した。
【０１２９】
図８は、ＭＯＰ-ＤＢのダイナミック・マルチオペレーション・プロセッシング、スタティック・マルチオペレーション・プロセッシング、及びＭｙＳＱＬのバージョン３に対して、数多くのクエリーを問い合わせたときに、クエリー数と測定したクエリーの処理速度の関係を表（ａ）とグラフ（ｂ）で表わしたものである。
図８に示した実験結果からクエリー数が１００件から１０００件までの件数において、全体的に、ダイナミック・マルチオペレーション・プロセッシングの処理速度が最も早く、その次にスタティック・マルチオペレーション・プロセッシングとなり、ＭｙＳＱＬの処理速度が一番遅いことがわかる。
【０１３０】
ダイナミック・マルチオペレーション・プロセッシングを用いたときには、クエリー数が１００件から５００件までは、図８（ａ），（ｂ）に示した表やグラフから、ＭｙＳＱＬバージョン３の処理速度よりも平均して３．８６倍の処理速度が得られ、クエリー数が６００件から１０００件まででは、ＭｙＳＱＬバージョン３の処理速度よりも平均して３．９１倍の処理速度が得られた。
スタティック・マルチオペレーション・プロセッシングを用いたときには、図８（ａ），（ｂ）に示すように、クエリーの数が１００件から５００件までは、ＭｙＳＱＬバージョン３の処理速度よりも平均して３．５９倍の処理速度が得られ、クエリー数が６００件から１０００件まででは、ＭｙＳＱＬバージョン３の処理速度よりも平均して３．６２倍の処理速度が得られた。
【０１３１】
以上のように、ダイナミック・マルチオペレーション・プロセッシングとスタティック・マルチオペレーション・プロセッシングは、ＭｙＳＱＬバージョン３よりも処理速度が改善され、ダイナミック・マルチオペレーション・プロセッシングの場合は、ＭｙＳＱＬバージョン３よりも３．８６〜３．９１倍の処理速度の向上が見られ、スタティック・マルチオペレーション・プロセッシングの場合は、ＭｙＳＱＬバージョン３よりも３．５９〜３．６２倍の処理速度の向上が見られ、クエリー数が増加するにつれて、処理速度が向上していく傾向がある。この２つのマルチオペレーション・プロセッシングにおいては、ダイナミック・マルチオペレーション・プロセッシングのほうがスタティック・マルチオペレーション・プロセッシングよりも処理速度が速くなっている。
【０１３２】
従来の技術の問題点の解決方法として、ディスクなどの２次記憶装置へのアクセス回数を減らし、クエリーの処理速度を向上させるために、マルチオペレーション・プロセッシングを用いたデータベースのクエリー（問い合わせ）処理システムを提案した。
マルチオペレーション・プロセッシングは、問い合わせのあった数多くのクエリーからのタスクが共通のリレーションに対して処理を行うときに、それらのタスクをグループに集め、グループ内の各タスクに対してアクセスプランを作成し、アクセスプランをもとにして、それぞれのタスクによるディスク内のブロックへのアクセスから共通ブロックを見つけ、その共通ブロックを使用して、グループに集められたタスクの処理を一度に行うようにした。
【０１３３】
そのことによって、それぞれのタスクごとにディスク内のブロックにアクセスすることなしに、ブロックをアクセスすることが一度だけで済むことになり、共通ブロックでいくつかのタスク処理を一度に行うことができるようになり、クエリーの処理速度を向上させることができるようになった。
また、マルチオペレーション・プロセッシングは、グループ内の各タスクのアクセスプランから処理コストを求めて、処理コストの小さいタスクから処理コストの大きいタスクへと順番に処理が終了するようにブロックをアクセスすることによって、処理コストの小さい処理ツリー（処理ツリーの処理コストは、処理ツリー内のすべてのタスクの処理コストを合計したものである）から順番に処理が終了していくことになり、その結果、その処理ツリーに対応するクエリーに対してすばやく処理結果を出すことができるようになった。
【０１３４】
以上のようにして、クエリーの処理速度を改善することによって、ユーザから問い合わせのあった数多くのクエリーの処理を効率よく行って、クエリーの処理結果をユーザに速やかに返すことができるようになった。
実験結果からもわかるように、これまで広く使用されているＭｙＳＱＬ．Ｖｅｒ３よりも３．５倍以上クエリーの処理速度を向上させることができた。
【図面の簡単な説明】
【０１３５】
【図１】データベース・マネージメント・システムのアーキテクチャを示す図である。
【図２】クエリー処理を行うためのフローチャートを示す図である。
【図３】主インデックスと２次インデックスを含んだデータベースのリレーション（DEPARTMENT）を示す図である。
【図４】主インデックス含んだデータベースのリレーション（EMPLOYEE）を示す図である。
【図５−１】処理ツリーを示す図である（その１)。
【図５−２】処理ツリーを示す図である（その２)。
【図６】ダイナミック・マルチオペレーション・プロセッシング及びスタティック．マルチオペレーション．プロセッシングによるタスク処理を示す図である。
【図７−１】実験例に使用したデータベースを示す図である（リレーション:EMPLOYEE， WORKS_ON）。
【図７−２】実験例に使用したデータベースを示す図である（リレーション:DEPARTMETNT, PROJECT）。
【図８】マルチオペレーション・プロセッシングの実行結果の表とグラフを示す図である。
【図１】
2008165622.tif 000010
【図２】
2008165622.tif 000011
【図３】
2008165622.tif 000012
【図４】
2008165622.tif 000013
【図５−１】
2008165622.tif 000014
【図５−２】
2008165622.tif 000015
【図６】
2008165622.tif 000016
【図７−１】
2008165622.tif 000017
【図７−２】
2008165622.tif 000018
【図８】
2008165622.tif 000019
【手続補正書】
【提出日】平成19年3月22日(2007.3.22)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
処理プランＰ１ 
（t11）:  TEMP_T1_1  ← πDNUMBER,MGRSSNDEPARTMENT
（t12）:  TEMP_T2_1  ← σSSN=453432334EMPLOYEE
（t13）:  TEMP_T3_1  ← πSSN,FNAME,LNAME,DNUMTEMP_T2_1
（t14）:  TEMP_T4_1  ← TEMP_T1_1 |X|DNUMBER = DNUM TEMP_T3_1
（t15）:  RESULT_Q1  ← πSSN,FNAME,LNAME,DNUMBER,MGRSSNTEMP_T4_1
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
処理プランＰ３ 
（t31）:  TEMP_T1_3  ← σDNUMBER≧7 AND DNUMBER≦18 DEPARTMENT
（t32）:  TEMP_T2_3  ← πDNUMBER,DNAME TEMP_T1_3
（t33）:  TEMP_T3_3  ← σBDATE>'JAN-1-1971'EMPLOYEE
（t34）:  TEMP_T4_3  ← πFNAME,LNAME,BDATE,DNUMTEMP_T3_3
（t35）:  TEMP_T5_3  ← TEMP_T2_3 |X|DNUMBER=DNUMTEMP_T4_3
（t36）:  RESULT_Q3  ← πFNAME,LNAME,BDATE,DNUMBER,DNAMETEMP_T5_3
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】
処理プランＰ５ 
（t51）:  TEMP_T1_5  ← σDPHONE=23-3721 DEPARTMENT
（t52）:  TEMP_T2_5  ← πDNUMBER,DNAME,DPHONE TEMP_T1_5
（t53）:  TEMP_T3_5  ← σSSN=441111111 EMPLOYEE
（t54）:  TEMP_T4_5  ← πSSN,FNAME,LNAME,DNUM TEMP_T3_5
（t55）:  TEMP_T5_5  ← TEMP_T2_5 |X|DNUMBER=DNUM TEMP_T4_5
（t56）:  RESULT_Q5  ← πSSN,FNAME,LNAME,DNUMBER,DNAME,DPHONE TEMP_T5_5
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
次に、これらのタスクを各タスクがアクセスするデータベースのリレーションをもとにグループに分けていくと、次のようにグループ分けすることになる。なお、２つのリレーションをアクセスする結合演算のタスクなどの場合は、検索先のリレーションではなく検索元のリレーションをもとにしてグループ分けを行う。
DEPARTMENT:    グループ  Ｇ１＝｛t11,t21,t31,t41,t51｝
EMPLOYEE:    グループ  Ｇ２＝｛t12,t23,t33,t53｝
グループＧ1には、リレーションDEPARTMENTに対して処理を行うタスクが集められ、グループＧ2には、リレーションEMPLOYEEに対して処理を行うタスクが集められてグループ分けが行われる。
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2008165622.tif 000020
【手続補正書】
【提出日】平成19年10月15日(2007.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースへのアクセス領域ごとにグループ分けするグループ分け手段と、
前記グループ分けされたタスクごとに、マルチオペレーション・プロセッシングを行う
マルチオペレーション・プロセッシング手段と
を備え、
前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクの処理コストを計算して処理コストの小さい順にタスクを並べ、タスクがアクセスするブロックの格納位置を調べ、タスクがアクセスする順に該ブロックの格納位置を並べ、この順に該ブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出して実行することを特徴とするクエリー処理システム。
【請求項２】
請求項１に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段が、タスクがアクセスする順にブロックの格納位置を並べることは、タスクがアクセスするブロックの集合に対して、タスクの処理コストが小さい順に順次和集合を求め、新たに加わる集合のブロックは和集合の最後に加え、最終の和集合のブロック順であり、
読み出したブロックにアクセスするタスクをグループ内から抽出することは、読み出したブロックと、前記タスクがアクセスするブロックの集合との積集合を求め、空集合でないタスクを求めることで行うことを特徴とするクエリー処理システム。
【請求項３】
請求項１又は２に記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項４】
請求項１又は２に記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
上記目的を達成するために、本発明は、マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースへのアクセス領域ごとにグループ分けするグループ分け手段と、前記グループ分けされたタスクごとに、マルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段とを備え、前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクの処理コストを計算して処理コストの小さい順にタスクを並べ、タスクがアクセスするブロックの格納位置を調べ、タスクがアクセスする順に該ブロックの格納位置を並べ、この順に該ブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出して実行することを特徴とする。
前記マルチオペレーション・プロセッシング手段が、タスクがアクセスする順にブロックの格納位置を並べることは、タスクがアクセスするブロックの集合に対して、タスクの処理コストが小さい順に順次和集合を求め、新たに加わる集合のブロックは和集合の最後に加え、最終の和集合のブロック順であり、読み出したブロックにアクセスするタスクをグループ内から抽出することは、読み出したブロックと、前記タスクがアクセスするブロックの集合との積集合を求め、空集合でないタスクを求めることで行ってもよい。
上述のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやそのプログラムを記録した記録媒体も本発明である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
ＳＱＬなどの問い合わせ言語で記述されたクエリーを、関係代数を接点とするタスクで構成された処理ツリーに変換して、処理ツリーの処理を行う。本発明では、このクエリーの処理ツリー内のいくつかのタスクが共通のリレーションに対して処理を要求する場合、共通のリレーションをアクセスするタスクをグループに集めて、マルチオペレーション・プロセッシングを使用してグループ処理を行うものである。
グループ内の各タスクのアクセスプランから処理コストを求めて、処理コストの小さいタスクから処理コストの大きいタスクへと順番に並べる。タスクの処理コストとは、タスクの処理を行うためにリレーション内のブロックをディスクからアクセスする回数であり、ブロックをアクセスする回数が少ないタスクほど処理コストが小さいことになる。
さらに、グループに集められた各タスクに対してアクセスプランを作成し、アクセスプランをもとに、各タスクから共通のブロックへのアクセスを見つけ、共通ブロックをアクセスし、共通ブロック上でグループ内のタスク処理を一度に行って、共通リレーションの同じブロックを何度もアクセスすることなしに、ブロックをアクセスすることが一度だけで済むようにしている。
処理コストの小さい処理ツリーから順番に処理が終了していくことになり、その結果、その処理ツリーに対応するクエリー(問い合わせ)に対してすばやく処理結果を出すことが可能になる。
【手続補正書】
【提出日】平成20年2月8日(2008.2.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースへのアクセス領域ごとにグループ分けするグループ分け手段と、
前記グループ分けされたタスクごとに、マルチオペレーション・プロセッシングを行う
マルチオペレーション・プロセッシング手段と
を備え、
前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクの処理コストを計算して処理コストの小さい順にグループ内のタスクを並べ、該タスクがアクセスするブロックを調べ、グループ内のタスクが並んだ順に該ブロックへのアクセス順を決定し、決定したアクセス順に該ブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出して実行することを特徴とするクエリー処理システム。
【請求項２】
請求項１に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段が、タスクが並んだ順にブロックへのアクセス順を決定することは、タスクがアクセスするブロックの集合に対して、該タスクが並んだ順に順次和集合を求め、順次和集合に加わるブロックは和集合中のブロックの後に加え、最終的に求まる和集合中のブロックの順番を得ることであり、
読み出したブロックにアクセスするタスクをグループ内から抽出することは、読み出したブロックと、前記タスクがアクセスするブロックの集合との積集合を求め、空集合でないタスクを求めることで行うことを特徴とするクエリー処理システム。
【請求項３】
請求項１又は２に記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項４】
請求項１又は２に記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
上記目的を達成するために、本発明は、マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースへのアクセス領域ごとにグループ分けするグループ分け手段と、前記グループ分けされたタスクごとに、マルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段とを備え、前記マルチオペレーション・プロセッシング手段は、前記グループ分けされたタスクの処理コストを計算して処理コストの小さい順にグループ内のタスクを並べ、該タスクがアクセスするブロックを調べ、グループ内のタスクが並んだ順に該ブロックへのアクセス順を決定し、決定したアクセス順に該ブロックを読み出し、読み出したブロックにアクセスするタスクをグループ内から抽出して実行することを特徴とする。
前記マルチオペレーション・プロセッシング手段が、タスクが並んだ順にブロックへのアクセス順を決定することは、タスクがアクセスするブロックの集合に対して、該タスクが並んだ順に順次和集合を求め、順次和集合に加わるブロックは和集合中のブロックの後に加え、最終的に求まる和集合中のブロックの順番を得ることであり、読み出したブロックにアクセスするタスクをグループ内から抽出することは、読み出したブロックと、前記タスクがアクセスするブロックの集合との積集合を求め、空集合でないタスクを求めることで行ってもよい。
上述のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやそのプログラムを記録した記録媒体も本発明である。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2008165622.tif 000021