【手続補正書】
【提出日】平成23年9月22日(2011.9.22)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、継続的に生成される時系列データを処理する技術に関し、特に、ストリームデータ処理における、再帰的処理を含む一般のデータ処理を、安定した低レイテンシで、かつ高レートで継続してリアルタイムに実行する技術に関する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
【非特許文献１】Ｂ．Ｂａｂｃｏｃｋ，Ｓ．Ｂａｂｕ，Ｍ．Ｄａｔａｒ，Ｒ．Ｍｏｔ    ｗａｎｉ  ａｎｄ  Ｊ．Ｗｉｄｏｍ，“Ｍｏｄｅｌｓ  ａｎｄ  ｉｓｓｕｅｓ  ｉｎ      ｄａｔａ  ｓｔｒｅａｍ  ｓｙｓｔｅｍｓ”，Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＰＯＤＳ      ２００２，  ｐｐ．１−１６．（２００２）
【非特許文献２】Ｔ．Ｊｏｈｏｎｓｏｎ，Ｓ．Ｍｕｔｈｕｋｒｉｓｈｎａｎ，Ｖ．Ｓ    ｈｋａｐｅｎｙｕｋ  ａｎｄ  Ｏ．Ｓｐａｔｓｃｈｅｃｋ，“Ａ  Ｈｅａｒｔｂｅａ    ｔ  Ｍｅｃｈａｎｉｓｍ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｉｎ  Ｇｉｇ    ａｓｃｏｐｅ”，Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＶＬＤＢ  ２００５，  ｐｐ．１０７９    −１０８８．（２００５）
【非特許文献３】Ｂ． Ｂａｂｃｏｃｋ， Ｓ． Ｂａｂｕ， Ｍ． Ｄａｔａｒ， Ｒ．     Ｍｏｔｗａｎｉ， ａｎｄ Ｄ． Ｔｈｏｍａｓ． “Ｏｐｅｒａｔｏｒ Ｓｃｈｅｄｕ    ｌｉｎｇ ｉｎ Ｄａｔａ Ｓｔｒｅａｍ Ｓｙｓｔｅｍｓ”，（２００５）
【非特許文献４】Ａ． Ａｒａｓｕ， Ｓ． Ｂａｂｕ  ａｎｄ Ｊ． Ｗｉｄｏｍ. “    Ｔｈｅ ＣＱＬ Ｃｏｎｔｉｎｕｏｕｓ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ： Sｅｍａｎｔ    ｉｃ Ｆｏｕｎｄａｔｉｏｎｓ  ａｎｄ Ｑｕｅｒｙ Ｅｘｅｃｕｔｉｏｎ”，（２０    ０５）
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
ハートビートタプルを利用する第１の問題は、データタプルの処理タイミングが、ハートビートタプルの送信間隔に律速される点である。例えば、プラスタプル４９０の５分後の９：１４’２４のタイムスタンプで時間ウィンドウオペレータ４３１から出力されるマイナスタプル４９１は、９：１５’００のハートビートタプルが到来するまで待たされることになるため、３６秒の処理タイミングの遅れとなっている。これは、クエリ３１３の売り注文を出すタイミングの遅れを意味する。一方、ＲＳｔｒｅａｍオペレータ４６３においても、ストリームタプル４９５，４９６の出力タイミングは、ハートビートタプル４９７が到来するまで待たされる。タプル４９５，４９６それぞれに関して６０秒、３０秒の処理タイミングの遅れとなっている。また、３０秒間隔で出力されるべきタプルが、１分間隔で同時に２個出力される動作になっている。これは、クエリ３１６の売り買い両注文を出すタイミングの不正を意味する。以上のように、平均してハートビートタプル送信間隔の半分の時間が、レイテンシとして現れてしまう。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
また、ストリームデータの分析結果をリアルタイムにビジネスに活用するためには、外部からの入力などの変化に対するアクションのみでなく、それに伴うストリームデータ処理システム内のデータ処理結果を含む内部状況の変化を迅速に反映して、次のアクションを決定する必要がある。このような処理を、従来のハートビートタプルによる実行方式で実現することが困難であることを、図５、および図６を用いて示す。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
図６は、このクエリの実行木を示す。実行木６７０，６７１，６７２，６７４は、それぞれオペレータ６００〜６０７，６１０，６２０〜６２６，６４０〜６４１より構成され、それぞれクエリ３１０，３１１，５１２，３１４に対応している。該実行木におけるｓｃａｎオペレータ６００，６２０，６４０からは、データタプルやハートビートタプルが出力される。しかし、これらのタプルは、それぞれ二項オペレータ６０５，６２５，６０４によって停滞する。原因は、これらのオペレータにおける他方の入力が、オペレータ６１０−６０４−６０５−６０６−６０７−６２２−６２３−６２４−６２５−６２６−６１０で形成される閉ループのパス上にあり、該ループ上を一切タプルが流れないことにある。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
図７は、図５のクエリを実行する際の、タプルの値、タイムスタンプ、生存期間を示している。なお、オペレータ６０２，６０４，６２５の処理については、煩雑になるため本図には含めていない。時刻ｔ０においてｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍに３００００００の値を持つストリームタプルが入力されると、個数ウィンドウオペレータ６１０によって、最新の資金額を表すｒｅｓｏｕｒｃｅリレーションに変換される。ここで、時刻ｔ１において、入力ストリームｍａｒｋｅｔにストリームタプルが入力されると、ウィンドウオペレータ６０１によって、論理的な微小時間の生存期間を持つリレーションに変換される。これと、リレーションｒｅｓｏｕｒｃｅがジョインオペレータ６０５によって結合され、射影オペレータ６０６、ストリーム化演算６０７を介して、買い注文を表すストリームｂｕｙ＿ｅｖｅｎｔのタプルとして出力される。該タプルは、オペレータ６２２，６２３，６２４を介してリレーションｒｅｓｏｕｒｃｅと結合され、買い注文を反映した新たな資金額２５２００００を表すリレーションとして出力される。該リレーションはストリーム化演算６２６によって、時刻ｔ１のタプルとしてストリームｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍに追加される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
以上のように、再帰的なクエリは、ハートビートタプルによる実行制御方法の問題、およびストリーム化演算の制限によって実行できない。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
本発明の目的は、従来の実行制御方法におけるレイテンシに関する課題を解決する実行制御方式を用いたストリームデータ処理方法、及びそのシステムを提供することにある。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
本発明の他の目的は、従来の実行制御方法における再帰クエリを実現できないという課題を解決し、更にはストリーム化演算の制限を回避する実行制御方式を用いたストリームデータ処理方法、及びそのシステムを提供することにある。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
クエリ実行の前段階において、複数のクエリの実行木を連結した単一のオペレータグラフを形成し、このオペレータグラフの外部からタプルを入力する外部発火オペレータ、および、時間ウィンドウ、ＲＳｔｒｅａｍといった内部発火オペレータを抽出する。本明細書では、外部発火オペレータと内部発火オペレータの両者を合わせて発火オペレータと呼ぶ。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
そして、オペレータグラフに属する全オペレータ集合上に全順序を定める。この順序は、オペレータ間の入出力関係における出力側のオペレータが入力側のオペレータより大となるような順序付けとする。そして、本明細書においては、この順序をオペレータ実行順序と呼ぶ。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
また、クエリ実行においては、各発火オペレータが次回実行された際に出力するタプルのタイムスタンプを、発火オペレータの発火時刻と呼ぶ。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
このとき、本発明においては、以下のような処理のループによって、クエリの実行を制御する。
（１）発火オペレータ群において、最も早い発火時刻のオペレータを選択する。選択されたオペレータを実行オペレータと呼ぶ。また、その発火時刻を実行時刻と呼ぶ。
（２）（１）で選択した実行オペレータを起点として、オペレータ実行順序の昇順に、オペレータグラフの出口までオペレータを順次実行する。
（３）この実行時刻をタイムスタンプとするタプルの処理を全て実行し、オペレータグラフ上から該当する発火時刻のタプルが無くなったら（１）に戻る。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００４０
【補正方法】変更
【補正の内容】
【００４０】
また、本発明においては、オペレータグラフがループを含む場合には、オペレータ実行順序を定めることができないので、グラフを強連結成分に分解する。強連結成分とは、有向グラフにおいて、互いに到達し合う関係にあるノードの集合である。これにより成分間にはループが存在しなくなるので、成分間の実行順序を決定することができる。さらに、成分内のオペレータ実行順序を決定するアルゴリズムを提供する。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
全オペレータの処理を実行時刻ごとに完結しつつ実行を進めるため、処理の各ループにおいて各オペレータの実行可能時刻が自ずと決まるので、ハートビートが不要である。従って、従来の実行制御方法における、レイテンシに関する課題を解決する。即ち、
（１）レイテンシを律速する要因はない。
（２）オペレータ間で処理タイミングにズレがないため、オペレータの実行順の非決定性によるレイテンシが発生しない。
（３）データタプル以外の無駄なタプルを処理するオーバヘッドは存在しない。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
また、再帰クエリの実行可能性に関して、実行木がループを持つため、従来のハートビートを利用する実行制御では実現不可であったが、本発明ではハートビートが不要となったことで実行が可能となる。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】削除
【補正の内容】
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００６４
【補正方法】削除
【補正の内容】
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】削除
【補正の内容】
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】削除
【補正の内容】
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００６７
【補正方法】削除
【補正の内容】
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００６８
【補正方法】削除
【補正の内容】
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
図１２は、オペレータグラフ解析部９０８で、オペレータ実行順序を決定するアルゴリズムのフローチャートである。また、図１３Ａは、該フローチャートにおいて使用するデータ構造である。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】００８４
【補正方法】変更
【補正の内容】
【００８４】
状態１８１０は、図８Ｂに示すシステムタイム９：１３’３０の実行木において、処理１７０１を実施した状態である。実行オペレータリスト１６０１には、オペレータ４４０、および４６３が格納され、オペレータ実行順表１４００より、それぞれのオペレータ実行順序は３、および２４であることが分かるので、実行オペレータフラグ配列１８００の３番目と２４番目の要素のみをＴｒｕｅとする。状態１８１１は、処理１７０２のループにおけるインデクス４の処理１７０４にて、該インデクスをオペレータ実行順序に持つオペレータ４４１の処理を実行し、出力結果があったため、処理１７０６を実施した状態である。オペレータ４４１の出力先である、オペレータ４３２、および４０３それぞれのオペレータ実行順序である、５番目、および１２番目の配列要素がＴｒｕｅとなる。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
複数のクエリを一つのクエリとみなして、実行木を構築し、データタプルの時刻情報が所定の条件を満たす場合に、実行される所定のオペレータの処理を契機として、入力タプルを構築された実行木を順に実行し、処理を完了する。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
以上示したように、図１７のフローは配列を用いた実行制御方法である。本実施例に限らずオペレータ実行順序を守る実行制御方法として、例えば、オペレータを実行する度に、その出力先に位置するオペレータを全て記憶し、その中で最小の実行順序を持つオペレータを実行することを繰り返す方法、オペレータ実行順序を付与する対象をストリーム化演算だけに絞り、実行制御を柔軟化する方法がある。
［実施例２］
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
以下では、第二の実施例として、再帰クエリの実行制御を行うストリームデータ処理システムについて説明する。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】００９４
【補正方法】変更
【補正の内容】
【００９４】
図２１は、図２０のクエリの実行木であり、オペレータ２１２７として遅延演算を含んでいる。この実行木はループを含んでおり、オペレータ間の入出力関係が相互再帰になっているため、図１０〜１４を用いて説明したアルゴリズムでは、オペレータ実行順序を定めることができない。図２１の四角枠内に示すオペレータ実行順序は、ループ上に位置しないオペレータである２１００，２１０１，２１０２，２１２０，２１２１，２１４０，２１４１，２１０３の８個については定まるが、それ以外は定義できないことを示している。
【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
図２５Ａは、該強連結成分に含まれない９個のオペレータについてオペレータ実行順を付与している。具体的には、１番目がオペレータ２４３０、２番目がオペレータ２４３１、３番目がオペレータ２４５０、４番目がオペレータ２４５１、５番目がオペレータ２４００、６番目がオペレータ２４０１、７番目がオペレータ２４０２、８番目がオペレータ２４２０、９番目がオペレータ２４２１である。各オペレータの右下の四角で囲まれた数字が、それぞれのオペレータの実行順番を示す。
【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】０１０２
【補正方法】変更
【補正の内容】
【０１０２】
図２５Ｂは、遅延演算２４５７で強連結成分を展開した実行木を示している。但し、破線２５０１に囲まれた１１個のオペレータは、なお強連結成分を形成している。該強連結成分を一つの仮想的なオペレータと捉えると、オペレータ実行順序１０〜２０、および３２〜３４については、定めることが可能である。破線２５０１内のオペレータには２１〜３１の実行順序が付く。図２５Ｃは、該強連結成分を遅延演算２４２７で展開し、２１〜３１の実行順序を定めた様子を示している。最終的には、実行木に属する全オペレータの実行順序が、図２６の四角枠で囲む数字で示すように定まる。クエリ実行時において、オペレータ２４２７が実行オペレータとなった場合、該オペレータを起点とするオペレータの実行は、太曲線矢印のパスに沿って進行することになる。
【手続補正３１】
【補正対象書類名】明細書
【補正対象項目名】０１１３
【補正方法】変更
【補正の内容】
【０１１３】
つまり、（３−１）ストリームデータ処理システム９００は、複数のオペレータで構成されるオペレータグラフをそれぞれノードに展開し、tree構造から一以上のオペレータにより閉路（再帰）になっている箇所をコンポーネント化する。図２５や図２６中の強連結成分や部分グラフが、コンポーネントやサブコンポーネントに対応し、仮想的なオペレータである。（３−２）次に、ストリームデータ処理システム９００は、生成したコンポーネント単位で、コンポーネント間の入出力関係を特定する。（３−３）ストリームデータ処理システム９００は、特定された入出力関係で、コンポーネントごとの実行順序を定義する。（３−４）ストリームデータ処理システム９００は、各コンポーネントに対してオペレータを複数含むか判断し、複数含む場合は、データタプルの入力遅延を設定するＤｅｌａｙＳｔｒｅａｍを構成するオペレータを閉路に追加する。（３−５）さらにストリームデータ処理システム９００は、各コンポーネント内（閉路部分）のノードを新たなサブコンポーネントとして再展開し、同様の（３−２）ないし（３−４）の処理を繰り返す。
【手続補正３２】
【補正対象書類名】明細書
【補正対象項目名】０１１６
【補正方法】変更
【補正の内容】
【０１１６】
図３０Ａ〜Ｇは、図２８に示したアルゴリズムの処理における、データ構造の状態遷移を表している。