(57)【要約】      （修正有）【課題】複数のイベントストリームからの複数のイベントにおけるイベントのパターンを検出するシステムおよび方法を提供する。【解決手段】イベントのパターンを検出する方法であって、検出すべきイベントのパターンを定義するテンプレートを受信し、テンプレートからリレーショナルデータベースに対する結合クエリを生成し、結合クエリに対するコスト関数を選択する。結合クエリの計算コストは複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストに等しい。さらに、コスト関数の最小値に従って結合クエリを実行するための好適な計画を特定し、好適な計画の複数のデータベース演算を複数のパターンの順序集合に変換することによって、好適な計画に従って複数のパターンの順序集合を生成し、順序集合を複数のパターンと複数のイベントとの間の複数の一致を検出するための入力として使用することを含む。【選択図】図２
2020017254.tif 000002
【特許請求の範囲】
【請求項１】
イベントのパターンを検出する方法であって、
検出すべきイベントのパターンを定義するテンプレートを受信し、
テンプレートからリレーショナルデータベースに対する結合クエリを生成し、
結合クエリに対するコスト関数を選択し、ただし結合クエリの計算コストは複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストに等しい、
コスト関数の最小値に従って結合クエリを実行するための好適な計画を特定し、
好適な計画の複数のデータベース演算を複数のパターンの順序集合に変換することによって、好適な計画に従って複数のパターンの順序集合を生成し、
順序集合を複数のパターンと複数のイベントとの間の複数の一致を検出するための入力として使用すること
を含む方法。
【請求項２】
テンプレートは純粋な連言パターンであり、イベントのパターンは、
ＡＮＤ演算子によって接続された複数のイベントオペランドであって、各イベントオペランドが予め定められた複数のイベントタイプから選択されたイベントタイプを有し、予め定められた複数のイベントタイプの各々が到着率を有しかつそれぞれのイベントオペランドの複数のイベント属性に関連付けられている、複数のイベントオペランドと、
時間間隔値と、
複数の連言述語であって、各々が複数のイベントオペランドのうちの第１イベントオペランドと複数のイベントオペランドのうちの第２イベントオペランドとを含み、かつ、第１イベントオペランドおよび第２イベントオペランドが時間間隔値内に連言述語を満たす確率を示す選択率値を有する、複数の連言述語と
を含む、請求項１に記載の方法。
【請求項３】
結合クエリを生成することはクエリテンプレートを形成することを含み、クエリテンプレートは、
複数のテーブルであって、各テーブルが予め定められた複数のイベントタイプのうちの一つのイベントタイプに対応し、かつ各テーブルが複数のカラムを含み、各カラムがイベントタイプに関連付けられる複数のイベント属性の一つに関連付けられ、かつ時間間隔値とイベントタイプのそれぞれの到着率との乗算に等しい濃度値を有する、複数のテーブルと、
複数の関係述語であって、各関係述語が複数のテーブルのうちの第１テーブルと複数のテーブルのうちの第２テーブルとを含み、かつ等価の連言述語と等しく、等価の連言述語の第１イベントオペランドが第１テーブルに対応する第１イベントタイプを有し、かつ等価の連言述語の第２イベントオペランドが第２テーブルに対応する第２イベントタイプを有し、各関係述語が等価の連言述語の選択率値に等しい関係選択率値を有する、複数の関係述語と、
全てのカラムの選択を含む結合クエリのＳＥＬＥＣＴ句と、
複数のテーブルを含む結合クエリのＦＲＯＭ句と、
複数の関係述語の間に複数のＡＮＤオペランドを含む結合クエリのＷＨＥＲＥ句と
を含む、請求項２に記載の方法。
【請求項４】
結合クエリを実行するための好適な計画は、各々が複数のノードを有する結合演算子のツリーを含む複数の実行計画から特定され、複数のノードの複数のリーフノードは各々、複数のテーブルのうちの一つのテーブルを表し、複数のノードの複数の内部ノードは各々、内部ノードの一つ以上の子によって表される一つ以上のテーブルを結合することによって生成されるテーブルを表す、請求項２に記載の方法。
【請求項５】
結合クエリのコスト関数は、
複数の実行計画の一つを使用する結合クエリのコスト関数の計算が：
各々が複数のテーブルのうちの一つのテーブルの濃度値である第１の複数の濃度値の和を計算してリーフコスト項を生成すること、
複数の内部ノードから内部ノードを選択し；内部ノードに等しいルートノードを有しかつ複数の関連ノードを含む結合演算子のツリーの関連サブツリーを特定し；複数の関連ノードから複数の関連リーフノードを選択し；複数の関係述語から、各々が複数の関連リーフノードにおける第１関連ノードによって表される第１テーブルと複数の関連リーフノードにおける第２関連ノードによって表される第２テーブルとを有する、複数の関連述語を選択し；複数の関連述語の複数の関連選択率値の積を計算して内部選択率項を生成し；各々が複数のテーブルのうちの一つのテーブルの濃度値であり、各々が複数の関連リーフノードのうちの一つによって表される、第２の複数の濃度値の積を計算して内部濃度項を生成し；内部選択率項に内部濃度項を乗算して内部コスト項を生成することによって、複数の反復の各々で内部コスト項を計算することによって複数の内部コスト項を計算すること、および
複数の内部コスト項とリーフコスト項の和を計算すること
を含むように定義される、請求項４に記載の方法。
【請求項６】
複数の実行計画の各々の結合演算子のツリーは左深ツリーであり、複数の実行計画の各々は、複数のテーブル間の複数の結合演算の実行の順序を示す複数のテーブルを含む結合されたテーブルの順序付きリストを含み、
結合クエリのコスト関数は、複数の実行計画の一つを使用する結合クエリのコスト関数の計算が：
複数の反復の第１反復で、順序付きリストの第１の結合されたテーブルの第１濃度値に、第１の結合されたテーブルに等しい第１テーブルおよび第１の結合されたテーブルに等しい第２テーブルを含む、複数の関係述語のうちの第１関係述語の関係選択率値を乗算して、複数のコスト項のうちの第１コスト項を生成し；累積結合コスト値をゼロに設定し；前に結合されたテーブルのリストに第１結合テーブルを追加し；第１結合テーブルを前の結合テーブルとして特定することによって、かつ、
複数の反復の複数の他の反復の各々で、順序付きリストで前の結合テーブルに続く次の結合テーブルを選択し；前に結合されたテーブルのリストに次の結合テーブルを追加し；各々が前に結合されたテーブルのリストのうちの一つのテーブルの濃度値である、複数の濃度値の積を計算して、濃度項を生成し；複数の関係述語から関連する複数の関係述語を選択し、ただし選択される各関係述語は、前に結合されたテーブルのリストから選択された第１テーブルおよび前に結合されたテーブルのリストから選択された第２テーブルを有し、ここで第１テーブルは前に結合されたテーブルに第２テーブルより先に追加されている；複数の関連述語の関連する複数の選択率値の積を計算して、選択率項を生成し；濃度項に選択率項を乗算して、複数のコスト項の新しいコスト項を生成することによって、複数の反復の各々でコスト項を計算することによって複数のコスト項を計算すること、および
複数のコスト項の和を計算すること
を含むように定義される、請求項４に記載の方法。
【請求項７】
検出すべきイベントのパターンを定義する複合テンプレートを受信し、
結合クエリを生成する前に複合テンプレートを少なくとも一つの純粋な連言パターンに変換し、
少なくとも一つの変換された純粋な連言パターンの各々を、結合クエリを生成するためのテンプレートとして使用することによって、複数の結合クエリを生成することをさらに含む、請求項２に記載の方法。
【請求項８】
複合テンプレートは、複数のイベントオペランド間のイベント順序を定義するＳＥＱＵＥＮＣＥ演算子によって接続された複数のイベントオペランドと、複数の連言述語と、時間間隔値とを含み、
複合テンプレートを純粋な連言パターンに変換することは、複数のイベントオペランドをＡＮＤ演算子によって接続し、複数のイベントオペランドの第１イベントオペランドのタイムスタンプイベント属性の第１タイムスタンプ値が、イベント順序に従って複数のイベントオペランドで第１イベントオペランドのすぐ後に続く第２イベントオペランドのタイムスタンプイベント属性の第２タイムスタンプ値より低い場合、各々が真値を受け取る複数の時間述語を生成し、複数の連言述語に複数の時間述語を付加することを含む、請求項７に記載の方法。
【請求項９】
複合テンプレートは、ＡＮＤ演算子によって接続される複数のイベントオペランドと、複数のイベントオペランドのうちの少なくとも一つのイベントオペランドの少なくとも一つのイベントタイプに適用される少なくとも一つのクリーネ閉包（ＫＬ）演算子と、真値を有する連言述語と、時間間隔値とを含み、
複合テンプレートを純粋な連言パターンに変換することは、複数のイベントオペランドにおいて少なくとも一つのイベントタイプの各々を、それぞれのイベントタイプの到着率に時間間隔値を乗算して指数を生成し、２に指数を累乗して累乗項を生成し、累乗項を時間間隔値で除算することによって計算された、それぞれの変換された到着率を有するそれぞれの変換されたイベントタイプに置換することを含む、請求項７に記載の方法。
【請求項１０】
複合テンプレートは、第１の複数のＡＮＤおよびＯＲ演算子によって接続された複数のイベントオペランドと、複数の連言述語と、時間間隔値とを含み、
複合テンプレートを純粋な連言パターンに変換することは、第１の複数のＡＮＤおよびＯＲ演算子を、複数の純粋な連言パターンを含む選言標準形に適合する第２の複数のＡＮＤ演算子に変換することを含む、請求項７に記載の方法。
【請求項１１】
複数のデータベース演算は、各々が結合演算および選択演算から成る群から選択されたデータベース演算の順序集合を含み、
好適な計画の複数のデータベース演算を複数のパターンの順序集合に変換することは、
複数のデータベース演算のうちの各結合演算に対し、複数の連言述語のうち、結合演算の第１テーブルに対応する第１イベントタイプを有する第１イベントオペランドと結合演算の第２テーブルに対応する第２イベントタイプを有する第２イベントオペランドとを含む連言述語を選択することによって、複数のパターンを生成すること、
複数のデータベース演算のうちの各選択演算に対し、複数のイベントオペランドのうち、選択演算のテーブルに対応するイベントタイプを有するイベントオペランドを含むパターンを生成すること、および
データベース演算の順序集合におけるデータベース演算のそれぞれの順序に従って複数のパターンを順序付けることを含む、請求項３に記載の方法。
【請求項１２】
イベントのパターンを検出するためのシステムであって、
検出すべきイベントのパターンを定義するテンプレートを受信し；テンプレートからリレーショナルデータベースに対する結合クエリを生成し、結合クエリに対するコスト関数を選択し、ここで結合クエリの計算コストは、複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストに等しく；コスト関数の最小値に従って結合クエリを実行するための好適な計画を特定し；計画の複数のデータベース演算を複数のパターンの順序集合に変換することによって、計画に従って複数のパターンの順序集合を生成し；かつ順序集合を複数のパターンと複数のイベントとの間の複数の一致を検出するための入力として使用する
ように適応された、少なくとも一つのハードウェアプロセッサを備える、システム。
【請求項１３】
複数のイベントストリームのうちの少なくとも一つは、少なくとも一つのハードウェアプロセッサに接続された少なくとも一つのセンサから、少なくとも一つのハードウェアプロセッサによって受信される、請求項１２に記載のシステム。
【請求項１４】
少なくとも一つのセンサは、少なくとも一つのハードウェアプロセッサに接続された少なくとも一つのデジタル通信ネットワークインタフェースを介して、少なくとも一つのハードウェアプロセッサに接続される、請求項１３に記載のシステム。
【請求項１５】
少なくとも一つのセンサは、デジタルカメラ、デジタル・ビデオ・カメラ、マイクロホン、温度センサ、電磁放射センサ、および圧力センサを含む一群のセンサから選択される、請求項１３に記載のシステム。
【請求項１６】
複数のイベントストリームのうちの少なくとも一つは、少なくとも一つのデジタル通信ネットワークインタフェースを介して少なくとも一つのハードウェアプロセッサに接続された少なくとも一つの他のハードウェアプロセッサから、少なくとも一つのハードウェアプロセッサによって受信される、請求項１２に記載のシステム。
【請求項１７】
少なくとも一つのハードウェアプロセッサはさらに、複数の一致を検出したことを示すものを出力するように適応される、請求項１２に記載のシステム。
【請求項１８】
少なくとも一つのハードウェアプロセッサは、複数の一致を検出したことを示す少なくとも一つのメッセージを、少なくとも一つの他のデジタル通信ネットワークインタフェースを介して送信すること、および複数の一致を検出したことを示すデータを、少なくとも一つのハードウェアプロセッサに接続された少なくとも一つの不揮発性デジタルストレージに保存することのうちの少なくとも一つによって、指示を出力する、請求項１７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本願は、２０１８年７月２５日に出願された米国特許出願第１６／０４４５２９号の優先権の利益を主張する。この出願は、その全体を参照によってここに組み入れられる。
発明の分野
本発明は、その一部の実施形態では、関心イベントを監視しかつ追跡するためのシステムに関し、さらに詳しくは、大量のデータストリームにおける関心イベントを監視しかつ追跡するためのシステムに関するが、それのみに限定されない。
【背景技術】
【０００２】
複合イベント処理（ＣＥＰ）とは、複数のソースから、イベントと呼ばれる、発生する出来事に関する情報の流れを追跡しかつ解析し、複数のソースからの情報の流れを組み合わせて、一つ以上の有意のイベント、例えば機会または脅威を特定し、一つ以上の有意のイベントにできるだけ迅速に対応することを指す。ＣＥＰ方法は複合イベント処理に使用される方法である。
【０００３】
ソースからの複数のイベントを本書ではイベントのストリームと呼ぶ。イベントのストリームは、処理のために共にグループ化された複数のソースから受信される複数のイベントを含んでよい。一部のＣＥＰシステムでは、イベントの幾つかは、物理的測定のセンサ、例えば温度センサ、空気圧センサ、または時間測定装置から受信される。一部のＣＥＰシステムでは、イベントの幾つかはコンピュータまたはプロセッサから受信される。コンピュータまたはプロセッサから受信されるイベント例の非限定リストは、テキストメッセージ、ソーシャル・メディア・ポスト、交通情報、セールスリード、および注文を含む。
【０００４】
一部のＣＥＰシステムは、複数のイベントを含む一つ以上のイベントストリームを受信し、複数の受信したイベントを検査して、一つ以上の予め定められたパターンと合致する出来事の組合せを検出する。ＣＥＰ方法を実現することのできるシステム例として、オンライン金融システム、不正検出システム、車両交通管理システム、およびセキュリティシステムが挙げられるが、それらに限定されない。
【発明の概要】
【０００５】
本発明の目的は、複数のイベントストリームからの複数のイベントにおけるイベントのパターンを検出するためのシステムおよび方法を提供することである。
【０００６】
上記および他の目的は、独立請求項の特徴によって達成される。さらなる実現形態は、従属請求項、本書の記載、および図面から明らかである。
【０００７】
本発明の第１態様によれば、イベントのパターンを検出する方法は、検出すべきイベントのパターンを定義するテンプレートを受信し、テンプレートからリレーショナルデータベースに対する結合クエリを生成し、結合クエリに対するコスト関数を選択し、ただし結合クエリの計算コストは複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストに等しい、コスト関数の最小値に従って結合クエリを実行するための好適な計画を特定し、好適な計画の複数のデータベース演算を複数のパターンの順序集合に変換することによって、好適な計画に従って複数のパターンの順序集合を生成し、順序集合を複数のパターンと複数のイベントとの間の複数の一致を検出するための入力として使用することを含む。
【０００８】
本発明の第２態様によれば、イベントのパターンを検出するためのシステムは、検出すべきイベントのパターンを定義するテンプレートを受信し；テンプレートからリレーショナルデータベースに対する結合クエリを生成し、結合クエリに対するコスト関数を選択し、ここで結合クエリの計算コストは、複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストに等しく；コスト関数の最小値に従って結合クエリを実行するための好適な計画を特定し；計画の複数のデータベース演算を複数のパターンの順序集合に変換することによって、計画に従って複数のパターンの順序集合を生成し；かつ順序集合を複数のパターンと複数のイベントとの間の複数の一致を検出するための入力として使用するように適応された、少なくとも一つのハードウェアプロセッサを備える。
【０００９】
イベントのパターンを定義するテンプレートを結合クエリに変換し、かつ結合クエリを実行するための計画を複数のパターンの順序集合に変換することにより、当業者で公知の方法を使用して、複数の一致を検出することによって複数のイベントのパターンを検出するための好適な実行計画を識別することが可能になる。本発明に従って特定される好適な計画は、イベントのパターンを検出するときに計算コストの低減、より高いスループット、および検出待ち時間の低減のうちの一つ以上を促進することができ、したがって操作のコストを低減し、検出システムの精度を高めることができる。
【００１０】
第１および第２態様に関連して、本発明の第１および第２態様の第１の可能な実現では、テンプレートは純粋な連言パターンであるので、イベントのパターンは、ＡＮＤ演算子によって接続された複数のイベントオペランドであって、各イベントオペランドが予め定められた複数のイベントタイプから選択されたイベントタイプを有し、予め定められた複数のイベントタイプの各々が到着率を有しかつそれぞれのイベントオペランドの複数のイベント属性に関連付けられている、複数のイベントオペランドと、時間間隔値と、複数の連言述語であって、各々が複数のイベントオペランドのうちの第１イベントオペランドと複数のイベントオペランドのうちの第２イベントオペランドとを含み、かつ、第１イベントオペランドおよび第２イベントオペランドが時間間隔値内に連言述語を満たす確率を示す選択率値を有する、複数の連言述語と、を含む。任意選択的に、結合クエリを生成することはクエリテンプレートを形成することを含み、クエリテンプレートは、複数のテーブルであって、各テーブルが予め定められた複数のイベントタイプのうちの一つのイベントタイプに対応し、かつ各テーブルが複数のカラムを含み、各カラムがイベントタイプに関連付けられる複数のイベント属性の一つに関連付けられ、かつ時間間隔値とイベントタイプのそれぞれの到着率との乗算に等しい濃度値を有する、複数のテーブルと、複数の関係述語であって、各関係述語が複数のテーブルのうちの第１テーブルと複数のテーブルのうちの第２テーブルとを含み、かつ等価の連言述語と等しく、等価の連言述語の第１イベントオペランドが第１テーブルに対応する第１イベントタイプを有し、かつ等価の連言述語の第２イベントオペランドが第２テーブルに対応する第２イベントタイプを有し、各関係述語が等価の連言述語の選択率値に等しい関係選択率値を有する、複数の関係述語と、全てのカラムの選択を含む結合クエリのＳＥＬＥＣＴ句と、複数のテーブルを含む結合クエリのＦＲＯＭ句と、複数の関係述語の間に複数のＡＮＤオペランドを含む結合クエリのＷＨＥＲＥ句と、を含む。任意選択的に、複数のデータベース演算は、各々が結合演算および選択演算から成る群から選択されたデータベース演算の順序集合を含み、好適な計画の複数のデータベース演算を複数のパターンの順序集合に変換することは、複数のデータベース演算のうちの各結合演算に対し、複数の連言述語のうち、結合演算の第１テーブルに対応する第１イベントタイプを有する第１イベントオペランドと結合演算の第２テーブルに対応する第２イベントタイプを有する第２イベントオペランドとを含む連言述語を選択することによって、複数のパターンを生成すること、複数のデータベース演算のうちの各選択演算に対し、複数のイベントオペランドのうち、選択演算のテーブルに対応するイベントタイプを有するイベントオペランドを含むパターンを生成すること、およびデータベース演算の順序集合におけるデータベース演算のそれぞれの順序に従って複数のパターンを順序付けることを含む。任意選択的に、結合クエリを実行するための好適な計画は、各々が複数のノードを有する結合演算子のツリーを含む複数の実行計画から特定され、複数のノードの複数のリーフノードは各々、複数のテーブルのうちの一つのテーブルを表し、複数のノードの複数の内部ノードは各々、内部ノードの一つ以上の子によって表される一つ以上のテーブルを結合することによって生成されるテーブルを表す。イベントタイプの複数のイベント属性と一致する複数のカラムを有するリレーショナル・データベース・テーブルにイベントタイプをマッピングし、イベントの到着率をそれぞれのリレーショナル・データベース・テーブルの濃度にマッピングし、イベントのパターンの連言述語と等価の関係述語を形成し、かつ連言述語の選択率値をそれぞれの関係述語の選択率値にマッピングすることにより、生成された結合クエリの好適な実行計画とイベントのパターンの好適な評価計画との間の関連付けを容易にし、したがって結合クエリ最適化方法を使用してイベントのパターンの好適な評価計画の特定を容易にすることができる。
【００１１】
第１および第２態様、または第１および第２態様の第１実現に関連して、本発明の第１および第２態様の第２の可能な実現では、結合クエリのコスト関数は次のように定義される。すなわち、複数の実行計画の一つを使用する結合クエリのコスト関数の計算が：各々が複数のテーブルのうちの一つのテーブルの濃度値である第１の複数の濃度値の和を計算してリーフコスト項を生成すること、複数の内部ノードから内部ノードを選択し；内部ノードに等しいルートノードを有しかつ複数の関連ノードを含む結合演算子のツリーの関連サブツリーを特定し；複数の関連ノードから複数の関連リーフノードを選択し；複数の関係述語から、各々が複数の関連リーフノードにおける第１関連ノードによって表される第１テーブルと複数の関連リーフノードにおける第２関連ノードによって表される第２テーブルとを有する、複数の関連述語を選択し；複数の関連述語の複数の関連選択率値の積を計算して内部選択率項を生成し；各々が複数のテーブルのうちの一つのテーブルの濃度値であり、各々が複数の関連リーフノードのうちの一つによって表される、第２の複数の濃度値の積を計算して内部濃度項を生成し；内部選択率項に内部濃度項を乗算して内部コスト項を生成することによって、複数の反復の各々で内部コスト項を計算することによって複数の内部コスト項を計算すること、および複数の内部コスト項とリーフコスト項の和を計算することを含む。そのような関数は、時間間隔内のメモリに共存する部分一致量に従って好適な実行計画を選択するために使用することができる。
【００１２】
第１および第２態様、または第１および第２態様の第１実現に関連して、本発明の第１および第２態様の第３の可能な実現では、複数の実行計画の各々の結合演算子のツリーは左深ツリーであり、複数の実行計画の各々は、複数のテーブル間の複数の結合演算の実行の順序を示す複数のテーブルを含む結合されたテーブルの順序付きリストを含み、ここで結合クエリのコスト関数は次のように定義される。すなわち、複数の実行計画の一つを使用する結合クエリのコスト関数の計算が：複数の反復の第１反復で、順序付きリストの第１の結合されたテーブルの第１濃度値に、第１の結合されたテーブルに等しい第１テーブルおよび第１の結合されたテーブルに等しい第２テーブルを含む、複数の関係述語のうちの第１関係述語の関係選択率値を乗算して、複数のコスト項のうちの第１コスト項を生成し；累積結合コスト値をゼロに設定し；前に結合されたテーブルのリストに第１結合テーブルを追加し；第１結合テーブルを前の結合テーブルとして特定することによって、かつ、複数の反復の複数の他の反復の各々で、順序付きリストで前の結合テーブルに続く次の結合テーブルを選択し；前に結合されたテーブルのリストに次の結合テーブルを追加し；各々が前に結合されたテーブルのリストのうちの一つのテーブルの濃度値である、複数の濃度値の積を計算して、濃度項を生成し；複数の関係述語から関連する複数の関係述語を選択し、ただし選択される各関係述語は、前に結合されたテーブルのリストから選択された第１テーブルおよび前に結合されたテーブルのリストから選択された第２テーブルを有し、ここで第１テーブルは前に結合されたテーブルに第２テーブルより先に追加されている；複数の関連述語の関連する複数の選択率値の積を計算して、選択率項を生成し；濃度項に選択率項を乗算して、複数のコスト項の新しいコスト項を生成することによって、複数の反復の各々でコスト項を計算することによって複数のコスト項を計算すること、および複数のコスト項の和を計算することを含む。そのような関数は、好適な実行計画が一連のパターンに配置されたパターンの順序集合であることが限定されるシステムにおいて、時間間隔内にメモリに共存する部分一致量に従って好適な実行計画を選択するために使用することができる。
【００１３】
第１および第２態様、または第１および第２態様の第１実現に関連して、本発明の第１および第２態様の第４の可能な実現では、方法はさらに、検出すべきイベントのパターンを定義する複合テンプレートを受信し、結合クエリを生成する前に複合テンプレートを少なくとも一つの純粋な連言パターンに変換し、少なくとも一つの変換された純粋な連言パターンの各々を、結合クエリを生成するためのテンプレートとして使用することによって、複数の結合クエリを生成することを含む。複合テンプレートを一つ以上の連言テンプレートに変換することで、本発明に従って複数のイベントの複雑なパターンを照合するための最小コストの実行計画を特定することが容易になる。任意選択的に、複合テンプレートは、複数のイベントオペランド間のイベント順序を定義するＳＥＱＵＥＮＣＥ演算子によって接続された複数のイベントオペランドと、複数の連言述語と、時間間隔値とを含み、複合テンプレートを純粋な連言パターンに変換することは、複数のイベントオペランドをＡＮＤ演算子によって接続し、複数のイベントオペランドの第１イベントオペランドのタイムスタンプイベント属性の第１タイムスタンプ値が、イベント順序に従って複数のイベントオペランドで第１イベントオペランドのすぐ後に続く第２イベントオペランドのタイムスタンプイベント属性の第２タイムスタンプ値より低い場合、各々が真値を受け取る複数の時間述語を生成し、複数の連言述語に複数の時間述語を付加することを含む。任意選択的に、複合テンプレートは、ＡＮＤ演算子によって接続される複数のイベントオペランドと、複数のイベントオペランドのうちの少なくとも一つのイベントオペランドの少なくとも一つのイベントタイプに適用される少なくとも一つのクリーネ閉包（ＫＬ）演算子と、真値を有する連言述語と、時間間隔値とを含み、複合テンプレートを純粋な連言パターンに変換することは、複数のイベントオペランドにおいて少なくとも一つのイベントタイプの各々を、それぞれのイベントタイプの到着率に時間間隔値を乗算して指数を生成し、２に指数を累乗して累乗項を生成し、累乗項を時間間隔値で除算することによって計算された、それぞれの変換された到着率を有するそれぞれの変換されたイベントタイプに置換することを含む。任意選択的に、複合テンプレートは、第１の複数のＡＮＤおよびＯＲ演算子によって接続された複数のイベントオペランドと、複数の連言述語と、時間間隔値とを含み、複合テンプレートを純粋な連言パターンに変換することは、第１の複数のＡＮＤおよびＯＲ演算子を、複数の純粋な連言パターンを含む選言標準形に適合する第２の複数のＡＮＤ演算子に変換することを含む。
【００１４】
第１および第２態様に関連して、本発明の第１および第２態様の第５の可能な実現では、複数のイベントストリームのうちの少なくとも一つは、少なくとも一つのハードウェアプロセッサに接続された少なくとも一つのセンサから、少なくとも一つのハードウェアプロセッサによって受信される。任意選択的に、少なくとも一つのセンサは、少なくとも一つのハードウェアプロセッサに接続された少なくとも一つのデジタル通信ネットワークインタフェースを介して、少なくとも一つのハードウェアプロセッサに接続される。任意選択的に、少なくとも一つのセンサは、デジタルカメラ、デジタル・ビデオ・カメラ、マイクロホン、温度センサ、電磁放射センサ、および圧力センサを含む一群のセンサから選択される。少なくとも一つのデジタル・ネットワーク・インタフェースを介して複数のセンサを少なくとも一つのハードウェアプロセッサに接続することは、複数の場所から受信される複数のイベントストリームから複数のイベントにおけるイベントのパターンを同時に検出することを容易にし、したがってイベントのパターンの検出待ち時間を低減することができる。任意選択的に、複数のイベントストリームのうちの少なくとも一つは、少なくとも一つのデジタル通信ネットワークインタフェースを介して少なくとも一つのハードウェアプロセッサに接続された少なくとも一つの他のハードウェアプロセッサから、少なくとも一つのハードウェアプロセッサによって受信される。少なくとも一つの他のハードウェアプロセッサからイベントのストリームを受信することは、デジタル画像における物体の検出のような、計算を必要とするイベントを含むイベントのパターンの検出を容易にすることができる。
【００１５】
第１および第２態様に関連して、本発明の第１および第２態様の第６の可能な実現では、少なくとも一つのハードウェアプロセッサはさらに、複数の一致を検出したことを示すものを出力するように適応される。任意選択的に、少なくとも一つのハードウェアプロセッサは、複数の一致を検出したことを示す少なくとも一つのメッセージを、少なくとも一つの他のデジタル通信ネットワークインタフェースを介して送信すること、および複数の一致を検出したことを示すデータを、少なくとも一つのハードウェアプロセッサに接続された少なくとも一つの不揮発性デジタルストレージに保存することのうちの少なくとも一つによって、指示を出力する。
【００１６】
本開示の他のシステム、方法、特徴、及び利点は、以下の図面及び詳細な記載の検討により当業者に明らかであるか、又は明らかになるだろう。全てのかかる追加のシステム、方法、特徴、及び利点がこの記載内に含まれ、本開示の範囲内にあり、添付の請求項によって保護されることが意図される。
【００１７】
別途定義されない限り、本明細書で使用されるすべての技術的用語および／または科学的用語は、本発明が属する技術分野の当業者によって一般に理解されるのと同じ意味を有する。本明細書に記載される方法および材料と類似または同等である方法および材料を本発明の実施または試験において使用することができるが、例示的な方法および／または材料が下記に記載される。矛盾する場合には、定義を含めて、本特許明細書が優先する。加えて、材料、方法および実施例は例示にすぎず、限定であることは意図されない。
【図面の簡単な説明】
【００１８】
本明細書では本発明のいくつかの実施形態を単に例示し添付の図面を参照して説明する。特に詳細に図面を参照して、示されている詳細が例示として本発明の実施形態を例示考察することだけを目的としていることを強調するものである。この点について、図面について行う説明によって、本発明の実施形態を実施する方法は当業者には明らかになるであろう。
【００１９】
【図１】図１は、本発明の一部の実施形態に係る例示的システムの略ブロック図である。
【００２０】
【図２】図２は、本発明の一部の実施形態に係る、イベントのパターンを検出するための操作の任意の流れを概略的に表すフローチャートである。
【００２１】
【図３】図３は、本発明の一部の実施形態に係る、左深ツリー解決法のコスト関数を計算するための操作の任意の流れを概略的に表すフローチャートである。
【００２２】
【図４】図４は、本発明の一部の実施形態に係る、一般ツリー解決法のコスト関数を計算するための操作の任意の流れを概略的に表すフローチャートである。
【００２３】
【図５】図５は、本発明の一部の実施形態に係る、結合クエリの実行計画を変換するための操作の任意の流れを概略的に表すフローチャートである。
【００２４】
【図６】図６は、本発明の一部の実施形態に係る、イベントの複合パターンを検出するための操作の任意の流れを概略的に表すフローチャートである。
【発明を実施するための形態】
【００２５】
本発明は、その一部の実施形態では、関心イベントを監視しかつ追跡するためのシステムに関し、さらに詳しくは、大量のデータストリームにおける関心イベントを監視しかつ追跡するためのシステムに関するが、それのみに限定されない。システムによっては、この処理は、イベントのストリームを受信しながら、実時間で行われる。複合イベント処理は、一つ以上のイベントストリームが高速で到達する用途にとってますます重要になってきており、任意に複雑なパターンは、一つ以上のイベントストリームを受信しながら効率的に検出されなければならず、したがって複数のイベントストリームを処理する処理時間を低減する必要がある。
【００２６】
パターン検出は一般的に、複数のイベントを収集すること、および予め定められた検出モデルを使用して複数のイベントを一つ以上の部分一致に結合することから成る。追加イベントは部分一致に追加され、完全パターン一致が最終的に形成され、かつ任意選択的に報告される。既存のＣＥＰ方法で使用される検出モデルは、非決定性有限オートマトン、有限状態機械、およびイベント処理ネットワークを含む。
【００２７】
これからは、用語「ＣＥＰエンジン」は、一つ以上のＣＥＰ方法を用いてイベントのパターンを検出するためのシステムを意味するものとして使用される。
【００２８】
ＣＥＰエンジンは、検出モデルに基づいて、検出すべきイベントのパターンの内部表現を形成することができる。表現の例としてツリーおよびオートマトンがある。ツリーは複数のノードを有する非循環接続グラフであり、ここで任意の二つのノードが厳密に一つの経路によって接続される。表現はパターンの構造を反映する。一部のＣＥＰエンジンはコストに基づく評価計画を使用し、ここではイベントのパターンの複数の表現が可能であり、ユーザの選好または予め定められたコストメトリックに従って一つが選択される。そのような評価計画は複数のパターンの評価の可能な順序を含み、可能な順序での複数のパターンの複合評価は、結果的にイベントのパターンと複数のイベントストリームとの間の完全なパターンの一致をもたらすことができる。順序は完全に逐次的でなくてもよく、例えば順序はツリー構造を有してもよく、そこでは一つ以上の評価が並行して実行されてよい。コストに基づく評価計画を使用することは、別の可能な評価計画より効率的に選択することを容易にする。イベントのパターンを含む複数のパターンの量が増大するにつれて、イベントのパターンの可能な表現の量は増大する。通常、可能な表現の量は、複数のパターンの量に対して少なくとも指数関数的に増大し、したがって最適コストを有する対応する評価計画の特定は、より複雑なタスクになり得る。ＣＥＰシステムのための好適な実行計画を特定する幾つかの既存の方法は、シミュレーションに基づく技術を使用して、実行計画の評価コストを推定することを含む。シミュレーションはかなりの量の計算リソースを必要とし、本来、実行計画の評価の正確な実際のコストを描くことはできない。
【００２９】
同様の問題は、大規模な結合クエリの好適な実行計画を特定することを必要とするリレーショナルデータベースの分野にも存在する。結合クエリの実行は、複数のデータベース演算を使用して、複数の関係制約を満たしながらリレーショナルデータベースの複数の関係を組み合わせることを含む。結合クエリの好適な実行計画の特定は、特定されたデータベースコスト関数が最小化されるように、複数のデータベース演算の実行順序を特定することを含む。結合クエリの好適な実行計画を特定する既存の方法は、貪欲な発見的技法、徹底的な動的プログラミング技法、ならびにランダマイズドおよび遺伝的アルゴリズムを含む。
【００３０】
本発明は、その一部の実施形態で、ＣＥＰ実行計画のコスト見積もりとリレーショナルデータベースにおける大規模な結合クエリのための実行計画のコスト見積もりとの間の類似性を使用して、ＣＥＰシステムにおける好適な実行計画を特定することを提案する。
【００３１】
ＣＥＰシステムにおいて、イベントのパターンは、（各々イベントオペランドによって表される）複数の原始イベントと複数の演算子との組合せ、複数のイベントオペランドによって満たされる複数の述語、および時間窓値を含むテンプレートによって定義することができる。各イベントオペランドはイベントタイプおよび複数のイベント属性を有することができる。一部のＣＥＰシステムでは、イベントの一つのストリーム内の複数のイベントは共通のイベントタイプを有する。タイムスタンプはイベント属性の一例である。時間窓値は、一つのイベントオペランドのタイムスタンプ属性値と、イベントパターンが一致する第２のイベントオペランドのタイムスタンプ属性値との間の最大許容差を定義する。イベントタイプが資金移動である別の実施例では、イベントタイプの複数のイベント属性は、移動のオリジネータ、移動の受取人、および金額を含むことができる。イベントタイプがデジタル画像における車両の検出であるさらに別の実施例では、イベントタイプの複数のイベント属性は、車種、車両の色、車両の寸法、および車両のナンバープレート番号を含むことができる。複数の演算子の幾つかは、複数のイベントオペランドのうちの一つとそれ以上との間のイベント関係を記述する。複数の演算子の他の幾つかは、それ自体とのイベント関係を記述する。例えばＡＮＤ演算子は、複数のイベントオペランドのうちの一つ以上が全部、時間窓値によって定められた時間窓内に発生する場合のイベント関係を記述する。ＳＥＱＵＥＮＣＥ演算子は、複数のイベントオペランドのうちの一つ以上が全部、時間窓値によって定められた時間窓内に、予め定められた順序で発生する場合のイベント関係を記述する。ＯＲ演算子は、複数のイベントオペランドのうちの一つ以上のうちのいずれか一つが、時間窓値によって定められた時間窓内に発生する場合のイベント関係を記述する。ＮＯＴ演算子は、複数のイベントオペランドのうちのイベントオペランドの不在を記述する。クリーネ閉包（ＫＬ）演算子は、時間窓値によって定められた時間窓内に生じる、あるイベントタイプの一つ以上のイベントオペランドの複数のイベントシーケンスを記述する。複数の述語は、複数のイベントオペランドのうちの一つ以上のイベントオペランドの一つ以上のイベント属性値に対し一つ以上の制約を指定する。複数のイベントが時間窓値内に受信され、複数のイベントオペランドを含み、かつイベントオペランドの複数のイベント属性値が複数の述語を満たす場合、イベントのパターンと複数のイベントストリームのうちの複数のイベントとの間に一致が検出される。
【００３２】
以下で詳述するように、本発明の一部の実施形態では、イベントのパターンを記述するテンプレートは、リレーショナルデータベースのための等価結合クエリテンプレートに変換される。加えて、そのような実施形態では、結合クエリのコスト関数は、コスト関数に従って結合クエリテンプレートによって定義された結合クエリの計算コストが、複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストと等価になるように選択される。任意選択的に、結合クエリを実行するための好適な実行計画は、任意選択的に当業者で公知の方法を使用して、コスト関数の最小値に従って特定される。好適な計画は任意選択的に複数のデータベース演算を含む。任意選択的に、複数のデータベース演算は、結合演算および選択演算を含む一群の可能なデータベース演算から選択される。次に、好適な計画の複数のデータベース演算は、複数のパターンの順序集合に変換される。複数のパターンの順序集合は次いで、複数のイベントストリームから複数のイベントのイベントパターンを検出するために、ＣＥＰシステムによって使用することができる。
【００３３】
本発明に従って生成されるイベントのパターンを検出する実行計画を使用することにより、シミュレーション方法のような他の方法を使用して生成される実行計画を使用する別のＣＥＰシステムと比較して、ＣＥＰシステムのスループットを増大することができる。加えて、または代替的に、本発明に従って生成されるイベントのパターンを検出する実行計画を使用することにより、他の方法を使用して生成される実行計画を使用する場合と比較して、例えばイベントのパターンを検出するために必要な演算量を低減することによって、イベントのパターンを検出するための計算コストを低減することができる。
【００３４】
本発明の少なくとも１つの実施形態を詳しく説明する前に、本発明は、その適用において、下記の説明に示されるか、および／または図面および／または実施例において例示される構成要素および／または方法の組み立ておよび構成の細部に必ずしも限定されないことを理解しなければならない。本発明は他の実施形態が可能であり、または様々な方法で実施または実行されることが可能である。
【００３５】
本発明は、システム、方法、および／またはコンピュータプログラム製品とすることができる。コンピュータプログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラム命令を有する、コンピュータ可読記憶媒体（単数または複数の）を含むことができる。
【００３６】
コンピュータ可読記憶媒体は、命令実行装置によって使用される命令を保持しかつ格納することのできる有形の装置とすることができる。コンピュータ可読記憶媒体は、例えば電子記憶装置、磁気記憶装置、光学記憶装置、電磁記憶装置、半導体記憶装置、または上記の任意の適切な組合せとすることができるが、それらに限定されない。
【００３７】
本書に記載するコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体からそれぞれのコンピューティング装置／処理装置に、またはネットワーク、例えばインターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、および／または無線ネットワークを介して外部コンピュータもしくは外部記憶装置にダウンロードすることができる。
【００３８】
コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンド・アロン・ソフトウェア・パッケージとして、部分的にユーザコンピュータ上でかつ部分的にリモートコンピュータ上で、または完全にリモートコンピュータもしくはサーバ上で実行することができる。後者のシナリオでは、リモートコンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）をはじめとする任意の種類のネットワークを介して、ユーザのコンピュータに接続することができ、あるいは接続は、（例えばインターネット・サーバ・プロバイダを使用してインターネットを介して）外部コンピュータに行うことができる。一部の実施形態では、例えばプログラマブル論理回路構成、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル論理アレイ（ＰＬＡ）をはじめとする電子回路構成は、本発明の態様を実行するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路構成を個別化することによって、コンピュータ可読プログラム命令を実行することができる。
【００３９】
本発明の態様を本書で、本発明の実施形態に係る方法、装置（システム）、およびコンピュータプログラム製品のフローチャート図および／またはブロック図に関連して記載する。フローチャート図および／またはブロック図の各ブロック、ならびにフローチャート図および／またはブロック図のブロックの組合せは、コンピュータ可読プログラム命令によって実現することができることは理解されるであろう。
【００４０】
図面におけるフローチャートおよびブロック図は、本発明の様々な実施形態に係るシステム、方法、およびコンピュータプログラム製品の可能な実現のアーキテクチャ、機能、および動作を示す。これに関して、フローチャートまたはブロック図の各ブロックは、特定の論理関数を実現するための一つ以上の実行可能な命令を含む命令のモジュール、セグメント、または部分を表す。一部の代替的実現では、ブロックに記された機能は、図に記された順序以外の順序で行うことができる。例えば連続して示される二つのブロックは、実際には、略同時に実行することができ、あるいはブロックは時には、関係する機能によっては、逆の順序で実行することができる。ブロック図および／またはフローチャート図の各ブロック、ならびにブロック図および／またはフローチャート図のブロックの組合せは、特定の機能または動作を実行するかあるいは特殊用途向けハードウェアおよびコンピュータ命令の組合せを実行する、特殊用途向けハードウェアベースのシステムによって実現することができることに留意されたい。
【００４１】
次に図１を参照すると、本発明の一部の実施形態に係る例示的システム１００の略ブロック図が示されている。そのような実施形態では、少なくとも一つのハードウェアプロセッサ１０１は、複数のイベントストリームを少なくとも一つのセンサ１０４から受信するために、少なくとも一つのデジタル通信ネットワークインタフェース１０２に接続される。任意選択的に、少なくとも一つのハードウェアプロセッサ１０１は、少なくとも一つのデジタル通信ネットワークインタフェースを介して、複数のイベントストリームの幾つかを少なくとも一つの他のプロセッサ１０５から受信する。少なくとも一つのデジタル通信ネットワークインタフェース１０２は任意選択的にローカル・エリア・ネットワーク（ＬＡＮ）、例えばイーサネット（登録商標）ネットワーク、またはワイヤレスフィデリティ（ＷｉＦｉ）ネットワークのような無線ネットワークに接続する。任意選択的に、少なくとも一つのデジタル通信ネットワークインタフェース１０２はワイド・エリア・ネットワーク（ＷＡＮ）、例えばインターネットに接続する。任意選択的に、少なくとも一つのセンサ１０４は少なくとも一つのハードウェアプロセッサ１０１に直接接続される。センサの幾つかの例として、デジタルカメラ、デジタル・ビデオ・カメラ、マイクロホン、温度センサ、電磁放射センサ、および圧力センサがある。任意選択的に、例えば複数の一致を検出することによってイベントのパターンを検出すると、少なくとも一つのハードウェアプロセッサ１０１は、複数の一致を検出したことを示す指示を出力する。任意選択的に、少なくとも一つのハードウェアプロセッサ１０１は、複数の一致を検出したことを示す少なくとも一つのメッセージを例えば少なくとも一つの管理ハードウェアプロセッサに送信するために、少なくとも一つの他のデジタル通信ネットワークインタフェース１０８に接続される。任意選択的に、少なくとも一つのハードウェアプロセッサ１０１は、複数の一致を検出したことを示すデータを少なくとも一つの不揮発性デジタルストレージ１０９に格納するために、少なくとも一つの不揮発性デジタルストレージ１０９に接続される。不揮発性デジタルストレージの例として、ハード・ディスク・ドライブ、ネットワークストレージ装置、およびストレージネットワークがある。任意選択的に、例えば不揮発性デジタルストレージがネットワークストレージ装置である場合、少なくとも一つの不揮発性デジタルストレージ１０９は、少なくとも一つのデジタル・ネットワーク・インタフェース１０８を介して、少なくとも一つのハードウェアプロセッサ１０１に接続される。任意選択的に、少なくとも一つのデジタル・ネットワーク・インタフェース１０８は、少なくとも一つのデジタル・ネットワーク・インタフェース１０２である。任意選択的に、少なくとも一つのハードウェアプロセッサ１０１はデジタルメモリ、例えばランダム・アクセス・メモリ（ＲＡＭ）に結合される。任意選択的に、デジタルメモリは不揮発性であり、例えば不揮発性ランダム・アクセス・メモリ（ＮＶＲＡＭ）である。
【００４２】
イベントのパターンを検出するために、本発明の一部の実施形態では、システム１００は以下の任意の方法を実現する。
【００４３】
次に図２も参照すると、本発明の一実施形態に係る、イベントのパターンを検出するための操作２００の任意の流れを概略的に表すフローチャートが示されている。そのような実施形態では、少なくとも一つのハードウェアアダプタは２０１で、検出すべきイベントのパターンを定義するテンプレートを受信する。任意選択的に、テンプレートは、ＡＮＤ演算子によって接続された複数のイベントオペランドを含む純粋な連言パターンである。任意選択的に、各イベントオペランドは予め定められた複数のイベントタイプから選択されたイベントタイプを有する。イベントタイプの例として、マイクロホンによって捕捉される音声信号、音声信号の処理結果、デジタル画像で予め定められたオブジェクトを検出したことを示す指示、および資金転送がある。予め定められた複数のイベントタイプの各々は任意選択的に、予め定められた時間量内に到着するイベントの平均量または予想量を記述する到着率を有する。任意選択的に、予め定められた複数のイベントタイプの各々は、それぞれのイベントオペランドの複数のイベント属性と関連付けられる。任意選択的に、複数のイベントオペランドの各々は、複数のイベント属性の複数のイベント属性値を有する。イベント属性の例として、例えばイベント発生時間または少なくとも一つのハードウェアプロセッサ１０１によるイベント受信時間のタイムスタンプがある。イベント属性の他の例として、資金転送のオリジネータ、資金転送の受取人、金額、車種、車両の色、車両の寸法、および車両のナンバープレート番号がある。任意選択的に、テンプレートは、複数のイベントオペランドの複数のタイムスタンプイベント属性値のうちで最も早いタイムスタンプイベント属性値と、複数のタイムスタンプイベント属性値のうちで最も遅いタイムスタンプイベント属性値との間の最大差を定義する時間間隔値を含む。任意選択的に、テンプレートは複数の連言述語を含み、各連言述語は、複数のイベントオペランドのうちの第１イベントオペランドと、複数のイベントオペランドのうちの第２イベントオペランドとを含む。任意選択的に、複数の連言述語の各々は、第１イベントオペランドおよび第２イベントオペランドの一つ以上のイベント属性値に対し一つ以上の制約を規定する。任意選択的に、複数の連言述語の各々は、第１イベントオペランドおよび第２イベントオペランドが、時間間隔値の期間を有する時間間隔内に連言述語を満たす確率を示す選択率値を有する。
【００４４】
任意選択的に、純粋な連言パターンは次のように定義される。
2020017254.tif 000003
ここで、
ｎは、イベントオペランドの量を表す。
ｅ１…ｅｎは、複数のイベントオペランドを表す。
Ｔ１…Ｔｎは、予め定められた複数のイベントタイプから選択された、複数のイベントオペランドのそれぞれのイベントタイプを表す。
ｃ１，１  ｃ１，２，…，ｃｎ−１，ｎ，ｃｎ，ｎは複数の連言述語を表し、ｃｉ，ｊはｅｉによって表される第１イベントオペランドとｅｊによって表される第２イベントオペランドとの間の連言述語を表す。
Ｗは時間間隔値を表す。
【００４５】
さらに、
Ｓｉ，ｊは、ｃｉ，ｊによって表される連言述語の選択率値であって、ｃｉ，ｊを満たすイベントタイプＴｉを有する第１イベントオペランドｅｉおよびイベントタイプＴｊを有する第２イベントオペランドｅｊを含む部分一致の確率を示す、選択率値を表す。
ｒｉは、Ｔｉによって表されるそれぞれのイベントタイプの到着率を表す。
【００４６】
任意選択的に、Ｓｉ，ｊは、０および１を含めて０と１との間の範囲の値である。
【００４７】
任意選択的に、Ｗの期間を有する時間間隔内に、少なくとも一つのハードウェアプロセッサ１０１によって受信されるタイプＴｉのイベントの予想量はＷｒｉである。
【００４８】
簡潔かつ明確を期して、これ以降、用語「テーブル」はリレーショナルデータベースのテーブルとしても知られる関係を意味するものとして使用される。
【００４９】
再び図２に関連して、本発明の一部の実施形態では、少なくとも一つのプロセッサ１０１は、２０４で、テンプレートからリレーショナルデータベースのための結合クエリを生成する。任意選択的に、結合クエリを生成するステップは、クエリテンプレートを作成するステップを含む。任意選択的に、クエリテンプレートは複数のテーブルを含み、各テーブルは複数のイベントタイプのうちのイベントタイプに対応し、各テーブルは複数のカラムを含み、各カラムは、イベントタイプに関連付けられる複数のイベント属性のうちの一つに関連付けられ、時間間隔値とイベントタイプのそれぞれの到着率との乗算に等しい濃度値を有する。任意選択的に、クエリテンプレートは複数の関係述語を含み、各関係述語は複数のテーブルのうちの第１テーブルおよび複数のテーブルのうちの第２テーブルを含み、かつ等価の連言述語と等価であり、等価の連言述語の第１イベントオペランドは第１テーブルに対応する第１イベントタイプを有し、等価の連言述語の第２イベントオペランドは第２テーブルに対応する第２イベントタイプを有し、関係述語は等価の連言述語の選択率値に等しい関係選択率値を有する。任意選択的に、クエリテンプレートは、全てのカラムを選択することを含む結合クエリのＳＥＬＥＣＴ句と、複数のテーブルを含む結合クエリのＦＲＯＭ句と、複数の関係述語の間に複数のＡＮＤオペランドを含む結合クエリのＷＨＥＲＥ句とを備える。
【００５０】
任意選択的に、クエリテンプレートは次のように定義される。
2020017254.tif 000004
ここで、
Ｒ１，…，Ｒｎは、それぞれのＴ１，…Ｔｎに対応する複数のテーブルを表す。
ｒｃ１，１  ｒｃ１，２，…，ｒｃｎ−１，ｎ，ｒｃｎ，ｎは複数の関係述語を表し、ｒｃｉ，ｊは、Ｒｉによって表される第１テーブルとＲｊによって表される第２テーブルとの間の連言述語を表し、それぞれのｃｉ，ｊと等価である。
【００５１】
本書で使用する場合、用語「濃度」とは、リレーショナルデータベースのテーブルの行の量を指す。Ｒｉの濃度はＷｒｉである。
【００５２】
関係述語ｒｃｉ，ｊの選択率はｆｉ，ｊによって表される。関係述語ｒｃｉ，ｊが存在しない場合、ｆｉ，ｊは１に等しいと定義され、それ以外の場合、ｆｉ，ｊはそれぞれのｓｉ，ｊに等しいと定義される。
【００５３】
再び図２に関連して、２０５で少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、結合クエリのコスト関数を選択する。任意選択的に、結合クエリの計算コストは、複数のイベントストリームからの複数のイベントとテンプレートとの間のマッチングの計算コストと等価である。任意選択的に、結合クエリのための実行計画は、複数のノードを有する結合演算子のツリーを含む。そのような結合演算子のツリーにおいて、リーフノードは子を持たないノードであり、内部ノードは少なくとも一つの子を有するノードである。任意選択的に、複数のノードのうちの複数のリーフノードは各々、複数のテーブルのうちのテーブルを表し、複数のノードのうちの複数の内部ノードは各々、内部ノードの一つ以上の子によって表される一つ以上のテーブルを結合することによって生成されるテーブルを表す。少なくとも一つのハードウェアプロセッサ１０１は、一つ以上の特定されたコストメトリック、例えばメモリ量およびデータベース演算量を反映する、当業者で公知のコスト関数を選択することができる。以下でいくつかの可能なコスト関数について記載する。一部の実施形態では、少なくとも一つのハードウェアプロセッサ１０１が、それぞれの実施形態に対して定義されるコスト関数を選択する。
【００５４】
本発明の一部の実施形態では、少なくとも一つのハードウェアプロセッサ１０１は、順序ベースの評価計画を使用してイベントのパターンを検出するように制約され、複数のパターンはＯによって表される定義された連続的順序で評価される。ここで、Ｏ＝（Ｔｐ１，Ｔｐ２，…，Ｔｐｎ）であり、ｐｉ∈［１，ｎ］である。そのような実施形態では、イベントのパターンを検出するための可能なコスト関数は、少なくとも一つのハードウェアプロセッサ１０１に結合されたデジタルメモリ内に共存する部分一致の数を反映する。そのようなコスト関数の計算は、複数のイベントストリームからの複数のイベントの複数の到着率、および複数の連言述語の複数の選択率値に基づくことができる。
【００５５】
任意選択的に、Ｏに従ってパターン評価中に、長さｋ（ここで１＜＝ｋ＜＝ｎ）の部分一致の予想量は、ＰＭ（ｋ）によって表され、次式によって与えられる。
2020017254.tif 000005
【００５６】
したがって、任意選択的に、連続的順序Ｏを使用する、複数のイベントストリームの複数のイベントとパターンとの間のマッチングのコスト関数は、Ｃｏｓｔｏｒｄ（Ｏ）によって表され、次式によって与えられる。
2020017254.tif 000006
【００５７】
イベントのパターンを検出する順序ベースの評価計画は、結合演算子の左深ツリーを含む結合クエリ実行計画を使用することと等価である。左深ツリーは、各内部ノードがリーフノードである少なくとも一つの子を有しかつリーフノードではない子を最大で一つ有する、深いツリーである。結合クエリ計画が結合演算子の左深ツリーを含む場合、複数の内部ノードの各内部ノードは、複数のテーブルのうちの一つのテーブルと、複数のテーブルのうちの別のテーブルまたは別の結合演算によって生成されたテーブルのいずれかと間の結合演算を表す。したがって、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、各々が結合演算子の左深ツリーを含む複数の結合クエリ実行計画から、結合クエリを実行するための好適な計画を特定するように制約される。
【００５８】
｜Ｒ｜はＲによって表されるテーブルの濃度を表す。結合クエリを実行するための可能なコスト関数は、結合クエリの実行計画に従って結合クエリ実行計画の実行中に生成される中間タプル量を計算する。任意選択的に、ＲｉおよびＲｊによって表される二つのテーブルを結合するコストは、Ｃ（Ｒｉ，Ｒｊ）によって表され、次のように定義される。
2020017254.tif 000007
Ｌは左深ツリーを表し、｛ｉ１，ｉ２，…．ｉｎ｝は、入力テーブルが左深ツリーＬに従って結合される順序を表す。
Ｐｋは、Ｌによって最初のｋのテーブルを結合する結果を表す。
Ｃ１は、テーブルＲｉ，ｊからの初期選択のコストを表し、任意選択的に次式によって計算される。
2020017254.tif 000008
【００５９】
Ｌに従って結合クエリ実行計画を実行するコストは次式によって表される。
2020017254.tif 000009
【００６０】
ＣｏｓｔＬＤ１（Ｌ）における再帰を開き、かつ一部のパラメータをイベントのパターンの等価パラメータに置き換えることによって、ＣｏｓｔＬＤ１（Ｌ）はＣｏｓｔｏｒｄ（Ｏ）と等しく、特に次のようになることが分かった。
2020017254.tif 000010
【００６１】
任意選択的に、２０５で、少なくとも一つのハードウェアプロセッサは、複数のテーブル間の複数の結合演算の実行順序を示す複数のテーブルを含む、結合されたテーブルの順序付きリストを含む結合クエリの実行計画のコスト関数を選択する。
【００６２】
次に図３も参照すると、本発明の一部の実施形態に係る、左深ツリー解決法のコスト関数を計算するための操作の任意の流れを概略的に表すフローチャート３００が示されている。そのような実施形態では、少なくとも一つのハードウェアプロセッサが２０５で選択するコスト関数は、次のようなものである。すなわち、結合されたテーブルの順序付きリストを含む結合クエリのコスト関数の計算は、次のように複数の反復の各々でコスト項を計算することによって、複数のコスト項を計算することを含む。３０１で、複数の反復における最初の反復で、複数のコスト項の第１コスト項が任意選択的に、順序付きリストの第１の結合されたテーブルの第１濃度値と、第１結合テーブルに等しい第１テーブルおよび第２結合テーブルに等しい第２テーブルを含む複数の関係述語の第１関係述語の関係選択率値との乗算によって生成される。３０２で、累積結合コスト値は任意選択的にゼロに設定され、３０３で、次の結合テーブルが任意選択的に前に結合されたテーブルのリストに追加され、３０４で、第１結合テーブルは任意選択的に、後に続く反復で、前の結合テーブルとして特定される。
【００６３】
次に、複数の反復のうちの複数の他の反復の各々で、３１１で、順序付きリストにおいて前の結合テーブルに続く次の結合テーブルが任意選択的に選択され、３１２で、次の結合テーブルが前に結合されたテーブルのリストに任意選択的に追加される。３１３で、複数の濃度値の積を計算することによって、濃度項が任意選択的に作成され、各濃度値は、前に結合されたテーブルの一つのリストの濃度値である。３１４で、関連する複数の関係述語は任意選択的に複数の関係述語から選択され、関連述語の各々は、前に結合されたテーブルのリストから選択された第１テーブル、および前に結合されたテーブルのリストから選択された第２テーブルを有し、第１テーブルは前に結合されたテーブルのリストに、第２テーブルより早く追加されており、３１５で、複数の関連述語の関連する複数の選択率値の積を計算することによって、選択率項が任意選択的に作成される。３１６で、複数のコスト項の新しいコスト項は任意選択的に、濃度項と選択率項の乗算によって作成される。複数のコスト項を作成した後、３２１で、複数のコスト項の和を計算することによって、計算コスト値が任意選択的に計算される。
【００６４】
本発明の一部の実施形態では、少なくとも一つのハードウェアプロセッサ１０１は、イベントのパターンを検出するために順序ベースの評価計画を使用するように制約されない。そのような実施形態では、評価の順序は非逐次的であり、ブッシーツリー構造を有し、一つ以上の評価を並行して実行することができる。そのような実施形態では、実行計画のブッシーツリー構造は、各々が複数のイベントタイプのうちの一つのイベントを収集する、複数のリーフノードを含む。タイプＴｉのイベントを収集しｌによって表されるリーフノードの場合、部分一致の予想量はＰＭ（ｌ）によって表され、時間間隔値：ＰＭ（ｌ）＝Ｗ・ｒｉの期間を有する時間間隔内に到着するタイプＴｉのイベント量に等しい。ブッシーツリーの内部ノードの部分一致の予想量の推定値を計算するために、内部ノードの複数の子ノードの各々のコスト関数値に、複数の連言述語から選択され内部ノードによって検証された複数の検証済み述語の総選択率を乗算することができる。再帰を開くことにより、Ｃｏｓｔｔｒｅｅ（Ｔ）＝ΣＮ∈ｎｏｄｅｓ（Ｔ）ＰＭ（Ｎ）によって表されるブッシーツリーＴのコスト関数がもたらされる。
【００６５】
イベントのパターンを検出する非逐次的評価計画は、結合演算子のブッシー結合ツリーを含む結合クエリ実行計画を使用することと等価である。したがって、少なくとも一つのハードウェアプロセッサ１０１は、ツリーのトポロジーに対する制約無しで、各々が結合演算のツリーを含む複数の結合クエリ実行計画から結合クエリを実行するための好適な計画を特定することができる。ブッシー結合ツリーでＪＮによって表されるツリーノードを評価するコスト関数はＣ（ＪＮ）によって表され、任意選択的に次式によって定義される。
2020017254.tif 000011
【００６６】
任意選択的に、ＪＴによって表されるツリーを含む実行計画に従って結合クエリを実行するためのコスト関数は、ＣｏｓｔＢＪ（ＪＴ）によって表され、次式の通り、ＪＴの複数のノードの複数のコスト関数の和である。
2020017254.tif 000012
【００６７】
式を開き、幾つかのパラメータをイベントのパターンの等価パラメータに置換することによって、Ｃｏｓｔｔｒｅｅ（Ｔ）はＣｏｓｔＢＪ（ＪＴ）に等しくなり、特に次のようになる。
2020017254.tif 000013
【００６８】
任意選択的に、２０５で、少なくとも一つのハードウェアプロセッサは、複数のテーブル間の複数の結合演算の実行の順序を示す複数のテーブルを含む、一組の結合されたテーブルを含む結合クエリの実行計画のコスト関数を選択する。実行の順序は逐次的であってもよく、非逐次的であってもよい。
【００６９】
次に図４も参照すると、本発明の一部の実施形態に係る、一般ツリー解決法のコスト関数を計算するための操作４００の任意の流れを概略的に表すフローチャートが示されている。そのような実施形態では、２０５で、少なくとも一つのハードウェアプロセッサが選択するコスト関数は、結合演算のツリーを含む結合クエリのコスト関数の計算が、４０１で、第１の複数の濃度値（各濃度値は複数のテーブルのうちの一つのテーブルの濃度値である）の和を計算することによってリーフコスト項を生成することを含むように構成される。任意選択的に、複数の内部コスト項は、次のように複数の反復の各々で内部コスト項を計算することによって計算される。４１１で、内部ノードは任意選択的に複数の内部ノードから選択され、４１２で、結合演算子のツリーの関連サブツリーは任意選択的に、関連サブツリーが選択された内部ノードに等しいルートノードを有しかつ関連サブツリーが複数の関連リーフノードを含むように特定される。任意選択的に、４１３で、複数の関連リーフノードは複数の関連ノードから選択され、かつ４１４で、複数の関連述語は任意選択的に、各々が複数の関連リーフノードにおける第１の関連ノードによって表される第１テーブルおよび複数の関連リーフノードにおける第２の関連ノードによって表される第２テーブルを有する、複数の関係述語から選択される。４１５で、内部選択率項は任意選択的に、複数の関連述語の複数の関連選択率値の積を計算することによって生成される。任意選択的に、４１６で、内部濃度項は、各々が複数のテーブルのうちの一つのテーブル（各テーブルは複数のリーフノードの一つによって表される）の濃度値である第２の複数の濃度値の積を計算することによって生成され、かつ４１７で、複数の内部コスト項のうちの内部コスト項は任意選択的に、内部選択率項に内部濃度項を乗算することによって生成される。リーフコスト項および複数の内部コスト項を生成した後、４２１で、計算コスト値は任意選択的に、複数の内部コスト項およびリーフコスト項の和を計算することによって計算される。
【００７０】
次に、再び図２を参照する。２０６で、少なくとも一つのハードウェアプロセッサは任意選択的に、２０５で選択されたコスト関数の最小値に従って結合クエリを実行するための好適な計画を特定する。任意選択的に、結合クエリを実行するための好適な計画は、複数のノードの複数のリーフノードが各々複数のテーブルのうちのテーブルを表し、かつ複数のノードの複数の内部ノードが各々、内部ノードの一つ以上の子によって表される一つ以上のテーブルを結合することによって生成されるテーブルを表すように、各々が複数のノードを有する結合演算子のツリーを含む複数の実行計画から特定される。任意選択的に、少なくとも一つのハードウェアプロセッサは、結合クエリを実行するための好適な計画を特定するために、当業者で公知の結合クエリ計画生成方法を実行する。そのような結合クエリ計画生成方法は、入力として結合クエリおよびコスト関数を受け取り、コスト関数の最小値に従って結合クエリを評価するための好適な計画を返す。
【００７１】
２０７で、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、好適な計画の複数のデータベース演算を複数のパターンの順序集合に変換することによって、好適な計画に従って複数のパターンの順序集合を生成する。任意選択的に、複数のデータベース演算の各々は、結合演算および選択演算を含む群から選択される。
【００７２】
次に図５も参照すると、本発明の一部の実施形態に係る、結合クエリ実行計画を変換するための操作５００の任意の流れを概略的に表すフローチャートが示されている。そのような実施形態では、少なくとも一つのハードウェアプロセッサ１０１は次のように複数のパターンを生成する。５０１で、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、複数のデータベース演算の各結合演算に対し、結合演算の第１テーブルに対応する第１イベントタイプを有する第１イベントオペランドおよび結合演算の第２テーブルに対応する第２イベントタイプを有する第２イベントオペランドを含む、複数の連言述語のうちの連言述語を選択する。５０２で、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、複数のデータベース演算の各選択演算に対し、選択演算のテーブルに対応するイベントタイプを有する複数のイベントオペランドのうちのイベントオペランドを含むパターンを生成する。複数のパターンを生成した後、５０３で、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、データベース演算の順序集合におけるデータベース演算のそれぞれの順序に従って、複数のパターンを順序付ける。
【００７３】
次に、再び図２を参照する。２０８で、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、複数のパターンと複数のイベントとの間の複数の一致を検出するための入力として、順序集合を使用する。複数のパターンと複数のイベントとの間の複数の一致を検出することにより、複数のイベントストリームからの複数のイベントとテンプレートとの間の一致が検出される。任意選択的に、少なくとも一つのハードウェアプロセッサ１０１は、例えばテンプレートの時間間隔より著しく長い期間にわたって複数のイベントが受信される場合、複数の検出反復で順序集合を使用して、複数のイベントストリームからの複数のイベント間の一つ以上の一致を検出する。
【００７４】
本発明の一部の実施形態では、テンプレートは複合テンプレートであり、すなわちテンプレートは純粋な連言テンプレートではない。そのような実施形態では、システム１００は任意選択的に以下の方法を実現する。
【００７５】
次に図６を参照すると、本発明の一部の実施形態に係る、イベントの複雑なパターンを検出するための操作の任意の流れ６００を概略的に示すフローチャートが示されている。そのような実施形態では、少なくとも一つのハードウェアプロセッサは、２０１で、検出すべきイベントのパターンを定義する複合テンプレートを受信し、結合クエリを生成する前に、６０２で、任意選択的に複合テンプレートを一つ以上の純粋な連言パターンに変換する。任意選択的に、少なくとも一つのハードウェアプロセッサ１０１は一つ以上の純粋な連言パターンの各々を、２０４で結合クエリを生成し、２０５でコスト関数を選択し、２０６で好適な計画を識別し、２０７で複数のパターンの順序集合を生成し、かつ２０８で順序集合を使用するためのテンプレートとして使用する。
【００７６】
例えば、一部の実施形態では、複合テンプレートは、ＡＮＤ演算子によって接続される代わりに、複数のイベントオペランド間のイベント順序を定義するＳＥＱＵＥＮＣＥ演算子によって接続された複数のイベントオペランドを含む。そのような実施形態では、複合テンプレートの純粋な連言パターンへの変換は任意選択的に、複数のイベントオペランドをＡＮＤオペランドによって接続し、複数のイベントオペランドのうちの第１イベントオペランドのタイムスタンプイベント属性の第１タイムスタンプ値が、イベント順序に従って複数のイベントオペランドにおける第１イベントオペランドのすぐ後に続く第２イベントオペランドのタイムスタンプイベント属性の第２タイムスタンプ値より低い場合、各々が真値を受け取る複数の時間述語を生成し、かつ複数の時間述語を複数の連言述語に追加することを含む。
【００７７】
本発明の一部の実施形態では、複合テンプレートはさらに、複数のイベントオペランドのうちの少なくとも一つのイベントオペランドの少なくとも一つのイベントタイプに適用されるＫＬ演算子を含む。任意選択的に、複合テンプレートは真値を有する連言述語を含む。そのような実施形態では、複合テンプレートを純粋な連言パターンに変換するステップは、複数のイベントオペランドにおいて少なくとも一つのイベントタイプの各々を、それぞれのイベントタイプの到着率に時間間隔値を乗算して指数を生成し、２に指数を累乗して累乗項を生成し、累乗項を時間間隔値で除算することによって計算された、それぞれの変換後の到着率を有するそれぞれの変換後のイベントタイプに置換することを含む。結果的に得られる変換後の到着率は複数のイベントタイプの他のどの到着率よりかなり高く、変換後のイベントタイプのイベント処理は好適な実行計画の最後のステップに延期される可能性が高くなり、それは元の複雑なパターンを評価するための望ましい戦略である。好適な計画を特定した後、少なくとも一つのハードウェアプロセッサ１０１は任意選択的に、好適な計画における少なくとも一つの変換後のイベントタイプの各々をそれぞれの少なくとも一つのイベントタイプに置換し、任意選択的に好適な計画のそれぞれの段階でＫＬ演算子を追加する。
【００７８】
本発明の一部の実施形態では、複合テンプレートは、ＡＮＤ演算子によってではなく、第１の複数のＡＮＤおよびＯＲ演算子によって接続された複数のイベントオペランドを含む。そのような実施形態では、複合テンプレートを純粋な連言パターンに変換するステップは、第１の複数のＡＮＤおよびＯＲ演算子を、複数の純粋な連言パターンを含む選言標準形に適合する第２の複数のＡＮＤ演算子に変換することを含む。複雑なパターンは、複数の純粋な連言パターンから生成された複数の実行計画に従って、一致の和集合に従って、複数のイベントストリームからの複数のイベントとマッチングされる。
【００７９】
本発明の一部の実施形態では、複雑なパターンは、複数のイベントオペランドのうちの少なくとも一つに適用されるＮＯＴ演算子を含む。本発明によれば、少なくとも一つのハードウェアプロセッサ１０１は、複雑なパターンの正の部分を特定し、それをパターンとして使用する。複数のパターンの順序集合を特定した後、少なくとも一つのハードウェアプロセッサ１０１は、少なくとも一つのイベントオペランドの全ての正のイベントを受け取った後、少なくとも一つのイベントオペランドの一つ以上の否定演算を追加する。
【００８０】
再び図２を参照する。本書で使用する場合、検出待ち時間とは、完全パターン一致の最後のイベントの到着時間と、完全パターン一致の検出を示す指示出力の報告時間との間の差である。既存のアプリケーションの中には、実時間要件を有し、検出待ち時間値の低減を要求するものもある。システムの待ち時間とシステムのスループットとの間には一般的にトレードオフが存在し、一方の向上は他方の犠牲の上に成り立ち、スループットを最大にするように実行計画が最適化されると、パターンにおける最後のイベントは実行計画における最後のイベントにならないかもしれない。パターンにおける最後のイベントが受け入れられた後、システムは依然として計画の追加部分を実行する必要があり、結果的に完全一致の検出は遅くなる。本発明の一部の実施形態では、２０５で少なくとも一つのハードウェアプロセッサ１０１によって選択されるコスト関数は、計画実行の予想待ち時間を反映し、したがってシステム１００は、パターンの順序集合を使用してイベントのパターンを検出することができ、結果的に最小限の検出待ち時間値が得られる。
【００８１】
部分一致のために複数のイベントストリームからイベントをいかに選択するかを指定する、イベント選択戦略は二つ以上存在する。一つの既存の戦略は、一致するまでスキップする（ｓｋｉｐ‐ｔｉｌｌ‐ａｎｙ‐ｍａｔｃｈ）方式であり、それはイベントがパターンとの無制限量の一致に関わることを可能にする（完全一致）。第２の既存の戦略は、次の一致までスキップする（ｓｋｉｐ‐ｔｉｌｌ‐ｎｅｘｔ‐ｍａｔｃｈ）方式であり、この場合、イベントは一回の完全一致にしか現れない。第３の既存の戦略は厳格な連続性であり、複数のイベントは複数のイベントストリームで連続していなければならず、すなわち複数のイベント間に他のイベントは現れない。第４の既存の戦略はパーティション連続性であり、厳格な連続性の多少緩和されたバージョンであり、複数のイベントストリームを特定された条件に従って分割し、共通のパーティションに位置する複数のイベントの全てのイベントが連続していることを要求する。一部の実施形態では、２０５で少なくとも一つのハードウェアプロセッサ１０１によって選択されたコスト関数は、イベント選択戦略によって課せられる一つ以上の制約を反映する。
【００８２】
本発明の様々な実施形態の記載は、説明の目的のために与えられたものであり、開示された実施形態に限定したものであることや網羅したものであることを意図しない。多くの修正及び変形が、記載された実施形態の範囲及び精神から逸脱せずに当業者に明らかであるだろう。本明細書に使用される用語法は、実施形態の原理、市場で見出される技術に対する技術改良もしくは実際の適応を最良に説明するため、又は本明細書に開示された実施形態を他の当業者に理解させるために選択される。
【００８３】
本出願から成熟する特許の存続期間の期間中には、多くの関連するイベントタイプが開発されることが予想され、イベントタイプの用語の範囲は、すべてのそのような新しい技術を先験的に包含することが意図される。
【００８４】
本明細書中で使用される用語「約」は、±１０％を示す。
【００８５】
用語「含む／備える（ｃｏｍｐｒｉｓｅｓ、ｃｏｍｐｒｉｓｉｎｇ、ｉｎｃｌｕｄｅｓ、ｉｎｃｌｕｄｉｎｇ）」、「有する（ｈａｖｉｎｇ）」、およびそれらの同根語は、「含むが、それらに限定されない（ｉｎｃｌｕｄｉｎｇ  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」ことを意味する。この用語は、「からなる（ｃｏｎｓｉｓｔｉｎｇ  ｏｆ）」および「から本質的になる（ｃｏｎｓｉｓｔｉｎｇ  ｅｓｓｅｎｔｉａｌｌｙ  ｏｆ）」を包含する。
【００８６】
表現「から本質的になる」は、さらなる成分および／または工程が、特許請求される組成物または方法の基本的かつ新規な特徴を実質的に変化させない場合にだけ、組成物または方法がさらなる成分および／または工程を含み得ることを意味する。
【００８７】
本明細書中で使用される場合、単数形態（「ａ」、「ａｎ」および「ｔｈｅ」）は、文脈がそうでないことを明確に示さない限り、複数の参照物を包含する。例えば、用語「化合物（ａ  ｃｏｍｐｏｕｎｄ）」または用語「少なくとも１つの化合物」は、その混合物を含めて、複数の化合物を包含し得る。
【００８８】
用語「例示的」は、本明細書では「例（ｅｘａｍｐｌｅ，ｉｎｓｔａｎｃｅ又はｉｌｌｕｓｔｒａｔｉｏｎ）として作用する」ことを意味するために使用される。「例示的」として記載されたいかなる実施形態も必ずしも他の実施形態に対して好ましいもしくは有利なものとして解釈されたりかつ／または他の実施形態からの特徴の組み入れを除外するものではない。
【００８９】
用語「任意選択的」は、本明細書では、「一部の実施形態に与えられるが、他の実施形態には与えられない」ことを意味するために使用される。本発明のいかなる特定の実施形態も対立しない限り複数の「任意選択的」な特徴を含むことができる。
【００９０】
本開示を通して、本発明の様々な態様が範囲形式で提示され得る。範囲形式での記載は単に便宜上および簡潔化のためであり、本発明の範囲に対する柔軟性のない限定として解釈すべきでないことを理解しなければならない。従って、範囲の記載は、具体的に開示された可能なすべての部分範囲、ならびに、その範囲に含まれる個々の数値を有すると見なさなければならない。例えば、１〜６などの範囲の記載は、具体的に開示された部分範囲（例えば、１〜３、１〜４、１〜５、２〜４、２〜６、３〜６など）、ならびに、その範囲に含まれる個々の数値（例えば、１、２、３、４、５および６）を有すると見なさなければならない。このことは、範囲の広さにかかわらず、適用される。
【００９１】
数値範囲が本明細書中で示される場合には常に、示された範囲に含まれる任意の言及された数字（分数または整数）を含むことが意味される。第１の示された数字および第２の示された数字「の範囲である／の間の範囲」という表現、および、第１の示された数字「から」第２の示された数「まで及ぶ／までの範囲」という表現は、交換可能に使用され、第１の示された数字と、第２の示された数字と、その間のすべての分数および整数とを含むことが意味される。
【００９２】
明確にするため別個の実施形態の文脈で説明されている本発明の特定の特徴が、単一の実施形態に組み合わせて提供されることもできることは分かるであろう。逆に、簡潔にするため単一の実施形態で説明されている本発明の各種の特徴は別個にまたは適切なサブコンビネーションで、あるいは本発明の他の記載される実施形態において好適なように提供することもできる。種々の実施形態の文脈において記載される特定の特徴は、その実施形態がそれらの要素なしに動作不能である場合を除いては、それらの実施形態の不可欠な特徴であると見なされるべきではない。
【００９３】
本明細書で挙げた刊行物、特許および特許出願はすべて、個々の刊行物、特許および特許出願が各々あたかも具体的にかつ個々に引用提示されているのと同程度に、全体を本明細書に援用するものである。さらに、本願で引用または確認したことは本発明の先行技術として利用できるという自白とみなすべきではない。節の見出しが使用されている程度まで、それらは必ずしも限定であると解釈されるべきではない。
それに加えて、本願のいかなる優先権書類も、その全体を参照によってここに組み入れられる。
【図１】
2020017254.tif 000014
【図２】
2020017254.tif 000015
【図３】
2020017254.tif 000016
【図４】
2020017254.tif 000017
【図５】
2020017254.tif 000018
【図６】
2020017254.tif 000019