(57)【要約】【課題】与えられたデータから複雑なクエリにより指定された順序パターンを効率良く抽出する。【解決手段】述語列ｐ［０］，．．．，ｐ［３］にマッチするレコード列を検索するとき、あらかじめ述語同士の両立性を解析することで最適なウィンドウシフト量が決められ、ウィンドウ内においてシフト方向とは逆向きに各述語がチェックされる。まず、ウィンドウ２１の位置で値４２がｐ［１］を満たさないことが分かると、ウィンドウ２１を１レコード分シフトし、ウィンドウ２２内でチェックが再開される。次に、値３６がｐ［２］を満たさないことが分かると、ウィンドウ２２を３レコード分シフトし、ウィンドウ２３の位置ですべての値が対応する述語を満たすことが確認される。【選択図】　　　図２
2004046601.tif 000002
【特許請求の範囲】
【請求項１】
複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するデータ処理装置であって、
データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力する入力手段と、
前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成する前処理手段と、
前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定する検索手段と、
前記条件列のすべての条件を満たしたデータ列の情報を出力する出力手段と
を備えることを特徴とするデータ処理装置。
【請求項２】
前記前処理手段は、前記ｍ個の条件からなる条件列上の各位置を右端とする部分条件列であって、該ｍ個の条件からなる条件列の右端の部分条件列と両立するような部分条件列の長さの最大値を表す配列を生成し、該配列を用いて前記補助情報を生成することを特徴とする請求項１記載のデータ処理装置。
【請求項３】
レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するデータ処理装置であって、
前記パターンを入力する入力手段と、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成する前処理手段と、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定する検索手段と、
前記パターンのすべての述語を満たしたレコード列の情報を出力する出力手段と
を備えることを特徴とするデータ処理装置。
【請求項４】
前記前処理手段は、複数の条件式が述語に含まれているとき、該複数の条件式を分離して解析することを特徴とする請求項３記載のデータ処理装置。
【請求項５】
前記前処理手段は、位置ｊを右端とし述語ｐ［ｊ−ｌｅｎ＋１］，．．．，ｐ［ｊ］からなる述語列であって、述語ｐ［ｍ−ｌｅｎ］，．．．，ｐ［ｍ−１］からなる述語列と両立するような述語列の長さｌｅｎの最大値を表す配列を生成し、該配列を用いて前記補助情報を生成することを特徴とする請求項３記載のデータ処理装置。
【請求項６】
ｋ個の属性ａ［０］，ａ［１］，．．．，ａ［ｋ−１］を有するレコードをｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）とし、ｒ［ｉ］の属性ａ［ｑ］（ｑ＝｛０，１，．．．，ｋ−１｝）の値をｒ［ｉ］．ａ［ｑ］とし、定数と属性ｒ［ｉ１］．ａ［ｑ１］（ｉ１＝｛０，１，．．．，ｎ−１からｉを除いた残り｝、ｑ１＝｛０，１，．．．，ｋ−１｝）を含む任意の関数をＦとし、｛＜，≦，＝，＞，≧，≠｝のうちのいずれかのオペレータをＯＰとして、（ｒ［ｉ］．ａ［ｑ］　ＯＰ　Ｆ）のような条件式の組み合わせで記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するデータ処理装置であって、
前記パターンを入力する入力手段と、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成する前処理手段と、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定する検索手段と、
前記パターンのすべての述語を満たしたレコード列の情報を出力する出力手段と
を備えることを特徴とするデータ処理装置。
【請求項７】
複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するコンピュータのためのプログラムであって、
データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力し、
前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成し、
前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記条件列のすべての条件を満たしたデータ列の情報を出力する
処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項８】
レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するコンピュータのためのプログラムであって、
前記パターンを入力し、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成し、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記パターンのすべての述語を満たしたレコード列の情報を出力する
処理を前記コンピュータに実行させることを特徴とするプログラム。
【請求項９】
複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するデータ処理方法であって、
入力手段が、データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力し、
前処理手段が、前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成し、
検索手段が、前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
出力手段が、前記条件列のすべての条件を満たしたデータ列の情報を出力することを特徴とするデータ処理方法。
【請求項１０】
レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するデータ処理方法であって、
入力手段が、前記パターンを入力し、
前処理手段が、述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成し、
検索手段が、前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
出力手段が、前記パターンのすべての述語を満たしたレコード列の情報を出力する
ことを特徴とするデータ処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、与えられたデータから複雑な条件により指定された順序パターンを抽出するデータ処理装置および方法に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】
今日の情報化社会では、大量の順序データをモニタしなければならない多くのアプリケーションが存在する。このようなデータおよびアプリケーションとしては、例えば、センサアプリケーション、ネットワークモニタリングやトラフィック管理におけるパフォーマンス測定、医療モニタリングのためのバイタルサイン（生命徴候）および処置、電気通信における呼の詳細に関するレコード、ウェブアプリケーションにおけるログレコードやクリックストリームが挙げられる。
【０００３】
ここで、センサデータに対する問い合わせと解析を行うことで物理的な世界をモニタするアプリケーションについて考えてみる。このようなアプリケーションの１つに、工場の倉庫に格納された物品を管理するアプリケーションがある。倉庫内の物品および壁には温度センサが貼り付けられ、床や天井にも温度センサが埋め込まれている。各センサは一定周期で測定温度を出力し、倉庫管理者はそのセンサデータを用いて物品が過熱状態になっていないことを確認する。この場合、アプリケーションにとっては以下のようなデータ検索のクエリが重要となる。
【０００４】
クエリ１：３つの連続する測定温度が３５度、３６度、および３７度であるようなセンサを検出せよ。
クエリ２：３回続けて２度を越える温度上昇があり、３５度未満の温度から４０度より高い温度に達したセンサを検出せよ。
クエリ３：３８度未満の温度から４０度と５０度の間の温度に上昇し、引き続いて２回の下落を経て３８度未満の温度に戻った時間的な変化パターンを検出せよ。
【０００５】
この温度モニタリングアプリケーションにおける対象パターンは、３つの連続する測定温度を見つければよいクエリ１のような非常に単純なものから、引き続く温度上昇や、倉庫管理者が注意すべきではあるが正確には指定できない異常なスパイクを見つけるクエリ２および３のようなより複雑なものまで変化する。絶対的な単一の測定値の代わりに、可能な測定値の範囲や増減する測定値の関係が指定されることもある。
【０００６】
より具体的に言えば、クエリ１、２、および３は、データストリームの中からそれぞれ以下のような述語（ｐｒｅｄｉｃａｔｅ　）ｐ［ｉ］で表されるパターンにマッチする温度属性値を有する複数のレコードｒを見つけるものである。
【０００７】
2004046601.tif 000003
ここで、述語ｐ［ｉ］（ｒ）はパターン内のｉ番目のレコードが持つ属性値に関する条件を表し、ｒ．ｔｅｍｐｅｒａｔｕｒｅはレコードｒの温度属性値を表し、ｒ．ｐｒｅｖｉｏｕｓはデータストリームにおけるレコードｒの直前のレコードを表す。与えられるデータを左から右へ順に並べた場合、クエリ２および３のｒ．ｐｒｅｖｉｏｕｓはレコードｒの左側のレコードに対応し、そのレコードに対する条件を指定することでパターンを記述することができる。
【０００８】
クエリ１のパターン述語は常に定数を用いた等式である。したがって、Ｂｏｙｅｒ−ＭｏｏｒｅアルゴリズムやＫｎｕｔｈ−Ｍｏｒｒｉｓ−Ｐｒａｔｔアルゴリズムのような周知の文字列マッチングアルゴリズムを効率良く適用することができる。しかしながら、クエリ２およびクエリ３はより複雑であり、それらの述部は隣接レコードの属性値と定数を用いた不等式の組み合わせ（ｃｏｎｊｕｎｃｔｉｏｎ）である。文字列マッチングアルゴリズムは、クエリ１のように定数を用いた等式で表されるクエリの場合にのみ適用可能であるので、より複雑なこれらの２つのクエリには適用できない。
【０００９】
このようなクエリに適用できるマッチングアルゴリズムとしては、Ｓａｄｒｉ　ｅｔ　ａｌ．により提案されたＯＰＳ（Ｏｐｔｉｍｉｚｅｄ　Ｐａｔｔｅｒｎ　Ｓｅａｒｃｈ）アルゴリズムがある（Ｓａｄｒｉ，　Ｒ．，　Ｚａｉｏｌｏ，　Ｃ．，　Ｚａｒｋｅｓｈ，　Ａ．，　ａｎｄ　Ａｄｉｂｉ，　Ｊ．，　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　Ｓｅｑｕｅｎｃｅ　Ｑｕｅｒｉｅｓ　ｉｎ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ，　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｔｗｅｎｔｉｅｔｈ　ＡＣＭＳＩＧＭＯＤ−ＳＩＧＡＣＴ−ＳＩＧＡＲＴ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ，　ｐｐ．７１−８１，　Ｍａｙ２００１）。このアルゴリズムでは、データストリーム上に設定されたウィンドウ内で、ｒ．ｐｒｅｖｉｏｕｓを用いて記述された述語を左から右に向かって（つまり、ｐ［０］、ｐ［１］、ｐ［２］、およびｐ［３］の順に）チェックしている。そして、ある位置で述語をチェックし終えるとウィンドウを別の位置にシフトして再びチェックを行うという操作を繰り返す。
【００１０】
しかしながら、この方法では、述語とマッチしなかったレコードを後続するウィンドウ位置において何回も再チェックしなければならないことが多く、必ずしも効率的なアルゴリズムとはいえない。
【００１１】
本発明の課題は、与えられたデータから複雑なクエリにより指定された順序パターンを効率良く抽出するデータ処理装置および方法を提供することである。
【００１２】
【課題を解決するための手段】
図１は、本発明の第１および第２のデータ処理装置の構成図である。図１のデータ処理装置は、入力手段１１、前処理手段１２、検索手段１３、および出力手段１４を備える。
【００１３】
本発明の第１のデータ処理装置は、複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出する。入力手段１１は、データ間の関係を用いてｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力する。前処理手段１２は、ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成する。検索手段１３は、順序付けられたデータ上で先頭のデータから末尾のデータに向かってデータ列を検索するとき、データが条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき上記補助情報を用いて次のチェック開始位置を決定する。そして、出力手段１４は、条件列のすべての条件を満たしたデータ列の情報を出力する。
【００１４】
入力手段１１により入力される条件列の各条件は、順序付けられたデータのうち任意の２つのデータ間の関係（値の大小関係等）を用いて記述され、ユーザは任意の関係を用いて複雑な順序パターンを指定することができる。この条件は、例えば、レコード間の関係を記述する述語に対応する。
【００１５】
前処理手段１２はあらかじめ複数の条件の間の両立性を解析することで補助情報を生成し、検索手段１３は、この補助情報を用いて次のチェック開始位置を決定することで、指定されたパターンとデータの間の不要なチェックをスキップしながら、パターンにマッチするデータ列を検索する。
【００１６】
多くの場合、データ上の検索方向と条件チェックの向きを逆向きにすることで、これらを同じ向きにした場合よりもチェック回数が削減されることが、シミュレーションにより確認された。このシミュレーションの結果については後述することにする。
【００１７】
本発明の第２のデータ処理装置は、レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出する。入力手段１１は、パターンを入力し、前処理手段１２は、述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析して、パターン抽出に用いる補助情報を生成する。検索手段１３は、順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かってパターンに対応するレコード列を検索するとき、レコードがパターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき上記補助情報を用いて次のチェック開始位置を決定する。そして、出力手段１４は、パターンのすべての述語を満たしたレコード列の情報を出力する。
【００１８】
入力手段１１により入力されるパターン内の各述語はレコードの属性値を含む条件式で記述され、ユーザは任意の条件式を用いて複雑な順序パターンを指定することができる。
【００１９】
前処理手段１２はあらかじめ複数の述語の間の両立性を解析することで補助情報を生成し、検索手段１３は、この補助情報を用いて次のチェック開始位置を決定することで、指定されたパターンとレコードの間の不要なチェックをスキップしながら、パターンにマッチするレコード列を検索する。
【００２０】
第１のデータ処理装置と同様に、順序データ上の検索方向と述語チェックの向きが逆向きになっているため、これらを同じ向きにした場合よりも効率の良い検索処理が可能となる。
【００２１】
図１の入力手段１１は、例えば、後述する図１４の入力装置８３に対応し、前処理手段１２および検索手段１３は、例えば、図１４のＣＰＵ（中央処理装置）８１およびメモリ８２の組み合わせに対応し、出力手段１４は、例えば、図１４の出力装置８４に対応する。
【００２２】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態のデータ処理装置は、例えば、コンピュータを用いて構成され、連続的かつ無限に入力されるデータストリームや有限の格納データの形式で与えられるデータから、複雑な時間的変化のパターンを検出する。
【００２３】
データ処理装置は、まず、ストリームデータに対するパターン述語の不要なチェックをスキップするために、コンパイル時に複雑なパターンの前処理を行って補助情報を生成しておく。そして、実行時にウィンドウを左から右に（ストリームの先頭から末尾に向かって）スライドさせながら、その補助情報を用いて効率良くストリーム検索を行う。このとき、ウィンドウ内のデータについては、右から左に向かってパターンの述語を満たすか否かをチェックする。
【００２４】
この方法では、クエリのコンパイル処理の一部としてパターンの述語間における論理的関係（補助情報）を抽出することで、ストリームとパターン述語の部分的マッチが得られたときにウィンドウをどのようにシフトすればうまくいくかが推測される。このようなチェック方法を用いることで、ウィンドウシフトの長さを改良し、同じデータの再チェックの回数を最小化することができる。
【００２５】
ウィンドウ内で述語を右から左に向かってチェックする場合、ｒ．ｐｒｅｖｉｏｕｓの情報を利用することができないので、クエリを別の形式に書き換える必要が生じる。上述したクエリ２および３のパターン述語は、例えば、以下のように書き換えられる。
【００２６】
2004046601.tif 000004
ｒ．ｎｅｘｔはデータストリームにおけるレコードｒの直後のレコード（レコードｒの右側のレコード）を表し、そのレコードに対する条件を指定することでパターンを記述することができる。ｒ．ｎｅｘｔを用いて書き換えられたパターンを用いれば、述語を右から左に向かって（つまり、ｐ［３］、ｐ［２］、ｐ［１］、およびｐ［０］の順に）チェックすることが可能となる。
【００２７】
以下では、クエリ３を例に用いてその処理を説明する。データストリームとしては、簡単のため、温度属性値がそれぞれ３６、４２、４７、３６、３７、４２、４０、および３７である８個のレコードを用いることにする。
【００２８】
図２に示すように、最初のウィンドウ２１の処理では、３６＜３８であることから値３６がｐ［３］（ｒ）：ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜３８を満たし、４７＞３６であることから値４７がｐ［２］（ｒ）：ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅを満たす。しかし、次の値４２はｐ［１］（ｒ）：４０＜ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜５０　ＡＮＤ　ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅを満たさない。なぜなら、４０＜４２＜５０ではあっても、４２＜４７であり４２＞４７ではないからである。
【００２９】
こうして、ｐ［３］およびｐ［２］がデータとマッチした後、最初のミスマッチがｐ［１］で発生し、パターン述語とストリームデータのチェックを再開するためにウィンドウ２１をシフトする必要が生じる。ここで、値３６および４７がそれぞれｐ［３］およびｐ［２］を満たすことが分かっており、値４２がｐ［１］を満たさないことが分かっている。
【００３０】
パターン述語を解析することにより、ｐ［３］とｐ［２］は互いに矛盾しないことが分かり、ｐ［３］を満たす値はｐ［２］も満たす可能性があるといえる。また、ｐ［２］を満たす値はｐ［１］も満たす可能性があり、ｐ［１］を満たさない値はｐ［０］を満たす可能性がある。そこで、ウィンドウ２１を１レコード分シフトして、新たなウィンドウ２２内で値３６、３７、および４２がそれぞれｐ［２］、ｐ［１］、およびｐ［０］と並ぶようにする。
【００３１】
この２番目のウィンドウ２２の処理では、３７＜３８であることから値３７はｐ［３］を満たすが、３６＜３７であり３６＞３７ではないことから値３６はｐ［２］を満たさないことが分かる。ミスマッチがｐ［２］で発生したため、チェックを再開するためにウィンドウ２２をいくらかシフトする必要が生じる。
【００３２】
上述したようにｐ［３］を満たす値はｐ［２］も満たす可能性があるが、ｐ［２］（ｒ）：ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅを満たさない値はｐ［１］（ｒ）：４０＜ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜５０　ＡＮＤ　ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅも満たさない。既に値３６はｐ［２］を満たさず、したがってｐ［１］も満たさないことが分かっているわけであるから、ウィンドウ２２を１レコード分シフトして値３６をｐ［１］と並ぶようにしても成果が得られないのは明らかである。
【００３３】
また、ウィンドウ２２を２レコード分シフトした場合、ｐ［３］（ｒ）：ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜３８を満たした値がｐ［１］（ｒ）：４０＜ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜５０　ＡＮＤ　ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅも満たさなければならないことになるが、ｐ［３］とｐ［１］は互いに矛盾するのでこれは不可能である。したがって、２レコードのシフト操作も破棄される。
【００３４】
次に、ｐ［３］を満たした値がｐ［０］も満たす可能性があれば、３レコードのシフト操作が考慮されることになるが、これは可能である。そこで、図２に示されるようにウィンドウ２２を３レコード分シフトし、３番目のウィンドウ２３の処理において、値３７、４０、４２、および３７がそれぞれｐ［３］、ｐ［２］、ｐ［１］、およびｐ［０］を満たすことが確認される。
【００３５】
この例では、パターン述語の間の関係に関する知識を用いることにより、与えられたパターンを３回のウィンドウ処理で検出できた。ストリームデータに対する述語のチェック回数は９回であった。
【００３６】
上述した基本処理においては温度属性値が連結述語（ｃｏｎｊｕｎｃｔｉｖｅ　ｐｒｅｄｉｃａｔｅ　）の不等式を満たすかどうかがチェックされているが、各不等式を別々に扱う拡張処理を導入することでチェック回数を削減することも可能である。この例では、次のレコードの値を用いた不等式と定数を用いた不等式を別々に扱うことにする。前者は２つのレコード間における属性値の相関関係（変化の形状）を表すので、“関係述語（ｒｅｌａｔｉｏｎｐｒｅｄｉｃａｔｅ）”と呼ぶことにし、後者は属性値の範囲を表すので、“範囲述語（ｒａｎｇｅ　ｐｒｅｄｉｃａｔｅ　）”と呼ぶことにする。
【００３７】
最初のウィンドウ２１の処理では、前述したように、値４２がｐ［１］（ｒ）：４０＜ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜５０　ＡＮＤ　ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅを満たさない。しかし、より詳細に見れば、この述語は範囲述語（４０＜ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜５０）と関係述語（ｒ．ｔｅｍｐｅｒａｔｕｒｅ＞ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅ）の論理積で表されており、値４２は範囲述語を満たしており（４０＜４２＜５０）、関係述語を満たしていない（４２＜４７であり４２＞４７ではない）ことが分かる。
【００３８】
このように値４２はｐ［１］の範囲述語を満たしているのであるから、ｐ［０］（ｒ）：ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜３８　ＡＮＤ　ｒ．ｔｅｍｐｅｒａｔｕｒｅ＜ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅを満たし得ない。したがって、連結述語ｐ［１］を分離しない基本処理で用いた１レコードのシフトより大きなウィンドウシフトが可能であることが分かる。また、ｐ［２］とｐ［０］は互いに矛盾しないので、図３に示すように、ウィンドウ２１を３レコード分シフトすることが決定される。
【００３９】
２番目のウィンドウ３１の処理では、４０＞３８であり４０＜３８ではないことから値４０はｐ［３］を満たさないことが分かり、ウィンドウ３１が１レコード分シフトされる。そして、３番目のウィンドウ３２の処理において、４つの値がそれぞれ対応する述語を満たすことが確認される。この例では、述語の不等式を別々に解析することでチェック回数が８回に削減された。
【００４０】
図２および図３の処理では、ストリームとパターン述語が部分的にマッチしたときにマッチングが成功する可能性のあるパターンシフトを、述語の間の相互依存性を活用して推測している。これにより、ウィンドウ内の述語とストリームデータの比較回数が削減され、結果的に検索速度が向上する。
【００４１】
この例では、理解を容易にするため、ミスマッチが発生した場合の処理の一部としてウィンドウのスライド長を推論することを示した。しかしながら、述語の間の相互依存性はストリームデータとは無関係であるため、クエリコンパイル時にあらかじめ計算することが可能である。
【００４２】
以下では、パターン述語の間の論理的関係を活用することでクエリコンパイルの一部として一旦補助情報を生成しておき、ストリームデータからパターンを検索する際に補助情報を繰り返し用いてウィンドウを効率良くスライドさせる方法について、詳細に説明する。まず、いくつかの必要な用語の意味をまとめておく。
【００４３】
データストリーム：ストリームはｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］の列であり、各ｒ［ｉ］はセンサＩＤ、温度センサが生成する温度、その生成時刻等のようなｋ個の属性ａ［０］，ａ［１］，．．．，ａ［ｋ−１］を持つ。
【００４４】
パターンと述語：パターンはｍ個の述語ｐ［０］（ｒ），．．．，ｐ［ｍ−１］（ｒ）の列であり、各ｐ［ｊ］（ｒ）（ｊ＝｛０，１，．．．，ｍ−１｝）は、ストリームレコードｒの属性と定数の間の条件式（不等式や等式）や、レコードｒの属性とデータストリーム中の他のレコードの属性の間の条件式を含んでいる。
【００４５】
この条件式は一般に（ｒ［ｉ］．ａ［ｑ］　ＯＰ　Ｆ）の形式で記述される。ｒ［ｉ］．ａ［ｑ］はｉ番目（ｉ＝｛０，１，．．．，ｎ−１｝）のレコードのｑ番目（ｑ＝｛０，１，．．．，ｋ−１｝）の属性の値を表し、Ｆは定数と複数の属性ｒ［ｉ１］．ａ［ｑ１］を含む任意の関数を表す。ただし、ｉ１＝｛０，１，．．．，ｎ−１　ｅｘｃｅｐｔ　ｉ｝、ｑ１＝｛０，１，．．．，ｋ−１｝であり、ｉ１は０，１，．．．，ｎ−１からｉを除いた残りの数字のいずれかを表す。また、ＯＰは任意のオペレータ（ＯＰ∈｛＜，≦，＝，＞，≧，≠｝）である。
【００４６】
例えば、レコードｒの温度属性をｒ．ｔｅｍｐｅｒａｔｕｒｅとし、隣接するレコードであるｒ．ｎｅｘｔの温度属性をｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅとし、実定数をＣとすると、以下のような条件式を指定することができる。
【００４７】
（ｒ．ｔｅｍｐｅｒａｔｕｒｅ　ＯＰ　Ｃ）
（ｒ．ｔｅｍｐｅｒａｔｕｒｅ　ＯＰ　ｒ．ｎｅｘｔ．ｔｅｍｐｅｒａｔｕｒｅ＋Ｃ）
連結述語は、論理積ＡＮＤで接続された複数の条件式からなる。
【００４８】
パターン述語の間の関係：パターン述語間におけるすべての論理的関係は、正の前提条件論理行列θおよび負の前提条件論理行列φを用いて表される。これらの行列のサイズはパターン述語の数ｍに一致し、その要素θ［ｊ，ｋ］およびφ［ｊ，ｋ］は以下のように定義される。
【００４９】
【数１】
2004046601.tif 000005
【００５０】
ここで、　外１　（以下ではｐ［ｊ］バーと記す）はｐ［ｊ］の否定を表し、
【００５１】
【外１】
2004046601.tif 000006
【００５２】
Ｕはｐ［ｊ］⇒ｐ［ｋ］なのかｐ［ｊ］⇒ｐ［ｋ］バーなのかが不明であることを表す。
本実施形態のパターン検出方法では、パターン述語の数ｍに等しいサイズのウィンドウを利用してストリームをスキャンする。図４に示すように、ウィンドウ４１がレコードｒ［ｉ］，．．．，ｒ［ｉ＋ｍ−１］をカバーしているとき、ウィンドウ４１の位置をｉで表すことにする。
【００５３】
ウィンドウ４１内のストリームレコードはパターン述語に対して右から左にチェックされるので、述語ｐ［ｍ−１］がレコードｒ［ｉ＋ｍ−１］に対して成り立てば、次にレコードｒ［ｉ＋ｍ−２］が述語ｐ［ｍ−２］に対してチェックされる。そして、述語ｐ［ｍ−２］がレコードｒ［ｉ＋ｍ−２］に対して成り立てば、次にレコードｒ［ｉ＋ｍ−３］が述語ｐ［ｍ−３］に対してチェックされ、同様の処理が続けられる。
【００５４】
述語ｐ［ｊ］がレコードｒ［ｉ＋ｊ］に対して成り立たないことが分かると、現在のウィンドウのマッチング処理は失敗する。そこで、現在のウィンドウ４１がｓｈｉｆｔ［ｊ］で表される長さだけ右にシフトされ、ｉ＋ｓｈｉｆｔ［ｊ］の位置のウィンドウ４２内のストリームレコードが前のウィンドウ４１の処理と同様にしてチェックされる。ｓｈｉｆｔ［ｊ］は、あらかじめ補助情報として計算しておく。
【００５５】
この方法では、ｍ個のパターン述語の列を満足するようなすべてのストリームレコードを検索するために、まず、ウィンドウの位置をｉ＝０に初期化する。これにより、ウィンドウの左端が最初のストリームレコードｒ［０］に並ぶことになる。ウィンドウをスライドさせる処理は、ウィンドウの右端が最初のデータストリームの右端を越えるまで繰り返される。このようなパターン検出アルゴリズムは、例えば、以下のように記述できる。
【００５６】
2004046601.tif 000007
ここで、ｐ［ｊ］（ｒ［ｉ］）は、ｐ［ｊ］がストリームのｉ番目のレコードｒ［ｉ］に対して成り立つか否かをテストすることを表している。ｒ［ｉ］がｐ［ｊ］を満足すればｐ［ｊ］（ｒ［ｉ］）＝１となり、満足しなければｐ［ｊ］（ｒ［ｉ］）＝０となる。
【００５７】
ｊ＜０となるのは位置ｉのウィンドウで検索パターンが得られたときであり、このときｆｉｎｄ（ｉ）は、パターン述語の全体ｐ［０］，．．．，ｐ［ｍ−１］を満足するストリームレコードｒ［ｉ］，．．．，ｒ［ｉ＋ｍ−１］を出力する。シフト配列ｓｈｉｆｔ［ｊ］に格納される距離値の計算方法については、後述することにする。
【００５８】
ｓｈｉｆｔ［ｊ］＝１とおいてウィンドウを毎回１位置だけスライドさせると、どの述語ｐ［ｊ］が成り立たない場合でも（どこでパターン全体のマッチが得られようとも）、ｍ個のパターン述語の列を満足するようなすべてのストリームレコードを検出するには、レコードの総数をｎとしてＯ（ｎｍ）の時間が必要である。
【００５９】
そこで、この大きなチェック回数を削減するために、ウィンドウを１位置より大きくスライドさせることを考える。言い換えれば、述語ｐ［ｊ］でミスマッチが起こったとき、いかなるマッチング候補をも漏らすことなく可能な限り大きくウィンドウをスライドさせるように、ｓｈｉｆｔ［ｊ］を決定する。
【００６０】
図４より、位置ｉのウィンドウにおいて述語ｐ［ｊ］でミスマッチが起こったとき、検索パターンの述語ｐ［ｊ＋１］からｐ［ｍ−１］まではそれぞれストリームレコードｒ［ｉ＋ｊ＋１］からｒ［ｉ＋ｍ−１］までに対して成り立っていることが分かる。このとき、述語ｐ［ｊ］はストリームレコードｒ［ｉ＋ｊ］に対して成り立っていない。
【００６１】
位置ｉのウィンドウをｋ位置だけ右にシフトして新たな位置（ｉ＋ｋ）にスライドさせたとき、前のウィンドウで述語ｐ［ｊ］，．．．，ｐ［ｍ−１］によりチェックされたストリームレコードｒ［ｉ＋ｊ］，．．．，ｒ［ｉ＋ｍ−１］と新たなウィンドウとのオーバラップの状況として、全体オーバラップ、部分オーバラップ、およびオーバラップなしの３つの場合が考えられる。
【００６２】
図５は、全体オーバラップの場合を示している。０＜ｋ≦ｊの場合、ウィンドウ５１は、述語ｐ［ｊ］とのミスマッチが発生したレコードｒ［ｉ＋ｊ］の左側の位置（ｉ＋ｋ）またはレコードｒ［ｉ＋ｊ］と丁度同じ位置にシフトする。したがって、新たなウィンドウ５１は前のウィンドウ４１で既にチェックしたレコードｒ［ｉ＋ｊ］，．．．，ｒ［ｉ＋ｍ−１］の列全体を含むことになる。
【００６３】
位置（ｉ＋ｋ）のウィンドウ５１では、レコードｒ［ｉ＋ｊ］，．．．，ｒ［ｉ＋ｍ−１］が述語ｐ［ｊ−ｋ］，．．．，ｐ［ｍ−ｋ−１］と並んでいる。これらの述語が対応するレコードに対して成り立つ可能性があるか否かを予測するために、前のウィンドウ４１における述語ｐ［ｊ］，．．．，ｐ［ｍ−１］のこれらのレコードに対するチェック結果を利用することができる。
【００６４】
そこで、ウィンドウ４１においてレコードｒ［ｉ＋ｊ］，．．．，ｒ［ｉ＋ｍ−１］と並んでいた述語の部分列ｐ［ｊ］，．．．，ｐ［ｍ−１］と、ウィンドウ５１においてそれらのレコードと並んでいる述語の部分列ｐ［ｊ−ｋ］，．．．，ｐ［ｍ−ｋ−１］の２つの部分列の論理的関係を解析することにより、パターン検索が成功する可能性のあるｋ位置のシフトを計算する。これらの述語列の間で次の関係が成り立てば、ｋ位置のシフトはパターン検索を満たすストリームレコードを含むようなウィンドウを生成する可能性がある。
【００６５】
2004046601.tif 000008
前述したθとφを用いると、この関係は以下のように記述することができる。まず、次式によりα［ｊ，ｋ］を定義する。
【００６６】
2004046601.tif 000009
ただし、Ｕ∧１＝Ｕ、Ｕ∧０＝０、およびＵ∧Ｕ＝Ｕである。α［ｊ，ｋ］＝０であれば、ｋ位置のウィンドウシフトは検索パターンにマッチするストリームレコードを含むことはなく、α［ｊ，ｋ］＝１であればマッチするレコードを含み、α［ｊ，ｋ］＝Ｕであればマッチするレコードを含む可能性がある。
【００６７】
次に、図６は、部分オーバラップの場合を示している。ｊ＜ｋ＜ｍの場合、ウィンドウ４１は、述語ｐ［ｊ］とのミスマッチが発生したレコードｒ［ｉ＋ｊ］の右側の位置（ｉ＋ｋ）にシフトする。したがって、新たなウィンドウ６１は前のウィンドウ４１で既にチェックしたレコードの部分列ｒ［ｉ＋ｋ］，．．．，ｒ［ｉ＋ｍ−１］を含むことになる。
【００６８】
位置（ｉ＋ｋ）のウィンドウ６１では、レコードｒ［ｉ＋ｋ］，．．．，ｒ［ｉ＋ｍ−１］が述語ｐ［０］，．．．，ｐ［ｍ−ｋ−１］と並んでいる。これらの述語が対応するレコードに対して成り立つ可能性があるか否かを予測するために、前のウィンドウ４１における述語ｐ［ｋ］，．．．，ｐ［ｍ−１］のこれらのレコードに対するチェック結果を利用することができる。
【００６９】
そこで、ウィンドウ４１においてレコードｒ［ｉ＋ｋ］，．．．，ｒ［ｉ＋ｍ−１］と並んでいた述語の部分列ｐ［ｋ］，．．．，ｐ［ｍ−１］と、ウィンドウ６１においてそれらのレコードと並んでいる述語の部分列ｐ［０］，．．．，ｐ［ｍ−ｋ−１］の２つの部分列の論理的関係を解析することにより、パターン検索が成功する可能性のあるｋ位置のシフトを計算する。これらの述語列の間で次の関係が成り立てば、ｋ位置のシフトはパターン検索を満たすストリームレコードを含むようなウィンドウを生成する可能性がある。
【００７０】
2004046601.tif 000010
ここで、θとφを用いて次式によりβ［ｊ，ｋ］を定義する。
【００７１】
2004046601.tif 000011
β［ｊ，ｋ］＝０であれば、ｋ位置のウィンドウシフトは検索パターンにマッチするストリームレコードを含むことはなく、β［ｊ，ｋ］＝１であればマッチするレコードを含み、β［ｊ，ｋ］＝Ｕであればマッチするレコードを含む可能性がある。
【００７２】
次に、図７は、オーバラップなしの場合を示している。ｋ≧ｍの場合、ウィンドウ４１は、その右端のレコードｒ［ｉ＋ｍ−１］の右側の位置（ｉ＋ｋ）にシフトする。特にｋ＝ｍの場合、新たなウィンドウ７１内の最初のレコード位置は、前のウィンドウ４１の直後のレコード位置に一致する。したがって、新たなウィンドウ７１は前のウィンドウ４１で既にチェックしたレコードｒ［ｉ＋ｊ］，．．．，ｒ［ｉ＋ｍ−１］のいずれも含んでいない。
【００７３】
新たなウィンドウ７１内のストリームレコードのいずれもまだチェックされていないわけであるから、それらが検索パターンにマッチするストリームレコードの候補であることを否定する根拠はない。
【００７４】
以上の３つの場合に関する考察から、ｋ位置のウィンドウシフトは、以下のいずれかの条件が成り立つときに、パターン述語を満たすストリームレコードを含む位置にウィンドウをスライドさせる可能性があることが分かる。
（ａ）α［ｊ，ｋ］≠０　ｆｏｒ　０＜ｋ≦ｊ
（ｂ）β［ｊ，ｋ］≠０　ｆｏｒ　ｊ＜ｋ＜ｍ
（ｃ）ｋ≧ｍ
検索処理においてはいかなるマッチング候補も漏らしたくないので、ｓｈｉｆｔ［ｊ］をパターンにマッチする可能性のある右方向への最小スライド距離として計算することにする。
【００７５】
まず、右端にある部分列ｐ［ｊ−ｋ］，ｐ［ｊ−ｋ＋１］，．．．，ｐ［ｍ−ｋ−１］を見つけるために、α［ｊ，ｋ］≠０となる最小のｋを求める。そのようなｋが存在しなければ、次に、最長の部分列ｐ［０］，．．．，ｐ［ｍ−ｋ−１］を見つけるために、β［ｊ，ｋ］≠０となる最小のｋを求める。そのようなｋも存在しなければ、ｋ＜ｍとなるいかなるシフトも失敗することが分かる。そこで、ｓｈｉｆｔ［ｊ］＝ｍとおいて、新たなウィンドウ内の最初のレコード位置が前のウィンドウの直後のレコード位置に一致するように、ウィンドウを右方向にシフトする。このようなｓｈｉｆｔ［ｊ］の求め方をまとめると、次のようになる。
【００７６】
【数２】
2004046601.tif 000012
【００７７】
シフト配列ｓｈｉｆｔ［ｊ］に格納される距離の単純な計算方法では、すべてのｊおよびｋについてα［ｊ，ｋ］およびβ［ｊ，ｋ］を最初に計算しておく必要があり、膨大な計算量が要求される。以下では、シフト配列をＯ（ｍ）の計算量で効率良く求める簡単なプログラムコードを紹介する。
【００７８】
まず、次式で定義される補助配列ｃｏｍｐａｔｉ［ｉ］の要素を計算する。
2004046601.tif 000013
図８に示すように、位置ｉにおけるｃｏｍｐａｔｉ［ｉ］は、位置ｉを右端としパターン述語ｐ［ｉ−ｌｅｎ＋１］，．．．，ｐ［ｉ］からなるパターン部分列（述語列）であって、パターン述語ｐ［ｍ−ｌｅｎ］，．．．，ｐ［ｍ−１］からなる長さｌｅｎの右端の部分列と両立するようなパターン部分列の長さｌｅｎの最大値を表す。
【００７９】
ｃｏｍｐａｔｉ［ｉ］の値は右から左に向かって（ｉ＝ｍ−１からｉ＝０に向かって）計算される。基本的なアイデアは、あるｃｏｍｐａｔｉ［ｉ］の値を可能な限りその左側の値（より小さいｉに対する値）の計算に用いるというものである。このアイデアを、次のような４つのパターン述語からなる非常に単純なパターンの例を用いて説明する。
【００８０】
ｐ［３］：ｒ．ｌｅｖｅｌ＞１０
ｐ［２］：ｒ．ｌｅｖｅｌ＞５
ｐ［１］：ｒ．ｌｅｖｅｌ＞３
ｐ［０］：ｒ．ｌｅｖｅｌ＞１
この場合、いずれのｐ［ｉ］をとってもｐ［ｉ］⇒ｐ［ｉ］であるから、明らかにｃｏｍｐａｔｉ［３］＝４である（以下に示すコードの１行目に対応）。ｃｏｍｐａｔｉ［２］の計算では、ｐ［３］とｐ［２］、ｐ［２］とｐ［１］、およびｐ［１］とｐ［０］の間の関係をチェックしなければならない。図９に示すように、ｐ［３］⇒ｐ［２］、ｐ［２］⇒ｐ［１］、およびｐ［１］⇒ｐ［０］であるから、ｃｏｍｐａｔｉ［２］＝３となる（以下に示すコードの７−１２行目に対応）。
【００８１】
ここで、ｐ［３］⇒ｐ［２］およびｐ［２］⇒ｐ［１］であることから、ｐ［３］⇒ｐ［１］であることが分かる。さらに、ｐ［２］⇒ｐ［１］およびｐ［１］⇒ｐ［０］であることから、ｐ［２］⇒ｐ［０］であることも分かる。したがって、ｐ［３］とｐ［１］およびｐ［２］とｐ［０］の間の関係を直接チェックしなくとも、図１０に示すようなｃｏｍｐａｔｉ［１］＝２という結論を得ることができる（以下に示すコードの４−５行目に対応）。
【００８２】
このようなｃｏｍｐａｔｉ［ｉ］の値を効率良く計算する簡単なプログラムコードとしては、例えば、以下のようなものが考えられる。
2004046601.tif 000014
配列ｃｏｍｐａｔｉ［ｉ］を決定されると、次にシフト配列が計算される。以下のプログラムコードに示されるように、まずシフト配列はオーバラップなしの場合の値で満たされ、可能であれば、次にｃｏｍｐａｔｉ［ｉ］を用いて部分オーバラップの場合の値がシフト配列に格納され、最後に全体オーバラップの場合の値が格納される。
【００８３】
2004046601.tif 000015
このシフト配列の計算コードの１−２行目では、ｍがオーバラップなしの場合に対応するシフト値として入力される。前述したように、このシフト値は、パターン述語の右端の部分列と両立するような部分列が存在しない場合に用いられるので、図１１に示すように、新たなウィンドウが前のウィンドウとオーバラップするパターン述語を含まないようにウィンドウがシフトされる。
【００８４】
また、３−８行目では、部分オーバラップの場合のシフト値が設定される。この場合、図１２に示す通り、パターン述語の左端にある最長の部分列ｐ［０］，．．．，ｐ［ｉ］が右端にある部分列ｐ［ｍ−１−ｉ］，．．．，ｐ［ｍ−１］と両立するように、最小のシフト値が計算される。
【００８５】
この左端の部分列ｐ［０］，．．．，ｐ［ｉ］の最後のパターン述語はｐ［ｉ］であり、その位置ｉにおいてはｃｏｍｐａｔｉ［ｉ］＝ｉ＋１である。したがって、配列ｃｏｍｐａｔｉ［ｉ］に格納されたパターン述語の両立性（ｃｏｍｐａｔｉｂｉｌｉｔｙ　）に関する情報（ｃｏｍｐａｔｉ［ｉ］＝ｉ＋１）が与えられれば、左端の部分列ｐ［０］，．．．，ｐ［ｉ］が両立する右端の部分列ｐ［ｍ−１−ｉ］，．．．，ｐ［ｍ−１］とオーバラップするようにウィンドウがシフトされる。
【００８６】
最後に、９−１１行目では、全体オーバラップの場合のシフト値が設定される。この場合、図１３に示す通り、パターン述語の右端にある部分列ｐ［ｍ−ｃｏｍｐａｔｉ［ｉ］］，．．．，ｐ［ｍ−１］がｃｏｍｐａｔｉ［ｉ］の長さの部分列ｐ［ｉ−ｃｏｍｐａｔｉ［ｉ］＋１］，．．．，ｐ［ｉ］と両立し、かつ、ｐ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１］バーがパターン述語ｐ［ｉ−ｃｏｍｐａｔｉ［ｉ］］と両立するように、最小のシフト値が計算される。
【００８７】
既にｃｏｍｐａｔｉ［ｉ］の計算時にチェックした通り、ｐ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１］⇒ｐ［ｉ−ｃｏｍｐａｔｉ［ｉ］］バー（θ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１，ｉ−ｃｏｍｐａｔｉ［ｉ］］＝０）が成り立つことが分かっている。さらに、ｐ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１］バー⇒ｐ［ｉ−ｃｏｍｐａｔｉ［ｉ］］（φ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１，ｉ−ｃｏｍｐａｔｉ［ｉ］］≠０）が成り立てば、上述した２つの条件が満たされる。したがって、ｓｈｉｆｔ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１］＝ｍ−１−ｉとおくことができる。
【００８８】
同じｃｏｍｐａｔｉ［ｉ］の値を持つ複数のｉが存在する場合、検索処理においていかなるマッチング候補も漏らすことがないように最小のシフト値を求めるという要請から、最後には最も右のｉ（最大のｉ）がシフト配列にｓｈｉｆｔ［ｍ−ｃｏｍｐａｔｉ［ｉ］−１］＝ｍ−１−ｉとして入力されることになる。したがって、配列ｃｏｍｐａｔｉ［ｉ］は左から右に向かって（ｉ＝０からｉ＝ｍ−２に向かって）スキャンされる。
【００８９】
ところで、上述した基本処理におけるｓｈｉｆｔ［ｊ］の計算方法では、パターン述語の間の両立性の解析において連結述語の複数の不等式を分離して考慮してはいない。これらを分離して扱えば、前述したように、より大きなシフトが得られる可能性がある。
【００９０】
そこで、拡張処理においては、連結述語ｐ［ｊ］を、定数を用いた条件式を含む“範囲述語ｐ１［ｊ］”と隣接レコードの値を用いた条件式を含む“関係述語ｐ２［ｊ］”の組み合わせで表し、ｐ［ｊ］＝ｐ１［ｊ］∧ｐ２［ｊ］と記述することにする。この場合にも、基本処理の計算方法を素直に拡張することでｓｈｉｆｔ［ｊ］を求めることができる。基本処理との主な違いは以下の通りである。
【００９１】
基本処理ではｐ［ｊ］バーのみを考慮しているが、拡張処理ではｐ１［ｊ］バー∧ｐ２［ｊ］、ｐ１［ｊ］∧ｐ２［ｊ］バー、およびｐ１［ｊ］バー∧ｐ２［ｊ］バーの３つの場合を考慮する。これらの３つの場合に応じて、上述のφ［ｊ，ｊ−ｋ］がそれぞれφ１［ｊ，ｊ−ｋ］、φ２［ｊ，ｊ−ｋ］、およびφ１２［ｊ，ｊ−ｋ］に分解され、α［ｊ，ｊ−ｋ］がそれぞれα１［ｊ，ｊ−ｋ］、α２［ｊ，ｊ−ｋ］、およびα１２［ｊ，ｊ−ｋ］に分解される。
【００９２】
したがって、ｓｈｉｆｔ［ｊ］もあらかじめｓｈｉｆｔ１［ｊ］、ｓｈｉｆｔ２［ｊ］、およびｓｈｉｆｔ１２［ｊ］に分けて計算される。そして、述語ｐ［ｊ］でミスマッチが起こったとき、ミスマッチを起こした述語が範囲述語のみか、関係述語のみか、あるいはその両方かに応じて、３つのシフト値ｓｈｉｆｔ１［ｊ］、ｓｈｉｆｔ２［ｊ］、およびｓｈｉｆｔ１２［ｊ］の中からウィンドウのスライド距離が選択される。
【００９３】
ところで、本実施形態のデータ処理装置は、例えば、図１４に示すような情報処理装置（コンピュータ）を用いて構成される。図１４の情報処理装置は、ＣＰＵ（中央処理装置）８１、メモリ８２、入力装置８３、出力装置８４、外部記憶装置８５、媒体駆動装置８６、およびネットワーク接続装置８７を備え、それらはバス８８により互いに接続されている。
【００９４】
メモリ８２は、例えば、ＲＯＭ（ｒｅａｄ　ｏｎｌｙ　ｍｅｍｏｒｙ）、ＲＡＭ（ｒａｎｄｏｍ　ａｃｃｅｓｓ　ｍｅｍｏｒｙ）等を含み、処理に用いられるプログラムとデータを格納する。ＣＰＵ８１は、メモリ８２を利用してプログラムを実行することにより、必要な処理を行う。
【００９５】
入力装置８３は、例えば、キーボード、ポインティングデバイス、タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力装置８４は、例えば、ディスプレイ装置、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【００９６】
外部記憶装置８５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。情報処理装置は、この外部記憶装置８５に、上述のプログラムとデータを保存しておき、必要に応じて、それらをメモリ８２にロードして使用する。
【００９７】
媒体駆動装置８６は、可搬記録媒体８９を駆動し、その記録内容にアクセスする。可搬記録媒体８９としては、メモリカード、フレキシブルディスク、ＣＤ−ＲＯＭ（ｃｏｍｐａｃｔ　ｄｉｓｋ　ｒｅａｄ　ｏｎｌｙ　ｍｅｍｏｒｙ　）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。ユーザは、この可搬記録媒体８９に上述のプログラムとデータを格納しておき、必要に応じて、それらをメモリ８２にロードして使用する。
【００９８】
ネットワーク接続装置８７は、ＬＡＮ（ｌｏｃａｌ　ａｒｅａ　ｎｅｔｗｏｒｋ）等の任意の通信ネットワークに接続され、通信に伴うデータ変換を行う。情報処理装置は、上述のプログラムとデータをネットワーク接続装置８７を介して他の装置から受け取り、必要に応じて、それらをメモリ８２にロードして使用する。
【００９９】
図１５は、図１４の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。可搬記録媒体８９やサーバ９０のデータベース８１に保存されたプログラムとデータは、メモリ８２にロードされる。このとき、サーバ９０は、プログラムとデータを搬送する搬送信号を生成し、ネットワーク上の任意の伝送媒体を介して情報処理装置に送信する。そして、ＣＰＵ８１は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【０１００】
次に、ウィンドウを常に１レコードずつシフトするナイーブアプローチと、前述したＯＰＳアルゴリズムによる検索処理と、本発明の検索処理とを比較したシミュレーションの結果について説明する。クエリおよびストリームデータとしては以下のようなものを用いた。
【０１０１】
クエリ
“ある企業の株価が２回続けて下落した後２回続けて上昇し、下落により株価は４０と５０の間の値となり、最初の上昇では株価は５２を越えないようなパターンをすべて抽出せよ。”
ストリームデータ
５５　５０　４５　５１　５４　５０　４７　４９　４５　４２　５５　５７
５９　６０　５７
図１６から図１９までは、このようなクエリとストリームデータを用いてパターン検索を行ったときの、ストリームデータ上の位置ｉと検索パターン上の位置ｊの値の変化を表している。このうち、図１６はナイーブアプローチによる結果を表し、図１７はＯＰＳアルゴリズムによる結果を表し、図１８は本発明の基本処理（連結述語の条件式を分離して扱わない処理）による結果を表し、図１９は本発明の拡張処理（連結述語の条件式を分離して扱う処理）による結果を表す。また、グラフ上の四角のマークは、ストリームレコードに対してパターン述語のチェックが行われた点を示している。
【０１０２】
図１６のナイーブアプローチでは、ｗ１〜ｗ９の９つのウィンドウの処理が行われ、ストリームレコードに対するパターン述語のチェックは２０回行われている。また、図１７のＯＰＳアルゴリズムでは、ｗ１〜ｗ７の７つのウィンドウの処理と１６回のチェックで検索が終了している。
【０１０３】
これに対して、図１８の基本処理では、ｗ１〜ｗ８の８つのウィンドウの処理と１１回のチェックで検索が終了しており、図１９の拡張処理では、ｗ１〜ｗ７の７つのウィンドウの処理と１０回のチェックで検索が終了している。したがって、この例では拡張処理が最も性能が良いことが分かる。
【０１０４】
ナイーブアプローチでは、処理の進行に伴って連続する点の間でｉの値が減少するバックトラックが発生しているが、ＯＰＳアルゴリズムでは、このようなバックトラックは発生していない。しかしながら、ＯＰＳアルゴリズムでは、同じｉの値を持つ連続する点において、ミスマッチしたレコードが引き続き何度も再チェックされている。
【０１０５】
これに対して、本発明の基本処理では、ウィンドウ処理の数はＯＰＳアルゴリズムのそれより小さくないが、レコードの再チェックはミスマッチが発生しなかった（つまり、パターンが完全に検出された）最後のウィンドウｗ８のみで行われている。さらに、関係述語と範囲述語を分離して解析する拡張処理では、最初のウィンドウｗ１内のレコードｒ［３］（ｉ＝３）でミスマッチが発生した後、基本処理より大きくウィンドウがシフトされ、レコードｒ［４］（ｉ＝４）のチェックがスキップされている。
【０１０６】
このように、本発明の検索処理は、ナイーブアプローチおよびＯＰＳアルゴリズムと比較して効率の良いアルゴリズムであることが分かる。
次に、他のクエリを用いたシミュレーションの結果について説明する。以下に示すＰ１〜Ｐ１０の１０個のパターンはいずれも７つの述語で記述され、これらの述語を用いてそれぞれの条件を満たす水位（および温度）属性を有する連続レコードを検索した。ストリームデータとしては、センサによる水位および温度の測定値を有するレコードとしてランダムに生成された１００，０００個のレコードを用いた。
【０１０７】
Ｐ１：連続する７回の測定において、水位は隣接する測定値に対して−２と＋２の間の範囲にある。
Ｐ２：連続する７回の測定において、水位は上昇し続ける。
Ｐ３：連続する７回の測定において、水位は低下し続ける。
Ｐ４：連続する７回の測定の前半において水位は上昇し続け、後半において安定するかまたは低下し続ける。
Ｐ５：３回連続して水位のスパイクが発生する。つまり、水位が突然１０より大きく上昇した後突然１０より大きく低下する現象が３回繰り返される。
Ｐ６：連続する７回の測定において、水位は隣接する測定値に対して−２と＋２の間の範囲にあり、温度は上昇し続ける。
Ｐ７：連続する７回の測定において、水位は上昇し続け、温度は低下し続ける。
Ｐ８：連続する７回の測定において、水位は隣接する測定値に対して−２と＋２の間の範囲にあり、温度は前半において上昇し続け、後半において安定するかまたは低下し続ける。
Ｐ９：連続する７回の測定において、水位は隣接する測定値に対して−２と＋２の間の範囲にあり、３回連続して温度のスパイクが発生する。つまり、温度が突然１０より大きく上昇した後突然１０より大きく低下する現象が３回繰り返される。
Ｐ１０：連続する７回の測定において、水位は上昇し続け、３回連続して温度のスパイクが発生する。
【０１０８】
図２０は、ナイーブアプローチ（Ｎａｉｖｅ）、ＯＰＳアルゴリズム、本発明の基本処理（Ｒ２Ｌ）、拡張ＯＰＳアルゴリズム（ＯＰＳ−ｅｘｔｅｎｄｅｄ）、および本発明の拡張処理（Ｒ２Ｌ−ｅｘｔｅｎｄｅｄ）の各処理において述語のチェックが行われた回数を示している。
【０１０９】
拡張ＯＰＳアルゴリズムとは、ＯＰＳアルゴリズムにおいて、本発明の拡張処理と同様に連結述語の条件式を分離して扱うアルゴリズムを指す。パターンＰ１〜Ｐ５では各述語が１つの条件式しか含まないため、拡張ＯＰＳアルゴリズムおよび本発明の拡張処理のシミュレーションは行われていない。
【０１１０】
図２１は、図２０のシミュレーション結果（チェック回数）の棒グラフを示しており、１０１、１０２、１０３、１０４、および１０５は、それぞれナイーブアプローチ、ＯＰＳ、本発明の基本処理、拡張ＯＰＳ、および本発明の拡張処理のチェック回数に対応する。
【０１１１】
このグラフから、ＯＰＳ、拡張ＯＰＳ、本発明の基本処理、および本発明の拡張処理は、どのパターンに対してもナイーブアプローチよりチェック回数が少ないことが分かる。ＯＰＳと拡張ＯＰＳのチェック回数は、レコードの総数（１００，０００）と同じかそれよりわずかに多い程度であり、これらの処理では大部分のパターンに対してバックトラックが発生していないことを意味している。
【０１１２】
また、パターンＰ４およびＰ９に対するＯＰＳの場合を除いて、本発明の基本処理と拡張処理のチェック回数は、それぞれＯＰＳと拡張ＯＰＳのそれより少ない。特にパターンＰ１、Ｐ２、Ｐ３、Ｐ６、およびＰ７に対しては、本発明の基本処理と拡張処理のチェック回数は、それぞれＯＰＳと拡張ＯＰＳのそれの半分以下である。パターンＰ８、Ｐ９、およびＰ１０に対しては、基本処理の代わりに拡張処理を用いることでチェック回数を大幅に削減することができる。
【０１１３】
上述したように、ランダムに生成された大量のデータから１０個の異なるパターンをそれぞれ検索するシミュレーションにより、多くの場合、本発明の検索処理がナイーブアプローチやＯＰＳアルゴリズムより格段に優れた性能を示し、拡張処理は基本処理よりさらに効率が良いことが分かった。
（付記１）　複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するデータ処理装置であって、
データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力する入力手段と、
前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成する前処理手段と、
前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定する検索手段と、
前記条件列のすべての条件を満たしたデータ列の情報を出力する出力手段と
を備えることを特徴とするデータ処理装置。
（付記２）　前記前処理手段は、前記ｍ個の条件からなる条件列上の各位置を右端とする部分条件列であって、該ｍ個の条件からなる条件列の右端の部分条件列と両立するような部分条件列の長さの最大値を表す配列を生成し、該配列を用いて前記補助情報を生成することを特徴とする付記１記載のデータ処理装置。
（付記３）　レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するデータ処理装置であって、
前記パターンを入力する入力手段と、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成する前処理手段と、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定する検索手段と、
前記パターンのすべての述語を満たしたレコード列の情報を出力する出力手段と
を備えることを特徴とするデータ処理装置。
（付記４）　前記前処理手段は、複数の条件式が述語に含まれているとき、該複数の条件式を分離して解析することを特徴とする付記３記載のデータ処理装置。（付記５）　前記前処理手段は、位置ｊを右端とし述語ｐ［ｊ−ｌｅｎ＋１］，．．．，ｐ［ｊ］からなる述語列であって、述語ｐ［ｍ−ｌｅｎ］，．．．，ｐ［ｍ−１］からなる述語列と両立するような述語列の長さｌｅｎの最大値を表す配列を生成し、該配列を用いて前記補助情報を生成することを特徴とする付記３記載のデータ処理装置。
（付記６）　ｋ個の属性ａ［０］，ａ［１］，．．．，ａ［ｋ−１］を有するレコードをｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）とし、ｒ［ｉ］の属性ａ［ｑ］（ｑ＝｛０，１，．．．，ｋ−１｝）の値をｒ［ｉ］．ａ［ｑ］とし、定数と属性ｒ［ｉ１］．ａ［ｑ１］（ｉ１＝｛０，１，．．．，ｎ−１からｉを除いた残り｝、ｑ１＝｛０，１，．．．，ｋ−１｝）を含む任意の関数をＦとし、｛＜，≦，＝，＞，≧，≠｝のうちのいずれかのオペレータをＯＰとして、（ｒ［ｉ］．ａ［ｑ］　ＯＰ　Ｆ）のような条件式の組み合わせで記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するデータ処理装置であって、
前記パターンを入力する入力手段と、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成する前処理手段と、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定する検索手段と、
前記パターンのすべての述語を満たしたレコード列の情報を出力する出力手段と
を備えることを特徴とするデータ処理装置。
（付記７）　複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するコンピュータのためのプログラムであって、
データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力し、
前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成し、
前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記条件列のすべての条件を満たしたデータ列の情報を出力する
処理を前記コンピュータに実行させることを特徴とするプログラム。
（付記８）　レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するコンピュータのためのプログラムであって、
前記パターンを入力し、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成し、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記パターンのすべての述語を満たしたレコード列の情報を出力する
処理を前記コンピュータに実行させることを特徴とするプログラム。
（付記９）　前記コンピュータは、前記補助情報を生成するとき、複数の条件式が述語に含まれていれば、該複数の条件式を分離して解析することを特徴とする付記８記載のプログラム。
（付記１０）　複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するコンピュータのためのプログラムを記録した記録媒体であって、該プログラムは、
データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力し、
前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成し、
前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記条件列のすべての条件を満たしたデータ列の情報を出力する
処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
（付記１１）　レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するコンピュータのためのプログラムを記録した記録媒体であって、該プログラムは、
前記パターンを入力し、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成し、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記パターンのすべての述語を満たしたレコード列の情報を出力する
処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
（付記１２）　前記コンピュータは、前記補助情報を生成するとき、複数の条件式が述語に含まれていれば、該複数の条件式を分離して解析することを特徴とする付記１１記載の記録媒体。
（付記１３）　複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するコンピュータのためのプログラムを該コンピュータに搬送する搬送信号であって、該プログラムは、
データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力し、
前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成し、
前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記条件列のすべての条件を満たしたデータ列の情報を出力する
処理を前記コンピュータに実行させることを特徴とする搬送信号。
（付記１４）　レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するコンピュータのためのプログラムを該コンピュータに搬送する搬送信号であって、該プログラムは、
前記パターンを入力し、
述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成し、
前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
前記パターンのすべての述語を満たしたレコード列の情報を出力する
処理を前記コンピュータに実行させることを特徴とする搬送信号。
（付記１５）　前記コンピュータは、前記補助情報を生成するとき、複数の条件式が述語に含まれていれば、該複数の条件式を分離して解析することを特徴とする付記１４記載の搬送信号。
（付記１６）　複数の順序付けられたデータから、順序付けられたｍ個のデータからなるデータ列を抽出するデータ処理方法であって、
入力手段が、データ間の関係を用いて前記ｍ個のデータをそれぞれ指定する順序付けられたｍ個の条件からなる条件列を入力し、
前処理手段が、前記ｍ個の条件の間の両立性を解析して、データ抽出に用いる補助情報を生成し、
検索手段が、前記順序付けられたデータ上で先頭のデータから末尾のデータに向かって前記データ列を検索するとき、データが前記条件列の対応する条件を満たすか否かを検索方向とは逆の向きにチェックし、チェックされたデータが条件を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
出力手段が、前記条件列のすべての条件を満たしたデータ列の情報を出力することを特徴とするデータ処理方法。
（付記１７）　レコードｒ［ｉ］（ｉ＝｛０，１，．．．，ｎ−１｝）の属性値に対する条件式で記述される述語をｐ［ｊ］（ｊ＝｛０，１，．．．，ｍ−１｝）とするとき、ｎ個のレコードｒ［０］，ｒ［１］，．．．，ｒ［ｎ−１］からなる順序データからｍ個の述語ｐ［０］，ｐ［１］，．．．，ｐ［ｍ−１］からなるパターンを抽出するデータ処理方法であって、
入力手段が、前記パターンを入力し、
前処理手段が、述語ｐ［ｊ］と述語ｐ［ｊ１］（ｊ１＝｛０，１，．．．，ｊ−１｝）の間の両立性を解析し、パターン抽出に用いる補助情報を生成し、
検索手段が、前記順序データ上でレコードｒ［０］からｒ［ｎ−１］に向かって前記パターンに対応するレコード列を検索するとき、レコードが該パターン内の対応する述語を満たすか否かを末尾の述語ｐ［ｍ−１］から先頭の述語ｐ［０］に向かってチェックし、チェックされたレコードが述語を満たさないとき前記補助情報を用いて次のチェック開始位置を決定し、
出力手段が、前記パターンのすべての述語を満たしたレコード列の情報を出力する
ことを特徴とするデータ処理方法。
（付記１８）　前記前処理手段は、複数の条件式が述語に含まれているとき、該複数の条件式を分離して解析することを特徴とする付記１７記載のデータ処理方法。
【０１１４】
【発明の効果】
本発明によれば、与えられたデータから複雑なクエリにより指定された順序パターンを抽出する処理において、指定されたパターンとデータの間の不要なチェックをスキップすることができ、パターンにマッチするデータ列を効率良く検出することができる。
【図面の簡単な説明】
【図１】本発明のデータ処理装置の構成図である。
【図２】基本ウィンドウ処理を示す図である。
【図３】拡張ウィンドウ処理を示す図である。
【図４】ｓｈｉｆｔ［ｊ］のウィンドウシフトを示す図である。
【図５】全体オーバラップを示す図である。
【図６】部分オーバラップを示す図である。
【図７】オーバラップなしのウィンドウシフトを示す図である。
【図８】ｃｏｍｐａｔｉ［ｉ］を示す図である。
【図９】ｃｏｍｐａｔｉ［２］を示す図である。
【図１０】ｃｏｍｐａｔｉ［１］を示す図である。
【図１１】オーバラップなしの場合のパターン述語を示す図である。
【図１２】部分オーバラップの場合のパターン述語を示す図である。
【図１３】全体オーバラップの場合のパターン述語を示す図である。
【図１４】情報処理装置の構成図である。
【図１５】記録媒体を示す図である。
【図１６】ナイーブアプローチの処理結果を示す図である。
【図１７】ＯＰＳアルゴリズムの処理結果を示す図である。
【図１８】本発明の基本処理の処理結果を示す図である。
【図１９】本発明の拡張処理の処理結果を示す図である。
【図２０】５つの検索処理におけるチェック回数を示す図である。
【図２１】チェック回数のグラフを示す図である。
【符号の説明】
１１　入力手段
１２　前処理手段
１３　検索手段
１４　出力手段
２１、２２、２３、３１、３２、４１、４２、５１、６１、７１　ウィンドウ
８１　ＣＰＵ
８２　メモリ
８３　入力装置
８４　出力装置
８５　外部記憶装置
８６　媒体駆動装置
８７　ネットワーク接続装置
８８　バス
８９　可搬記録媒体
９０　サーバ
９１　データベース
１０１、１０２、１０３、１０４、１０５　チェック回数
【図１】
2004046601.tif 000016
【図２】
2004046601.tif 000017
【図３】
2004046601.tif 000018
【図４】
2004046601.tif 000019
【図５】
2004046601.tif 000020
【図６】
2004046601.tif 000021
【図７】
2004046601.tif 000022
【図８】
2004046601.tif 000023
【図９】
2004046601.tif 000024
【図１０】
2004046601.tif 000025
【図１１】
2004046601.tif 000026
【図１２】
2004046601.tif 000027
【図１３】
2004046601.tif 000028
【図１４】
2004046601.tif 000029
【図１５】
2004046601.tif 000030
【図１６】
2004046601.tif 000031
【図１７】
2004046601.tif 000032
【図１８】
2004046601.tif 000033
【図１９】
2004046601.tif 000034
【図２０】
2004046601.tif 000035
【図２１】
2004046601.tif 000036