(57)【要約】【課題】クエリーの処理速度を向上させる。【解決手段】クエリーの問い合わせが入力される（S110）と、関係演算で構成された処理ツリーに変換され（S120)、直接的に処理することのできるタスクを見つける（S130）。タスクを見つけると、共通のリレーションをアクセスするグループがグループ列に存在するかどうかを調べ（S140)、共通のリレーションをアクセスするグループがグループ列に存在しているならば、そのグループにタスクを加える（S150)。存在していない場合は、新たなグループを作成する(S160)。  グループ内の共通部分式を持つタスクは、さらにサブグループに集め(S170)、サブグループにタスクを集めると、サブグループ内のタスクをもとに合成関係演算タスクを作成する(S180)。グループ内の合成関係演算タスク等の処理を一度に行う(S190)。合成関係演算タスクの処理が終了すると、サブグループ内のタスクに対して仮想リレーションを作成して、合成関係演算タスクの処理結果として得られたリレーションを部分的に共有できるようにする(S200)。【選択図】図２
2008234495.tif 000002
【特許請求の範囲】
【請求項１】
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするクループ分け手段と、
グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、
前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、
グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段と
を備えることを特徴とするクエリー処理システム。
【請求項２】
請求項１記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、サブグループに集めた複数の選択演算タスクで使用する属性名と属性数が等しいときに、それらの属性の中の１つの属性に関する選択条件だけが異なった条件かまたは同じ条件であり、それ以外の属性に関する選択条件はまったく同じであるならば、それらの選択条件をブール演算のＯＲを使用して接続し、接続した選択条件から選択範囲の重複した部分を取り除くために、簡潔化して最適化した選択条件を作成し、その選択条件を用いて複数の選択演算タスクの合成関係演算を作成することを特徴とするクエリー処理システム。
【請求項３】
請求項１記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、サブグループに集めた複数の射影演算タスクが、共通のリレーションに対して射影演算の処理を行うならば、これらの射影演算タスクの属性の和集合を求めて得られた属性を用いて、複数の射影演算タスクの合成関係演算を作成することを特徴とするクエリー処理システム。
【請求項４】
請求項１〜３のいずれかに記載のクエリー処理システムにおいて、
前記仮想リレーション作成手段は、仮想リレーションのレコードに対してタスクが検索処理を行う場合、仮想リレーションが部分的に共有するリレーションの検索に使用する属性に対して、インデックスを作成することを特徴とするクエリー処理システム。
【請求項５】
請求項１〜４のいずれかに記載のクエリー処理システムにおいて、
前記グループ分け手段は、前記合成関係演算タスクの処理結果として得られたリレーションごとにも、タスクをグループ分けすることを特徴とするクエリー処理システム。
【請求項６】
請求項１〜５のいずれかに記載の合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項７】
請求項１〜５のいずれかに記載のマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースのクエリー処理システムに関し、特に、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリーの処理に関するものである。
【背景技術】
【０００２】
データベース・マネージメント・システム（ＤＢＭＳ）に、一度に数多くのクエリーが問い合わせられると、データベース・マネージメント・システムは、トランザクションの同時処理制御機能を使用して、それぞれの問い合わせ処理を行っている。検索のみのトランザクションはクエリーと呼ばれ、データベース・マネージメント・システムは、問い合わせのあったクエリーを別々に処理しているが、この方法には次のような問題点がある。
【０００３】
問題点（１）：従来のデータベース・マネージメント・システムによるクエリー処理方法は、多くのクエリーが共通のリレーションに対して処理を行うと、ディスクから同じデータが何度もメインメモリに読み込まれてアクセスされ、アクセスするたびにブロック内のデータが繰り返しメインメモリに読み込まれて処理が行われる。このため、効率的ではなくクエリーの処理速度が低下するといった問題がある。
【０００４】
問題点（２）：従来のデータベース・マネージメント・システムによるクエリー処理方法は、クエリー内のタスク処理を行うたびに、クエリーの中間結果であるタスクの処理結果のリレーションをディスク上に作成している。それぞれのタスクの処理結果では、レコードや属性の選択範囲が重なっているため、ディスク上にレコードや属性の選択範囲の重なっている処理結果のリレーションを数多く作成することになる。このため、ディスクをアクセスする回数が多くなり、クエリーの処理速度が低下するといった問題がある。
【０００５】
問題点（３）：従来のデータベース・マネージメント・システムによるクエリー処理方法は、クエリーに含まれる結合演算の処理を行うとき、ハッシュ結合などの結合方法を用いている。このため、結合演算の処理を行うたびに、結合演算に使用する検索先のリレーション内のレコードをディスクからアクセスして、メインメモリ内にハッシュテーブル（ハッシュテーブルを検索先のリレーション内のレコードのインデックスとして使用する）を作成することになるので、ディスクをアクセスする回数が多くなり、クエリーの処理速度が低下するといった問題がある。
【０００６】
また、それぞれの結合演算に使用される検索先のリレーションは異なるので、個々の結合演算に対して別々にハッシュテーブルを作成する必要があり、一度に数多くのハッシュテーブルをメインメモリに作成すると、メインメモリに十分なスペースを確保することができなくなり、クエリーの処理速度が低下するといった問題が起こる。
【０００７】
（演算と演算結果のキャッシングの問題点）
ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させるために、問い合わせの多いクエリーとクエリーの処理結果、クエリーに含まれる演算（選択演算，射影演算，結合演算などの関係代数）と演算の処理結果（クエリーの中間結果）を一時的にディスクに保存（キャッシング）しておく方法がよく用いられている。ユーザからクエリーの問い合わせがあると、データベース・マネージメント・システムは、問い合わせのあったクエリーと同じクエリーの処理結果がディスクに保存されているかどうかを調べて、保存されているならば、そのクエリーの処理を行わずに、保存されているクエリーの処理結果をそのままユーザに返すことになる。また、クエリーは異なるけれども、クエリーに含まれる演算と同じ演算の処理結果がディスクに保存されているならば、データベース・マネージメント・システムは、その演算の処理を行わずに、すでに存在する演算の処理結果を利用してクエリーの処理を行うことになる。
【０００８】
この方法は、保存するクエリーの処理結果、演算の処理結果を増やすことで、同じクエリーや演算の処理を繰り返して行うことなしに、クエリーの処理速度を向上させることを目的としている。しかし、この方法は、問い合わせのあったクエリーやクエリーに含まれる演算がディスクに保存しているものと同じでなければならないため、クエリーや演算が異なる場合は、保存されている処理結果を利用することはできない。また、この方法は、データベースに新たなレコードが加えられるなどしてデータベースが更新されると、保存されている処理結果は古くなるので、データベース・マネージメント・システムは、古くなった処理結果を破棄しなければならない。そのためデータベースの更新がたびたび行われると、その都度、古くなった処理結果を破棄しなければならないので、この方法は効率的ではなくなる。マイクロソフト社のＳＱＬサーバーなどのデータベース・マネージメント・システムは、クエリーの処理速度を維持するために、古くなったクエリーの処理結果をすぐには破棄せずに、しばらく古い処理結果をユーザに返すようにしている。
【０００９】
（メインメモリへのキャッシングの問題点）
ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させるその他の方法は、クエリーを処理するためによくアクセスされるディスク上のブロックの複製をメインメモリに一時的に保存（キャッシング）しておく方法が用いられる。この方法は、ユーザからクエリーの問い合せがあると、データベース・マネージメント・システムは、クエリーを処理するためにディスクからアクセスするブロックの複製がメインメモリに保存されているかどうかを調べて、保存されているならば、メインメモリ内の複製を利用する。
この方法は、メインメモリ内で保存するブロックの容量を増やしておくことで、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させることを目的としている。
【００１０】
しかし、この方法は、ディスク上のブロックとメインメモリ上の複製が同じでなければならないため、ブロック内のデータを変更するときには、ディスク上のブロックとメインメモリ上の複製の両方を更新しておかなければならない。また、クエリーを処理するために数ギガバイト（ＧＢ）もあるようなデータベースのリレーションを線形探索（スキャン）するような場合は、メインメモリに保存されているブロック以外のほとんどのブロックをディスクからアクセスすることになるので有効ではなくなる。
また、オペレーティング・システム自体もこのようなメモリー管理を行っているため、データベース・マネージメント・システムがメインメモリに保存するブロックの容量を増やすと、メインメモリに保存されたはずのブロックがオペレーティング・システムによって仮想メモリー（ディスク）に移動されることなどが起こり、逆にクエリーの処理速度が低下するといった問題が発生する。
【００１１】
（クエリー処理のパイプライン化の問題点）
クエリーの中間結果であるタスクの処理結果のリレーションをディスク上に作成しないで、ディスクをアクセスする回数を減少させてクエリーの処理速度を向上させる方法としては、クエリー処理をパイプライン化した方法が用いられる。
クエリー処理をパイプライン化した方法とは、複数のマイクロプロセッサを備えているコンピュータ・システムにおいて、クエリーに含まれるいくつものタスク処理を複数のマイクロプロセッサを用いてパイプラン化し、個々のタスク処理を並列に処理していく方法である。この方法は、クエリーに含まれる個々のタスクの処理結果はストリーム化され、個々のタスク処理が完全に終了するのを待たずして、部分的に終了したタスクの処理結果に対する次のタスク処理を行っていくものである。しかし、パイプライン化できるタスク処理は、選択演算や射影演算などのタスクに限られ、結合演算などのタスクは、結合演算の前に行われるタスク処理が完全に終了してからではないと処理を始めることができないので、パイプライン化することはできない。また、クエリー処理をパイプライン化した方法は、複数のマイクロプロセッサを搭載してあるコンピュータ・システムが必要であるので、マイクロプロセッサを１つしか備えていないコンピュータ・システムでは有効ではない。
【００１２】
発明者が参考にした参考文献を以下に記載する。
問い合わせの多いクエリーとクエリーの処理結果、クエリーに含まれる演算（選択演算、射影演算、結合演算などの関係代数）と演算の処理結果(クエリーの中間結果) を一時的にディスクに保存(キャッシング)しておくことを記載したものとして、以下に記載する非特許文献１〜６がある。
クエリーを処理するためにアクセスされるディスク上のブロックの複製をメインメモリーに一時的に保存(キャッシング)しておくことを記載したものとして、非特許文献７〜１１がある。
また、クエリー処理のパイプライン化を記載したものとしては、非特許文献１２がある。
【非特許文献１】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
【非特許文献６】TIMOS K. SELLIS. Multiple-Query Optimization. ACM Transactions on Database Systems, Vol. 13, No. 1, Pages 23-52, March 1988.
【非特許文献７】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
【発明の開示】
【発明が解決しようとする課題】
【００１３】
以上に述べたような解決方法は、数多くのデータベース・マネージメント・システムに採用されているが、問題点もあるために必ずしも効率的な方法ではない。
本発明では、これらの解決方法とは別に、独自に考案するクエリーの処理方法を用いて、ディスクをアクセスする回数を減少させ、クエリーの処理速度を向上させる方法を提案する。
【課題を解決するための手段】
【００１４】
上記発明の目的を達成するために、本発明は、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカルソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするクループ分け手段と、グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備えることを特徴とする。
【００１５】
前記合成関係演算作成手段は、サブグループに集めた複数の選択演算タスクで使用する属性名と属性数が等しいときに、それらの属性の中の１つの属性に関する選択条件だけが異なった条件かまたは同じ条件であり、それ以外の属性に関する選択条件はまったく同じであるならば、それらの選択条件をブール演算のＯＲを使用して接続し、接続した選択条件から選択範囲の重複した部分を取り除くために、簡潔化して最適化した選択条件を作成し、その選択条件を用いて複数の選択演算タスクの合成関係演算を作成するとよい。
前記合成関係演算作成手段は、サブグループに集めた複数の射影演算タスクが、共通のリレーションに対して射影演算の処理を行うならば、これらの射影演算タスクの属性の和集合を求めて得られた属性を用いて、複数の射影演算タスクの合成関係演算を作成するとよい。
前記仮想リレーション作成手段は、仮想リレーションのレコードに対してタスクが検索処理を行う場合、仮想リレーションが部分的に共有するリレーションの検索に使用する属性に対して、インデックスを作成するとよい。前記グループ分け手段は、前記合成関係演算タスクの処理結果として得られたリレーションごとにも、タスクをグループ分けするとよい。
上述した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやプログラムを記録した記録媒体も本発明である。
【発明の効果】
【００１６】
独自のタスクに関する共通部分式を定義し、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理を行うことによって、マルチオペレーション・プロセッシングのみを用いたクエリー処理よりも効率よくクエリー処理を行うことができるようになった。
その方法は、グループ内の共通部分式を持つタスクをさらにサブグループに集めて、サブグループに集めたいくつかのタスクを１つの合成関係演算タスクに置き換えて処理を行うことになる。また、サブグループ内の個々のタスクは、仮想リレーションを用いて、合成関係演算タスクの処理結果として得られたリレーションを部分的に共有することになり、従来のクエリー処理のように、選択範囲及び／又は属性の重なっている数多くの処理結果のリレーションをディスク上に別々に作成することがなくなり、ディスクをアクセスする回数を減少させ、クエリーの処理速度が向上させることができた。
【００１７】
また、仮想リレーションのレコードに対してタスクが検索処理を行う場合、仮想リレーションが部分的に共有する合成関係演算タスクの処理結果として得られたリレーションの検索に使用する属性に対して、インデックスを作成することによって、そのインデックスを他のタスクも共有して検索処理を行うことができるようになり、ディスクをアクセスする回数を減少させて、クエリーの処理速度を向上させることができた。
【００１８】
また、合成関係演算タスクの処理結果として得られたリレーションのアクセス領域ごとにも、タスクをグループ分けすることによって、そのリレーションの共通ブロック上でタスク処理を一度に行うことができるようになり、ディスクをアクセスする回数を減少させ、極めて効率的にタスク処理を行うことができるようになった。
実際の処理結果からもわかるように、これまで広く使用されているMySQL.Ver3や以前のマルチオペレーション・プロセッシングのみを用いたクエリー・プロセッサよりも一段と数多くのクエリーの処理を高速に行うことができるようになった。
【発明を実施するための最良の形態】
【００１９】
従来の技術の問題点（１）の解決方法として、ディスクなどの２次記憶装置へのアクセスを減らしてクエリーの処理速度を向上させるために、本発明者も「マルチオペレーション・プロセッシングによるデータベースのクエリー処理の向上」について提案した（特願２００６−３５６４０６号参照）。マルチオペレーション・プロセッシングは、いくつかのタスクが共通のリレーションに対して処理を行うときに、それらのタスクをグループに集め、グループ内の各タスクに対してアクセスプランを作成し、アクセスプランをもとにして、それぞれのタスクによるディスク内のリレーションのブロックへのアクセスから得られる共通ブロック（Common Block）を見つけ、その共通ブロックを使用して、グループに集められたタスクの処理を一度に行うものである。
【００２０】
この方法は、それぞれのタスクごとにディスク内のブロックにアクセスすることを回避して、共通ブロックでいくつかのタスクを一度に処理することによって、クエリー（全体のタスク）の処理速度を向上させることをめざしている。このマルチオペレーション・プロセッシングの処理を行うに当たって、本発明者は、前述の出願において、ダイナミックマルチオペレーション・プロセッシング（Dynamic Multi-Operation Processing）とスタティックマルチオペレーション・プロセッシング（Static Multi-Operation Processing）との２つの処理方法を提案した。
【００２１】
ダイナミックマルチオペレーション・プロセッシングは、グループ内の各タスクに対してアクセスプランを作成し、アクセスプランから各タスクの処理コストを計算し、求められた処理コストを参照して、処理コストの小さいタスクから順番にタスク処理を行うものである。この処理では、当面のタスク（処理コストの小さいタスク）の処理を行うためにアクセスしたブロックにおいて、グループ内の他のタスクも処理を行う必要がある場合は、アクセスしたブロックは共通ブロックとなり、共通ブロックでこれらのタスク処理を一度に行う。当面のタスク処理が終了し、グループ内で次に処理コストの小さいタスクの処理を行うときは、すでにアクセスしたブロックでの当面のタスクを含むグループ内の個々のタスク処理は終了しているので、まだアクセスしていない残りのブロックの中から、次に処理コストの小さいタスク処理を行うために必要とされるブロックをアクセスする。アクセスしたブロックにおいて、グループ内の他のタスク（残りのタスク）も処理を行う必要がある場合は、アクセスしたブロックは共通ブロックとなり、共通ブロックでこれらのタスク処理を一度に行う。このようにしてグループ内の残りのタスクに対しても繰返してタスク処理を行っていくものである。
【００２２】
また、スタティックマルチオペレーションは、グループ内の各タスクからアクセスプランを作成し、アクセスプランから各タスクの処理コストを求め、求めた処理コストを参照して、処理コストの１番小さいタスクから処理コストの１番大きいタスクへと順番にグループ内の各タスクを並べることにする。ここまでは、ダイナミックマルチオペレーション・プロセッシングと同じ手順である。次にデータベースのインデックスを使用して、グループ内の各タスクが、共通のリレーション内のブロックからタスク処理を行うためにアクセスする必要のあるブロックを調べて、各タスクに対応するブロック集合に集める。次に、前に求めた処理コストの小さいタスクから処理コストの大きいタスクまでの順番にしたがって、各タスクに対応するブロック集合の和集合を求めていくことによって、アクセスするブロックの順位を決定する。その順位にしたがって共通のリレーション内のブロックをディスクからアクセスし、このブロックを共通ブロックとして、このブロック上で処理を行う必要のあるグループ内のタスク処理を一度に処理していく方法である。この方法は、アクセスすべきブロック（共通ブロック）の順位にしたがって、和集合、積集合及び差集合などの集合論を用いて、クエリーに含まれる各タスクの処理をきわめて論理的に行うものである。
【００２３】
今回は、上述の問題点（１）の解決方法のさらなる改善と、問題点（２），（３）を解決するため、データベースに問い合わせのあった数多くのクエリーを効率よく処理することができる合成関係演算を利用したマルチオペレーション・プロセッシングを提案する。合成関係演算を利用したマルチオペレーション・プロセッシングは、マルチオペレーション・プロセッシングに独自に定義する合成関係演算を利用した処理方法を加えることによって、前述のマルチオペレーション・プロセッシングを用いたクエリーの処理よりもさらに数多くのタスクの処理を一度に行い、ディスクへのアクセスを少なくして、ユーザから問い合わせのあった数多くのクエリーをすばやく処理していく方法である。
【００２４】
以下で詳しく説明する合成関係演算を利用したマルチオペレーション・プロセッシングは、ユーザから問い合わせがあったクエリーが、クエリーの最適化によってクエリーの処理ツリーが作成されると、処理ツリー上の接点であるタスクをトポロジカルソートの順番で、他のタスクから依存がなく、直接的に処理できるタスクを見つけ、これらのタスクを、それぞれのタスクがアクセスするデータベースのリレーションをもとにグループに分ける。次に、グループ内のタスクをさらに共通部分式ごとにサブグループに集めて、それぞれのサブグループに対して、サブグループ内のタスクをもとに合成関係演算タスクを作成し、マルチオペレーション・プロセッシングを使用して、合成関係演算タスクを含むグループ内のタスクの処理を一度に行うものである。
【００２５】
合成関係演算タスクの処理結果は、サブグループ内の個々のタスクの処理結果のすべてを含んでいるために、サブグループ内のタスクは、合成関係演算タスクの処理結果として得られたリレーションを部分的に共有することになる。
合成関係演算タスクの処理結果を部分的に共有していることを示すために、サブグループ内の個々のタスクに対して格納位置による仮想リレーションを作成し、仮想リレーションに合成関係演算タスクの処理結果を共有するために必要な情報を記録しておく。
合成関係演算タスクが選択演算の場合には、選択条件に使用された属性で整列された処理結果であるリレーションを作成し、仮想リレーションとして、共有する合成関係演算タスクの処理結果のリレーション名、レコードの格納位置（レコードの行範囲、レコードが格納してあるブロックの番号とアドレス）などの情報を記録しておく。
合成関係演算タスクが射影演算の場合には、仮想リレーションとして、共有する合成関係演算タスクの処理結果のリレーション名、属性の格納位置(列番号)などの情報を記録しておく。
仮想リレーションにこれらの情報を記録しておくことによって、仮想リレーションを用いて処理を行うタスクは、合成関係演算タスクの処理結果の中から必要なレコードをすばやく取り出すことができるようになる。このように、合成関係演算を利用したマルチオペレーション・プロセッシングは、サブグループに集められたいくつかのタスクを１つの合成関係演算タスクに置き換えて処理を行い、サブグループ内の個々のタスクは、仮想リレーションを通して、合成関係演算タスクの処理結果のリレーションを部分的に共有することになる。このため、サブグループ内の個々のタスクの間で選択範囲及び／又は属性列の重なっているレコードを含んだ処理結果のリレーションをディスク上に別々に作成する必要がなくなり、ディスクをアクセスする回数を減らすことができるようになり、そのことによってクエリーの処理速度を向上させることが可能となる。
【００２６】
また、仮想リレーションのレコードに対してタスクが検索処理を行う場合は、仮想リレーションが部分的に共有する、合成関係演算タスクの処理結果として得られたリレーションの検索に使用する属性に対して、インデックスを作成しておく。そのことによって、共通の属性を用いて検索処理を行う他のタスクもインデックスを共有してレコードを検索することができるようになり、従来のハッシュ法を用いた結合演算処理のように、それぞれの結合演算タスクに対してメインメモリ内にハッシュテーブルを別々に作成する必要がなくなり、ディスクをアクセスする回数を減少させて、クエリーの処理速度を向上させることが可能となる。
さらに、仮想リレーションを用いて合成関係演算タスクの処理結果に対して処理を行うタスクは、仮想リレーションをもとにしてグループ分けをするのではなく、（仮想リレーションを包含している）合成関係演算タスクの処理結果として得られるリレーションをもとにグループ分けを行って、マルチオペレーション・プロセッシングを使用してこれらのタスク処理を一度に行うものとする。マルチオペレーション・プロセッシングを使用してこれらのタスク処理を一度に行うことによって、合成関係演算タスクの処理結果得られたリレーションは、何度もアクセスされることがなくなり、クエリーの処理速度を向上させることが可能となる。
以上に述べた方法を用いてクエリーからのタスク処理を行うことによって、合成関係演算を利用したマルチオペレーション・プロセッシングは、マルチオペレーション・プロセッシングだけを用いたタスク処理よりも、効率よくタスク処理を一度に行うことができるようになり、ディスクをアクセスする回数を減少させて、クエリーの処理速度を向上させることが可能となる。
【００２７】
以下で、図面を参照して、本発明の実施形態について詳しく説明する。
まず、本発明の合成関係演算を利用したマルチオペレーション・プロセッシングの概要を説明する。
【００２８】
［１．合成関係演算を利用したマルチオペレーション・プロセッシング］
合成関係演算を利用したマルチオペレーション・プロセッシングは、ユーザから問い合わせのあったクエリーがクエリーの最適化によって、関係代数で構成された処理ツリーに変換されると、処理ツリー上の接点であるタスクをトポロジカルソートの順番で、他のタスクから依存がなく、直接的に処理できるタスクを見つける。そして、これらのタスクを、それぞれのタスクがアクセスするデータベースのリレーションをもとにグループ分けを行い、さらにグループ内のタスクを共通部分式ごとにサブグループに集めて、それぞれのサブグループに対して、サブグループ内のタスクをもとに合成関係演算タスクを作成する。その後、マルチオペレーション・プロセッシングを使用して合成関係演算タスクを含むグループ内のタスクの処理を一度に行うものである。
【００２９】
［１−１．データベースシステムのアーキテクチャ］
図１は、本文で説明したクエリーの処理方法を用いたデータベースシステムのアーキテクチャの例である。ここで示した構成は、基本的に、上述した本発明者が出願した特願２００６−３５６４０６号の図１と同様のものである。
図１において、クエリーQ1〜Q6をユーザから問い合わせのあったクエリーとして扱い、データベースのアーキテクチャを説明していくことにする。クエリーQ1〜Q6は、クエリー・オプティマイザー（問い合わせ最適化処理）(900)によって最適化され、関係代数で構成された処理ツリーP1〜P6(902)に変換される。クエリー・プロセッサ(901)は、クエリー・オプティマイザー(900)とマルチオペレーション・プロセッサ（マルチオペレーション・プロセッシングを行うプロセッサ）(905)を制御している。
クエリーの一連の処理を行うクエリー・プロセッサ(901)は、処理ツリーP1〜P6からトポロジカルソートの順番で、他のタスクから依存がなく、直接的に処理できるタスクt11，t13，t17，t19，t21，t23，t24，t31，t32，t41，t42，t51，t52，t61，t63(903)を見つける。次に、クエリー・プロセッサは、これらの直接的に処理できるタスクをそれぞれのタスクがアクセスするデータベースのリレーションをもとにしてグループG1〜G4に分ける。タスクt13，t21，t32，t41，t51，t63をグループG1に集め、タスクt11，t23，t31，t61をグループG2に集め、タスクt17，t24をグループG3に集め、タスクt19，t42，t52をグループG4に集める。
【００３０】
グループにタスクを集めると、クエリー・プロセッサは、共通部分式を持つタスクをさらにサブグループに集める。タスクt13，t32，t63をサブグループSG1G1集め、タスクt41，t51をサブグループSG2G1に集め、タスクt23，t31をサブグループSG1G2に集め、タスクt17，t24をサブグループSG1G3に集めることになる。クエリー・プロセッサは、サブグループにタスクを集めると、サブグループに対して合成関係演算タスクを作成する。
サブグループSG1G1に対して合成関係演算タスクtG1SG1を作成し、サブグループSG2G1に対して合成関係演算タスクtG1SG2を作成し、サブグループSG1G2に対して合成関係演算タスクtG2SG1を作成し、サブグループSG1G3に対して合成関係演算タスクtG3SG1を作成する。合成関係演算タスクを作成すると、クエリー・プロセッサは、グループG1〜G4をグループ列（キュー）(904)に挿入する。
【００３１】
グループの処理を行うマルチオペレーション・プロセッサ(905)は、利用できるプロセスの数（ここでは例として４つのプロセスを用意している）にしたがって、グループ列（キュー）からグループG1〜G4を取り出し、用意しているそれぞれのプロセスにマルチオペレーション・プロセッシングを使用してグループの処理を行わせる。ここでは、プロセス１がグループG1の処理を行い、プロセス２がグループG2の処理を行い、プロセス３がグループG3の処理を行い、プロセス４はグループG4の処理を行うことにする。これらのプロセスの処理は、オペレーティングシステム（ＯＳ）のプロセスのスケジューリングによって同時に処理されることになる。また、データベースサーバーに複数のＣＰＵ(907)を備えているならば、それぞれのプロセスによるグループの処理は、別々のＣＰＵ上で並列に処理されることになる。
【００３２】
まず、プロセス１が、グループG1内の合成関係演算タスクtG1SG1，tG1SG2、及びサブグループに集まらないタスクt21の処理を、t21，tG1SG1，tG1SG2の順番で終了すると、クエリー・プロセッサは、新たに処理できるタスクを処理ツリー(902)から検索する。タスクt21が終了すると、新たにタスクt22の処理を始めることができるようになり、クエリー・プロセッサは、新たにグループG5を作成してグループG5にタスクt22を加えて、グループG5をグループ列（キュー）(904)に挿入する。次にタスクtG1SG1の処理が終了すると、新たにタスクt14，t33，t64の処理ができるようになり、クエリー・プロセッサは、新たにグループG6を作成してグループG6にタスクt14，t33，t64を加えて、グループG6をグループ列（キュー）(904)に挿入する。最後にタスクtG1SG2の処理が終了すると、新たに処理できるタスクは見出されないのでグループは作成されない。グループG1の処理が終了すると、プロセス１以外のすべてのプロセスは、他のグループの処理を行っているので、続けてプロセス１がグループ列からグループG5を取り出して、グループG5の処理を始めることになる。
他のプロセス２〜４もそれぞれ、グループ列からグループを取り出し、並列に処理を行う。
【００３３】
このようにして、それぞれのプロセスがグループの処理を終了するにつれて、次々にグループ列(904)からグループを取り出して、グループ内のタスク処理を行うことになり、マルチオペレーション・プロセッサ(905)は、グループの処理を繰り返して行っていくうちに、処理ツリー(902)内のタスクが次第に終了に近づき、処理ツリー内すべてのタスク処理が終了すると、与えられたすべてのクエリー処理は終了したことになる。また、クエリー・プロセッサ(901)が現在クエリーの処理（Q1からQ6までのクエリー）を行っている最中に、ユーザからの新たな問い合わせのクエリーQ7(909)があった場合には、クエリー・プロセッサは、クエリー・オプティマイザーを用いて新しいクエリーQ7に対する最適化を行って処理ツリーP7を作成し、処理ツリーP7からトポロジカルソートの順番で、処理できるタスクを見出し、それらのタスクと共通のリレーションをアクセスするタスクを集めたグループがグループ列に存在するかどうかを調べる。そのようなグループが既存のグループの中に存在するならば、そのグループにタスクを加えることになり、既存のグループに存在しない場合には、新たにグループを作成してそのグループにタスクを加えることにする。さらに、問い合わせのクエリーの数が増えると、プロセスがグループの処理を行っている間に、グループ列にいくつかのグループが待機するようになり、その間に数多くのタスクがグループに集められ、グループに集められたタスクが、さらにサブグループに集められて、数多くのタスク処理が一度に行われるようになる。このようにしてクエリーの処理を行うデータベースシステムは、数多くのクエリーを効率よく高速に行っていくものである。
【００３４】
［１−２．合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー・プロセッサのフローチャート］
図２は、合成関係演算を利用したマルチオペレーション・プロセッシングを用いてクエリーが処理される一連の流れを説明するためのフローチャートである。
まず、ＳＱＬなどのリレーショナルデータベースの言語を使用して、ユーザからデータベースサーバーにクエリーの問い合わせが入力される(S110)。問い合わせのあったＳＱＬの構文は、クエリー・オプティマイザー(900)によるクエリーの最適化処理によって関係演算で構成された処理ツリーに変換される(S120)。クエリー・プロセッサ(901)は、トポロジカルソートの順番で、直接的に処理することのできるタスクを見つける(S130)。直接的に処理することのできるタスクを見つけると、これらのタスクがアクセスするリレーションと共通のリレーションをアクセスするタスクが集められたグループがグループ列に存在するかどうかを調べる(S140)。共通のリレーションをアクセスするタスクが集められたグループがグループ列に存在しているならば、そのグループにタスクを加える(S150)。存在していない場合は、タスクのために新たなグループを作成し、そのグループにタスクを加えて、そのグループをグループ列に挿入する(S160)。
ここまでの処理は、前述した本発明者による特願２００６−３５６４０６号に記載したものと同じである。
【００３５】
グループにタスクを集めると、グループ内のタスクで共通部分式を持つタスクは、さらにサブグループに集める(S170)。サブグループにタスクを集めると、グループ内のサブグループに対して、サブグループ内のタスクをもとに合成関係演算タスクを作成する(S180)。
マルチオペレーション・プロセッサ(905)は、利用できるプロセスの数だけグループ列からグループを取り出し、マルチオペレーション・プロセッシングを用いて、グループ内の合成関係演算タスク、及びサブグループに集まらないタスクの処理を一度に行う(S190)。グループ内の合成関係演算タスクの処理が終了すると、サブグループ内のタスクに対して仮想リレーションを作成して合成関係演算タスクの処理結果内のレコードを部分的に共有できるようにする(S200)。
【００３６】
グループ内のタスク処理が終了すると、処理ツリー内のすべてのタスク処理が終了したかどうかを調べる(S210)。処理ツリー内にまだタスクが残っている場合は、繰り返して次に処理できるタスクを処理ツリーから見出していくことになる。
処理ツリー内のすべてのタスク処理が終了するとその処理ツリーに対応したクエリーの処理が終了する。
【００３７】
［１−３．合成関係演算を利用したマルチオペレーション・プロセッシングのアルゴリズム］
合成関係演算を利用したマルチオペレーション・プロセッシングを使用してグループに集められたタスクを一度に処理を行うに当たって、合成関係演算を利用したマルチオペレーション・プロセッシングのアルゴリズムをステップ１からステップ３に分けて、さらに説明する。
【００３８】
［（ａ）ステップ１：タスクのサブグループ化］
共通のリレーションRに対してグループ内のタスクの処理を行うに当たって、次のようにタスク間の共通部分式に関する定義を定めて、グループ内のタスクを共通部分式ごとにサブグループに集める(S170)。
・共通部分式に関する定義：
次に示す選択演算，射影演算，及びその他の演算に関する条件を満たすならば、タスクtiとタスクtjは共通部分式をもっている。
・選択演算：
タスクtiは、リレーションRに対して属性A1,A2,A3,…,Akに関する選択条件(ＡＮＤ，ＯRで結合したもの)に使用する選択演算タスクであり、タスクtjは、同一のリレーションRに対して同一の属性A1,A2,A3,…,Akに関する選択条件(ＡＮＤ，ＯＲで結合したもの)に使用する選択演算タスクであるときに、タスクtiとタスクtjが使用する選択条件において、１つの属性Ai(1≦i≦k)に関する選択条件だけは異なった条件かまたは同じ条件であり、Ai以外の属性に関する選択条件はまったく同じ条件である。
・射影演算：
タスクtiは、リレーションRに対する射影演算タスクであり、タスクtjは、同一のリレーションRに対する射影演算タスクである。
・その他の関係演算：
tiとtjは、同一の関係演算のタスク（ti≡tj)である。
以上の定義の条件に用いた演算は、あくまでも共通部分式に関するものである。
【００３９】
［（ｂ）ステップ２：合成関係演算タスクの作成］
ステップ１によってグループ内のタスクを共通部分式ごとにサブグループに集めると、サブグループ内のタスクの演算の種類に応じて、下記の方法を使用して、グループ内の各サブグループに対して、合成関係演算タスクを作成する(S180)。
【００４０】
・合成選択演算タスク作成方法：
サブグループ内の選択演算タスクTEMP_T1←σ<selection condition 1>R，TEMP_T2←σ<selection condition 2>R，TEMP_T3←σ<selection condition 3>R，…，TEMP_Tn←σ<selection condition n>Rに使われている選択条件<selection condition i>(i=1,2,…,n)を、ブール演算のＯＲを使用して接続し、接続した選択条件から選択範囲の重複した部分を取り除くために、次のような最適化を行って１つの合成選択演算タスクを作成する。
TEMP_SG←σoptimize(<selection condition 1> OR <selection condition 2> OR <selection condition 3> …OR <selection condition n>)R
ここで、σ<selection condition i>R (i=1,2,…,n)は、リレーションRに対して選択条件<selection condition i>にもとづいて選択演算することを意味し、σoptimize(…)は、最適化により選択演算を行うことを意味する。また、TEMP_Ti←σ<selection condition i>Rは、リレーションRに対して、選択条件<selection condition i>にしたがって選択(σ)するタスクを表し、その処理結果をTEMP_Tiに記録するものとする。
【００４１】
・合成射影演算タスク作成方法：
サブグループ内の射影演算タスクTEMP_T1←π<attribute list 1>R，TEMP_T2←π<attribute list 2>R，TEMP_T3←π<attribute list 3>R ,…，TEMP_Tn←π<attribute list n>Rに使われている属性のリスト<attribute list i>(i＝1,2,…,n)を集合Siに変換し、和集合（Union）を用いて各タスクからの属性を１つの集合TS＝S1∪S2∪S3∪…∪Snに集める。そして属性の集合TSを属性のリスト<attribute list SG>に変換して、合成射影演算タスクTEMP_SG←π<attribute list SG>Rを作成する。ここで、π<attribute list i>R(i=1,2,…,n)は、リレーションRに対して、属性のリスト<attribute list i>にもとづき射影演算を行うことを意味する。また、TEMP_Ti←π<attribute list i>R(i=1,2,…,n)はリレーションRに対して属性<attribute list i>にもとづいて射影演算を行った結果をTEMP_Tiに記録することを表すものとする。
【００４２】
・その他の合成関係演算タスク作成方法：
サブグループには、同一の関係演算のタスクが集められているので、サブグループ内のタスクの１つを合成関係演算タスクとして使うものとする。
【００４３】
［（ｃ）ステップ３：マルチオペレーション・プロセッシングを使ったグループの処理］
ステップ２を用いてグループ内の各サブグループに関して作成された合成関係演算タスク及びグループ内でサブグループに集められないタスクに対してマルチオペレーション・プロセッシングを使用して処理を行う(S190)。
このマルチオペレーション・プロセッシングとして、ダイナミックマルチオペレーション・プロセッシングとスタティックマルチオペレーション・プロセッシングの２つの処理方法を提案してきた（特願２００６−３５６４０６号参照）が、この実施形態では、スタティック・マルチオペレーション・プロセッシングをマルチオペレーション・プロセッシングとして用いて処理を行っていくことにする。スタティック・マルチオペレーション・プロセッシングを使って処理を行う場合は、グループ内の合成関係演算タスク及びグループ内でサブグループに集まらないタスクに対してアクセスプランを作成し、アクセスプランから各タスクの処理コストをもとめ、処理コストの小さいタスクから処理コストの大きいタスクへと順番に処理するために、アクセスするリレーション内のブロックの順位を決定し、その順位にしたがってディスク内のブロックをアクセスし、このブロックを共通ブロックとして、このブロック上で処理を行う必要のあるグループ内のタスク処理を一度に処理していくことになる。
【００４４】
この方法は、アクセスすべきブロック（共通ブロック）の順位に従って、和集合、積集合及び差集合などの集合論を用いて、クエリーに含まれる各タスクの処理をきわめて論理的に行うものである。
【００４５】
［（ｄ）仮想リレーション］
合成関係演算を利用したマルチオペレーション・プロセッシングによって処理された合成関係演算タスクの処理結果は、サブグループ内の個々のタスクの処理結果のすべてを含んでいるために、サブグループ内のタスクは、合成関係演算タスクの処理結果を部分的に共有することになる。
合成関係演算タスクの処理結果を部分的に共有していることを示すために、サブグループ内の個々のタスクに対して仮想リレーションを作成し、仮想リレーションに合成関係演算タスクの処理結果を共有するために必要な情報を記録しておく。
合成関係演算タスクが選択演算の場合、選択条件に使われた属性で整列された処理結果のリレーションを作成し、仮想リレーションとして、共有する合成関係演算の処理結果のリレーション名、レコードの格納位置（レコードの行範囲、レコードが格納してあるブロックの番号とアドレス）などの情報を記録しておくことになる。
また、合成関係演算タスクが射影演算の場合、仮想リレーションとして、共有する処理結果のリレーション名、属性の格納位置(列番号)などの情報を記録しておくことになる。
仮想リレーションにこれらの情報を記録しておくことによって、仮想リレーションを用いて処理を行うタスクは、合成関係演算タスクの処理結果の中から必要なレコードをすばやく取り出すことができるようになる(S200)。
【００４６】
このようにして、サブグループに集められたいくつものタスクを１つの合成関係演算タスクに置き換えて処理を行い、サブグループ内の個々のタスクは仮想リレーションを通して合成関係演算タスクの処理結果を部分的に共有することになり、サブグループ内の個々のタスクの間で選択範囲、及び属性（列）の重なっているレコードを含んだ処理結果のリレーションをディスク上に別々に作成する必要がなくなるので、ディスクをアクセスする回数を減らすことができ、クエリーの処理速度を向上させることが可能となる。
また、仮想リレーションを用いて処理を行うタスクは、仮想リレーションをもとにしてグループ分けするのではなく、（仮想リレーションを包含している）合成関係演算タスクの処理結果として得られたリレーションをもとにグループ分けを行い、マルチオペレーション・プロセッシングを使用してこれらのタスク処理を一度に行うものとする。マルチオペレーション・プロセッシングを使用してこれらのタスク処理を一度に行うことによって、合成関係演算タスクの処理結果得られたリレーションのブロックは、何度もアクセスされることがなくなり、クエリーの処理速度を向上させることが可能となる。
【００４７】
以上のようにして、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー処理を行うことによって、マルチオペレーション・プロセッシングだけを用いたクエリー処理よりも数多くのタスク処理が一度に行うことができるようになり、ディスクをアクセスする回数を減少させ、クエリーの処理速度を向上させることができる。
【００４８】
［２．合成関係演算を利用したマルチオペレーション・プロセッシングの具体例］
ここでは、上述で説明した合成関係演算を利用したマルチオペレーション・プロセッシングを、図３−１〜図３−３に示したデータ構造を有するデータベースに対するクエリーQ1〜Q5の例を用いて説明する。
【００４９】
［２−１．リレーションとクエリー（問い合わせ）処理］
［（ａ）リレーションの例］
図３−１〜図３−３には、リレーションDEPARTMENT，EMPLOYEE，WORKS_ON，PROJECTから構成されているデータベースを示している。
リレーションDEPARTMENT（図３−１（ａ）参照）には２５件のレコードが５つのブロックに格納してあり、それぞれのブロックには５件のレコードが存在しており、各ブロックは、次のブロックに対してブロックポインタを持っている。リレーションDEPARTMENTの主属性DNUMBERには、主インデックス(100)が存在し、主インデックスは、各ブロックに対してインデックスポインタを持っている。リレーションDEPARTMENTの属性DPHONEには、２次インデックス(102)が存在し、２次インデックスはリレーションDEPARTMENT内の各レコードに対してインデックスポインタを持っている。
リレーションEMPLOYEE（図３−２参照）には、２０件のレコードが５つのブロックに格納してあり、それぞれのブロックには４件レコードが存在しており、各ブロックは次のブロックに対してブロックポインタを持っている。リレーションEMPLOYEEの主属性SSNには、主インデックス(104)が存在し、主インデックスは各ブロックに対してインデックスのポインタを持っている。
【００５０】
リレーションPROJECT（図３−３（ｃ）参照）には、１０件のレコードが２つのブロックに格納してあり、それぞれのブロックには５件レコードが存在しており、各ブロックは、次のブロックに対してブロックポインタを持っている。リレーションPROJECTの主属性PNUMBERには、主インデックス(106)が存在し、主インデックスは、各ブロックに対してインデックスのポインタを持っている。
リレーションWORKS_ON（図３−３（ｄ）参照）には、２５件のレコードが５つのブロックに格納してあり、それぞれのブロックには５件のレコードが存在する。各ブロックは、次のブロックに対してブロックポインタを持っている。リレーションWORKS_ONの主属性ESSN，PNOは、リレーションEMPLOYEE，PROJECTに対する外部キーである。以上をまとめると次のような表になる。
【表１】
2008234495.tif 000003
【００５１】
［（ｂ）クエリー例］
次に、図３−１〜図３−３に示したデータベースをもとにして合成関係演算を利用したマルチオペレーション・プロセッシングを説明するために、下記に示すようなクエリーQ1，Q2，Q3，Q4，Q5，Q6処理を取り上げることにする。図３−１〜図３−３のデータベースに対して、次のような６つのクエリーQ1，Q2，Q3，Q4，Q5，Q6の問い合わせがあったとする。
【００５２】
（Q1）SELECT LNAME,DNUMBER,DNAME,PNUMBER,PNAME
FROM DEPARTMENT,EMPLOYEE,PROJECT,WORKS_ON
WHERE DPHONE=23-3732 AND DNUMBER=DNUM AND
BDATE<'DEC-31-1961' AND SSN=ESSN AND
PNAME='Aquarius' AND PLOCATION='New York' AND PNUMBER=PNO;
【００５３】
（Q2）SELECT DNAME,DNUMBER,PNAME,PNUMBER,SSN,LNAME,BDATE
FROM EMPLOYEE,DEPARTMENT,PROJECT
WHERE SSN=164545566 AND SSN=MGRSSN AND
PNAME='Stafford' AND PLOCATION='New York' AND DNUMBER=DNUM;
【００５４】
（Q3）SELECT SSN,FNAME,LNAME,DNAME,DNUMBER
FROM DEPARTMENT,EMPLOYEE
WHERE DNUMBER=DNUM AND BDATE>'JAN-1-1971';
【００５５】
（Q4）SELECT *
FROM PROJECT,DEPARTMENT,EMPLOYEE
WHERE DNUMBER=DNUM AND PNUMBER=PNO AND SSN=ESSN;
【００５６】
（Q5）SELECT *
FROM DEPARTMENT,EMPLOYEE,WORKS_ON
WHERE DNUMBER=DNUM AND SSN=ESSN AND HOURS<10;
【００５７】
（Q6）SELECT FNAME,LNAME,DNUMBER,DNAME
FROM DEPARTMENT,EMPLOYEE
WHERE DNUMBER=7 AND DNUMBER=DNUM AND 
BDATE>'FEB-11-1959' AND BDATE<'NOV-21-1966';
【００５８】
［２−２．処理プランの作成］
クエリー・プロセッサは、問い合わせのあった各クエリーQ1，Q2，Q3，Q4，Q5，Q6に対して、クエリーの最適化を行い、各クエリーを処理していくための最良な処理方法である下記の処理プランを作成していくことになる。クエリーQ1に対して処理プランP1を作成し、クエリーQ2に対して処理プランP2を作成し、クエリーQ3に対して処理プランP3を作成し、クエリーQ4に対して処理プランP4を作成し、クエリーQ5に対して処理プランP5を作成し、クエリーQ6に対して処理プランP6を作成する。
【００５９】
作成した処理プランを処理ツリーで表すと、図４−１〜図４−３に示したようにP1〜P6となる。
処理ツリーPi内のタスクtij（iは処理ツリーの番号、jはそれぞれの処理ツリー内の処理番号を表わしている）は、以下に示すように、
（tij）：処理結果←関係代数
として表し、処理結果は関係代数を処理した結果を表すものとする。処理結果名がTEMP_Tj_iの場合は、処理ツリーPi内のタスクtijの処理結果(処理ツリーの中間結果)を表し、処理結果がRESULT_Qiの場合は、処理ツリーPiの処理結果であることを表している。関係代数は、データベースのリレーションに対して、直接的に処理を行う演算であり、選択演算(σ)、射影演算(π)、結合演算(|X|)などの演算である。
【００６０】
処理プランP1
(t11)： TEMP_T1_1←σDPHONE=23-3732DEPARTMENT
(t12)： TEMP_T2_1←πDNUMBER,DNAMETEMP_T1_1
(t13)： TEMP_T3_1←σBDATE<'DEC-31-1961'EMPLOYEE
(t14)： TEMP_T4_1←πSSN,LNAME,DNUMTEMP_T3_1
(t15)： TEMP_T5_1←TEMP_T2_1 |X|DNUMBER=DNUMTEMP_T4_1
(t16)： TEMP_T6_1←πSSN,LNAME,DNUMBER,DNAMETEMP_T5_1
(t17)： TEMP_T7_1←σPNAME='Aquarius” AND PLOCATION='New York'PROJECT
(t18)： TEMP_T8_1←πPNUMBER,PNAMETEMP_T7_1
(t19)： TEMP_T9_1←πESSN,PNOWORKS_ON
(t110)：TEMP_T10_1←TEMP_T8_1 |X|PNUMBER=PNOTEMP_T9_1
(t111)：TEMP_T11_1←πESSN,PNUMBER,PNAMETEMP_T10_1
(t112)：TEMP_T12_1←TEMP_T6_1 |X|SSN=ESSNTEMP_T11_1
(t113)： RESULT_Q1←πLNAME,DNUMBER,DNAME,PNUMBER,PNAMETEMP_T12_1
【００６１】
処理プランP2
(t21)：TEMP_T1_2←σSSN=164545566EMPLOYEE
(t22)：TEMP_T2_2←πSSN,LNAME,BDATETEMP_T1_2
(t23)：TEMP_T3_2←πDNUMBER,DNAME,MGRSSNDEPARTMENT
(t24)：TEMP_T4_2←σPNAME='Stafford' AND PLOCATION='New York'PROJECT
(t25)：TEMP_T5_2←πPNUMBER,PNAME,DNUMTEMP_T4_2
(t26)：TEMP_T6_2←TEMP_T3_2 |X|DNUMBER=DNUMTEMP_T5_2
(t27)：TEMP_T7_2←πDNUMBER,DNAME,MGRSSN,PNUMBER,PNAMETEMP_T6_2
(t28)：TEMP_T8_2←TEMP_T2_2 |X|SSN=MGRSSNTEMP_T7_2
(t29)：RESULT_Q2←πDNAME,DNUMBER,PNAME,PNUMBER,SSN,LNAME,BDATETEMP_T8_2
【００６２】
処理プランP3
(t31)：TEMP_T1_3←πDNUMBER,DNAMEDEPARTMENT
(t32)：TEMP_T2_3←σBDATE>'JAN-1-1971'EMPLOYEE
(t33)：TEMP_T3_3←πSSN,FNAME,LNAME,DNUMTEMP_T2_3
(t34)：TEMP_T4_3←TEMP_T1_3 |X|DNUMBER=DNUMTEMP_T3_3
(t35)：RESULT_Q3←πSSN,FNAME,LNAME,DNAME,DNUMBERTEMP_T4_3
【００６３】
処理プランP4
(t41)：TEMP_T1_4←DEPARTMENT |X|DNUMBER=DNUMEMPLOYEE
(t42)：TEMP_T2_4←PROJECT |X|PNUMBER=PNOWORKS_ON
(t43)：RESULT_Q4←TEMP_T1_4 |X|SSN=ESSNTEMP_T2_4
【００６４】
処理プランP5
(t51)：TEMP_T1_5←DEPARTMENT |X|DNUMBER=DNUMEMPLOYEE
(t52)：TEMP_T2_5←σHOURS<10WORKS_ON
(t53)：RESULT_Q5←TEMP_T1_5 |X|SSN=ESSNTEMP_T2_5
【００６５】
処理プランP6 
(t61)：TEMP_T1_6←σDNUMBER=7DEPARTMENT
(t62)：TEMP_T2_6←πDNUMBER,DNAMETEMP_T1_6
(t63)：TEMP_T3_6←σBDATE>'FEB-11-1959' AND BDATE < NOV-21-1966'EMPLOYEE
(t64)：TEMP_T4_6←πFNAME,LNAME,DNUMTEMP_T3_6
(t65)：TEMP_T5_6←TEMP_T2_6 |X|DNUMBER=DNUMTEMP_T4_6
(t66)：RESULT_Q6←πFNAME,LNAME,DNUMBER,DNAMETEMP_T5_6
【００６６】
［２−３．タスクのグループ化とサブグループ化］
［（ａ）タスクのグループ化］
合成関係演算を利用したマルチオペレーション・プロセッシングを適用するにあたって、図４−１〜図４−３に示した処理プランP1，P2，P3，P4，P5，P6にもとづいて作成された処理ツリーからトポロジカルソートの順番で、他のタスクから依存がなく直接的に処理できるタスクt11，t13，t17，t19，t21，t23，t24，t31，t32，t41，t42，t51，t52，t61，t63を見つけて、各タスクがアクセスするデータベースのリレーションをもとにグループに分けていくと、次のようにグループ分けすることになる。
【００６７】
また、２つのリレーションをアクセスする結合演算タスクなどの場合は、検索先のリレーションではなく検索元のリレーションをもとにしてグループ分けを行う。
EMPLOYEE：  グループ G1＝{t13,t21,t32,t41,t51,t63}
DEPARTMENT：グループ G2＝{t11,t23,t31,t61}
PROJECT：   グループ G3＝{t17,t24}
WORKS_ON：  グループ G4＝{t19,t42,t52}
【００６８】
グループG1には、リレーションEMPLOYEEをアクセスするタスクが集められ、グループG2には、リレーションDEPARTMENTをアクセスするタスクが集められ、グループG3にはリレーションPROJECTをアクセスするタスクが集められる。そしてグループG4にはリレーションWORKS_ONをアクセスするタスクが集められてグループ分けが行われる。
【００６９】
［（ｂ）タスクのサブグループ化］
グループG1，G2，G3，G4にタスクが分けられると、グループ内のタスクで共通部分式を持っているタスクは、次のようにさらに共通部分式ごとにサブグループSG1G1，SG2G1，SG1G2，SG1G3に分けていくことになる。
【００７０】
EMPLOYEE：      グループ G1   ＝{SG1G1,SG2G1,t21} 
サブグループ SG1G1＝{t13,t32,t63}
サブグループ SG2G1＝{t41,t51}
DEPARTMENT：    グループ G2   ＝{SG1G2,t11,t61}
サブグループ SG1G2＝{t23,t31}
PROJECT：       グループ G3   ＝{SG1G3}
サブグループ SG1G3＝{t17,t24}
WORKS_ON：      グループ G4   ＝{t19,t42,t52}
【００７１】
サブグループSG1G1はリレーションEMPLOYEEに対して共通部分式の定義で述べた属性BDATEを選択条件に使用する選択演算タスクが集められたサブグループである。
サブグループSG2G1はリレーションEMPLOYEEに対して共通部分式の定義で述べた同一の関係演算の処理を行うタスクが集められたサブグループである。
サブグループSG1G2はリレーションDEPARTMENTに対して共通部分式の定義で述べた射影演算の処理を行うタスクのサブグループである。
サブグループSG1G3はリレーションPROJECTに対して共通部分式の定義で述べた属性PNAME,PLOCATIONを選択条件に使用する選択演算タスクが集められたサブグループであり、これらのタスクが使用する選択条件において、属性PNAMEに関する選択条件は異なっているが、それ以外の属性PLOCATIONに関する選択条件は全く同じ条件である。
グループG4内のタスクt19，t42，t52は共通部分式を持っていないので、グループG4にサブグループは作成されないことになる。
【００７２】
図５は、処理ツリーからトポロジカルソートの順番で直接的に処理できるタスクt11，t13，t17，t19，t21，t23，t24，t31，t32，t41，t42，t51，t52，t61，t63(300)を、それぞれのタスクがアクセスするデータベースのリレーションをもとにグループG1，G2，G3，G4に分け、さらにグループ内のタスクで共通部分式を持っているタスクを共通部分式ごとにサブグループSG1G1，SG2G1，SG1G2，SG1G3に分けている様子を表わしている。
【００７３】
［（ｃ）合成関係演算タスクの作成］
グループ内にサブグループが作成されると、作成されたサブグループSG1G1，SG2G1，SG1G2，SG1G3に対して次のように合成関係演算タスクtG1SG1，tG1SG2，tG2SG1，tG3SG1を作成することができる。
(tG1SG1)：TEMP_SG1_G1←σBDATE<'NOV-21-1966' OR BDATE>'JAN-1-1971'EMPLOYEE
(tG1SG2)：TEMP_SG2_G1←DEPARTMENT |X|DNUMBER=DNUMEMPLOYEE
(tG2SG1)：TEMP_SG1_G2←πDNUMBER,DNAME,MGRSSNDEPARTMENT
(tG3SG1)：TEMP_SG1_G3←σPLOCATION='New York' AND (PNAME='Aquarius” OR PNAME='Stafford')PROJECT
【００７４】
以上のように得られた合成関係演算タスクを説明すると、以下のようになる。
タスクtG1SG1は、下記に示すようにサブグループSG1G1内の選択演算タスクt13，t32，t63の選択条件をブール演算のORを用いて接続して１つの選択条件<temp_cond>を作成し、接続した選択条件から選択範囲の重複した部分を取り除くために、簡潔化し最適化Optimize(<temp_cond>)した選択条件を作成し、その選択条件を用いた合成選択演算タスクである。
<temp_cond>＝(BDATE<'DEC-31-1961') OR (BDATE>'JAN-1-1971') OR
(BDATE>'FEB-11-1959' AND BDATE<'NOV-21-1966')
Optimize(<temp_cond>) ⇒ BDATE<'NOV-21-1966' OR BDATE>'1-JAN-1972'
Optimize(<temp_cond>)によって表わされる選択条件は、ブール演算のＯＲを用いて作成した選択条件<temp_cond>を最適化するために、それぞれの選択条件の選択範囲の論理和（Union）を求めて、選択範囲の重複した部分を取り除いて新たに簡潔化された選択条件として得られたものである。
【００７５】
この最適化を、上述のタスクtG1SG1の例で、図６を用いて詳しく説明する。
図６（ａ）は、ブール演算のＯＲを使用して接続しているタスクt13の選択条件BDATE<'DEC-31-1961'である生年月日の選択範囲、タスクt63の選択条件BDATE>'FEB-11-1959' AND BDATE<'NOV-21-1966'である生年月日の選択範囲、タスクt32の選択条件BDATE>'JAN-1-1971'の生年月日の選択範囲を、生年月日の値が小さいほうから順番に左から右に１つの水平な線上に表している。
次に、図６（ｂ）に示すように、タスクt13，t32，t63の選択条件に使われている生年月日の選択範囲の論理和（Union）を求めると、BDATEの値がNOV-21-1966以前とBDATEの値JAN-1-1971以降のBDATEの選択範囲のみが必要になることがわかる。
このようにして選択条件の選択範囲の論理和で求めた生年月日の選択範囲を新たな選択条件に直すと”BDATE<'NOV-21-1966' OR BDATE>'JAN-1-1971'”と簡潔化された選択条件になり、この選択条件を前述したように合成選択演算タスクtG1SG1の選択演算の選択条件として使用することになる。
【００７６】
タスクtG1SG2は、サブグループSG2G1内のタスクが同一の結合演算（t41≡t51）なので、サブグループSG2G1内の結合演算タスクの１つをそのまま合成関係演算タスクとして使用することになる。
タスクtG2SG1は、サブグループSG1G2内の射影演算タスクt23，t31に使われている属性を、和集合（Union）を使用して作成した合成射影演算タスクである。
タスクtG3SG1は、下記に示すようにサブグループSG1G3内の選択演算タスクt17，t24の選択条件をブール演算のＯＲを用いて接続して１つの選択条件<temp_cond>を作成し、接続した選択条件から選択範囲の重複した部分を取り除くために最適化Optimize(<temp_cond>)を行って作成した合成選択演算タスクである。
<temp_cond>＝(PNAME='Aquarius' AND PLOCATION='New York') OR 
(PNAME='Stafford' AND PLOCATION='New York')
Optimize(<temp_cond>) ⇒ PLOCATION='New York' AND (PNAME='Aquarius' OR PNAME='Stafford')
【００７７】
Optimize(<temp_cond>)は、ブール演算のＯＲを用いて作成した選択条件<temp_cond>を最適化するために、それぞれの選択条件の選択範囲の論理和(Union)を求めて、選択範囲の重複した部分であるPLOCATION='New York'を取り除いて新たに簡潔化された選択条件として得られたものである。
【００７８】
以上のように、グループ内のサブグループに対して合成関係演算タスクを作成すると、グループ内のサブグループを次のように合成関係演算タスクで置き換えることができる。
EMPLOYEE：  グループ G1＝{tG1SG1,tG1SG2,t21}
DEPARTMENT：グループ G2＝{tG2SG1,t11,t61}
PROJECT：   グループ G3＝{tG3SG1}
WORKS_ON：  グループ G4＝{t19,t42,t52}
【００７９】
［２−４．マルチオペレーション・プロセッシングによる合成関係演算タスク処理］
グループ内のサブグループが合成関係演算タスクで置き換えられると、マルチオペレーション・プロセッシングを適用して、グループ内の合成関係演算タスクを含むグループ内のタスクの処理を一度に行っていくことにする。マルチオペレーション・プロセッシングとして、スタティック・マルチオペレーション・プロセッシング（特願２００６−３５６４０６号参照）を使用して、グループG1，G2，G3，G4の処理を行っていく場合について記述する。
【００８０】
［（ａ）グループG1の処理］
スタティックマルチオペレーション・プロセッシングを使用してグループG1内の合成選択演算タスクtG1SG1，tG1SG2及びサブグループに集まらないタスクt21の処理を一度に行うことにする。前述したように、グループG1内の各タスクは次のようなものである。
EMPLOYEE：グループ G1＝{tG1SG1,tG1SG2,t21}
(tG1SG1)：TEMP_SG1_G1←σBDATE<'NOV-21-1966' OR BDATE>'JAN-1-1971'EMPLOYEE
(tG1SG2)：TEMP_SG2_G1←DEPARTMENT |X|DNUMBER=DNUMEMPLOYEE
(t21)：   TEMP_T1_2←σSSN=164545566EMPLOYEE
【００８１】
［（ａ−１）各タスクのアクセスプラン］
まずグループG1内のタスクtG1SG1，tG1SG2，t21に対して次のようなアクセスプランを作成する。
plan(tG1SG1)：EMPLOYEEを線形探索して選択処理を行う。
plan(tG1SG2)：EMPLOYEEをスキャンしてDEPARTMENTの主インデックスを使用して結合処理を行う。
plan(t21)： EMPLOYEEの主インデックスを使った選択処理を行う。
【００８２】
［（ａ-２）各タスクの処理コスト］
各タスクに対してアクセスプランを作成した後に、アクセスプランをもとに各タスクの処理コストを計算すると、以下のようになる。
タスクtG1SG1の処理コスト：cost(tG1SG1)＝b＝5
タスクtG1SG2の処理コスト：cost(tG1SG2)＝bE+(|EMPLOYEE|*(xD+1))＝5+(20*(1+1))＝45
タスクt21の処理コスト：cost(t21)＝xE+1＝2
処理コストとはタスクの処理を行うためにディスクをアクセスする回数である。ここではタスクの処理を行うためにディスクをアクセスする回数を減らすのが目的であるので、メインメモリで計算する時間、処理結果をディスクに保存するコストは省略することにする。また、cost()は、処理コストを表すものとする。
【００８３】
タスクtG1SG1の処理コストは、リレーションEMPLOYEEを線形探索し、５つのブロックをアクセスするので処理コストはbE＝5である。
タスクtG1SG2の処理コストは、リレーションEMPLOYEEをスキャンする処理コストbEとEMPLOYEE内の各レコードに対してリレーションDEPARTMENTの主インデックスを使用して結合できるレコードを検索する処理コスト|EMPLOYEE|*(xD+1)を合計した処理コストである。
リレーションEMPLOYEEには、２０件のレコードが５つのブロックに格納してある。xD+1は、B+ツリーインデックスなどマルチレベルのインデックスのレベルとブロックをアクセスする処理コストであり、図３−１のリレーションDEPARTMENTに存在する主インデックスのレベルxDは１であるので、タスクtG1SG2の処理コストは、bE+(|EMPLOYEE|*(xD+1))＝5+(20*(1+1))＝45である。
タスクt21の処理コストは、主インデックスを使用して１つのレコードを検索する処理コストである。これは、リレーションのEMPLOYEEの主インデックスのレベルxEとブロックをアクセスする処理コストであり、図３−２のリレーションEMPLOYEEの主インデックスのレベルは１であるので、処理コストはxE+1＝2である。
【００８４】
以上のようにタスクtG1SG1，tG1SG2，t21に対して、処理コストを計算し、処理コストをもとに、これらのタスクを処理コストの小さい順番から並び替えると次のようになる。
sort(tG1SG1,tG1SG2,t21) ⇒ (t21,tG1SG1,tG1SG2)
sort(…)は並べ替えを表している。
【００８５】
［（ａ−３）各タスクに対応するブロックの集合］
タスクt21，tG1SG1，tG1SG2を処理するにあたって、インデックスを用いてアクセスする必要のあるリレーションのすべてのブロックを事前に調べて、各タスクに対応するブロック集合B21，BG1SG1，BG1SG2に集めると、次のようになる。
タスクt21に対するブロック集合：B21＝{b2}
タスクtG1SG1に対するブロック集合：BG1SG1＝{b1,b2,b3,b4,b5} 
タスクtG1SG2に対するブロック集合：BG1SG2＝{b1,b2,b3,b4,b5}
このように、各タスクt21，tG1SG1，tG1SG2に対応するブロック集合B21，BG1SG1，BG1SG2を見出すことができるのは、以下に示すような理由にもとづくからである。
【００８６】
タスクt21は、選択条件”SSN=164545566”を満たすレコードが必要である。リレーションEMPLOYEEの主インデックスを使用すると、属性SSNの値が164545566であるレコードはブロックの相対アドレスが256であるブロックb2に格納してあることがわかり、ブロックb2だけをアクセスすることが必要となるので、タスクt21の処理を行うためにアクセスする必要のあるブロックの集合は{b2}となる。ブロックb2の相対アドレスとはリレーションEMPLOYEEの最初のブロックアドレスをゼロとしたときに、そこから何バイト移動したところにブロックb2が格納してあるかを表したものである。
【００８７】
タスクtG1SG1は、選択条件”BDATE<'NOV-21-1966' OR BDATE>'JAN-1-1971'”を満たすレコードが必要である。リレーションEMPLOYEEの属性BDATEにはインデックスが存在しないので、リレーションEMPLOYEE内のすべてのレコードを線形探索するために、リレーションEMPLOYEEの最初のブロックb1から最後のブロックb5までのブロックをアクセスすることが必要となるので、タスクtG1SG1の処理を行うためにアクセスする必要のあるブロックの集合は{b1,b2,b3,b4,b5}となる。
【００８８】
タスクtG1SG2は、結合演算の処理を行うために、リレーションEMPLOYEEの最初のブロックb1から最後のブロックb5までのブロックをアクセスすることが必要となるので、タスクtG1SG2の処理を行うためにアクセスする必要のあるブロックの集合は{b1,b2,b3,b4,b5}となる。
【００８９】
［（ａ−４）アクセスすべきブロック（共通ブロック）の順位の決定］
以上のように、各タスクに対応するブロック集合を見出した後に、処理コストの小さいタスクから処理コストの大きいタスクへと順番に、すなわちタスクt21，tG1SG1，tG1SG2の順番に各タスクに対応するブロック集合の和集合を求めていくことにする。
まず、TB0＝{}（空集合）として、TB0とタスクt21に対応するブロック集合B21と和集合TB21を求める。次に、このTB21とタスクtG1SG1に対応するブロック集合BG1SG1の和集合TBG1SG1を求める。さらに、このTBG1SG1とタスクtG1SG2に対応するブロック集合BG1SG2との和集合TBG1SG2を求めると次のようになる。この場合、和集合を求めるに当たっては、新たに加える集合は和集合の中で最後に加えていくものとする。
TB0＝{}
タスクt21に対応する集合B21との和集合：TB21＝TB0∪B21＝{b2}
タスクtG1SG1に対応する集合BG1SG1との和集合：TBG1SG1＝TB21∪BG1SG1＝{b2,b1,b3,b4,b5}
タスクtG1SG2に対応する集合BG1SG2との和集合：TBG1SG2＝TBG1SG1∪BG1SG2＝{b2,b1,b3,b4,b5}
【００９０】
以上のように、処理コストの小さいタスクに対応するブロック集合から処理コストの大きいタスクに対応するブロック集合へと順番に和集合を求めていくと、最後のタスク（処理コストの１番大きいタスク）に対応するブロック集合との和集合TBG1SG2から、ディスクのブロックb2からアクセスを開始し、ブロックb5でアクセスを終了すればよいことになり、ディスクにおけるリレーションEMPLOYEE内のブロックへのアクセスの順番を（b2，b1，b3，b4，b5）のように決定することができる。このような方法で和集合を求めることは、処理コストの小さいタスクから順番に処理を行うに当たって、ディスク内のブロックをどのような順番でアクセスすればよいか、その順番を決定するためである。このようにして得られたブロックb2，b1，b3，b4，b5は、タスクt21，tG1SG1，tG1SG2を順番に処理していくときに共有され得るので、これらのブロックを共通ブロックと呼ぶことにする。
【００９１】
前述したブロック集合B21，BG1SG1，BG1SG2の中に含まれているブロックを見ると、ブロックb2は、タスクt21，tG1SG1，tG1SG2を処理するために使用され、ブロックb1は、タスクtG1SG1，tG1SG2を処理するために使用され、ブロックb3，b4，b5は、タスクtG1SG1，tG1SG2を処理するために使用されることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。以上のことをまとめると次のような表になる。
【表２】
2008234495.tif 000004
【００９２】
［（ａ−５）共通ブロックでのタスクの処理］
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、タスクt21，tG1SG1，tG1SG2に対して作成されたブロック集合B21，BG1SG1，BG1SG2の情報にもとづいて、次に記述するような手順を用いればよい。
最初に、ブロックの相対アドレスが256であるブロックb2をディスクからアクセスして、ブロックb2内のデータをメインメモリに読み込み、グループ内のタスクt21，tG1SG1，tG1SG2がブロックb2で処理を行う必要があるかどうかを調べるため、ブロックb2を集合{b2}として表し、この{b2}とブロックの集合B21，BG1SG1，BG1SG2との間でそれぞれ積集合（Intersection）を求めると次のようになる。
タスクt21に対して：B21∩{b2}＝{b2}
タスクtG1SG1に対して：BG1SG1∩{b2}＝{b2}
タスクtG1SG2に対して：BG1SG2∩{b2}＝{b2}
【００９３】
タスクt21，tG1SG1，tG1SG2に対する積集合が{b2}となり、タスクt21，tG1SG1，tG1SG2がメインメモリに読み込んだブロックb2で処理を行う必要があることが明らかになり、ブロックb2は共通ブロックとなり、共通ブロックb2で各タスクの処理を行うことになる。共通ブロックであるブロックb2でのタスクの処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、ブロックb2を取り除くために、集合B21，BG1SG1，BG1SG2と集合{b2}との差集合（Difference）を求める。得られた差集合の値をB21(1)，BG1SG1(1)，BG1SG2(1)とすると、次のようになる。
タスクt21に対して：B21−{b2}＝{}＝B21(1)
タスクtG1SG1に対して：BG1SG1−{b2}＝{b1,b3,b4,b5}＝BG1SG1(1)
タスクtG1SG2に対して：BG1SG2−{b2}＝{b1,b3,b4,b5}＝BG1SG2(1)
この結果、集合B21(1)が空集合{}になりタスクt21の処理が終了したことがわかる。
【００９４】
次に、ブロックの相対アドレスが0であるブロックb1をディスクからアクセスして、ブロックb1内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21を除くグループ内のタスクtG1SG1，tG1SG2がブロックb1で処理を行う必要があるかどうかを調べるために、ブロックb1を集合{b1}として表し、{b1}とブロックの集合BG1SG1(1)，BG1SG2(1)との間でそれぞれ積集合を求めると次のようになる。
タスクtG1SG1に対して：BG1SG1(1)∩{b1}＝{b1}
タスクtG1SG2に対して：BG1SG2(1)∩{b1}＝{b1}
タスクtG1SG1，tG1SG2に対する積集合が{b1}となり、タスクtG1SG1，tG1SG2がメインメモリに読み込んだブロックb1で処理を行うことが必要となり、ブロックb1は共通ブロックとなり、共通ブロックb1で各タスクの処理を行うことになる。共通ブロックであるブロックb1でのタスクの処理が終了すると、ブロックb1を再びアクセスする必要がなくなるので、集合BG1SG1(1)，BG1SG2(1)と集合{b1}との差集合を求める。得られた差集合の値をBG1SG1(2)，BG1SG2(2)とすると、次のようになる。
タスクtG1SG1に対して：BG1SG1(1)−{b1}＝{b3,b4,b5}＝BG1SG1(2)
タスクtG1SG2に対して：BG1SG2(1)−{b1}＝{b3,b4,b5}＝BG1SG2(2)
【００９５】
次に、ブロックの相対アドレスが512であるブロックb3をディスクからアクセスして、ブロックb3内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21を除くグループ内のタスクtG1SG1，tG1SG2がブロックb3で処理を行う必要があるかどうかを調べるために、ブロックb3を集合{b3}として表し、{b3}とブロックの集合BG1SG1(2)，BG1SG2(2)との間で積集合を求めると次のようになる。
タスクtG1SG1に対して：BG1SG1(2)∩{b3}＝{b3}
タスクtG1SG2に対して：BG1SG2(2)∩{b3}＝{b3}
タスクtG1SG1，tG1SG2に対する積集合が{b3}となり、タスクtG1SG1，tG1SG2がメインメモリに読み込んだブロックb3で処理を行うことが必要となり、ブロックb3は共通ブロックとなり、共通ブロックb3でタスクtG1SG1，tG1SG2の処理を行うことになる。共通ブロックであるブロックb3でのタスクの処理が終了すると、ブロックb3を再びアクセスする必要がなくなるので、集合BG1SG1(2)，BG1SG2(2)と集合{b3}との差集合を求めて、得られた差集合の値をBG1SG1(3)，BG1SG2(3)とすると、次のようになる。
タスクtG1SG1に対して：BG1SG1(2)−{b3}＝{b4,b5}＝BG1SG1(3)
タスクtG1SG2に対して：BG1SG2(2)−{b3}＝{b4,b5}＝BG1SG2(3)
【００９６】
次に、ブロックの相対アドレスが768であるブロックb4をディスクからアクセスして、ブロックb4内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21を除くグループ内のタスクtG1SG1，tG1SG2がブロックb4で処理を行う必要があるかどうかを調べるために、ブロックb4を集合{b4}として表し、{b4}とブロックの集合BG1SG1(3)，BG1SG2(3)との間で積集合を求めると次のようになる。
タスクtG1SG1に対して：BG1SG1(3)∩{b4}＝{b4}
タスクtG1SG2に対して：BG1SG2(3)∩{b4}＝{b4}
タスクtG1SG1，tG1SG2に対する積集合が{b4}となり、タスクtG1SG1，tG1SG2がメインメモリに読み込んだブロックb4で処理を行うことが必要となり、ブロックb4は共通ブロックとなり、共通ブロックb4でタスクtG1SG1，tG1SG2の処理を行うことになる。共通ブロックであるブロックb4でのタスクの処理が終了すると、ブロックb4を再びアクセスする必要がなくなるので、集合BG1SG1(3)，BG1SG2(3)と集合{b4}との差集合を求める。得られた差集合の値をBG1SG1(4)，BG1SG2(4)とすると、次のようになる。
タスクtG1SG1に対して：BG1SG1(3)−{b4}＝{b5}＝BG1SG1(4)
タスクtG1SG2に対して：BG1SG2(3)−{b4}＝{b5}＝BG1SG2(4)
【００９７】
最後に、ブロックの相対アドレスが1024であるブロックb5をディスクからアクセスして、ブロックb5内のデータをメインメモリに読み込み、すでに処理の済んだタスクt21を除くグループ内のタスクtG1SG1，tG1SG2がブロックb5で処理を行う必要があるかどうかを調べるために、ブロックb5を集合{b5}として表し、集合{b5}とブロックの集合BG1SG1(4)，BG1SG2(4)との間で積集合を求めると次のようになる。
タスクtG1SG1に対して：BG1SG1(4)∩{b5}＝{b5}
タスクtG1SG2に対して：BG1SG2(4)∩{b5}＝{b5}
タスクtG1SG1，tG1SG2に対する積集合が{b5}となり、タスクtG1SG1，tG1SG2がメインメモリに読み込んだブロックb5で処理を行うことが必要となり、ブロックb5は共通ブロックとなり、共通ブロックb5でタスクtG1SG1，tG1SG2の処理を行う。共通ブロックであるブロックb5でのタスクの処理が終了すると、ブロックb5を再びアクセスする必要がなくなるので、集合BG1SG1(4)，BG1SG2(4)と集合{b5}との差集合を求める。得られた差集合の値をBG1SG1(5)，BG1SG2(5)とすると、次のようになる。
タスクtG1SG1に対して：BG1SG1(4)−{b5}＝{}＝BG1SG1(5)
タスクtG1SG2に対して：BG1SG2(4)−{b5}＝{}＝BG1SG2(5)
この結果、集合BG1SG1(5)，BG1SG2(5)が空集合{}になり、タスクtG1SG1，tG1SG2の処理が終了したことがわかり、これによってグループ内のすべてのタスクの処理が終了したことになる。
【００９８】
このように共通ブロックを利用して、ディスク内のリレーションのブロックを何度もアクセスすることなしに、グループ内のタスク処理を一度に行い、処理コストの小さいタスクから順番に次々と処理を行っていき、最後のタスク処理ですべてのタスク処理を終了させることができる。
【００９９】
図７は、リレーションEMPLOYEEに対するタスクt21，tG1SG1，tG1SG2を、スタティック・マルチオペレーション・プロセッシングを使用して処理する様子を示す図である。
図７において、リレーションEMPLOYEEに対するタスクt21，tG1SG1，tG1SG2の処理を、処理コストの小さいタスクからアクセスしてく状態（スキャン１からスキャン３にわたって）と、処理結果のリレーションTEMP_T1_2，TEMP_SG1_G1，TEMP_SG2_G1に書き込んだ結果を表わしている。
一連のタスクの処理を行うプロセス(501)は、ディスク内のブロックをスキャン１でb2を、スキャン２でb1を、スキャン３でb3，b4，b5を、順にアクセスする。
プロセス(501)は、アクセスする各ブロックにおいて、そのブロックで処理を行う必要のあるグループ内のタスクの処理を一度に行い、処理結果をリレーションTEMP_T1_2，TEMP_SG1_G1，TEMP_SG2_G1に書き込み、すべてのブロックでのタスク処理が終了すると、スタティック・マルチオペレーション・プロセッシングによるグループG1のタスク処理は終了したことになる。
【０１００】
［（ａ−６）サブグループ内のタスクによる合成選択演算の処理結果の共有］
図７において、合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1(503)は、サブグループ内のタスクt13，t32，t63の処理結果のすべてを含んでいるため、サブグループ内のタスクt13，t32，t63は、合成選択演算タスクtG1SG2の処理結果TEMP_SG1_G1(503)を部分的に共有することになる。
【０１０１】
図７に示した合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1(503)は、選択条件に使用された属性BDATEの値で整列してあり、サブグループ内の個々のタスクt13，t32，t63の処理結果にそれぞれ対応する仮想リレーションTEMP_T3_1，TEMP_T2_3，TEMP_T3_6が処理結果TEMP_SG1_G1のレコードを部分的に共有している様子を表わしている。サブグループ内のタスクが合成関係演算タスクtG1SG1の処理結果TEMP_SG1_G1を部分的に共有していることを示すために、処理結果TEMP_SG1_G1内のレコードを合成選択演算の選択条件に使用された属性BDATEの値で整列したときに、サブグループ内の個々のタスクt13，t32，t63に対して、以下のように仮想リレーションTEMP_T3_1,TEMP_T2_3，TEMP_T3_6を作成する。仮想リレーションには共有する合成関係演算タスクの処理結果(リレーション)名、その処理結果を共有するレコードの格納位置（レコードの行範囲、レコードが格納されているブロックの番号とアドレス）を記録しておく。
TEMP_T3_1＝{リレーション:TEMP_SG1_G1; 行:1〜9; ブロック:b1[0,256],b2[256,512],b3[512,768]};
TEMP_T2_3＝{リレーション:TEMP_SG1_G1; 行:13〜16; ブロック:b4[768,-]};
TEMP_T3_6＝{リレーション:TEMP_SG1_G1; 行:7〜12; ブロック:b2[256,512],b3[512,768]};
【０１０２】
仮想リレーションTEMP_T3_1は、サブグループSG1G1内のタスクt13の処理結果であり、合成関係演算タスクtG1SG1の処理結果TEMP_SG1_G1のブロックb1，b2，b3に格納してあるレコードの1行から9行までを共有していることを表わしている。
仮想リレーションTEMP_T2_3は、サブグループSG1G1内のタスクt32の処理結果であり、TEMP_SG1_G1のブロックb4に格納してあるレコードの13行から16行までを共有していることを表わしている。
仮想リレーションTEMP_T3_6は、サブグループSG1G1内のタスクt63の処理結果であり、TEMP_SG1_G1のブロックb2，b3に格納してあるレコードの7行から12行までを共有していることを表わしている。
【０１０３】
［（ａ−７）合成選択演算の処理結果を共有するための手順］
合成選択演算タスクの処理結果得られたリレーションのレコードをサブグループ内個々の選択演算タスクが仮想リレーションを用いて部分的に共有するには、以下の手順を用いることになる。
（i）合成選択演算タスクの処理結果内のレコードは合成選択演算の選択条件に使用された属性の値で整列する。
（ii）整列された処理結果内のレコードをスキャンし、１つ１つのレコードがサブグループ内個々の選択演算タスクの選択条件を満たしているかどうかを調べていく。
（iii）合成選択演算タスクの処理結果において、どの行からどの行までのレコードがサブグループ内個々の選択演算タスクの選択範囲内のレコードであったかをそれぞれの処理結果である仮想リレーションに記録しておく。
【０１０４】
前述したよう合成選択演算tG1SG1の処理結果TEMP_SG1_G1中からレコードを部分的に共有するサブグループSG1G1内のタスクは次のようなものである。
サブグループ SG1G1＝{t13,t32,t63}
(t13)：TEMP_T3_1←σBDATE<'DEC-31-1961'EMPLOYEE
(t32)：TEMP_T2_3←σBDATE>'JAN-1-1971'EMPLOYEE
(t63)：TEMP_T3_6←σBDATE>'FEB-11-1959' AND BDATE<NOV-21-1966'EMPLOYEE
【０１０５】
図８−１，図８−２は、variable length record（可変長レコード），contiguous block allocation（隣接したブロックの配置），unspanned record（２つのブロックにまたがって格納されないレコード）のファイル形式で表せられる合成選択演算タスクtG1SG1の処理結果TEMP_G1_SG1(600)内のレコードを、合成選択演算の選択条件に使用された属性BDATEの値をもとに、マージソートとクイックソートの２つのソートアルゴリズムを組み合わせて整列し、整列された処理結果(613)内のレコードを、サブグループSG1G1内の選択演算タスクt13，t32，t63の処理結果である仮想リレーションTEMP_T3_1，TEMP_T2_3，TEMP_T3_6が部分的に共有するための手順を表している。
【０１０６】
（１）最初にマージソートを適用してリレーション内のブロック列をブロック数が１つになるまで再帰的に２つに分割していく（図８−１：600〜606）。
【０１０７】
（２）ブロック列内のブロック数が１つになると、ブロック列（図８−１：603〜606）をそれ以上分割することはできないので、ブロック列内のブロックb1〜b4を順番にメインメモリに読み込んで、属性BDATEの値をもとにブロック内のレコードを整列する。ブロック内のレコードを整列するにあたって、ブロック内の可変長レコードはそれぞれサイズが異なるので（バイト数が異なるので）、ブロック内の個々のレコードに対してポインタ（レコードのアドレス）（図８−１：614〜617）をメインメモリ内に配列させ、クイックソートを用いて配列されたポインタをポインタが持つレコードの値（レコードのアドレスから求められるレコードのBDATEの値）をもとに整列する。
【０１０８】
（３）整列されたポインタの順番（図８−２：618〜621）に従ってブロック内のレコードを並びかえる。
【０１０９】
（４）ブロック内のレコードが整列されると、次はマージソートによる再起の呼び出しから戻るときに（図８−２：607〜613）、整列済みの２つのブロック列から１つのブロック列に結合していく。結合するにあたっては、結合するレコードを整列された順番で並べていく。
【０１１０】
（５）最後に２つのブロック列（図８−２：611，612）が１つのブロック列(613)に結合される際に、１つ１つのレコードがサブグループSG1G1内の選択演算タスクt13，t32，t63の選択条件をそれぞれ満たしているかどうかを一度に調べていく。
【０１１１】
（６）ブロック列（図８−２：613）にすべてレコードが整列されると、タスクt13，t32，t63に対して、ブロック列(613)に加えられたレコードの中でどの行からどの行までのレコードが選択範囲内のレコードであったかを仮想リレーションTEMP_T3_1，TEMP_T2_3，TEMP_T3_6に記録しておくことになる。仮想リレーションTEMP_T3_1，TEMP_T2_3，TEMP_T3_6には実際のレコードを加えるのではなく、前述したように整列された処理結果(613)を部分的に共有するレコードの格納位置(レコードの行範囲及びそれらのレコードが格納してあるブロックの番号とアドレス)を記録しておくことになる。
【０１１２】
このようにして、サブグループSG1G1内の選択演算タスクt13，t32，t63が合成選択演算タスクtG1SG1の処理結果TEMP_G1_SG1内のレコードを部分的に共有できるのは、処理結果TEMP_G1_SG1(613)内のレコードを整列するために用いた属性BDATEを、タスクt13，t32，t63が個々の選択条件に使用しているからである。このレコードを共有する範囲を調べる作業は、以上に述べた方法のようにリレーション内のレコードを最終的にブロック列(613)を形成するときに行うことが重要である。その理由は、最終的にブロック列(613)で整列した後に、サブグループ内のタスクのレコードの共有する範囲を求めると、再度、リレーション内のすべてのレコードをディスクから読み直さなければならなくなり、そのためにディスクアクセスが必要になるからである。
【０１１３】
その他、処理結果内のレコードを整列する必要がない場合、すなわち合成選択演算の選択条件に使用されている属性が主属性である場合は、処理結果内のレコードはすでに整列された順番に格納されていくことになるので、処理結果にレコードを加える際に、サブグループ内の個々の選択演算タスクの選択条件を満たしているかを一度に調べていくことになる。
【０１１４】
以上のようにして、サブグループに集められたいくつかの選択演算タスクを１つの合成選択演算タスクtG1SG1に置き換えて処理を行うと、サブグループSG1G1内のタスクt13，t32，t63に対応する仮想リレーションは処理結果TEMP_SG1_G1内のレコードを部分的に共有することになり、サブグループ内の個々のタスクt13，t32，t63の間で選択範囲の重なっているレコードを含んだ処理結果のリレーションをディスク上に別々に作成する必要がなくなるので、ディスクをアクセスする回数を減少させ、クエリーの処理速度を向上させることができる。
【０１１５】
また、仮想リレーションを作成して合成選択演算タスクの処理結果を共有するその他の理由は、仮想リレーションを用いて合成選択演算タスクの処理結果に対して処理を行うタスクを別々に処理するのではなく、マルチオペレーション・プロセッシングを用いて一度に処理するためである。そのため仮想リレーションを用いて処理を行うタスクは、仮想リレーションをもとにしてグループ分けをするのではなく、仮想リレーションを包含している合成関係演算タスクの処理結果のリレーションをもとにグループ分けを行い、仮想リレーションに記録してある情報から共通ブロックを見出し、グループ内のタスク処理を一度に行っていくことになる。
【０１１６】
このようにして、仮想リレーションを用いたタスク処理を一度に行うと、合成選択演算の処理結果内のブロックは一度しかアクセスされないので、ディスクをアクセスする回数を減少させ、クエリーの処理速度を向上させることができる。
【０１１７】
［（ａ−８）その他の合成関係演算の処理結果の共有］
グループG1の合成関係演算タスクtG1SG2の処理結果TEMP_SG2_G1は、サブグループSG2G1内のタスクt41，t51によって共有されることになる。合成関係演算タスクtG1SG2は結合演算であり、サブグループSG2G1内のタスクt41，t51は、同一のタスク（t41≡t51）なので、タスクt41の処理結果TEMP_T1_4とタスクt51の処理結果TEMP_T1_5は、合成関係演算タスクtG1SG2の処理結果TEMP_SG2_G1をそのまま、それぞれのタスクの処理結果として使用することになる(TEMP_T1_4≡TEMP_T1_5≡TEMP_SG2_G1)。
【０１１８】
［（ａ−９）新たなグループの作成］
マルチオペレーション・プロセッシングを使用してグループG1内の合成関係演算タスクtG1SG1，tG1SG2及びサブグループに集まらないタスクt21の処理が、タスクt21，tG1SG1，tG1SG2の順番で終了すると、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
最初にタスクt21が終了すると、処理ツリーP2からわかるように、新たにタスクt22の処理を始めることができるようになる。タスクt22は、タスクt21の処理結果TEMP_T1_2に対して処理を行うタスクとして、新たにグループG5（これまでのグループG4に加えて）を作成してグループG5にタスクt22を加えることにする。
【０１１９】
次に、タスクtG1SG1の処理が終了すると、サブグループSG1G1内のタスクt13，t32，t63の処理が終了することになり、処理ツリーP1，P3，P6からわかるように、新たにタスクt14，t33，t64の処理ができるようになる。タスクt14，t33，t64はそれぞれアクセスする仮想リレーションが異なるが、タスクt14はタスクt13の処理結果である仮想リレーションTEMP_T3_1を包含している合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1をアクセスし、タスクt33はタスクt32の処理結果である仮想リレーションTEMP_T2_3を包含している合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1をアクセスし、タスクt64はタスクt63の処理結果である仮想リレーションTEMP_T3_6を包含している合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1をアクセスするので、これらの新たなタスクt14，t33，t64は共通のリレーションTEMP_SG1_G1に対して処理を行うタスクとして、新たにグループG6を作成して、グループG6にタスクt14，t33，t64を加えることにする。
【０１２０】
最後に、タスクtG1SG2の処理が終了すると、サブグループSG2G1内のタスクt41，t51の処理が終了することになり、処理ツリーP4，P5からわかるように、グループG4に集められたタスクt42，t52の処理が終了していないため、新たに処理できるタスクは見出されないのでグループは作成されない。
【０１２１】
以上のことをまとめると、グループG1内のタスクの処理が終了することによって新たに見出されたタスクt22，t14，t33，t64がアクセスする処理結果のリレーションをもとに、次のようにグループG5，グループG6が作成される。
TEMP_T1_2：グループ G5＝{t22}
(t22)：TEMP_T2_2←πSSN,LNAME,BDATETEMP_T1_2
TEMP_SG1_G1：グループ G6＝{t14,t33,t64}
(t14)：TEMP_T4_1←πSSN,LNAME,DNUMTEMP_T3_1
(t33)：TEMP_T3_3←πSSN,FNAME,LNAME,DNUMTEMP_T2_3
(t64)：TEMP_T4_6←πFNAME,LNAME,DNUMTEMP_T3_6
【０１２２】
グループG5には、タスクt21の処理結果TEMP_T1_2に対して処理を行うタスクt22が集められることになり、グループG6には、合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1に対して処理を行うタスクt14，t33，t64が集められることになる。
【０１２３】
［（ｂ）グループG2の処理］
次に、マルチオペレーション・プロセッシングを使用してグループG2内の合成射影演算タスクtG2SG1及びサブグループに集まらないタスクt11，t61の処理を一度に行うことにする。前述したように、グループG2内の各タスクは次のようなものである。
DEPARTMENT：グループ G2＝{tG2SG1,t11,t61}
(tG2SG1)：TEMP_SG1_G2←πDNUMBER,DNAME,MGRSSNDEPARTMENT
(t11)：   TEMP_T1_1←σDPHONE=23-3732DEPARTMENT
(t61)：   TEMP_T1_6←σDNUMBER=7DEPARTMENT
【０１２４】
［（ｂ−１）各タスクのアクセスプラン］
まず、グループG2内の合成射影演算タスクtG2SG1及びサブグループに集められないタスクt11，t61に対して次のようなアクセスプランを作成する。
plan(tG2SG1)：DEPARTMENTをスキャンして射影演算を行う。
plan(t11)：DEPARTMENTの2次インデックスを使用して１つのレコードを検索する。
plan(t61)：DEPARTMENTの主インデックスを使用して１つのレコードを検索する。
【０１２５】
［（ｂ−２）各タスクの処理コスト］
各タスクに対してアクセスプランを作成すると、アクセスプランをもとに、各タスクの処理コストを計算する。
タスクtG2SG1の処理コスト：cost(tG2SG1)＝bD＝5
タスクt11の処理コスト：cost(t11)＝xD2+1＝3
タスクt61の処理コスト：cost(t61)＝xD1+1＝2
タスクtG2SG1の処理コストは、リレーションDEPARTMENTをスキャンして射影演算の処理を行うために、リレーション中のすべてのブロックをアクセスする処理コストなのでbD＝5である。
【０１２６】
タスクt11の処理コストは、リレーションDEPARTMENTの２次インデックス(102)を使用して１つのレコードを検索する処理コストである。これは２次インデックスのレベルxD2とブロックをアクセスする処理コストであり、図３−１のリレーションDEPARTMENTの２次インデックス(102)のレベルxD2は2であるので、処理コストはxD2+1＝3である。
タスクt61の処理コストは、リレーションDEPARTMENTの主インデックス(100)を使用して１つのレコードを検索する処理コストである。xD1+1は、リレーションDEPARTMENTの主インデックス(100)を使用して目的のデータを見つけるためにアクセスするインデックスのレベルxD1と当面のブロックをアクセスする処理コストである。図３−１のリレーションDEPARTMENTの主インデックス(100)のレベルは１であるので(xD1＝1となり)、タスクt61の処理コストはxD1+1＝2である。
【０１２７】
以上のように処理コストを計算すると、処理コストをもとにグループ内のタスクを処理コストの小さい順番から並べ替えると次のようになる。
sort(tG2SG1,t11,t61)⇒(t61,t11,tG2SG1)
【０１２８】
［（ｂ−３）各タスクに対応するブロック集合］
タスクt61，t11，tG2SG1に対して、インデックスを使用して、アクセスする必要のあるすべてのブロックを事前に調べて、各タスクに対応するブロック集合B61，B11，BG2SG1に集めると、次のようになる。
タスクt61に対して：B61＝{b2}
タスクt11に対して：B11＝{b5}
タスクtG2SG1に対して：BG2SG1＝{b1,b2,b3,b4,b5}
このように、各タスクt61，t11，tG2SG1 に対応するブロック集合B61，B11，BG2SG1を見出すことができるのは、以下に示すような理由にもとづくからである。
タスクt61は、選択条件”DNUMBER＝7”を満たすレコードが必要である。リレーションDEPARTMENTの主インデックスを使用すると、属性DNUMBERの値が7であるレコードはブロックの相対アドレスが256であるブロックb2に格納してあることがわかり、ブロックb2だけをアクセスすることが必要となるので、タスクt61の処理を行うためにアクセスする必要のあるブロックの集合は{b2}となる。
【０１２９】
タスクt11は、選択条件”DPHONE＝23-3732”を満たすレコードが必要である。リレーションDEPARTMENTの２次インデックスを使用すると、属性DPHONEの値が23-3732であるレコードはブロックの相対アドレスが1024であるブロックb5に格納してあることがわかり、ブロックb5だけをアクセスすることが必要となるので、タスクt11の処理を行うためにアクセスする必要のあるブロックの集合は{b5}となる。
タスクtG2SG1は、射影演算の処理を行うために、リレーションDEPARTMENT内の最初のブロックb1から最後のブロックb5までのブロックをアクセスすることが必要となるので、タスクtG2SG1の処理を行うためにアクセスする必要のあるブロック集合は｛b1,b2,b3,b4,b5｝となる。
【０１３０】
［（ｂ−４）アクセスすべきブロック（共通ブロック）の順位の決定］
以上のように、各タスクに対応するブロック集合を見出した後に、処理コストの小さいタスクから処理コストの大きいタスクへと順番に、すなわちタスクt61，t11，tG2SG1の順番に各タスクに対応するブロック集合の和集合を求めていくことにする。
まず、TB0＝{}（空集合）として、TB0とタスクt61に対応するブロック集合B61と和集合TB61を求める。次に、このTB61とタスクt11に対応するブロック集合B11の和集合TB11を求める。さらに、このTB11とタスクtG2SG1に対応するブロック集合BG2SG1との和集合TBG2SG1を求めると次のようになる。この場合、和集合を求めるに当たっては、新たに加える集合は和集合の中で最後に加えていくものとする。
TB0＝{}
タスクt61に対応する集合B61との和集合：TB61＝TB0∪B61＝{b2}
タスクt11に対応する集合B11との和集合：TB11＝TB61∪B11＝{b2,b5}
タスクtG2SG1に対応する集合BG2SG1との和集合：TBG2SG1＝TB11∪BG2SG1＝{b2,b5,b1,b3,b4}
【０１３１】
以上のように、処理コストの小さいタスクに対応するブロック集合から処理コストの大きいタスクに対応するブロック集合へと順番に和集合を求めていくと、最後のタスク（処理コストの１番大きいタスク）に対応するブロック集合との和集合TBG2SG1から、ディスクのブロックb2からアクセスを開始し、ブロックb4でアクセスを終了すればよいことになり、ディスクにおけるリレーションDEPARTMENT内のブロックへのアクセスの順番を（b2,b5,b1,b3,b4）のように決定することができる。このような方法で和集合を求めることは、処理コストの小さいタスクから順番に処理を行うに当たって、ディスク内のブロックをどのような順番でアクセスすればよいか、その順番を決定するためである。このようにして得られたブロックb2，b5，b1，b3，b4は、タスクt61，t11，tG2SG1を順番に処理していくときに共用され得るので、これらのブロックを共通ブロックと呼ぶことにする。
【０１３２】
前述したブロック集合B61，B11，BG2SG1の中に含まれているブロックを見ると、ブロックb2は、タスクt61，tG2SG1を処理するために使用され、ブロックb5は、タスクt11，tG2SG1を処理するために使用され、ブロックb1，b3，b4は、タスクtG2SG1を処理するために使用されることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。以上のことをまとめると次のような表になる。
【表３】
2008234495.tif 000005
【０１３３】
［（ｂ−５）共通ブロックでのタスクの処理］
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、タスクt61，t11，tG2SG1に対して作成されたブロック集合B61，B11，BG2SG1の情報にもとづいて、次に記述するような手順を用いればよい。
最初に、ブロックの相対アドレスが256であるブロックb2をディスクからアクセスして、ブロックb2内のデータをメインメモリに読み込み、グループ内のタスクt61，t11，tG2SG1がブロックb2で処理を行う必要があるかどうかを調べるため、ブロックb2を集合{b2}として表し、この集合{b2}とブロックの集合B61，B11，BG2SG1との間でそれぞれ積集合（Intersection）を求めると次のようになる。
タスクt61に対して：B61∩{b2}＝{b2}
タスクt11に対して：B11∩{b2}＝{}
タスクtG2SG1に対して：BG2SG1∩{b2}＝{b2}
【０１３４】
タスクt11を除くタスクt61，tG2SG1に対する積集合が{b2}となり、タスクt61，tG2SG1がメインメモリに読み込んだブロックb2で処理を行う必要があることが明らかになり、ブロックb2は共通ブロックとなり、共通ブロックb2で各タスクの処理を行うことになる。共通ブロックであるブロックb2でのタスクの処理が終了するとブロックb2を再びアクセスする必要がなくなるので、集合B61，BG2SG1と集合{b2}との差集合（Difference）を求める。得られた差集合の値をB61 (1)，BG2SG1(1)とすると、次のようになる。
タスクt61に対して：B61−{b2}＝{}＝B61(1)
タスクtG2SG1に対して：BG2SG1−{b2}＝{b1,b3,b4,b5}＝BG2SG1(1)
この結果、集合B61(1)が空集合{}になりタスクt61の処理が終了したことがわかる。
【０１３５】
次に、ブロックの相対アドレスが1024であるブロックb5をディスクからアクセスして、ブロックb5内のデータをメインメモリに読み込み、すでに処理の済んだタスクt61を除くグループ内のタスクt11，tG2SG1がブロックb5で処理を行う必要があるかどうかを調べるために、ブロックb5を集合{b5}として表し、{b5}とブロックの集合B11，BG2SG1(1)との間でそれぞれ積集合を求めると次のようになる。
タスクt11に対して：B11∩{b5}＝{b5}
タスクtG2SG1に対して：BG2SG1(1)∩{b5}＝{b5}
【０１３６】
タスクt11，tG2SG1に対する積集合が{b5}となり、タスクt11，tG2SG1がメインメモリに読み込んだブロックb5で処理を行うことが必要となり、ブロックb5は共通ブロックとなり、共通ブロックb5でタスクt11，tG2SG1の処理を行うことになる。共通ブロックであるブロックb5でのタスクの処理が終了すると、ブロックb5を再びアクセスする必要がなくなるので、集合B11，BG2SG1(1)と集合{b5}との差集合を求める。得られた差集合の値をB11(1)，BG2SG1(2)とすると、次のようになる。
タスクt11に対して：B11−{b5}＝{}＝B11(1)
タスクtG2SG1に対して：BG2SG1(1)−{b5}＝{b1,b3,b4}＝BG2SG1(2)
この結果、集合B11(1)が空集合{}になりタスクt11の処理が終了したことがわかる。この段階で、グループに残ったタスクはtG2SG1のみとなるので、リレーションDEPARTMENTから残ったブロックb1，b3，b4をアクセスしてタスクtG2SG1の処理を行い、タスクtG2SG1の処理が終了するとグループ内すべてのタスクの処理が終了することになる。
【０１３７】
図９は、スタティックマルチオペレーション・プロセッシングを使用して、リレーションDEPARTMENTに対するタスクt61，t11，tG2SG1の処理コストの小さいタスクからアクセスしていく状態（スキャン１からスキャン５にわたって）と処理結果をリレーションTEMP_T1_6(704)，TEMP_T1_1(703)，TEMP_SG1_G2(705)に書き込んだ結果を表わした図である。
一連のタスクの処理を行うプロセス(701)は、ディスク内のブロックを、図９で示すように、ブロックb2，b5，b1，b3，b4の順番でアクセスし、各ブロックにおいて、そのブロックで処理を行う必要のあるグループ内のタスクの処理を行い、処理結果をリレーションTEMP_T1_6(704)，TEMP_T1_1(703)，TEMP_SG1_G2(705)に書き込み、すべてのブロックでのタスク処理が終了するとスタティックマルチオペレーション・プロセッシングによるグループG2のタスク処理は終了したことになる。
【０１３８】
［（ｂ−６）合成射影演算タスクの処理結果の作成］
合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2は、サブグループSG1G2内の射影演算タスクt23，t31によって部分的に共有されることになる。前述したようにサブグループSG1G2内のタスクは次のようなものである。
サブグループ SG1G2＝{t23,t31}
(t23)：TEMP_T3_2←πDNUMBER,DNAME,MGRSSNDEPARTMENT
(t31)：TEMP_T1_3←πDNUMBER,DNAMEDEPARTMENT
合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2内の属性（列）をサブグループSG1G2内の射影演算タスクt23，t31が部分的に共有するには、合成射影演算タスクtG2SG1の処理を行った際に、処理結果TEMP_SG1_G2を共有するサブグループSG1G2内のタスクt23，t31に対して、図９に示した仮想リレーションTEMP_T3_2，TEMP_T1_3を作成することにする。仮想リレーションには、共有する合成射影演算の処理結果(リレーション)名、その処理結果を共有する属性の格納位置(列番号)を次のように記録しておくことにする。
TEMP_T3_2＝{リレーション:TEMP_SG1_G2; 列:1,2,3};
TEMP_T1_3＝{リレーション:TEMP_SG1_G2; 列:1,2};
【０１３９】
仮想リレーションTEMP_T3_2は、サブグループSG1G2内のタスクt23の処理結果であり、合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2の列1，2，3を共有する。
仮想リレーションTEMP_T1_3は、サブグループSG1G2内のタスクt31の処理結果であり、合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2の列1，2を共有する。
以上のようにして、サブグループに集められたいくつもの射影演算タスクを１つの合成射影演算タスクtG2SG1に置き換えて処理を行い、サブグループSG1G2内のタスクt23，t31は、仮想リレーションを通して処理結果TEMP_SG1_G2内の属性（列）を部分的に共有することになり、サブグループ内の個々のタスクt23，t31に対して射影する属性が重なっているレコードを含んだ処理結果のリレーションをディスク上に別々に作成する必要がなくなるので、ディスクをアクセスする回数を減少させ、クエリーの処理速度を向上させることが可能になる。
【０１４０】
図９の合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2(705)は、仮想リレーションTEMP_T3_2と仮想リレーションTEMP_T1_3によって共有されている様子を表わしている。マルチオペレーション・プロセッシングを使用して合成関係演算タスクの処理結果を作成するにあたって、合成関係演算タスクの処理結果内のレコードに対して、結合演算などのタスクによって検索処理が行われる場合は、検索処理に使用される属性に対してインデックスを作成しておく。
【０１４１】
図９の合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2(705)内のレコードは、サブグループSG1G2内のタスクt23，t31の処理終了後に、図４−１〜図４−３の処理ツリーが示すように、結合演算タスクt26，t34によって検索されるため、検索処理に使用される属性DNUMBERに対してインデックス(702)を作成している。結合演算タスクt26は仮想リレーションTEMP_T3_2に対して検索処理を行うタスクであり、結合演算タスクt34は仮想リレーションTEMP_T1_3に対して検索処理を行うタスクであり、仮想リレーションTEMP_T3_2と仮想リレーションTEMP_T1_3はリレーションTEMP_SG1_G2(705)内の属性(列)を部分的に共有しているので、リレーションTEMP_SG1_G2に対して作成されたインデックス(702)は結合演算タスクt26，t34の検索処理のために共有されることになる。タスクt26はインデックス(702)を用いてリレーションTEMP_SG1_G2(705)からレコードを検索し、検索されたレコードが仮想リレーションTEMP_T3_2内に含まれているときには、仮想リレーションTEMP_T3_2からレコードを検索したことになる。同様に、タスクt34はインデックス(702)を用いてリレーションTEMP_SG1_G2(705)からレコードを検索し、検索されたレコードが仮想リレーションTEMP_T1_3内に含まれているときには、仮想リレーションTEMP_T1_3からレコードを検索したことになる。レコードが検索されると、検索されたレコードから個々の仮想リレーションに記録してある必要な属性（列）のみを射影することになる。
【０１４２】
このようにして、合成関係演算タスクの処理結果に対してインデックスを作成しておくと、仮想リレーションに対してレコードを検索するタスクは、インデックスを共有することができるようになり、個々の仮想リレーションに対して別々にインデックスを作成する必要がなくなるので、ディスクをアクセスする回数を減少させて、クエリーの処理速度を向上させることが可能になる。
【０１４３】
［（ｂ−７）新たなグループの作成］
以上のように合成関係演算を利用したマルチオペレーション・プロセッシングを使用してグループG2内の合成射影演算タスクtG2SG1及びサブグループに集まらないタスクt61，t11の処理が、タスクt61，t11，tG2SG1の順番で終了し、合成射影演算タスクtG2SG1の処理結果TEMP_SG1_G2に対してインデックスが作成されると、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
【０１４４】
最初に、タスクt61が終了すると処理ツリーP6からわかるように新たにタスクt62の処理を始めることができるようになる。タスクt62は、タスクt61の処理結果TEMP_T1_6に対して処理を行うタスクとして新たにグループG7を作成してグループG7にタスクt62を加えることになる。
次に、タスクt11が終了すると処理ツリーP1からわかるように新たにタスクt12の処理を始めることができるようになる。タスクt12は、タスクt11の処理結果TEMP_T1_1に対して処理を行うタスクとして新たにグループG8を作成してグループG8にタスクt12を加えることになる。
【０１４５】
最後、にタスクtG2SG1の処理が終了すると、サブグループSG1G2内のタスクt23，t31の処理が終了することになり、処理ツリーP2，P3からわかるように、グループG3に集められたタスクt24の処理とグループG6に集められたタスクt33の処理が終了していないので、新たに処理できるタスクは見出されないのでグループは作成することはない。
以上のことをまとめるとグループG2内のタスクの処理が終了することによって新たに見出されたタスクt62，t12をアクセスする処理結果のリレーションをもとに次のようにグループG7，グループG8が作成される。
TEMP_T1_6：グループ G7＝{t62}
(t62)：TEMP_T2_6←πDNUMBER,DNAMETEMP_T1_6
TEMP_T1_1：グループ G8＝{t12}
(t12)：TEMP_T2_1←πDNUMBER,DNAMETEMP_T1_1
グループG7には、タスクt61の処理結果TEMP_T1_6に対して処理を行うタスクt62が集められることになる。グループG8には、タスクt11の処理結果TEMP_T1_1に対して処理を行うタスクt12が集められることになる。
【０１４６】
［（ｃ）グループG3の処理］
グループG2の処理が終了すると、次はグループG3内の合成選択演算タスクtG3SG1の処理を行うことになる。前述したようにグループG3内の合成選択演算タスクは次のようなものである。
PROJECT：グループ G3＝{tG3SG1}
(tG3SG1)：TEMP_SG1_G3←σPLOCATION='New York' AND (PNAME='Aquarius' OR PNAME='Stafford')PROJECT
グループG3には１つのタスクしか存在しないため、合成選択演算タスクtG3SG1の処理を直接行うことになる。合成選択演算タスクtG3SG1の処理が終了すると、PLOCATONがNew Yorkであり、PNAMEが'Aquarius' または'Stafford'であるレコードを２件ほど含んだ処理結果TEMP_SG1_G3を作成する。処理結果TEMP_SG1_G3内のレコードは属性PNAMEの値で整列し、サブグループSG1G3内のタスクt17，t24に対しては次のような仮想リレーションを作成する。
TEMP_T7_1＝{リレーション:TEMP_SG1_G3; 行:1; ブロック:b1};
TEMP_T4_2＝{リレーション:TEMP_SG1_G3; 行:2; ブロック:b1};
仮想リレーションTEMP_T7_1は、サブグループSG1G3内のタスクt17の処理結果であり、TEMP_SG1_G3のブロックb1に格納されている属性PNAMEの値がAquariusである１行目のレコードを共有することになる。
【０１４７】
仮想リレーションTEMP_T4_2は、サブグループSG1G3内のタスクt24の処理結果であり、TEMP_SG1_G3のブロックb1に格納されている属性PNAMEの値がStaffordである２行目のレコードを共有することになる。
グループG3内の合成選択演算タスクtG3SG1の処理が終了すると、サブグループSG1G3内のタスクt17，t24の処理が終了することになり、図４−１〜図４−３の処理ツリーP1，P2からわかるように、新たにタスクt18，t25を処理できるようになる。
タスクt18，t25はそれぞれアクセスする仮想リレーションが異なるが、タスクt18は、タスクt17の処理結果である仮想リレーションTEMP_T7_1を通して、合成選択演算タスクtG3SG1の処理結果TEMP_SG1_G3をアクセスし、タスクt25は、タスクt24の処理結果である仮想リレーションTEMP_T4_2を通して、合成選択演算タスクtG3SG1の処理結果TEMP_SG1_G3をアクセスすることになるので、共通のリレーションTEMP_SG1_G3に対して処理を行うタスクとして、新たにグループG9を作成して、グループG9にタスクt18，t25を加えることになる。
【０１４８】
以上のことをまとめると、グループG3内のタスク処理が終了することによって見出されたタスクt18，t25を次のようにグループG9に集めることになる。
TEMP_SG1_G3：グループG9＝{t18,t25}
(t18)：TEMP_T8_1←πPNUMBER,PNAMETEMP_T7_1
(t25)：TEMP_T5_2←πPNUMBER,PNAME,DNUMTEMP_T4_2
【０１４９】
［（ｄ）グループG4の処理］
次に、マルチオペレーション・プロセッシングを適用してグループG4内のタスクt19，t42，t52の処理を一度に行うことになる。前述したように、グループG4内の各タスクは次のようなものである。
WORKS_ON：グループ G4＝{t19,t42,t52}
(t19)：TEMP_T9_1←πESSN,PNOWORKS_ON
(t42)：TEMP_T2_4←PROJECT |X|PNUMBER=PNOWORKS_ON
(t52)：TEMP_T2_5←σHOURS<10WORKS_ON
ここではマルチオペレーション・プロセッシングによるG4内のタスクt19，t42，t52の処理の説明は省略することにする。マルチオペレーション・プロセッシングによってグループG4内のタスクt19，t42，t52の処理を行うと、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
【０１５０】
最初に、タスクt19の処理が終了すると、処理ツリーP1からわかるように、グループG9内のタスクt18の処理が終了していないため、新たに処理できるタスクは見出されないので、グループは作成されないままである。
次に、タスクt42の処理が終了すると、処理ツリーP4からわかるように、グループG1内のタスクt41の処理はすでに終了しているので、新たにタスクt43の処理を始めることができるようになる。タスクt43はタスクt41の処理結果TEMP_T1_4とタスクt42の処理結果TEMP_T2_4を用いて結合演算の処理を行うタスクである。結合演算の検索元にTEMP_T2_4を使用するので、処理結果TEMP_T2_4に対して処理を行うタスクとして新たにグループG10を作成して、グループG10にタスクt43を加えることにする。
【０１５１】
最後に、タスクt52の処理が終了すると、処理ツリーP5からわかるように、グループG1内のタスクt51の処理はすでに終了しているので、新たにタスクt53の処理を始めることができるようになる。タスクt53はタスクt51の処理結果TEMP_T1_5とタスクt52の処理結果TEMP_T2_5を用いて結合演算の処理を行うタスクである。結合演算の検索元にTEMP_T2_5を使用するので、処理結果TEMP_T2_5に対して処理を行うタスクとして新たにグループG11を作成して、グループG11にタスクt53を加えることにする。
以上のことをまとめると、グループG4内のタスクt19，t42，t52の処理が終了することによって見出されたタスクt43，t53を次のようにグループに分けすることになる。タスクt43の処理結果は、クエリーQ4の最終の処理結果となるので、RESULT_Q4で表わすことにする。タスクt53の処理結果は、クエリーQ5の最終の処理結果となるので、RESULT_Q5で表わすことにする。
TEMP_T2_4：グループ G10＝{t43}
(t43)：RESULT_Q4←TEMP_T1_4 |X|SSN=ESSNTEMP_T2_4
TEMP_T2_5：グループ G11＝{t53}
(t53)：RESULT_Q5←TEMP_T1_5 |X|SSN=ESSNTEMP_T2_5
【０１５２】
［（ｅ）グループG5の処理］
グループG4の処理が終了すると、次はグループG5の処理を行うことになる。前述したように、グループG5内のタスクは次のようなものである。
TEMP_T1_2：グループ G5＝{t22}
(t22)：TEMP_T2_2←πSSN,LNAME,BDATETEMP_T1_2
グループG5には１つのタスクt22しか存在しておらず、タスクt22はタスクt21の処理結果TEMP_T1_2に対して射影演算の処理を行うタスクである。このようにグループに１つのタスクしか存在してしない場合は、グループG5内のタスクt22を直接処理することになる。
タスクt22の処理が終了すると、図４−２の処理ツリーP2からわかるように、グループG9内のタスクt25の処理が終了しておらず、グループに集められていないタスクt26，t27の処理も終了していないので、新たに処理できるタスクは見出されないのでグループは作成されない。
【０１５３】
グループG5の処理を終わると、次はグループG6の処理を行うことになる。グループG6には、合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1に対して処理を行うタスクが集められているので、詳しく説明することにする。
【０１５４】
ここまで扱ってきたタスク処理は、データベースのリレーションEMPLOYEE，DEPARTMENT，PROJECT，WORKS_ONなどデータベースのリレーションに対するタスク処理であった。次に、データベースのリレーションではなく、合成関係演算タスクの処理結果として得られたリレーションに対するタスク処理を取り上げて説明することにする。
【０１５５】
［（ｆ）グループG6の処理（合成関係演算タスクの処理結果として得られたリレーションに対するタスク処理）］
マルチオペレーション・プロセッシングを使用してグループG6内のタスクt14，t33，t64の処理を一度に行うことにする。前述したように、グループG6内のタスクは次のようなものである。
TEMP_SG1_G1：グループ G6＝{t14,t33,t64}
(t14)：TEMP_T4_1←πSSN,LNAME,DNUM TEMP_T3_1
(t33)：TEMP_T3_3←πSSN,FNAME,LNAME,DNUM TEMP_T2_3
(t64)：TEMP_T4_6←πFNAME,LNAME,DNUM TEMP_T3_6
【０１５６】
［（ｆ−１）各タスクのアクセスプラン］
スタティック・マルチオペレーション・プロセッシングの処理方法にもとづいて、グループG6内の各タスクt14，t33，t64に対してアクセスプランを作成する。タスクt14の処理に用いられる仮想リレーションTEMP_T3_1，タスクt33の処理に用いられる仮想リレーションTEMP_T2_3，タスクt64の処理に用いられる仮想リレーションTEMP_T3_6からそれぞれタスクがアクセスするブロックを調べることになる。前述したように、仮想リレーションTEMP_T3_1，TEMP_T2_3，TEMP_T3_6には、合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1を共有するブロックの番号とアドレスがすでに記録してあるので、事前にどのブロックをアクセスしたらよいかがわかる。タスクt14，t33，t64のアクセスプランは次のようになる。
plan(t14)：TEMP_SG1_G1のブロックb1,b2,b3をアクセスして射影演算の処理を行う。
plan(t33)：TEMP_SG1_G1のブロックb4をアクセスして射影演算の処理を行う。
plan(t64)：TEMP_SG1_G1のブロックb2,b3をアクセスして射影演算の処理を行う。
【０１５７】
［（ｆ−２）各タスクの処理コスト］
アクセスプランをもとに各タスクの処理コストを計算すると、次のように表すことができる。
タスクt14の処理コスト：cost(t14)＝3
タスクt33の処理コスト：cost(t33)＝1
タスクt64の処理コスト：cost(t64)＝2
タスクt14の処理コストは、リレーションTEMP_SG1_G1からブロックの相対アドレスが0，256，512である3つのブロックb1，b2，b3をアクセスして射影演算の処理を行う処理コストなので3である。
タスクt33の処理コストは、リレーションTEMP_SG1_G1からブロックの相対アドレスが768であるブロックb4をアクセスして射影演算の処理を行う処理コストなので1である。
タスクt64の処理コストは、リレーションTEMP_SG1_G1からブロックの相対アドレスが256，512である2つのブロックb2，b3をアクセスして射影演算の処理を行う処理コストなので2である。以上のように処理コストを計算すると、処理コストをもとにグループ内のタスクを処理コストの小さい順番で並べ替えると次のようになる。
sort(t14,t33,t64) ⇒ (t33,t64,t14)
【０１５８】
［（ｆ−３）各タスクに対応するブロック集合］
仮想リレーションに記録してある情報をもとに、タスクt33，t64，t14がリレーションTEMP_SG1_G1からアクセスする必要のあるブロックを調べて、各タスクに対応するブロック集合B33，B64，B14に集めると、次のようになる。
タスクt33に対応する集合B33との和集合：B33＝{b4}
タスクt64に対応する集合B64との和集合：B64＝{b2,b3}
タスクt14に対応する集合B14との和集合：B14＝{b1,b2,b3}
【０１５９】
［（ｆ−４）アクセスすべきブロック（共通ブロック）の順位の決定］
以上のように、各タスクに対応するブロック集合を見出した後に、処理コストの小さいタスクから処理コストの大きいタスクへと順番に、すなわちタスクt33，t64，t14の順番に各タスクに対応するブロック集合の和集合を求めていくことにする。
まず、TB0＝{}（空集合）として、TB0とタスクt33に対応するブロック集合B33と和集合TB33を求める。次に、このTB33とタスクt64に対応するブロック集合B64との和集合TB64を求める。さらに、このTB64とタスクt14に対応するブロック集合B14との和集合TB14を求めると次のようになる。この場合、和集合を求めるに当たっては、新たに加える集合は和集合の中で最後に加えていくものとする。
TB0＝{}
タスクt33に対して：TB33＝TB0∪B33＝{b4}
タスクt64に対して：TB64＝TB33∪B64＝{b4,b2,b3}
タスクt14に対して：TB14＝TB64∪B14＝{b4,b2,b3,b1}
【０１６０】
集合TB14からリレーションTEMP_SG1_G1内のブロックをb4，b2，b3，b1の順番でアクセスしていけばよいことがわかる。前述したブロック集合B33，B64，B14の中に含まれているブロックを見ると、ブロックb4は、タスクt33を処理するために使用され、ブロックb2は、タスクt64，t14を処理するために使用され、ブロックb3は、タスクt64，t14を処理するために使用され、ブロックb1は、タスクt14を処理するために使用されることがわかる。これらのブロックを共通ブロックとして扱うことにすると、これらの共通ブロックを必要とするタスクを共通ブロック上で一度に処理することができる。以上のことをまとめると次のような表になる。
【表４】
2008234495.tif 000006
【０１６１】
[(ｆ−５)共通ブロックでのタスクの処理］
以上のように、それぞれの共通ブロックでどのようなタスクが処理されるかを見出すためには、タスクt33，t64，t14に対して作成されたブロック集合B33，B64，B14の情報にもとづいて、次に記述するような手順を用いればよい。
最初に、ブロックの相対アドレスが768であるブロックb4をディスクからアクセスして、ブロックb4内のデータをメインメモリに読み込み、グループ内のタスクt33，t64，t14がブロックb4で処理を行う必要があるかどうかを調べるため、ブロックb4を集合{b4}として表わし、ブロック集合B33，B64，B14とそれぞれ積集合（intersection）を求める。
タスクt33に対して：B33∩{b4}＝{b4}
タスクt64に対して：B64∩{b4}＝{}
タスクt14に対して：B14∩{b4}＝{}
【０１６２】
タスクt64，t14を除くタスクt33に対する集合の積が空集合{}ではないため、メインメモリに読み込んだブロックb4内の各レコードに対してタスクt33の処理を行う。ブロックb4での処理が終了するとブロックb4を再びアクセスする必要がなくなるため、集合B33と集合{b4}との差集合（difference）を求めて、求めた差集合の値をB33(1)とすると次のようになる。
タスクt33に対して：B33−{b4}＝{}＝B33(1)
集合B33(1)が空集合{}になりタスクt33の処理が終了したことがわかる。
次に、ブロックの相対アドレスが256であるブロックb2をディスクからアクセスして、ブロックb2内のデータをメインメモリに読み込み、すでに処理の済んだタスクt33を除くグループ内のタスクt64，t14がブロックb2で処理を行う必要があるかどうかを調べるために、ブロックb2を集合{b2}として表し、集合{b2}とブロック集合B64，B14との間でそれぞれ積集合を求めると次のようになる。
タスクt64に対して：B64∩{b2}＝{b2}
タスクt14に対して：B14∩{b2}＝{b2}
【０１６３】
タスクt64，t14に対する積集合が{b2}となり、タスクt64，t14がメインメモリに読み込んだブロックb2で処理を行うことが必要となり、ブロックb2は共通ブロックとなり、共通ブロックb2でタスクt64，t14の処理を行うことになる。共通ブロックであるブロックb2でのタスクの処理が終了すると、ブロックb2を再びアクセスする必要がなくなるので、集合B64，B14と集合{b2}との差集合を求める。得られた差集合の値をB64(1)，B14(1)とすると、次のようになる。
タスクt64に対して：B64−{b2}＝{b3}＝B64(1)
タスクt14に対して：B14−{b2}＝{b1,b3}＝B14(1)
【０１６４】
次に、ブロックの相対アドレスが512であるブロックb3をディスクからアクセスして、ブロックb3内のデータをメインメモリに読み込み、すでに処理の済んだタスクt33を除くグループ内のタスクt64，t14がブロックb3で処理を行う必要があるかどうかを調べるために、ブロックb3を集合{b3}として表し、集合{b3}とブロック集合B64(1)，B14(1)との間でそれぞれ積集合を求めると次のようになる。
タスクt64に対して：B64(1)∩{b3}＝{b3}
タスクt14に対して：B14(1)∩{b3}＝{b3}
タスクt64，t14に対する積集合が{b3}となり、タスクt64，t14がメインメモリに読み込んだブロックb3で処理を行うことが必要となり、ブロックb3は共通ブロックとなり、共通ブロックb3でタスクt64，t14の処理を行うことになる。共通ブロックであるブロックb3でのタスクの処理が終了すると、ブロックb3を再びアクセスする必要がなくなるので、集合B64(1)，B14(1)と集合{b3}との差集合を求める。得られた差集合の値をB64(2)，B14(2)とすると、次のようになる。
タスクt64に対して：B64(1)−{b3}＝{}＝B64(2)
タスクt14に対して：B14(1)−{b3}＝{b1}＝B14(2)
【０１６５】
この結果、集合B64(3)が空集合{}になりタスクt64の処理が終了したことがわかる。この段階で、グループに残ったタスクはt14のみとなるので、リレーションTEMP_SG1_G1から残ったブロックb1をアクセスしてタスクt14の処理を行い、タスクt14の処理が終了するとグループ内すべてのタスクの処理が終了することになる。
【０１６６】
以上のように、リレーションTEMP_SG1_G1内のブロックをb4，b2，b3，b1の順番でアクセスすることによって、処理コストの小さいタスクからt33，t64，t14の順番でタスク処理が終了することがわかる。図１０は、スタティックマルチオペレーション・プロセッシングを使用してグループG6の処理を行っている様子を表している。プロセス(801)は、リレーションTEMP_SG1_G1(800)内ブロックをb4，b2，b3，b1の順番でアクセスして、タスクt33，t64，t14の処理を一度に行い、処理結果をTEMP_T3_3，TEMP_T4_6，TEMP_T4_1に書き込んでいる。
【０１６７】
［（ｆ−６）新たなグループの作成］
マルチオペレーション・プロセッシングを使用してグループG6内のタスクが、タスクt33，t64，t14の順番で終了すると、図４−１〜図４−３の処理ツリーからトポロジカルソートの順番で新たに処理できるタスクを見出していくことになる。
最初に、タスクt33の処理が終了すると、処理ツリーP3からわかるように新たにタスクt34の処理を始めることができるようになる。タスクt34は、タスクt31の処理結果TEMP_T1_3とタスクt33の処理結果TEMP_T3_3を用いた結合演算の処理を行うタスクであり、TEMP_T1_3を検索先のリレーションとして使用し、TEMP_T3_3を検索元のリレーションとして使用することになるので、検索元のリレーションであるTEMP_T3_3に対して処理を行うタスクとして新たにグループG12を作成してグループG12にタスクt34を加える。
【０１６８】
次に、タスクt64の処理が終了すると、処理ツリーP6からわかるように、グループG7内のタスクt62の処理が終了していないので、新たに処理できるタスクは見出されないので新たなグループは作成されない。
最後に、タスクt14の処理が終了すると、処理ツリーP1からわかるようにグループG8内のタスクt12の処理が終了していないので新たなグループは作成されない。
以上のことをまとめると、グループG6内のタスクt33，t64，t14の処理が終了することによって見出されたタスクt34を次のようにグループG12に加えることになる。
TEMP_T3_3：グループ G12＝{t34}
(t34)：TEMP_T4_3←TEMP_T1_3 |X|DNUMBER=DNUMTEMP_T3_3
【０１６９】
このようにして、グループの処理を繰り返して行っていくうちに、図４−１〜図４−３に示した処理ツリー内のタスクが次第に終了していき、処理ツリー内すべてのタスクの処理が終了すると、与えられたすべてのクエリー処理は終了することになる。
【０１７０】
［３．実際の処理結果］
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー・プロセッサが、マルチオペレーション・プロセッシングを用いたクエリー・プロセッサ及び従来のクエリー・プロセッサ（ＭｙＳＱＬ Ｖｅｒ.３）よりも数多くのクエリーを早く処理することを証明するために、独自に開発したデータベースマネージメントシステム（ＤＢＭＳ）のソフトウェアＭＯＢ−ＤＢに新たに合成関係演算を利用したマルチオペレーション・プロセッシングの処理を行うことができる機能を追加した。ＭＯＢ−ＤＢは、ＭｙＳＱＬなど市場で幅広く使われているデータベースシステムよりも数多くのクエリーを高速に処理することを目的とし、ＳＱＬのインタープリタ、クエリーの最適化、トランザクションの同時処理、データを格納するストレージシステムなどデータベースマネージメントシステム（ＤＢＭＳ）に必要な十分な機能を備えたソフトウェアである。合成関係演算を利用したマルチオペレーション・プロセッシングの実験を行うにあたって、合成関係演算を利用したマルチオペレーション・プロセッシングには、スタティックマルチオペレーション・プロセッシングを使用することにした。
【０１７１】
独自に開発したＭＯＢ−ＤＢに、合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを用いたクエリー処理を追加したことによって、ＭＯＢ−ＤＢは合成関係演算を利用したスタティックマルチオペレーションを用いたクエリー処理、スタティックマルチオペレーション・プロセッシングを用いたクエリー処理、ダイナミックマルチオペレーション・プロセッシングを用いたクエリー処理を行うことができ、これらのクエリー処理方法を自由に選択して実行することが可能になった。
次にＭＯＢ−ＤＢを使用して、これらのクエリー処理方法によるクエリーの処理速度をそれぞれ調べた。さらに市場で幅広く使用されているＭｙＳＱＬのバージョン３と比較するために、共通のクエリー処理を行ってＭＯＢ−ＤＢとＭｙＳＱＬの処理速度を調べた。
【０１７２】
ＭＯＢ−ＤＢを用いてクエリー処理のテストを行うには、数多くのレコードを格納した十分に大きいデータベースが必要なため、Windows XP Professional(R)を搭載した一般のエントリーレベルのパーソナルコンピューター（１つのCeleron CPU 2.53GHzプロセッサ、512MBメインメモリ、１つの145GBディスク）上に、図１１のリレーションEMPLOYEE，DEPARTMENT，WORKS_ON，PROJECTと４つのリレーションから構成されるデータベースを作成し、それぞれのリレーションに１０万件ずつレコードを格納し、合計４０万件ほどのレコードをデータベースに加えた。クエリーを効率よく高速に処理するには、リレーションにインデックスが必要であるため、リレーションEMPLOYEE(1101)の主属性SSNに対して主インデックス(1100)を作成し、２次属性PHONEに対して２次インデックス(1102)を作成した。リレーションDEPARTMENT(1105)では、主属性DNUMBERに対して主インデックス(1104)を作成し、２次属性DPHONEに対して２次インデックス(1106)を作成した。リレーションPROJECT(1108)では、主属性PNUMBERに対して主インデックス(1107)を作成した。同様に、ＭｙＳＱＬバージョン３を用いた場合にも、４個のリレーションから構成される共通のデータベースを作成し、ＭＯＢ−ＤＢと同様に、データベース内のリレーションに対してインデックスを加えた。
【０１７３】
次に、データベースサーバーに問い合わせるクエリーは、それぞれのクエリー・プロセッサの処理能力を最大限に利用するために、複雑な検索処理を必要とする数多くの異なるクエリーをSQLで記述した。それらのクエリーは次のような条件や特性を持つものである。
【０１７４】
（１）問い合わせるクエリーには、同じクエリーが１つとして含まれないようにするため、すべてのクエリーの検索条件は異なるものにした。また、各クエリーには、演算、属性、変数からなる検索条件をブール演算のＡＮＤ，ＯＲを組み合わせて、さらに複雑な検索条件を持たせて絞込み検索を行うようにした。
【０１７５】
（２）クエリー・プロセッサによって十分な結合演算処理が行われるように、各クエリーには２つ以上の結合演算を含むようにした。また、クエリー・プロセッサによって必ず検索結果が得られるように、各クエリーには検索条件がゼロにならない検索条件を与えた。
【０１７６】
（３）クエリー・プロセッサによってあらゆる種類の処理結果が得られるように、１０００件以下の処理結果が得られるクエリー、１０００件から１万件の処理結果が得られるクエリー、１万件から５万件の処理結果が得られるクエリー、５万件から１０万件の処理結果が得られるクエリーをそれぞれ十分な数ほど（それぞれ２５パーセントずつ）データベースに問い合わせた。
【０１７７】
（４）クエリー・プロセッサによってインデックスを用いた検索が行われるように、検索条件に主インデックスを利用するクエリー、２次インデックスを利用するクエリー、主インデックスと２次インデックスの両方を利用するクエリーを与えた。また、インデックスを利用しないクエリーがインデックスを利用するクエリーと交わって処理されるように、選択条件に主インデックスと２次インデックスの両方を利用しないクエリーも与えた。
【０１７８】
ＭＯＢ−ＤＢの合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを用いたクエリー処理、ダイナミックマルチオペレーション・プロセッシングを用いたクエリー処理、スタティックマルチオペレーション・プロセッシングを用いたクエリー処理、及びＭｙＳＱＬバージョン３の処理速度を調べるために、データベースサーバーに検索処理を要求するクライアントプログラムを用意し、クライアントプログラムから数多くのＳＱＬで記述されたクエリーをデータベースサーバーに問い合わせて、データベースサーバー上のクエリー・プロセッサによってすべてのクエリーが処理されて、検索結果がクライアントプログラムに返されるまでの時間を測定する方法を用いた。クライアントコンピューターとデータベースサーバーとの間の通信速度の影響を避けるために、直接、データベースサーバー上でクライアントプログラムを起動させて、検索処理結果が得られるようにした。データベースに問い合わせるために作成したクエリーの数は、１００件、２００件、３００件、４００件、５００件、６００件、７００件、８００件、９００件、１０００件となるように、徐々に件数を増加させてクエリーの処理速度を測定した。同様に、ＭｙＳＱＬバージョン３に対しても、上述した件数と同数のクエリー数を用いて、ＭｙＳＱＬのクエリーの処理速度を測定して、ＭｙＳＱＬの処理速度とＭＯＢ−ＤＢを用いた合成関係演算を利用したスタティックマルチオペレーション・プロセッシング、ダイナミックマルチオペレーション・プロセッシング、スタティックマルチオペレーション・プロセッシングとの処理速度を比較した。
【０１７９】
図１２は、ＭＯＢ−ＤＢの合成関係演算を利用したスタティックマルチオペレーション・プロセッシング、ダイナミックマルチオペレーション・プロセッシング、スタティックマルチオペレーション・プロセッシング、及びＭｙＳＱＬのバージョン３に対して、数多くのクエリーを問い合わせたときに、クエリー数とクエリーの処理速度の関係を比較した結果を表（図１２（ａ）参照）とグラフ（図１２（ｂ）参照）で表わしたものである。
【０１８０】
図１２（ａ），（ｂ）に示した処理結果から、クエリー数が１００件から１０００件までの件数において、全体的に、合成関係演算を利用したスタティックマルチオペレーション・プロセッシングが最も早く、次にダイナミックマルチオペレーション・プロセッシングの処理速度が速く、その次にスタティックオペレーションプロセッシングとなり、ＭｙＳＱＬの処理速度が一番遅いことがわかる。
【０１８１】
合成関係演算を利用したスタティックマルチオペレーション・プロセッシングは、クエリー数が１００件から５００件までは、ダイナミックマルチオペレーション・プロセッシングよりも平均して1.64倍の処理速度が得られ、スタティックマルチオペレーション・プロセッシングよりも平均して1.76倍の処理速度が得られ、ＭｙＳＱＬバージョン３の処理速度よりも平均して6.34倍の処理速度が得られ、クエリー数が６００件から１０００件まででは、ダイナミックマルチオペレーション・プロセッシングよりも平均して1.65倍の処理速度が得られ、スタティックマルチオペレーション・プロセッシングよりも平均して、1.79倍の処理速度が得られ、ＭｙＳＱＬバージョン３の処理速度よりも平均して6.47倍の処理速度が得られた。
【０１８２】
以上のように、合成関係演算を利用したスタティックマルチオペレーション・プロセッシングは、これらのクエリー・プロセッサよりも処理速度が改善され、ＭｙＳＱＬバージョン３よりも6.34〜6.47倍の処理速度の向上が見られ、クエリー数が増加するにつれて、処理速度が向上していく傾向がある。
【図面の簡単な説明】
【０１８３】
【図１】データベースシステムのアーキテクチャの構成例を示す図である。
【図２】クエリーを処理するフローチャートである。
【図３−１】実施形態で使用するデータベースのリレーションDEPARTMENTを示す図である。
【図３−２】実施形態で使用するデータベースのリレーションEMPLOYEEを示す図である。
【図３−３】実施形態で使用するデータベースのリレーションPROJECT，WORKS_ONを示す図である。
【図４−１】処理ツリーP１を示す図である。
【図４−２】処理ツリーP2，P3，P4を示す図である。
【図４−３】処理ツリーP5，P6を示す図である。
【図５】タスクのグループ分け及びサブグループ分けを説明する図である。
【図６】合成選択演算の最適化を説明する図である。
【図７】合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを説明する図である。
【図８−１】合成選択演算の処理結果を共有するための手順を説明する図である。
【図８−２】合成選択演算の処理結果を共有するための手順（続き）を説明する図である。
【図９】合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを説明する図である。
【図１０】合成関係演算タスクの処理結果として得られたリレーションに対するスタティックマルチオペレーション・プロセッシングを説明する図である。
【図１１】実際に処理を行ったデータベースのリレーションを示す図である。
【図１２】処理結果を示す図である。
【図１】
2008234495.tif 000007
【図２】
2008234495.tif 000008
【図３−１】
2008234495.tif 000009
【図３−２】
2008234495.tif 000010
【図３−３】
2008234495.tif 000011
【図４−１】
2008234495.tif 000012
【図４−２】
2008234495.tif 000013
【図４−３】
2008234495.tif 000014
【図５】
2008234495.tif 000015
【図７】
2008234495.tif 000016
【図９】
2008234495.tif 000017
【図１０】
2008234495.tif 000018
【図１１】
2008234495.tif 000019
【図１２】
2008234495.tif 000020
【図６】
2008234495.tif 000021
【図８−１】
2008234495.tif 000022
【図８−２】
2008234495.tif 000023
【手続補正書】
【提出日】平成19年6月12日(2007.6.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
また、合成関係演算タスクの処理結果として得られたリレーションのアクセス領域ごとにも、タスクをグループ分けすることによって、そのリレーションの共通ブロック上でタスク処理を一度に行うことができるようになり、ディスクをアクセスする回数を減少させ、極めて効率的にタスク処理を行うことができるようになった。
実験の処理結果からもわかるように、これまで広く使用されているMySQL.Ver3や以前のマルチオペレーション・プロセッシングのみを用いたクエリー・プロセッサよりも一段と数多くのクエリーの処理を高速に行うことができるようになった。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
また、スタティックマルチオペレーション・プロセッシングは、グループ内の各タスクからアクセスプランを作成し、アクセスプランから各タスクの処理コストを求め、求めた処理コストを参照して、処理コストの１番小さいタスクから処理コストの１番大きいタスクへと順番にグループ内の各タスクを並べることにする。ここまでは、ダイナミックマルチオペレーション・プロセッシングと同じ手順である。次にデータベースのインデックスを使用して、グループ内の各タスクが、共通のリレーション内のブロックからタスク処理を行うためにアクセスする必要のあるブロックを調べて、各タスクに対応するブロック集合に集める。次に、前に求めた処理コストの小さいタスクから処理コストの大きいタスクまでの順番にしたがって、各タスクに対応するブロック集合の和集合を求めていくことによって、アクセスするブロックの順位を決定する。その順位にしたがって共通のリレーション内のブロックをディスクからアクセスし、このブロックを共通ブロックとして、このブロック上で処理を行う必要のあるグループ内のタスク処理を一度に処理していく方法である。この方法は、アクセスすべきブロック（共通ブロック）の順位にしたがって、和集合、積集合及び差集合などの集合論を用いて、クエリーに含まれる各タスクの処理をきわめて論理的に行うものである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
［（ａ）ステップ１：タスクのサブグループ化］
共通のリレーションRに対してグループ内のタスクの処理を行うに当たって、次のようにタスク間の共通部分式に関する定義を定めて、グループ内のタスクを共通部分式ごとにサブグループに集める(S170)。
・共通部分式に関する定義：
次に示す選択演算，射影演算，及びその他の演算に関する条件を満たすならば、タスクtiとタスクtjは共通部分式をもっている。
・選択演算：
タスクtiは、リレーションRに対して属性A1,A2,A3,…,Akに関する選択条件(ＡＮＤ，ＯRで結合したもの)を使用する選択演算タスクであり、タスクtjは、同一のリレーションRに対して同一の属性A1,A2,A3,…,Akに関する選択条件(ＡＮＤ，ＯＲで結合したもの)を使用する選択演算タスクであるときに、タスクtiとタスクtjが使用する選択条件において、１つの属性Ai(1≦i≦k)に関する選択条件だけは異なった条件かまたは同じ条件であり、Ai以外の属性に関する選択条件はまったく同じ条件である。
・射影演算：
タスクtiは、リレーションRに対する射影演算タスクであり、タスクtjは、同一のリレーションRに対する射影演算タスクである。
・その他の関係演算：
tiとtjは、同一の関係演算のタスク（ti≡tj)である。
以上の定義の条件に用いた演算は、あくまでも共通部分式に関するものである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００７４
【補正方法】変更
【補正の内容】
【００７４】
以上のように得られた合成関係演算タスクを説明すると、以下のようになる。
タスクtG1SG1は、下記に示すようにサブグループSG1G1内の選択演算タスクt13，t32，t63の選択条件をブール演算のORを用いて接続して１つの選択条件<temp_cond>を作成し、接続した選択条件から選択範囲の重複した部分を取り除くために、簡潔化し最適化Optimize(<temp_cond>)した選択条件を作成し、その選択条件を用いた合成選択演算タスクである。
<temp_cond>＝(BDATE<'DEC-31-1961') OR (BDATE>'JAN-1-1971') OR
(BDATE>'FEB-11-1959' AND BDATE<'NOV-21-1966')
Optimize(<temp_cond>) ⇒ BDATE<'NOV-21-1966' OR BDATE>'JAN-1-1971'
Optimize(<temp_cond>)によって表わされる選択条件は、ブール演算のＯＲを用いて作成した選択条件<temp_cond>を最適化するために、それぞれの選択条件の選択範囲の論理和（Union）を求めて、選択範囲の重複した部分を取り除いて新たに簡潔化された選択条件として得られたものである。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１００
【補正方法】変更
【補正の内容】
【０１００】
［（ａ−６）サブグループ内のタスクによる合成選択演算の処理結果の共有］
図７において、合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1(503)は、サブグループ内のタスクt13，t32，t63の処理結果のすべてを含んでいるため、サブグループ内のタスクt13，t32，t63は、合成選択演算タスクtG1SG1の処理結果TEMP_SG1_G1(503)を部分的に共有することになる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１５８
【補正方法】変更
【補正の内容】
【０１５８】
［（ｆ−３）各タスクに対応するブロック集合］
仮想リレーションに記録してある情報をもとに、タスクt33，t64，t14がリレーションTEMP_SG1_G1からアクセスする必要のあるブロックを調べて、各タスクに対応するブロック集合B33，B64，B14に集めると、次のようになる。
タスクt33に対して：B33＝{b4}
タスクt64に対して：B64＝{b2,b3}
タスクt14に対して：B14＝{b1,b2,b3}
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１５９
【補正方法】変更
【補正の内容】
【０１５９】
［（ｆ−４）アクセスすべきブロック（共通ブロック）の順位の決定］
以上のように、各タスクに対応するブロック集合を見出した後に、処理コストの小さいタスクから処理コストの大きいタスクへと順番に、すなわちタスクt33，t64，t14の順番に各タスクに対応するブロック集合の和集合を求めていくことにする。
まず、TB0＝{}（空集合）として、TB0とタスクt33に対応するブロック集合B33と和集合TB33を求める。次に、このTB33とタスクt64に対応するブロック集合B64との和集合TB64を求める。さらに、このTB64とタスクt14に対応するブロック集合B14との和集合TB14を求めると次のようになる。この場合、和集合を求めるに当たっては、新たに加える集合は和集合の中で最後に加えていくものとする。
TB0＝{}
タスクt33に対応する集合B33との和集合：TB33＝TB0∪B33＝{b4}
タスクt64に対応する集合B64との和集合：TB64＝TB33∪B64＝{b4,b2,b3}
タスクt14に対応する集合B14との和集合：TB14＝TB64∪B14＝{b4,b2,b3,b1}
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１７０
【補正方法】変更
【補正の内容】
【０１７０】
［３．実験の処理結果］
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたクエリー・プロセッサが、マルチオペレーション・プロセッシングを用いたクエリー・プロセッサ及び従来のクエリー・プロセッサ（ＭｙＳＱＬ Ｖｅｒ.３）よりも数多くのクエリーを早く処理することを証明するために、独自に開発したデータベースマネージメントシステム（ＤＢＭＳ）のソフトウェアＭＯＰ−ＤＢに新たに合成関係演算を利用したマルチオペレーション・プロセッシングの処理を行うことができる機能を追加した。ＭＯＰ−ＤＢは、ＭｙＳＱＬなど市場で幅広く使われているデータベースシステムよりも数多くのクエリーを高速に処理することを目的とし、ＳＱＬのインタープリタ、クエリーの最適化、トランザクションの同時処理、データを格納するストレージシステムなどデータベースマネージメントシステム（ＤＢＭＳ）に必要な十分な機能を備えたソフトウェアである。合成関係演算を利用したマルチオペレーション・プロセッシングの実験を行うにあたって、合成関係演算を利用したマルチオペレーション・プロセッシングには、スタティックマルチオペレーション・プロセッシングを使用することにした。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１７１
【補正方法】変更
【補正の内容】
【０１７１】
独自に開発したＭＯＰ−ＤＢに、合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを用いたクエリー処理を追加したことによって、ＭＯＰ−ＤＢは合成関係演算を利用したスタティックマルチオペレーションを用いたクエリー処理、スタティックマルチオペレーション・プロセッシングを用いたクエリー処理、ダイナミックマルチオペレーション・プロセッシングを用いたクエリー処理を行うことができ、これらのクエリー処理方法を自由に選択して実行することが可能になった。
次にＭＯＰ−ＤＢを使用して、これらのクエリー処理方法によるクエリーの処理速度をそれぞれ調べた。さらに市場で幅広く使用されているＭｙＳＱＬのバージョン３と比較するために、共通のクエリー処理を行ってＭＯＰ−ＤＢとＭｙＳＱＬの処理速度を調べた。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１７２
【補正方法】変更
【補正の内容】
【０１７２】
ＭＯＰ−Ｄを用いてクエリー処理のテストを行うには、数多くのレコードを格納した十分に大きいデータベースが必要なため、Windows XP Professional(R)を搭載した一般のエントリーレベルのパーソナルコンピューター（１つのCeleron CPU 2.53GHzプロセッサ、512MBメインメモリ、１つの145GBディスク）上に、図１１のリレーションEMPLOYEE，DEPARTMENT，WORKS_ON，PROJECTと４つのリレーションから構成されるデータベースを作成し、それぞれのリレーションに１０万件ずつレコードを格納し、合計４０万件ほどのレコードをデータベースに加えた。クエリーを効率よく高速に処理するには、リレーションにインデックスが必要であるため、リレーションEMPLOYEE(1101)の主属性SSNに対して主インデックス(1100)を作成し、２次属性PHONEに対して２次インデックス(1102)を作成した。リレーションDEPARTMENT(1105)では、主属性DNUMBERに対して主インデックス(1104)を作成し、２次属性DPHONEに対して２次インデックス(1106)を作成した。リレーションPROJECT(1108)では、主属性PNUMBERに対して主インデックス(1107)を作成した。同様に、ＭｙＳＱＬバージョン３を用いた場合にも、４個のリレーションから構成される共通のデータベースを作成し、ＭＯＰ−ＤＢと同様に、データベース内のリレーションに対してインデックスを加えた。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１７８
【補正方法】変更
【補正の内容】
【０１７８】
ＭＯＰ−ＤＢの合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを用いたクエリー処理、ダイナミックマルチオペレーション・プロセッシングを用いたクエリー処理、スタティックマルチオペレーション・プロセッシングを用いたクエリー処理、及びＭｙＳＱＬバージョン３の処理速度を調べるために、データベースサーバーに検索処理を要求するクライアントプログラムを用意し、クライアントプログラムから数多くのＳＱＬで記述されたクエリーをデータベースサーバーに問い合わせて、データベースサーバー上のクエリー・プロセッサによってすべてのクエリーが処理されて、検索結果がクライアントプログラムに返されるまでの時間を測定する方法を用いた。クライアントコンピューターとデータベースサーバーとの間の通信速度の影響を避けるために、直接、データベースサーバー上でクライアントプログラムを起動させて、検索処理結果が得られるようにした。データベースに問い合わせるために作成したクエリーの数は、１００件、２００件、３００件、４００件、５００件、６００件、７００件、８００件、９００件、１０００件となるように、徐々に件数を増加させてクエリーの処理速度を測定した。同様に、ＭｙＳＱＬバージョン３に対しても、上述した件数と同数のクエリー数を用いて、ＭｙＳＱＬのクエリーの処理速度を測定して、ＭｙＳＱＬの処理速度とＭＯＰ−ＤＢを用いた合成関係演算を利用したスタティックマルチオペレーション・プロセッシング、ダイナミックマルチオペレーション・プロセッシング、スタティックマルチオペレーション・プロセッシングとの処理速度を比較した。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１７９
【補正方法】変更
【補正の内容】
【０１７９】
図１２は、ＭＯＰ−ＤＢの合成関係演算を利用したスタティックマルチオペレーション・プロセッシング、ダイナミックマルチオペレーション・プロセッシング、スタティックマルチオペレーション・プロセッシング、及びＭｙＳＱＬのバージョン３に対して、数多くのクエリーを問い合わせたときに、クエリー数とクエリーの処理速度の関係を比較した結果を表（図１２（ａ）参照）とグラフ（図１２（ｂ）参照）で表わしたものである。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１８０
【補正方法】変更
【補正の内容】
【０１８０】
図１２（ａ），（ｂ）に示した処理結果から、クエリー数が１００件から１０００件までの件数において、全体的に、合成関係演算を利用したスタティックマルチオペレーション・プロセッシングが最も早く、次にダイナミックマルチオペレーション・プロセッシングの処理速度が速く、その次にスタティックマルチオペレーション・プロセッシングとなり、ＭｙＳＱＬの処理速度が一番遅いことがわかる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１８２
【補正方法】変更
【補正の内容】
【０１８２】
【図１】データベースシステムのアーキテクチャの構成例を示す図である。
【図２】クエリーを処理するフローチャートである。
【図３−１】実施形態で使用するデータベースのリレーションDEPARTMENTを示す図である。
【図３−２】実施形態で使用するデータベースのリレーションEMPLOYEEを示す図である。
【図３−３】実施形態で使用するデータベースのリレーションPROJECT，WORKS_ONを示す図である。
【図４−１】処理ツリーP１を示す図である。
【図４−２】処理ツリーP2，P3，P4を示す図である。
【図４−３】処理ツリーP5，P6を示す図である。
【図５】タスクのグループ分け及びサブグループ分けを説明する図である。
【図６】合成選択演算の最適化を説明する図である。
【図７】合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを説明する図である。
【図８−１】合成選択演算の処理結果を共有するための手順を説明する図である。
【図８−２】合成選択演算の処理結果を共有するための手順（続き）を説明する図である。
【図９】合成関係演算を利用したスタティックマルチオペレーション・プロセッシングを説明する図である。
【図１０】合成関係演算タスクの処理結果として得られたリレーションに対するスタティックマルチオペレーション・プロセッシングを説明する図である。
【図１１】実際に処理を行ったデータベースのリレーションを示す図である。
【図１２】実験の処理結果を示す図である。
【手続補正書】
【提出日】平成19年10月15日(2007.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、
前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、
前記処理ツリーから、トポロジカル・ソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、
前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするグループ分け手段と、
グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、
前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、
グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備え、
前記グループ分け手段は、前記合成関係演算タスクの処理結果として得られたリレーションごとにも、タスクをグループ分けすることを特徴とするクエリー処理システム。
【請求項２】
請求項１記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、サブグループに集めた複数の選択演算タスクで使用する属性名と属性数が等しいときに、それらの属性の中の１つの属性に関する選択条件だけが異なった条件かまたは同じ条件であり、それ以外の属性に関する選択条件はまったく同じであるならば、それらの選択条件をブール演算のＯＲを使用して接続し、接続した選択条件から選択範囲の重複した部分を取り除くために、簡潔化して最適化した選択条件を作成し、その選択条件を用いて複数の選択演算タスクの合成関係演算を作成することを特徴とするクエリー処理システム。
【請求項３】
請求項１記載のクエリー処理システムにおいて、
前記合成関係演算作成手段は、サブグループに集めた複数の射影演算タスクが、共通のリレーションに対して射影演算の処理を行うならば、これらの射影演算タスクの属性の和集合を求めて得られた属性を用いて、複数の射影演算タスクの合成関係演算を作成することを特徴とするクエリー処理システム。
【請求項４】
請求項１〜３のいずれかに記載のクエリー処理システムにおいて、
前記仮想リレーション作成手段は、仮想リレーションのレコードに対してタスクが検索処理を行う場合、仮想リレーションが部分的に共有するリレーションの検索に使用する属性に対して、インデックスを作成することを特徴とするクエリー処理システム。
【請求項５】
請求項１〜４のいずれかに記載の合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラム。
【請求項６】
請求項１〜４のいずれかに記載のマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムを記録した記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
上記発明の目的を達成するために、本発明は、合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムであって、前記クエリーを関係代数による処理ツリーに変換する処理ツリー変換手段と、前記処理ツリーから、トポロジカルソートにより、関係代数を他の関係代数の結果に依存しないで実施できる順番に、タスクとして取り出すタスク取り出し手段と、前記取り出したタスクを、前記データベースのリレーションごとにグループ分けするグループ分け手段と、グループ分けされた前記タスクに対して、共通部分式を持つタスクをさらにサブグループに集め、合成関係演算タスクを作成する合成関係演算作成手段と、前記グループ分けされたタスクごとに、作成された前記合成関係演算タスクとサブグループに集まらないタスクとに対してマルチオペレーション・プロセッシングを行うマルチオペレーション・プロセッシング手段と、グループ内の前記合成関係演算タスクの処理結果として得られたリレーションに対して、前記合成関係演算に含まれる個々のタスクが、そのリレーションのレコード及び／又は属性を部分的に共有するように、格納位置による仮想リレーションを作成する仮想リレーション作成手段とを備え、前記グループ分け手段は、前記合成関係演算タスクの処理結果として得られたリレーションごとにも、タスクをグループ分けすることを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
前記合成関係演算作成手段は、サブグループに集めた複数の選択演算タスクで使用する属性名と属性数が等しいときに、それらの属性の中の１つの属性に関する選択条件だけが異なった条件かまたは同じ条件であり、それ以外の属性に関する選択条件はまったく同じであるならば、それらの選択条件をブール演算のＯＲを使用して接続し、接続した選択条件から選択範囲の重複した部分を取り除くために、簡潔化して最適化した選択条件を作成し、その選択条件を用いて複数の選択演算タスクの合成関係演算を作成するとよい。
前記合成関係演算作成手段は、サブグループに集めた複数の射影演算タスクが、共通のリレーションに対して射影演算の処理を行うならば、これらの射影演算タスクの属性の和集合を求めて得られた属性を用いて、複数の射影演算タスクの合成関係演算を作成するとよい。
前記仮想リレーション作成手段は、仮想リレーションのレコードに対してタスクが検索処理を行う場合、仮想リレーションが部分的に共有するリレーションの検索に使用する属性に対して、インデックスを作成するとよい。
上述した合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システムの各機能を、コンピュータ・システムに実現させるためのプログラムやプログラムを記録した記録媒体も本発明である。