(57)【要約】      （修正有）【課題】クエリーの処理速度を向上させる。【解決手段】ＳＱＬなどのクエリーの問い合わせがあると、関係演算で構成された処理ツリーに変換する。直接的に処理することのできるタスクがあると、処理結果に対して処理を行う次のタスクが射影演算であるならば、そのタスクと射影演算タスクの両方を取り出し、射影演算タスクに該タスクを組み合わせたタスクを作成する。共通部分式を持つタスクはさらにサブグループに分ける。サブグループに対しては、グループ内のタスクをもとに、合成関係演算タスク及び／又は合成関係演算を組み合わせたタスクを作成し、グループ内のこれらのタスクの処理を一度に行う。サブグループ内のタスクに対して仮想リレーションを作成し、処理結果のリレーションを部分的に共有できるようにする。 【選択図】図２
2008276464.tif 000002
【特許請求の範囲】
【請求項１】
結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするクループ分け手段と、
グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、
前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、
グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備え、
前記タスク取り出し手段は、グループに加えるべきタスクが選択演算タスク又は結合演算タスクであり、該選択演算タスク又は結合演算タスクの処理結果に対して処理を行う次のタスクが射影演算タスクである場合は、該選択演算タスク又は結合演算タスクと該射影演算タスクとを同時に取り出し、選択演算又は結合演算と射影演算を組み合わせたタスクを作成する
ことを特徴とするクエリー処理システム。
【請求項２】
請求項１に記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、さらに、グループ分けされた前記タスクに複数の結合演算タスクが存在するときに、結合演算タスクを結合演算の共通部分式ごとにサブグループに分け、サブグループに共通のリレーションに対して検索処理を行う結合演算タスクを集め、サブグループに集めた結合演算タスクを、論理和を用いて組み合わせて１つの合成結合演算タスクを作成して処理を行い、
前記仮想リレーション作成手段は、前記サブグループに集めた結合演算タスクに対して仮想リレーションを作成する
ことを特徴とするクエリー処理システム。
【請求項３】
請求項２に記載のクエリー処理システムにおいて、
前記合成関係演算作成手段における前記論理和を用いて組み合わせた１つの合成結合演算タスクの処理は、合成結合演算タスクに含まれる個々の結合演算が共有する１つの検索元のリレーションに対してアクセスするブロックを和集合による集合に集め、該集合内のブロックをディスクにアクセスし、該ブロックからレコードを取り出し、合成結合演算タスクに含まれる個々の結合演算が共有する１つの検索先のリレーションに対して、結合できるレコードを検索し、レコードが検索されると、ブロックから取り出したレコードと検索されたレコードが合成結合演算タスクに含まれる少なくとも１つの結合演算の結合関係を満たしているならば、合成結合演算タスクの処理結果に該レコードを加えていく
ことを特徴とするクエリー処理システム。
【請求項４】
請求項１〜３のいずれかに記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、さらに、グループに選択演算又は結合演算と射影演算とを組み合わせた複数のタスクが存在するときに、
選択演算と組み合わせた該複数のタスクを、それぞれのタスクに含まれる選択演算をもとにして、選択演算の共通部分式ごとにサブグループに分け、サブグループに選択演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの選択条件を満たした合成選択演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成選択演算と合成射影演算を組み合わせた１つのタスクを作成するか、又は、
結合演算と組み合わせた該複数のタスクを、それぞれのタスクに含まれる結合演算をもとにして、結合演算の共通部分式ごとにサブグループに分け、サブグループに結合演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの結合条件を満たした合成結合演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成結合演算と合成射影演算を組み合わせた１つのタスクを作成し、
前記仮想リレーション作成手段は、前記組み合わせた選択演算又は結合演算と射影演算のタスクに対して仮想リレーションを作成する
ことを特徴とするクエリー処理システム。
【請求項５】
請求項１〜４のいずれかに記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段は、１つのグループ内に複数の結合演算タスクが存在するときに、該複数の結合演算タスクが、結合条件に同一の属性を用いて、検索元の仮想リレーションと検索先の仮想リレーションに対して結合演算の処理を行うタスクであり、結合演算の検索元の仮想リレーションは１つの共通の検索元のリレーションに属し、該結合演算の検索先の仮想リレーションは１つの共通の検索先のリレーションに属しているならば、該結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行う
ことを特徴とするクエリー処理システム。
【請求項６】
請求項１〜５のいずれかに記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項７】
請求項１〜５のいずれかに記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースのクエリー処理システムに関し、特に、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリーの処理に関するものである。
【背景技術】
【０００２】
データベース・マネージメント・システム(DBMS)に一度に数多くのクエリーが問い合わせられると、データベース・マネージメント・システムは、トランザクションの同時処理制御機能を使用してそれぞれの問い合わせの処理を行っている。検索のみのトランザクションは、クエリーと呼ばれ、各クエリーは別々に処理されている。そのため従来のデータベース・マネージメント・システムによるクエリーの処理には、問い合わせのあった数多くのクエリーを処理するにあたって次のような問題点がある。
【０００３】
問題点(1): 各クエリーの処理のためにデータベースのデータがアクセスされ、多くのクエリーが共通のリレーションに対して処理を行うと、ディスクから同じデータが何度もメインメモリに読み込まれてアクセスされ、アクセスするたびにディスクのブロック内のデータが繰り返してメインメモリに読み込まれて処理が行われるので、効率的ではなくクエリーの処理速度が低下するといった問題がある。
【０００４】
問題点(2): 従来のデータベース・マネージメント・システムによるクエリー処理方法では、クエリー内のタスク処理を行うたびに、クエリーの中間結果であるタスクの処理結果のリレーションをディスク上に作成しているが、それぞれのタスクの処理結果では、レコードや属性の選択範囲が重なっているため、ディスク上に選択範囲の重なっている処理結果のリレーションを数多く作成することになり、ディスクをアクセスする回数が多くなりクエリーの処理速度が低下するといった問題がある。
【０００５】
問題点(3): 従来のデータベース・マネージメント・システムによるクエリー処理方法では、クエリーに含まれる結合演算の処理を行うとき、ハッシュ結合などの結合方法を用いるので、結合演算の処理を行うたびに、結合演算に使用する検索先のリレーション内のレコードをディスクからアクセスして、メインメモリ内にハッシュテーブル(ハッシュテーブルを検索先のリレーション内のレコードのインデックスとして使用する)を作成するので、ディスクをアクセスする回数が多くなり、クエリーの処理速度が低下するといった問題がある。また、それぞれの結合演算に使用される検索先のリレーションは異なるので、それぞれの結合演算に対して別々にハッシュテーブルを作成する必要があり、数多くのハッシュテーブルをメインメモリに作成すると、十分なメインメモリのスペースを確保することができなくなり、クエリーの処理速度が低下するといった問題がある。
【０００６】
（演算と演算結果のキャッシングの問題点）
ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させるために、問い合わせの多いクエリーとクエリーの処理結果、クエリーに含まれる演算（選択演算，射影演算，結合演算などの関係代数）と演算の処理結果（クエリーの中間結果）を一時的にディスクに保存（キャッシング）しておく方法がよく用いられている。ユーザからクエリーの問い合わせがあると、データベース・マネージメント・システムは、問い合わせのあったクエリーと同じクエリーの処理結果がディスクに保存されているかどうかを調べて、保存されているならば、そのクエリーの処理を行わずに、保存されているクエリーの処理結果をそのままユーザに返すことになる。また、クエリーは異なるけれども、クエリーに含まれる演算と同じ演算の処理結果がディスクに保存されているならば、データベース・マネージメント・システムは、その演算の処理を行わずに、すでに存在する演算の処理結果を利用してクエリーの処理を行うことになる。
【０００７】
この方法は、保存するクエリーの処理結果、演算の処理結果を増やすことで、同じクエリーや演算の処理を繰り返して行うことなしに、クエリーの処理速度を向上させることを目的としている。しかし、この方法は、問い合わせのあったクエリーやクエリーに含まれる演算がディスクに保存しているものと同じでなければならないため、クエリーや演算が異なる場合は、保存されている処理結果を利用することはできない。
また、この方法は、データベースに新たなレコードが加えられるなどしてデータベースが更新されると、保存されている処理結果は古くなるので、データベース・マネージメント・システムは、古くなった処理結果を破棄しなければならない。そのためデータベースの更新がたびたび行われると、その都度、古くなった処理結果を破棄しなければならないので、この方法は効率的ではなくなる。
マイクロソフト社のＳＱＬサーバーなどのデータベース・マネージメント・システムは、クエリーの処理速度を維持するために、古くなったクエリーの処理結果をすぐには破棄せずに、しばらく古い処理結果をユーザに返すようにしている。
【０００８】
（メインメモリへのキャッシングの問題点）
ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させるその他の方法は、クエリーを処理するためによくアクセスされるディスク上のブロックの複製をメインメモリに一時的に保存（キャッシング）しておく方法が用いられる。この方法は、ユーザからクエリーの問い合せがあると、データベース・マネージメント・システムは、クエリーを処理するためにディスクからアクセスするブロックの複製がメインメモリに保存されているかどうかを調べて、保存されているならば、メインメモリ内の複製を利用する。
この方法は、メインメモリ内で保存するブロックの容量を増やしておくことで、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることを目的としている。
【０００９】
しかし、この方法は、ディスク上のブロックとメインメモリ上の複製が同じでなければならないため、ブロック内のデータを変更するときには、ディスク上のブロックとメインメモリ上の複製の両方を更新しておかなければならない。また、クエリーを処理するために数ギガバイト（ＧＢ）もあるようなデータベースのリレーションを線形探索（スキャン）するような場合は、メインメモリに保存されているブロック以外のほとんどのブロックをディスクからアクセスすることになるので有効ではなくなる。
また、オペレーティング・システム自体もこのようなメモリー管理を行っているため、データベース・マネージメント・システムがメインメモリに保存するブロックの容量を増やすと、メインメモリに保存されたはずのブロックがオペレーティング・システムによって仮想メモリー（ディスク）に移動されることなどが起こり、逆にクエリーの処理速度が低下するといった問題が発生する。
【００１０】
（クエリー処理のパイプライン化の問題点）
クエリーの中間結果であるタスクの処理結果のリレーションをディスク上に作成しないで、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させる方法としては、クエリー処理をパイプライン化した方法が用いられる。
クエリー処理をパイプライン化した方法とは、複数のマイクロプロセッサを備えているコンピュータ・システムにおいて、クエリーに含まれるいくつものタスク処理を複数のマイクロプロセッサを用いてパイプラン化し、個々のタスク処理を並列に処理していく方法である。この方法は、クエリーに含まれる個々のタスクの処理結果はストリーム化され、個々のタスク処理が完全に終了するのを待たずして、部分的に終了したタスクの処理結果に対する次のタスク処理を行っていくものである。
しかし、パイプライン化できるタスク処理は、選択演算や射影演算などのタスクに限られ、結合演算などのタスクは、結合演算の前に行われるタスク処理が完全に終了してからではないと処理を始めることができないので、パイプライン化することはできない。
また、クエリー処理をパイプライン化した方法は、複数のマイクロプロセッサを搭載してあるコンピュータ・システムが必要であるので、マイクロプロセッサを１つしか備えていないコンピュータ・システムでは有効ではない。
【００１１】
（マルチクエリーの最適化の問題点）
問い合わせのあったクエリーをそれぞれ別々に処理していく従来のクエリー処理方法とは別の方法としては、問い合わせたあったいくつかのクエリーを組み合わせて１つの処理グラフを作成して処理することによって、いくつかのクエリーの処理を一度に行うマルチクエリーの最適化によるクエリー処理方法がある(１つ以上の処理結果を見出す場合は処理ツリーではなく処理グラフを用いる)。
マルチクエリーの最適化によるクエリー処理方法は、問い合わせたあったいくつかの処理ツリー内に同一のタスク(接点)が存在するならば、それらのタスクを１つのタスクに置き換えて、そのタスクの処理結果を共有するための処理グラフを作成して処理を行う方法である。
【００１２】
また、いくつかの処理ツリーに含まれるタスクが同一ではなくても、処理ツリー内のタスクの処理結果が他の処理ツリー内のタスクの処理結果のサブセットとなる場合は、他のタスクの処理結果からタスク処理を行うための処理グラフを作成して処理を行う方法である。この方法は、他のタスクの処理結果を利用することによって、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることを目的としている。
しかし、他のタスクの処理結果からタスク処理を行うと、データベースのリレーションに含まれるインデックスを利用しないで、処理結果内のレコードを線形探索することになるので、むしろディスクをアクセスする回数が増えて、クエリーの処理速度が低下するといった問題がある。また、この方法は問い合わせられるクエリーの数が増えると、作成することのできる処理グラフの数も増えるので、その中から最も処理コストの少ない処理グラフを検索するのに時間がかかり、クエリーの処理速度が低下するといった問題がある。
その他、マルチクエリーの最適化によるクエリー処理方法は、ユーザから問い合わせたがあったクエリーをすぐに処理するのではなく、一定の時間に与えられたいくつかのクエリーに対して一度に処理していくので、個々のクエリーに対してすばやく反応できないといった問題がある。
【００１３】
発明者が参考にした参考文献を以下に記載する。
問い合わせの多いクエリーとクエリーの処理結果、クエリーに含まれる演算（選択演算、射影演算、結合演算などの関係代数）と演算の処理結果(クエリーの中間結果) を一時的にディスクに保存(キャッシング)しておくことを記載したものとして、以下に記載する非特許文献１〜５がある。
クエリーを処理するためにアクセスされるディスク上のブロックの複製をメインメモリに一時的に保存(キャッシング)しておくことを記載したものとして、非特許文献６〜１０がある。
クエリー処理のパイプライン化を記載したものとしては、非特許文献１１がある。
また、マルチクエリーの最適化を記載したものとしては、非特許文献１２がある。
【００１４】
【非特許文献１】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
【非特許文献１１】David J. DeWitt and Jim Gray. Parallel Database Systems: The Future of High Performance Database Processing. Communications of The ACM, Vol. 36, No. 6, June 1992
【非特許文献１２】TIMOS K. SELLIS. Multiple-Query Optimization. ACM Transactions on Database Systems, Vol. 13, No. 1, Pages 23-52, March 1988.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
以上に述べたような解決方法は、数多くのデータベース・マネージメント・システムに採用されているが、問題点もあるために必ずしも効率的な方法ではない。本発明では、これらの解決方法とは別に、独自に考案するクエリーの処理方法を用いて、ディスクをアクセスする回数を減少させ、クエリーの処理速度を向上させる方法を提案する。
【課題を解決するための手段】
【００１６】
上述の目的を達成するために、本発明は、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするクループ分け手段と、グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備え、前記タスク取り出し手段は、グループに加えるべきタスクが選択演算タスク又は結合演算タスクであり、該選択演算タスク又は結合演算タスクの処理結果に対して処理を行う次のタスクが射影演算である場合は、該選択演算タスク又は結合演算タスクと該射影演算タスクとを同時に取り出し、選択演算又は結合演算と射影演算を組み合わせたタスクを作成することを特徴とする。
【００１７】
前記合成関係演算作成手段は、さらに、グループ分けされた前記タスクに複数の結合演算タスクが存在するときに、結合演算タスクを結合演算の共通部分式ごとにサブグループに分け、サブグループに共通のリレーションに対して検索処理を行う結合演算タスクを集め、サブグループに集めた結合演算タスクを、論理和を用いて組み合わせて１つの合成結合演算タスクを作成して処理を行い、前記仮想リレーション作成手段は、前記サブグループに集めた結合演算タスクに対して仮想リレーションを作成するとよい。
【００１８】
前記合成関係演算作成手段は、さらに、グループに選択演算又は結合演算と射影演算とを組み合わせた複数のタスクが存在するときに、選択演算と組み合わせた該複数のタスクを、それぞれのタスクに含まれる選択演算をもとにして、選択演算の共通部分式ごとにサブグループに分け、サブグループに選択演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの選択条件を満たした合成選択演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成選択演算と合成射影演算を組み合わせた１つのタスクを作成するか、又は、結合演算と組み合わせた該複数のタスクを、それぞれのタスクに含まれる結合演算をもとにして、結合演算の共通部分式ごとにサブグループに分け、サブグループに結合演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの結合条件を満たした合成結合演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成結合演算と合成射影演算を組み合わせた１つのタスクを作成し、前記仮想リレーション作成手段は、前記組み合わせた選択演算又は結合演算と射影演算のタスクに対して仮想リレーションを作成するとよい。
【００１９】
前記マルチオペレーション・プロセッシング手段は、１つのグループ内に複数の結合演算タスクが存在するときに、該複数の結合演算タスクが、結合条件に同一の属性を用いて、検索元の仮想リレーションと検索先の仮想リレーションに対して結合演算の処理を行うタスクであり、結合演算の検索元の仮想リレーションは１つの共通の検索元のリレーションに属し、該結合演算の検索先の仮想リレーションは１つの共通の検索先のリレーションに属しているならば、該結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行うとよい。
上述のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやそのプログラムを記録した記録媒体も本発明である。
【発明の効果】
【００２０】
結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムを適用することによって、単に合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムよりもクエリーの処理速度が向上した。
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムに、改善方法１の関係演算を組み合わせたタスクの取り出し方法を加えることによって、選択演算の処理結果、及び結合演算の処理結果であるリレーションをディスク上に作成することなしに、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることができるようになった。さらに、この関係演算を組み合わせたタスクを作成することによって、複数の関係演算を組み合わせたタスクに対して、改善方法３の合成関係演算を組み合わせたタスクを作成し処理することができるようになった。
【００２１】
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムに、改善方法２の合成結合演算タスクの処理方法を加えることによって、結合演算の共通部分式を持つ結合演算タスクは、サブグループに集められ、サブグループに集められた複数の結合演算タスクを１つの合成結合演算タスクに置き換えて処理を行うことができるようになった。その結果、サブグループ内の個々の結合演算タスクに対して、結合演算の処理を別々に行う必要がなくなり、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることができるようになった。
また、サブグループ内の個々の結合演算タスクは、仮想リレーションを通して合成結合演算タスクの処理結果のリレーションを部分的に共有することができるようになり、サブグループ内の個々の結合演算タスクに対して、結合範囲が重なっている処理結果のリレーションをディスク上に別々に作成する必要がなくなり、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることができるようになった。
さらに合成結合演算タスクの処理を行うことによって、合成結合演算タスクの処理結果のリレーションに対して、改善方法４のマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理を行うことができるようになった。
【００２２】
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムに、改善処理３の合成関係演算を組み合わせたタスクの処理方法を加えることによって、サブグループに集められたいくつもの関係演算を組み合わせたタスクを、１つの合成関係演算を組み合わせたタスクに置き換えて処理を行うことができるようになった。その結果、サブグループに集められた個々の関係演算を組み合わせたタスクは、仮想リレーションを通して合成関係演算を組み合わせたタスクの処理結果のリレーションを部分的に共有することができるようになり、サブグループ内の個々の関係演算を組み合わせたタスクに対して、選択範囲、結合範囲、及び属性(列)が重なる処理結果のリレーションをディスク上に別々に作成する必要がなくなり、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることができるようになった。
さらに、合成関係演算を組み合わせたタスクの処理を行うことによって、合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーションに対して、合成結合演算と合成射影演算を組み合わせたタスクの処理を行うことができるようになり、上述の合成関係演算を組み合わせたタスクの処理を繰り返して行うことができるようになった。
【００２３】
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムに、改善方法４のマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法を加えることによって、グループ内の結合演算タスクに対して、グループ内の個々の結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行うことができるようになり、それぞれの結合演算タスクに対して、レコードの検索処理とレコードの結合処理を別々に行う必要がなくなり、ディスクをアクセスする回数を減少させて、クエリーの処理速度を向上させることができるようになった。
【００２４】
以上のように、本発明は、結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、新しい、関係演算を組み合わせたタスクの取り出し方法、合成結合演算タスクの処理方法、合成関係演算を組み合わせたタスクの処理方法、マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法をデータベースのクエリー処理システムに新たに加えることにして、とくに結合演算に関する処理の向上を図り、ユーザから問い合わせられる数多くのクエリーをさらに効率よく処理することができるようになった。
【発明を実施するための最良の形態】
【００２５】
本発明の発明者は、従来の技術の問題点(１)の解決方法として、ディスクなどの２次記憶装置へのアクセス回数を減らし、クエリーの処理速度を向上させるために、「マルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システム」を提案した（特許２００６−３５６４０６号参照）。
この提案したマルチオペレーション・プロセッシングは、クエリーからのいくつかのタスクが共通のリレーションに対して処理を行うときに、それらのタスクをグループに集め、グループ内の各タスクに対してアクセスプランを作成し、アクセスプランをもとにして、それぞれのタスクによるリレーション内のブロックへのアクセスから共通ブロックを見つけ、その共通ブロックを使用して、グループに集められたタスクの処理を一度に行うものである。この方法は、それぞれのタスクごとにディスク内のブロックにアクセスすることなしに、共通ブロックでいくつかのタスクを一度に処理することによって、クエリー(全体のタスク)の処理速度を向上させることをめざしたものである。
【００２６】
また、問題点(１) の解決方法のさらなる改善と、問題点(２), (３)の解決方法として、本発明の発明者は、「合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システム」を提案した（特許２００７−０７５６７０号参照）。
提案した合成関係演算を利用したマルチオペレーション・プロセッシングは、問題点(1)の解決方法のさらなる改善のために、クエリーからのいくつかのタスクが共通のリレーションに対して処理を行うときに、それらのタスクをグループに集め、グループ内のタスクをさらに共通部分式ごとにサブグループに集めて、それぞれのサブグループに対して合成関係演算タスクを作成し、マルチオペレーション・プロセッシングを用いてグループ内の合成関係演算タスク及びサブグループに集まらないタスクの処理を一度に行うことによって、効率的にクエリー処理を行うことができるようにしたものである。また、この方法は、合成関係演算の処理結果に対して処理を行うタスクもグループに集めてマルチオペレーション・プロセッシングを用いて処理を行うことによって、合成関係演算の処理結果内のブロックを何度もアクセスしないようにしてクエリーの処理速度を向上させることが可能となった。
【００２７】
発明者が前の出願（特許２００７−０７５６７０号参照）で提案した、合成関係演算を利用したマルチオペレーション・プロセッシングでは、問題点(２)を解決するために、グループ内の共通部分式を持つタスクをサブグループに集めて、サブグループに集めたいくつものタスクを１つの合成関係演算タスクに置き換えて処理を行い、サブグループ内の個々のタスクは(自らの処理結果から得られる)仮想リレーションを用いて合成関係演算タスクの処理結果を部分的に共有することによって、サブグループ内の個々のタスクに対して選択範囲が重なっている処理結果のリレーションをディスク上に別々に作成する必要がなくなり、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることが可能となった。
さらに、この合成関係演算を利用したマルチオペレーション・プロセッシングは、問題点(3)を解決するために、合成関係演算タスクの処理結果内のレコードに対して、いくつかの結合演算などのタスクが検索処理を行う場合は、検索に使用される属性に対してインデックスを作成しておくことによって、検索処理を行うタスクはインデックスを共有してレコードを検索することができるようにしたものである。そのことによって、検索処理を行う個々の結合演算タスクのためにメインメモリ内にハッシュテーブルを別々に作成することなしに、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることが可能となった。
【００２８】
今回は、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムをさらに改善するために、４つの改善方法として、関係演算を組み合わせたタスクの取り出し方法、合成結合演算タスクの処理方法、合成関係演算を組み合わせたタスクの処理方法、マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法を取り上げ、これらの方法を、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムに新たに加える。
これらの４つの改善方法を加えることによって、特に結合演算に関する処理が改善され、これらの改善方法を用いない合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムよりもさらに数多くのタスク処理を一度に行い、ディスクへのアクセスを少なくして、ユーザから問い合わせのあった数多くのクエリーをすばやく処理していくことが可能になる。
以下に詳しく説明する、本発明の「結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システム」は、本発明者が、以前に出願した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システム（特許２００７−０７５６７０号参照）に次に述べる４つの改善方法を加えたものである。
【００２９】
[改善方法１: 関係演算を組み合わせたタスクの取り出し方法]
関係演算を組み合わせたタスクの取出し方法とは、問い合わせがあった数多くのクエリーからのタスク処理を行うにあたって、クエリーの最適化によって作成された処理ツリーから、直接的に処理できるタスクをアクセスするデータベースのリレーションをもとにグループに分けるときに、グループに加えるべきタスクが選択演算のタスクであり、選択演算のタスクの処理結果に対して処理を行う次のタスクが射影演算である場合は、選択演算タスクと射影演算タスクを同時に取り出し、選択演算と射影演算を組み合わせたタスクを作成し、そのタスクをグループに加えるようにしたものである。
【００３０】
また、グループに加えるべきタスクが結合演算タスクであり、結合演算タスクの処理結果に対して処理を行う次のタスクが射影演算である場合は、結合演算タスクと射影演算タスクを同時に取り出し、結合演算と射影演算を組み合わせたタスクを作成し、そのタスクをグループに加えるようにしたものである。
選択演算と射影演算を組み合わせたタスクの処理方法は、選択演算と射影演算の処理を一度に行うことになり、選択演算の処理を行った個々のレコードに対して、射影演算の処理を行い、射影したレコードを選択演算と射影演算を組み合わせたタスクの処理結果に直接加えるものとする。結合演算と射影演算を組み合わせたタスクの処理方法は、結合演算と射影演算の処理を一度に行うことになり、結合演算の処理を行った個々のレコードに対して、射影演算の処理を行い、射影したレコードを結合演算と射影演算を組み合わせたタスクの処理結果に直接加えるものとする。
【００３１】
このようにして、関係演算を組み合わせたタスクの取り出し方法は、選択演算の処理結果、及び結合演算の処理結果であるリレーションをディスク上に作成して、次のタスク処理として射影演算のタスクを行うということではなく、選択演算と射影演算を組み合わせたタスク処理、及び結合演算と射影演算を組み合わせたタスク処理を行って、クエリーの処理速度を向上させることを目的とするものである。
【００３２】
[改善方法２: 合成結合演算タスクの処理方法]
改善方法２としての合成結合演算タスクの処理方法は、問い合わせがあった数多くのクエリーからのタスク処理を行うにあたって、グループに結合演算タスクがいくつか存在するときに、結合演算タスクを結合演算の共通部分式ごとにサブグループに分け、サブグループに一つの共通のリレーションに対して検索処理を行う結合演算タスクを集め、サブグループに集めた結合演算タスクを、論理和を用いて組み合わせ、サブグループ内のすべての結合演算タスクの結合条件を満たした１つの合成結合演算タスクを作成して処理を行うことである。
【００３３】
作成した合成結合演算タスクの処理は、合成結合演算タスクに含まれる個々の結合演算が共有する検索元のリレーションに対してアクセスする必要のあるブロックを見出し、それらのブロックをそれぞれの結合演算に対応するブロック集合に集める。次に、それぞれの結合演算に対応するブロック集合の和集合を求めて、合成結合演算タスクに対応するブロック集合を求める。次に、合成結合演算タスクに対応するブロック集合のブロックをディスクにアクセスし、アクセスされたブロックからレコードを取り出して、合成結合演算の結合条件を満たすレコードを、共通の検索先のリレーションに対して検索する。合成結合演算の結合条件を満たすということは、合成結合演算に含まれる個々の結合演算のどれかの結合関係を満たすということである。検索先のリレーションからレコードが検索されると、検索されたレコードとブロックから取り出したレコードを結合し、結合したレコードを合成結合演算タスクの処理結果に加える。
このようにして合成結合演算タスクの処理を行うことによって、合成結合演算タスクに含まれる個々の結合演算の処理を別々に行う必要がなくなり、ディスクのブロックをアクセスする回数を減少させてクエリーの処理速度を向上させることが可能となる。
【００３４】
合成結合演算タスクの処理を行って、処理結果を作成すると、サブグループ内の個々の結合演算タスクが、合成結合演算タスクの処理結果を部分的に共有することになるので、共有していることを示すために、サブグループ内の個々の結合演算タスクに対して、仮想リレーションを作成し、その仮想リレーションに、その仮想リレーションが共有する処理結果のリレーション名、その処理結果に包含されるレコードの行範囲、属性の列番号、レコードが格納してあるブロックの番号とアドレスを記録しておくことにする。
このようにして合成結合演算タスクの処理結果内のレコードをサブグループ内の個々の結合演算タスクが仮想リレーションとして部分的に共有することによって、サブグループ内の個々の結合演算タスクに対して、レコードの結合範囲が重なっている処理結果のリレーションをディスク上に別々に作成することがなくなり、クエリーの処理速度を向上させることができる。
また、仮想リレーションを作成して合成結合演算タスクの処理結果を共有するもう一つの目的は、合成結合演算タスクの処理結果のリレーションに対して改善方法４のマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理を行うためである。
【００３５】
[改善方法３:合成関係演算を組み合わせたタスクの処理方法]
改善方法３としての方法は、問い合わせがあった数多くのクエリーからのタスク処理を行うにあたって、グループに選択演算と射影演算を組み合わせたタスクがいくつか存在するときに、それらのタスクをそれぞれのタスクに含まれる選択演算をもとにして、選択演算の共通部分式ごとにサブグループに分け、サブグループに選択演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの選択条件を満たした合成選択演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成選択演算と合成射影演算を組み合わせた１つのタスクを作成して処理を行うことである。
また、問い合わせのあった数多くのクエリーからのタスク処理を行うにあたって、グループに結合演算と射影演算を組み合わせたタスクがいくつか存在するときに、タスクに含まれる結合演算をもとにして、結合演算の共通部分式ごとにサブグループに分け、サブグループに結合演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの結合条件を満たした合成結合演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成結合演算と合成射影演算を組み合わせた１つのタスクを作成して処理を行うことである。
【００３６】
このようにしてサブグループに集められたいくつかの関係演算を組み合わせたタスクを合成関係演算として１つのタスクに置き換えて処理を行うことによって、クエリーの処理速度を向上させることが可能になる。
合成関係演算を組み合わせたタスク処理を行って、処理結果を作成すると、サブグループ内の個々の関係演算を組み合わせたタスクは、合成関係演算を組み合わせたタスクの処理結果を部分的に共有することになる。そのため、共有していることを示すために、サブグループ内の個々のタスクに対して、仮想リレーションを作成し、その仮想リレーションに、仮想リレーションが共有する処理結果のリレーション名、その処理結果の中から共有するレコードの行範囲、属性の列番号、レコードが格納してあるブロックの番号とアドレスを記録しておくことにする。
このようにして、合成関係演算を組み合わせたタスクの処理結果内のレコード及び属性(列)を、サブグループ内の関係演算を組み合わせたタスクが仮想リレーションとして部分的に共有することによって、サブグループ内の個々の関係演算を組み合わせたタスクに対して、レコードの選択範囲、結合範囲、及び属性(列)が重なっている処理結果のリレーションをディスク上に別々に作成することがなくなり、クエリーの処理速度を向上させることができる。
また、仮想リレーションを通して合成関係演算を組み合わせたタスクの処理結果のリレーションを共有するもう一つの目的は、合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーションに対して、合成結合演算と合成射影演算を組み合わせたタスク処理を行うためである。
【００３７】
[改善方法４：マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法]
改善方法４としての方法は、問い合わせがあった数多くのクエリーからのタスク処理を行うにあたって、グループに結合演算タスクがいくつか存在するときに、グループ内の個々の結合演算タスクは、結合条件に同一の属性を用いて、検索元の仮想リレーションと検索先の仮想リレーションに対して結合演算の処理を行うタスクであり、結合演算の検索元の仮想リレーションは１つの共通の検索元のリレーションに属し、結合演算の検索先の仮想リレーションは１つの共通の検索先のリレーションに属しているならば、個々の結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行う方法である。
【００３８】
この方法を用いてグループ内の複数の結合演算タスクの処理を行うには、マルチオペレーション・プロセッシングの手順にもとづいて、共通の検索元のリレーションに対してアクセスする必要のあるブロックを共通ブロックとしてディスクにアクセスし、共通ブロックからレコードを取り出し、取り出したレコードと結合関係を満たすレコードを共通の検索先であるリレーションに対して検索する。レコードが検索されると、検索されたレコードと共通ブロックから取り出したレコードを結合し、共通ブロックで処理を行う必要のあるグループ内の最初の結合演算タスクに対して、その結合演算タスクが使用する検索先の仮想リレーションに、検索されたレコードを含んでいて、その結合演算タスクが使用する検索元の仮想リレーションに、共通ブロックから取り出したレコードを含んでいるならば(その結合演算タスクの結合関係を満たしているならば)、結合されたレコードを結合演算タスクの処理結果に加えるものとする。
【００３９】
次に、共通ブロックで処理を行う必要のあるグループ内の次の結合演算タスクに対しても、その結合演算タスクが使用する検索先の仮想リレーションにすでに検索されたレコードを含んでいて、その結合演算タスクが使用する検索元の仮想リレーションに共通ブロックからすでに取り出したレコードを含んでいるならば、すでに結合したレコードをその結合演算タスクの処理結果に加えるものとする。同様に、共通ブロックで処理を行う必要のあるグループ内の残りの結合演算タスクに対しても、それらの結合演算タスクの検索先の仮想リレーションにすでに検索されたレコードを含んでいて、それらの結合演算タスクが使用する検索元の仮想リレーションに共通ブロックからすでに取り出したレコードを含んでいるならば、すでに結合されたレコードをそれらの結合演算タスクの処理結果にそれぞれ加えるものとする。
【００４０】
共通ブロックから最初に取り出されたレコードに対して、グループ内のすべての結合演算タスクの処理が行われると、共通ブロックから次々とレコードを取り出して、それぞれのレコードに対して、以上に述べた結合演算のタスク処理を繰りかえてして行うものとする。このようにして、共通の検索先のリレーションに対して検索されたレコードと検索元のリレーションの共通ブロックから取り出されたレコード及びそれらのレコードを結合したレコードをグループ内の個々の結合演算タスクごとに利用し、個々の結合演算タスクの処理のために、レコードの検索処理とレコードの結合処理を別々に行うことなしに、クエリーの処理速度を向上させることがマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法である。
以下で、本発明の実施形態について詳しく説明する。
＜結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムの概要＞
まず、４つの改善手段を加えた合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムの概要を説明する。
【００４１】
［データベースシステムのアーキテクチャ］
図１は、この実施形態のクエリーの処理に用いるデータベースシステムのアーキテクチャである。ここで示したアーキテクチャは、この出願の発明者が前に出願した特願２００６−３５６４０６号及び特願２００７−０７５６７０号で示したアーキテクチャと、基本的に同様のものである。以下では、クエリーQ1〜Q6をユーザから問い合わせのあったクエリーとして扱い、データベースのアーキテクチャを説明していくことにする。
【００４２】
クエリーQ1〜Q6は、クエリーの最適化を行うクエリーオプティマイザ (1000)によって最適化され、関係代数で構成された処理ツリーP1〜P6(1002)に変換される。クエリーオプティマイザ(1000)とマルチオペレーション・プロセッサ(1006)を制御し、クエリーの一連の処理を行うクエリー・プロセッサ(1001)は、処理ツリーP1〜P6からトポロジカルソートの順番で、他のタスクから依存がなく、直接的に処理できる選択演算タスクt11, t13, t15, t21, t23, t25, t31, t33, t35, t41, t43, t45, t51, t53, t55, t61, t62 (1003)を見つける。
次に、上述した[改善方法１］を適用して、選択演算タスクt11, t13, t21, t23, t31, t33, t41, t43, t51, t53, t62 (1003)の処理結果に対して、処理を行う次のタスクt12, t14, t22, t24, t32, t34, t42, t44, t52, t54, t63が射影演算であるため、クエリー・プロセッサは、選択演算タスクと射影演算タスクを同時に取り出して、選択演算と射影演算を組み合わせたタスクt12', t14', t22', t24', t32', t34', t42', t44', t52', t54', t63'を作成する。これらの選択演算タスクや射影演算タスクの組み合わせについては、後で詳しく説明する。
【００４３】
クエリー・プロセッサは選択演算と射影演算を組み合わせたタスクt12', t14', t22', t24', t32', t34', t42', t44', t52', t54', t63'、及び直接的に処理できるタスクt15, t25, t35, t45, t55, t61(1004)を、それぞれのタスクがアクセスするデータベースのリレーションをもとにしてグループG1〜G4に分ける。
タスクt14', t24', t34', t44', t54', t63'をグループG1に集め、タスクt12', t22', t32', t42', t52'をグループG2に集め、タスクt15, t25, t35, t45, t55をグループG3に集め、タスクt61をグループG4に集めることになる。
【００４４】
グループにタスクを集めると、クエリー・プロセッサは、共通部分式を持つタスクを、さらにサブグループに集める。選択演算と射影演算の共通部分式をもつタスクとして、タスクt14', t24', t34'をサブグループSG1G1集め、タスクt54', t63'をサブグループSG2G1に集め、タスクt12', t22', t32'をサブグループSG1G2に集め、タスクt15, t25, t35, t55をサブグループSG1G3に集めることになる。クエリー・プロセッサは、サブグループにタスクを集めると、サブグループに対して、［改善方法２］，[改善方法３]を適用して、合成関係演算を組み合わせたタスク及びを作成する。サブグループSG1G1に対して合成選択演算と合成射影演算を組み合わせたタスクtG1SG1を作成し、サブグループSG2G1に対して、合成選択演算と合成射影演算を組み合わせたタスクtG1SG2を作成し、サブグループSG1G2に対して合成選択演算と合成射影演算を組み合わせたタスクtG2SG1を作成し、サブグループSG1G3に対して合成射影演算タスクtG3SG1を作成する。グループ内の個々のサブグループに対して合成関係演算を組み合わせたタスク及び合成関係演算タスクを作成すると、クエリー・プロセッサは、グループG1〜G4をグループ列(キュー) (1005)に挿入する。
【００４５】
グループの処理を行うマルチオペレーション・プロセッサ(1006)は、利用できるプロセス(1007)の数 (ここでは、例として４つのプロセスを用意している)に対して、グループ列(キュー)(1005)からグループG1〜G4（ここでは4グループ）を取り出し、用意しているそれぞれのプロセスにマルチオペレーション・プロセッシングを用いたグループの処理を行わせる。ここでは、プロセス１がグループG1の処理を行い、プロセス２がグループG2の処理を行い、プロセス３がグループG3の処理を行い、プロセス4はグループG4の処理を行うことにする。これらのプロセスの処理は、オペレーティングシステム(OS)のプロセスのスケジューリングによって同時に処理されることになる。このグループごとのプロセスの処理において、［改善方法４］による処理方法が行われる。
また、データベースサーバーに複数のCPU(1008)を備えているならば、それぞれのプロセスによるグループの処理は、別々のCPU上で並列に処理されることになる。
【００４６】
まず、プロセス１で、グループG1内の合成選択演算と合成射影演算を組み合わせたタスクtG1SG1, tG1SG2及びサブグループに集まらないタスクt44'の処理が、t44', tG1SG2, tG1SG1の順番で行われる。これらのタスクが終了すること、クエリー・プロセッサは、新たに処理できるタスクを処理ツリーから検索する。新たに処理できるタスクは見つからないときは、プロセス１は、グループ列に新しいグループが加えられるまで待機することになる。
プロセス２では、グループG2内の合成選択演算と合成射影演算を組み合わせたタスクtG2SG1及びサブグループに集まらないタスクt42', t52'の処理がt42', tG2SG1, t52'の順番で行われる。これらのタスクが終了すると、クエリー・プロセッサは、新たに処理できるタスクを処理ツリーから検索する。新たに処理できるタスクが見つからないときは、プロセス２は、グループ列に新しいグループが加えられるまで待機することになる。
プロセス３では、グループG3内の合成射影演算のタスクtG3SG1、及びサブグループに集まらないタスクt45の処理がtG3SG1, t45の順番で行われる。
【００４７】
これらのタスクが終了すると、クエリー・プロセッサは、新たに処理できるタスクを処理ツリーから検索する。合成射影演算のタスクtG3SG1の処理が終了すると、新たに結合演算タスクt16, t26, t36, t56の処理ができるようになる。また、これらのタスクの処理結果に対して処理を行うタスクt17, t27, t37, t57は射影演算であるので、クエリー・プロセッサは、結合演算タスクと射影演算タスクを同時に取り出し、結合演算タスクt16, t26, t36, t56と射影演算タスクt17, t27, t37, t57をそれぞれ組み合わせて、結合演算と射影演算を組み合わせたタスクt17', t27', t37', t57'を作成し、これらのタスクのために新たにグループG5を作成し、グループG5にこれらのタスクを加える。さらに、タスクt17', t27', t37'は結合演算の共通部分式を持っているため、クエリー・プロセッサは、グループG5内にサブグループSG1G5を作成し、SG1G5に結合演算と射影演算を組み合わせたタスクt17', t27', t37'を加えて、SG1G5に対して合成結合演算と合成射影演算を組み合わせたタスクtG5SG1を作成する。
【００４８】
合成結合演算と合成射影演算を組み合わせたタスクtG5SG1とタスクt57'を作成すると、クエリー・プロセッサは、グループG5をグループ列(キュー)に挿入する。そのとき、グループ列にグループが加えられるまで待機していたプロセス１とプロセス２のうち、プロセス１がグループ列からグループG5を取り出して、グループG5の処理を始めることになる。同様に、グループG3のタスクt45の処理が終了すると、新たに結合演算タスクt46の処理ができるようになり、結合演算タスクt46の処理結果に対して処理を行うタスクt47は射影演算であるので、クエリー・プロセッサは、結合演算タスクと射影演算タスクを同時に取り出し、結合演算タスクt46と射影演算タスクt47を組み合わせてタスクt47'を作成し、タスクt47'のために新たにグループG6を作成して、グループG6にタスクt47'を加えて、グループG6をグループ列に挿入する。挿入が終了すると、グループ列にグループが加えられるまで待機していたプロセス２がグループ列からグループG6を取り出して、グループG6の処理を始めることになる。プロセス３は、グループ列が空になったので、グループ列に新しいグループが加えられるまで待機することになる。
【００４９】
プロセス４で、グループG4内のタスクt61の処理を終了すると、クエリー・プロセッサは、処理ツリーから新たに処理できるタスクを検索する。タスクt61の処理が終了すると、新たに結合演算タスクt64の処理ができるようになり、タスクt64の処理結果に対して処理を行うタスクt65は射影演算であるので、クエリー・プロセッサは、結合演算タスクと射影演算タスクを同時に取り出し、結合演算タスクt64と射影演算タスクt65を組み合わせてタスクt65'を作成し、タスクt65'のために、新たにグループG7を作成して、グループG7をグループ列(キュー)に挿入する。挿入が終了すると、グループ列にグループが加えられるまで待機していたプロセス３がグループ列からグループG7を取り出して、グループG7の処理を始めることになる。プロセス４は、グループ列が空になったので、グループ列に新しいグループが加えられるまで待機することになる。
【００５０】
プロセス１が、グループG5内の合成結合演算と合成射影演算を組み合わせたtG5SG1及びサブグループに集まらないタスクt57'の処理を、tG5SG1, t57'の順番で終了すると、クエリー・プロセッサは、これらのタスクが終了することによって、新たに処理できるタスクを処理ツリーから検索する。合成結合演算と合成射影演算を組み合わせたタスクtG5SG1が終了すると、新たに結合演算タスクt18, t28, t38の処理ができるようになる。また、これらのタスクの処理結果に対して処理を行うタスクt19, t29, t39は射影演算であるので、クエリー・プロセッサは、結合演算タスクと射影演算タスクを同時に取り出し、結合演算タスクt18, t28, t38と射影演算タスクt19, t29, t39をそれぞれ組み合わせてタスクt19', t29', t39' を作成し、タスクt19', t29', t39'のために、新たにグループG8を作成し、グループG8にこれらのタスクを加えて、グループG8をグループ列に挿入する。
【００５１】
挿入が終了すると、グループ列にグループが加えられるまで待機していたプロセス4は、グループ列からグループG8を取り出してグループG8の処理を始める。同様に、グループG5のタスクt57'の処理が終了すると、新たに結合演算タスクt58の処理ができるようになり、タスクt58の処理結果に対して処理を行うタスクt59は射影演算であるので、クエリー・プロセッサは、結合演算タスクと射影演算タスクを同時に取り出し、結合演算タスクt58と射影演算タスクt59を組み合わせてタスクt59'を作成し、グループG9にタスクt59'を加えて、グループG9をグループ列に挿入する。挿入が終了すると、プロセス１以外のすべてのプロセスは、他のグループの処理を行っているので、続けてプロセス１がグループ列からグループG9を取り出して、グループG9の処理を始めることになる。
【００５２】
このようにして、それぞれのプロセスがグループの処理を終了するにつれて、次々にグループ列(1005)から、作成されたグループを取り出して、グループのタスク処理を行うことになり、マルチオペレーションプロセッサ(1006)は、グループの処理を繰り返して行っていくうちに、処理ツリー(1002) 内のタスクが次第に終了に近づき、処理ツリー内すべてのタスク処理が終了すると、与えられたすべてのクエリー処理は終了したことになる。
【００５３】
また、クエリー・プロセッサ(1001)が現在クエリーの処理(Q1からQ6までのクエリー)を行っている最中に、ユーザからの新たな問い合わせのクエリーQ7 (1009) があった場合には、クエリー・プロセッサは、クエリーオプティマイザを用いて新しいクエリーQ7に対する最適化を行って処理ツリーP7を作成し、処理ツリーP7からトポロジカルソートの順番で、処理できるタスクを見出し、それらのタスクがアクセスするリレーションと同一のリレーションをアクセスするタスクを集めたグループがグループ列に存在するかどうかを調べる。そのようなグループが既存のグループの中に存在するならば、そのグループにタスクを加えることになり、既存のグループに存在しない場合には、新たにグループを作成してそのグループにタスクを加えることにする。さらに、問い合わせのクエリーの数が増えると、プロセスがグループの処理を行っている間に、グループ列にいくつかのグループが待機するようになり、その間に数多くのタスクがグループに集められ、グループに集められたタスクが、さらにサブグループに集められて、数多くのタスク処理が一度に行われるようになる。このようにしてクエリーの処理を行うデータベースシステムは、数多くのクエリー効率よく高速に行っていくものである。
【００５４】
[結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理システムのフローチャート]
図２は、図１に示したアーキテクチャで、合成関係演算を利用したマルチオペレーション・プロセッシングを適用して、クエリーが処理される一連の流れを説明するためのフローチャートである。このフローチャートで行われる基本的な処理の流れは、特願２００６−３５６４０６号及び特願２００７−０７５６７０号と同様である。
【００５５】
図２のフローチャートにおいて、まず、SQLなどのリレーショナルデータベースの言語を使用して、ユーザからデータベースサーバーにクエリーの問い合わせがある（Ｓ１１００）。問い合わせのあったSQLの構文は、クエリーオプティマイザ1000によって関係演算で構成された処理ツリーに変換される（Ｓ１１０２）。
クエリー・プロセッサ1001は、トポロジカルソートの順番で、直接的に処理することのできるタスクを見つける（Ｓ１１０４）。
直接的に処理することのできるタスクを見つけると、これらのタスクの処理結果に対して処理を行う次のタスクが射影演算であるならば、［改善方法１］を適用して、直接的に処理できるタスクと射影演算タスクの両方を取り出し、射影演算タスクに直接的に処理することができるタスクをそれぞれ組み合わせて関係演算を組み合わせたタスクを作成する。（Ｓ１１０６）
【００５６】
次に、関係演算を組み合わせたタスク、及び直接的に処理できるタスクがアクセスするリレーションと同一のリレーションをアクセスするタスクが集められたグループがグループ列に存在するかどうかを調べる（Ｓ１１０８）。
同一のリレーションをアクセスするタスクが集められたグループがグループ列に存在しているならば、そのグループにタスクを加えることになる（Ｓ１１１２）。そうではない場合は、タスクのために新たにグループを作成し、そのグループにタスクを加えて、グループをグループ列に挿入する（Ｓ１１１０）。
【００５７】
グループにタスクを集めると、共通部分式を持つタスクはさらにサブグループに集める（Ｓ１１１６）。サブグループにタスクを集められると、サブグループに対してサブグループ内のタスクをもとに、［改善方法２］，［改善方法３］を適用して、合成関係演算タスク及び／又は合成関係演算を組み合わせたタスクを作成する（Ｓ１１１８）。
マルチオペレーション・プロセッサは、利用できるプロセスの数だけグループ列からグループを取り出し、[改善方法４]を適用して、マルチオペレーション・プロセッシングを用いて、グループ内の合成関係演算タスク及び／又は合成関係演算を組み合わせたタスク、その他サブグループに集まらないタスクの処理を一度に行うものとする（Ｓ１１２０）。
【００５８】
グループ内の合成関係演算タスク及び／又は合成関係演算を組み合わせたタスクを処理すると、[改善方法２]，[改善方法３]を適用して、サブグループ内のタスクに対して仮想リレーションを作成し、合成関係演算タスクの処理結果のリレーション及び／又は合成関係演算タスクを組み合わせたタスクの処理結果のリレーションを部分的に共有できるようにする（Ｓ１１２２）。 
グループ内のタスクの処理が終了すると、処理ツリー内のすべてのタスクが終了したかどうかを調べる（Ｓ１１２４）。処理ツリー内にまだタスクが残っている場合は、繰り返して次に処理できるタスクを処理ツリーから見出していく。
処理ツリー内のすべてのタスク処理が終了するとその処理ツリーに対応したクエリーの処理が終了することになる。
【００５９】
＜各改善方法の詳細な説明＞
上述した４つの改善方法について、以下で詳細に説明する。
［１．結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシング］
合成関係演算を利用したマルチオペレーション・プロセッシングは、ユーザから問い合わせのあったクエリーがクエリーの最適化によって、関係代数で構成された処理ツリーに変換される（Ｓ１１０２）と、処理ツリー上の接点であるタスクをトポロジカルソートの順番で、他のタスクから依存がなく、直接的に処理できるタスクを関係演算タスク、関係演算を組み合わせたタスクとして取り出す（Ｓ１１０４，Ｓ１１０６）。
次に、これらのタスクを、それぞれのタスクがアクセスするデータベースのリレーションをもとにグループ分けを行い（Ｓ１１０８〜Ｓ１１１２）、さらにグループ内のタスクを共通部分式ごとにサブグループに集めて（Ｓ１１１６）、それぞれのサブグループに対して、サブグループ内のタスクをもとにして合成関係演算を組み合わせたタスク、合成関係演算タスクを作成する（Ｓ１１１８）。その後、マルチオペレーション・プロセッシングを使用して合成関係演算タスク、合成関係演算を組み合わせたタスク、サブグループに集まらないタスクの処理を一度に行うものである（Ｓ１１２０）。
【００６０】
[１−１．関係演算を組み合わせたタスクの取り出し方法]
改善方法１である関係演算を組み合わせたタスクの取り出し方法（Ｓ１１０６）を、以下で詳細に説明する。
処理ツリーからトポロジカルソートの順番で直接的に処理できるタスクをアクセスするリレーションRをもとにグループに集めていくにあたって、グループに加えるタスクが次のように
TEMP_T1 ← σ<selection condition>R 
で表わされる選択演算のタスクであり、タスクの処理結果TEMP_T1に対して処理を行うタスクが次のように
TEMP_T2 ← π<attribute list> TEMP_T1 
で表わされる射影演算である場合がある。この場合は、選択演算タスクと射影演算タスクを同時に取り出し、選択演算タスクと射影演算タスクを次のように組み合わせて、
TEMP_T2 ← π<attribute list>(σ< selection condition >R) 
として表わせる関係演算を組み合わせたタスクを作成してグループに加えていく。ここで、σは選択演算を表わし、πは射影演算を表している。
同様に、結合演算タスクと射影演算タスクでも組み合わせたタスクを作成する。即ち、処理ツリーから直接的に処理できるタスクをアクセスするリレーションSをもとにグループに集めていくにあたって、グループに加えるタスクが。次のように
TEMP_T3 ← R|X|<join condition> S
で表わされる結合演算タスクであり、タスクの処理結果TEMP_T3に対して処理を行うタスクが次のように
TEMP_T4 ← π<attribute list> TEMP_T3 
として表わされる射影演算である場合である。この場合も、結合演算タスクと射影演算タスクを同時に取り出し、結合演算タスクと射影演算のタスクを次のように組み合わせて、
TEMP_T4 ← π<attribute list>(R|X|<join condition>S)
で表わせる関係演算を組み合わせたタスクを作成して、グループに加えていく。ここで、|X|は結合演算を表わしている。
【００６１】
［１−２．結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングのアルゴリズム］
次に、改善方法２である合成結合演算タスクの処理方法、改善方法３である合成関係演算を組み合わせたタスクの処理方法を新たに加えた合成関係演算を利用したマルチオペレーション・プロセッシングのアルゴリズムをステップ１からステップ３に分けてさらに説明する。ここで説明するアルゴリズムは、本発明者が出願した特許２００６−３５６４０６号で述べてアルゴリズムに、新たに合成結合演算タスクの処理方法、合成関係演算を組み合わせたタスク処理方法を新たに加えたものであり、これらのタスクに重点を置いて説明する。
【００６２】
[(a）ステップ１：タスクのサブグループ化］
共通のリレーションRに対してグループ内のタスクの処理を行うに当たって、次のようにタスク間の共通部分式に関する定義を定めて、グループ内のタスクを共通部分式ごとにサブグループに集める（Ｓ１１１６）。ここで述べる共通部分式において、結合演算の共通部分式の定義は本発明で新たに加えた共通部分式の定義である。それ以外の共通部分式の定義(選択演算、射影演算、その他の関係演算)は基本的に、本発明者が出願した特願２００６−３５６４０６号で述べた定義と同様のものである。
【００６３】
・共通部分式に関する定義：
次に示す選択演算、射影演算、結合演算、及びその他の演算に関する条件を満たすならば、タスクtiとタスクtjは共通部分式をもっている。
・選択演算：
タスクtiは、リレーションRに対して属性A1,A2,A3,…,Akに関する選択条件(AND，ORで結合したもの)を使用する選択演算タスクであり、タスクtjは、同一のリレーションRに対して同一の属性A1,A2,A3,…,Akに関する選択条件(AND，ORで結合したもの)を使用する選択演算タスクであるときに、タスクtiとタスクtjが使用する選択条件において、１つの属性Ai(1≦i≦k)に関する選択条件だけは異なった条件かまたは同じ条件であり、Ai以外の属性に関する選択条件はまったく同じ条件である。
【００６４】
・射影演算：
タスクtiは、リレーションRに対する射影演算タスクであり、タスクtjは、同一のリレーションRに対する射影演算タスクである。
・結合演算：
タスクtiは、Ri|X|<join condition i> Siで表わされる結合演算タスクであり、タスクtjは、Rj|X|<join condition j> Sjで表わされる結合演算タスクであり、リレーションRiとリレーションRjは等しく(Ri≡Rj)、リレーションSiとリレーションSjはリレーションSのサブセットである場合、または、リレーションSiとリレーションSjは等しく(Si≡Sj)、リレーションRiとリレーションRjは、リレーションRのサブセットである場合において、結合条件<join condition i>と結合条件<join condition j>が同一の属性を用いて結合処理を行うときは、共通部分式をもつことになる。
・その他の関係演算：
tiとtjは、同一の関係演算タスク（ti≡tj)である。
【００６５】
以上の定義の条件に用いた演算は、あくまでも共通部分式に関するものである。
次に、グループ内の選択演算と射影演算を組み合わせたタスクは、タスクに含まれる選択演算をもとにしてサブグループに集める。またグループ内の結合演算と射影演算を組み合わせたタスクは、タスクに含まれる結合演算をもとにしてサブグループに集める。
【００６６】
［（b）ステップ２：合成関係演算タスク及び合成関係演算を組み合わせたタスクの作成］
ステップ１によってグループ内のタスクを共通部分式ごとにサブグループに集めると、サブグループ内のタスクの演算の種類に応じて、下記の方法を使用して、グループ内の各サブグループに対して、合成関係演算タスクと合成関係演算を組み合わせたタスクを作成する（Ｓ１１１６）。
結合演算の共通部分式を新たに加えたことによって、改善方法２で取り上げた合成結合演算タスクは次にように作成されることになる。
【００６７】
[(b-1) 合成結合演算タスクの作成方法]
サブグループ内に結合演算の共通部分式をもつ複数の結合演算タスクとして、
TEMP_T1 ← R1|X|<join condition 1>S1 
TEMP_T2 ← R2|X|<join condition 2>S2
TEMP_T3 ← R3|X|<join condition 3> S3
…
TEMP_Tn ← Rn|X|<join condition n> Sn
が存在するときに、これらの結合演算タスクの論理和を求めて組み合わせ、サブグループ内すべての結合演算タスクの結合条件を満たす合成結合演算タスクとして、
TEMP_SG ←(R1|X|<join condition 1>S1)∪(R2|X|<join condition 2>S2)∪
(R3|X|<join condition 3>S3)∪…∪(Rn|X|<join condition n>Sn)
を作成する。個々の結合演算タスクは、結合演算の共通部分式の定義に従うものである。ここで、TEMP_Ti ← Ri|X|<join condition i> Siは、リレーションRi,Siに対して、結合条件<join condition i>にしたがって結合(|X|)する結合演算タスクを表し、その処理結果をTEMP_Tiに記録するものとする。    
次に、サブグループに集められた複数の関係演算を組み合わせたタスクから、改善方法３で取り上げた合成関係演算を組み合わせたタスクは次のように作成される。
【００６８】
[(b-2) 合成選択演算と合成射影演算を組み合わせたタスク作成方法]
サブグループに選択演算と射影演算を組み合わせた（関係演算を組み合わせた）タスクとして、
TEMP_T1 ← π<attribute list 1>(σ<selection condition 1>R) 
TEMP_T2 ← π<attribute list 2>(σ<selection condition 2>R) 
TEMP_T3 ← π<attribute list 3>(σ<selection condition 3>R)
…
TEMP_Tn ← π<attribute list n>(σ<selection condition n>R)
が存在するときに、これらのタスクの選択演算に使用されている選択条件<selection condition i>(i = 1,2,…,n)をブール演算のＯＲを使用して接続し、さらに接続した選択条件から選択範囲が重複した部分を取り除くために、最適化optimize(…)を行って、次のようにサブグループ内すべてのタスクの選択条件を満たす合成選択演算を作成する。
σoptimize(<selection condition 1> OR <selection condition 2> OR <selection condition 3> …OR <selection condition n>)R
次に、サブグループ内の個々のタスクに含まれる射影演算に使用されている属性のリスト<attribute list i>(i = 1, 2,…,n) から属性の和集合を求め、得られた和集合に含まれる属性を用いて、属性のリスト<attribute list SG>を作成し、サブグループ内のすべてのタスクに含まれる射影演算を含んだ合成射影演算を次のように作成する。
π<attribute list SG>(…)
このようにして、作成した合成選択演算と合成射影演算を組み合わせて、サブグループ内のすべての選択演算タスクに含まれる選択条件を満たして、射影演算のすべての属性を含んだ１つの合成選択演算と合成射影演算を組み合わせたタスクを次のように作成する。
TEMP_SG  ←  π<attribute list SG > (σoptimize(<selection conditon 1> OR <selection condition 2> OR <selection condition 3>… OR <selection condition n>)R)
【００６９】
[(b-3) 合成結合演算と合成射影演算を組み合わせたタスク作成方法]
サブグループに結合演算と射影演算を組み合わせた(関係演算を組み合わせた)タスクとして、
TEMP_T1 ← π<attribute list 1>(R1|X|<join condition 1> S1) 
TEMP_T2 ← π<attribute list 2>(R2|X|<join condition 2> S2) 
TEMP_T3 ← π<attribute list 3>(R3|X|<join condition 3> S3)
…
TEMP_Tn ← π<attribute list n>(Rn|X|<join condition n> Sn)
が存在するときに、これらのタスクに含まれる結合演算Ri|X|<join condition i>Si  (i=1,2,…,n)を、論理和を用いて組み合わせ、サブグループ内すべての結合演算タスクの結合条件を満たす合成結合演算を次のように作成する。
(R1|X|<join condition 1>S1)∪(R2|X|<join condition 2>S2)∪
(R3|X|<join condition 3>S3) … ∪(Rn|X|<join condition n>Sn)
【００７０】
次にサブグループ内の個々のタスクに含まれる射影演算に使われている属性のリスト<attribute list i>(i = 1, 2,…,n) から属性の和集合を求めて、サブグループ内すべてのタスクの射影演算の属性を含んだ１つの合成射影演算を次のように作成する。
π<attribute list SG>(…)
このようにして、作成した合成結合演算と合成射影演算を組み合わせて、サブグループ内すべての結合演算タスクに含まれる結合条件を満たし、射影演算すべての属性を含んだ１つの合成結合演算と合成射影演算を組み合わせたタスクを次にように作成する。
TEMP_SG ← π<attribute list SG>((R1|X|<join condition 1> S1)∪
(R2|X|<join condition 2> S2)∪ (R3|X|<join condition 3> S3)…
∪(Rn|X|<join condition n>Sn)) 
【００７１】
［（ｃ）ステップ３：マルチオペレーション・プロセッシングを用いたグループ内のタスク処理］
ステップ２を用いてグループ内の各サブグループに関して作成された合成結合演算タスクと合成関係演算を組み合わせたタスクに対して、マルチオペレーション・プロセッシングを使用して処理を行う。
このマルチオペレーション・プロセッシングとして、本願の発明者は、ダイナミックマルチオペレーション・プロセッシングとスタティックマルチオペレーション・プロセッシングの２つの処理方法を提案してきた（特願２００６−３５６４０６号参照）が、今回は、スタティック・マルチオペレーション・プロセッシングをマルチオペレーション・プロセッシングとして用いて処理を行っていくことにする。
スタティック・マルチオペレーション・プロセッシングを使って処理を行う場合は、グループ内の合成関係演算タスク、合成関係演算を組み合わせたタスク、及びサブグループに集まらないタスクに対してアクセスプランを作成し、アクセスプランから各タスクの処理コストをもとめ、処理コストの小さいタスクから処理コストの大きいタスクへと順番に処理するために、アクセスするブロックの順位を決定し、その順位にしたがってリレーション内のブロックをアクセスし、このブロックを共通ブロックとして、このブロック上で処理を行う必要のあるグループ内のタスク処理を一度に処理していくことになる。
マルチオペレーション・プロセッシングを用いてグループ内の合成結合演算タスクの処理を行う場合には、次にような合成結合演算の処理を行うための特有の手順を用いて処理を行うことになる。
【００７２】
［（ｃ−１）合成結合演算タスクの処理方法］
前述した合成結合演算タスクの作成方法によって、合成結合演算タスクが次のように作成される。
TEMP_SG ←(R1|X|<join condition 1>S1)∪(R2|X|<join condition 2>S2)∪
(R3 |X|<join condition 3>S3)∪…∪ (Rn|X|<join condition n>Sn)
ここで、仮想リレーションS1,S2,S3,…,SnはリレーションSを部分的に共有するサブセットであり、仮想リレーションR1,R2,R3,…,RnはリレーションRを部分的に共有するサブセットである。
マルチオペレーション・プロセッシングを用いて、作成された合成結合演算タスクの処理を行う場合の合成結合演算タスクの処理方法は、合成結合演算タスクに含まれるいくつもの結合演算(Ri|X|<join condition i>Si)(i=1,2,…,n)の処理を別々に行って、それぞれの結合演算の処理結果を和集合∪を用いて１つの合成結合演算タスクの処理を行い、その処理結果をTEMP_SGに集めるのではなく、以下に示すような方法を用いる。
【００７３】
最初に、仮想リレーションS1,S2,S3,…,Snが検索元のリレーションSに対して共有するブロックを調べて、それらのブロックを集めた集合をそれぞれブロック集合B1,B2,…,Bnとする。言い換えると、仮想リレーションS1,S2,S3,…,Snに対して、それに対応するブロック集合として、Bi={リレーションSを構成するブロックb1, b2,…, bmに対してリレーションSiが共有するブロックの集合}(i = 1, 2,…, n)となる集合を見出す。このように見出したブロック集合B1, B2,…,Bnからブロックの和集合B1∪B2∪B3∪…∪Bnをもとめて、合成結合演算タスクに対応するブロック集合BSGを作成する。      
ブロック集合BSGを作成すると、ブロック集合のブロックbi(i = 1,2,…,k, k ≦ m)にアクセスし、ブロックbiからレコードsを取り出して、合成結合演算の結合条件<join condition i>(i=1,2,…,n)を満たすレコードrを検索先のリレーションRに対して検索する(R|X|<join condition i>Sの結合関係を満たすレコードを検索する)。レコードrが検索されると、合成結合演算タスクに含まれる少なくとも１つの結合演算(Ri|X|<join condition i>Si) (1≦i≦n)が、結合演算に使用する検索先の仮想リレーションRi(1≦i≦n)にレコードrを含んでいて、結合演算に使用する検索元の仮想リレーションSi(1≦i≦n)にレコードsを含んでいるならば(Ri|X|<join condition i>Siの結合関係を満たしているならば)、レコードrとレコードsを結合してレコードtを作成し、レコードtを合成結合演算タスクの処理結果TEMP_SGに加える。続けて、ブロックbi内の残りのレコードに対しても同じように処理を行い、ブロックbiでのすべてのレコードに対して処理が終了すると、ブロック集合BSG内の残りのブロックに対しても、ブロックbiで行った処理を同様に繰り返して行うことにする。
【００７４】
合成結合演算タスクの処理を行うに当たって、仮想リレーションRi(1≦i≦n)にレコードrが含まれているかどうかを調べるには、レコードrの相対アドレスが、リレーションRに対して仮想リレーションRi(1≦i≦n)が共有するレコードの相対アドレスの範囲内であるかどうかで判断することになる。同様に、仮想リレーションSi(1≦i≦n)にレコードsが含まれているかどうかを調べるには、レコードsの相対アドレスが、リレーションSに対して仮想リレーションSi(1≦i≦n)が共有するレコードの相対アドレスの範囲内であるかどうかで判断することになる。レコードの相対アドレスとは、レコードのリレーション上の相対アドレスであり、リレーションの最初の位置をゼロとしたときに、そこから何バイト移動したところにレコードが格納してあるかを表したものである。
【００７５】
このようにして、合成結合演算タスクの処理を行うことによって、合成結合演算タスクに含まれる個々の結合演算(Ri|X|<join condition i>Si) (i = 1, 2,…,n)を別々に処理する必要はなく、仮想リレーションSi(i = 1, 2,…,n)が共有するリレーションS内のブロックを一度しかアクセスせず、仮想リレーションRi(i=1,2,…n)が共有するリレーションR内のレコードは一度しか検索しないことになる。また、合成結合演算タスクはグループ内の他のタスクと一緒に処理されることになるので、ブロック集合BSG内のブロックをアクセスする順番はマルチオペレーション・プロセッシングによって決定されることになる。 以上のような、合成結合演算タスクの処理方法にもとづいて、合成結合演算タスクの処理を行うことによって、合成結合演算タスクに含まれる個々の結合演算(Ri|X|<join condition i>Si) (i = 1, 2,…,n)の処理を別々に行う必要がなくなり、ディスクのブロックをアクセスする回数を減少させてクエリーの処理速度を向上させることが可能になる。
【００７６】
［（ｃ−２）合成選択演算と合成射影演算を組み合わせたタスクの処理方法］
マルチオペレーション・プロセッシングを用いて、グループ内の合成選択演算と合成射影演算を組み合わせたタスクの処理を行うには、合成選択演算と合成射影演算の処理を一度に行うことになり、合成選択演算の処理を行った個々のレコードに対して、合成射影演算の処理を行って、合成選択演算と合成射影演算を組み合わせたタスクの処理結果に直接加えていくものとする。
【００７７】
［（ｃ−３）合成結合演算と合成射影演算を組み合わせたタスクの処理方法］
マルチオペレーション・プロセッシングを用いて、グループ内の合成結合演算と合成射影演算を組み合わせたタスクの処理を行うには、合成結合演算と合成射影演算の処理を一度に行うことになり、合成結合演算の処理を行った個々のレコードに対して、合成射影演算の処理を行って、合成結合演算と合成射影演算を組み合わせたタスクの処理結果に直接加えていくものとする。
【００７８】
［（ｄ）仮想リレーション］
［（ｄ−１）合成結合演算タスクの処理結果を共有する仮想リレーション］
合成関係演算を利用したマルチオペレーション・プロセッシングによって得られた合成結合演算タスクの処理結果は、サブグループ内すべての結合演算タスクの処理結果を含んでいるので、サブグループ内の結合演算タスクは、合成結合演算タスクの処理結果のリレーションを部分的に共有することになる。そのため合成結合演算タスクの処理結果は、合成結合演算に使用した検索先のリレーション又は検索元のリレーション内のレコードを整列している属性と同じ属性で整列され、サブグループ内の個々の結合演算タスクに対して、それぞれのタスクの処理結果を示す仮想リレーションを作成し、その仮想リレーションに、仮想リレーションが部分的に共有する合成結合演算タスクの処理結果のリレーション名、その処理結果を共有するレコードの格納位置(レコードの行範囲、レコードが格納してあるブロックの番号とアドレス)などの情報を記録しておく。
【００７９】
［（ｄ−２）合成選択演算と合成射影演算を組み合わせたタスクの処理結果を共有する仮想リレーション］
合成関係演算を利用したマルチオペレーション・プロセッシングによって得られた合成選択演算と合成射影演算を組み合わせたタスクの処理結果は、サブグループ内すべての選択演算と射影演算を組み合わせたタスクの処理結果を含んでいるので、サブグループ内のタスクは、合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーションを部分的に共有することになる。そのため合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーションは、そのタスクに含まれる合成選択演算の選択条件に使用された属性で整列し、サブグループ内の個々の選択演算と射影演算を組み合わせたタスクに対して、それぞれのタスクの処理結果を示す仮想リレーションを作成し、その仮想リレーションに、仮想リレーションが部分的に共有する合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーション名、その処理結果を共有するレコードの格納位置(レコードの行範囲、レコードが格納してあるブロックの番号とアドレスと属性の格納位置(属性の列番号)などの情報を記録しておく。
【００８０】
［（ｄ−３）合成結合演算と合成射影演算を組み合わせたタスクの処理結果を共有する仮想リレーション］
合成関係演算を利用したマルチオペレーション・プロセッシングによって得られた合成結合演算と合成射影演算を組み合わせたタスクの処理結果は、サブグループ内すべての結合演算と射影演算を組み合わせたタスクの処理結果を含んでいるので、サブグループ内のタスクは、合成結合演算と合成射影演算を組み合わせたタスクの処理結果のリレーションを部分的に共有することになる。そのため合成結合演算と合成射影演算を組み合わせたタスクの処理結果のリレーションは、タスクに含まれる合成結合演算に使用された検索先のリレーション又は検索元のリレーション内のレコードを整列している属性と同じ属性で整列し、サブグループ内の個々の結合演算と射影演算を組み合わせたタスクに対して、それぞれタスクの処理結果を示す仮想リレーションを作成し、その仮想リレーションに、仮想リレーションが部分的に共有する合成結合演算と合成射影演算を組み合わせたタスクの処理結果のリレーション名、その処理結果を共有するレコードの格納位置(レコードの行範囲、レコードが格納してあるブロックの番号とアドレス)と属性の格納位置(属性の列番号)などの情報を記録しておく。
以上のように仮想リレーションを作成すると、サブグループ内の関係演算を組み合わせたタスクは、合成関係演算を組み合わせたタスクの処理結果のリレーションを部分的に共
有していることを明記することができ、このことによって、サブグループ内の個々の関係演算を組み合わせたタスクに対して、レコードの選択範囲、結合範囲、属性(列)の重なっている処理結果のリレーションをディスク上に別々に作成する必要がなくなり、ディスクをアクセスする回数を減らし、クエリーに処理速度を向上させることが可能になる。
【００８１】
［(ｅ) マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法］
改善手段４のマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法とは、グループ内の複数の結合演算タスクの処理を行うに当たって、グループ内の個々の結合演算タスクは、結合演算に同一の属性を用いて、検索元の仮想リレーションと検索先の仮想リレーションに対して結合演算の処理を行うタスクであり、結合演算の検索元に使用する仮想リレーションは１つの共通の検索元のリレーション属し、結合演算の検索先に使用する仮想リレーションは１つの共通の検索先のリレーションに属しているならば、個々の結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行う方法である。
【００８２】
グループ内に、次のような複数の結合演算タスクが集められたとする。
(t1): TEMP_T1 ← R1|X|<join condition 1>S1,
(t2): TEMP_T2 ← R2|X|<join condition 2>S2,
(t3): TEMP_T3 ← R3|X|<join condition 3>S3,
…,
(tn): TEMP_Tn ← Rn|X|<join condition n>Sn
【００８３】
結合演算タスクt1, t2, t3,…,tnは、使用される結合条件<join condition 1>,<join condition 2>,<join condition 3>,…,<join condition n>が同一の属性を持つものとして、仮想リレーションR1,R2,R3,…,Rnと仮想リレーションS1,S2,S3,…,Snに対して結合演算の処理を行うタスクである。また、結合演算タスクt1, t2, t3,…,tnが使用する仮想リレーションS1, S2, S3,…,Snは、リレーションS内のレコード及び属性(列)を部分的に共有し、仮想リレーションR1, R2, R3,…,RnはリレーションR内のレコード及び属性(列)を部分的に共有するものとする。マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法は、次のような手順を用いてグループ内のこれらの結合演算タスクt1, t2, t3,…,tnの処理を行うことになる。
【００８４】
最初に、グループ内の結合演算タスクt1, t2, t3,…,tnに対してアクセスプランを作成する。次に求めたアクセスプランをもとにして各タスクの処理コストを求めて、グループ内の結合演算タスクを処理コストの小さい順番から並び替える。次に仮想リレーションS1, S2,S3,..Snに記録してある情報(仮想リレーションS1,S2,S3,…,SnがリレーションSを共有するレコードの格納位置、属性の格納位置、レコードが格納してあるブロックの番号とアドレスなどの情報)をもとにして、結合演算タスクt1, t2, t3,…,tnがリレーションSに対してアクセスするブロックを調べて、それぞれのタスクに対応するブロック集合B1,B2,B3,…,Bnを作成する。ブロック集合B1,B2,B3,…,Bnを作成すると、前に求めた処理コストの小さいタスクから処理コストの大きいタスクまでの順番にしたがって、ブロック集合B1,B2,B3,…,Bnの和集合を求めて、リレーションSに対してアクセスするブロックの順位を決定する。
【００８５】
次に、ブロックをアクセスする順位にしたがって、ブロックb1,b2,b3,…,bmからなるリレーションＳ内のブロックbk(1≦k≦m)を共通ブロックとしてメインメモリに読み込み、共通ブロックbkからレコードsを取り出し、レコードsと結合条件<join condition i>(i=1,2,3,…,n)を満たすレコードrをリレーションRに対して検索する(R|X|<join condition i>Sの結合関係を満たすレコードを検索する)。レコードrが検索されると、検索されたレコードrと共通ブロックから取り出したレコードsを結合してレコードtを作成し、共通ブロックbkで処理を行う必要のあるグループ内の最初の結合演算タスクti(1≦i≦n)が、タスクtiの結合演算に使用する検索先のリレーションRiにレコードrを含んでいて、検索元に使用するリレーションSiにレコードsを含んでいるならば(Ri|X|<join condition i> Siの結合関係を満たしているならば)、結合されたレコードtをタスクtiの処理結果TEMP_Ti(1≦i≦n)に加えるものとする。
【００８６】
次に、共通ブロックbkで処理を行う必要のあるグループ内の次の結合演算タスクtj(1≦j≦n)が、結合演算に使用する検索先のリレーションRjにレコードrを含んでいて、検索元に使用するリレーションSjにレコードsを含んでいるならば(Rj|X|<join condition j> Sjの結合関係を満たしているならば)、すでに結合されたレコードtを利用して、レコードtをタスクtjの処理結果TEMP_Tj(1≦j≦n)に加える。同様に、共通ブロックbkで処理を行う必要があるグループ内の残りの結合演算タスクに対しても、同じようにして結合演算の処理を行っていくものとする。
共通ブロックbkから最初に取り出されたレコードsに対して、グループ内すべての結合演算タスクの処理が行われると、共通ブロックbkから次々とレコードを取り出して、それぞれのレコードに対して、以上に述べた結合演算のタスク処理を繰りかえてして行うものとする。
【００８７】
このようにして、共通の検索先のリレーションに対して検索されたレコードと検索元のリレーションの共通ブロックから取り出されたレコード及びそれらのレコードを結合したレコードをグループ内の個々の結合演算タスクごとに利用し、個々の結合演算タスクの処理のために、レコードの検索処理とレコードの結合処理を別々に行うことなしに、クエリーの処理速度を向上させることがマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法である。
【００８８】
［２．結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングの具体例］
ここでは、上述で説明した合成関係演算を利用したマルチオペレーション・プロセッシングを、図３−１〜図３−４に示したデータ構造を有するデータベースに対するクエリーQ1〜Q5の例を用いて説明する。
【００８９】
［２−１．リレーションとクエリー（問い合わせ）処理］
［（ａ）リレーションの例］
図３−１〜図３−４は、リレーションEMPLOYEE, DEPARTMENT, PROJECT, WORKS_ONから構成されているデータベースである。
図３−１において、リレーションEMPLOYEEには、20件のレコードが５つのブロックに格納してあり、それぞれのブロックには4件レコードが存在しており、各ブロックは次のブロックに対してブロックポインターを持っている。リレーションEMPLOYEEの主属性SSNには、主インデックス(100)が存在し、主インデックスは各ブロックに対してインデックスのポインターを持っている。リレーションEMPLOYEEの属性PHONEには、2次インデックス(102)が存在し、2次インデックスはリレーションEMPLOYEE内の各レコードに対してインデックスポインターを持っている。
【００９０】
図３−２において、リレーションDEPARTMENTには、25件のレコードが５つのブロックに格納してあり、それぞれのブロックには5件のレコードが存在しており、各ブロックは次のブロックに対してブロックポインターを持っている。リレーションDEPARTMENTの主属性DNUMBERには、主インデックス(103)が存在し、主インデックスは、各ブロックに対してインデックスポインターを持っている。リレーションDEPARTMENTの属性DPHONEには、2次インデックス(105)が存在し、２次インデックスはリレーションDEPARTMENT内の各レコードに対してインデックスポインターを持っている。
【００９１】
図３−３において、リレーションPROJECTには、25件のレコードが５つのブロックに格納してあり、それぞれのブロックには5件レコードが存在しており、各ブロックは、次のブロックに対してブロックポインターを持っている。リレーションPROJECTの主属性PNUMBERには、主インデックス(201)が存在し、主インデックスは、各ブロックに対してインデックスのポインターを持っている。リレーションPROJECTの属性PNAMEには、2次インデックス(203)が存在し、２次インデックスはリレーションPROJECT内の各レコードに対してインデックスポインターを持っている。
図３−４において、リレーションWORKS_ONには、25件のレコードが5つのブロックに格納してあり、それぞれのブロックには5件のレコードが存在する。各ブロックは、次のブロックに対してブロックポインターを持っている。リレーションWORKS_ONの主属性ESSN, PNOは、リレーションEMPLOYEE, PROJECTに対する外部キーである。
【００９２】
以上をまとめると次のような表になる。
【表１】
2008276464.tif 000003
【００９３】
次に、図３−１〜図３−４のデータベースをもとにして合成関係演算を利用したマルチオペレーション・プロセッシングを具体的に説明するために、下記に示すような６つクエリーQ1, Q2, Q3, Q4, Q5, Q6処理を取り上げることにする。それぞれのクエリーQ1, Q2, Q3, Q4, Q5, Q6は次のような問い合わせであったとする。
【００９４】
(Q1) SELECT  FNAME, LNAME, BDATE, PNUMBER, PNAME
FROM    EMPLOYEE, WORKS_ON, PROJECT
WHERE   PROJECT.PNUMBER > 2 AND PROJECT.PNUMBER < 11 AND 
EMPLOYEE.BDATE > 'DEC-01-1951' AND EMPLOYEE.BDATE < 'DEC-31-1959'              AND PROJECT.PNUMBER = WORKS_ON.PNO AND EMPLOYEE.SSN = WORKS_ON.
ESSN;
【００９５】
(Q2) SELECT FNAME, LNAME, BDATE, PNUMBER, PNAME
FROM   EMPLOYEE, WORKS_ON, PROJECT
WHERE  PROJECT.PNUMBER > 10 AND PROJECT.PNUMBER < 18 AND  EMPLOYEE.BDATE >             'JAN-01-1961' AND EMPLOYEE.BDATE < 'DEC-31-1966' AND PROJECT.
PNUMBER = WORKS_ON.PNO AND EMPLOYEE.SSN = WORKS_ON.ESSN; 
【００９６】
(Q3) SELECT  FNAME, LNAME, BDATE, PNUMBER, PNAME
FROM    EMPLOYEE, WORKS_ON, PROJECT
WHERE   PROJECT.PNUMBER > 7 AND PROJECT.PNUMBER < 13 AND  EMPLOYEE.BDATE                 > 'JAN-01-1966' AND PROJECT.PNUMBER = WORKS_ON.PNO AND EMPLOYEE.                SSN = WORKS_ON.ESSN;
【００９７】
(Q4)  SELECT  FNAME, LNAME, PHONE, HOURS, PNUMBER, PNAME
FROM    EMPLOYEE, WORKS_ON, PROJECT
WHERE   EMPLOYEE.PHONE = 21-3728 AND PROJECT.PNAME = 'ProjectO' AND WORKS_
ON.HOURS > 24 AND PROJECT.PNUMBER = WORKS_ON.PNO AND EMPLOYEE.SSN               = WORKS_ON.ESSN;
【００９８】
(Q5) SELECT SSN, FNAME, LNAME, PNUMBER, PNAME
FROM   EMPLOYEE, WORKS_ON, PROJECT
WHERE  EMPLOYEE.SSN > 2311111131 AND EMPLOYEE.SSN < 2834567894 AND PROJECT             .PLOCATION = 'New York' AND PROJECT.PNUMBER = WORKS_ON.PNO AND
EMPLOYEE.SSN = WORKS_ON.ESSN;
【００９９】
(Q6) SELECT  SSN, FNAME, LNAME, DNUMBER, DNAME
FROM    EMPLOYEE, DEPARTMENT
WHERE   EMPLOYEE.SSN > 2611111134 AND DEPARTMENT.DNUMBER = EMPLOYEE.DNUM;
【０１００】
［２−２．処理プランの作成］
クエリー・プロセッサは、問い合わせのあった各クエリーQ1, Q2, Q3, Q4, Q5, Q6に対して、クエリーの最適化を行い、各クエリーを処理していくための最良な処理方法である下記の処理プランを作成していく。すると、次のように各クエリーQi (i = 1, 2,…,6) に対して、処理プランPi (i = 1, 2,…,6)を作成することができる。作成した処理プランを処理ツリーで表すと、図４−１〜図４−３に示したようにP1〜P6となる。
処理ツリーPi内のタスクtij(iは処理ツリーの番号、jはそれぞれの処理ツリー内の処理番号を表わしている)は、以下に示すように、
(tij):  処理結果 ← 関係代数  
として表し、処理結果は関係代数を処理した結果を表すものとする。処理結果名がTEMP_Tj_iの場合は、処理ツリーPi内のタスクtijの中間の処理結果を表し、処理結果がRESULT_Qiの場合は、処理ツリーPi内のタスクtijの最終の処理結果であることを表している。
関係代数は、データベースのリレーションに対して、直接的に処理を行う演算であり、選択演算(σ)、射影演算(π) 、結合演算(|X|)などの演算である。
【０１０１】
処理プランP1 
(t11): TEMP_T1_1  ← σPNUMBER > 2 and PNUMBER < 11 PROJECT
(t12): TEMP_T2_1  ← πPNUMBER,PNAME TEMP_T1_1
(t13): TEMP_T3_1  ← σBDATE>'DEC-01-1951' AND BDATE < 'DEC-31-1959' EMPLOYEE
(t14): TEMP_T4_1  ← πSSN, FNAME,LNAME,BDATE TEMP_T3_1
(t15): TEMP_T5_1  ← πESSN,PNOWORKS_ON
(t16): TEMP_T6_1  ← TEMP_T4_1|X|SSN = ESSNTEMP_T5_1
(t17): TEMP_T7_1  ← πFNAME,LNAME,BDATE,PNOTEMP_T6_1
(t18): TEMP_T8_1  ← TEMP_T2_1|X|PNUMBER=PNOTEMP_T7_1
(t19): RESULT_Q1 ← πFNAME,LNAME,BDATE,PNUMBER,PNAME TEMP_T8_1
【０１０２】
処理プランP2 
(t21): TEMP_T1_2  ← σPNUMBER > 10 AND PNUMBER < 18 PROJECT
(t22): TEMP_T2_2  ← πPNUMBER,PNAME TEMP_T1_2
(t23): TEMP_T3_2  ← σBDATE > 'JAN-01-1961' AND BDATE < 'DEC-31-1966' EMPLOYEE
(t24): TEMP_T4_2  ← πSSN, FNAME, LNAME, BDATE TEMP_T3_2
(t25): TEMP_T5_2  ← πESSN,PNOWORKS_ON
(t26): TEMP_T6_2  ← TEMP_T4_2|X|SSN=ESSN TEMP_T5_2
(t27): TEMP_T7_2  ← πFNAME,LNAME,BDATE,PNOTEMP_T6_2
(t28): TEMP_T8_2  ← TEMP_T2_2|X|PNUMBER= PNOTEMP_T7_2
(t29): RESULT_Q2  ← πFNAME,LNAME,BDATE,PNUMBER,PNAME TEMP_T8_2
【０１０３】
処理プランP3 
(t31): TEMP_T1_3  ← σPNUMBER > 7 AND PNUMBER < 13 PROJECT
(t32): TEMP_T2_3  ← πPNUMBER,PNAME TEMP_T1_3
(t33): TEMP_T3_3  ← σBDATE > 'JAN-01-1966' EMPLOYEE
(t34): TEMP_T4_3  ← πSSN, FNAME, LNAME, BDATE TEMP_T3_3
(t35): TEMP_T5_3  ← πESSN,PNO WORKS_ON
(t36): TEMP_T6_3  ← TEMP_T4_3 |X|SSN = ESSNTEMP_T5_3
(t37): TEMP_T7_3  ← πFNAME,LNAME,BDATE, PNOTEMP_T6_3
(t38): TEMP_T8_3  ← TEMP_T2_3 |X|PNUMBER=PNOTEMP_T7_3
(t39): RESULT_Q3  ← πFNAME,LNAME,BDATE,PNUMBER,PNAME TEMP_T8_3
【０１０４】
処理プランP4 
(t41): TEMP_T1_4  ← σPNAME ='ProjectO'PROJECT
(t42): TEMP_T2_4  ← πPNUMBER,PNAME TEMP_T1_4
(t43): TEMP_T3_4  ← σPHONE = 21-3728EMPLOYEE
(t44): TEMP_T4_4  ← πSSN,FNAME,LNAME,PHONETEMP_T3_4
(t45): TEMP_T5_4  ← σHOURS > 24 WORKS_ON
(t46): TEMP_T6_4  ← TEMP_T4_4|X|SSN = ESSNTEMP_T5_4
(t47): TEMP_T7_4  ← πFNAME,LNAME,PHONE, PNO,HOURSTEMP_T6_4
(t48): TEMP_T8_4  ← TEMP_T2_4|X|PNUMBER = PNOTEMP_T7_4
(t49): RESULT_Q4  ← πFNAME,LNAME,PHONE,HOURS,PNUMBER,PNAMETEMP_T8_4
【０１０５】
処理プランP5 
(t51): TEMP_T1_5  ← σPLOCATION= 'New York' PROJECT
(t52): TEMP_T2_5  ← πPNUMBER, PNAMETEMP_T1_5
(t53): TEMP_T3_5  ← σSSN > 2311111131 AND SSN < 2834567894EMPLOYEE
(t54): TEMP_T4_5  ← πSSN,FNAME,LNAME TEMP_T3_5
(t55): TEMP_T5_5  ← πESSN,PNO WORKS_ON
(t56): TEMP_T6_5  ← TEMP_T4_5|X|SSN = ESSNTEMP_T5_5
(t57): TEMP_T7_5  ← πSSN,FNAME,LNAME, PNOTEMP_T6_5
(t58): TEMP_T8_5  ← TEMP_T2_5|X|PNUMBER=PNOTEMP_T7_5
(t59): RESULT_Q5  ← πSSN,FNAME,LNAME,PNUMBER,PNAMETEMP_T8_5
【０１０６】
処理プランP6 
(t61): TEMP_T1_6  ← πDNUMBER,DNAMEDEPARTMENT
(t62): TEMP_T2_6  ← σSSN > 2611111134EMPLOYEE
(t63): TEMP_T3_6  ← πSSN,FNAME,LNAME,DNUM TEMP_T2_6
(t64): TEMP_T4_6  ← TEMP_T1_6|X|DNUMBER=DNUMTEMP_T3_6
(t65): RESULT_Q6  ← πSSN,FNAME,LNAME,DNUMBER,DNAMETEMP_T4_6
【０１０７】
[2.3タスクのグループ化とサブグループ化]
[(a) 関係演算を組み合わせたタスクの取り出し]
図４−１〜図４−３は、作成した処理プランP1, P2, P3, P4, P5, P6を処理ツリーとして表わしたものである。まず、改善方法１である関係演算を組み合わせたタスクの取り出し手段を用いて、処理ツリーからタスクを取り出していく。
クエリー・プロセッサは、処理プランP1, P2, P3, P4, P5, P6にもとづいて作成された処理ツリーからトポロジカルソートの順番で、他のタスクから依存がなく直接的に処理できる選択演算タスクt11, t13, t15, t21, t23, t25, t31, t33, t35, t41, t43, t45, t51, t53, t55, t61, t62を見出す。これらの直接的に処理できる選択演算タスクを見出すと、これらのタスクの処理結果に対して、次に行うのタスクが射影演算であるかどうかを調べる。その結果、タスクt11の処理結果TEMP_T1_1に対して処理を行うタスクt12が射影演算である。
【０１０８】
同様に、次のようなタスクが射影演算である。
タスクt13の処理結果TEMP_T3_1に対して処理を行うタスクt14, タスクt21の処理結果TEMP_T1_2に対して処理を行うタスクt22, タスクt23の処理結果TEMP_T3_2に対して処理を行うタスクt24, タスクt31の処理結TEMP_T1_3に対して処理を行うタスクt32, タスクt33の処理結果TEMP_T3_3に対して処理を行うタスクt34, タスクt41の処理結果TEMP_T1_4に対して処理を行うタスクt42, タスクt43の処理結果TEMP_T3_4に対して処理を行うタスクt44, タスクt51の処理結果TEMP_T1_5に対して処理を行うタスクt52, タスクt53の処理結果TEMP_T3_5に対して処理を行うタスクt54, タスクt62の処理結果TEMP_T2_6に対して処理を行うタスクt63は射影演算であることがわかる。
【０１０９】
次に、選択演算(σ)と射影演算(π)を組み合わせたタスクを作成するために、タスクt12 (射影演算) にタスクt11(選択演算)を組みあわせてタスクt12'を作成する。
同様に、タスクt14にタスクt13を組み合わせてタスクt14'を作成し、タスクt22にタスクt21を組み合わせてタスクt22'を作成し、タスクt24にタスクt23を組み合わせてタスクt24'を作成し、タスクt32にタスクt31を組み合わせてタスクt32'を作成し、タスクt34にタスクt33を組み合わせてタスクt34'を作成し、タスクt42にタスクt41を組み合わせてタスクt42'を作成し、タスクt44にタスクt43を組み合わせてタスクt44'を作成し、タスクt52にタスクt51を組み合わせてタスクt52'を作成し、タスクt54にタスクt53を組み合わせてタスクt54'を作成し、タスクt63にタスクt62を組み合わせてタスクt63'を作成する。
【０１１０】
以上のことをまとめると、次のように、関係演算を組み合わせたタスクとして、選択演算タスクと射影演算タスクを同時に取り出し、選択演算と射影演算を組み合わせたタスクを作成することになる。
(t12'): TEMP_T2_1  ← πPNUMBER,PNAME(σPNUMBER > 2 AND PNUMBER < 11 PROJECT)
(t14'): TEMP_T4_1  ← πSSN, FNAME,LNAME,BDATE(σBDATE > 'DEC-01-1951' AND BDATE < 'DEC-31-1959' EMPLOYEE) 
(t22'): TEMP_T2_2  ← πPNUMBER,PNAME(σPNUMBER > 10 AND PNUMBER < 18 PROJECT)
(t24'): TEMP_T4_2  ← πSSN, FNAME, LNAME, BDATE(σBDATE > 'JAN-01-1961' AND BDATE < 'DEC-31-1966' EMPLOYEE)
(t32'): TEMP_T2_3  ← πPNUMBER,PNAME(σPNUMBER > 7 AND PNUMBER < 13 PROJECT)
(t34'): TEMP_T4_3  ← πSSN, FNAME, LNAME, BDATE (σBDATE > 'JAN-01-1966' EMPLOYEE)
(t42'): TEMP_T2_4  ← πPNUMBER,PNAME(σPNAME ='ProjectO' PROJECT)
(t44'): TEMP_T4_4  ← πSSN,FNAME,LNAME,PHONE(σPHONE = 21-3728 EMPLOYEE)
(t52'): TEMP_T2_5  ← πPNUMBER, PNAME(σPLOCATION= 'New York' PROJECT)
(t54'): TEMP_T4_5  ← πSSN,FNAME,LNAME(σSSN > 2311111131 AND SSN < 2834567894 EMPLOYEE)
(t63'): TEMP_T3_6  ← πSSN,FNAME,LNAME,DNUM (σSSN > 2611111134 EMPLOYEE)
【０１１１】
このようにして、関係演算を組み合わせたタスクt12', t14', t22', t24', t32', t34', t42',t44',t52',t54',t63'と直接的に処理できるタスクt15,t25,t35,t45,t55,t61がアクセスするリレーションをもとに、次のようにグループG1〜G4に分けることにする。
EMPLOYEE:   グループ  G1 = {t14', t24', t34', t44', t54', t63'}
PROJECT:    グループ  G2 = {t12', t22', t32', t42', t52'}
WORKS_ON:   グループ  G3 = {t15, t25, t35, t45, t55}
DEPARTMENT: グループ  G4 = {t61}
グループG1には、リレーションEMPLOYEEをアクセスするためのタスクを集め、グループG2には、リレーションPROJECTをアクセスするタスクを集め、グループG3にはリレーションWORKS_ONをアクセスするタスクを集め、グループG4にはリレーションDEPARTMENTをアクセスするタスクを集めることにする。
【０１１２】
[(b) 関係演算を組み合わせたタスクのサブグループ化]
グループ内のタスクを選択演算と射影演算の共通部分式に関する定義にしたがって、次のようにサブグループに分ける。
EMPLOYEE:  グループG1 = {SG1G1, SG2G1, t44'}
サブグループ SG1G1 = {t14', t24', t34'}
サブグループ SG2G1 = {t54', t63'}
PROJECT:   グループ G2  = {SG1G2, t42', t52'} 
サブグループ SG1G2 = {t12', t22', t32'}
WORKS_ON:  グループ G3 = {SG1G3, t45}
サブグループ  SG1G3 = {t15, t25, t35, t55}
DEPARTMENT:グループ G4 = {t61}
【０１１３】
SG1G1はリレーションEMPLOYEEに対して属性BDATEを選択条件とした選択演算の処理を行うタスクのサブグループである。
SG2G1はリレーションEMPLOYEEに対して属性SSNを選択条件とした選択演算の処理を行うタスクのサブグループである。
SG1G2はリレーションPROJECTに対して属性PNUMBERを選択条件とした選択演算のタスクのサブグループである。
SG1G3はリレーションWORKS_ONに対して射影演算の処理を行うタスクのサブグループである。
選択演算に射影演算を組み合わせたタスクと直接的に処理できるタスクがアクセスするリレーションをもとにしてグループG1〜G4に分け、さらにサブグループ化した結果を示すと、図５のようになる。
【０１１４】
[(c) 合成関係演算を組み合わせたタスクの作成]
グループ内にサブグループが作成されると、サブグループSG1G1, SG2G1, SG1G2, SG1G3に対して、下記に示すような手順にしたがって、合成関係演算を組み合わせたタスクtG1SG1, tG1SG2, tG2SG1(ステップ２の(b-2)のタスク作成に該当する)と合成射影演算タスク tG3SG1を作成する。
(tG1SG1): TEMP_SG1_G1 ← πSSN,FNAME,LNAME,BDATE(σ(BDATE>'DEC-01-1951' AND BDATE < 'DEC-31-1959') OR (BDATE > 'JAN-01-1961')EMPLOYEE)
(tG1SG2): TEMP_SG2_G1 ← πSSN,FNAME,LNAME,DNUM(σSSN > 2311111131EMPLOYEE)
(tG2SG1): TEMP_SG1_G2 ← πPNUMBER, PNAME(σPNUMBER > 2 AND PNUMBER < 18PROJECT)
(tG3SG1): πESSN,PNO WORKS_ON
【０１１５】
タスクtG1SG1は、次のように作成される。まず、タスクt14', t24', t34'内の選択演算の選択条件をブール演算のORを用いて接続して、下記に示すような接続した選択条件<temp_cond>を作成し、その選択条件から選択範囲の重複した選択条件を取り除くために、下記に示すような最適化Optimize(<temp_cond>)を行って合成された選択演算の選択条件を作成する。さらに、タスクt14', t24', t34'内の射影演算に使われている属性から属性の和集合{SSN,FNAME,LNAME,BDATE}を求めて、合成射影演算を作成する。このようにして作成された選択条件をもつ合成選択演算と合成射影演算を組み合わせて作成したタスクがtG1SG1である。
<temp_cond> = (BDATE>'DEC-01-1951' AND BDATE < 'DEC-31-1959') OR (BDATE > 'JAN-01-1961' AND BDATE < 'DEC-31-1966') OR (BDATE > 'JAN-01-1966') 
Optimize (<temp_cond>) = (BDATE>'DEC-01-1951' AND BDATE < 'DEC-31-1959') OR (BDATE > 'JAN-01-1961')
【０１１６】
タスクtG1SG2は、次のように作成される。まず、タスクt54', t63'内の選択演算の選択条件をブール演算のORを用いて接続して、下記に示すような接続した選択条件<temp_cond>を作成し、その選択条件から選択範囲の重複した選択条件を取り除くために、下記に示すような最適化Optimize(<temp_cond>)を行って合成された選択演算の選択条件を作成する。さらにタスクt54', t63'内の射影演算に使われている属性から和集合{SSN,FNAME,LNAME,DNUM}を求めて合成射影演算を作成する。このようにして作成された選択条件をもつ合成選択演算と合成射影演算を組み合わせて作成したタスクがtG1SG2である。
<temp_cond> = (SSN > 2311111131 AND SSN < 2834567894) OR (SSN > 2611111134)
Optimize(<temp_cond>) = SSN > 2311111131
【０１１７】
タスクtG2SG1は、次のように作成される。まず、タスクt12', t22', t32' 内の選択演算の選択条件をブール演算のORを使用して結合して、下記に示すような接続した選択条件<temp_cond>を作成し、その選択条件から選択範囲の重複した選択条件を取り除くために、下記のような最適化Optimize(<temp_cond>)を行って合成された選択演算の選択条件を作成する。さらに、タスクt12', t22', t32'内の射影演算に使われている属性の和集合{PNUMBER,PNAME}を求めてサブグループの合成射影演算を作成する。このようにして作成された選択条件をもつ合成選択演算と合成射影演算を組み合わせて作成したタスクがtG2SG1である。
<temp_cond> = (PNUMBER > 2 AND PNUMBER < 11) OR (PNUMBER > 10
AND PNUMBER < 18) OR (PNUMBER > 7 AND PNUMBER < 13)
Optimize(<temp_cond>) = PNUMBER > 2 AND PNUMBER < 18
【０１１８】
タスクtG3SG1は、サブグループSG1G3内の射影演算のタスクt15, t25, t35, t55に使われている属性から和集合{ESSN,PNO}を用いて作成した合成射影演算のタスクである。
以上のように、グループ内の各サブグループに対して合成関係演算を組み合わせたタスクを作成すると、次のようにグループ内のサブグループを、合成関係演算を組み合わせたタスクで置き換える。
EMPLOYEE:    グループ G1 = {tG1SG1, t G1SG2, t44'}
PROJECT:     グループ G2 = {tG2SG1, t42', t52'}
WORKS_ON:    グループ G3 = {tG3SG1, t45}
DEPARTMENT:  グループ G4 = {t61}
【０１１９】
［2.4 マルチオペレーション・プロセッシングによるグループ内のタスク処理］
グループ内のサブグループが合成関係演算を組み合わせたタスクで置き換えられると、マルチオペレーション・プロセッシングを用いてグループG1〜G4の処理を行う。改善方法２である合成結合演算タスクの処理は、(合成結合演算と合成射影演算を組み合わせたタスクとして)新たに作成されるグループG5の処理を行う際に適用している。改善方法３である合成関係演算を組み合わせたタスク処理は、グループG1, G2と新たに作成されるグループG5の処理を行う際に適用している。改善処理４であるマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法は、新たに作成されるグループG8の処理を行う際に適用している。その他のグループ処理は以上に述べたグループ処理を実行するために必要なグループ処理である。
【０１２０】
[(a) グループG1の処理（合成選択演算と合成射影演算を組み合わせたタスクを含んだグループ処理）]
マルチオペレーション・プロセッシングを使用して、グループG1内の合成選択演算と合成射影演算を組み合わせたタスクtG1SG1, tG1SG2及び選択演算と射影演算を組み合わせたタスクt44'の処理を一度に行うことになる。前述したように、グループG1内のタスクは次のようなものである。      
EMPLOYEE:  グループ G1 = {tG1SG1, tG2SG2, t44'}
(tG1SG1): TEMP_SG1_G1 ← πSSN,FNAME,LNAME,BDATE(σ(BDATE>'DEC-01-1951' AND BDATE < 'DEC-31-1959') OR (BDATE > 'JAN-01-1961')EMPLOYEE)
(tG1SG2): TEMP_SG2_G1 ← πSSN,FNAME,LNAME, DNUM(σSSN > 2311111131EMPLOYEE)
(t44'): TEMP_T4_4  ← πSSN, FNAME, LNAME, PHONE(σPHONE = 21-3728 EMPLOYEE))
【０１２１】
[(a-1) アクセスプランの作成]
グループG1内の合成選択演算と合成射影演算を組み合わせたタスクtG1SG1, tG1SG2、及び選択演算と射影演算を組み合わせたタスクt44'に対して次のようなアクセスプランを作成する。
plan(tG1SG1): EMPLOYEEをスキャンして複数のレコードを検索し、検索したレコードから属性SSN, FNAME, LNAME, BDATEを射影する。
plan(tG1SG2): EMPLOYEEの主インデックスを使用して複数のレコードを検索し、検索したレコードから属性SSN,FNAME,LNAME,DNUMを射影する。
plan(t44'):  EMPLOYEEの２次インデックスを使用して1つのレコードを検索し、検索したレコードから属性SSN,FNAME, LNAME,PHONEを射影する。
【０１２２】
[(a-2) アクセスプランのコスト計算]
各タスクに対してアクセスプランを作成すると、アクセスプランをもとに各タスクの処理コストを計算する。各タスクに含まれる射影演算の処理は、選択演算の処理を行うためにレコードをディスクからアクセスして選択した際に一緒にメインメモリ内で行うので、射影演算のために別にディスクをアクセスする必要はなく、射影演算の処理コストはかからないことになる。各タスクの処理コストは次のようになる。
タスクtG1SG1の処理コスト:  cost(tG1SG1) = bE = 5 (bE:リレーションEMPLOYEEのブロック数)
タスクtG1SG2の処理コスト:  cost(tG1SG2) = xE1 + [bE / 2] = 3 (xE1:リレーションEMPLOYEEの主インデックスのレベル) 
タスクt44'の処理コスト:              cost(t44')  =  xE2 + 1 = 2 (xE2:リレーションEMPLOYEEの二次インデックスのレベル) 
【０１２３】
タスクtG1SG1の処理コストcost(tG1SG1)は、リレーションEMPLOYEEをスキャンして合成選択演算の処理を行うために、リレーションEMPLOYEE内すべてのブロックをアクセスする処理コストなのでbE = 5である。
タスクtG1SG2の処理コストcost(tG1SG2)は、リレーションEMPLOYEEの主インデックスを使用して最初のレコードを検索し(xE1 = 1)、続けてリレーション内の約半分のブロックをアクセスする処理コストであるので、xE1 + [bE / 2] = 1 + [5 / 2] = 4である。
タスクt44'の処理コストcost(t44')は、２次インデックスを使用して１つのレコードを検索する処理コストである。これは、２次インデックスのレベルxE2と１つのブロックをアクセスする処理コストであり、EMPLOYEEの２次インデックスのレベルxE2は1であるので、処理コストはxE2 + 1 = 2である。
以上のように処理コストを計算すると、処理コストをもとにグループ内のタスクを処理コストの小さい順番から次のように並び替えることになる。
sort(tG1SG1, tG1SG2, t44') ⇒ (t44', tG1SG2, tG1SG1)
sort(..) は、各タスクの処理コストの小さい順番からの並べ替えを表している。
【０１２４】
タスクt44', tG1SG2, tG1SG1に対して、図３−１に示したリレーションEMPLOYEEからアクセスする必要のあるブロックを、リレーションEMPLOYEEのインデックスを用いてそれぞれ割り出し、それぞれのタスクt44', tG1SG2, tG1SG1の処理に必要なブロックを集めたブロック集合をB44', BG1SG2, BG1SG1とすると、次のようになる。
タスクt44'に対するブロック集合:    B44'   =  {b2}
タスクtG1SG2に対するブロック集合:  BG1SG2  =  {b4, b5}
タスクtG1SG1に対するブロック集合:  BG1SG1  =  {b1, b2, b3, b4, b5}
このように、各タスクt44', tG1SG2, tG1SG1に対応するブロック集合B44', BG1SG2, BG1SG1を見出すことができるのは、以下に示すような理由にもとづくからである。
【０１２５】
タスクt44'は、選択条件 "PHONE=21-3728" を満たすレコードが必要である。リレーションEMPLOYEEの2次インデックス(102)を使用すると、属性PHONEの値が21-3728であるレコードはブロックの相対アドレスが256であるブロックb2に格納してあることがわかり、ブロックb2だけをアクセスすることが必要となるので、タスクt44'の処理を行うためにアクセスする必要のあるブロックの集合は{b2}となる。
タスクtG1SG2は、選択条件 "SSN>2311111131" を満たすレコードが必要である。リレーションEMPLOYEEの主インデックス(100)を使用すると、属性SSNの値が2311111131以上のレコードはブロックの相対アドレスが768であるブロックb4から格納してあることがわかり、ブロックb4から最後のブロックb5までのブロックをアクセスすることが必要となるので、タスクtG1SG2の処理を行うためにアクセスする必要のあるブロックの集合は{b4, b5}となる。
【０１２６】
タスクtG1SG1は、選択条件" (BDATE <'DEC-01-1951' AND BDATE <'DEC-31-1959') OR (BDATE >'JAN-01-1961')を満たすレコードが必要である。リレーションEMPLOYEEの属性BDATEにはインデックスが存在しないので、リレーションEMPLOYEE内のすべてのレコードを線形探索するために、リレーションEMPLOYEEの最初のブロックb1から最後のブロックb5までのブロックをアクセスすることが必要となるので、タスクtG1SG1の処理を行うためにアクセスする必要のあるブロックの集合は{b1, b2, b3, b4, b5}となる。
各タスクに対してアクセスする必要のあるすべてのブロックを割り出すと、処理コストの小さいタスクからアクセスする必要のあるブロックから順番にブロックの和集合を求める。
TB0   =  {} (空集合)
タスクt44'に対応するブロック集合B44'との和集合:
TB44'  =  TB0  ∪ B44' = {b2}
タスクtG1SG2に対応するブロック集合BG1SG2との和集合: 
TBG1SG2 = TB44'∪ BG1SG2 = {b2, b4, b5}
タスクtG1SG1に対応するブロック集合BG1SG1:               
TBG1SG1 = TBG1SG2∪ BG1SG1 = {b2, b4, b5, b1, b3}
【０１２７】
以上のように、処理コストの小さいタスクに対応するブロック集合から処理コストの大きいタスクに対応するブロック集合へと順番に和集合を求めていくと、最後のタスク(処理コストの１番大きいタスク)に対応するブロック集合との和集合TBG1SG1から、ディスクのブロックb2からアクセスを開始し、ブロックb3でアクセスを終了すればよいことになり、ディスクにおけるリレーションEMPLOYEE内のブロックへのアクセスの順番を(b2, b4, b5, b1, b3)のように決定することができる。
このような方法で和集合を求めることは、処理コストの小さいタスクから順番に処理を行うに当たって、ディスク内のブロックをどのような順番でアクセスすればよいか、その順番を決定するためである。このようにして得られたブロックb2, b4, b5, b1, b3は、タスクt44', tG1SG2, tG1SG1を順番に処理していくときに共用され得るので、これらのブロックを共通ブロックと呼ぶことにする。
【０１２８】
前述したブロック集合B44', BG1SG2, BG1SG1の中に含まれているブロックを見ると、ブロックb2は、タスクt44', tG1SG1を処理するために使用され、ブロックb4, b5は、タスクtG1SG1, tG1SG2を処理するために使用され、ブロックb1, b3は、タスクtG1SG1を処理するために使用されることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。以上のことをまとめると次のような表になる。
【表２】
2008276464.tif 000004
【０１２９】
[(a-3) 共通ブロックでのタスク処理]
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、タスクt44', tG1SG2, tG1SG1に対して作成されたブロック集合B44', BG1SG2, BG1SG1の情報にもとづいて、次に記述するような手順を用いればよい。
最初に、ブロックb2をディスクからアクセスして、ブロックb2内のデータをメインメモリに読み込み、グループ内のタスクt44', tG1SG2, tG1SG1がブロックb2で処理を行う必要があるかどうかを調べるため、ブロックb2を集合{b2}として表し、この{b2}とブロックの集合B44', BG1SG2, BG1SG1との間でそれぞれ積集合(Intersection)を求めると次のようになる。
タスクt44'に対して: B44' ∩ {b2} = {b2}
タスクt G1SG2に対して: BG1SG2 ∩  {b2} = {}
タスクtG1SG1に対して: BG1SG1 ∩ {b2} = {b2}
【０１３０】
タスクt G1SG2を除くタスクt44', t G1SG1に対する積集合が{b2}となり、タスクt44', t G1SG1がメインメモリに読み込んだブロックb2で処理を行う必要があることが明らかになり、ブロックb2は共通ブロックとなり、共通ブロックb2で各タスクの処理を行うことになる。共通ブロックであるブロックb2でのタスクの処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、集合B44', B G1SG1と集合{b2}との差集合（Difference)を求める。得られた差集合の値をB44'(1), BG1SG1(1)とすると、次のようになる。
タスクt44'に対して: B44'  - {b2} = {} = B44'(1)
タスクtG1SG1に対して: BG1SG1 - {b2} = {b1, b3, b4, b5} = BG1SG1(1)
この結果、集合B44'(1)が空集合({})になり、タスクt44'の処理が終了したことがわかる。
【０１３１】
次に、ブロックb4をディスクからアクセスして、ブロックb4内のデータをメインメモリに読み込み、すでに処理の済んだタスクt44'を除くグループ内のタスクtG1SG2, tG1SG1がブロックb4で処理を行う必要があるかどうかを調べるために、ブロックb4を集合{b4}として表し、{b4}とブロックの集合B G1SG2, B G1SG1(1)との間でそれぞれ積集合を求めると次のようになる。
タスクtG1SG2に対して: B G1SG2 ∩ {b4} = {b4}
タスクtG1SG1に対して: B G1SG1(1) ∩ {b4} = {b4}
タスクt G1SG2, tG1SG1に対する積集合が{b4}となり、タスクtG1SG2, tG2SG1がメインメモリに読み込んだブロックb4で処理を行うことが必要となり、ブロックb4は、共通ブロックとなる。
【０１３２】
共通ブロックであるブロックb4でのタスクの処理が終了すると、ブロックb4を再びアクセスする必要がなくなるので、集合B G1SG2, BG1SG1(1)と集合{b4}との差集合を求める。得られた差集合の値をBG1SG2(1), BG1SG1(2)とすると、次のようになる。
タスクtG1SG2に対して: BG1SG2  - {b4} = {b5} = B G1SG2(1)
タスクtG1SG1に対して: BG1SG1(1)  - {b4} = {b1, b3, b5} = BG1SG1(2)
【０１３３】
次に、ブロックb5をディスクからアクセスして、ブロックb5内のデータをメインメモリに読み込み、すでに処理の済んだタスクt44'を除くグループ内のタスクtG1SG2, tG1SG1がブロックb5で処理を行う必要があるかどうかを調べるために、ブロックb5を集合{b5}として表し、{b5}とブロックの集合BG1SG2(1), BG1SG1(2)との間で積集合を求めると次のようになる。
タスクtG1SG2に対して: B G1SG2(1) ∩ {b5} = {b5}
タスクtG1SG1に対して: B G1SG1(2) ∩ {b5} = {b5}
タスクtG1SG2, tG2SG1に対する積集合が{b5}となり、タスクtG1SG2, t G2SG1がメインメモリに読み込んだブロックb5で処理を行うことが必要となり、ブロックb5は共通ブロックとなる。
【０１３４】
共通ブロックであるブロックb5でのタスクの処理が終了すると、ブロックb5を再びアクセスする必要がなくなるので、集合B G1SG2(1), BG1SG1(2)と集合{b5}との差集合を求めて、得られた差集合の値をBG1SG2(2), BG1SG1(3)とすると、次のようになる。
タスクtG1SG2に対して: BG1SG2(1)  - {b5} = {} = BG1SG2 (2)
タスクtG1SG1に対して: BG1SG1(2)  - {b5} = {b1, b3} = BG1SG1(3)
この結果、集合BG1SG2(2)が空集合({})になり、タスクtG1SG2の処理が終了したことがわかる。
この段階で、グループに残ったタスクはtG1SG1のみとなるので、リレーションEMPLOYEEから残ったブロックb1, b3をアクセスしてタスクtG1SG1の処理を行う。タスクtG1SG1の処理が終了するとグループ内のすべてのタスクの処理が終了することになる。
図６は、プロセス(502)がリレーションEMPLOYEE内のブロックをb2, b4, b5, b1, b3の順番でアクセスして、タスクt44', tG1SG2, tG1SG1の処理を一度に行い、処理結果をTEMP_T4_4, TEMP_SG2_G1, TEMP_SG1_G1に書き込んでいる様子を表している。
【０１３５】
[(a-4) 仮想リレーションの作成]
図６において、TEMP_T4_4は、タスクt44' の処理結果である。
合成選択演算と合成射影演算を組み合わせたタスクtG1SG2の処理結果TEMP_SG2_G1は、サブグループ内のタスクt54', t63'によって部分的に共有される。前述したようにサブグループSG2G1内のタスクは次のようなものである。
サブグループ  SG2G1 = {t54', t63'}
(t54'): TEMP_T4_5  ← πSSN,FNAME,LNAME (σSSN > 2311111131 AND SSN < 2834567894 EMPLOYEE)
(t63'): TEMP_T3_6  ← πSSN,FNAME,LNAME,DNUM (σSSN > 2611111134 EMPLOYEE)
【０１３６】
サブグループSG2G1内のタスクt54', t63'の処理結果に対して、図６に示すような仮想リレーションTEMP_T4_5, TEMP_T3_6 を作成する。仮想リレーションには、合成関係演算を組み合わせたタスクtG1SG2の処理結果のリレーション名、その処理結果が共有するレコードの格納位置(レコードの行の範囲)、属性の格納位置(属性の列番号)を記録しておくことにすると次のようになる。
TEMP_T4_5 = {リレーション: TEMP_SG2_G1; 行: 1〜5; 列:1〜3; ブロック: b1[0, 256], b2[256, 512]};
TEMP_T3_6 = {リレーション: TEMP_SG2_G1; 行: 4〜8; 列: 1〜4; ブロック: b1[0, 256], b2[256, 512]};
【０１３７】
仮想リレーションTEMP_T4_5は、サブグループSG2G1内のタスクt54'の処理結果であり、合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーションTEMP_SG2_G1に対して、相対アドレス0〜512をもつブロックb1, b2に格納されている1〜5行までのレコードの列1〜3を共有する。
仮想リレーションTEMP_T3_6は、サブグループSG2G1内のタスクt63'の処理結果であり、合成選択演算と合成射影演算を組み合わせたタスクの処理結果のリレーションTEMP_SG2_G1に対して、相対アドレス0〜512をもつb1, b2に格納されている4〜8行までのレコードの列1〜4を共有する。
【０１３８】
同様に、合成選択演算と合成射影演算を組み合わせたタスクtG1SG1の処理理結果TEMP_SG1_G1は、サブグループ内のタスクt14', t24', t34'によって部分的に共有されることになる。前述したようにサブグループSG1G1内のタスクは次のようなものである。
サブグループ  SG1G1 = {t14', t24', t34'}
(t14'): TEMP_T4_1  ← πSSN, FNAME,LNAME,BDATE (σBDATE > 'DEC-01-1951' AND BDATE < 'DEC-31-1959' EMPLOYEE) 
(t24'): TEMP_T4_2  ← πSSN, FNAME, LNAME, BDATE(σBDATE > 'JAN-01-1961' AND BDATE < 'DEC-31-1966' EMPLOYEE)
(t34'): TEMP_T4_3  ← πSSN, FNAME, LNAME, BDATE(σBDATE > 'JAN-01-1966' EMPLOYEE)
【０１３９】
サブグループ内のタスクt14', t24', t34'対して、図６に示すように仮想リレーションTEMP_T4_1, TEMP_T4_2, TEMP_T4_3を作成する。仮想リレーションに合成選択演算と合成射影演算を組み合わせたタスクtG1SG1の処理結果のリレーション名TEMP_SG1_G1、その処理結果が共有するレコードの行と属性の列を記録すると次のようになる。
TEMP_T4_1 = {リレーション名: TEMP_SG1_G1; 行:1〜4; 列:1〜4; ブロック: b1[0, 256]};
TEMP_T4_2 = {リレーション名: TEMP_SG1_G1; 行:5〜8; 列:1〜4; ブロック: b2[256, 512]};
TEMP_T4_3 = {リレーション名: TEMP_SG1_G1; 行:8〜16; 列:1〜4;  ブロック:b2[256, 512],b3[512, 768],b4[768, 1024]};
【０１４０】
仮想リレーションTEMP_T4_1は、サブグループSG1G1内のタスクt14'の処理結果であり、合成選択演算と合成射影演算を組み合わせたタスクtG1SG1の処理結果のリレーションTEMP_SG1_G1に対して、相対アドレス0〜256をもつブロックb1に格納してある1〜4行までのレコードの列1〜4を共有する。
仮想リレーションTEMP_T4_2は、サブグループSG1G1内のタスクt24'の処理結果であり、タスクtG1SG1の処理結果のリレーションTEMP_SG1_G1に対して、相対アドレス256〜512をもつブロックb2に格納してある5〜8行までのレコードの列1〜4を共有する。
仮想リレーションTEMP_T4_3は、サブグループSG1G1内のタスクt34'の処理結果であり、タスクtG1SG1の処理結果のリレーションTEMP_SG1_G1に対して、相対アドレス256〜1024をもつブロックb2, b3, b4に格納してある8〜16行までのレコードの列1〜4を共有する。
【０１４１】
[(a-5) 新たなグループの作成の有無]
以上のように合成関係演算を利用したマルチオペレーション・プロセッシングを使用して、グループG1内の合成選択演算と合成射影演算を組み合わせたタスクtG1SG2, tG1SG1及び選択演算と射影演算を組み合わせたタスクt44' が、タスクt44', tG1SG2, tG1SG1の順番で終了すると、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
最初に、タスクt44'の処理が終了すると処理ツリーP4からわかるようにグループG3内のタスクt45の処理が終了していないため、新たに処理できるタスクは見出されないのでグループは作成されない。
【０１４２】
次に、タスクtG1SG2の処理が終了すると、サブグループSG2G1内のタスクt54', t63'の処理が終了することになり、処理ツリーP5, P6からわかるように、グループG3内のタスクt55の処理とグループG4内のタスクt61の処理が終了していないため、新たに処理できるタスクは見出されないのでグループは作成されない。
最後に、タスクtG1SG1の処理が終了すると、サブグループSG1G1内のタスクt14', t24', t34'の処理が終了することになり、処理ツリーP1, P2, P3からわかるように、グループG3内のタスクt15, t25, t35の処理が終了していないため、新たに処理できるタスクは見出されないのでグループは作成されない。
【０１４３】
[(b) グループG2の処理（合成選択演算と合成射影演算を組み合わせたタスクを含んだグループ処理]
マルチオペレーション・プロセッシングを使用してグループG2内の合成選択演算と合成射影演算を組み合わせたタスクtG2SG1, 及びサブグループに集まらないタスクt42', t52'の処理を一度に行うことにする。前述したように、グループG2内のタスクは次のようなものである。グループG2には、合成選択演算と合成射影演算を組み合わせたタスクtG2SG1及び選択演算と射影演算を組み合わせたタスクt42', t52'が集められている。
PROJECT:  グループ  G2 = {tG2SG1,t42',t52'}
(tG2SG1): TEMP_SG1_G2 ← πPNUMBER, PNAME (σPNUMBER > 2 AND PNUMBER < 18 PROJECT)
(t42'): TEMP_T2_4  ← πPNUMBER,PNAME (σPNAME ='ProjectO' PROJECT)
(t52'): TEMP_T2_5  ← πPNUMBER, PNAME(σPLOCATION= 'New York' PROJECT)
【０１４４】
[(b-1) 各タスクのアクセスプラン]
グループG2内の合成選択演算と合成射影演算を組み合わせたタスクtG2SG1及び選択演算と射影演算を組み合わせたタスクt42', t52'に対して次のようなアクセスプランを作成する。
plan(tG2SG1): PROJECTの主インデックスを使用して複数のレコードを検索し、検索したレコードから属性PNUMBER, PNAMEを射影する。
plan(t42'): PROJECTの２次インデックスを使用して１つのレコードを検索し、検索したレコードから属性PNUMBER, PNAMEを射影する。
plan(t52'): PROJECTを線形探索してレコードを検索し、検索したレコードから属性PNUMBER, PNAMEを射影する。
【０１４５】
[(b-2) 各タスクの処理コスト]
各タスクに対してアクセスプランを作成すると、アクセスプランをもとに、各タスクの処理コストを計算する。
タスクtG2SG1の処理コスト: cost(tG2SG1) = xP + [bP / 2] = 4 (xP:リレーションPROJECTの主インデックスのレベル,bp:リレーションPROJECTのブロック数)
タスクt42'の処理コスト: cost(t42') = xP2 + 1 = 2 (xP2:リレーションPROJECTの2次インデックスのレベル) 
タスクt52'の処理コスト: cost(t52') = bP = 5 
タスクtG2SG1の処理コストは、リレーションPROJECT主インデックスを使用して最初のレコードを検索し(xP=1)、続けて、リレーション内の約半分のブロックをアクセスする処理コストであるので、xP + [bP / 2] = 4である。
タスクt42'の処理コストは、リレーションPROJECTの２次インデックス(203)を使用して１つのレコードを検索する処理コストである。これは２次インデックスのレベルxP2とブロックをアクセスする処理コストであり、図３−３のリレーションPROJECTの２次インデックス(201)のレベルxP2は１であるので、処理コストはxP2 + 1 = 2である。
タスクt52'の処理コストは、リレーションPROJECTを線形探索し、5つのブロックをアクセスするので、処理コストはbP = 5である。
以上のように処理コストを計算すると、処理コストをもとにグループ内のタスクを処理コストの小さい順番で並べ替えると次のようになる。
sort(t42', t52', tG2SG1) ⇒ (t42', tG2SG1, t52')
【０１４６】
[(b-3) 各タスクに対応するブロック集合]
グループ内のタスクを処理コストの小さい順番から並び替えると、リレーションPROJECTのインデックスを参照して、タスクt42', tG2SG1, t52'の順番でリレーションPROJECTのデータリレーションからアクセスする必要のあるすべてのブロックを事前に調べて、それぞれ集合B42', BG2SG1, B52'に集めると次のようになり、各タスクに対応するブロック集合が得られる。
タスクt42'に対するブロック集合: B42' = {b3}
タスクtG2SG1に対するブロック集合: BG2SG1  = {b1, b2, b3, b4}
タスクt52' に対するブロック集合: B52'  = {b1, b2, b3, b4, b5}
このように、各タスクt42', tG2SG1, t52'に対応するブロック集合B44', BG2SG1, B52'を見出すことができるのは、以下に示すような理由にもとづくからである。
【０１４７】
タスクt42'は、選択条件 "PNAME='ProjectO'" を満たすレコードが必要である。リレーションPROJECTの2次インデックス(203)を使用すると、属性PNAMEの値が'ProjectO'であるレコードはブロックの相対アドレスが512であるブロックb3に格納してあることがわかり、ブロックb3だけをアクセスすることが必要となるので、タスクt42'の処理を行うためにアクセスする必要のあるブロックの集合は{b3}となる。
タスクtG2SG1は、選択条件 "PNUMBER>2 AND PNUMBER<18" を満たすレコードが必要である。リレーションPROJECTの主インデックス(201)を使用すると、属性PNUMBERの値が2以上のレコードはブロックの相対アドレスが0であるブロックb1から格納してあり、次にPNUMBERの値が18であるレコードはブロックの相対アドレスが768であるブロックb4に格納してあり、タスクtG2SG1の処理を行うためにアクセスする必要のあるブロックは、ブロックb1からブロックb4までのブロックとなり、ブロックの集合は{b1, b2, b3, b4}となる。
タスクt52は、選択条件"PLOCATION='New York'"を満たすレコードが必要である。リレーションPROJECTの属性PLOCATIONにはインデックスが存在しないので、リレーションPROJECT内のすべてのレコードを線形探索するために、リレーションPROJECTの最初のブロックb1から最後のブロックb5までのブロックをアクセスすることが必要となるので、タスクtG1SG1の処理を行うためにアクセスする必要のあるブロックの集合は{b1, b2, b3, b4, b5}となる。
【０１４８】
各タスクに対してアクセスする必要のあるすべてのブロックを割り出すと、処理コストの小さいタスクからアクセスする必要のあるブロックから順番にブロックの和を求める。
TB0  =  {}    
タスクt42'に対応するブロック集合B42'との和集合:
TB42'= TB0 ∪B42' = {b3}
タスクtG2SG1に対応するブロック集合BG2SG1との和集合:
TBG2SG1= TB42'∪BG2SG1 = {b3,b1,b2,b4}
タスクt52'に対応するブロック集合B52'との和集合:
TB52'= TBG2SG1∪ B52'= {b3,b1,b2,b4,b5}
【０１４９】
以上のように、処理コストの小さいタスクに対応するブロック集合から処理コストの大きいタスクに対応するブロック集合へと順番に和集合を求めていくと、最後のタスク(処理コストの１番大きいタスク)に対応するブロック集合との和集合TB52'から、ブロックb3からアクセスを開始し、ブロックb5でアクセスを終了すればよいことになり、ディスクにおけるリレーションPROJECT内のブロックへのアクセスの順番をb3, b1, b2, b4, b5のように決定することができる。このようにして得られたブロックb3, b1, b2, b4, b5は、タスクt42', tG2SG1, t52'を順番に処理していくときに共用され得るので、これらのブロックを共通ブロックと呼ぶことにする。
【０１５０】
前述したブロック集合B42', BG2SG1, B52'の中に含まれているブロックを見ると、ブロックb3は、タスクt42, tG2SG1, t52'を処理するために使用され、ブロックb1は、タスクtG2SG1, t52'を処理するために使用され、ブロックb2は、タスクtG2SG1, t52'を処理するために使用され、ブロックb4は、タスクtG2SG1, t52'を処理するために使用され、ブロックb5は、タスクt52'を処理するために使用されることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。以上のことをまとめると次のような表になる。  
【表３】
2008276464.tif 000005
【０１５１】
[(b-4) 共通ブロックでのタスクの処理]
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、タスクt42', tG2SG1, t52'に対して作成されたブロック集合B42', BG2SG1, B52'の情報にもとづいて、次に記述するような手順を用いればよい。
【０１５２】
最初に、ブロックb3をディスクからアクセスして、ブロックb3内のデータをメインメモリに読み込み、グループ内のタスクt42', tG2SG1, t52'がブロックb3で処理を行う必要があるかどうかを調べるため、ブロックb3を集合{b3}として表し、{b3}とブロックの集合B42', BG2SG1, B52'との間でそれぞれ積集合(Intersection)を求めると次のようになる。
タスクt42'に対して: B42' ∩ {b3} = {b3}
タスクtG2SG1に対して: BG2SG1 ∩ {b3} = {b3}
タスクt52'に対して: B52' ∩ {b3} = {b3}
【０１５３】
タスクt42', tG2SG1, t52'に対する積集合が{b3}となり、タスクt42', tG2SG1, t52'がメインメモリに読み込んだブロックb3で処理を行う必要があることが明らかになり、ブロックb3は共通ブロックとなり、共通ブロックb3で各タスクの処理を行うことになる。共通ブロックであるブロックb3でのタスクの処理が終了すると、ブロックb3を再びアクセスする必要がなくなるので、集合B42', BG2SG1, B52'と集合{b3}との差集合（Difference)を求める。得られた差集合の値をB42'(1), BG2SG1(1), B52'(1)とすると、次のようになる。
タスクt42'に対して: B42'  - {b3} = {} = B42'(1)
タスクtG2SG1に対して: BG2SG1 - {b3} = {b1, b2, b4} = BG2SG1(1)
タスクt52'に対して: B52'  - {b3} = {b1, b2, b4, b5} = B52'(1)
この結果、集合B42'(1)が空集合({})になり、タスクt42'の処理が終了したことがわかる。
【０１５４】
次に、ブロックb1をディスクからアクセスして、ブロックb1内のデータをメインメモリに読み込み、すでに処理の済んだタスクt42'を除くグループ内のタスクtG2SG1, t52'がブロックb1で処理を行う必要があるかどうかを調べるために、ブロックb1を集合{b1}として表し、{b1}とブロックの集合BG2SG1(1), B52'(1)との間でそれぞれ積集合を求めると次のようになる。
タスクtG2SG1に対して: B G2SG1(1) ∩ {b1} = {b1}
タスクt52' に対して: B52'(1) ∩ {b1} = {b1}
【０１５５】
タスクt G2SG1, t52'に対する積集合が{b1}となり、タスクt G2SG1, t52'がメインメモリに読み込んだブロックb1で処理を行うことが必要となり、ブロックb1は、共通ブロックとなる。共通ブロックであるブロックb1でのタスクの処理が終了すると、ブロックb1を再びアクセスする必要がなくなるので、集合B G2SG1(1), B52'(1)と集合{b1}との差集合を求める。得られた差集合の値をBG2SG1(2), B52'(2)とすると、次のようになる。
タスクtG2SG1に対して: BG2SG1(1) - {b1} = {b2, b4} = BG2SG1(2)
タスクt52'に対して: B52'(1) - {b1} = {b2, b4, b5} = B52'(2)
【０１５６】
次に、ブロックb2をディスクからアクセスして、ブロックb2内のデータをメインメモリに読み込み、すでに処理の済んだタスクt42を除くグループ内のタスクtG2SG1, t52'がブロックb2で処理を行う必要があるかどうかを調べるために、ブロックb2を集合{b2}として表し、{b2}とブロックの集合BG2SG1(2), B52'(2)との間で積集合を求めると次のようになる。
タスクtG2SG1に対して: BG2SG1(2) ∩ {b2} = {b2}
タスクt52'に対して: B52'(2) ∩ {b2} = {b2}
【０１５７】
タスクtG2SG1, t52'に対する積集合が{b2}となり、タスクtG2SG1, t52'がメインメモリに読み込んだブロックb2で処理を行うことが必要となり、ブロックb2は、共通ブロックとなる。共通ブロックであるブロックb2でのタスクの処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、集合BG2SG1(2), B52'(2)と集合{b2}との差集合を求める。得られた差集合の値をBG2SG1(3), B52'(3)とすると、次のようになる。
タスクtG2SG1に対して: BG2SG1(2)  - {b2} = {b4} = BG2SG1(3)
タスクt52' に対して: B52'(2)  - {b2} = {b4, b5} = B52'(3)
【０１５８】
次に、ブロックb4をディスクからアクセスして、ブロックb4内のデータをメインメモリに読み込み、すでに処理の済んだタスクt41'を除くグループ内のタスクt G2SG1, t52'がブロックb4で処理を行う必要があるかどうかを調べるために、ブロックb4を集合{b4}として表し、{b4}とブロックの集合BG2SG1(3), B52'(3)との間で積集合を求めると次のようになる。
タスクtG2SG1に対して: BG2SG1(3) ∩ {b4} = {b4}
タスクt52' に対して: B52'(3) ∩ {b4} = {b4}
【０１５９】
タスクtG2SG1, t52'に対する積集合が{b4}となり、タスクtG2SG1, t52'がメインメモリに読み込んだブロックb4で処理を行うことが必要となり、ブロックb4は、共通ブロックとなる。共通ブロックであるブロックb4でのタスクの処理が終了すると、ブロックb4を再びアクセスする必要がなくなるので、集合BG2SG1(3), B52'(3)と集合{b4}との差集合を求める。得られた差集合の値をBG2SG1(4), B52'(4)とすると、次のようになる。
タスクtG2SG1に対して: BG2SG1(3)  - {b4} = {} = BG2SG1(4)
タスクt52' に対して: B52'(3)  - {b4} = {b5} = B52'(4)
この結果、集合BG2SG1(4)が空集合({})になりタスクtG2SG1の処理が終了したことがわかる。この段階で、残ったタスクはt52'のみとなるので、リレーションPROJECTから残ったブロックb5をアクセスしてタスクt52'の処理を行い、タスクt52'の処理が終了すると、グループ内すべてのタスクの処理が終了することになる。
図７は、プロセス(602)がリレーションPROJECT内のブロックをb3, b1, b2, b4, b5の順番でアクセスして、タスクt42', tG2SG1, t52'の処理を一度に行い、処理結果をTEMP_T2_4, TEMP_SG1_G2, TEMP_T2_5に書き込んでいる様子を表している。
【０１６０】
[(b-5) 仮想リレーションの作成]
合成選択演算と合成射影演算を組み合わせたタスクtG2SG1の処理結果TEMP_SG1_G2は、サブグループSG1G2内の選択演算と射影演算を組み合わせたタスクt12', t22', t32'によって部分的に共有されることになる。
前述したようにサブグループSG1G2内のタスクは次のようなものである。
サブグループ  SG1G2 = {t12', t22', t32'}
(t12'): TEMP_T2_1  ← πPNUMBER,PNAME (σPNUMBER > 2 AND PNUMBER < 11 PROJECT)
(t22'): TEMP_T2_2  ← πPNUMBER,PNAME (σPNUMBER > 10 AND PNUMBER < 18 PROJECT)
(t32'): TEMP_T2_3  ← πPNUMBER,PNAME (σPNUMBER > 7 AND PNUMBER < 13 PROJECT)
【０１６１】
サブグループSG1G2内のタスクt12', t22', t32' に対して、図７に示すような仮想リレーションTEMP_T2_1, TEMP_T2_2, TEMP_T2_3を作成し、その仮想リレーションに、仮想リレーションが共有する合成選択演算と合成射影演算を組み合わせたタスクtG2SG1の処理結果のリレーション名(TEMP_SG1_G2)、その処理結果を共有するレコードの格納位置(レコードの行範囲)、属性の格納位置（列番号）、レコードが格納されているブロックの番号とアドレス)を次のように記録しておくことにする。
TEMP_T2_1 = {リレーション: TEMP_SG1_G2; 行: 1〜8;  列: 1〜2;
ブロック: b1[0, 256], b2[256, 512]};
TEMP_T2_2 = {リレーション: TEMP_SG1_G2; 行: 9〜15; 列: 1〜2; 
ブロック: b2[256, 512], b3[512, 768]};
TEMP_T2_3 = {リレーション: TEMP_SG1_G2; 行: 6〜10; 列: 1〜2; 
ブロック: b1[0, 256], b2[256, 512]};
【０１６２】
仮想リレーションTEMP_T2_1は、サブグループSG1G2内のタスクt12'の処理結果であり、TEMP_SG1_G2に対して、相対アドレス0〜512上ブロックb1, b2に格納してある1〜8行までのレコードの列1〜2を共有する。
仮想リレーションTEMP_T2_2は、サブグループSG1G2内のタスクt22'の処理結果であり、TEMP_SG1_G2に対して、相対アドレス256〜768上ブロックb2, b3に格納してある9〜15行までのレコードの列1〜2を共有する。
仮想リレーションTEMP_T2_3は、サブグループSG1G2内のタスクt32'の処理結果であり、TEMP_SG1_G2に対して、相対アドレス0〜512上ブロックb1, b2に格納してある6〜10行までのレコードの列1〜2を共有する。
【０１６３】
以上のようにサブグループSG1G2の各タスクに対して仮想リレーションを作成することによって、サブグループ内のタスクt12', t22', t32' は、合成選択演算と合成射影演算を組み合わせたタスクtG2SG1の処理結果TEMP_SG1_G2内のレコード及び属性(列)を部分的に共有することになる。図７は、合成選択演算と合成射影演算を組み合わせたタスクtG2SG1の処理結果TEMP_SG1_G2が、仮想リレーションTEMP_ T2_1, TEMP_ T2_2, TEMP_ T2_3によって部分的に共有されている様子を表わしている。
【０１６４】
[(b-6) 新たなグループの作成の有無]
グループG2の処理が終了すると、グループG2内のタスクt42', tG2SG1, t52'の処理が一度に終了することによって、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。最初に、タスクt42'の処理が終了すると、処理ツリーP4からわかるようにグループG3内のタスクt45'の処理とグループに集められていないタスクt46, t47の処理が終了していないため、新たに処理できるタスクは見出されないのでグループは作成されない。
【０１６５】
次に、タスクtG1SG2の処理が終了すると、サブグループSG2G1内のタスクt12', t22', t32'の処理が一度に終了することになる。タスクt12'の処理が終了すると処理ツリーP1からわかるようにグループG3に集められたタスクt15の処理とグループに集められていないタスクt16, t17の処理が終了していないため、新たなグループは作成されない。タスクt22'の処理が終了すると処理ツリーP2からわかるようにグループG3に集められたタスクt25の処理とグループに集められていないタスクt26, t27の処理が終了していないため、新たなグループは作成されない。タスクt32'の処理が終了すると、処理ツリーP3からわかるようにグループG3に集められたタスクt35の処理とグループに集められていないタスクt36, t37の処理が終了していないため新たなグループは作成されない。
最後に、タスクt52'の処理が終了すると、処理ツリーP5からわかるようにグループG3内のタスクt55の処理とグループに集められていないタスクt56, t57の処理が終了していないため新たなグループは作成されない。
【０１６６】
[(c) グループG3の処理]
スタティックマルチオペレーション・プロセッシングを使用してグループG3内の合成射影演算のタスクtG3SG1及び選択演算のタスクt45の処理を一度に行うことにする。前述したように、グループG3内のタスクは次のようなものである。
WORKS_ON: グループ  G3 = {tG3SG1, t45}
(tG3SG1): TEMP_SG1_G3  ← πESSN,PNO WORKS_ON
(t45): TEMP_T5_4  ← σHOURS > 24 WORKS_ON
【０１６７】
[(c-1) アクセスプランの作成]
グループG3内の合成射影演算のタスクtG3SG1及び選択演算のタスクt45に対して次のようなアクセスプランを作成する。
plan(tG3SG1): WORKS_ONをスキャンして射影演算を行う。
plan(t45): WORKS_ONを線形探索して選択演算を行う。
【０１６８】
[(c-2) 各タスクの処理コスト]
各タスクに対してアクセスプランを作成すると、アクセスプランをもとに、各タスクの処理コストを計算する。
タスクtG3SG1の処理コスト: cost(tG3SG1) = bW = 5 (bW:リレーションWORKS_ONのブロック数) 
タスクt45の処理コスト: cost(t45) = bW = 5
【０１６９】
タスクtG3SG1の処理コストは、射影演算の処理を行うために、リレーションWORKS_ONをスキャンしてリレーション内すべてのブロックをアクセスする処理コストなのでbW = 5である。
タスクt45の処理コストは、選択演算の処理を行うために、リレーションWORKS_ONを線形探索し、5つのブロックをアクセスするので処理コストなのでbW = 5である。
【０１７０】
[(c-3) タスクのアクセスするブロックの集合]
スタティックマルチオペレーション・プロセッシングを使用してグループG3内のタスクtG3SG1, t45'の処理を一度に行うことにする。タスクtG3SG1, t45に対してアクセスする必要のあるすべてのブロックをそれぞれ割り出して、集合BG3SG1, B45 に集める。
タスクtG3SG1に対するブロック集合: BG3SG1  = {b1, b2, b3, b4, b5}
タスクt45に対するブロック集合: B45 = {b1, b2, b3, b4, b5}
【０１７１】
[(c-4) アクセスするブロックの順番の決定]
各タスクに対してアクセスする必要のあるすべてのブロックを割り出すと、処理コストの小さいタスクからアクセスする必要のあるブロックから順番にブロックの和を求める(２つの処理コストはともに５で同じであるので順番はどちらからでもよい)。
TB0 =  {}
タスクtG3SG1に対するブロック集合: TBG3SG1 = TB0 ∪BG3SG1 = {b1, b2, b3, b4, b5}
タスクt45に対するブロック集合:           TB45 = TBG3SG1∪ B45  = {b1, b2, b3, b4, b5}
TB0〜TB45からリレーションWORKS_ON内のブロックをb1〜b5の順番でディスクからアクセスして、メインメモリに読み込んだ各ブロックに対してタスクtG3SG1, t45の処理を一度に行えばよいことがわかる。
図８は、プロセス(700)がスタティックマルチオペレーション・プロセッシングを使用してリレーションWORKS_ON内のブロックをb1〜b5の順番でアクセスして、各ブロック上でタスクtG3SG1, t45の処理を行った処理結果をTEMP_SG1_G3, TEMP_T5_4に書き込んでいる様子を表している。
【０１７２】
[(c-5) 仮想リレーションの作成]
図８において、合成射影演算のタスクtG3SG1の処理結果TEMP_SG1_G3は、サブグループ内の射影演算のタスクt15, t25, t35, t55によって共有されることになり、タスクt15, t25, t35, t55 対して、図８に示すように仮想リレーションTEMP_T5_1, TEMP_T5_2, TEMP_T5_3, TEMP_T5_5を作成する。仮想リレーションには合成射影演算のタスクtG3SG1の処理結果のリレーション名(TEMP_SG1_G3)、その処理結果が共有するレコードの格納位置(レコードの行範囲)、属性の格納位置(列番号)、レコードが格納されているブロックの番号とアドレスを記録しておくことにする。
TEMP_T5_1 = {リレーション: TEMP_SG1_G3; 行: 1〜25; 列: 1〜2; 
ブロック: b1[0, 256], b2[256, 512], b3[512, 768], b4[768,1024],
b5[1024, -]};
TEMP_T5_2 = {リレーション: TEMP_SG1_G3; 行: 1〜25; 列: 1〜2; 
ブロック: b1[0, 256], b2[256,512], b3[512,768], b4[768,1024],
b5[1024, -]};
TEMP_T5_3 = {リレーション: TEMP_SG1_G3; 行: 1〜25; 列: 1〜2; 
ブロック: b1[0, 256], b2[256,512], b3[512,768], b4[768,1024],
b5[1024, -]};
TEMP_T5_5 = {リレーション: TEMP_SG1_G3; 行: 1〜25; 列: 1〜2; 
ブロック: b1[0, 256], b2[256,512], b3[512,768], b4[768,1024],                             b5[1024, -]};
サブグループ内の射影演算のタスクt15, t25, t35, t55は射影演算の処理が等しいため(t15≡t25≡t35≡t55)、これらのタスクの処理結果である仮想リレーションTEMP_T5_1,TEMP_T5_2, TEMP_T5_3, TEMP_T5_5は等しくなる(TEMP_T5_1≡TEMP_T5_2≡TEMP_T5_3≡TEMP_T5_5) 。
【０１７３】
[(c-6) 新たなグループの作成の有無]
マルチオペレーション・プロセッシングを使用して、グループG3内の合成射影演算のタスクtG3SG1及び射影演算のタスクt45の処理が終了すると、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
最初に、タスクtG3SG1の処理が終了すると、サブグループSG1G3内の射影演算のタスクt15, t25, t35, t55の処理が終了することになり、処理ツリーP1, P2, P3, P5からわかるように、新たに結合演算タスクt16, t26, t36, t56の処理ができるようになる。タスクt16, t26, t36, t56はそれぞれ結合演算の検索元に使用する仮想リレーションが異なるが、タスクt16はタスクt15の処理結果である仮想リレーションTEMP_T5_1 (図８)を用いてタスクtG3SG1の処理結果TEMP_SG1_G3をアクセスし、タスクt26はタスクt25の処理結果である仮想リレーションTEMP_T5_2を用いてタスクtG3SG1の処理結果TEMP_SG1_G3をアクセスし、タスクt36はタスクt35の処理結果である仮想リレーションTEMP_T5_3を用いてタスクtG3SG1の処理結果TEMP_SG1_G3をアクセスし、タスクt56はタスクt55の処理結果である仮想リレーションTEMP_T5_5を用いてタスクtG3SG1の処理結果TEMP_SG1_G3をアクセスする。このため、共通のリレーションTEMP_SG1_G3に対して処理を行うタスクとして扱い、新たにグループG5を作成する。
さらに、結合演算タスクt16の処理結果に対して処理を行うタスクt17は射影演算であるので、結合演算タスクt16と射影演算のタスクt17を組み合わせてタスクt17' を作成し、結合演算タスクt26の処理結果に対して処理を行うタスクt27 は射影演算であるので、結合演算タスクt26と射影演算のタスクt27を組み合わせてタスクt27' を作成し、結合演算タスクt36の処理結果に対して処理を行うタスクt37 は射影演算であるので、結合演算タスクt36と射影演算タスクt37を組み合わせてタスクt37' を作成し、結合演算タスクt56の処理結果に対して処理を行うタスクt57 は射影演算であるので、結合演算タスクt56と射影演算のタスクt57を組み合わせてタスクt57' を作成すると、グループG5にこれらの結合演算と射影演算を組み合わせたタスクt17', t27', t37', t57'を加える。
【０１７４】
次に、タスクt45が終了すると、図４−２（ｂ）の処理ツリーP4からわかるように新たに結合演算タスクt46の処理を始めることができるようになる。
タスクt46はタスクt45の処理結果TEMP_T5_4を結合演算の検索元のリレーションとして使用するので、タスクt46はタスクt45の処理結果TEMP_T5_4に対して処理を行うタスクとして新たにグループG6を作成する。さらに、結合演算タスクt46の処理結果に対して処理を行うタスクt47 は射影演算であるので、結合演算タスクt46と射影演算のタスクt47を組み合わせてタスクt47' を作成すると、グループG6にタスクt47'を加える。
【０１７５】
以上のことをまとめると、グループG3内のタスクの処理が終了することによって新たに見出されたタスクt17', t27', t37', t57', t47'は、次のようにグループG5, G6に位置づけられる。
TEMP_SG1_G3:  グループG5 = {t17', t27', t37', t57'}
(t17'): TEMP_T7_1 ← πFNAME,LNAME,BDATE,PNO(TEMP_T4_1|X|SSN=ESSNTEMP_T5_1)
(t27'): TEMP_T7_2 ← πFNAME,LNAME,BDATE,PNO(TEMP_T4_2|X|SSN=ESSNTEMP_T5_2)
(t37'): TEMP_T7_3 ← πFNAME,LNAME,BDATE,PNO(TEMP_T4_3|X|SSN=ESSNTEMP_T5_3)
(t57'): TEMP_T7_5 ← πSSN, FNAME,LNAME, PNO(TEMP_T4_5|X|SSN=ESSNTEMP_T5_5)
TEMP_T5_4:  グループG6 = {t47'}
(t47'): TEMP_T7_4 ← πFNAME,LNAME,PHONE,PNO, HOURS (TEMP_T4_4 |X|SSN=ESSN TEMP_T5_4)
グループG5には、合成射影演算のタスクtG3SG1の処理結果のリレーションTEMP_SG1_G3に対して処理を行うタスクが集められることになり、グループG6には、タスクt45の処理結果TEMP_T5_4のリレーションに対して処理を行うタスクが集められることになる。
【０１７６】
[(c-7)  合成結合演算と合成射影演算を組み合わせたタスクの作成]
次に、グループG5に集められたタスクt17', t27', t37', t57' を次のように共通部分式ごとにサブグループに集める。
TEMP_SG1_G3: グループ G5 = {SG1G5, t57'}
サブグループ  SG1G5 = {t17', t27', t37'}
リレーションTEMP_T5_1, TEMP_T5_2, TEMP_T5_3は、図８に示すように、同一のリレーションであり、リレーションTEMP_T4_1, TEMP_T4_2, TEMP_T4_3は、図６に示すように、リレーションTEMP_SG1_G1のサブセットであるため、タスクt17', t27', t37'は、結合演算の共通部分式に関する定義にしたがって、結合演算の共通部分式を持ったタスクとしてサブグループSG1G5 に集めることにする。
【０１７７】
サブグループSG1G5に結合演算の共通部分式を持ったタスクを集めると、サブグループSG1G5内のタスクt17', t27', t37' に含まれている結合演算を、論理和Ｕを用いて次のように組み合わせて、これらの結合演算タスクのすべての結合条件を満たした１つの合成結合演算を作成する。
(TEMP_T4_1 |X|SSN=ESSN TEMP_T5_1) ∪ (TEMP_T4_2 |X|SSN=ESSN TEMP_T5_2) ∪(TEMP_T4_3 |X|SSN=ESSN TEMP_T5_3)     
【０１７８】
次に、タスクt17', t27', t37'は射影演算も含んでいるので、これらのタスクに含まれる射影演算の属性から、属性の和集合を求めて、得られた属性を含んだ合成射影演算を次のように作成する。
πFNAME,LNAME,BDATE,PNO (…)
さらに、作成した合成結合演算と合成射影演算を組み合わせて、タスクt17', t27', t37'の結合条件を満たし、射影演算のすべての属性を含んだ１つのタスクtG5SG1を次のように作成する。
(tG5SG1): TEMP_SG1_G5 ← πFNAME,LNAME,BDATE,PNO((TEMP_T4_1|X|SSN=ESSNTEMP_T5_1)∪(TEMP_T4_2|X|SSN=ESSN TEMP_T5_2)∪(TEMP_T4_3|X|SSN=ESSNTEMP_T5_3))
合成結合演算と合成射影演算を組み合わせたタスクtG5SG1を作成すると、グループG5内のサブグループを次のように合成結合演算と合成射影演算を組み合わせたタスクで置き換えることにする。
TEMP_SG1_G3: グループG5 = {tG5SG1, t57'}
この合成結合演算と合成射影演算を組み合わせたタスクtG5SG1を含んだグループG5の処理については、次のグループG4処理の後に記述する。グループG3の処理が終了すると、次はグループG4の処理を行うことになる。
【０１７９】
[(d) グループG4の処理]
前述したように、グループG4内のタスクは次のようなものである。グループG4には、射影演算のタスクt61が集められている。
DEPARTMENT:  グループ  G4 = {t61}
(t61): TEMP_T1_6  ← πDNUMBER, DNAME DEPARTMENT
グループG4には１つのタスクしか存在せず、射影演算であるタスクt61の処理のみを直接行うことになる。タスクt61の処理が終了すると、図４−３（ｂ）の処理ツリーP6からわかるように新たに結合演算タスクt64の処理を行うことができるようになる。
タスクt64はタスクt61の処理結果TEMP_T1_6とタスクt63の処理結果TEMP_T3_6に対して結合演算の処理を行うタスクであり、処理結果TEMP_T3_6を検索元のリレーションとして使用するので、リレーションTEMP_T3_6に対して処理を行うタスクとして、新たにグループG7を作成する。
【０１８０】
さらに結合演算タスクt64の処理結果に対して処理を行うタスクt65は射影演算であるため、結合演算タスクt64と射影演算のタスクt65を組み合わせてタスクt65' を作成し、グループG7にタスクt65'を加えることにする。タスクt65'の処理結果は、クエリーQ6の最終の処理結果となるので、RESULT_Q6で表わすことにする。
TEMP_T3_6:  グループG7 = {t65'}
(t65'): RESULT_Q6  ← πSSN, FNAME, LNAME, DNUMBER, DNAME
(TEMP_T1_6 |X|DNUMBER=DNUM TEMP_T3_6)
グループG4の処理が終了すると、次はグループG5の処理を行うことになる。
【０１８１】
［(e) グループG5の処理（合成結合演算と合成射影演算を組み合わせたタスク処理）]
スタティックマルチオペレーション・プロセッシングを使用して、グループG5内の合成結合演算と合成射影演算を組み合わせたタスクtG5SG1及び結合演算と射影演算を組み合わせたタスクt57'の処理を一度に行うことにする。前述したように、グループG5内のタスクは次のようなものである。
TEMP_SG1_G3: グループG5 = {tG5SG1, t57'}
(tG5SG1): TEMP_SG1_G5 ← πFNAME,LNAME,BDATE,PNO((TEMP_T4_1|X|SSN=ESSNTEMP_T5_1) ∪ (TEMP_T4_2|X|SSN=ESSN TEMP_T5_2) ∪ (TEMP_T4_3|X|SSN=ESSN TEMP_T5_3))
(t57'): TEMP_T7_5  ← πSSN, FNAME, LNAME, PNO (TEMP_T4_5|X|SSN=ESSN TEMP_T5_5)
【０１８２】
合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理を行うに当たっては、図６に示したTEMP_SG1_G1(仮想リレーションとしてTEMP_T4_1, TEMP_T4_2, TEMP_T4_3を包含しているタスクtG1SG1の処理結果)と図８に示したTEMP_SG1_G3（同一の仮想リレーションとしてTEMP_T5_1, TEMP_T5_2, TEMP_T5_3を包含しているタスクtG3SG1の処理結果）を使用することになるので、図９に改めてTEMP_SG1_G1とTEMP_SG1_G3を示すことにする。
【０１８３】
[(e-1) アクセスプランの作成]
グループG5内の合成結合演算と合成射影演算を組み合わせたタスクtG5SG1及び結合演算と射影演算を組み合わせたタスクt57'に対して、次のようなアクセスプランを作成する。
plan(tG5SG1):  合成結合演算の処理を行うための特有の手順を用いて合成結合演算と合成射影演算を組み合わせたタスクの処理を行う。
plan(t57'):  仮想リレーションTEMP_T5_5をスキャンして、仮想リレーションTEMP_T4_5が部分的に共有するリレーションTEMP_SG2_G1のインデックスを使用して結合できるレコードを検索し、検索されたレコードから属性SSN, FNAME, LNAME, PNOを射影していく。
【０１８４】
アクセスプランplan(tG5SG1) (タスクtG5SG1の処理方法)を具体的に説明すると、図８及び図９に示している仮想リレーションTEMP_T5_1, TEMP_T5_2, TEMP_T5_3に記録してある情報を用いて、これらの仮想リレーションがリレーションTEMP_SG1_G3に対して共有するブロックを調べて、次のようにそれぞれブロック集合BTEMP_T5_1, BTEMP_T5_2, BTEMP_T5_3に集める。
TEMP_T5_1:  BTEMP_T5_1  = {b1, b2, b3, b4, b5}
TEMP_T5_2:  BTEMP_T5_2  = {b1, b2, b3, b4, b5}
TEMP_T5_3:  BTEMP_T5_3  = {b1, b2, b3, b4, b5}
ここでのb1〜b5は図８及び図９に示したリレーションTEMP_SG1_G3のブロックである。ブロック集合BTEMP_T5_1, BTEMP_T5_2, BTEMP_T5_3を作成すると、これらのブロック集合から次のようにしてブロックの和集合BG5SG1を求める。
BG5SG1 = BTEMP_T5_1 U BTEMP_T5_2 U BTEMP_T5_3  = {b1, b2, b3, b4, b5}
【０１８５】
ブロックの和集合BG5SG1を作成すると、集合BG5SG1に含まれるブロックb1, b2, b3, b4, b5を図９のリレーションTEMP_SG1_G3に対してアクセスしていき、アクセスしたブロックからレコードsを取り出し、図９に示したリレーションTEMP_SG1_G1のインデックス(804)を使用して、r[SSN] = s[ESSN]となるように、レコードsの属性ESSNと同じ値の属性SSNをもつレコードrをリレーションTEMP_SG1_G1から検索する。
レコードrが検索されたときに、レコードrが仮想リレーションTEMP_T4_1内のレコードであり、レコードsが仮想リレーションTEMP_T5_1内のレコードであるならば(TEMP_T4_1|X|SSN=ESSN TEMP_T5_1の結合関係を満たしているならば)、もしくは、レコードrが仮想リレーションTEMP_T4_2内のレコードであり、レコードsが仮想リレーションTEMP_T5_2内のレコードであるならば(TEMP_T4_2|X|SSN=ESSN TEMP_T5_2の結合関係を満たしているならば)、もしくは、レコードrが仮想リレーションTEMP_T4_3内のレコードであり、レコードsが仮想リレーションTEMP_T5_3内のレコードであるならば(TEMP_T4_3|X|SSN=ESSN TEMP_T5_3の結合関係を満たしているならば)、レコードrとレコードsを結合してレコードtを作成する。
レコードtを作成すると、レコードtから属性FNAME,LNAME,BDATE,PNOを射影してレコードuを作成し、レコードuを図９に示すように合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理結果TEMP_SG1_G5に直接加えていくものとする。
【０１８６】
[(e-2) 各タスクの処理コストの計算]
グループG5内の合成結合演算と合成射影演算を組み合わせたタスクtG5SG1, 及び結合演算と射影演算を組み合わせたタスクt57'に対してアクセスプランを作成すると、次のように、アクセスプランをもとに各タスクの処理コストを計算する。
タスクtG5SG1の処理コスト:  
cost(tG5SG1) = |BG5SG1| + (|b1| * (x TEMP_SG1_G1 + 1)) + (|b2| * (x TEMP_SG1_G1 + 1)) + (|b3| * (x TEMP_SG1_G1 + 1)) + (|b4| * (x TEMP_SG1_G1 + 1)) + (|b5| * 
(x TEMP_SG1_G1 + 1)) = 55 (xTEMP_SG1_G1:リレーションTEMP_SG1_G1のインデックスのレベル) 
タスクt57'の処理コスト: 
cost(t57') = bTEMP_T5_5  + (|TEMP_T5_5| * (xTEMP_SG2_G1 + 1)) = 55 (bTEMP_T5_5:仮想リレーションTEMP_T5_5のブロック数, xTEMP_SG2_G1:リレーションTEMP_SG2_G1のインデックスのレベル) 
【０１８７】
合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理コストcost(tG5SG1)は、ブロック集合B G5SG1内の5つのブロックをアクセスする処理コストと、各ブロックbi(i = 1, 2,…,5)内のレコードに対して、リレーションTEMP_SG1_G1のインデックス(804)を用いて結合できるレコードを検索する処理コスト|bi| * (x TEMP_SG1_G1 + 1)を合計した処理コストである。図９で示しているように、リレーションTEMP_SG1_G1のインデックス(804) のレベルxTEMP_SG1_G1は１であり、ブロック集合BSG1には5つのブロックが存在していて、各ブロックには5つのレコードが格納してあるので、タスクtG5SG1の処理コストは、
cost(tG5SG1) = 5 + (5* (1 + 1)) + (5 * (1 + 1)) + (5 * (1 + 1)) + (5 * (1 + 1)) + (5 * (1 + 1)) = 55
となる。
【０１８８】
タスクt57'の処理コストcost(t57')は、仮想リレーションTEMP_T5_5内のブロックをアクセスする処理コストbTEMP_T5_5と、仮想リレーションTEMP_T5_5内の各レコードに対して、リレーションTEMP_SG2_G1のインデックス(805)を用いて結合できるレコードを検索する処理コスト|TEMP_T5_5| * (xTEMP_SG2_G1 + 1)を合計した処理コストである。図９に示しているように、仮想リレーションTEMP_T5_5は、リレーションTEMP_SG1_G3から５つのブロックを共有しているので、仮想リレーションTEMP_T5_5をスキャンする処理コストbTEMP_T5_5は５である。また、図９に示しているように、リレーションTEMP_SG2_G1のインデックス(805) のレベルx TEMP_SG2_G1は１であるので、タスクt57'の処理コストは、
cost(t57') = 5 + (25 * (1 + 1)) = 55 となる。
【０１８９】
[(e-3) アクセスするブロックの順番の決定]
以上のようにタスクtG5SG1, t57'に対して、処理コストを計算すると、処理コストをもとにこれらのタスクを処理コストの小さい順番で並べ替えると次のようになる。(この場合、２つの処理コストはともに55で同じである)。
sort(tG5SG1, t57') ⇒ (tG5SG1, t57')
グループ内のタスクを処理コストの小さい順番で並び替えると、タスクtG5SG1, t57'がリレーションTEMP_SG1_G3からアクセスする必要のあるブロックを集合BG5SG1, B57'に集めることにする。タスクt G5SG1がリレーションTEMP_SG1_G3からアクセスするブロックは、アクセスプランplan(tG5SG1)を作成したときに見出したブロック集合BG5SG1を使用することになる。タスクt57' がリレーションTEMP_SG1_G3からアクセスするブロックは、仮想リレーションTEMP_T5_5に記録してある情報をもとにして調べることになる。
タスクt G5SG1に対するブロック集合: BG5SG1 = {b1, b2, b3, b4, b5}
タスクt57'に対するブロック集合: B57'  = {b1, b2, b3, b4, b5}
【０１９０】
各タスクに対してアクセスする必要のあるすべてのブロックを割り出すと、処理コストの小さいタスクからアクセスする必要のあるブロックから順番にブロックの和集合を求める。
TB0  = {}
タスクt G5SG1に対応するブロック集合B G5SG1との和集合:        
TBG5SG1 = TB0 U BG5SG1 = {b1, b2, b3, b4, b5}
タスクt57'に対応するブロック集合B57'との和集合:              
TB57' = TBG5SG1 U B57'  = {b1, b2, b3, b4, b5}
TB0〜TB57'から、タスクtG5SG1, t57'は図９に示したリレーションTEMP_SG1_G3内のすべてのブロック上で処理を行う必要があることがわかる。リレーションTEMP_SG1_G3からブロックをb1〜b5の順番でアクセスしていき、各ブロックにおいて、それぞれのタスクのアクセスプランにもとづいて、タスクtG5SG1, t57'の処理を一度に行っていくことになる。
【０１９１】
[(e-4) 共通ブロックでのタスクの処理]
最初に、図９に示したリレーションTEMP_SG1_G3のブロックb1から１番目のレコードs1(1123343444, 1) (属性ESSN=1123343444, 属性PNO=1)を取り出し、合成結合演算タスクtG5SG1のために、属性SSNの値が1123343444であるレコードを図９に示したリレーションTEMP_SG1_G1のインデックス(804)を使用して検索し、リレーションTEMP_SG1_G1のブロックb2に格納してあるレコードr1(1123343444,Ramesh, Borg,Mar-29-1966)を見つける。
レコードr1を見つけると、レコードr1は仮想リレーションTEMP_T4_2内のレコードであり、レコードs1は仮想リレーションTEMP_T5_2内のレコードであり、TEMP_T4_2|X|SSN=ESSN TEMP_T5_2の結合関係を満たすことになるので、レコードr1とレコードs1を結合してレコードt1(1123343444,Ramesh, Borg,Mar-29-1966, 1123343444,1)を作成し、レコードt1から属性FNAME, LNAME, BDATE, PNOを射影してレコードu1(Ramesh, Borg,Mar-29-1966,1) を作成し、レコードu1を図９に示した合成結合演算タスクtG5SG1の処理結果TEMP_SG1_G5に加えることになる。
続けて、レコードs1を使用して、タスクt57'のために、属性SSNの値が1123343444であるレコードを図９に示したリレーションTEMP_SG2_G1のインデックス(805)を使用して検索すると、そのようなレコードが見つからないため、図９に示したタスクt57'の処理結果TEMP_T7_5にレコードは加えることはできない。
【０１９２】
次に、図９に示したリレーションTEMP_SG1_G3のブロックb1から2番目のレコードs2(1223445455, 2) (ESSN=1223445455, PNO=2)を取り出し、タスクtG5SG1のために属性SSNの値が1223445455であるレコードをリレーションTEMP_SG1_G1のインデックス(804)を使用して検索し、TEMP_SG1_G1のブロックb4に格納してあるレコードr2(1223445455, Jannifer, Wallace, May-31-1972)を見つける。
レコードr2を見つけると、レコードr2は仮想リレーションTEMP_T4_3内のレコードであり、レコードs2は仮想リレーションTEMP_T5_3内のレコードであり、TEMP_T4_3|X|SSN=ESSN TEMP_T5_3の結合関係を満たすことになるので、レコードr2とレコードs2を結合してレコードt2(1223445455, Jannifer, Wallace, May-31-1972, 1223445455, 2)を作成し、レコードt2から属性FNAME, LNAME, BDATE, PNOを射影し、レコードu2(Jannfer, Wallace, May-31-1972, 2)を作成し、レコードu2を図９に示したタスクtG5SG1の処理結果TEMP_SG1_G5に加えることになる。
続けて、レコードs2を使用してタスクt57'のために、属性SSNの値が1223445455であるレコードをリレーションTEMP_SG2_G1のインデックス(805)を使用して検索すると、そのようなレコードが見つからないので、タスクt57'の処理結果TEMP_T7_5にはレコードは加えることはできない。
【０１９３】
次に、図９に示したリレーションTEMP_SG1_G3のブロックb1から3番目のレコードs3(2311111132,12)を取り出し、タスクtG5SG1のために属性SSNの値が2311111132であるレコードをリレーションTEMP_SG1_G1のインデックスを使用して検索し、TEMP_SG1_G1のブロックb4に格納してあるレコードr3(2311111132, Joyce, Coleman, DEC-12-1978)を見つける。
レコードr3を見つけると、レコードr3は仮想リレーションTEMP_T4_3内のレコードであり、レコードs3は仮想リレーションTEMP_T5_3内のレコードであり、TEMP_T4_3|X|SSN=ESSN TEMP_T5_3の結合関係を満たすことになるので、レコードr3とレコードs3を結合してレコードt3(2311111132, Joyce, Coleman, DEC-12-1978, 2311111132,12)を作成し、レコードt3から属性FNAME, LNAME, BDATE, PNOを射影して、レコードu3(Joyce, Coleman, DEC-12-1978, 12)を作成し、レコードu3をタスクtG5SG1の処理結果TEMP_SG1_G5に加える。
【０１９４】
続けて、レコードs3を使用してタスクt57'のために、属性SSNの値が2311111132であるレコードをリレーションTEMP_SG2_G1のインデックスを使用して検索し、TEMP_SG2_G1のブロックb1に格納してあるレコードv3(2311111132, Joyce, Coleman, 3)を見つける。
レコードv3を見つけると、レコードv3は仮想リレーションTEMP_T4_5内のレコードであり、レコードs3は仮想リレーションTEMP_T5_5内のレコードであり、TEMP_T4_5|X|SSN=ESSN TEMP_T5_5の結合関係を満たすことになるので、レコードv3とレコードs3を結合してレコードw3(2311111132, Joyce, Coleman, 3, 2311111132, 12)を作成し、レコードw3から属性SSN,FNAME, LNAME, PNOを射影し、レコードx3(2311111132, Joyce, Coleman, 12)を作成し、レコードx3を図９に示したタスクt57'の処理結果TEMP_T7_5に加える。
このようにして、リレーションTEMP_SG1_G3のブロックb1内の残りのレコード対しても、レコードs1, s2, s3の処理を行ったのと同じようにして処理を繰り返していく。ブロックb1での処理が終了すると、続けてブロックb2〜b5内のレコードをアクセスし、ブロックb1内で行った処理をブロックb2〜b5においても行うことになる。
図９はスタティック・マルチオペレーション・プロセッシングを使用してグループG5の処理を行っている様子を表している。プロセス(806)は、リレーションTEMP_SG1_G3からブロックをb1〜b5の順番でアクセスして、タスクtG5SG1, t57'の処理を一度に行い、処理結果をTEMP_SG1_G5, TEMP_T7_5に書き込んでいる状況を表わしている。
【０１９５】
[(e-5) 仮想リレーションの作成]
合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理結果TEMP_SG1_G5は、サブグループSG1G5内の結合演算タスクt17', t27', t37'によって部分的に共有されることになる。前述したようにサブグループSG1G5内のタスクは次のようなものである。
サブグループ  SG1G5 = {t17', t27', t37'}
(t17'): TEMP_T7_1  ← πFNAME,LNAME,BDATE,PNO (TEMP_T4_1 |X|SSN=ESSN 
TEMP_T5_1)
(t27'): TEMP_T7_2  ← πFNAME,LNAME,BDATE,PNO (TEMP_T4_2 |X|SSN=ESSN 
TEMP_T5_2)
(t37'): TEMP_T7_3  ← πFNAME,LNAME,BDATE,PNO (TEMP_T4_3 |X|SSN=ESSN 
TEMP_T5_3)
【０１９６】
タスクtG5SG1が使用したリレーションTEMP_SG1_G1内のレコードは属性BDATEの値で整列されていたので、タスクtG5SG1の処理結果TEMP_SG1_G5内のレコードも、属性BDATEの値で整列する。タスクtG5SG1の処理結果TEMP_SG1_G5内のレコードを属性BDATEで整列する理由は、タスクtG5SG1に含まれる検索元の仮想リレーションTEMP_T5_1, TEMP_T5_2, TEMP_T5_3は等しく(TEMP_T5_1≡TEMP_T5_2≡TEMP_T5_3)、検索先の仮想リレーションTEMP_T4_1, TEMP_T4_2, TEMP_T4_3は、リレーションTEMP_SG1_G1のサブセットであり、リレーションTEMP_SG1_G1内のレコードは属性BDATEの値で整列されいて、仮想リレーションTEMP_T4_1, TEMP_T4_2, TEMP_T4_3は、属性BDATEの値をもとにして、リレーションTEMP_SG1_G1内のレコードを部分的に共有していたからである。
【０１９７】
次に、サブグループSG1G5内のタスクt17', t27', t37'に対して、図９に示すような仮想リレーションTEMP_T7_1, TEMP_T7_2, TEMP_T7_3を作成する。仮想リレーションTEMP_T7_1, TEMP_T7_2, TEMP_T7_3は、属性BDATEの値によって整列された合成結合演算タスクtG5SG1の処理結果TEMP_SG1_G5内のレコード及び属性(列)を部分的に共有することになる。そして処理結果TEMP_SG1_G5内のレコードを属性BDATEの値をもとに整列したときに、仮想リレーションが共有する合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理結果のリレーション名、その処理結果から共有するレコードの格納位置(行範囲)、属性の格納位置(列番号)、レコードが格納してあるブロックの番号とアドレスを次のように記録しておくことにする。
TEMP_T7_1 = {リレーション:TEMP_SG1_G5; 行:1〜6; 列: 1〜4; 
ブロック: b1[0, 256],b2[256, 512]};
TEMP_T7_2 ={リレーション:TEMP_SG1_G5; 行:7〜11; 列: 1〜4; 
ブロック: b2[256, 512],b3[512, 768]};
TEMP_T7_3 ={リレーション:TEMP_SG1_G5; 行:10〜20; 列: 1〜4;
ブロック: b3[512, 768],b4[768, 1024],b5[1024, 1280]};
【０１９８】
仮想リレーションTEMP_T7_1は、サブグループSG1G5内のタスクt17'の処理結果であり、属性BDATEの値で整列されたタスクtG5SG1の処理結果TEMP_SG1_G5のブロックb1, b2に格納してある1〜6行までのレコードから列1〜4を共有することになる。
仮想リレーションTEMP_T7_2は、サブグループSG1G5内のタスクt27'の処理結果であり、属性BDATEの値で整列されたタスクtG5SG1の処理結果TEMP_SG1_G5のブロックb2, b3に格納してある7〜11行までのレコードから列1〜4を共有することになる。
仮想リレーションTEMP_T7_3は、サブグループSG1G5内のタスクt37'の処理結果であり、属性BDATEの値で整列されたタスクtG5SG1の処理結果TEMP_SG1_G5のブロックb3〜b5に格納してある10〜20行までのレコードから列1〜4を共有することになる。
【０１９９】
以上のようにして、仮想リレーションTEMP_T7_1, TEMP_T7_2, TEMP_T7_3を作成することによって、結合演算と射影演算を組み合わせたタスクt17', t27', t37'は合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理結果TEMP_SG1_G5を部分的に共有することができるようになる。図９は、属性BDATEの値で整列されたタスクtG5SG1の処理結果TEMP_SG1_G5(803)を、仮想リレーションTEMP_ T7_1, TEMP_ T7_2, TEMP_ T7_3が部分的に共有している様子を表わしている。
このように合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理を行うことによって、タスクtG5SG1に含まれるいくつもの結合演算の処理ために何度も同じレコードを検索する必要がなくなる。またマルチオペレーション・プロセッシングを用いることによって、共通ブロックで処理を行う必要のあるタスクtG5SG1とタスクt57' の処理を一度に行うことができる。
【０２００】
[(e-6) 新たなグループの作成の有無]
マルチオペレーション・プロセッシングを使用してグループG5内の合成結合演算と合成射影演算を組み合わせたタスクtG5SG1及び結合演算と射影演算を組み合わせたタスクt57'の処理が、タスクtG5SG1, t57'の順番で終了すると、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
【０２０１】
最初に、合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理が終了すると、サブグループSG1G5内のタスクt17',t27',t37'の処理が終了することになり、図４−１（ａ），（ｂ），図４−２（ａ）の処理ツリーP1, P2, P3からわかるように、新たにタスクt18, t28, t38の処理ができるようになる。
タスクt18, t28, t38は結合演算タスクであり、それぞれアクセスする仮想リレーションが異なるが、タスクt18はタスクt17'の処理結果である仮想リレーションTEMP_T7_1を用いてタスクtG5SG1の処理結果TEMP_SG1_G5をアクセスし、タスクt28はタスクt27'の処理結果である仮想リレーションTEMP_T7_2を用いてタスクtG5SG1の処理結果TEMP_SG1_G5をアクセスし、タスクt38はタスクt37'の処理結果である仮想リレーションTEMP_T7_3を用いてタスクtG3SG1の処理結果TEMP_SG1_G5をアクセスするので、これらのタスクは共通のリレーションTEMP_SG1_G5に対して処理を行うタスクとして新たにグループG8を作成する。
さらに、結合演算タスクt18の処理結果に対して処理を行うタスクt19は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt18と射影演算のタスクt19を組み合わせてタスクt19' を作成する。
結合演算タスクt28の処理結果に対して処理を行うタスクt29は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt28と射影演算のタスクt29を組み合わせてタスクt29' を作成する。
結合演算タスクt38の処理結果に対して処理を行うタスクt39は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt38と射影演算のタスクt39を組み合わせてタスクt39' を作成して、これらのタスクt19', t29', t39'をグループG8に加えることにする。
【０２０２】
次に、タスクt57'が終了すると、図４−３（ａ）の処理ツリーP5からわかるように、新たにタスクt58の処理を始めることができる。タスクt58は、結合演算タスクであり、タスクt57'の処理結果TEMP_T7_5を結合演算の検索元のリレーションとして使用するので、リレーションTEMP_T7_5に対して処理を行うタスクとして新たにグループG9を作成する。
さらに、結合演算タスクt58の処理結果TEMP_T8_5に対して処理を行うタスクt59は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt58と射影演算のタスクt59を組み合わせてタスクt59'を作成して、タスクt59' をグループG9に加えることになる。
【０２０３】
以上から、グループG8, グループG9は次のようになる。グループG8には、合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理結果TEMP_SG1_G5に対して処理を行うタスクが集められ、グループG9には、タスクt57'の処理結果TEMP_T7_5に対して処理を行うタスクが集められることになる。
TEMP_SG1_G5: グループG8 = {t19', t29', t39'}
(t19'): RESULT_Q1  ← πFNAME,LNAME,BDATE,PNUMBER,PNAME
(TEMP_T2_1|X|PNUMBER=PNOTEMP_T7_1)
(t29'): RESULT_Q2  ← πFNAME,LNAME,BDATE,PNUMBER,PNAME
(TEMP_T2_2|X|PNUMBER=PNOTEMP_T7_2)
(t39'): RESULT_Q3  ← πFNAME,LNAME,BDATE,PNUMBER,PNAME
(TEMP_T2_3|X|PNUMBER=PNO TEMP_T7_3)
TEMP_T7_5: グループG9 = {t59'}
(t59'): RESULT_Q5  ← πSSN,FNAME,LNAME,PNUMBER,PNAME 
(TEMP_T2_5 |X|PNUMBER=PNO TEMP_T7_5)
グループG5の処理が終了すると、次はグループG6の処理を行うことになる。
【０２０４】
[(f) グループG6の処理]
前述したように、グループG6にはリレーションTEMP_T5_4に対して処理を行う結合演算と射影演算を組み合わせたタスクt47'が集められている。
TEMP_T5_4: グループ G6 = {t47'}
(t47'): TEMP_T7_4  ← πFNAME,LNAME,PHONE,PNO,HOURS(TEMP_T4_4|X|SSN=ESSNTEMP_T5_4)
グループG6の処理を行うにあたって、グループG6には１つのタスクしか存在していないのでタスクt47'の処理を直接行うことになる。タスクt47'の処理方法は、結合演算の処理を行った個々のレコードに対して射影演算の処理を行い、射影したレコードをタスクt47'の処理結果TEMP_T7_4に直接加えていくことになる。
【０２０５】
タスクt47'の処理が終了すると、図４−２（ｂ）の処理ツリーP4からわかるように、新たにタスクt48の処理を行うことができるようになる。タスクt48はタスクt42'の処理結果TEMP_T2_4とタスクt47'の処理結果TEMP_T7_4に対して結合演算の処理を行うタスクであり、処理結果TEMP_T7_4を結合演算の検索元のリレーションとして使用することになるので、タスクt48は処理結果TEMP_T7_4に対して処理を行うタスクとして、新たにグループG10を作成する。
さらに、結合演算タスクt48の処理結果TEMP_T8_4に対して処理を行うタスクt49は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt48と射影演算のタスクt49を組み合わせてタスクt49'を作成し、グループG10にタスクt49'を加えると次のようになる。
TEMP_T7_4: グループ  G10 = {t49'}
(t49'): RESULT_Q4  ← πFNAME, LNAME, PHONE, HOURS,PNUMBER,PNAME (TEMP_T2_4 |X|PNUMBER=PNO TEMP_T7_4)
グループG6の処理が終了すると、次はグループG7の処理を行うことになる。
【０２０６】
[(g) グループG7の処理]
前述したようにグループG7にはリレーションTEMP_T3_6に対して処理を行う結合演算と射影演算を組み合わせたタスクt65'が集められている。
TEMP_T3_6: グループ  G7 = {t65'}
(t65'): RESULT_Q6  ← πSSN, FNAME, LNAME, DNUMBER, DNAME (TEMP_T1_6 |X|DNUMBER=DNUM TEMP_T3_6)
グループG7の処理を行うにあたって、グループG7には１つのタスクしか存在しないので、タスクt65'の処理を直接行うことになる。タスクt65'の処理方法は、タスクt65'に含まれるの結合演算の処理を行うことになり、結合演算の処理結果に加えるべきレコードからタスクt65'に含まれる射影演算に指定してある属性のみを射影し、射影したレコードをタスクt65'の処理結果RESULT_Q6に直接加えていくことにする。
タスクt65'の処理が終了すると、図４−３（ｂ）の処理ツリーP6内のすべてのタスク処理が終了し、クエリーQ6の処理が終了する。グループG7の処理が終了すると、次はグループG8の処理を行う。
【０２０７】
[(h) グループG8の処理（マルチオペレーション・プロセッシングによる複数の結合演算タスク処理方法）]
次に、改善方法４のマルチオペレーション・プロセッシングによる複数の結合演算タスク処理方法を用いて、グループG8に集められた結合演算と射影演算を組み合わせたタスクt19', t29', t39'の処理を一度に行うことにする。
前述したように、グループG8内のタスクは次のようなものである。
TEMP_SG1_G5: グループ  G8 = {t19', t29', t39'}
(t19'): RESULT_Q1  ← πFNAME,LNAME, BDATE,PNUMBER,PNAME(TEMP_T2_1|X|PNUMBER=PNO TEMP_T7_1)
(t29'): RESULT_Q2  ← πFNAME,LNAME, BDATE,PNUMBER,PNAME(TEMP_T2_2|X|PNUMBER=PNO TEMP_T7_2)
(t39'): RESULT_Q3  ← πFNAME,LNAME, BDATE,PNUMBER,PNAME(TEMP_T2_3|X|PNUMBER=PNO TEMP_T7_3)
【０２０８】
結合演算と射影演算を組み合わせたタスクt19', t29', t39' の処理を行うに当たっては、図７に示したTEMP_SG1_G2(仮想リレーションとして、TEMP_T2_1, TEMP_T2_2, TEMP_T2_3を包含しているタスクtG2SG1の処理結果)と図９に示したTEMP_SG1_G5(仮想リレーションとして、TEMP_T7_1, TEMP_T7_2, TEMP_T_3を包含しているタスクtG5SG1の処理結果)を使用することになるので、図１０に改めてTEMP_SG1_G2とTEMP_SG1_G5を示すことにする。
【０２０９】
［(h-1) アクセスプランの作成]
グループG8内の各タスクt19', t29', t39'に対して次のようなアクセスプランを作成する。
plan(t19'): 図１０に示した仮想リレーションTEMP_T7_1をスキャンして、リレーションTEMP_SG1_G2のインデックスを使用して結合処理を行い、結合した個々のレコードに対して射影演算の処理を行って、処理結果をRESULT_Q1に加えていく。
plan(t29'): 図１０に示した仮想リレーションTEMP_T7_2をスキャンして、リレーションTEMP_SG1_G2のインデックスを使用して結合処理を行い、結合した個々のレコードに対して射影演算の処理を行って、処理結果をRESULT_Q2に加えていく。
plan(t39'): 図１０に示した仮想リレーションTEMP_T7_3をスキャンして、リレーションTEMP_SG1_G2のインデックスを使用して結合処理を行い、結合した個々のレコードに対して射影演算の処理を行って処理結果をRESULT_Q3に加えていく。
【０２１０】
グループG8内のタスクt19', t29', t39'に対するアクセスプランをもとにして、各タスクの処理コストを計算すると次のようになる。
タスクt19'の処理コスト:  cost(t19') = bTEMP_T7_1 + (|TEMP_T7_1| * (xTEMP_SG1_G2 + 1)) = 2 + (6 * (1 + 1)) = 14 (bTEMP_T7_1:仮想リレーションTEMP_T7_1のブロック数, xTEMP_SG1_G2:リレーションTEMP_SG1_G2のインデックスのレベル)
タスクt29'の処理コスト:  cost(t29') = bTEMP_T7_2 + (|TEMP_T7_2| * (xTEMP_SG1_G2 + 1))= 2 + (5 * (1 + 1)) = 12 (bTEMP_T7_2:仮想リレーションTEMP_T7_2のブロック数)
タスクt39'の処理コスト:  cost(t39') = bTEMP_T7_3 + (|TEMP_T7_3| * (xTEMP_SG1_G2 + 1)) = 3 + (11 * (1 + 1)) = 25 (bTEMP_T7_3:仮想リレーションTEMP_T7_3のブロック数)
【０２１１】
タスクt19'の処理コストは、仮想リレーションTEMP_T7_1をスキャンする処理コストb TEMP_T7_1と仮想リレーションTEMP_T7_1内の各レコードに対してリレーションTEMP_SG1_G2のインデックスを使用して結合できるレコードを検索する処理コスト| TEMP_T7_1| * (x TEMP_SG1_G2 + 1) を合計した処理コストである。図１０からわかるように、仮想リレーションTEMP_T7_1はリレーションTEMP_SG1_G5から２つのブロックを共有するのでbTEMP_T7_1は２となり、リレーションTEMP_SG1_G2の属性PNUMBERに存在するインデックス(900)のレベルx TEMP_SG1_G2は1であるので、タスクt19'の処理コストは
cost(t19') = 2 + (6 * (1 + 1)) = 14
である。
【０２１２】
タスクt29'の処理コストは、仮想リレーションTEMP_T7_2をスキャンする処理コストbTEMP_T7_2と仮想リレーションTEMP_T7_2内の各レコードに対してリレーションTEMP_SG1_G2のインデックスを使用して結合できるレコードを検索する処理コスト|TEMP_T7_2| * (xTEMP_SG1_G2 + 1) を合計した処理コストである。図１０からわかるように、仮想リレーションTEMP_T7_2はリレーションTEMP_SG1_G5から２つのブロックを共有するのでbTEMP_T7_2は２となり、リレーションTEMP_SG1_G2の属性PNUMBERに存在するインデックス(900)のレベルx TEMP_SG1_G2は1であるので、タスクt29'の処理コストは
cost(t29') = 2 + (5 * (1 + 1)) = 12
である。
【０２１３】
タスクt39'の処理コストは、仮想リレーションTEMP_T7_3をスキャンする処理コストbTEMP_T7_3とリレーションTEMP_T7_3内の各レコードに対してリレーションTEMP_SG1_G2のインデックスを使用して結合できるレコードを検索するコスト|TEMP_T7_3| * (xTEMP_SG1_G2 + 1) を合計した処理コストである。図１０からわかるように、仮想リレーションTEMP_T7_3はリレーションTEMP_SG1_G5から３つのブロックを共有するのでbTEMP_T7_3は３となり、リレーションTEMP_SG1_G2の属性PNUMBERに存在するインデックス(900)のレベルx TEMP_T2_3は1であるので、タスクt39'の処理コストは
cost(t39') = 3 + (11 * (1 + 1)) = 25
である。
【０２１４】
[(h-2) アクセスするブロックの順番の決定]
以上のようにタスクt19', t29', t39' に対して、処理コストを計算すると、処理コストをもとに、これらのタスクを処理コストの小さい順番から次のように並べ替える。
sort(t19', t29', t39') ⇒ (t29', t19', t39')
グループ内のタスクを処理コストの小さい順番で並べ替えると、図１０に示した仮想リレーションTEMP_T7_2, TEMP_T7_1, TEMP_T7_3に記録してある情報を参照して、タスクt29', t19', t39'がリレーションTEMP_SG1_G5からアクセスする必要のあるブロックをブロック集合B29', B19', B39'に集めると、次のように各タスクに対応するブロック集合が得られる。
タスクt29' に対して:  B29' = {b2, b3}
タスクt19' に対して:  B19' = {b1, b2}
タスクt39' に対して:  B39' = {b3, b4, b5}
以上のように、各タスクに対応するブロック集合を見出した後に、処理コストの小さいタスクから処理コストの大きいタスクへと順番に、すなわちタスクt29', t19', t39'の順番に各タスクに対応するブロック集合の和集合を求めていくことにする。
【０２１５】
まず、TB0 = {}(空集合)として、TB0とタスクt29'に対応するブロック集合B29'と和集合TB29'を求める。次に、このTB29'とタスクt19'に対応するブロック集合B19'の和集合TB19'を求める。さらに、このTB19'とタスクt39'に対応するブロック集合B39'との和集合TB39'を求めると次のようになる。この場合、和集合を求めるに当たっては、新たに加える集合は和集合の中で最後に加えていくものとする。
TB0 = {}
タスクt29'に対応するブロック集合B29'との和集合:
TB29' = TB0 U B29'  = {b2, b3}
タスクt19'に対応するブロック集合B19'との和集合:
TB19' = TB29' U B19' = {b2, b3, b1}
タスクt39'に対応するブロック集合B39'との和集合:              
TB39' = TB19' U B39' = {b2, b3, b1, b4, b5}
以上のように、処理コストの小さいタスクに対応するブロック集合から処理コストの大きいタスクに対応するブロック集合へと順番に和集合を求めていくと、最後のタスク(処理コストの１番大きいタスク)に対応するブロック集合との和集合TB39'から、ブロックb2からアクセスを開始し、ブロックb5でアクセスを終了すればよいことになり、ディスクにおけるリレーションTEMP_SG1_G5内のブロックへのアクセスの順番を(b2, b3, b1, b4, b5)のように決定することができる。
【０２１６】
前述したブロック集合B29', B19', B39'の中に含まれているブロックを見ると、ブロックb2はタスクt29', t19'を処理するために使用され、ブロックb3はタスクt29', t39'を処理するために使用され、ブロックb1は、タスクt19'を処理するために使用され、ブロックb4, b5は、タスクt39'を処理するために使用されることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。以上のことをまとめると次のような表になる。
【表４】
2008276464.tif 000006
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、タスクt29', t19', t39'に対して作成されたブロック集合B29', B19', B39'の情報にもとづいて、次に記述するような手順を用いればよい。
【０２１７】
[(h-3) 共通ブロックでのタスクの処理]
改善方法４のマルチオペレーション・プロセッシングによる複数の結合演算タスクの処理方法を用いて、グループ内のタスクt19', t29', t39'の処理を行っていく。
最初に、リレーションTEMP_SG1_G5からブロックの相対アドレスが256であるブロックb2をディスクからアクセスし、ブロックb2内のデータをメインメモリに読み込み、グループ内のタスクt29', t19', t39'がブロックb2で処理を行う必要があるかどうかを調べるため、ブロックb2を集合{b2}として表し、この{b2}とブロックの集合B29', B19', B39'との間でそれぞれ積集合(Intersection)を求めると次のようになる。
タスクt29' に対して: B29' ∩ {b2} = {b2}
タスクt19' に対して: B19' ∩ {b2} = {b2}
タスクt39' に対して: B39' ∩ {b2} = {}
【０２１８】
タスクt29', t19'に対する積集合が{b2}となり、タスクt29', t19'がメインメモリに読み込んだブロックb2で処理を行う必要があることが明らかになり、ブロックb2は共通ブロックとなり、共通ブロックb2で各タスクの処理を行うことになる。共通ブロックb2での結合演算タスクt29', t19'の処理は次のようになる。
まず、図１０に示したリレーションTEMP_SG1_G5のブロックb2から最初のレコードs1(Kevin, Singer, JUL-19-1958, 13)(属性PNO=13)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して属性PNUMBERの値が13であるレコードr1(13, ProjectM)をリレーションTEMP_SG1_G2から見つける。そして結合演算タスクt29'を処理するにあたって、レコードr1が仮想リレーションTEMP_T2_2内のレコードであり、レコードs1が仮想リレーションTEMP_T7_2内のレコードであるかを調べる(タスクt29'の処理には、TEMP_T2_2とTEMP_T7_2との結合演算を含むため)。
レコードs1は仮想リレーションTEMP_T7_2に存在しないので結合演算の処理を行うことができず、タスクt29'の処理結果RESULT_Q2にレコードを加えることができない。
次に、タスクt19'を処理するにあたって、レコードr1が仮想リレーションTEMP_T2_1内のレコードであり、レコードs1が仮想リレーションTEMP_T7_1内のレコードであるかを調べる(タスクt19'を処理には、TEMP_T2_1とTEMP_T7_1との結合演算を含むため)。
レコードr1は仮想リレーションTEMP_T2_1に存在しないので、タスクt19'の処理結果RESULT_Q1にレコードを加えないことはできない。
【０２１９】
次に、リレーションTEMP_SG1_G5のブロックb2から２番目のレコードs2(Ahmad, Jabbar, MAR-29-1959, 3)(属性PNO=3)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して、属性PNUMBERの値が3であるレコードを検索し、レコードr2(3, ProjectC)をリレーションTEMP_SG1_G2から見つける。結合演算タスクt29'を処理するにあたって、レコードr2が仮想リレーションTEMP_T2_2内のレコードであり、レコードs2が仮想リレーションTEMP_T7_2内のレコードであるかを調べると、それらの仮想リレーションには存在しないので、タスクt29'の処理結果RESULT_Q2にレコードを加えることはできない。
次に、タスクt19'を処理するにあたって、レコードr2が仮想リレーションTEMP_T2_1内のレコードであり、レコードs2が仮想リレーションTEMP_T7_1内のレコードであるかを調べると、それらの仮想リレーションに存在するので(TEMP_T2_1|X|PNUMBER=PNO TEMP_T7_1の結合関係を満たしているので)、レコードr2とレコードs2を結合し、レコードt2(Ahmad, Jabbar, MAR-29-1959, 3, 3, ProjectC)を作成する。結合したレコードt2から必要な属性FNAME, LNAME, BDATE, PNUMBER, PNAMEを射影して、レコードv2(Ahmad, Jabbar, MAR-29-1959, 3, ProjectC)を作成して、レコードv2をタスクt19'の処理結果のリレーションRESULT_Q1に加えることにする。
【０２２０】
次に、ブロックb2から３番目のレコードs3(Maurith, Jordan SEP-15-1961, 1)(属性PNO=1)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して属性PNUMBERの値が１であるレコードを検索すると、そのレコードは見つからないので、タスクt29'の処理結果RESULT_Q2とタスクt19' の処理結果RESULT_Q1にレコードは加えることはできない。
次に、ブロックb2から４番目のレコードs4(William, Martin, JAN-09-1962, 5)(属性PNO=5)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して属性PNUMBERの値が5であるレコードr4(5, ProjectE)を見つける。結合演算タスクt29'を処理するにあたって、レコードr4が仮想リレーションTEMP_T2_2内のレコードであり、レコードs4が仮想リレーションTEMP_T7_2内のレコードであるかを調べると、レコードr4はTEMP_T2_2には存在しないので、タスクt29'の処理結果RESULT_Q2にレコードを加えることができない。  続けて、タスク t19'を処理するにあたって、レコードr4が仮想リレーションTEMP_T2_1内のレコードであり、レコードs4が仮想リレーションTEMP_T7_1内のレコードであるかを調べると、レコードs4はTEMP_T7_1には存在しないので、タスクt29'の処理結果RESULT_Q2にレコードを加えることができない。
【０２２１】
このようにして、リレーションTEMP_SG1_G5のブロックb2において、タスクt29', t19'の処理を行うにあたって、タスクt29', t19'がリレーションTEMP_SG1_G2に対して検索されたレコードを共に利用することによって、何度も同じレコードを検索する必要がなくなる。共通ブロックb2でのタスクt29', t19の処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、集合B29', B19'と集合{b2}との差集合（Difference）を求める。得られた差集合の値をB29'(1), B19'(1)とすると、次のようになる。
タスクt29' に対して:  B29'  - {b2} = {b3} = B29'(1)
タスクt19' に対して:  B19'  - {b2} = {b1} = B19'(1)
【０２２２】
次に、リレーションTEMP_SG1_G5からブロックの相対アドレスが512であるブロックb3をディスクからアクセスして、ブロックb3内のデータをメインメモリに読み込み、グループ内のタスクt29', t19', t39'がブロックb3で処理を行う必要があるかどうかを調べるために、ブロックb3を集合{b3}として表し、{b3}とブロックの集合B29'(1), B19'(1), B39'との間でそれぞれ積集合を求めると次のようになる。
タスクt29' に対して: B29'(1) ∩ {b3} = {b3}
タスクt19' に対して: B19'(1) ∩ {b3} = {}
タスクt39' に対して: B39' ∩ {b3} = {b3}
タスクt29', t39'に対する積集合が{b3}となり、タスクt29', t39'がメインメモリに読み込んだブロックb3で処理を行う必要があることが明らかになり、ブロックb3は共通ブロックとなり、共通ブロックb3でこれらのタスクの処理を行うことになる。
【０２２３】
図１０に示したリレーションTEMP_SG1_G5のブロックb3におけるタスクt29', t39'の処理は、ブロックb2で行ったタスク処理と同様である。まず、リレーションTEMP_SG1_G5からブロックの相対アドレスが512であるブロックb3をアクセスしてブロックb3内のレコードをメインメモリに読み込み、ブロックb3から最初のレコードs5(Alicia, Zelaya, JUL-19-1964, 14)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して属性PNUMBERの値が14であるレコードr5(14, ProjectN)を見つける。タスクt29'を処理するにあたって、レコードr5が仮想リレーションTEMP_T2_2内のレコードであり、レコードs5が仮想リレーションTEMP_T7_2内のレコードであるかを調べると、それらの仮想リレーションに存在するので(TEMP_T2_2|X|PNUMBER=PNO TEMP_T7_2の結合関係を満たしているので)、レコードr5とレコードs5を結合してレコードt5(Alicia, Zelaya, JUL-19-1964, 14, 14, ProjectN)を作成し、結合したレコードt5から必要な属性FNAME, LNAME, BDATE, PNUMBER, PNAMEを射影してレコードu5(Alicia, Zelaya, JUL-19-1964, 14, ProjectN)を作成し、レコードu5をタスクt29'の処理結果のリレーションRESULT_Q2に加えることにする。続けて、タスクt39'を処理するにあたって、レコードr5が仮想リレーションTEMP_T2_3内のレコードであり、レコードs5が仮想リレーションTEMP_T7_3内のレコードであるかを調べると、それらのレコードは存在しないので、タスクt39'の処理結果RESULT_Q3にレコードを加えることはできない。
次に、リレーションTEMP_SG1_G5のブロックb3から２番目のレコードs6(Ramesh, Borg, MAR-29-1966, 1)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して、属性PNUMBERの値が1であるレコードが見つからないので、タスクt29' の処理結果RESULT_Q2とタスクt39' の処理結果RESULT_Q3にレコードは加えることはできない。
【０２２４】
このようにして、リレーションTEMP_SG1_G5の共通ブロックb3内の残りのレコードに対しても、１番目のレコードと２番目のレコードに対して行った処理を繰り返して行い、 共通ブロックb3でのタスク処理が終了すると、ブロックb3を再びアクセスする必要がなくなるので、集合B29'(1), B39'と集合{b3}との差集合（Difference)を求める。得られた差集合の値をB29'(2), B39'(1)とすると、次のようになる。
タスクt29' に対して: B29'(1)  - {b3} = {} = B29'(2)
タスクt39' に対して: B39'  - {b3} = {b4, b5} = B39'(1)
この結果、集合B29'(2)が空集合({})になってタスクt29'の処理が終了することになり、図４−１（ｂ）に示した処理ツリーP2内すべてのタスクの処理が終了し、クエリーQ2の処理が完了することになる。
【０２２５】
次に、リレーションTEMP_SG1_G5からブロックの相対アドレスが0であるブロックb1をディスクからアクセスして、ブロックb1内のデータをメインメモリに読み込み、すでに処理の済んだタスクt29'を除くグループ内のタスクt19', t39'がブロックb1で処理を行う必要があるかどうかを調べるために、ブロックb1を集合{b1}として表し、{b1}とブロックの集合B19'(2), B39'(1)との間で積集合を求めると次のようになる。
タスクt19' に対して:  B19'(1) ∩ {b1} = {b1}
タスクt39' に対して:  B39'(1) ∩ {b1} = {}
タスクt19'に対する積集合が{b1}となり、タスクt19'がメインメモリに読み込んだブロックb1で処理を行うことが必要となり、ブロックb1は共通ブロックとなる。そして共通ブロックb1において、タスクt19'の結合演算の処理を行う。ブロックb1での処理が終了すると、ブロックb1を再びアクセスする必要がなくなるので、集合B19'(1)と集合{b1}との差集合を求めて、得られた差集合の値をB19'(2)とすると次のようになる。
タスクt19' に対して:  B19'(1)  - {b1} = {} = B19'(2)
【０２２６】
この結果、集合B19'(2)が空集合({})になってタスクt19'の処理が終了することになり、  図４−１（ａ）に示した処理ツリーP1内すべてのタスクの処理が終了し、クエリーQ1の処理が完了することになる。
この段階で、残ったタスクはt39' のみとなるので、リレーションTEMP_SG1_G3から残ったブロックb4, b5をアクセスしてタスクt39' の処理を行って、タスクt39'の処理が終了すると、処理ツリーP3内すべてのタスクの処理が終了することになるので、クエリーQ3の処理は終了することになる。
【０２２７】
以上のように、リレーションTEMP_SG1_G5内のブロックをb2, b3, b1, b4, b5の順番でアクセスすることによって、処理コストの小さいタスクからt29', t19', t39'の順番で処理が終了することになる。図１０は、マルチオペレーション・プロセッシングを使用してグループG8内の複数の結合演算と射影演算を組み合わせたタスクの処理を行っているのを表している。リレーションTEMP_SG1_G5内のブロックをb2, b3, b1, b4, b5の順番でアクセスして、結合演算と射影演算を組み合わせたタスクt29', t19', t39'の処理を一度に行い、処理結果をRESULT_Q1, RESULT_Q2, RESULT_Q3に書き込んでいる様子を表わしている。
【０２２８】
[(i) グループG9の処理] 
前述したように、グループG9にはリレーションTEMP_T7_5に対して処理を行う結合演算と射影演算を組み合わせたタスクt59'が集められている。
TEMP_T7_5:     グループG9 = {t59'}
(t59'): RESULT_Q5  ← πSSN,FNAME,LNAME,PNUMBER,PNAME (TEMP_T2_5|X|PNUMBER=PNOTEMP_T7_5)
グループG9には１つのタスクしか存在しないので、タスクt59'の処理を直接行うことになる。タスクt59'の処理方法は、タスクt59' 内の結合演算の処理を行い、結合演算の処理結果に加えるレコードからタスクt59'の射影演算に指定してある属性のみを射影し、射影したレコードをタスクt59'の処理結果RESULT_Q5に直接加えることになる。タスクt59'の処理が終了すると、図４−３（ａ）の処理ツリーP5内のすべてのタスク処理が終了し、クエリーQ5の処理は完了する。このようにして、グループの処理を繰り返して行っていくうちに、図４−１〜図４−３に示した処理ツリー内のタスクが次第に終了していき、処理ツリーのすべてのタスクの処理が終了すると、与えられたすべてのクエリー処理は終了する。
【０２２９】
[５.実施の結果]
結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシング(以下、改良型の合成関係演算を利用したマルチオペレーション・プロセッシング)を適用したクエリー・プロセッサが、改良前の合成関係演算を利用したマルチオペレーション・プロセッシングを適用したクエリー・プロセッサよりも数多くのクエリーを早く処理することを明確にするために、独自に開発したデータベース・マネージメント・システムのソフトウェアMOP-DBに、新たに改良型の合成関係演算を利用したマルチオペレーション・プロセッシングの処理が行うことができる機能を追加した。
MOP-DBは、MySQLなど市場で幅広く使われているデータベースシステムよりも数多くのクエリーを高速に処理することを目的として設計され、SQLのインタープリタ、クエリーの最適化、トランザクションの同時処理、データを格納するストレージシステムなどデータベース・マネージメント・システム(DBMS)に必要な十分な機能を備えたソフトウェアである。また、実験にはマルチオペレーション・プロセッシングの方法としてスタティックマルチクエリープロセッシング（特願２００６−３５６４０６号参照）を使用することにした。
【０２３０】
独自に開発したMOP-DBに、改良型の合成関係演算を利用したマルチオペレーション・プロセッシングの処理が追加したことによって、MOP-DBは改良型の合成関係演算を利用したマルチオペレーションを用いたクエリー処理、改良前の合成関係演算を利用したマルチオペレーションを用いたクエリー処理、マルチオペレーション・プロセッシングを用いたクエリー処理を行うことができ、これらのクエリー処理方法を自由に選択して実行することが可能になった。
【０２３１】
次にMOP-DBを使用して、これらのクエリー処理方法によるクエリーの処理時間をそれぞれ調べた。さらに市場で幅広く使用されているＭｙＳＱＬのバージョン３と比較するために、共通のクエリー処理を行ってMOP-DBとＭｙＳＱＬの処理時間を調べた。
MOP-DBでクエリー処理のテストを行うには、数多くのレコードを格納した十分に大きいデータベースが必要なため、Windows XP Professionalを搭載した一般のエントリーレベルのパーソナルコンピューター（1つのCeleron CPU 2.53GHzプロセッサ、512MBメインメモリ、 1つの145GBディスク）上に、図１１に示した４つのリレーションEMPLOYEE, DEPARTMENT, WORKS_ON, PROJECTから構成されるデータベースを作成し、それぞれのリレーションに10万件ずつレコードを格納し、合計40万件ほどのレコードをデータベースに加えた。クエリーを効率よく高速に処理するには、リレーションにインデックスが必要であるため、リレーションEMPLOYEE (1201)の主属性SSNに対して主インデックス(1200)を作成し、2次属性PHONEに対して2次インデックス(1202)を作成した。リレーションDEPARTMENT (1205)では、主属性DNUMBERに対して主インデックス(1204)を作成し、２次属性DPHONEに対して２次インデックス(1206)を作成した。リレーションPROJECT (1208)では、主属性PNUMBERに対して主インデックス(1207)を作成し、２次属性PNAMEに対して２次インデックス(1209)を作成した。同様に、MySQLバージョン3を用いた場合にも、４個のリレーションから構成される共通のデータベースを作成し、MOP-DBと同様に、データベース内のリレーションに対してインデックスを加えた。
【０２３２】
次に、データベースサーバーに問い合わせるクエリーは、それぞれのクエリー・プロセッサの処理能力を最大限に利用するために、複雑な検索処理を必要とする数多くの異なるクエリーをSQLで記述した。それらのクエリーは次のような条件や特性を持つものである。
1) 問い合わせるクエリーには、同じクエリーが１つとして含まれないようにするため、すべてのクエリーの検索条件は異なるものにした。また、各クエリーには、演算、属性、変数からなる選択条件をブール演算のAND,ORを組み合わせて、さらに複雑な選択条件を持たせて絞込み検索を行うようにした。
2) クエリー・プロセッサによって十分な結合演算処理が行われるように、各クエリーには２つ以上の結合演算を含むようにした。また、クエリー・プロセッサによって必ず検索結果が得られるように、各クエリーには検索条件がゼロにならない検索条件を与えた。
3) クエリー・プロセッサによってあらゆる種類の処理結果が得られるように、1000件以下の処理結果が得られるクエリー、1000件から１万件の処理結果が得られるクエリー、1万件から5万件の処理結果が得られるクエリー、5万件から10万件の処理結果が得られるクエリーをそれぞれ十分な数ほど(それぞれ25パーセントずつ)データベースに問い合わせた。
4) クエリー・プロセッサによってインデックスを用いた検索が行われるように、検索条件に主インデックスを利用するクエリー、2次インデックスを利用するクエリー、主インデックスと2次インデックスの両方を利用するクエリーを与えた。また、インデックスを利用しないクエリーがインデックスを利用するクエリーと交わって処理されるように、選択条件に主インデックスと2次インデックスの両方を利用しないクエリーも与えた。
【０２３３】
MOP-DBの改良型の合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理、改良前の合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理、マルチオペレーション・プロセッシングを用いたクエリー処理、及びMySQLバージョン３の処理時間を調べるために、データベースサーバーに検索処理を要求するクライアントプログラムを用意し、クライアントプログラムから数多くのSQLで記述されたクエリーをデータベースサーバーに問い合わせて、データベースサーバー上のクエリー・プロセッサによってすべてのクエリーが処理されて、検索結果がクライアントプログラムに返されるまでの時間を測定し、処理時間をもとめた。クライアントコンピューターとデータベースサーバーとの間の通信速度の影響を避けるために、直接、データベースサーバー上でクライアントプログラムを起動させて、検索処理結果が得られるようにした。データベースに問い合わせるために作成したクエリーの数は、100件、200件、300件、 400件、 500件、600件、700件、800件、900件、1000件となるように、徐々に件数を増加させてクエリーの処理時間を測定した。同様に、MySQLバージョン3に対しても、上述した件数と同数のクエリー数を用いて、MySQLのクエリーの処理時間を測定して、MySQLの処理時間とMOP-DBを用いた改良型の合成関係演算を利用したマルチオペレーション・プロセッシング、改良前の合成関係演算を利用したマルチオペレーション・プロセッシング、マルチオペレーション・プロセッシングとの処理時間を比較した。
【０２３４】
図１２は、MOP-DBの改良型の合成関係演算を利用したマルチオペレーション・プロセッシング、改良前の合成関係演算を利用したマルチオペレーション・プロセッシング、マルチオペレーション・プロセッシング、及びMySQLのバージョン3に対して、数多くのクエリーを問い合わせたときに、クエリー数とクエリーの処理時間の関係を比較した結果を図１２（ａ）の表１と図１２（ｂ）のグラフで表わしたものである。
図１２に示した実験結果から、クエリー数が100件から1000件までの件数において、全体的に、改良型の合成関係演算を利用したマルチオペレーション・プロセッシングの処理時間が最も早く、次に改良前の合成関係演算を利用したマルチオペレーション・プロセッシングの処理時間が早く、その次にマルチオペレーション・プロセッシングの処理時間となり、MySQLの処理時間が一番遅いことがわかる。
改良型の合成関係演算を利用したマルチオペレーション・プロセッシングは、クエリー数が100件から500件までは、図１２（ａ）の表から、改良前の合成関係演算を利用したマルチオペレーション・プロセッシングよりも平均して処理時間が2.07倍速くなり、マルチオペレーション・プロセッシングよりも平均して処理時間が3.65倍早くなり、MySQLバージョンよりも平均して処理時間が13.11倍早くなった。クエリー数が600件から1000件まででは、改良型の合成関係演算を利用したマルチオペレーション・プロセッシングは、改良前の合成関係演算を利用したマルチオペレーション・プロセッシングよりも平均して処理時間が2.17倍早くなり、マルチオペレーション・プロセッシングよりも平均して処理時間が3.88倍早くなり、MySQLバージョン3よりも平均して処理時間が14.04倍早くなった。以上のように、改良型の合成関係演算を利用したマルチオペレーション・プロセッシングは
処理速度が改善され、MySQLバージョン３よりも13.11〜14.04倍の処理速度の向上が見られ、クエリー数が増加するにつれて、処理速度が向上していく傾向がある。
【図面の簡単な説明】
【０２３５】
【図１】データベースシステムのアーキテクチャを示す図である。
【図２】クエリー処理のフローチャートである。
【図３−１】データベースのリレーションEMPLOYEEを示す図である。
【図３−２】データベースのリレーションDEPARTMENTを示す図である。
【図３−３】データベースのリレーションPROJECTを示す図である。
【図３−４】データベースのリレーションWORK_ONを示す図である。
【図４−１】（ａ）処理プランP1，（ｂ）処理プランP2の処理ツリーを示す図である。
【図４−２】（ａ）処理プランP3，（ｂ）処理プランP4の処理ツリーを示す図である。
【図４−３】（ａ）処理プランP5，（ｂ）処理プランP6の処理ツリーを示す図である。
【図５】タスクのグループ分けを示す図である。
【図６】マルチオペレーション・プロセッシングによる合成選択演算と合成射影演算を組み合わせたタスク処理を示す図である。
【図７】マルチオペレーション・プロセッシングによる合成選択演算と合成射影演算を組み合わせたタスク処理を示す図である。
【図８】マルチオペレーション・プロセッシングによるタスク処理を示す図である。
【図９】マルチオペレーション・プロセッシングによる合成結合演算と合成射影演算を組み合わせたタスク処理を示す図である。
【図１０】マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理を示す図である。
【図１１−１】実施結果を示すために使用したデータベースのリレーションを示す図である。
【図１１−２】実施結果を示すために使用したデータベースのリレーションを示す図である。
【図１２】実施結果を示す（ａ）表と（ｂ）グラフである。
【図１】
2008276464.tif 000007
【図２】
2008276464.tif 000008
【図３−１】
2008276464.tif 000009
【図３−２】
2008276464.tif 000010
【図３−３】
2008276464.tif 000011
【図３−４】
2008276464.tif 000012
【図４−１】
2008276464.tif 000013
【図４−２】
2008276464.tif 000014
【図４−３】
2008276464.tif 000015
【図５】
2008276464.tif 000016
【図１１−１】
2008276464.tif 000017
【図１１−２】
2008276464.tif 000018
【図１２】
2008276464.tif 000019
【図６】
2008276464.tif 000020
【図７】
2008276464.tif 000021
【図８】
2008276464.tif 000022
【図９】
2008276464.tif 000023
【図１０】
2008276464.tif 000024
【手続補正書】
【提出日】平成19年6月12日(2007.6.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
前記合成関係演算作成手段は、さらに、グループ分けされた前記タスクに複数の結合演算タスクが存在するときに、結合演算タスクを結合演算の共通部分式ごとにサブグループに分け、サブグループに共通のリレーションに対して検索処理を行う結合演算タスクを集め、サブグループに集めた結合演算タスクを、論理和を用いて組み合わせて１つの合成結合演算タスクを作成して処理を行い、前記仮想リレーション作成手段は、前記サブグループに集めた結合演算タスクに対して仮想リレーションを作成するとよい。
前記合成関係演算作成手段における前記論理和を用いて組み合わせた１つの合成結合演算タスクの処理は、合成結合演算タスクに含まれる個々の結合演算が共有する１つの検索元のリレーションに対してアクセスするブロックを和集合による集合に集め、該集合内のブロックをディスクにアクセスし、該ブロックからレコードを取り出し、合成結合演算タスクに含まれる個々の結合演算が共有する１つの検索先のリレーションに対して、結合できるレコードを検索し、レコードが検索されると、ブロックから取り出したレコードと検索されたレコードが合成結合演算タスクに含まれる少なくとも１つの結合演算の結合関係を満たしているならば、合成結合演算タスクの処理結果に該レコードを加えていくことでできる。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
［（ｃ）ステップ３：マルチオペレーション・プロセッシングを用いたグループ内のタスク処理］
ステップ２を用いてグループ内の各サブグループに関して作成された合成結合演算タスクと合成関係演算を組み合わせたタスクに対して、マルチオペレーション・プロセッシングを使用して処理を行う。
このマルチオペレーション・プロセッシングとして、本願の発明者は、ダイナミックマルチオペレーション・プロセッシングとスタティックマルチオペレーション・プロセッシングの２つの処理方法を提案してきた（特願２００６−３５６４０６号参照）が、今回は、スタティック・マルチオペレーション・プロセッシングをマルチオペレーション・プロセッシングとして用いて処理を行っていくことにする。
スタティック・マルチオペレーション・プロセッシングを使って処理を行う場合は、グループ内の合成関係演算タスク、合成関係演算を組み合わせたタスク、及びサブグループに集まらないタスクに対してアクセスプランを作成し、アクセスプランから各タスクの処理コストをもとめ、処理コストの小さいタスクから処理コストの大きいタスクへと順番に処理するために、アクセスするブロックの順位を決定し、その順位にしたがってリレーション内のブロックをアクセスし、このブロックを共通ブロックとして、このブロック上で処理を行う必要のあるグループ内のタスク処理を一度に処理していくことになる。
マルチオペレーション・プロセッシングを用いてグループ内の合成結合演算タスクの処理を行う場合には、次のような合成結合演算の処理を行うための特有の手順を用いて処理を行うことになる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１４６
【補正方法】変更
【補正の内容】
【０１４６】
[(b-3) 各タスクに対応するブロック集合]
グループ内のタスクを処理コストの小さい順番から並び替えると、リレーションPROJECTのインデックスを参照して、タスクt42', tG2SG1, t52'の順番でリレーションPROJECTに対してアクセスする必要のあるすべてのブロックを事前に調べて、それぞれ集合B42', BG2SG1, B52'に集めると次のようになり、各タスクに対応するブロック集合が得られる。
タスクt42'に対するブロック集合: B42' = {b3}
タスクtG2SG1に対するブロック集合: BG2SG1  = {b1, b2, b3, b4}
タスクt52' に対するブロック集合: B52'  = {b1, b2, b3, b4, b5}
このように、各タスクt42', tG2SG1, t52'に対応するブロック集合B44', BG2SG1, B52'を見出すことができるのは、以下に示すような理由にもとづくからである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０２０１
【補正方法】変更
【補正の内容】
【０２０１】
最初に、合成結合演算と合成射影演算を組み合わせたタスクtG5SG1の処理が終了すると、サブグループSG1G5内のタスクt17',t27',t37'の処理が終了することになり、図４−１（ａ），（ｂ），図４−２（ａ）の処理ツリーP1, P2, P3からわかるように、新たにタスクt18, t28, t38の処理ができるようになる。
タスクt18, t28, t38は結合演算タスクであり、それぞれアクセスする仮想リレーションが異なるが、タスクt18はタスクt17'の処理結果である仮想リレーションTEMP_T7_1を用いてタスクtG5SG1の処理結果TEMP_SG1_G5をアクセスし、タスクt28はタスクt27'の処理結果である仮想リレーションTEMP_T7_2を用いてタスクtG5SG1の処理結果TEMP_SG1_G5をアクセスし、タスクt38はタスクt37'の処理結果である仮想リレーションTEMP_T7_3を用いてタスクtG5SG1の処理結果TEMP_SG1_G5をアクセスするので、これらのタスクは共通のリレーションTEMP_SG1_G5に対して処理を行うタスクとして新たにグループG8を作成する。
さらに、結合演算タスクt18の処理結果に対して処理を行うタスクt19は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt18と射影演算のタスクt19を組み合わせてタスクt19' を作成する。
結合演算タスクt28の処理結果に対して処理を行うタスクt29は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt28と射影演算のタスクt29を組み合わせてタスクt29' を作成する。
結合演算タスクt38の処理結果に対して処理を行うタスクt39は射影演算であるので、結合演算タスクと射影演算タスクを同時に取り出して、結合演算タスクt38と射影演算のタスクt39を組み合わせてタスクt39' を作成して、これらのタスクt19', t29', t39'をグループG8に加えることにする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０２２０
【補正方法】変更
【補正の内容】
【０２２０】
次に、ブロックb2から３番目のレコードs3(Maurith, Jordan SEP-15-1961, 1)(属性PNO=1)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して属性PNUMBERの値が１であるレコードを検索すると、そのレコードは見つからないので、タスクt29'の処理結果RESULT_Q2とタスクt19' の処理結果RESULT_Q1にレコードは加えることはできない。
次に、ブロックb2から４番目のレコードs4(William, Martin, JAN-09-1962, 5)(属性PNO=5)を取り出し、リレーションTEMP_SG1_G2のインデックス(900)を使用して属性PNUMBERの値が5であるレコードr4(5, ProjectE)を見つける。結合演算タスクt29'を処理するにあたって、レコードr4が仮想リレーションTEMP_T2_2内のレコードであり、レコードs4が仮想リレーションTEMP_T7_2内のレコードであるかを調べると、レコードr4はTEMP_T2_2には存在しないので、タスクt29'の処理結果RESULT_Q2にレコードを加えることができない。  続けて、タスク t19'を処理するにあたって、レコードr4が仮想リレーションTEMP_T2_1内のレコードであり、レコードs4が仮想リレーションTEMP_T7_1内のレコードであるかを調べると、レコードs4はTEMP_T7_1には存在しないので、タスクt19'の処理結果RESULT_Q1にレコードを加えることができない。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０２３５
【補正方法】変更
【補正の内容】
【０２３５】
【図１】データベースシステムのアーキテクチャを示す図である。
【図２】クエリー処理のフローチャートである。
【図３−１】データベースのリレーションEMPLOYEEを示す図である。
【図３−２】データベースのリレーションDEPARTMENTを示す図である。
【図３−３】データベースのリレーションPROJECTを示す図である。
【図３−４】データベースのリレーションWORK_ONを示す図である。
【図４−１】（ａ）処理プランP1，（ｂ）処理プランP2の処理ツリーを示す図である。
【図４−２】（ｃ）処理プランP3，（ｄ）処理プランP4の処理ツリーを示す図である。
【図４−３】（ｅ）処理プランP5，（ｆ）処理プランP6の処理ツリーを示す図である。
【図５】タスクのグループ分けを示す図である。
【図６】マルチオペレーション・プロセッシングによる合成選択演算と合成射影演算を組み合わせたタスク処理を示す図である。
【図７】マルチオペレーション・プロセッシングによる合成選択演算と合成射影演算を組み合わせたタスク処理を示す図である。
【図８】マルチオペレーション・プロセッシングによるタスク処理を示す図である。
【図９】マルチオペレーション・プロセッシングによる合成結合演算と合成射影演算を組み合わせたタスク処理を示す図である。
【図１０】マルチオペレーション・プロセッシングによる複数の結合演算タスクの処理を示す図である。
【図１１−１】実施結果を示すために使用したデータベースのリレーションを示す図である。
【図１１−２】実施結果を示すために使用したデータベースのリレーションを示す図である。
【図１２】実施結果を示す（ａ）表と（ｂ）グラフである。
【手続補正書】
【提出日】平成19年10月15日(2007.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
結合演算の処理機能の向上を考慮した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするグループ分け手段と、
グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、
前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、
グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備え、
前記タスク取り出し手段は、グループに加えるべきタスクが選択演算タスク又は結合演算タスクであり、該選択演算タスク又は結合演算タスクの処理結果に対して処理を行う次のタスクが射影演算タスクである場合は、該選択演算タスク又は結合演算タスクと該射影演算タスクとを同時に取り出し、選択演算又は結合演算と射影演算を組み合わせたタスクを作成し、
前記合成関係演算作成手段は、さらに、グループ分けされた前記タスクに複数の結合演算タスクが存在するときに、結合演算タスクを結合演算の共通部分式ごとにサブグループに分け、サブグループに共通のリレーションに対して検索処理を行う結合演算タスクを集め、サブグループに集めた結合演算タスクを、論理和を用いて組み合わせて１つの合成結合演算タスクを作成して処理を行い、
前記仮想リレーション作成手段は、前記サブグループに集めた結合演算タスクに対して仮想リレーションを作成する
ことを特徴とするクエリー処理システム。
【請求項２】
請求項１に記載のクエリー処理システムにおいて、
前記合成関係演算作成手段における前記論理和を用いて組み合わせた１つの合成結合演算タスクの処理は、合成結合演算タスクに含まれる個々の結合演算が共有する１つの検索元のリレーションに対してアクセスするブロックを和集合による集合に集め、該集合内のブロックをディスクにアクセスし、該ブロックからレコードを取り出し、合成結合演算タスクに含まれる個々の結合演算が共有する１つの検索先のリレーションに対して、結合できるレコードを検索し、レコードが検索されると、ブロックから取り出したレコードと検索されたレコードが合成結合演算タスクに含まれる少なくとも１つの結合演算の結合関係を満たしているならば、合成結合演算タスクの処理結果に該レコードを加えていく
ことを特徴とするクエリー処理システム。
【請求項３】
請求項１又は２に記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、さらに、グループに選択演算又は結合演算と射影演算とを組み合わせた複数のタスクが存在するときに、
選択演算と組み合わせた該複数のタスクを、それぞれのタスクに含まれる選択演算をもとにして、選択演算の共通部分式ごとにサブグループに分け、サブグループに選択演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの選択条件を満たした合成選択演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成選択演算と合成射影演算を組み合わせた１つのタスクを作成するか、又は、
結合演算と組み合わせた該複数のタスクを、それぞれのタスクに含まれる結合演算をもとにして、結合演算の共通部分式ごとにサブグループに分け、サブグループに結合演算と射影演算を組み合わせたタスクを集め、これらの組み合わせたタスクの結合条件を満たした合成結合演算を作成し、射影演算のすべての属性を含んだ合成射影演算を作成し、合成結合演算と合成射影演算を組み合わせた１つのタスクを作成し、
前記仮想リレーション作成手段は、前記組み合わせた選択演算又は結合演算と射影演算のタスクに対して仮想リレーションを作成する
ことを特徴とするクエリー処理システム。
【請求項４】
請求項１〜３のいずれかに記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段は、１つのグループ内に複数の結合演算タスクが存在するときに、該複数の結合演算タスクが、結合条件に同一の属性を用いて、検索元の仮想リレーションと検索先の仮想リレーションに対して結合演算の処理を行うタスクであり、結合演算の検索元の仮想リレーションは１つの共通の検索元のリレーションに属し、該結合演算の検索先の仮想リレーションは１つの共通の検索先のリレーションに属しているならば、該結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行う
ことを特徴とするクエリー処理システム。
【請求項５】
請求項４に記載のクエリー処理システムにおいて、
前記マルチオペレーション・プロセッシング手段が、グループ内の結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行うときは、
共通ブロックから取り出したレコードと結合関係を満たすレコードを共通の検索先であるリレーションに対して検索し、検索したレコードと共通ブロックから取り出したレコードを結合し、
共通ブロックで処理を行う必要のあるグループ内の個々の結合演算タスクに対して、その結合演算タスクが使用する検索先の仮想リレーションに検索されたレコードを含んでいて、その結合演算タスクが使用する検索元の仮想リレーションに共通ブロックから取り出したレコードを含んでいるならば、結合されたレコードをその結合演算タスクの処理結果に加える
ことを特徴とするクエリー処理システム。
【請求項６】
請求項１〜５のいずれかに記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項７】
請求項１〜５のいずれかに記載のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
上述の目的を達成するために、本発明は、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするグループ分け手段と、グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備え、前記タスク取り出し手段は、グループに加えるべきタスクが選択演算タスク又は結合演算タスクであり、該選択演算タスク又は結合演算タスクの処理結果に対して処理を行う次のタスクが射影演算である場合は、該選択演算タスク又は結合演算タスクと該射影演算タスクとを同時に取り出し、選択演算又は結合演算と射影演算を組み合わせたタスクを作成し、前記合成関係演算作成手段は、さらに、グループ分けされた前記タスクに複数の結合演算タスクが存在するときに、結合演算タスクを結合演算の共通部分式ごとにサブグループに分け、サブグループに共通のリレーションに対して検索処理を行う結合演算タスクを集め、サブグループに集めた結合演算タスクを、論理和を用いて組み合わせて１つの合成結合演算タスクを作成して処理を行い、前記仮想リレーション作成手段は、前記サブグループに集めた結合演算タスクに対して仮想リレーションを作成することを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】削除
【補正の内容】
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
前記マルチオペレーション・プロセッシング手段は、１つのグループ内に複数の結合演算タスクが存在するときに、該複数の結合演算タスクが、結合条件に同一の属性を用いて、検索元の仮想リレーションと検索先の仮想リレーションに対して結合演算の処理を行うタスクであり、結合演算の検索元の仮想リレーションは１つの共通の検索元のリレーションに属し、該結合演算の検索先の仮想リレーションは１つの共通の検索先のリレーションに属しているならば、該結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行うとよい。
前記マルチオペレーション・プロセッシング手段が、グループ内の結合演算タスクが必要とするレコードの検索処理とレコードの結合処理を一度に行うときは、共通ブロックから取り出したレコードと結合関係を満たすレコードを共通の検索先であるリレーションに対して検索し、検索したレコードと共通ブロックから取り出したレコードを結合し、共通ブロックで処理を行う必要のあるグループ内の個々の結合演算タスクに対して、その結合演算タスクが使用する検索先の仮想リレーションに検索されたレコードを含んでいて、その結合演算タスクが使用する検索元の仮想リレーションに共通ブロックから取り出したレコードを含んでいるならば、結合されたレコードをその結合演算タスクの処理結果に加えるとよい。
上述のクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやそのプログラムを記録した記録媒体も本発明である。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
［（ｄ−３）合成結合演算と合成射影演算を組み合わせたタスクの処理結果を共有する仮想リレーション］
合成関係演算を利用したマルチオペレーション・プロセッシングによって得られた合成結合演算と合成射影演算を組み合わせたタスクの処理結果は、サブグループ内すべての結合演算と射影演算を組み合わせたタスクの処理結果を含んでいるので、サブグループ内のタスクは、合成結合演算と合成射影演算を組み合わせたタスクの処理結果のリレーションを部分的に共有することになる。そのため合成結合演算と合成射影演算を組み合わせたタスクの処理結果のリレーションは、タスクに含まれる合成結合演算に使用された検索先のリレーション又は検索元のリレーション内のレコードを整列している属性と同じ属性で整列し、サブグループ内の個々の結合演算と射影演算を組み合わせたタスクに対して、それぞれタスクの処理結果を示す仮想リレーションを作成し、その仮想リレーションに、仮想リレーションが部分的に共有する合成結合演算と合成射影演算を組み合わせたタスクの処理結果のリレーション名、その処理結果を共有するレコードの格納位置(レコードの行範囲、レコードが格納してあるブロックの番号とアドレス)と属性の格納位置(属性の列番号)などの情報を記録しておく。
以上のように仮想リレーションを作成すると、サブグループ内の関係演算を組み合わせたタスクは、合成関係演算を組み合わせたタスクの処理結果のリレーションを部分的に共
有していることを明記することができ、このことによって、サブグループ内の個々の関係演算を組み合わせたタスクに対して、レコードの選択範囲、結合範囲、属性(列)の重なっている処理結果のリレーションをディスク上に別々に作成する必要がなくなり、ディスクをアクセスする回数を減らし、クエリーの処理速度を向上させることが可能になる。